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