1/*
2 * Copyright 2003-2006, Axel D��rfler, axeld@pinc-software.de. All rights reserved.
3 * Distributed under the terms of the MIT License.
4 */
5
6
7#include <util/list.h>
8#include <util/DoublyLinkedList.h>
9#include <BytePointer.h>
10
11
12#define GET_ITEM(list, item) ({ BytePointer<void> pointer((uint8*)item \
13	- list->offset); &pointer; })
14#define GET_LINK(list, item) ({ BytePointer<list_link> pointer((uint8*)item \
15	+ list->offset); &pointer; })
16
17STATIC_ASSERT(sizeof(DoublyLinkedListLink<void*>) == sizeof(list_link));
18
19
20/** Initializes the list with a specified offset to the link
21 *	structure in the items that will be part of the list.
22 */
23
24void
25list_init_etc(struct list *list, int32 offset)
26{
27	list->link.next = list->link.prev = &list->link;
28	list->offset = offset;
29}
30
31
32void
33list_init(struct list *list)
34{
35	list_init_etc(list, 0);
36}
37
38
39/** Adds a link to the head of the list
40 */
41
42void
43list_add_link_to_head(struct list *list, void *_link)
44{
45	list_link *link = (list_link *)_link;
46
47	link->next = list->link.next;
48	link->prev = &list->link;
49
50	list->link.next->prev = link;
51	list->link.next = link;
52
53#if DEBUG_DOUBLY_LINKED_LIST
54	ASSERT(link->next != link);
55#endif
56}
57
58
59/** Adds a link to the tail of the list
60 */
61
62void
63list_add_link_to_tail(struct list *list, void *_link)
64{
65	list_link *link = (list_link *)_link;
66
67	link->next = &list->link;
68	link->prev = list->link.prev;
69
70	list->link.prev->next = link;
71	list->link.prev = link;
72
73#if DEBUG_DOUBLY_LINKED_LIST
74	ASSERT(link->prev != link);
75#endif
76}
77
78
79/** Removes a link from the list it's currently in.
80 *	Note: the link has to be in a list when you call this function.
81 */
82
83void
84list_remove_link(void *_link)
85{
86	list_link *link = (list_link *)_link;
87
88	link->next->prev = link->prev;
89	link->prev->next = link->next;
90
91#if DEBUG_DOUBLY_LINKED_LIST
92	link->prev = link->next = NULL;
93#endif
94}
95
96
97static inline list_link *
98get_next_link(struct list *list, list_link *link)
99{
100	if (link->next == &list->link)
101		return NULL;
102
103	return link->next;
104}
105
106
107static inline list_link *
108get_prev_link(struct list *list, list_link *link)
109{
110	if (link->prev == &list->link)
111		return NULL;
112
113	return link->prev;
114}
115
116
117/** Gets the successor for the current item. If the passed
118 *	item is NULL, it returns the first entry in the list,
119 *	if there is one.
120 *	Returns NULL if there aren't any more items in this list.
121 */
122
123void *
124list_get_next_item(struct list *list, void *item)
125{
126	list_link *link;
127
128	if (item == NULL)
129		return list_is_empty(list) ? NULL : GET_ITEM(list, list->link.next);
130
131	link = get_next_link(list, GET_LINK(list, item));
132	return link != NULL ? GET_ITEM(list, link) : NULL;
133}
134
135
136/** Gets the predecessor for the current item. If the passed
137 *	item is NULL, it returns the last entry in the list,
138 *	if there is one.
139 *	Returns NULL if there aren't any previous items in this list.
140 */
141
142void *
143list_get_prev_item(struct list *list, void *item)
144{
145	list_link *link;
146
147	if (item == NULL)
148		return list_is_empty(list) ? NULL : GET_ITEM(list, list->link.prev);
149
150	link = get_prev_link(list, GET_LINK(list, item));
151	return link != NULL ? GET_ITEM(list, link) : NULL;
152}
153
154
155void *
156list_get_last_item(struct list *list)
157{
158	return list_is_empty(list) ? NULL : GET_ITEM(list, list->link.prev);
159}
160
161
162/** Adds an item to the end of the list.
163 *	Similar to list_add_link_to_tail() but works on the item, not the link.
164 */
165
166void
167list_add_item(struct list *list, void *item)
168{
169	list_add_link_to_tail(list, GET_LINK(list, item));
170}
171
172
173/** Removes an item from the list.
174 *	Similar to list_remove_link() but works on the item, not the link.
175 */
176
177void
178list_remove_item(struct list *list, void *item)
179{
180	list_remove_link(GET_LINK(list, item));
181}
182
183
184/** Inserts an item before another item in the list.
185 *	If you pass NULL as \a before item, the item is added at the end of
186 *	the list.
187 */
188
189void
190list_insert_item_before(struct list *list, void *before, void *item)
191{
192	list_link *beforeLink;
193	list_link *link;
194
195	if (before == NULL) {
196		list_add_item(list, item);
197		return;
198	}
199
200	beforeLink = GET_LINK(list, before);
201	link = GET_LINK(list, item);
202
203	link->prev = beforeLink->prev;
204	link->next = beforeLink;
205
206	beforeLink->prev->next = link;
207	beforeLink->prev = link;
208}
209
210
211/** Removes the first item in the list and returns it.
212 *	Returns NULL if the list is empty.
213 */
214
215void *
216list_remove_head_item(struct list *list)
217{
218	list_link *link;
219
220	if (list_is_empty(list))
221		return NULL;
222
223	list_remove_link(link = list->link.next);
224	return GET_ITEM(list, link);
225}
226
227
228/** Removes the last item in the list and returns it.
229 *	Returns NULL if the list is empty.
230 */
231
232void *
233list_remove_tail_item(struct list *list)
234{
235	list_link *link;
236
237	if (list_is_empty(list))
238		return NULL;
239
240	list_remove_link(link = list->link.prev);
241	return GET_ITEM(list, link);
242}
243
244
245/**	Moves the contents of the source list to the target list.
246 *	The target list will be emptied before the items are moved;
247 *	this is a very fast operation.
248 */
249
250void
251list_move_to_list(struct list *sourceList, struct list *targetList)
252{
253	if (list_is_empty(sourceList)) {
254		targetList->link.next = targetList->link.prev = &targetList->link;
255		return;
256	}
257
258	*targetList = *sourceList;
259
260	// correct link pointers to this list
261	targetList->link.next->prev = &targetList->link;
262	targetList->link.prev->next = &targetList->link;
263
264	// empty source list
265	sourceList->link.next = sourceList->link.prev = &sourceList->link;
266}
267
268
269