xref: /illumos-gate/usr/src/common/mdesc/mdesc_scandag.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 2006 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_scan_dag(md_impl_t *mdp,
41 	int nodeidx,
42 	mde_str_cookie_t node_cookie,
43 	mde_str_cookie_t arc_cookie,
44 	uint8_t *dseenp,
45 	int *idxp,
46 	mde_cookie_t *stashp,
47 	int level);
48 
49 
50 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)51 md_scan_dag(md_t *ptr,
52 	mde_cookie_t startnode,
53 	mde_str_cookie_t node_name_cookie,
54 	mde_str_cookie_t arc_name_cookie,
55 	mde_cookie_t *stashp)
56 {
57 	int	res;
58 	int	idx;
59 	uint8_t *seenp;
60 	md_impl_t *mdp;
61 	int	start;
62 
63 	mdp = (md_impl_t *)ptr;
64 
65 	/*
66 	 * Possible the caller was lazy and didn't check the
67 	 * validitiy of either the node name or the arc name
68 	 * on calling ... in which case fail to find any
69 	 * nodes.
70 	 * This is distinct, from a fail (-1) since we return
71 	 * that nothing was found.
72 	 */
73 
74 	if (node_name_cookie == MDE_INVAL_STR_COOKIE ||
75 		arc_name_cookie == MDE_INVAL_STR_COOKIE) return 0;
76 
77 	/*
78 	 * if we want to start at the top, start at index 0
79 	 */
80 
81 	start = (int)startnode;
82 	if (start == MDE_INVAL_ELEM_COOKIE) start = 0;
83 
84 	/*
85 	 * Scan from the start point until the first node.
86 	 */
87 	while (MDE_TAG(&mdp->mdep[start]) == MDET_NULL) start++;
88 
89 	/*
90 	 * This was a bogus start point if no node found
91 	 */
92 	if (MDE_TAG(&mdp->mdep[start]) != MDET_NODE) {
93 		return (-1);	/* illegal start node specified */
94 	}
95 
96 	/*
97 	 * Allocate a recursion mask on the local stack fail
98 	 * if we can't allocate the recursion detection.
99 	 */
100 	seenp = (uint8_t *)mdp->allocp(mdp->element_count);
101 	if (seenp == NULL)
102 		return (-1);
103 	(void) memset(seenp, 0, mdp->element_count);
104 
105 	/*
106 	 * Now build the list of requested nodes.
107 	 */
108 	idx = 0;
109 	res = mdl_scan_dag(mdp, start,
110 		node_name_cookie, arc_name_cookie,
111 		seenp, &idx, stashp, 0);
112 
113 	mdp->freep(seenp, mdp->element_count);
114 
115 	return (res >= 0 ? idx : res);
116 }
117 
118 
119 
120 
121 
122 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)123 mdl_scan_dag(md_impl_t *mdp,
124 	int nodeidx,
125 	mde_str_cookie_t node_name_cookie,
126 	mde_str_cookie_t arc_name_cookie,
127 	uint8_t *seenp,
128 	int *idxp,
129 	mde_cookie_t *stashp,
130 	int level)
131 {
132 	md_element_t *mdep;
133 
134 	mdep = &(mdp->mdep[nodeidx]);
135 
136 	/* see if cookie is infact a node */
137 	if (MDE_TAG(mdep) != MDET_NODE)
138 		return (-1);
139 
140 	/* have we been here before ? */
141 	if (seenp[nodeidx])
142 		return (0);
143 	seenp[nodeidx] = 1;
144 
145 	/* is this node of the type we seek ? */
146 
147 #ifdef	DEBUG_LIBMDESC
148 	{
149 	int x;
150 	for (x = 0; x < level; x++)
151 		printf("-");
152 	printf("%d (%s)\n", nodeidx, (char *)(mdp->datap + MDE_NAME(mdep)));
153 	}
154 #endif
155 
156 	if (MDE_NAME(mdep) == node_name_cookie) {
157 		/* record the node in the list and keep searching */
158 		if (stashp != NULL) {
159 			stashp[*idxp] = (mde_cookie_t)nodeidx;
160 		}
161 		(*idxp)++;
162 #ifdef	DEBUG_LIBMDESC
163 		printf("\t* %d\n", *idxp);
164 #endif
165 	}
166 
167 	/*
168 	 * Simply walk the elements in the node.
169 	 * if we find a matching arc, then recursively call
170 	 * the subordinate looking for a match
171 	 */
172 
173 	for (mdep++; MDE_TAG(mdep) != MDET_NODE_END; mdep++) {
174 		if (MDE_TAG(mdep) == MDET_PROP_ARC &&
175 			MDE_NAME(mdep) == arc_name_cookie) {
176 			int res;
177 
178 			res = mdl_scan_dag(mdp,
179 			    (int)mdep->d.prop_idx,
180 			    node_name_cookie,
181 			    arc_name_cookie,
182 			    seenp, idxp, stashp, level+1);
183 
184 			if (res == -1)
185 				return (res);
186 		}
187 	}
188 
189 	return (0);
190 }
191