xref: /illumos-gate/usr/src/common/mdesc/mdesc_walkdag.c (revision c40a6cd785e883b3f052b122c332e21174fc1871)
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 #include <sys/types.h>
28 #include <sys/param.h>
29 #ifdef _KERNEL
30 #include <sys/systm.h>
31 #else
32 #include <string.h>
33 #include <strings.h>
34 #endif
35 
36 #include <sys/mdesc.h>
37 #include <sys/mdesc_impl.h>
38 
39 static int
40 mdl_walk_dag(md_impl_t *, mde_cookie_t, mde_cookie_t, mde_str_cookie_t,
41     mde_str_cookie_t, uint8_t *, md_walk_fn_t, void *, int);
42 
43 
44 /*
45  * Walk the machine description directed graph from a starting
46  * node searching for nodes of a given node name and using a
47  * given arc type.  Call a callback function for each node found.
48  * Each node will be visited only once.
49  *
50  * Input		Description
51  * -------------------	----------------------------------------
52  * md_t *		Pointer to md session
53  * mde_cookie_t		Index of the starting node
54  * mde_str_cookie_t	Node name cookie of the nodes to call
55  *			the walk function
56  * mde_str_cookie_t	Arc name cookie of the path to follow
57  * md_walk_fn_t		The function to call for each node
58  * void *		Private data to pass to the walker function
59  *
60  */
61 int
md_walk_dag(md_t * ptr,mde_cookie_t startnode,mde_str_cookie_t node_name_cookie,mde_str_cookie_t arc_name_cookie,md_walk_fn_t func,void * private)62 md_walk_dag(md_t *ptr, mde_cookie_t startnode,
63     mde_str_cookie_t node_name_cookie, mde_str_cookie_t arc_name_cookie,
64     md_walk_fn_t func, void *private)
65 {
66 	int		res;
67 	uint8_t		*seenp;
68 	md_impl_t	*mdp;
69 	mde_cookie_t	start;
70 
71 	mdp = (md_impl_t *)ptr;
72 	if (mdp == NULL) {
73 		return (-1);
74 	}
75 
76 	/*
77 	 * Possible the caller was lazy and didn't check the
78 	 * validitiy of either the node name or the arc name
79 	 * on calling ... in which case fail to find any
80 	 * nodes.
81 	 * This is distinct, from a fail (-1) since we return
82 	 * that nothing was found.
83 	 */
84 	if (node_name_cookie == MDE_INVAL_STR_COOKIE ||
85 	    arc_name_cookie == MDE_INVAL_STR_COOKIE) {
86 		return (0);
87 	}
88 
89 	/*
90 	 * if we want to start at the top, start at index 0
91 	 */
92 	start = startnode;
93 	if (start == MDE_INVAL_ELEM_COOKIE) {
94 		start = 0;
95 	}
96 
97 	/*
98 	 * Scan from the start point until the first node.
99 	 */
100 	while (start < mdp->element_count &&
101 	    MDE_TAG(&mdp->mdep[start]) == MDET_NULL) {
102 		start++;
103 	}
104 
105 	/*
106 	 * This was a bogus start point if no node found
107 	 */
108 	if (MDE_TAG(&mdp->mdep[start]) != MDET_NODE) {
109 		return (-1);	/* illegal start node specified */
110 	}
111 
112 	/*
113 	 * Allocate a recursion detection structure so we only visit
114 	 * each node once.
115 	 */
116 	seenp = (uint8_t *)mdp->allocp(mdp->element_count);
117 	if (seenp == NULL) {
118 		return (-1);
119 	}
120 	(void) memset(seenp, 0, mdp->element_count);
121 
122 	/*
123 	 * Now build the list of requested nodes.
124 	 */
125 	res = mdl_walk_dag(mdp, MDE_INVAL_ELEM_COOKIE, start,
126 	    node_name_cookie, arc_name_cookie, seenp, func, private, 0);
127 
128 	mdp->freep(seenp, mdp->element_count);
129 
130 	return (res >= 0 ? 0 : res);
131 }
132 
133 
134 static int
mdl_walk_dag(md_impl_t * mdp,mde_cookie_t parentidx,mde_cookie_t nodeidx,mde_str_cookie_t node_name_cookie,mde_str_cookie_t arc_name_cookie,uint8_t * seenp,md_walk_fn_t func,void * private,int level)135 mdl_walk_dag(md_impl_t *mdp, mde_cookie_t parentidx, mde_cookie_t nodeidx,
136     mde_str_cookie_t node_name_cookie, mde_str_cookie_t arc_name_cookie,
137     uint8_t *seenp, md_walk_fn_t func, void *private, int level)
138 {
139 	int		result;
140 	md_element_t	*mdep;
141 
142 	/* Get the node element from the session */
143 	mdep = &(mdp->mdep[nodeidx]);
144 
145 	/* see if cookie is infact a node */
146 	if (MDE_TAG(mdep) != MDET_NODE) {
147 		return (MDE_WALK_ERROR);
148 	}
149 
150 	/* have we been here before ? */
151 	if (seenp[nodeidx]) {
152 		return (MDE_WALK_NEXT);
153 	}
154 	seenp[nodeidx] = 1;
155 
156 #ifdef	DEBUG_LIBMDESC
157 	{
158 		int x;
159 		for (x = 0; x < level; x++) {
160 			printf("-");
161 		}
162 		printf("%d (%s)\n", nodeidx,
163 		    (char *)(mdp->datap + MDE_NAME(mdep)));
164 	}
165 #endif
166 
167 	/* is this node of the type we seek ? */
168 	if (MDE_NAME(mdep) == node_name_cookie) {
169 		/*
170 		 * Yes.  Call the callback function.
171 		 */
172 		result = (func)((md_t *)mdp, parentidx, nodeidx, private);
173 		if (result != MDE_WALK_NEXT) {
174 			return (result);
175 		}
176 	}
177 
178 	/*
179 	 * Simply walk the elements in the node.
180 	 * if we find a matching arc, then recursively call
181 	 * the subordinate looking for a match
182 	 */
183 	result = MDE_WALK_NEXT;
184 	for (mdep++; MDE_TAG(mdep) != MDET_NODE_END; mdep++) {
185 		if (MDE_TAG(mdep) == MDET_PROP_ARC &&
186 		    MDE_NAME(mdep) == arc_name_cookie) {
187 			/*
188 			 * The current node becomes the parent node, and the
189 			 * arc index is the new current node.
190 			 */
191 			result = mdl_walk_dag(mdp, nodeidx, mdep->d.prop_idx,
192 			    node_name_cookie, arc_name_cookie, seenp, func,
193 			    private, level+1);
194 			if (result != MDE_WALK_NEXT) {
195 				/* The walk is complete or terminated. */
196 				return (result);
197 			}
198 		}
199 	}
200 
201 	return (result);
202 }
203