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 61void 62list_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 74void 75list_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 86void 87list_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 97void 98list_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 108void 109list_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 115void 116list_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 122void 123list_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 131void * 132list_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 141void * 142list_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 151void * 152list_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 159void * 160list_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 167void * 168list_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 178void * 179list_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 */ 192void 193list_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 213void 214list_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 226void 227list_link_init(list_node_t *link) 228{ 229 link->list_next = NULL; 230 link->list_prev = NULL; 231} 232 233int 234list_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 240int 241list_is_empty(list_t *list) 242{ 243 return (list_empty(list)); 244} 245