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/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 ASSERT3P(list, !=, NULL); 65 ASSERT3U(size, >=, offset + sizeof (list_node_t)); 66 67 (void) size; 68 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 ASSERT3P(list, !=, NULL); 80 ASSERT3P(list->list_head.list_next, ==, node); 81 ASSERT3P(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 ASSERT3P(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 ASSERT3U(dst->list_offset, ==, src->list_offset); 199 200 if (list_empty(src)) 201 return; 202 203 dstnode->list_prev->list_next = srcnode->list_next; 204 srcnode->list_next->list_prev = dstnode->list_prev; 205 dstnode->list_prev = srcnode->list_prev; 206 srcnode->list_prev->list_next = dstnode; 207 208 /* empty src list */ 209 srcnode->list_next = srcnode->list_prev = srcnode; 210} 211 212void 213list_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->list_next = lold->list_next; 219 lnew->list_prev = lold->list_prev; 220 lold->list_prev->list_next = lnew; 221 lold->list_next->list_prev = lnew; 222 lold->list_next = lold->list_prev = NULL; 223} 224 225void 226list_link_init(list_node_t *link) 227{ 228 link->list_next = NULL; 229 link->list_prev = NULL; 230} 231 232int 233list_link_active(list_node_t *link) 234{ 235 EQUIV(link->list_next == NULL, link->list_prev == NULL); 236 return (link->list_next != NULL); 237} 238 239int 240list_is_empty(list_t *list) 241{ 242 return (list_empty(list)); 243} 244