1 /** @file list.c Doubly linked list.
2
3 @authors Copyright (c) 2017 Jaakko Keränen <jaakko.keranen@iki.fi>
4
5 @par License
6
7 Redistribution and use in source and binary forms, with or without
8 modification, are permitted provided that the following conditions are met:
9
10 1. Redistributions of source code must retain the above copyright notice, this
11 list of conditions and the following disclaimer.
12 2. Redistributions in binary form must reproduce the above copyright notice,
13 this list of conditions and the following disclaimer in the documentation
14 and/or other materials provided with the distribution.
15
16 <small>THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
18 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
19 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
20 ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
21 (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
22 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
23 ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.</small>
26 */
27
28 #include "the_Foundation/list.h"
29
30 #include <stdlib.h>
31
32 #define iListNode_(ptr) ((iListNode *) (ptr))
33
nextNode_List_(const iList * d,const iListNode * node)34 static iListNode *nextNode_List_(const iList *d, const iListNode *node) {
35 if (!node || node->next == &d->root) return NULL;
36 return node->next;
37 }
38
prevNode_List_(const iList * d,const iListNode * node)39 static iListNode *prevNode_List_(const iList *d, const iListNode *node) {
40 if (!node || node->prev == &d->root) return NULL;
41 return node->prev;
42 }
43
iDefineTypeConstruction(List)44 iDefineTypeConstruction(List)
45
46 void init_List(iList *d) {
47 clear_List(d);
48 }
49
deinit_List(iList * d)50 void deinit_List(iList *d) {
51 /* List doesn't own any memory, so nothing needs to be deinitialized. */
52 iUnused(d);
53 }
54
size_List(const iList * d)55 size_t size_List(const iList *d) {
56 return d ? d->size : 0;
57 }
58
front_List(const iList * d)59 void *front_List(const iList *d) {
60 return d->size > 0? d->root.next : NULL;
61 }
62
back_List(const iList * d)63 void *back_List(const iList *d) {
64 return d->size > 0? d->root.prev : NULL;
65 }
66
clear_List(iList * d)67 void clear_List(iList *d) {
68 d->root.next = d->root.prev = &d->root;
69 d->size = 0;
70 }
71
pushBack_List(iList * d,iAny * node)72 iAny *pushBack_List(iList *d, iAny *node) {
73 return insertBefore_List(d, &d->root, node);
74 }
75
pushFront_List(iList * d,iAny * node)76 iAny *pushFront_List(iList *d, iAny *node) {
77 return insertAfter_List(d, &d->root, node);
78 }
79
insertAfter_ListNode_(iListNode * d,iListNode * after)80 static void insertAfter_ListNode_(iListNode *d, iListNode *after) {
81 d->next = after->next;
82 after->next->prev = d;
83 d->prev = after;
84 after->next = d;
85 }
86
insertBefore_ListNode_(iListNode * d,iListNode * before)87 static void insertBefore_ListNode_(iListNode *d, iListNode *before) {
88 d->prev = before->prev;
89 before->prev->next = d;
90 d->next = before;
91 before->prev = d;
92 }
93
insertAfter_List(iList * d,iAny * after,iAny * node)94 iAny *insertAfter_List(iList *d, iAny *after, iAny *node) {
95 iAssert(node);
96 if (!after) after = d->root.prev;
97 insertAfter_ListNode_(node, after);
98 d->size++;
99 return node;
100 }
101
insertBefore_List(iList * d,iAny * before,iAny * node)102 iAny *insertBefore_List(iList *d, iAny *before, iAny *node) {
103 iAssert(node);
104 if (!before) before = d->root.next;
105 insertBefore_ListNode_(node, before);
106 d->size++;
107 return node;
108 }
109
popFront_List(iList * d)110 iAny *popFront_List(iList *d) {
111 if (d->size == 0) return NULL;
112 return remove_List(d, front_List(d));
113 }
114
popBack_List(iList * d)115 iAny *popBack_List(iList *d) {
116 if (d->size == 0) return NULL;
117 return remove_List(d, back_List(d));
118 }
119
remove_ListNode_(iListNode * d)120 static void remove_ListNode_(iListNode *d) {
121 d->next->prev = d->prev;
122 d->prev->next = d->next;
123 d->next = d->prev = NULL;
124 }
125
remove_List(iList * d,iAny * node)126 iAny *remove_List(iList *d, iAny *node) {
127 iAssert(node);
128 iAssert(d->size > 0);
129 d->size--;
130 remove_ListNode_(node);
131 return node;
132 }
133
quicksortPartition_ListNode_(iListNode ** low,iListNode ** high,iListCompareFunc cmp)134 static iListNode *quicksortPartition_ListNode_(iListNode **low, iListNode **high,
135 iListCompareFunc cmp) {
136 iListNode *pivot = *high;
137 iListNode *prev;
138 for (iListNode *i = pivot->prev; i != *low; i = prev) {
139 prev = i->prev;
140 if (cmp(i, pivot) > 0) {
141 remove_ListNode_(i);
142 insertAfter_ListNode_(i, pivot);
143 if (*high == pivot) *high = i;
144 }
145 }
146 if (cmp(*low, pivot) > 0) {
147 iListNode *i = *low;
148 *low = i->next;
149 remove_ListNode_(i);
150 insertAfter_ListNode_(i, pivot);
151 if (*high == pivot) *high = i;
152 }
153 return pivot;
154 }
155
quicksort_ListNode_(iListNode ** start,iListNode ** end,iListCompareFunc cmp)156 static void quicksort_ListNode_(iListNode **start, iListNode **end,
157 iListCompareFunc cmp) {
158 if (*start != *end) {
159 iListNode *p = quicksortPartition_ListNode_(start, end, cmp);
160 /* Recurse to both halves. */
161 if (p != *start) {
162 iListNode *firstHalf = p->prev;
163 quicksort_ListNode_(start, &firstHalf, cmp);
164 }
165 if (p != *end) {
166 iListNode *secondHalf = p->next;
167 quicksort_ListNode_(&secondHalf, end, cmp);
168 }
169 }
170 }
171
sort_List(iList * d,iListCompareFunc cmp)172 void sort_List(iList *d, iListCompareFunc cmp) {
173 if (size_List(d) >= 2) {
174 iListNode *start = front_List(d);
175 iListNode *end = back_List(d);
176 quicksort_ListNode_(&start, &end, cmp);
177 }
178 }
179
180 /*-------------------------------------------------------------------------------------*/
181
182 #define init_ListIterator_(d, list) \
183 { d->list = list; \
184 d->value = nextNode_List_(list, &list->root); \
185 d->next = nextNode_List_(list, d->value); }
186
187 #define next_ListIterator_(d) \
188 { d->value = d->next; \
189 d->next = nextNode_List_(d->list, d->value); }
190
init_ListIterator(iListIterator * d,iList * list)191 void init_ListIterator(iListIterator *d, iList *list) {
192 init_ListIterator_(d, list);
193 }
194
next_ListIterator(iListIterator * d)195 void next_ListIterator(iListIterator *d) {
196 next_ListIterator_(d);
197 }
198
init_ListConstIterator(iListConstIterator * d,const iList * list)199 void init_ListConstIterator(iListConstIterator *d, const iList *list) {
200 init_ListIterator_(d, list);
201 }
202
next_ListConstIterator(iListConstIterator * d)203 void next_ListConstIterator(iListConstIterator *d) {
204 next_ListIterator_(d);
205 }
206
207 /*-------------------------------------------------------------------------------------*/
208
209 #define init_ListReverseIterator_(d, list) \
210 { d->list = list; \
211 d->value = prevNode_List_(list, &list->root); \
212 d->next = prevNode_List_(list, d->value); }
213
214 #define next_ListReverseIterator_(d) \
215 { d->value = d->next; \
216 d->next = prevNode_List_(d->list, d->value); }
217
init_ListReverseIterator(iListReverseIterator * d,iList * list)218 void init_ListReverseIterator(iListReverseIterator *d, iList *list) {
219 init_ListReverseIterator_(d, list);
220 }
221
next_ListReverseIterator(iListReverseIterator * d)222 void next_ListReverseIterator(iListReverseIterator *d) {
223 next_ListReverseIterator_(d);
224 }
225
init_ListReverseConstIterator(iListReverseConstIterator * d,const iList * list)226 void init_ListReverseConstIterator(iListReverseConstIterator *d, const iList *list) {
227 init_ListReverseIterator_(d, list);
228 }
229
next_ListReverseConstIterator(iListReverseConstIterator * d)230 void next_ListReverseConstIterator(iListReverseConstIterator *d) {
231 next_ListReverseIterator_(d);
232 }
233