xref: /freebsd/sys/contrib/openzfs/lib/libspl/list.c (revision 7fdf597e96a02165cfe22ff357b857d5fa15ed8a)
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/list.h>
31 #include <sys/list_impl.h>
32 #include <sys/types.h>
33 #include <sys/sysmacros.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.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->prev = (node);			\
43 	lnew->next = (node)->next;		\
44 	(node)->next->prev = lnew;		\
45 	(node)->next = lnew;			\
46 }
47 
48 #define	list_insert_before_node(list, node, object) {	\
49 	list_node_t *lnew = list_d2l(list, object);	\
50 	lnew->next = (node);			\
51 	lnew->prev = (node)->prev;		\
52 	(node)->prev->next = lnew;		\
53 	(node)->prev = lnew;			\
54 }
55 
56 #define	list_remove_node(node)					\
57 	(node)->prev->next = (node)->next;	\
58 	(node)->next->prev = (node)->prev;	\
59 	(node)->next = (node)->prev = NULL
60 
61 void
62 list_create(list_t *list, size_t size, size_t offset)
63 {
64 	ASSERT(list);
65 	ASSERT(size > 0);
66 	ASSERT(size >= offset + sizeof (list_node_t));
67 
68 	(void) size;
69 
70 	list->list_offset = offset;
71 	list->list_head.next = list->list_head.prev = &list->list_head;
72 }
73 
74 void
75 list_destroy(list_t *list)
76 {
77 	list_node_t *node = &list->list_head;
78 
79 	ASSERT(list);
80 	ASSERT(list->list_head.next == node);
81 	ASSERT(list->list_head.prev == node);
82 
83 	node->next = node->prev = NULL;
84 }
85 
86 void
87 list_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 
97 void
98 list_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 
108 void
109 list_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 
115 void
116 list_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 
122 void
123 list_remove(list_t *list, void *object)
124 {
125 	list_node_t *lold = list_d2l(list, object);
126 	ASSERT(!list_empty(list));
127 	ASSERT(lold->next != NULL);
128 	list_remove_node(lold);
129 }
130 
131 void *
132 list_remove_head(list_t *list)
133 {
134 	list_node_t *head = list->list_head.next;
135 	if (head == &list->list_head)
136 		return (NULL);
137 	list_remove_node(head);
138 	return (list_object(list, head));
139 }
140 
141 void *
142 list_remove_tail(list_t *list)
143 {
144 	list_node_t *tail = list->list_head.prev;
145 	if (tail == &list->list_head)
146 		return (NULL);
147 	list_remove_node(tail);
148 	return (list_object(list, tail));
149 }
150 
151 void *
152 list_head(list_t *list)
153 {
154 	if (list_empty(list))
155 		return (NULL);
156 	return (list_object(list, list->list_head.next));
157 }
158 
159 void *
160 list_tail(list_t *list)
161 {
162 	if (list_empty(list))
163 		return (NULL);
164 	return (list_object(list, list->list_head.prev));
165 }
166 
167 void *
168 list_next(list_t *list, void *object)
169 {
170 	list_node_t *node = list_d2l(list, object);
171 
172 	if (node->next != &list->list_head)
173 		return (list_object(list, node->next));
174 
175 	return (NULL);
176 }
177 
178 void *
179 list_prev(list_t *list, void *object)
180 {
181 	list_node_t *node = list_d2l(list, object);
182 
183 	if (node->prev != &list->list_head)
184 		return (list_object(list, node->prev));
185 
186 	return (NULL);
187 }
188 
189 /*
190  *  Insert src list after dst list. Empty src list thereafter.
191  */
192 void
193 list_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 	ASSERT(dst->list_offset == src->list_offset);
199 
200 	if (list_empty(src))
201 		return;
202 
203 	dstnode->prev->next = srcnode->next;
204 	srcnode->next->prev = dstnode->prev;
205 	dstnode->prev = srcnode->prev;
206 	srcnode->prev->next = dstnode;
207 
208 	/* empty src list */
209 	srcnode->next = srcnode->prev = srcnode;
210 }
211 
212 void
213 list_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->next = lold->next;
219 	lnew->prev = lold->prev;
220 	lold->prev->next = lnew;
221 	lold->next->prev = lnew;
222 	lold->next = lold->prev = NULL;
223 }
224 
225 void
226 list_link_init(list_node_t *ln)
227 {
228 	ln->next = NULL;
229 	ln->prev = NULL;
230 }
231 
232 int
233 list_link_active(list_node_t *ln)
234 {
235 	EQUIV(ln->next == NULL, ln->prev == NULL);
236 	return (ln->next != NULL);
237 }
238 
239 int
240 list_is_empty(list_t *list)
241 {
242 	return (list_empty(list));
243 }
244