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