1 // SPDX-License-Identifier: CDDL-1.0 2 /* 3 * CDDL HEADER START 4 * 5 * The contents of this file are subject to the terms of the 6 * Common Development and Distribution License (the "License"). 7 * You may not use this file except in compliance with the License. 8 * 9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 10 * or https://opensource.org/licenses/CDDL-1.0. 11 * See the License for the specific language governing permissions 12 * and limitations under the License. 13 * 14 * When distributing Covered Code, include this CDDL HEADER in each 15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 16 * If applicable, add the following below this CDDL HEADER, with the 17 * fields enclosed by brackets "[]" replaced with your own identifying 18 * information: Portions Copyright [yyyy] [name of copyright owner] 19 * 20 * CDDL HEADER END 21 */ 22 /* 23 * Copyright 2008 Sun Microsystems, Inc. All rights reserved. 24 * Use is subject to license terms. 25 */ 26 27 /* 28 * Generic doubly-linked list implementation 29 */ 30 31 #include <sys/list.h> 32 #include <sys/list_impl.h> 33 #include <sys/types.h> 34 #include <sys/sysmacros.h> 35 #include <sys/debug.h> 36 37 #define list_d2l(a, obj) ((list_node_t *)(((char *)obj) + (a)->list_offset)) 38 #define list_object(a, node) ((void *)(((char *)node) - (a)->list_offset)) 39 #define list_empty(a) ((a)->list_head.next == &(a)->list_head) 40 41 #define list_insert_after_node(list, node, object) { \ 42 list_node_t *lnew = list_d2l(list, object); \ 43 lnew->prev = (node); \ 44 lnew->next = (node)->next; \ 45 (node)->next->prev = lnew; \ 46 (node)->next = lnew; \ 47 } 48 49 #define list_insert_before_node(list, node, object) { \ 50 list_node_t *lnew = list_d2l(list, object); \ 51 lnew->next = (node); \ 52 lnew->prev = (node)->prev; \ 53 (node)->prev->next = lnew; \ 54 (node)->prev = lnew; \ 55 } 56 57 #define list_remove_node(node) \ 58 (node)->prev->next = (node)->next; \ 59 (node)->next->prev = (node)->prev; \ 60 (node)->next = (node)->prev = NULL 61 62 void 63 list_create(list_t *list, size_t size, size_t offset) 64 { 65 ASSERT(list); 66 ASSERT(size > 0); 67 ASSERT(size >= offset + sizeof (list_node_t)); 68 69 (void) size; 70 71 list->list_offset = offset; 72 list->list_head.next = list->list_head.prev = &list->list_head; 73 } 74 75 void 76 list_destroy(list_t *list) 77 { 78 list_node_t *node = &list->list_head; 79 80 ASSERT(list); 81 ASSERT(list->list_head.next == node); 82 ASSERT(list->list_head.prev == node); 83 84 node->next = node->prev = NULL; 85 } 86 87 void 88 list_insert_after(list_t *list, void *object, void *nobject) 89 { 90 if (object == NULL) { 91 list_insert_head(list, nobject); 92 } else { 93 list_node_t *lold = list_d2l(list, object); 94 list_insert_after_node(list, lold, nobject); 95 } 96 } 97 98 void 99 list_insert_before(list_t *list, void *object, void *nobject) 100 { 101 if (object == NULL) { 102 list_insert_tail(list, nobject); 103 } else { 104 list_node_t *lold = list_d2l(list, object); 105 list_insert_before_node(list, lold, nobject); 106 } 107 } 108 109 void 110 list_insert_head(list_t *list, void *object) 111 { 112 list_node_t *lold = &list->list_head; 113 list_insert_after_node(list, lold, object); 114 } 115 116 void 117 list_insert_tail(list_t *list, void *object) 118 { 119 list_node_t *lold = &list->list_head; 120 list_insert_before_node(list, lold, object); 121 } 122 123 void 124 list_remove(list_t *list, void *object) 125 { 126 list_node_t *lold = list_d2l(list, object); 127 ASSERT(!list_empty(list)); 128 ASSERT(lold->next != NULL); 129 list_remove_node(lold); 130 } 131 132 void * 133 list_remove_head(list_t *list) 134 { 135 list_node_t *head = list->list_head.next; 136 if (head == &list->list_head) 137 return (NULL); 138 list_remove_node(head); 139 return (list_object(list, head)); 140 } 141 142 void * 143 list_remove_tail(list_t *list) 144 { 145 list_node_t *tail = list->list_head.prev; 146 if (tail == &list->list_head) 147 return (NULL); 148 list_remove_node(tail); 149 return (list_object(list, tail)); 150 } 151 152 void * 153 list_head(list_t *list) 154 { 155 if (list_empty(list)) 156 return (NULL); 157 return (list_object(list, list->list_head.next)); 158 } 159 160 void * 161 list_tail(list_t *list) 162 { 163 if (list_empty(list)) 164 return (NULL); 165 return (list_object(list, list->list_head.prev)); 166 } 167 168 void * 169 list_next(list_t *list, void *object) 170 { 171 list_node_t *node = list_d2l(list, object); 172 173 if (node->next != &list->list_head) 174 return (list_object(list, node->next)); 175 176 return (NULL); 177 } 178 179 void * 180 list_prev(list_t *list, void *object) 181 { 182 list_node_t *node = list_d2l(list, object); 183 184 if (node->prev != &list->list_head) 185 return (list_object(list, node->prev)); 186 187 return (NULL); 188 } 189 190 /* 191 * Insert src list after dst list. Empty src list thereafter. 192 */ 193 void 194 list_move_tail(list_t *dst, list_t *src) 195 { 196 list_node_t *dstnode = &dst->list_head; 197 list_node_t *srcnode = &src->list_head; 198 199 ASSERT(dst->list_offset == src->list_offset); 200 201 if (list_empty(src)) 202 return; 203 204 dstnode->prev->next = srcnode->next; 205 srcnode->next->prev = dstnode->prev; 206 dstnode->prev = srcnode->prev; 207 srcnode->prev->next = dstnode; 208 209 /* empty src list */ 210 srcnode->next = srcnode->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->next = lold->next; 220 lnew->prev = lold->prev; 221 lold->prev->next = lnew; 222 lold->next->prev = lnew; 223 lold->next = lold->prev = NULL; 224 } 225 226 void 227 list_link_init(list_node_t *ln) 228 { 229 ln->next = NULL; 230 ln->prev = NULL; 231 } 232 233 int 234 list_link_active(list_node_t *ln) 235 { 236 EQUIV(ln->next == NULL, ln->prev == NULL); 237 return (ln->next != NULL); 238 } 239 240 int 241 list_is_empty(list_t *list) 242 { 243 return (list_empty(list)); 244 } 245