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
41extern 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
69void
70list_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
82void
83list_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
94void
95list_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
105void
106list_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
116void
117list_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
123void
124list_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
130void
131list_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
139void *
140list_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
149void *
150list_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
159void *
160list_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
167void *
168list_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
175void *
176list_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
186void *
187list_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 */
200void
201list_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
221void
222list_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
234void
235list_link_init(list_node_t *link)
236{
237	link->list_next = NULL;
238	link->list_prev = NULL;
239}
240
241int
242list_link_active(list_node_t *link)
243{
244	return (link->list_next != NULL);
245}
246
247int
248list_is_empty(list_t *list)
249{
250	return (list_empty(list));
251}
252