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 https://opensource.org/licenses/CDDL-1.0. 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 (void) size; 69 70 list->list_offset = offset; 71 list->list_head.next = list->list_head.prev = &list->list_head; 72 } 73 74 void 75 list_destroy(list_t *list) 76 { 77 list_node_t *node = &list->list_head; 78 79 ASSERT(list); 80 ASSERT(list->list_head.next == node); 81 ASSERT(list->list_head.prev == node); 82 83 node->next = node->prev = NULL; 84 } 85 86 void 87 list_insert_after(list_t *list, void *object, void *nobject) 88 { 89 if (object == NULL) { 90 list_insert_head(list, nobject); 91 } else { 92 list_node_t *lold = list_d2l(list, object); 93 list_insert_after_node(list, lold, nobject); 94 } 95 } 96 97 void 98 list_insert_before(list_t *list, void *object, void *nobject) 99 { 100 if (object == NULL) { 101 list_insert_tail(list, nobject); 102 } else { 103 list_node_t *lold = list_d2l(list, object); 104 list_insert_before_node(list, lold, nobject); 105 } 106 } 107 108 void 109 list_insert_head(list_t *list, void *object) 110 { 111 list_node_t *lold = &list->list_head; 112 list_insert_after_node(list, lold, object); 113 } 114 115 void 116 list_insert_tail(list_t *list, void *object) 117 { 118 list_node_t *lold = &list->list_head; 119 list_insert_before_node(list, lold, object); 120 } 121 122 void 123 list_remove(list_t *list, void *object) 124 { 125 list_node_t *lold = list_d2l(list, object); 126 ASSERT(!list_empty(list)); 127 ASSERT(lold->next != NULL); 128 list_remove_node(lold); 129 } 130 131 void * 132 list_remove_head(list_t *list) 133 { 134 list_node_t *head = list->list_head.next; 135 if (head == &list->list_head) 136 return (NULL); 137 list_remove_node(head); 138 return (list_object(list, head)); 139 } 140 141 void * 142 list_remove_tail(list_t *list) 143 { 144 list_node_t *tail = list->list_head.prev; 145 if (tail == &list->list_head) 146 return (NULL); 147 list_remove_node(tail); 148 return (list_object(list, tail)); 149 } 150 151 void * 152 list_head(list_t *list) 153 { 154 if (list_empty(list)) 155 return (NULL); 156 return (list_object(list, list->list_head.next)); 157 } 158 159 void * 160 list_tail(list_t *list) 161 { 162 if (list_empty(list)) 163 return (NULL); 164 return (list_object(list, list->list_head.prev)); 165 } 166 167 void * 168 list_next(list_t *list, void *object) 169 { 170 list_node_t *node = list_d2l(list, object); 171 172 if (node->next != &list->list_head) 173 return (list_object(list, node->next)); 174 175 return (NULL); 176 } 177 178 void * 179 list_prev(list_t *list, void *object) 180 { 181 list_node_t *node = list_d2l(list, object); 182 183 if (node->prev != &list->list_head) 184 return (list_object(list, node->prev)); 185 186 return (NULL); 187 } 188 189 /* 190 * Insert src list after dst list. Empty src list thereafter. 191 */ 192 void 193 list_move_tail(list_t *dst, list_t *src) 194 { 195 list_node_t *dstnode = &dst->list_head; 196 list_node_t *srcnode = &src->list_head; 197 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