common/mdesc/mdesc_scandag.c

	mdesc_scandag.c revision 26cf27f05670b1ca90e4a07802cba858cb358690
/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License, Version 1.0 only
 * (the "License").  You may not use this file except in compliance
 * with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */
/*
 * Copyright 2005 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

#pragma ident   "%Z%%M% %I% %E% SMI"

#include <sys/types.h>
#include <sys/param.h>
#ifdef _KERNEL
#include <sys/systm.h>
#else
#include <string.h>
#include <strings.h>
#endif

#include <sys/mdesc.h>
#include <sys/mdesc_impl.h>

static int
mdl_scan_dag(md_impl_t *mdp,
    int nodeidx,
    mde_str_cookie_t node_cookie,
    mde_str_cookie_t arc_cookie,
    uint8_t *dseenp,
    int *idxp,
    mde_cookie_t *stashp,
    int level);


int
md_scan_dag(md_t *ptr,
    mde_cookie_t startnode,
    mde_str_cookie_t node_name_cookie,
    mde_str_cookie_t arc_name_cookie,
    mde_cookie_t *stashp)
{
    int res;
    int idx;
    uint8_t *seenp;
    md_impl_t *mdp;
    int start;

    mdp = (md_impl_t *)ptr;

    /*
     * Possible the caller was lazy and didn't check the
     * validitiy of either the node name or the arc name
     * on calling ... in which case fail to find any
     * nodes.
     * This is distinct, from a fail (-1) since we return
     * that nothing was found.
     */

    if (node_name_cookie == MDE_INVAL_STR_COOKIE ||
        arc_name_cookie == MDE_INVAL_STR_COOKIE) return 0;

    /*
     * if we want to start at the top, start at index 0
     */

    start = (int)startnode;
    if (start == MDE_INVAL_ELEM_COOKIE) start = 0;

    /*
     * Scan from the start point until the first node.
     */
    while (MDE_TAG(&mdp->mdep[start]) == MDET_NULL) start++;

    /*
     * This was a bogus start point if no node found
     */
    if (MDE_TAG(&mdp->mdep[start]) != MDET_NODE) {
        return (-1);    /* illegal start node specified */
    }

    /*
     * Allocate a recursion mask on the local stack fail
     * if we can't allocate the recursion detection.
     */
    seenp = (uint8_t *)mdp->allocp(mdp->element_count);
    if (seenp == NULL)
        return (-1);
    (void) memset(seenp, 0, mdp->element_count);

    /*
     * Now build the list of requested nodes.
     */
    idx = 0;
    res = mdl_scan_dag(mdp, start,
        node_name_cookie, arc_name_cookie,
        seenp, &idx, stashp, 0);

    mdp->freep(seenp, mdp->element_count);

    return (res >= 0 ? idx : res);
}


static int mdl_scan_dag(md_impl_t *mdp,
    int nodeidx,
    mde_str_cookie_t node_name_cookie,
    mde_str_cookie_t arc_name_cookie,
    uint8_t *seenp,
    int *idxp,
    mde_cookie_t *stashp,
    int level)
{
    md_element_t *mdep;

    mdep = &(mdp->mdep[nodeidx]);

    /* see if cookie is infact a node */
    if (MDE_TAG(mdep) != MDET_NODE)
        return (-1);

    /* have we been here before ? */
    if (seenp[nodeidx])
        return (0);
    seenp[nodeidx] = 1;

    /* is this node of the type we seek ? */

#ifdef  DEBUG_LIBMDESC
    {
    int x;
    for (x = 0; x < level; x++)
        printf("-");
    printf("%d (%s)\n", nodeidx, (char *)(mdp->datap + MDE_NAME(mdep)));
    }
#endif

    if (MDE_NAME(mdep) == node_name_cookie) {
        /* record the node in the list and keep searching */
        if (stashp != NULL) {
            stashp[*idxp] = (mde_cookie_t)nodeidx;
        }
        (*idxp)++;
#ifdef  DEBUG_LIBMDESC
        printf("\t* %d\n", *idxp);
#endif
    }

    /*
     * Simply walk the elements in the node.
     * if we find a matching arc, then recursively call
     * the subordinate looking for a match
     */

    for (mdep++; MDE_TAG(mdep) != MDET_NODE_END; mdep++) {
        if (MDE_TAG(mdep) == MDET_PROP_ARC &&
            MDE_NAME(mdep) == arc_name_cookie) {
            int res;

            res = mdl_scan_dag(mdp,
                (int)mdep->d.prop_idx,
                node_name_cookie,
                arc_name_cookie,
                seenp, idxp, stashp, level+1);

            if (res == -1)
                return (res);
        }
    }

    return (0);
}