Merge branch 'master' into blender2.8
[blender.git] / source / blender / blenlib / intern / listbase.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  * 
27  */
28
29 /** \file blender/blenlib/intern/listbase.c
30  *  \ingroup bli
31  *
32  * Manipulations on ListBase structs
33  */
34
35 #include <string.h>
36 #include <stdlib.h>
37
38
39 #include "MEM_guardedalloc.h"
40
41 #include "DNA_listBase.h"
42
43 #include "BLI_listbase.h"
44
45 #include "BLI_strict_flags.h"
46
47 /* implementation */
48
49 /**
50  * moves the entire contents of \a src onto the end of \a dst.
51  */
52 void BLI_movelisttolist(ListBase *dst, ListBase *src)
53 {
54         if (src->first == NULL) return;
55
56         if (dst->first == NULL) {
57                 dst->first = src->first;
58                 dst->last = src->last;
59         }
60         else {
61                 ((Link *)dst->last)->next = src->first;
62                 ((Link *)src->first)->prev = dst->last;
63                 dst->last = src->last;
64         }
65         src->first = src->last = NULL;
66 }
67
68 /**
69  * Prepends \a vlink (assumed to begin with a Link) onto listbase.
70  */
71 void BLI_addhead(ListBase *listbase, void *vlink)
72 {
73         Link *link = vlink;
74
75         if (link == NULL) return;
76
77         link->next = listbase->first;
78         link->prev = NULL;
79
80         if (listbase->first) ((Link *)listbase->first)->prev = link;
81         if (listbase->last == NULL) listbase->last = link;
82         listbase->first = link;
83 }
84
85
86 /**
87  * Appends \a vlink (assumed to begin with a Link) onto listbase.
88  */
89 void BLI_addtail(ListBase *listbase, void *vlink)
90 {
91         Link *link = vlink;
92
93         if (link == NULL) return;
94
95         link->next = NULL;
96         link->prev = listbase->last;
97
98         if (listbase->last) ((Link *)listbase->last)->next = link;
99         if (listbase->first == NULL) listbase->first = link;
100         listbase->last = link;
101 }
102
103
104 /**
105  * Removes \a vlink from \a listbase. Assumes it is linked into there!
106  */
107 void BLI_remlink(ListBase *listbase, void *vlink)
108 {
109         Link *link = vlink;
110
111         if (link == NULL) return;
112
113         if (link->next) link->next->prev = link->prev;
114         if (link->prev) link->prev->next = link->next;
115
116         if (listbase->last == link) listbase->last = link->prev;
117         if (listbase->first == link) listbase->first = link->next;
118 }
119
120 /**
121  * Checks that \a vlink is linked into listbase, removing it from there if so.
122  */
123 bool BLI_remlink_safe(ListBase *listbase, void *vlink)
124 {
125         if (BLI_findindex(listbase, vlink) != -1) {
126                 BLI_remlink(listbase, vlink);
127                 return true;
128         }
129         else {
130                 return false;
131         }
132 }
133
134 /**
135  * Swaps \a vlinka and \a vlinkb in the list. Assumes they are both already in the list!
136  */
137 void BLI_listbase_swaplinks(ListBase *listbase, void *vlinka, void *vlinkb)
138 {
139         Link *linka = vlinka;
140         Link *linkb = vlinkb;
141
142         if (!linka || !linkb)
143                 return;
144
145         if (linkb->next == linka) {
146                 SWAP(Link *, linka, linkb);
147         }
148
149         if (linka->next == linkb) {
150                 linka->next = linkb->next;
151                 linkb->prev = linka->prev;
152                 linka->prev = linkb;
153                 linkb->next = linka;
154         }
155         else {  /* Non-contiguous items, we can safely swap. */
156                 SWAP(Link *, linka->prev, linkb->prev);
157                 SWAP(Link *, linka->next, linkb->next);
158         }
159
160         /* Update neighbors of linka and linkb. */
161         if (linka->prev) linka->prev->next = linka;
162         if (linka->next) linka->next->prev = linka;
163         if (linkb->prev) linkb->prev->next = linkb;
164         if (linkb->next) linkb->next->prev = linkb;
165
166         if (listbase->last == linka) listbase->last = linkb;
167         else if (listbase->last == linkb) listbase->last = linka;
168         if (listbase->first == linka) listbase->first = linkb;
169         else if (listbase->first == linkb) listbase->first = linka;
170 }
171
172 /**
173  * Swaps \a vlinka and \a vlinkb from their respective lists. Assumes they are both already in their lista!
174  */
175 void BLI_listbases_swaplinks(ListBase *listbasea, ListBase *listbaseb, void *vlinka, void *vlinkb)
176 {
177         Link *linka = vlinka;
178         Link *linkb = vlinkb;
179         Link linkc = {NULL};
180
181         if (!linka || !linkb) {
182                 return;
183         }
184
185         /* Temporary link to use as placeholder of the links positions */
186         BLI_insertlinkafter(listbasea, linka, &linkc);
187
188         /* Bring linka into linkb position */
189         BLI_remlink(listbasea, linka);
190         BLI_insertlinkafter(listbaseb, linkb, linka);
191
192         /* Bring linkb into linka position */
193         BLI_remlink(listbaseb, linkb);
194         BLI_insertlinkafter(listbasea, &linkc, linkb);
195
196         /* Remove temporary link */
197         BLI_remlink(listbasea, &linkc);
198 }
199
200 /**
201  * Removes the head from \a listbase and returns it.
202  */
203 void *BLI_pophead(ListBase *listbase)
204 {
205         Link *link;
206         if ((link = listbase->first)) {
207                 BLI_remlink(listbase, link);
208         }
209         return link;
210 }
211
212
213 /**
214  * Removes the tail from \a listbase and returns it.
215  */
216 void *BLI_poptail(ListBase *listbase)
217 {
218         Link *link;
219         if ((link = listbase->last)) {
220                 BLI_remlink(listbase, link);
221         }
222         return link;
223 }
224
225 /**
226  * Removes \a vlink from listbase and disposes of it. Assumes it is linked into there!
227  */
228 void BLI_freelinkN(ListBase *listbase, void *vlink)
229 {
230         Link *link = vlink;
231
232         if (link == NULL) return;
233
234         BLI_remlink(listbase, link);
235         MEM_freeN(link);
236 }
237
238 /**
239  * Assigns all #Link.prev pointers from #Link.next
240  */
241 static void listbase_double_from_single(Link *iter, ListBase *listbase)
242 {
243         Link *prev = NULL;
244         listbase->first = iter;
245         do {
246                 iter->prev = prev;
247                 prev = iter;
248         } while ((iter = iter->next));
249         listbase->last = prev;
250 }
251
252 #define SORT_IMPL_LINKTYPE Link
253
254 /* regular call */
255 #define SORT_IMPL_FUNC listbase_sort_fn
256 #include "list_sort_impl.h"
257 #undef SORT_IMPL_FUNC
258
259 /* reentrant call */
260 #define SORT_IMPL_USE_THUNK
261 #define SORT_IMPL_FUNC listbase_sort_fn_r
262 #include "list_sort_impl.h"
263 #undef SORT_IMPL_FUNC
264 #undef SORT_IMPL_USE_THUNK
265
266 #undef SORT_IMPL_LINKTYPE
267
268 /**
269  * Sorts the elements of listbase into the order defined by cmp
270  * (which should return 1 if its first arg should come after its second arg).
271  * This uses insertion sort, so NOT ok for large list.
272  */
273 void BLI_listbase_sort(ListBase *listbase, int (*cmp)(const void *, const void *))
274 {
275         if (listbase->first != listbase->last) {
276                 Link *head = listbase->first;
277                 head = listbase_sort_fn(head, cmp);
278                 listbase_double_from_single(head, listbase);
279         }
280 }
281
282 void BLI_listbase_sort_r(ListBase *listbase, int (*cmp)(void *, const void *, const void *), void *thunk)
283 {
284         if (listbase->first != listbase->last) {
285                 Link *head = listbase->first;
286                 head = listbase_sort_fn_r(head, cmp, thunk);
287                 listbase_double_from_single(head, listbase);
288         }
289 }
290
291 /**
292  * Inserts \a vnewlink immediately following \a vprevlink in \a listbase.
293  * Or, if \a vprevlink is NULL, puts \a vnewlink at the front of the list.
294  */
295 void BLI_insertlinkafter(ListBase *listbase, void *vprevlink, void *vnewlink)
296 {
297         Link *prevlink = vprevlink;
298         Link *newlink = vnewlink;
299
300         /* newlink before nextlink */
301         if (newlink == NULL) return;
302
303         /* empty list */
304         if (listbase->first == NULL) {
305                 listbase->first = newlink;
306                 listbase->last = newlink;
307                 return;
308         }
309         
310         /* insert at head of list */
311         if (prevlink == NULL) {
312                 newlink->prev = NULL;
313                 newlink->next = listbase->first;
314                 newlink->next->prev = newlink;
315                 listbase->first = newlink;
316                 return;
317         }
318
319         /* at end of list */
320         if (listbase->last == prevlink) {
321                 listbase->last = newlink;
322         }
323
324         newlink->next = prevlink->next;
325         newlink->prev = prevlink;
326         prevlink->next = newlink;
327         if (newlink->next) {
328                 newlink->next->prev = newlink;
329         }
330 }
331
332 /**
333  * Inserts \a vnewlink immediately preceding \a vnextlink in listbase.
334  * Or, if \a vnextlink is NULL, puts \a vnewlink at the end of the list.
335  */
336 void BLI_insertlinkbefore(ListBase *listbase, void *vnextlink, void *vnewlink)
337 {
338         Link *nextlink = vnextlink;
339         Link *newlink = vnewlink;
340
341         /* newlink before nextlink */
342         if (newlink == NULL) return;
343
344         /* empty list */
345         if (listbase->first == NULL) {
346                 listbase->first = newlink;
347                 listbase->last = newlink;
348                 return;
349         }
350         
351         /* insert at end of list */
352         if (nextlink == NULL) {
353                 newlink->prev = listbase->last;
354                 newlink->next = NULL;
355                 ((Link *)listbase->last)->next = newlink;
356                 listbase->last = newlink;
357                 return;
358         }
359
360         /* at beginning of list */
361         if (listbase->first == nextlink) {
362                 listbase->first = newlink;
363         }
364
365         newlink->next = nextlink;
366         newlink->prev = nextlink->prev;
367         nextlink->prev = newlink;
368         if (newlink->prev) {
369                 newlink->prev->next = newlink;
370         }
371 }
372
373
374 /**
375  * Insert a link in place of another, without changing it's position in the list.
376  *
377  * Puts `vnewlink` in the position of `vreplacelink`, removing `vreplacelink`.
378  * - `vreplacelink` *must* be in the list.
379  * - `vnewlink` *must not* be in the list.
380  */
381 void BLI_insertlinkreplace(ListBase *listbase, void *vreplacelink, void *vnewlink)
382 {
383         Link *l_old = vreplacelink;
384         Link *l_new = vnewlink;
385
386         /* update adjacent links */
387         if (l_old->next != NULL) {
388                 l_old->next->prev = l_new;
389         }
390         if (l_old->prev != NULL) {
391                 l_old->prev->next = l_new;
392         }
393
394         /* set direct links */
395         l_new->next = l_old->next;
396         l_new->prev = l_old->prev;
397
398          /* update list */
399         if (listbase->first == l_old) {
400                 listbase->first = l_new;
401         }
402         if (listbase->last == l_old) {
403                 listbase->last = l_new;
404         }
405 }
406
407 /**
408  * Reinsert \a vlink relative to its current position but offset by \a step. Doesn't move
409  * item if new position would exceed list (could optionally move to head/tail).
410  *
411  * \param step: Absolute value defines step size, sign defines direction. E.g pass -1
412  *              to move \a vlink before previous, or 1 to move behind next.
413  * \return If position of \a vlink has changed.
414  */
415 bool BLI_listbase_link_move(ListBase *listbase, void *vlink, int step)
416 {
417         Link *link = vlink;
418         Link *hook = link;
419         const bool is_up = step < 0;
420
421         if (step == 0) {
422                 return false;
423         }
424         BLI_assert(BLI_findindex(listbase, link) != -1);
425
426         /* find link to insert before/after */
427         for (int i = 0; i < ABS(step); i++) {
428                 hook = is_up ? hook->prev : hook->next;
429                 if (!hook) {
430                         return false;
431                 }
432         }
433
434         /* reinsert link */
435         BLI_remlink(listbase, vlink);
436         if (is_up) {
437                 BLI_insertlinkbefore(listbase, hook, vlink);
438         }
439         else {
440                 BLI_insertlinkafter(listbase, hook, vlink);
441         }
442         return true;
443 }
444
445
446 /**
447  * Removes and disposes of the entire contents of listbase using direct free(3).
448  */
449 void BLI_freelist(ListBase *listbase)
450 {
451         Link *link, *next;
452         
453         link = listbase->first;
454         while (link) {
455                 next = link->next;
456                 free(link);
457                 link = next;
458         }
459
460         BLI_listbase_clear(listbase);
461 }
462
463 /**
464  * Removes and disposes of the entire contents of \a listbase using guardedalloc.
465  */
466 void BLI_freelistN(ListBase *listbase)
467 {
468         Link *link, *next;
469         
470         link = listbase->first;
471         while (link) {
472                 next = link->next;
473                 MEM_freeN(link);
474                 link = next;
475         }
476
477         BLI_listbase_clear(listbase);
478 }
479
480 /**
481  * Returns the number of elements in \a listbase, up until (and including count_max)
482  *
483  * \note Use to avoid redundant looping.
484  */
485 int BLI_listbase_count_ex(const ListBase *listbase, const int count_max)
486 {
487         Link *link;
488         int count = 0;
489
490         for (link = listbase->first; link && count != count_max; link = link->next) {
491                 count++;
492         }
493
494         return count;
495 }
496
497 /**
498  * Returns the number of elements in \a listbase.
499  */
500 int BLI_listbase_count(const ListBase *listbase)
501 {
502         Link *link;
503         int count = 0;
504
505         for (link = listbase->first; link; link = link->next) {
506                 count++;
507         }
508
509         return count;
510 }
511
512 /**
513  * Returns the nth element of \a listbase, numbering from 0.
514  */
515 void *BLI_findlink(const ListBase *listbase, int number)
516 {
517         Link *link = NULL;
518
519         if (number >= 0) {
520                 link = listbase->first;
521                 while (link != NULL && number != 0) {
522                         number--;
523                         link = link->next;
524                 }
525         }
526
527         return link;
528 }
529
530 /**
531  * Returns the nth-last element of \a listbase, numbering from 0.
532  */
533 void *BLI_rfindlink(const ListBase *listbase, int number)
534 {
535         Link *link = NULL;
536
537         if (number >= 0) {
538                 link = listbase->last;
539                 while (link != NULL && number != 0) {
540                         number--;
541                         link = link->prev;
542                 }
543         }
544
545         return link;
546 }
547
548 /**
549  * Returns the position of \a vlink within \a listbase, numbering from 0, or -1 if not found.
550  */
551 int BLI_findindex(const ListBase *listbase, const void *vlink)
552 {
553         Link *link = NULL;
554         int number = 0;
555
556         if (vlink == NULL) return -1;
557         
558         link = listbase->first;
559         while (link) {
560                 if (link == vlink)
561                         return number;
562                 
563                 number++;
564                 link = link->next;
565         }
566         
567         return -1;
568 }
569
570 /**
571  * Finds the first element of \a listbase which contains the null-terminated
572  * string \a id at the specified offset, returning NULL if not found.
573  */
574 void *BLI_findstring(const ListBase *listbase, const char *id, const int offset)
575 {
576         Link *link = NULL;
577         const char *id_iter;
578
579         for (link = listbase->first; link; link = link->next) {
580                 id_iter = ((const char *)link) + offset;
581
582                 if (id[0] == id_iter[0] && STREQ(id, id_iter)) {
583                         return link;
584                 }
585         }
586
587         return NULL;
588 }
589 /* same as above but find reverse */
590 /**
591  * Finds the last element of \a listbase which contains the
592  * null-terminated string \a id at the specified offset, returning NULL if not found.
593  */
594 void *BLI_rfindstring(const ListBase *listbase, const char *id, const int offset)
595 {
596         Link *link = NULL;
597         const char *id_iter;
598
599         for (link = listbase->last; link; link = link->prev) {
600                 id_iter = ((const char *)link) + offset;
601
602                 if (id[0] == id_iter[0] && STREQ(id, id_iter)) {
603                         return link;
604                 }
605         }
606
607         return NULL;
608 }
609
610 /**
611  * Finds the first element of \a listbase which contains a pointer to the
612  * null-terminated string \a id at the specified offset, returning NULL if not found.
613  */
614 void *BLI_findstring_ptr(const ListBase *listbase, const char *id, const int offset)
615 {
616         Link *link = NULL;
617         const char *id_iter;
618
619         for (link = listbase->first; link; link = link->next) {
620                 /* exact copy of BLI_findstring(), except for this line */
621                 id_iter = *((const char **)(((const char *)link) + offset));
622
623                 if (id[0] == id_iter[0] && STREQ(id, id_iter)) {
624                         return link;
625                 }
626         }
627
628         return NULL;
629 }
630 /* same as above but find reverse */
631 /**
632  * Finds the last element of \a listbase which contains a pointer to the
633  * null-terminated string \a id at the specified offset, returning NULL if not found.
634  */
635 void *BLI_rfindstring_ptr(const ListBase *listbase, const char *id, const int offset)
636 {
637         Link *link = NULL;
638         const char *id_iter;
639
640         for (link = listbase->last; link; link = link->prev) {
641                 /* exact copy of BLI_rfindstring(), except for this line */
642                 id_iter = *((const char **)(((const char *)link) + offset));
643
644                 if (id[0] == id_iter[0] && STREQ(id, id_iter)) {
645                         return link;
646                 }
647         }
648
649         return NULL;
650 }
651
652 /**
653  * Finds the first element of listbase which contains the specified pointer value
654  * at the specified offset, returning NULL if not found.
655  */
656 void *BLI_findptr(const ListBase *listbase, const void *ptr, const int offset)
657 {
658         Link *link = NULL;
659         const void *ptr_iter;
660
661         for (link = listbase->first; link; link = link->next) {
662                 /* exact copy of BLI_findstring(), except for this line */
663                 ptr_iter = *((const void **)(((const char *)link) + offset));
664
665                 if (ptr == ptr_iter) {
666                         return link;
667                 }
668         }
669
670         return NULL;
671 }
672 /* same as above but find reverse */
673 /**
674  * Finds the last element of listbase which contains the specified pointer value
675  * at the specified offset, returning NULL if not found.
676  */
677 void *BLI_rfindptr(const ListBase *listbase, const void *ptr, const int offset)
678 {
679         Link *link = NULL;
680         const void *ptr_iter;
681
682         for (link = listbase->last; link; link = link->prev) {
683                 /* exact copy of BLI_rfindstring(), except for this line */
684                 ptr_iter = *((const void **)(((const char *)link) + offset));
685
686                 if (ptr == ptr_iter) {
687                         return link;
688                 }
689         }
690
691         return NULL;
692 }
693
694 /**
695  * Returns the 1-based index of the first element of listbase which contains the specified
696  * null-terminated string at the specified offset, or -1 if not found.
697  */
698 int BLI_findstringindex(const ListBase *listbase, const char *id, const int offset)
699 {
700         Link *link = NULL;
701         const char *id_iter;
702         int i = 0;
703
704         link = listbase->first;
705         while (link) {
706                 id_iter = ((const char *)link) + offset;
707
708                 if (id[0] == id_iter[0] && STREQ(id, id_iter))
709                         return i;
710                 i++;
711                 link = link->next;
712         }
713
714         return -1;
715 }
716
717 /**
718  * Sets dst to a duplicate of the entire contents of src. dst may be the same as src.
719  */
720 void BLI_duplicatelist(ListBase *dst, const ListBase *src)
721 {
722         struct Link *dst_link, *src_link;
723
724         /* in this order, to ensure it works if dst == src */
725         src_link = src->first;
726         dst->first = dst->last = NULL;
727
728         while (src_link) {
729                 dst_link = MEM_dupallocN(src_link);
730                 BLI_addtail(dst, dst_link);
731
732                 src_link = src_link->next;
733         }
734 }
735
736 void BLI_listbase_reverse(ListBase *lb)
737 {
738         struct Link *curr = lb->first;
739         struct Link *prev = NULL;
740         struct Link *next = NULL;
741         while (curr) {
742                 next = curr->next;
743                 curr->next = prev;
744                 curr->prev = next;
745                 prev = curr;
746                 curr = next;
747         }
748
749         /* swap first/last */
750         curr = lb->first;
751         lb->first = lb->last;
752         lb->last = curr;
753 }
754
755 /**
756  * \param vlink Link to make first.
757  */
758 void BLI_listbase_rotate_first(ListBase *lb, void *vlink)
759 {
760         /* make circular */
761         ((Link *)lb->first)->prev = lb->last;
762         ((Link *)lb->last)->next = lb->first;
763
764         lb->first = vlink;
765         lb->last = ((Link *)vlink)->prev;
766
767         ((Link *)lb->first)->prev = NULL;
768         ((Link *)lb->last)->next = NULL;
769 }
770
771 /**
772  * \param vlink Link to make last.
773  */
774 void BLI_listbase_rotate_last(ListBase *lb, void *vlink)
775 {
776         /* make circular */
777         ((Link *)lb->first)->prev = lb->last;
778         ((Link *)lb->last)->next = lb->first;
779
780         lb->first = ((Link *)vlink)->next;
781         lb->last = vlink;
782
783         ((Link *)lb->first)->prev = NULL;
784         ((Link *)lb->last)->next = NULL;
785 }
786
787 /* create a generic list node containing link to provided data */
788 LinkData *BLI_genericNodeN(void *data)
789 {
790         LinkData *ld;
791         
792         if (data == NULL)
793                 return NULL;
794                 
795         /* create new link, and make it hold the given data */
796         ld = MEM_callocN(sizeof(LinkData), __func__);
797         ld->data = data;
798         
799         return ld;
800