Cleanup: remove redundant doxygen \file argument
[blender.git] / source / blender / blenlib / intern / BLI_linklist.c
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 \ingroup bli
22  *
23  * Routines for working with single linked lists of 'links' - pointers to other data.
24  *
25  * For double linked lists see 'BLI_listbase.h'.
26  */
27
28 #include <stdlib.h>
29
30 #include "MEM_guardedalloc.h"
31
32 #include "BLI_utildefines.h"
33 #include "BLI_linklist.h"
34 #include "BLI_memarena.h"
35 #include "BLI_mempool.h"
36
37 #include "BLI_strict_flags.h"
38
39 int BLI_linklist_count(const LinkNode *list)
40 {
41         int len;
42
43         for (len = 0; list; list = list->next)
44                 len++;
45
46         return len;
47 }
48
49 int BLI_linklist_index(const LinkNode *list, void *ptr)
50 {
51         int index;
52
53         for (index = 0; list; list = list->next, index++)
54                 if (list->link == ptr)
55                         return index;
56
57         return -1;
58 }
59
60 LinkNode *BLI_linklist_find(LinkNode *list, int index)
61 {
62         int i;
63
64         for (i = 0; list; list = list->next, i++)
65                 if (i == index)
66                         return list;
67
68         return NULL;
69 }
70
71 void BLI_linklist_reverse(LinkNode **listp)
72 {
73         LinkNode *rhead = NULL, *cur = *listp;
74
75         while (cur) {
76                 LinkNode *next = cur->next;
77
78                 cur->next = rhead;
79                 rhead = cur;
80
81                 cur = next;
82         }
83
84         *listp = rhead;
85 }
86
87 /**
88  * Move an item from its current position to a new one inside a single-linked list.
89  * Note *listp may be modified.
90  */
91 void BLI_linklist_move_item(LinkNode **listp, int curr_index, int new_index)
92 {
93         LinkNode *lnk, *lnk_psrc = NULL, *lnk_pdst = NULL;
94         int i;
95
96         if (new_index == curr_index) {
97                 return;
98         }
99
100         if (new_index < curr_index) {
101                 for (lnk = *listp, i = 0; lnk; lnk = lnk->next, i++) {
102                         if (i == new_index - 1) {
103                                 lnk_pdst = lnk;
104                         }
105                         else if (i == curr_index - 1) {
106                                 lnk_psrc = lnk;
107                                 break;
108                         }
109                 }
110
111                 if (!(lnk_psrc && lnk_psrc->next && (!lnk_pdst || lnk_pdst->next))) {
112                         /* Invalid indices, abort. */
113                         return;
114                 }
115
116                 lnk = lnk_psrc->next;
117                 lnk_psrc->next = lnk->next;
118                 if (lnk_pdst) {
119                         lnk->next = lnk_pdst->next;
120                         lnk_pdst->next = lnk;
121                 }
122                 else {
123                         /* destination is first element of the list... */
124                         lnk->next = *listp;
125                         *listp = lnk;
126                 }
127         }
128         else {
129                 for (lnk = *listp, i = 0; lnk; lnk = lnk->next, i++) {
130                         if (i == new_index) {
131                                 lnk_pdst = lnk;
132                                 break;
133                         }
134                         else if (i == curr_index - 1) {
135                                 lnk_psrc = lnk;
136                         }
137                 }
138
139                 if (!(lnk_pdst && (!lnk_psrc || lnk_psrc->next))) {
140                         /* Invalid indices, abort. */
141                         return;
142                 }
143
144                 if (lnk_psrc) {
145                         lnk = lnk_psrc->next;
146                         lnk_psrc->next = lnk->next;
147                 }
148                 else {
149                         /* source is first element of the list... */
150                         lnk = *listp;
151                         *listp = lnk->next;
152                 }
153                 lnk->next = lnk_pdst->next;
154                 lnk_pdst->next = lnk;
155         }
156 }
157
158 /**
159  * A version of prepend that takes the allocated link.
160  */
161 void BLI_linklist_prepend_nlink(LinkNode **listp, void *ptr, LinkNode *nlink)
162 {
163         nlink->link = ptr;
164         nlink->next = *listp;
165         *listp = nlink;
166 }
167
168 void BLI_linklist_prepend(LinkNode **listp, void *ptr)
169 {
170         LinkNode *nlink = MEM_mallocN(sizeof(*nlink), __func__);
171         BLI_linklist_prepend_nlink(listp, ptr, nlink);
172 }
173
174 void BLI_linklist_prepend_arena(LinkNode **listp, void *ptr, MemArena *ma)
175 {
176         LinkNode *nlink = BLI_memarena_alloc(ma, sizeof(*nlink));
177         BLI_linklist_prepend_nlink(listp, ptr, nlink);
178 }
179
180 void BLI_linklist_prepend_pool(LinkNode **listp, void *ptr, BLI_mempool *mempool)
181 {
182         LinkNode *nlink = BLI_mempool_alloc(mempool);
183         BLI_linklist_prepend_nlink(listp, ptr, nlink);
184 }
185
186 /**
187  * A version of append that takes the allocated link.
188  */
189 void BLI_linklist_append_nlink(LinkNodePair *list_pair, void *ptr, LinkNode *nlink)
190 {
191         nlink->link = ptr;
192         nlink->next = NULL;
193
194         if (list_pair->list) {
195                 BLI_assert((list_pair->last_node != NULL) && (list_pair->last_node->next == NULL));
196                 list_pair->last_node->next = nlink;
197         }
198         else {
199                 BLI_assert(list_pair->last_node == NULL);
200                 list_pair->list = nlink;
201         }
202
203         list_pair->last_node = nlink;
204 }
205
206 void BLI_linklist_append(LinkNodePair *list_pair, void *ptr)
207 {
208         LinkNode *nlink = MEM_mallocN(sizeof(*nlink), __func__);
209         BLI_linklist_append_nlink(list_pair, ptr, nlink);
210 }
211
212 void BLI_linklist_append_arena(LinkNodePair *list_pair, void *ptr, MemArena *ma)
213 {
214         LinkNode *nlink = BLI_memarena_alloc(ma, sizeof(*nlink));
215         BLI_linklist_append_nlink(list_pair, ptr, nlink);
216 }
217
218 void BLI_linklist_append_pool(LinkNodePair *list_pair, void *ptr, BLI_mempool *mempool)
219 {
220         LinkNode *nlink = BLI_mempool_alloc(mempool);
221         BLI_linklist_append_nlink(list_pair, ptr, nlink);
222 }
223
224 void *BLI_linklist_pop(struct LinkNode **listp)
225 {
226         /* intentionally no NULL check */
227         void *link = (*listp)->link;
228         void *next = (*listp)->next;
229
230         MEM_freeN(*listp);
231
232         *listp = next;
233         return link;
234 }
235
236 void *BLI_linklist_pop_pool(struct LinkNode **listp, struct BLI_mempool *mempool)
237 {
238         /* intentionally no NULL check */
239         void *link = (*listp)->link;
240         void *next = (*listp)->next;
241
242         BLI_mempool_free(mempool, (*listp));
243
244         *listp = next;
245         return link;
246 }
247
248 void BLI_linklist_insert_after(LinkNode **listp, void *ptr)
249 {
250         LinkNode *nlink = MEM_mallocN(sizeof(*nlink), __func__);
251         LinkNode *node = *listp;
252
253         nlink->link = ptr;
254
255         if (node) {
256                 nlink->next = node->next;
257                 node->next = nlink;
258         }
259         else {
260                 nlink->next = NULL;
261                 *listp = nlink;
262         }
263 }
264
265 void BLI_linklist_free(LinkNode *list, LinkNodeFreeFP freefunc)
266 {
267         while (list) {
268                 LinkNode *next = list->next;
269
270                 if (freefunc)
271                         freefunc(list->link);
272                 MEM_freeN(list);
273
274                 list = next;
275         }
276 }
277
278 void BLI_linklist_free_pool(LinkNode *list, LinkNodeFreeFP freefunc, struct BLI_mempool *mempool)
279 {
280         while (list) {
281                 LinkNode *next = list->next;
282
283                 if (freefunc)
284                         freefunc(list->link);
285                 BLI_mempool_free(mempool, list);
286
287                 list = next;
288         }
289 }
290
291 void BLI_linklist_freeN(LinkNode *list)
292 {
293         while (list) {
294                 LinkNode *next = list->next;
295
296                 MEM_freeN(list->link);
297                 MEM_freeN(list);
298
299                 list = next;
300         }
301 }
302
303 void BLI_linklist_apply(LinkNode *list, LinkNodeApplyFP applyfunc, void *userdata)
304 {
305         for (; list; list = list->next)
306                 applyfunc(list->link, userdata);
307 }
308
309 /* -------------------------------------------------------------------- */
310 /* Sort */
311 #define SORT_IMPL_LINKTYPE LinkNode
312 #define SORT_IMPL_LINKTYPE_DATA link
313
314 /* regular call */
315 #define SORT_IMPL_FUNC linklist_sort_fn
316 #include "list_sort_impl.h"
317 #undef SORT_IMPL_FUNC
318
319 /* reentrant call */
320 #define SORT_IMPL_USE_THUNK
321 #define SORT_IMPL_FUNC linklist_sort_fn_r
322 #include "list_sort_impl.h"
323 #undef SORT_IMPL_FUNC
324 #undef SORT_IMPL_USE_THUNK
325
326 #undef SORT_IMPL_LINKTYPE
327 #undef SORT_IMPL_LINKTYPE_DATA
328
329
330 LinkNode *BLI_linklist_sort(LinkNode *list, int (*cmp)(const void *, const void *))
331 {
332         if (list && list->next) {
333                 list = linklist_sort_fn(list, cmp);
334         }
335         return list;
336 }
337
338 LinkNode *BLI_linklist_sort_r(LinkNode *list, int (*cmp)(void *, const void *, const void *), void *thunk)
339 {
340         if (list && list->next) {
341                 list = linklist_sort_fn_r(list, cmp, thunk);
342         }
343         return list;
344 }