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 * Copyright 2019 Joyent, Inc.
28 */
29
30 #include <string.h>
31 #include <unistd.h>
32 #include <assert.h>
33
34 #include <topo_error.h>
35 #include <topo_list.h>
36 #include <topo_tree.h>
37
38 /*
39 * Embedded Linked Lists
40 *
41 * Simple doubly-linked list implementation. This implementation assumes that
42 * each list element contains an embedded topo_list_t (previous and next
43 * pointers), which is typically the first member of the element struct.
44 * An additional topo_list_t is used to store the head (l_next) and tail
45 * (l_prev) pointers. The current head and tail list elements have their
46 * previous and next pointers set to NULL, respectively.
47 *
48 * NOTE: The embeddable list code in this file intentionally provides no
49 * locking of any kind. The implementation of any list in topo must provide
50 * an appropriate locking strategy to protect the list or to protect access
51 * to the embedded topo_list_t inside of each list element to avoid corruption.
52 * Refer to comments in the source files that use topo_list_t for lock details.
53 */
54
55
56 void
topo_list_append(topo_list_t * lp,void * new)57 topo_list_append(topo_list_t *lp, void *new)
58 {
59 topo_list_t *p = lp->l_prev; /* p = tail list element */
60 topo_list_t *q = new; /* q = new list element */
61
62 lp->l_prev = q;
63 q->l_prev = p;
64 q->l_next = NULL;
65
66 if (p != NULL) {
67 assert(p->l_next == NULL);
68 p->l_next = q;
69 } else {
70 assert(lp->l_next == NULL);
71 lp->l_next = q;
72 }
73 }
74
75 void
topo_list_prepend(topo_list_t * lp,void * new)76 topo_list_prepend(topo_list_t *lp, void *new)
77 {
78 topo_list_t *p = new; /* p = new list element */
79 topo_list_t *q = lp->l_next; /* q = head list element */
80
81 lp->l_next = p;
82 p->l_prev = NULL;
83 p->l_next = q;
84
85 if (q != NULL) {
86 assert(q->l_prev == NULL);
87 q->l_prev = p;
88 } else {
89 assert(lp->l_prev == NULL);
90 lp->l_prev = p;
91 }
92 }
93
94 void
topo_list_insert_before(topo_list_t * lp,void * before_me,void * new)95 topo_list_insert_before(topo_list_t *lp, void *before_me, void *new)
96 {
97 topo_list_t *p = before_me;
98 topo_list_t *q = new;
99
100 if (p == NULL || p->l_prev == NULL) {
101 topo_list_prepend(lp, new);
102 return;
103 }
104
105 q->l_prev = p->l_prev;
106 q->l_next = p;
107 p->l_prev = q;
108 q->l_prev->l_next = q;
109 }
110
111 void
topo_list_insert_after(topo_list_t * lp,void * after_me,void * new)112 topo_list_insert_after(topo_list_t *lp, void *after_me, void *new)
113 {
114 topo_list_t *p = after_me;
115 topo_list_t *q = new;
116
117 if (p == NULL || p->l_next == NULL) {
118 topo_list_append(lp, new);
119 return;
120 }
121
122 q->l_next = p->l_next;
123 q->l_prev = p;
124 p->l_next = q;
125 q->l_next->l_prev = q;
126 }
127
128 void
topo_list_delete(topo_list_t * lp,void * existing)129 topo_list_delete(topo_list_t *lp, void *existing)
130 {
131 topo_list_t *p = existing;
132
133 if (p->l_prev != NULL)
134 p->l_prev->l_next = p->l_next;
135 else
136 lp->l_next = p->l_next;
137
138 if (p->l_next != NULL)
139 p->l_next->l_prev = p->l_prev;
140 else
141 lp->l_prev = p->l_prev;
142 }
143
144 tnode_t *
topo_child_first(tnode_t * pnode)145 topo_child_first(tnode_t *pnode)
146 {
147 int i;
148 topo_nodehash_t *nhp;
149
150 for (nhp = topo_list_next(&pnode->tn_children); nhp != NULL;
151 nhp = topo_list_next(nhp)) {
152 for (i = 0; i < nhp->th_arrlen; ++i) {
153 if (nhp->th_nodearr[i] != NULL)
154 return (nhp->th_nodearr[i]);
155 }
156 }
157
158 return (NULL);
159 }
160
161 tnode_t *
topo_child_next(tnode_t * pnode,tnode_t * node)162 topo_child_next(tnode_t *pnode, tnode_t *node)
163 {
164 int i;
165 int index;
166 topo_nodehash_t *nhp;
167
168 if (node == NULL) {
169 return (topo_child_first(pnode));
170 }
171
172 /*
173 * Begin search for next child in the current hash array
174 * If none found or we are at the end of the array, move
175 * on to the next array
176 */
177 index = topo_node_hash(node->tn_phash, node->tn_instance) + 1;
178 for (nhp = node->tn_phash; nhp != NULL; nhp = topo_list_next(nhp)) {
179 for (i = index; i < nhp->th_arrlen; ++i) {
180 if (nhp->th_nodearr[i] != NULL) {
181 return (nhp->th_nodearr[i]);
182 }
183 }
184 index = 0;
185 }
186
187 return (NULL);
188 }
189
190 int
topo_list_deepcopy(topo_hdl_t * thp,topo_list_t * dest,topo_list_t * src,size_t elem_sz)191 topo_list_deepcopy(topo_hdl_t *thp, topo_list_t *dest, topo_list_t *src,
192 size_t elem_sz)
193 {
194 void *elem;
195
196 /* if the destination list is not empty - bail out */
197 if (topo_list_next(dest) != NULL)
198 return (topo_hdl_seterrno(thp, ETOPO_UNKNOWN));
199
200 for (elem = topo_list_next(src); elem != NULL;
201 elem = topo_list_next(elem)) {
202 void *elem_copy;
203
204 if ((elem_copy = topo_hdl_alloc(thp, elem_sz)) == NULL) {
205 goto err;
206 }
207 (void) memcpy(elem_copy, elem, elem_sz);
208 topo_list_append(dest, elem_copy);
209 }
210 return (0);
211
212 err:
213 /*
214 * If we hit an error, cleanup any partially copied list elements
215 * before we return.
216 */
217 elem = topo_list_next(dest);
218 while (elem != NULL) {
219 void *tmp = elem;
220
221 elem = topo_list_next(elem);
222 topo_list_delete(dest, tmp);
223 topo_hdl_free(thp, tmp, elem_sz);
224 }
225 return (topo_hdl_seterrno(thp, ETOPO_NOMEM));
226 }
227