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 2008 Sun Microsystems, Inc.  All rights reserved.
23 * Use is subject to license terms.
24 */
25
26#pragma ident	"%Z%%M%	%I%	%E% SMI"
27
28/*
29 * Generic doubly-linked list implementation
30 */
31
32#include <sys/list.h>
33#include <sys/list_impl.h>
34#include <sys/types.h>
35#include <sys/sysmacros.h>
36#include <sys/debug.h>
37
38#ifdef _STANDALONE
39#define	ASSERT(x)	/* nothing */
40#endif
41
42#define	list_d2l(a, obj) ((list_node_t *)(((char *)obj) + (a)->list_offset))
43#define	list_object(a, node) ((void *)(((char *)node) - (a)->list_offset))
44#define	list_empty(a) ((a)->list_head.list_next == &(a)->list_head)
45
46#define	list_insert_after_node(list, node, object) {	\
47	list_node_t *lnew = list_d2l(list, object);	\
48	lnew->list_prev = (node);			\
49	lnew->list_next = (node)->list_next;		\
50	(node)->list_next->list_prev = lnew;		\
51	(node)->list_next = lnew;			\
52}
53
54#define	list_insert_before_node(list, node, object) {	\
55	list_node_t *lnew = list_d2l(list, object);	\
56	lnew->list_next = (node);			\
57	lnew->list_prev = (node)->list_prev;		\
58	(node)->list_prev->list_next = lnew;		\
59	(node)->list_prev = lnew;			\
60}
61
62#define	list_remove_node(node)					\
63	(node)->list_prev->list_next = (node)->list_next;	\
64	(node)->list_next->list_prev = (node)->list_prev;	\
65	(node)->list_next = (node)->list_prev = NULL
66
67void
68list_create(list_t *list, size_t size, size_t offset)
69{
70	ASSERT(list);
71	ASSERT(size > 0);
72	ASSERT(size >= offset + sizeof (list_node_t));
73
74	list->list_size = size;
75	list->list_offset = offset;
76	list->list_head.list_next = list->list_head.list_prev =
77	    &list->list_head;
78}
79
80void
81list_destroy(list_t *list)
82{
83	list_node_t *node = &list->list_head;
84
85	ASSERT(list);
86	ASSERT(list->list_head.list_next == node);
87	ASSERT(list->list_head.list_prev == node);
88
89	node->list_next = node->list_prev = NULL;
90}
91
92void
93list_insert_after(list_t *list, void *object, void *nobject)
94{
95	if (object == NULL) {
96		list_insert_head(list, nobject);
97	} else {
98		list_node_t *lold = list_d2l(list, object);
99		list_insert_after_node(list, lold, nobject);
100	}
101}
102
103void
104list_insert_before(list_t *list, void *object, void *nobject)
105{
106	if (object == NULL) {
107		list_insert_tail(list, nobject);
108	} else {
109		list_node_t *lold = list_d2l(list, object);
110		list_insert_before_node(list, lold, nobject);
111	}
112}
113
114void
115list_insert_head(list_t *list, void *object)
116{
117	list_node_t *lold = &list->list_head;
118	list_insert_after_node(list, lold, object);
119}
120
121void
122list_insert_tail(list_t *list, void *object)
123{
124	list_node_t *lold = &list->list_head;
125	list_insert_before_node(list, lold, object);
126}
127
128void
129list_remove(list_t *list, void *object)
130{
131	list_node_t *lold = list_d2l(list, object);
132	ASSERT(!list_empty(list));
133	ASSERT(lold->list_next != NULL);
134	list_remove_node(lold);
135}
136
137void *
138list_remove_head(list_t *list)
139{
140	list_node_t *head = list->list_head.list_next;
141	if (head == &list->list_head)
142		return (NULL);
143	list_remove_node(head);
144	return (list_object(list, head));
145}
146
147void *
148list_remove_tail(list_t *list)
149{
150	list_node_t *tail = list->list_head.list_prev;
151	if (tail == &list->list_head)
152		return (NULL);
153	list_remove_node(tail);
154	return (list_object(list, tail));
155}
156
157void *
158list_head(list_t *list)
159{
160	if (list_empty(list))
161		return (NULL);
162	return (list_object(list, list->list_head.list_next));
163}
164
165void *
166list_tail(list_t *list)
167{
168	if (list_empty(list))
169		return (NULL);
170	return (list_object(list, list->list_head.list_prev));
171}
172
173void *
174list_next(list_t *list, void *object)
175{
176	list_node_t *node = list_d2l(list, object);
177
178	if (node->list_next != &list->list_head)
179		return (list_object(list, node->list_next));
180
181	return (NULL);
182}
183
184void *
185list_prev(list_t *list, void *object)
186{
187	list_node_t *node = list_d2l(list, object);
188
189	if (node->list_prev != &list->list_head)
190		return (list_object(list, node->list_prev));
191
192	return (NULL);
193}
194
195/*
196 *  Insert src list after dst list. Empty src list thereafter.
197 */
198void
199list_move_tail(list_t *dst, list_t *src)
200{
201	list_node_t *dstnode = &dst->list_head;
202	list_node_t *srcnode = &src->list_head;
203
204	ASSERT(dst->list_size == src->list_size);
205	ASSERT(dst->list_offset == src->list_offset);
206
207	if (list_empty(src))
208		return;
209
210	dstnode->list_prev->list_next = srcnode->list_next;
211	srcnode->list_next->list_prev = dstnode->list_prev;
212	dstnode->list_prev = srcnode->list_prev;
213	srcnode->list_prev->list_next = dstnode;
214
215	/* empty src list */
216	srcnode->list_next = srcnode->list_prev = srcnode;
217}
218
219void
220list_link_replace(list_node_t *lold, list_node_t *lnew)
221{
222	ASSERT(list_link_active(lold));
223	ASSERT(!list_link_active(lnew));
224
225	lnew->list_next = lold->list_next;
226	lnew->list_prev = lold->list_prev;
227	lold->list_prev->list_next = lnew;
228	lold->list_next->list_prev = lnew;
229	lold->list_next = lold->list_prev = NULL;
230}
231
232void
233list_link_init(list_node_t *link)
234{
235	link->list_next = NULL;
236	link->list_prev = NULL;
237}
238
239int
240list_link_active(list_node_t *link)
241{
242	return (link->list_next != NULL);
243}
244
245int
246list_is_empty(list_t *list)
247{
248	return (list_empty(list));
249}
250