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