usr/src/common/mdesc/mdesc_walkdag.c

   1 /*
   2  * CDDL HEADER START
   3  *
   4  * The contents of this file are subject to the terms of the
   5  * Common Development and Distribution License (the "License").
   6  * You may not use this file except in compliance with the License.
   7  *
   8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
   9  * or http://www.opensolaris.org/os/licensing.
  10  * See the License for the specific language governing permissions
  11  * and limitations under the License.
  12  *
  13  * When distributing Covered Code, include this CDDL HEADER in each
  14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
  15  * If applicable, add the following below this CDDL HEADER, with the
  16  * fields enclosed by brackets "[]" replaced with your own identifying
  17  * information: Portions Copyright [yyyy] [name of copyright owner]
  18  *
  19  * CDDL HEADER END
  20  */
  21
  22 /*
  23  * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
  24  * Use is subject to license terms.
  25  */
  26
  27 #pragma ident   "%Z%%M% %I%     %E% SMI"
  28
  29 #include <sys/types.h>
  30 #include <sys/param.h>
  31 #ifdef _KERNEL
  32 #include <sys/systm.h>
  33 #else
  34 #include <string.h>
  35 #include <strings.h>
  36 #endif
  37
  38 #include <sys/mdesc.h>
  39 #include <sys/mdesc_impl.h>
  40
  41 static int
  42 mdl_walk_dag(md_impl_t *, mde_cookie_t, mde_cookie_t, mde_str_cookie_t,
  43     mde_str_cookie_t, uint8_t *, md_walk_fn_t, void *, int);
  44
  45
  46 /*
  47  * Walk the machine description directed graph from a starting
  48  * node searching for nodes of a given node name and using a
  49  * given arc type.  Call a callback function for each node found.
  50  * Each node will be visited only once.
  51  *
  52  * Input                Description
  53  * -------------------  ----------------------------------------
  54  * md_t *               Pointer to md session
  55  * mde_cookie_t         Index of the starting node
  56  * mde_str_cookie_t     Node name cookie of the nodes to call
  57  *                      the walk function
  58  * mde_str_cookie_t     Arc name cookie of the path to follow
  59  * md_walk_fn_t         The function to call for each node
  60  * void *               Private data to pass to the walker function
  61  *
  62  */
  63 int
  64 md_walk_dag(md_t *ptr, mde_cookie_t startnode,
  65     mde_str_cookie_t node_name_cookie, mde_str_cookie_t arc_name_cookie,
  66     md_walk_fn_t func, void *private)
  67 {
  68         int             res;
  69         uint8_t         *seenp;
  70         md_impl_t       *mdp;
  71         mde_cookie_t    start;
  72
  73         mdp = (md_impl_t *)ptr;
  74         if (mdp == NULL) {
  75                 return (-1);
  76         }
  77
  78         /*
  79          * Possible the caller was lazy and didn't check the
  80          * validitiy of either the node name or the arc name
  81          * on calling ... in which case fail to find any
  82          * nodes.
  83          * This is distinct, from a fail (-1) since we return
  84          * that nothing was found.
  85          */
  86         if (node_name_cookie == MDE_INVAL_STR_COOKIE ||
  87             arc_name_cookie == MDE_INVAL_STR_COOKIE) {
  88                 return (0);
  89         }
  90
  91         /*
  92          * if we want to start at the top, start at index 0
  93          */
  94         start = startnode;
  95         if (start == MDE_INVAL_ELEM_COOKIE) {
  96                 start = 0;
  97         }
  98
  99         /*
 100          * Scan from the start point until the first node.
 101          */
 102         while (start < mdp->element_count &&
 103             MDE_TAG(&mdp->mdep[start]) == MDET_NULL) {
 104                 start++;
 105         }
 106
 107         /*
 108          * This was a bogus start point if no node found
 109          */
 110         if (MDE_TAG(&mdp->mdep[start]) != MDET_NODE) {
 111                 return (-1);    /* illegal start node specified */
 112         }
 113
 114         /*
 115          * Allocate a recursion detection structure so we only visit
 116          * each node once.
 117          */
 118         seenp = (uint8_t *)mdp->allocp(mdp->element_count);
 119         if (seenp == NULL) {
 120                 return (-1);
 121         }
 122         (void) memset(seenp, 0, mdp->element_count);
 123
 124         /*
 125          * Now build the list of requested nodes.
 126          */
 127         res = mdl_walk_dag(mdp, MDE_INVAL_ELEM_COOKIE, start,
 128             node_name_cookie, arc_name_cookie, seenp, func, private, 0);
 129
 130         mdp->freep(seenp, mdp->element_count);
 131
 132         return (res >= 0 ? 0 : res);
 133 }
 134
 135
 136 static int
 137 mdl_walk_dag(md_impl_t *mdp, mde_cookie_t parentidx, mde_cookie_t nodeidx,
 138     mde_str_cookie_t node_name_cookie, mde_str_cookie_t arc_name_cookie,
 139     uint8_t *seenp, md_walk_fn_t func, void *private, int level)
 140 {
 141         int             result;
 142         md_element_t    *mdep;
 143
 144         /* Get the node element from the session */
 145         mdep = &(mdp->mdep[nodeidx]);
 146
 147         /* see if cookie is infact a node */
 148         if (MDE_TAG(mdep) != MDET_NODE) {
 149                 return (MDE_WALK_ERROR);
 150         }
 151
 152         /* have we been here before ? */
 153         if (seenp[nodeidx]) {
 154                 return (MDE_WALK_NEXT);
 155         }
 156         seenp[nodeidx] = 1;
 157
 158 #ifdef  DEBUG_LIBMDESC
 159         {
 160                 int x;
 161                 for (x = 0; x < level; x++) {
 162                         printf("-");
 163                 }
 164                 printf("%d (%s)\n", nodeidx,
 165                     (char *)(mdp->datap + MDE_NAME(mdep)));
 166         }
 167 #endif
 168
 169         /* is this node of the type we seek ? */
 170         if (MDE_NAME(mdep) == node_name_cookie) {
 171                 /*
 172                  * Yes.  Call the callback function.
 173                  */
 174                 result = (func)((md_t *)mdp, parentidx, nodeidx, private);
 175                 if (result != MDE_WALK_NEXT) {
 176                         return (result);
 177                 }
 178         }
 179
 180         /*
 181          * Simply walk the elements in the node.
 182          * if we find a matching arc, then recursively call
 183          * the subordinate looking for a match
 184          */
 185         result = MDE_WALK_NEXT;
 186         for (mdep++; MDE_TAG(mdep) != MDET_NODE_END; mdep++) {
 187                 if (MDE_TAG(mdep) == MDET_PROP_ARC &&
 188                     MDE_NAME(mdep) == arc_name_cookie) {
 189                         /*
 190                          * The current node becomes the parent node, and the
 191                          * arc index is the new current node.
 192                          */
 193                         result = mdl_walk_dag(mdp, nodeidx, mdep->d.prop_idx,
 194                             node_name_cookie, arc_name_cookie, seenp, func,
 195                             private, level+1);
 196                         if (result != MDE_WALK_NEXT) {
 197                                 /* The walk is complete or terminated. */
 198                                 return (result);
 199                         }
 200                 }
 201         }
 202
 203         return (result);
 204 }