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/param.h> 31 #include <sys/list.h> 32 #include <sys/list_impl.h> 33 #include <sys/types.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.list_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->list_prev = (node); \ 43 lnew->list_next = (node)->list_next; \ 44 (node)->list_next->list_prev = lnew; \ 45 (node)->list_next = lnew; \ 46 } 47 48 #define list_insert_before_node(list, node, object) { \ 49 list_node_t *lnew = list_d2l(list, object); \ 50 lnew->list_next = (node); \ 51 lnew->list_prev = (node)->list_prev; \ 52 (node)->list_prev->list_next = lnew; \ 53 (node)->list_prev = lnew; \ 54 } 55 56 #define list_remove_node(node) \ 57 (node)->list_prev->list_next = (node)->list_next; \ 58 (node)->list_next->list_prev = (node)->list_prev; \ 59 (node)->list_next = (node)->list_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.list_next = list->list_head.list_prev = 71 &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.list_next == node); 81 ASSERT(list->list_head.list_prev == node); 82 83 node->list_next = node->list_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->list_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.list_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.list_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.list_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.list_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->list_next != &list->list_head) 173 return (list_object(list, node->list_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->list_prev != &list->list_head) 184 return (list_object(list, node->list_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_size == src->list_size); 199 ASSERT(dst->list_offset == src->list_offset); 200 201 if (list_empty(src)) 202 return; 203 204 dstnode->list_prev->list_next = srcnode->list_next; 205 srcnode->list_next->list_prev = dstnode->list_prev; 206 dstnode->list_prev = srcnode->list_prev; 207 srcnode->list_prev->list_next = dstnode; 208 209 /* empty src list */ 210 srcnode->list_next = srcnode->list_prev = srcnode; 211 } 212 213 void 214 list_link_replace(list_node_t *lold, list_node_t *lnew) 215 { 216 ASSERT(list_link_active(lold)); 217 ASSERT(!list_link_active(lnew)); 218 219 lnew->list_next = lold->list_next; 220 lnew->list_prev = lold->list_prev; 221 lold->list_prev->list_next = lnew; 222 lold->list_next->list_prev = lnew; 223 lold->list_next = lold->list_prev = NULL; 224 } 225 226 void 227 list_link_init(list_node_t *link) 228 { 229 link->list_next = NULL; 230 link->list_prev = NULL; 231 } 232 233 int 234 list_link_active(list_node_t *link) 235 { 236 EQUIV(link->list_next == NULL, link->list_prev == NULL); 237 return (link->list_next != NULL); 238 } 239 240 int 241 list_is_empty(list_t *list) 242 { 243 return (list_empty(list)); 244 } 245