list.c revision 177698 
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 2006 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#define	list_d2l(a, obj) ((list_node_t *)(((char *)obj) + (a)->list_offset))
39#define	list_object(a, node) ((void *)(((char *)node) - (a)->list_offset))
40#define	list_empty(a) ((a)->list_head.list_next == &(a)->list_head)
41
42#define	list_insert_after_node(list, node, object) {	\
43	list_node_t *lnew = list_d2l(list, object);	\
44	lnew->list_prev = node;				\
45	lnew->list_next = node->list_next;		\
46	node->list_next->list_prev = lnew;		\
47	node->list_next = lnew;				\
48}
49
50#define	list_insert_before_node(list, node, object) {	\
51	list_node_t *lnew = list_d2l(list, object);	\
52	lnew->list_next = node;				\
53	lnew->list_prev = node->list_prev;		\
54	node->list_prev->list_next = lnew;		\
55	node->list_prev = lnew;				\
56}
57
58void
59list_create(list_t *list, size_t size, size_t offset)
60{
61	ASSERT(list);
62	ASSERT(size > 0);
63	ASSERT(size >= offset + sizeof (list_node_t));
64
65	list->list_size = size;
66	list->list_offset = offset;
67	list->list_head.list_next = list->list_head.list_prev =
68	    &list->list_head;
69}
70
71void
72list_destroy(list_t *list)
73{
74	list_node_t *node = &list->list_head;
75
76	ASSERT(list);
77	ASSERT(list->list_head.list_next == node);
78	ASSERT(list->list_head.list_prev == node);
79
80	node->list_next = node->list_prev = NULL;
81}
82
83void
84list_insert_after(list_t *list, void *object, void *nobject)
85{
86	list_node_t *lold = list_d2l(list, object);
87	list_insert_after_node(list, lold, nobject);
88}
89
90void
91list_insert_before(list_t *list, void *object, void *nobject)
92{
93	list_node_t *lold = list_d2l(list, object);
94	list_insert_before_node(list, lold, nobject)
95}
96
97void
98list_insert_head(list_t *list, void *object)
99{
100	list_node_t *lold = &list->list_head;
101	list_insert_after_node(list, lold, object);
102}
103
104void
105list_insert_tail(list_t *list, void *object)
106{
107	list_node_t *lold = &list->list_head;
108	list_insert_before_node(list, lold, object);
109}
110
111void
112list_remove(list_t *list, void *object)
113{
114	list_node_t *lold = list_d2l(list, object);
115	ASSERT(!list_empty(list));
116	lold->list_prev->list_next = lold->list_next;
117	lold->list_next->list_prev = lold->list_prev;
118	lold->list_next = lold->list_prev = NULL;
119}
120
121void *
122list_head(list_t *list)
123{
124	if (list_empty(list))
125		return (NULL);
126	return (list_object(list, list->list_head.list_next));
127}
128
129void *
130list_tail(list_t *list)
131{
132	if (list_empty(list))
133		return (NULL);
134	return (list_object(list, list->list_head.list_prev));
135}
136
137void *
138list_next(list_t *list, void *object)
139{
140	list_node_t *node = list_d2l(list, object);
141
142	if (node->list_next != &list->list_head)
143		return (list_object(list, node->list_next));
144
145	return (NULL);
146}
147
148void *
149list_prev(list_t *list, void *object)
150{
151	list_node_t *node = list_d2l(list, object);
152
153	if (node->list_prev != &list->list_head)
154		return (list_object(list, node->list_prev));
155
156	return (NULL);
157}
158
159/*
160 *  Insert src list after dst list. Empty src list thereafter.
161 */
162void
163list_move_tail(list_t *dst, list_t *src)
164{
165	list_node_t *dstnode = &dst->list_head;
166	list_node_t *srcnode = &src->list_head;
167
168	ASSERT(dst->list_size == src->list_size);
169	ASSERT(dst->list_offset == src->list_offset);
170
171	if (list_empty(src))
172		return;
173
174	dstnode->list_prev->list_next = srcnode->list_next;
175	srcnode->list_next->list_prev = dstnode->list_prev;
176	dstnode->list_prev = srcnode->list_prev;
177	srcnode->list_prev->list_next = dstnode;
178
179	/* empty src list */
180	srcnode->list_next = srcnode->list_prev = srcnode;
181}
182
183int
184list_link_active(list_node_t *link)
185{
186	return (link->list_next != NULL);
187}
188
189int
190list_is_empty(list_t *list)
191{
192	return (list_empty(list));
193}
194