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 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 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 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 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 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 * 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 * 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 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