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.
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.
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]
22 * Copyright 2008 Sun Microsystems, Inc. All rights reserved.
23 * Use is subject to license terms.
27 * Generic doubly-linked list implementation
31 #include <sys/list_impl.h>
32 #include <sys/types.h>
33 #include <sys/sysmacros.h>
34 #include <sys/debug.h>
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)
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; \
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; \
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
62 list_create(list_t *list, size_t size, size_t offset)
66 ASSERT(size >= offset + sizeof (list_node_t));
68 list->list_size = size;
69 list->list_offset = offset;
70 list->list_head.list_next = list->list_head.list_prev =
75 list_destroy(list_t *list)
77 list_node_t *node = &list->list_head;
80 ASSERT(list->list_head.list_next == node);
81 ASSERT(list->list_head.list_prev == node);
83 node->list_next = node->list_prev = NULL;
87 list_insert_after(list_t *list, void *object, void *nobject)
90 list_insert_head(list, nobject);
92 list_node_t *lold = list_d2l(list, object);
93 list_insert_after_node(list, lold, nobject);
98 list_insert_before(list_t *list, void *object, void *nobject)
100 if (object == NULL) {
101 list_insert_tail(list, nobject);
103 list_node_t *lold = list_d2l(list, object);
104 list_insert_before_node(list, lold, nobject);
109 list_insert_head(list_t *list, void *object)
111 list_node_t *lold = &list->list_head;
112 list_insert_after_node(list, lold, object);
116 list_insert_tail(list_t *list, void *object)
118 list_node_t *lold = &list->list_head;
119 list_insert_before_node(list, lold, object);
123 list_remove(list_t *list, void *object)
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);
132 list_remove_head(list_t *list)
134 list_node_t *head = list->list_head.list_next;
135 if (head == &list->list_head)
137 list_remove_node(head);
138 return (list_object(list, head));
142 list_remove_tail(list_t *list)
144 list_node_t *tail = list->list_head.list_prev;
145 if (tail == &list->list_head)
147 list_remove_node(tail);
148 return (list_object(list, tail));
152 list_head(list_t *list)
154 if (list_empty(list))
156 return (list_object(list, list->list_head.list_next));
160 list_tail(list_t *list)
162 if (list_empty(list))
164 return (list_object(list, list->list_head.list_prev));
168 list_next(list_t *list, void *object)
170 list_node_t *node = list_d2l(list, object);
172 if (node->list_next != &list->list_head)
173 return (list_object(list, node->list_next));
179 list_prev(list_t *list, void *object)
181 list_node_t *node = list_d2l(list, object);
183 if (node->list_prev != &list->list_head)
184 return (list_object(list, node->list_prev));
190 * Insert src list after dst list. Empty src list thereafter.
193 list_move_tail(list_t *dst, list_t *src)
195 list_node_t *dstnode = &dst->list_head;
196 list_node_t *srcnode = &src->list_head;
198 ASSERT(dst->list_size == src->list_size);
199 ASSERT(dst->list_offset == src->list_offset);
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;
210 srcnode->list_next = srcnode->list_prev = srcnode;
214 list_link_replace(list_node_t *lold, list_node_t *lnew)
216 ASSERT(list_link_active(lold));
217 ASSERT(!list_link_active(lnew));
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;
227 list_link_init(list_node_t *ln)
229 ln->list_next = NULL;
230 ln->list_prev = NULL;
234 list_link_active(list_node_t *ln)
236 return (ln->list_next != NULL);
240 list_is_empty(list_t *list)
242 return (list_empty(list));