xref: /illumos-gate/usr/src/common/list/list.c (revision 3c112a2b)
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
41 extern 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 
69 void
list_create(list_t * list,size_t size,size_t offset)70 list_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 
82 void
list_destroy(list_t * list)83 list_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 
94 void
list_insert_after(list_t * list,void * object,void * nobject)95 list_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 
105 void
list_insert_before(list_t * list,void * object,void * nobject)106 list_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 
116 void
list_insert_head(list_t * list,void * object)117 list_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 
123 void
list_insert_tail(list_t * list,void * object)124 list_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 
130 void
list_remove(list_t * list,void * object)131 list_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 
139 void *
list_remove_head(list_t * list)140 list_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 
149 void *
list_remove_tail(list_t * list)150 list_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 
159 void *
list_head(list_t * list)160 list_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 
167 void *
list_tail(list_t * list)168 list_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 
175 void *
list_next(list_t * list,void * object)176 list_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 
186 void *
list_prev(list_t * list,void * object)187 list_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  */
200 void
list_move_tail(list_t * dst,list_t * src)201 list_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 
221 void
list_link_replace(list_node_t * lold,list_node_t * lnew)222 list_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 
234 void
list_link_init(list_node_t * link)235 list_link_init(list_node_t *link)
236 {
237 	link->list_next = NULL;
238 	link->list_prev = NULL;
239 }
240 
241 int
list_link_active(list_node_t * link)242 list_link_active(list_node_t *link)
243 {
244 	return (link->list_next != NULL);
245 }
246 
247 int
list_is_empty(list_t * list)248 list_is_empty(list_t *list)
249 {
250 	return (list_empty(list));
251 }
252