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