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
41 static list_node_t *
42 list_d2l(list_t *list, void *obj)
43 {
44 /* Pretty version for lint... */
45 uint64_t *offset = (uint64_t *)obj;
46
47 if (!IS_P2ALIGNED(obj, 8))
48 return (NULL);
49
50 return ((list_node_t *)(offset + (list->list_offset >> 3)));
51 }
52 #else
53 #define list_d2l(a, obj) ((list_node_t *)(((char *)obj) + (a)->list_offset))
54 #endif
55 #define list_object(a, node) ((void *)(((char *)node) - (a)->list_offset))
56 #define list_empty(a) ((a)->list_head.list_next == &(a)->list_head)
57
58 #define list_insert_after_node(list, node, object) { \
59 list_node_t *lnew = list_d2l(list, object); \
60 lnew->list_prev = (node); \
61 lnew->list_next = (node)->list_next; \
62 (node)->list_next->list_prev = lnew; \
63 (node)->list_next = lnew; \
64 }
65
66 #define list_insert_before_node(list, node, object) { \
67 list_node_t *lnew = list_d2l(list, object); \
68 lnew->list_next = (node); \
69 lnew->list_prev = (node)->list_prev; \
70 (node)->list_prev->list_next = lnew; \
71 (node)->list_prev = lnew; \
72 }
73
74 #define list_remove_node(node) \
75 (node)->list_prev->list_next = (node)->list_next; \
76 (node)->list_next->list_prev = (node)->list_prev; \
77 (node)->list_next = (node)->list_prev = NULL
78
79 void
80 list_create(list_t *list, size_t size, size_t offset)
81 {
82 ASSERT(list);
83 ASSERT(size > 0);
84 ASSERT(size >= offset + sizeof (list_node_t));
85
86 list->list_size = size;
87 list->list_offset = offset;
88 list->list_head.list_next = list->list_head.list_prev =
89 &list->list_head;
90 }
91
92 void
93 list_destroy(list_t *list)
94 {
95 list_node_t *node = &list->list_head;
96
97 ASSERT(list);
98 ASSERT(list->list_head.list_next == node);
99 ASSERT(list->list_head.list_prev == node);
100
101 node->list_next = node->list_prev = NULL;
102 }
103
104 void
105 list_insert_after(list_t *list, void *object, void *nobject)
106 {
107 if (object == NULL) {
108 list_insert_head(list, nobject);
109 } else {
110 list_node_t *lold = list_d2l(list, object);
111 list_insert_after_node(list, lold, nobject);
112 }
113 }
114
115 void
116 list_insert_before(list_t *list, void *object, void *nobject)
117 {
118 if (object == NULL) {
119 list_insert_tail(list, nobject);
120 } else {
121 list_node_t *lold = list_d2l(list, object);
122 list_insert_before_node(list, lold, nobject);
123 }
124 }
125
126 void
127 list_insert_head(list_t *list, void *object)
128 {
129 list_node_t *lold = &list->list_head;
130 list_insert_after_node(list, lold, object);
131 }
132
133 void
134 list_insert_tail(list_t *list, void *object)
135 {
136 list_node_t *lold = &list->list_head;
137 list_insert_before_node(list, lold, object);
138 }
139
140 void
141 list_remove(list_t *list, void *object)
142 {
143 list_node_t *lold = list_d2l(list, object);
144 ASSERT(!list_empty(list));
145 ASSERT(lold->list_next != NULL);
146 list_remove_node(lold);
147 }
148
149 void *
150 list_remove_head(list_t *list)
151 {
152 list_node_t *head = list->list_head.list_next;
153 if (head == &list->list_head)
154 return (NULL);
155 list_remove_node(head);
156 return (list_object(list, head));
157 }
158
159 void *
160 list_remove_tail(list_t *list)
161 {
162 list_node_t *tail = list->list_head.list_prev;
163 if (tail == &list->list_head)
164 return (NULL);
165 list_remove_node(tail);
166 return (list_object(list, tail));
167 }
168
169 void *
170 list_head(list_t *list)
171 {
172 if (list_empty(list))
173 return (NULL);
174 return (list_object(list, list->list_head.list_next));
175 }
176
177 void *
178 list_tail(list_t *list)
179 {
180 if (list_empty(list))
181 return (NULL);
182 return (list_object(list, list->list_head.list_prev));
183 }
184
185 void *
186 list_next(list_t *list, void *object)
187 {
188 list_node_t *node = list_d2l(list, object);
189
190 if (node->list_next != &list->list_head)
191 return (list_object(list, node->list_next));
192
193 return (NULL);
194 }
195
196 void *
197 list_prev(list_t *list, void *object)
198 {
199 list_node_t *node = list_d2l(list, object);
200
201 if (node->list_prev != &list->list_head)
202 return (list_object(list, node->list_prev));
203
204 return (NULL);
205 }
206
207 /*
208 * Insert src list after dst list. Empty src list thereafter.
209 */
210 void
211 list_move_tail(list_t *dst, list_t *src)
212 {
213 list_node_t *dstnode = &dst->list_head;
214 list_node_t *srcnode = &src->list_head;
215
216 ASSERT(dst->list_size == src->list_size);
217 ASSERT(dst->list_offset == src->list_offset);
218
219 if (list_empty(src))
220 return;
221
222 dstnode->list_prev->list_next = srcnode->list_next;
223 srcnode->list_next->list_prev = dstnode->list_prev;
224 dstnode->list_prev = srcnode->list_prev;
225 srcnode->list_prev->list_next = dstnode;
226
227 /* empty src list */
228 srcnode->list_next = srcnode->list_prev = srcnode;
229 }
230
231 void
232 list_link_replace(list_node_t *lold, list_node_t *lnew)
233 {
234 ASSERT(list_link_active(lold));
235 ASSERT(!list_link_active(lnew));
236
237 lnew->list_next = lold->list_next;
238 lnew->list_prev = lold->list_prev;
239 lold->list_prev->list_next = lnew;
240 lold->list_next->list_prev = lnew;
241 lold->list_next = lold->list_prev = NULL;
242 }
243
244 void
245 list_link_init(list_node_t *link)
246 {
247 link->list_next = NULL;
248 link->list_prev = NULL;
249 }
250
251 int
252 list_link_active(list_node_t *link)
253 {
254 return (link->list_next != NULL);
255 }
256
257 int
258 list_is_empty(list_t *list)
259 {
260 return (list_empty(list));
261 }