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