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