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