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 * Copyright (c) 2003, 2010, Oracle and/or its affiliates. All rights reserved. 23 */ 24 25 /* 26 * Generic doubly-linked list implementation 27 */ 28 29 #include <sys/list.h> 30 #include <sys/list_impl.h> 31 #include <sys/types.h> 32 #include <sys/sysmacros.h> 33 #ifdef _KERNEL 34 #include <sys/debug.h> 35 #else 36 #include <assert.h> 37 #define ASSERT(a) assert(a) 38 #endif 39 40 #ifdef lint 41 extern list_node_t *list_d2l(list_t *list, void *obj); 42 #else 43 #define list_d2l(a, obj) ((list_node_t *)(((char *)obj) + (a)->list_offset)) 44 #endif 45 #define list_object(a, node) ((void *)(((char *)node) - (a)->list_offset)) 46 #define list_empty(a) ((a)->list_head.list_next == &(a)->list_head) 47 48 #define list_insert_after_node(list, node, object) { \ 49 list_node_t *lnew = list_d2l(list, object); \ 50 lnew->list_prev = (node); \ 51 lnew->list_next = (node)->list_next; \ 52 (node)->list_next->list_prev = lnew; \ 53 (node)->list_next = lnew; \ 54 } 55 56 #define list_insert_before_node(list, node, object) { \ 57 list_node_t *lnew = list_d2l(list, object); \ 58 lnew->list_next = (node); \ 59 lnew->list_prev = (node)->list_prev; \ 60 (node)->list_prev->list_next = lnew; \ 61 (node)->list_prev = lnew; \ 62 } 63 64 #define list_remove_node(node) \ 65 (node)->list_prev->list_next = (node)->list_next; \ 66 (node)->list_next->list_prev = (node)->list_prev; \ 67 (node)->list_next = (node)->list_prev = NULL 68 69 void 70 list_create(list_t *list, size_t size, size_t offset) 71 { 72 ASSERT(list); 73 ASSERT(size > 0); 74 ASSERT(size >= offset + sizeof (list_node_t)); 75 76 list->list_size = size; 77 list->list_offset = offset; 78 list->list_numnodes = 0; 79 list->list_head.list_next = list->list_head.list_prev = 80 &list->list_head; 81 } 82 83 void 84 list_destroy(list_t *list) 85 { 86 list_node_t *node = &list->list_head; 87 88 ASSERT(list); 89 ASSERT(list->list_head.list_next == node); 90 ASSERT(list->list_head.list_prev == node); 91 92 list->list_numnodes = 0; 93 node->list_next = node->list_prev = NULL; 94 } 95 96 void 97 list_insert_after(list_t *list, void *object, void *nobject) 98 { 99 if (object == NULL) { 100 list_insert_head(list, nobject); 101 } else { 102 list_node_t *lold = list_d2l(list, object); 103 list_insert_after_node(list, lold, nobject); 104 } 105 } 106 107 void 108 list_insert_before(list_t *list, void *object, void *nobject) 109 { 110 if (object == NULL) { 111 list_insert_tail(list, nobject); 112 } else { 113 list_node_t *lold = list_d2l(list, object); 114 list_insert_before_node(list, lold, nobject); 115 } 116 } 117 118 void 119 list_insert_head(list_t *list, void *object) 120 { 121 list_node_t *lold = &list->list_head; 122 list->list_numnodes++; 123 list_insert_after_node(list, lold, object); 124 } 125 126 void 127 list_insert_tail(list_t *list, void *object) 128 { 129 list_node_t *lold = &list->list_head; 130 list->list_numnodes++; 131 list_insert_before_node(list, lold, object); 132 } 133 134 void 135 list_remove(list_t *list, void *object) 136 { 137 list_node_t *lold = list_d2l(list, object); 138 ASSERT(!list_empty(list)); 139 ASSERT(lold->list_next != NULL); 140 list->list_numnodes--; 141 list_remove_node(lold); 142 } 143 144 void * 145 list_remove_head(list_t *list) 146 { 147 list_node_t *head = list->list_head.list_next; 148 if (head == &list->list_head) 149 return (NULL); 150 list->list_numnodes--; 151 list_remove_node(head); 152 return (list_object(list, head)); 153 } 154 155 void * 156 list_remove_tail(list_t *list) 157 { 158 list_node_t *tail = list->list_head.list_prev; 159 if (tail == &list->list_head) 160 return (NULL); 161 list->list_numnodes--; 162 list_remove_node(tail); 163 return (list_object(list, tail)); 164 } 165 166 void * 167 list_head(list_t *list) 168 { 169 if (list_empty(list)) 170 return (NULL); 171 return (list_object(list, list->list_head.list_next)); 172 } 173 174 void * 175 list_tail(list_t *list) 176 { 177 if (list_empty(list)) 178 return (NULL); 179 return (list_object(list, list->list_head.list_prev)); 180 } 181 182 void * 183 list_next(list_t *list, void *object) 184 { 185 list_node_t *node = list_d2l(list, object); 186 187 if (node->list_next != &list->list_head) 188 return (list_object(list, node->list_next)); 189 190 return (NULL); 191 } 192 193 void * 194 list_prev(list_t *list, void *object) 195 { 196 list_node_t *node = list_d2l(list, object); 197 198 if (node->list_prev != &list->list_head) 199 return (list_object(list, node->list_prev)); 200 201 return (NULL); 202 } 203 204 /* 205 * Insert src list after dst list. Empty src list thereafter. 206 */ 207 void 208 list_move_tail(list_t *dst, list_t *src) 209 { 210 list_node_t *dstnode = &dst->list_head; 211 list_node_t *srcnode = &src->list_head; 212 213 ASSERT(dst->list_size == src->list_size); 214 ASSERT(dst->list_offset == src->list_offset); 215 216 if (list_empty(src)) 217 return; 218 219 dst->list_numnodes += src->list_numnodes; 220 dstnode->list_prev->list_next = srcnode->list_next; 221 srcnode->list_next->list_prev = dstnode->list_prev; 222 dstnode->list_prev = srcnode->list_prev; 223 srcnode->list_prev->list_next = dstnode; 224 225 /* empty src list */ 226 src->list_numnodes = 0; 227 srcnode->list_next = srcnode->list_prev = srcnode; 228 } 229 230 void 231 list_link_replace(list_node_t *lold, list_node_t *lnew) 232 { 233 ASSERT(list_link_active(lold)); 234 ASSERT(!list_link_active(lnew)); 235 236 lnew->list_next = lold->list_next; 237 lnew->list_prev = lold->list_prev; 238 lold->list_prev->list_next = lnew; 239 lold->list_next->list_prev = lnew; 240 lold->list_next = lold->list_prev = NULL; 241 } 242 243 void 244 list_link_init(list_node_t *link) 245 { 246 link->list_next = NULL; 247 link->list_prev = NULL; 248 } 249 250 int 251 list_link_active(list_node_t *link) 252 { 253 return (link->list_next != NULL); 254 } 255 256 int 257 list_is_empty(list_t *list) 258 { 259 return (list_empty(list)); 260 } 261 262 ulong_t 263 list_numnodes(list_t *list) 264 { 265 /* 266 size_t sz = 0; 267 list_node_t *node; 268 269 node = &list->list_head; 270 while (node->list_next != &list->list_head) { 271 sz++; 272 node = node->list_next; 273 } 274 return (sz); 275 */ 276 return (list->list_numnodes); 277 }