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