1 /*
2 * This program is free software; you can redistribute it and/or
3 * modify it under the terms of the GNU General Public License
4 * as published by the Free Software Foundation; either version 2
5 * of the License, or (at your option) any later version.
6 *
7 * This program is distributed in the hope that it will be useful,
8 * but WITHOUT ANY WARRANTY; without even the implied warranty of
9 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 * GNU General Public License for more details.
11 *
12 * You should have received a copy of the GNU General Public License
13 * along with this program; if not, write to the Free Software Foundation,
14 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15 *
16 * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
17 * All rights reserved.
18 * Support for linked lists.
19 */
20
21 /** \file
22 * \ingroup bli
23 *
24 * Routines for working with single linked lists of 'links' - pointers to other data.
25 *
26 * For double linked lists see 'BLI_listbase.h'.
27 */
28
29 #include <stdlib.h>
30
31 #include "MEM_guardedalloc.h"
32
33 #include "BLI_linklist.h"
34 #include "BLI_memarena.h"
35 #include "BLI_mempool.h"
36 #include "BLI_utildefines.h"
37
38 #include "BLI_strict_flags.h"
39
BLI_linklist_count(const LinkNode * list)40 int BLI_linklist_count(const LinkNode *list)
41 {
42 int len;
43
44 for (len = 0; list; list = list->next) {
45 len++;
46 }
47
48 return len;
49 }
50
BLI_linklist_index(const LinkNode * list,void * ptr)51 int BLI_linklist_index(const LinkNode *list, void *ptr)
52 {
53 int index;
54
55 for (index = 0; list; list = list->next, index++) {
56 if (list->link == ptr) {
57 return index;
58 }
59 }
60
61 return -1;
62 }
63
BLI_linklist_find(LinkNode * list,int index)64 LinkNode *BLI_linklist_find(LinkNode *list, int index)
65 {
66 int i;
67
68 for (i = 0; list; list = list->next, i++) {
69 if (i == index) {
70 return list;
71 }
72 }
73
74 return NULL;
75 }
76
BLI_linklist_find_last(LinkNode * list)77 LinkNode *BLI_linklist_find_last(LinkNode *list)
78 {
79 if (list) {
80 while (list->next) {
81 list = list->next;
82 }
83 }
84 return list;
85 }
86
BLI_linklist_reverse(LinkNode ** listp)87 void BLI_linklist_reverse(LinkNode **listp)
88 {
89 LinkNode *rhead = NULL, *cur = *listp;
90
91 while (cur) {
92 LinkNode *next = cur->next;
93
94 cur->next = rhead;
95 rhead = cur;
96
97 cur = next;
98 }
99
100 *listp = rhead;
101 }
102
103 /**
104 * Move an item from its current position to a new one inside a single-linked list.
105 * Note *listp may be modified.
106 */
BLI_linklist_move_item(LinkNode ** listp,int curr_index,int new_index)107 void BLI_linklist_move_item(LinkNode **listp, int curr_index, int new_index)
108 {
109 LinkNode *lnk, *lnk_psrc = NULL, *lnk_pdst = NULL;
110 int i;
111
112 if (new_index == curr_index) {
113 return;
114 }
115
116 if (new_index < curr_index) {
117 for (lnk = *listp, i = 0; lnk; lnk = lnk->next, i++) {
118 if (i == new_index - 1) {
119 lnk_pdst = lnk;
120 }
121 else if (i == curr_index - 1) {
122 lnk_psrc = lnk;
123 break;
124 }
125 }
126
127 if (!(lnk_psrc && lnk_psrc->next && (!lnk_pdst || lnk_pdst->next))) {
128 /* Invalid indices, abort. */
129 return;
130 }
131
132 lnk = lnk_psrc->next;
133 lnk_psrc->next = lnk->next;
134 if (lnk_pdst) {
135 lnk->next = lnk_pdst->next;
136 lnk_pdst->next = lnk;
137 }
138 else {
139 /* destination is first element of the list... */
140 lnk->next = *listp;
141 *listp = lnk;
142 }
143 }
144 else {
145 for (lnk = *listp, i = 0; lnk; lnk = lnk->next, i++) {
146 if (i == new_index) {
147 lnk_pdst = lnk;
148 break;
149 }
150 if (i == curr_index - 1) {
151 lnk_psrc = lnk;
152 }
153 }
154
155 if (!(lnk_pdst && (!lnk_psrc || lnk_psrc->next))) {
156 /* Invalid indices, abort. */
157 return;
158 }
159
160 if (lnk_psrc) {
161 lnk = lnk_psrc->next;
162 lnk_psrc->next = lnk->next;
163 }
164 else {
165 /* source is first element of the list... */
166 lnk = *listp;
167 *listp = lnk->next;
168 }
169 lnk->next = lnk_pdst->next;
170 lnk_pdst->next = lnk;
171 }
172 }
173
174 /**
175 * A version of prepend that takes the allocated link.
176 */
BLI_linklist_prepend_nlink(LinkNode ** listp,void * ptr,LinkNode * nlink)177 void BLI_linklist_prepend_nlink(LinkNode **listp, void *ptr, LinkNode *nlink)
178 {
179 nlink->link = ptr;
180 nlink->next = *listp;
181 *listp = nlink;
182 }
183
BLI_linklist_prepend(LinkNode ** listp,void * ptr)184 void BLI_linklist_prepend(LinkNode **listp, void *ptr)
185 {
186 LinkNode *nlink = MEM_mallocN(sizeof(*nlink), __func__);
187 BLI_linklist_prepend_nlink(listp, ptr, nlink);
188 }
189
BLI_linklist_prepend_arena(LinkNode ** listp,void * ptr,MemArena * ma)190 void BLI_linklist_prepend_arena(LinkNode **listp, void *ptr, MemArena *ma)
191 {
192 LinkNode *nlink = BLI_memarena_alloc(ma, sizeof(*nlink));
193 BLI_linklist_prepend_nlink(listp, ptr, nlink);
194 }
195
BLI_linklist_prepend_pool(LinkNode ** listp,void * ptr,BLI_mempool * mempool)196 void BLI_linklist_prepend_pool(LinkNode **listp, void *ptr, BLI_mempool *mempool)
197 {
198 LinkNode *nlink = BLI_mempool_alloc(mempool);
199 BLI_linklist_prepend_nlink(listp, ptr, nlink);
200 }
201
202 /**
203 * A version of append that takes the allocated link.
204 */
BLI_linklist_append_nlink(LinkNodePair * list_pair,void * ptr,LinkNode * nlink)205 void BLI_linklist_append_nlink(LinkNodePair *list_pair, void *ptr, LinkNode *nlink)
206 {
207 nlink->link = ptr;
208 nlink->next = NULL;
209
210 if (list_pair->list) {
211 BLI_assert((list_pair->last_node != NULL) && (list_pair->last_node->next == NULL));
212 list_pair->last_node->next = nlink;
213 }
214 else {
215 BLI_assert(list_pair->last_node == NULL);
216 list_pair->list = nlink;
217 }
218
219 list_pair->last_node = nlink;
220 }
221
BLI_linklist_append(LinkNodePair * list_pair,void * ptr)222 void BLI_linklist_append(LinkNodePair *list_pair, void *ptr)
223 {
224 LinkNode *nlink = MEM_mallocN(sizeof(*nlink), __func__);
225 BLI_linklist_append_nlink(list_pair, ptr, nlink);
226 }
227
BLI_linklist_append_arena(LinkNodePair * list_pair,void * ptr,MemArena * ma)228 void BLI_linklist_append_arena(LinkNodePair *list_pair, void *ptr, MemArena *ma)
229 {
230 LinkNode *nlink = BLI_memarena_alloc(ma, sizeof(*nlink));
231 BLI_linklist_append_nlink(list_pair, ptr, nlink);
232 }
233
BLI_linklist_append_pool(LinkNodePair * list_pair,void * ptr,BLI_mempool * mempool)234 void BLI_linklist_append_pool(LinkNodePair *list_pair, void *ptr, BLI_mempool *mempool)
235 {
236 LinkNode *nlink = BLI_mempool_alloc(mempool);
237 BLI_linklist_append_nlink(list_pair, ptr, nlink);
238 }
239
BLI_linklist_pop(struct LinkNode ** listp)240 void *BLI_linklist_pop(struct LinkNode **listp)
241 {
242 /* intentionally no NULL check */
243 void *link = (*listp)->link;
244 void *next = (*listp)->next;
245
246 MEM_freeN(*listp);
247
248 *listp = next;
249 return link;
250 }
251
BLI_linklist_pop_pool(struct LinkNode ** listp,struct BLI_mempool * mempool)252 void *BLI_linklist_pop_pool(struct LinkNode **listp, struct BLI_mempool *mempool)
253 {
254 /* intentionally no NULL check */
255 void *link = (*listp)->link;
256 void *next = (*listp)->next;
257
258 BLI_mempool_free(mempool, (*listp));
259
260 *listp = next;
261 return link;
262 }
263
BLI_linklist_insert_after(LinkNode ** listp,void * ptr)264 void BLI_linklist_insert_after(LinkNode **listp, void *ptr)
265 {
266 LinkNode *nlink = MEM_mallocN(sizeof(*nlink), __func__);
267 LinkNode *node = *listp;
268
269 nlink->link = ptr;
270
271 if (node) {
272 nlink->next = node->next;
273 node->next = nlink;
274 }
275 else {
276 nlink->next = NULL;
277 *listp = nlink;
278 }
279 }
280
BLI_linklist_free(LinkNode * list,LinkNodeFreeFP freefunc)281 void BLI_linklist_free(LinkNode *list, LinkNodeFreeFP freefunc)
282 {
283 while (list) {
284 LinkNode *next = list->next;
285
286 if (freefunc) {
287 freefunc(list->link);
288 }
289 MEM_freeN(list);
290
291 list = next;
292 }
293 }
294
BLI_linklist_free_pool(LinkNode * list,LinkNodeFreeFP freefunc,struct BLI_mempool * mempool)295 void BLI_linklist_free_pool(LinkNode *list, LinkNodeFreeFP freefunc, struct BLI_mempool *mempool)
296 {
297 while (list) {
298 LinkNode *next = list->next;
299
300 if (freefunc) {
301 freefunc(list->link);
302 }
303 BLI_mempool_free(mempool, list);
304
305 list = next;
306 }
307 }
308
BLI_linklist_freeN(LinkNode * list)309 void BLI_linklist_freeN(LinkNode *list)
310 {
311 while (list) {
312 LinkNode *next = list->next;
313
314 MEM_freeN(list->link);
315 MEM_freeN(list);
316
317 list = next;
318 }
319 }
320
BLI_linklist_apply(LinkNode * list,LinkNodeApplyFP applyfunc,void * userdata)321 void BLI_linklist_apply(LinkNode *list, LinkNodeApplyFP applyfunc, void *userdata)
322 {
323 for (; list; list = list->next) {
324 applyfunc(list->link, userdata);
325 }
326 }
327
328 /* -------------------------------------------------------------------- */
329 /* Sort */
330 #define SORT_IMPL_LINKTYPE LinkNode
331 #define SORT_IMPL_LINKTYPE_DATA link
332
333 /* regular call */
334 #define SORT_IMPL_FUNC linklist_sort_fn
335 #include "list_sort_impl.h"
336 #undef SORT_IMPL_FUNC
337
338 /* re-entrant call */
339 #define SORT_IMPL_USE_THUNK
340 #define SORT_IMPL_FUNC linklist_sort_fn_r
341 #include "list_sort_impl.h"
342 #undef SORT_IMPL_FUNC
343 #undef SORT_IMPL_USE_THUNK
344
345 #undef SORT_IMPL_LINKTYPE
346 #undef SORT_IMPL_LINKTYPE_DATA
347
BLI_linklist_sort(LinkNode * list,int (* cmp)(const void *,const void *))348 LinkNode *BLI_linklist_sort(LinkNode *list, int (*cmp)(const void *, const void *))
349 {
350 if (list && list->next) {
351 list = linklist_sort_fn(list, cmp);
352 }
353 return list;
354 }
355
BLI_linklist_sort_r(LinkNode * list,int (* cmp)(void *,const void *,const void *),void * thunk)356 LinkNode *BLI_linklist_sort_r(LinkNode *list,
357 int (*cmp)(void *, const void *, const void *),
358 void *thunk)
359 {
360 if (list && list->next) {
361 list = linklist_sort_fn_r(list, cmp, thunk);
362 }
363 return list;
364 }
365