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, Version 1.0 only
6 * (the "License"). You may not use this file except in compliance
7 * with the License.
8 *
9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
10 * or http://www.opensolaris.org/os/licensing.
11 * See the License for the specific language governing permissions
12 * and limitations under the License.
13 *
14 * When distributing Covered Code, include this CDDL HEADER in each
15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
16 * If applicable, add the following below this CDDL HEADER, with the
17 * fields enclosed by brackets "[]" replaced with your own identifying
18 * information: Portions Copyright [yyyy] [name of copyright owner]
19 *
20 * CDDL HEADER END
21 */
22 /*
23 * Copyright 2006 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 <unistd.h>
30 #include <assert.h>
31
32 #include <topo_list.h>
33 #include <topo_tree.h>
34
35 /*
36 * Embedded Linked Lists
37 *
38 * Simple doubly-linked list implementation. This implementation assumes that
39 * each list element contains an embedded topo_list_t (previous and next
40 * pointers), which is typically the first member of the element struct.
41 * An additional topo_list_t is used to store the head (l_next) and tail
42 * (l_prev) pointers. The current head and tail list elements have their
43 * previous and next pointers set to NULL, respectively.
44 *
45 * NOTE: The embeddable list code in this file intentionally provides no
46 * locking of any kind. The implementation of any list in topo must provide
47 * an appropriate locking strategy to protect the list or to protect access
48 * to the embedded topo_list_t inside of each list element to avoid corruption.
49 * Refer to comments in the source files that use topo_list_t for lock details.
50 */
51
52
53 void
topo_list_append(topo_list_t * lp,void * new)54 topo_list_append(topo_list_t *lp, void *new)
55 {
56 topo_list_t *p = lp->l_prev; /* p = tail list element */
57 topo_list_t *q = new; /* q = new list element */
58
59 lp->l_prev = q;
60 q->l_prev = p;
61 q->l_next = NULL;
62
63 if (p != NULL) {
64 assert(p->l_next == NULL);
65 p->l_next = q;
66 } else {
67 assert(lp->l_next == NULL);
68 lp->l_next = q;
69 }
70 }
71
72 void
topo_list_prepend(topo_list_t * lp,void * new)73 topo_list_prepend(topo_list_t *lp, void *new)
74 {
75 topo_list_t *p = new; /* p = new list element */
76 topo_list_t *q = lp->l_next; /* q = head list element */
77
78 lp->l_next = p;
79 p->l_prev = NULL;
80 p->l_next = q;
81
82 if (q != NULL) {
83 assert(q->l_prev == NULL);
84 q->l_prev = p;
85 } else {
86 assert(lp->l_prev == NULL);
87 lp->l_prev = p;
88 }
89 }
90
91 void
topo_list_insert_before(topo_list_t * lp,void * before_me,void * new)92 topo_list_insert_before(topo_list_t *lp, void *before_me, void *new)
93 {
94 topo_list_t *p = before_me;
95 topo_list_t *q = new;
96
97 if (p == NULL || p->l_prev == NULL) {
98 topo_list_prepend(lp, new);
99 return;
100 }
101
102 q->l_prev = p->l_prev;
103 q->l_next = p;
104 p->l_prev = q;
105 q->l_prev->l_next = q;
106 }
107
108 void
topo_list_insert_after(topo_list_t * lp,void * after_me,void * new)109 topo_list_insert_after(topo_list_t *lp, void *after_me, void *new)
110 {
111 topo_list_t *p = after_me;
112 topo_list_t *q = new;
113
114 if (p == NULL || p->l_next == NULL) {
115 topo_list_append(lp, new);
116 return;
117 }
118
119 q->l_next = p->l_next;
120 q->l_prev = p;
121 p->l_next = q;
122 q->l_next->l_prev = q;
123 }
124
125 void
topo_list_delete(topo_list_t * lp,void * existing)126 topo_list_delete(topo_list_t *lp, void *existing)
127 {
128 topo_list_t *p = existing;
129
130 if (p->l_prev != NULL)
131 p->l_prev->l_next = p->l_next;
132 else
133 lp->l_next = p->l_next;
134
135 if (p->l_next != NULL)
136 p->l_next->l_prev = p->l_prev;
137 else
138 lp->l_prev = p->l_prev;
139 }
140
141 tnode_t *
topo_child_first(tnode_t * pnode)142 topo_child_first(tnode_t *pnode)
143 {
144 int i;
145 topo_nodehash_t *nhp;
146
147 for (nhp = topo_list_next(&pnode->tn_children); nhp != NULL;
148 nhp = topo_list_next(nhp)) {
149 for (i = 0; i < nhp->th_arrlen; ++i) {
150 if (nhp->th_nodearr[i] != NULL)
151 return (nhp->th_nodearr[i]);
152 }
153 }
154
155 return (NULL);
156 }
157
158 tnode_t *
topo_child_next(tnode_t * pnode,tnode_t * node)159 topo_child_next(tnode_t *pnode, tnode_t *node)
160 {
161 int i;
162 int index;
163 topo_nodehash_t *nhp;
164
165 if (node == NULL) {
166 return (topo_child_first(pnode));
167 }
168
169 /*
170 * Begin search for next child in the current hash array
171 * If none found or we are at the end of the array, move
172 * on to the next array
173 */
174 index = topo_node_hash(node->tn_phash, node->tn_instance) + 1;
175 for (nhp = node->tn_phash; nhp != NULL; nhp = topo_list_next(nhp)) {
176 for (i = index; i < nhp->th_arrlen; ++i) {
177 if (nhp->th_nodearr[i] != NULL) {
178 return (nhp->th_nodearr[i]);
179 }
180 }
181 index = 0;
182 }
183
184 return (NULL);
185 }
186