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.
26 #pragma ident "%Z%%M% %I% %E% SMI"
29 * Generic doubly-linked list implementation
33 #include <sys/list_impl.h>
34 #include <sys/types.h>
35 #include <sys/sysmacros.h>
36 #include <sys/debug.h>
38 #define list_d2l(a, obj) ((list_node_t *)(((char *)obj) + (a)->list_offset))
39 #define list_object(a, node) ((void *)(((char *)node) - (a)->list_offset))
40 #define list_empty(a) ((a)->list_head.list_next == &(a)->list_head)
42 #define list_insert_after_node(list, node, object) { \
43 list_node_t *lnew = list_d2l(list, object); \
44 lnew->list_prev = (node); \
45 lnew->list_next = (node)->list_next; \
46 (node)->list_next->list_prev = lnew; \
47 (node)->list_next = lnew; \
50 #define list_insert_before_node(list, node, object) { \
51 list_node_t *lnew = list_d2l(list, object); \
52 lnew->list_next = (node); \
53 lnew->list_prev = (node)->list_prev; \
54 (node)->list_prev->list_next = lnew; \
55 (node)->list_prev = lnew; \
58 #define list_remove_node(node) \
59 (node)->list_prev->list_next = (node)->list_next; \
60 (node)->list_next->list_prev = (node)->list_prev; \
61 (node)->list_next = (node)->list_prev = NULL
64 list_create(list_t *list, size_t size, size_t offset)
68 ASSERT(size >= offset + sizeof (list_node_t));
70 list->list_size = size;
71 list->list_offset = offset;
72 list->list_head.list_next = list->list_head.list_prev =
77 list_destroy(list_t *list)
79 list_node_t *node = &list->list_head;
82 ASSERT(list->list_head.list_next == node);
83 ASSERT(list->list_head.list_prev == node);
85 node->list_next = node->list_prev = NULL;
89 list_insert_after(list_t *list, void *object, void *nobject)
92 list_insert_head(list, nobject);
94 list_node_t *lold = list_d2l(list, object);
95 list_insert_after_node(list, lold, nobject);
100 list_insert_before(list_t *list, void *object, void *nobject)
102 if (object == NULL) {
103 list_insert_tail(list, nobject);
105 list_node_t *lold = list_d2l(list, object);
106 list_insert_before_node(list, lold, nobject);
111 list_insert_head(list_t *list, void *object)
113 list_node_t *lold = &list->list_head;
114 list_insert_after_node(list, lold, object);
118 list_insert_tail(list_t *list, void *object)
120 list_node_t *lold = &list->list_head;
121 list_insert_before_node(list, lold, object);
125 list_remove(list_t *list, void *object)
127 list_node_t *lold = list_d2l(list, object);
128 ASSERT(!list_empty(list));
129 ASSERT(lold->list_next != NULL);
130 list_remove_node(lold);
134 list_remove_head(list_t *list)
136 list_node_t *head = list->list_head.list_next;
137 if (head == &list->list_head)
139 list_remove_node(head);
140 return (list_object(list, head));
144 list_remove_tail(list_t *list)
146 list_node_t *tail = list->list_head.list_prev;
147 if (tail == &list->list_head)
149 list_remove_node(tail);
150 return (list_object(list, tail));
154 list_head(list_t *list)
156 if (list_empty(list))
158 return (list_object(list, list->list_head.list_next));
162 list_tail(list_t *list)
164 if (list_empty(list))
166 return (list_object(list, list->list_head.list_prev));
170 list_next(list_t *list, void *object)
172 list_node_t *node = list_d2l(list, object);
174 if (node->list_next != &list->list_head)
175 return (list_object(list, node->list_next));
181 list_prev(list_t *list, void *object)
183 list_node_t *node = list_d2l(list, object);
185 if (node->list_prev != &list->list_head)
186 return (list_object(list, node->list_prev));
192 * Insert src list after dst list. Empty src list thereafter.
195 list_move_tail(list_t *dst, list_t *src)
197 list_node_t *dstnode = &dst->list_head;
198 list_node_t *srcnode = &src->list_head;
200 ASSERT(dst->list_size == src->list_size);
201 ASSERT(dst->list_offset == src->list_offset);
206 dstnode->list_prev->list_next = srcnode->list_next;
207 srcnode->list_next->list_prev = dstnode->list_prev;
208 dstnode->list_prev = srcnode->list_prev;
209 srcnode->list_prev->list_next = dstnode;
212 srcnode->list_next = srcnode->list_prev = srcnode;
216 list_link_replace(list_node_t *lold, list_node_t *lnew)
218 ASSERT(list_link_active(lold));
219 ASSERT(!list_link_active(lnew));
221 lnew->list_next = lold->list_next;
222 lnew->list_prev = lold->list_prev;
223 lold->list_prev->list_next = lnew;
224 lold->list_next->list_prev = lnew;
225 lold->list_next = lold->list_prev = NULL;
229 list_link_init(list_node_t *link)
231 link->list_next = NULL;
232 link->list_prev = NULL;
236 list_link_active(list_node_t *link)
238 return (link->list_next != NULL);
242 list_is_empty(list_t *list)
244 return (list_empty(list));