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