ListBase: Add insert-replace function
[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  * Removes the head from \a listbase and returns it.
174  */
175 void *BLI_pophead(ListBase *listbase)
176 {
177         Link *link;
178         if ((link = listbase->first)) {
179                 BLI_remlink(listbase, link);
180         }
181         return link;
182 }
183
184
185 /**
186  * Removes the tail from \a listbase and returns it.
187  */
188 void *BLI_poptail(ListBase *listbase)
189 {
190         Link *link;
191         if ((link = listbase->last)) {
192                 BLI_remlink(listbase, link);
193         }
194         return link;
195 }
196
197 /**
198  * Removes \a vlink from listbase and disposes of it. Assumes it is linked into there!
199  */
200 void BLI_freelinkN(ListBase *listbase, void *vlink)
201 {
202         Link *link = vlink;
203
204         if (link == NULL) return;
205
206         BLI_remlink(listbase, link);
207         MEM_freeN(link);
208 }
209
210 /**
211  * Assigns all #Link.prev pointers from #Link.next
212  */
213 static void listbase_double_from_single(Link *iter, ListBase *listbase)
214 {
215         Link *prev = NULL;
216         listbase->first = iter;
217         do {
218                 iter->prev = prev;
219                 prev = iter;
220         } while ((iter = iter->next));
221         listbase->last = prev;
222 }
223
224 #define SORT_IMPL_LINKTYPE Link
225
226 /* regular call */
227 #define SORT_IMPL_FUNC listbase_sort_fn
228 #include "list_sort_impl.h"
229 #undef SORT_IMPL_FUNC
230
231 /* reentrant call */
232 #define SORT_IMPL_USE_THUNK
233 #define SORT_IMPL_FUNC listbase_sort_fn_r
234 #include "list_sort_impl.h"
235 #undef SORT_IMPL_FUNC
236 #undef SORT_IMPL_USE_THUNK
237
238 #undef SORT_IMPL_LINKTYPE
239
240 /**
241  * Sorts the elements of listbase into the order defined by cmp
242  * (which should return 1 if its first arg should come after its second arg).
243  * This uses insertion sort, so NOT ok for large list.
244  */
245 void BLI_listbase_sort(ListBase *listbase, int (*cmp)(const void *, const void *))
246 {
247         if (listbase->first != listbase->last) {
248                 Link *head = listbase->first;
249                 head = listbase_sort_fn(head, cmp);
250                 listbase_double_from_single(head, listbase);
251         }
252 }
253
254 void BLI_listbase_sort_r(ListBase *listbase, int (*cmp)(void *, const void *, const void *), void *thunk)
255 {
256         if (listbase->first != listbase->last) {
257                 Link *head = listbase->first;
258                 head = listbase_sort_fn_r(head, cmp, thunk);
259                 listbase_double_from_single(head, listbase);
260         }
261 }
262
263 /**
264  * Inserts \a vnewlink immediately following \a vprevlink in \a listbase.
265  * Or, if \a vprevlink is NULL, puts \a vnewlink at the front of the list.
266  */
267 void BLI_insertlinkafter(ListBase *listbase, void *vprevlink, void *vnewlink)
268 {
269         Link *prevlink = vprevlink;
270         Link *newlink = vnewlink;
271
272         /* newlink before nextlink */
273         if (newlink == NULL) return;
274
275         /* empty list */
276         if (listbase->first == NULL) {
277                 listbase->first = newlink;
278                 listbase->last = newlink;
279                 return;
280         }
281         
282         /* insert at head of list */
283         if (prevlink == NULL) {
284                 newlink->prev = NULL;
285                 newlink->next = listbase->first;
286                 newlink->next->prev = newlink;
287                 listbase->first = newlink;
288                 return;
289         }
290
291         /* at end of list */
292         if (listbase->last == prevlink) {
293                 listbase->last = newlink;
294         }
295
296         newlink->next = prevlink->next;
297         newlink->prev = prevlink;
298         prevlink->next = newlink;
299         if (newlink->next) {
300                 newlink->next->prev = newlink;
301         }
302 }
303
304 /**
305  * Inserts \a vnewlink immediately preceding \a vnextlink in listbase.
306  * Or, if \a vnextlink is NULL, puts \a vnewlink at the end of the list.
307  */
308 void BLI_insertlinkbefore(ListBase *listbase, void *vnextlink, void *vnewlink)
309 {
310         Link *nextlink = vnextlink;
311         Link *newlink = vnewlink;
312
313         /* newlink before nextlink */
314         if (newlink == NULL) return;
315
316         /* empty list */
317         if (listbase->first == NULL) {
318                 listbase->first = newlink;
319                 listbase->last = newlink;
320                 return;
321         }
322         
323         /* insert at end of list */
324         if (nextlink == NULL) {
325                 newlink->prev = listbase->last;
326                 newlink->next = NULL;
327                 ((Link *)listbase->last)->next = newlink;
328                 listbase->last = newlink;
329                 return;
330         }
331
332         /* at beginning of list */
333         if (listbase->first == nextlink) {
334                 listbase->first = newlink;
335         }
336
337         newlink->next = nextlink;
338         newlink->prev = nextlink->prev;
339         nextlink->prev = newlink;
340         if (newlink->prev) {
341                 newlink->prev->next = newlink;
342         }
343 }
344
345
346 /**
347  * Insert a link in place of another, without changing it's position in the list.
348  *
349  * Puts `vnewlink` in the position of `vreplacelink`, removing `vreplacelink`.
350  * - `vreplacelink` *must* be in the list.
351  * - `vnewlink` *must not* be in the list.
352  */
353 void BLI_insertlinkreplace(ListBase *listbase, void *vreplacelink, void *vnewlink)
354 {
355         Link *l_old = vreplacelink;
356         Link *l_new = vnewlink;
357
358         /* update adjacent links */
359         if (l_old->next != NULL) {
360                 l_old->next->prev = l_new;
361         }
362         if (l_old->prev != NULL) {
363                 l_old->prev->next = l_new;
364         }
365
366         /* set direct links */
367         l_new->next = l_old->next;
368         l_new->prev = l_old->prev;
369
370          /* update list */
371         if (listbase->first == l_old) {
372                 listbase->first = l_new;
373         }
374         if (listbase->last == l_old) {
375                 listbase->last = l_new;
376         }
377 }
378
379 /**
380  * Reinsert \a vlink relative to its current position but offset by \a step. Doesn't move
381  * item if new position would exceed list (could optionally move to head/tail).
382  *
383  * \param step: Absolute value defines step size, sign defines direction. E.g pass -1
384  *              to move \a vlink before previous, or 1 to move behind next.
385  * \return If position of \a vlink has changed.
386  */
387 bool BLI_listbase_link_move(ListBase *listbase, void *vlink, int step)
388 {
389         Link *link = vlink;
390         Link *hook = link;
391         const bool is_up = step < 0;
392
393         if (step == 0) {
394                 return false;
395         }
396         BLI_assert(BLI_findindex(listbase, link) != -1);
397
398         /* find link to insert before/after */
399         for (int i = 0; i < ABS(step); i++) {
400                 hook = is_up ? hook->prev : hook->next;
401                 if (!hook) {
402                         return false;
403                 }
404         }
405
406         /* reinsert link */
407         BLI_remlink(listbase, vlink);
408         if (is_up) {
409                 BLI_insertlinkbefore(listbase, hook, vlink);
410         }
411         else {
412                 BLI_insertlinkafter(listbase, hook, vlink);
413         }
414         return true;
415 }
416
417
418 /**
419  * Removes and disposes of the entire contents of listbase using direct free(3).
420  */
421 void BLI_freelist(ListBase *listbase)
422 {
423         Link *link, *next;
424         
425         link = listbase->first;
426         while (link) {
427                 next = link->next;
428                 free(link);
429                 link = next;
430         }
431
432         BLI_listbase_clear(listbase);
433 }
434
435 /**
436  * Removes and disposes of the entire contents of \a listbase using guardedalloc.
437  */
438 void BLI_freelistN(ListBase *listbase)
439 {
440         Link *link, *next;
441         
442         link = listbase->first;
443         while (link) {
444                 next = link->next;
445                 MEM_freeN(link);
446                 link = next;
447         }
448
449         BLI_listbase_clear(listbase);
450 }
451
452 /**
453  * Returns the number of elements in \a listbase, up until (and including count_max)
454  *
455  * \note Use to avoid redundant looping.
456  */
457 int BLI_listbase_count_ex(const ListBase *listbase, const int count_max)
458 {
459         Link *link;
460         int count = 0;
461
462         for (link = listbase->first; link && count != count_max; link = link->next) {
463                 count++;
464         }
465
466         return count;
467 }
468
469 /**
470  * Returns the number of elements in \a listbase.
471  */
472 int BLI_listbase_count(const ListBase *listbase)
473 {
474         Link *link;
475         int count = 0;
476
477         for (link = listbase->first; link; link = link->next) {
478                 count++;
479         }
480
481         return count;
482 }
483
484 /**
485  * Returns the nth element of \a listbase, numbering from 0.
486  */
487 void *BLI_findlink(const ListBase *listbase, int number)
488 {
489         Link *link = NULL;
490
491         if (number >= 0) {
492                 link = listbase->first;
493                 while (link != NULL && number != 0) {
494                         number--;
495                         link = link->next;
496                 }
497         }
498
499         return link;
500 }
501
502 /**
503  * Returns the nth-last element of \a listbase, numbering from 0.
504  */
505 void *BLI_rfindlink(const ListBase *listbase, int number)
506 {
507         Link *link = NULL;
508
509         if (number >= 0) {
510                 link = listbase->last;
511                 while (link != NULL && number != 0) {
512                         number--;
513                         link = link->prev;
514                 }
515         }
516
517         return link;
518 }
519
520 /**
521  * Returns the position of \a vlink within \a listbase, numbering from 0, or -1 if not found.
522  */
523 int BLI_findindex(const ListBase *listbase, const void *vlink)
524 {
525         Link *link = NULL;
526         int number = 0;
527
528         if (vlink == NULL) return -1;
529         
530         link = listbase->first;
531         while (link) {
532                 if (link == vlink)
533                         return number;
534                 
535                 number++;
536                 link = link->next;
537         }
538         
539         return -1;
540 }
541
542 /**
543  * Finds the first element of \a listbase which contains the null-terminated
544  * string \a id at the specified offset, returning NULL if not found.
545  */
546 void *BLI_findstring(const ListBase *listbase, const char *id, const int offset)
547 {
548         Link *link = NULL;
549         const char *id_iter;
550
551         for (link = listbase->first; link; link = link->next) {
552                 id_iter = ((const char *)link) + offset;
553
554                 if (id[0] == id_iter[0] && STREQ(id, id_iter)) {
555                         return link;
556                 }
557         }
558
559         return NULL;
560 }
561 /* same as above but find reverse */
562 /**
563  * Finds the last element of \a listbase which contains the
564  * null-terminated string \a id at the specified offset, returning NULL if not found.
565  */
566 void *BLI_rfindstring(const ListBase *listbase, const char *id, const int offset)
567 {
568         Link *link = NULL;
569         const char *id_iter;
570
571         for (link = listbase->last; link; link = link->prev) {
572                 id_iter = ((const char *)link) + offset;
573
574                 if (id[0] == id_iter[0] && STREQ(id, id_iter)) {
575                         return link;
576                 }
577         }
578
579         return NULL;
580 }
581
582 /**
583  * Finds the first element of \a listbase which contains a pointer to the
584  * null-terminated string \a id at the specified offset, returning NULL if not found.
585  */
586 void *BLI_findstring_ptr(const ListBase *listbase, const char *id, const int offset)
587 {
588         Link *link = NULL;
589         const char *id_iter;
590
591         for (link = listbase->first; link; link = link->next) {
592                 /* exact copy of BLI_findstring(), except for this line */
593                 id_iter = *((const char **)(((const char *)link) + offset));
594
595                 if (id[0] == id_iter[0] && STREQ(id, id_iter)) {
596                         return link;
597                 }
598         }
599
600         return NULL;
601 }
602 /* same as above but find reverse */
603 /**
604  * Finds the last element of \a listbase which contains a pointer to the
605  * null-terminated string \a id at the specified offset, returning NULL if not found.
606  */
607 void *BLI_rfindstring_ptr(const ListBase *listbase, const char *id, const int offset)
608 {
609         Link *link = NULL;
610         const char *id_iter;
611
612         for (link = listbase->last; link; link = link->prev) {
613                 /* exact copy of BLI_rfindstring(), except for this line */
614                 id_iter = *((const char **)(((const char *)link) + offset));
615
616                 if (id[0] == id_iter[0] && STREQ(id, id_iter)) {
617                         return link;
618                 }
619         }
620
621         return NULL;
622 }
623
624 /**
625  * Finds the first element of listbase which contains the specified pointer value
626  * at the specified offset, returning NULL if not found.
627  */
628 void *BLI_findptr(const ListBase *listbase, const void *ptr, const int offset)
629 {
630         Link *link = NULL;
631         const void *ptr_iter;
632
633         for (link = listbase->first; link; link = link->next) {
634                 /* exact copy of BLI_findstring(), except for this line */
635                 ptr_iter = *((const void **)(((const char *)link) + offset));
636
637                 if (ptr == ptr_iter) {
638                         return link;
639                 }
640         }
641
642         return NULL;
643 }
644 /* same as above but find reverse */
645 /**
646  * Finds the last element of listbase which contains the specified pointer value
647  * at the specified offset, returning NULL if not found.
648  */
649 void *BLI_rfindptr(const ListBase *listbase, const void *ptr, const int offset)
650 {
651         Link *link = NULL;
652         const void *ptr_iter;
653
654         for (link = listbase->last; link; link = link->prev) {
655                 /* exact copy of BLI_rfindstring(), except for this line */
656                 ptr_iter = *((const void **)(((const char *)link) + offset));
657
658                 if (ptr == ptr_iter) {
659                         return link;
660                 }
661         }
662
663         return NULL;
664 }
665
666 /**
667  * Returns the 1-based index of the first element of listbase which contains the specified
668  * null-terminated string at the specified offset, or -1 if not found.
669  */
670 int BLI_findstringindex(const ListBase *listbase, const char *id, const int offset)
671 {
672         Link *link = NULL;
673         const char *id_iter;
674         int i = 0;
675
676         link = listbase->first;
677         while (link) {
678                 id_iter = ((const char *)link) + offset;
679
680                 if (id[0] == id_iter[0] && STREQ(id, id_iter))
681                         return i;
682                 i++;
683                 link = link->next;
684         }
685
686         return -1;
687 }
688
689 /**
690  * Sets dst to a duplicate of the entire contents of src. dst may be the same as src.
691  */
692 void BLI_duplicatelist(ListBase *dst, const ListBase *src)
693 {
694         struct Link *dst_link, *src_link;
695
696         /* in this order, to ensure it works if dst == src */
697         src_link = src->first;
698         dst->first = dst->last = NULL;
699
700         while (src_link) {
701                 dst_link = MEM_dupallocN(src_link);
702                 BLI_addtail(dst, dst_link);
703
704                 src_link = src_link->next;
705         }
706 }
707
708 void BLI_listbase_reverse(ListBase *lb)
709 {
710         struct Link *curr = lb->first;
711         struct Link *prev = NULL;
712         struct Link *next = NULL;
713         while (curr) {
714                 next = curr->next;
715                 curr->next = prev;
716                 curr->prev = next;
717                 prev = curr;
718                 curr = next;
719         }
720
721         /* swap first/last */
722         curr = lb->first;
723         lb->first = lb->last;
724         lb->last = curr;
725 }
726
727 /**
728  * \param vlink Link to make first.
729  */
730 void BLI_listbase_rotate_first(ListBase *lb, void *vlink)
731 {
732         /* make circular */
733         ((Link *)lb->first)->prev = lb->last;
734         ((Link *)lb->last)->next = lb->first;
735
736         lb->first = vlink;
737         lb->last = ((Link *)vlink)->prev;
738
739         ((Link *)lb->first)->prev = NULL;
740         ((Link *)lb->last)->next = NULL;
741 }
742
743 /**
744  * \param vlink Link to make last.
745  */
746 void BLI_listbase_rotate_last(ListBase *lb, void *vlink)
747 {
748         /* make circular */
749         ((Link *)lb->first)->prev = lb->last;
750         ((Link *)lb->last)->next = lb->first;
751
752         lb->first = ((Link *)vlink)->next;
753         lb->last = vlink;
754
755         ((Link *)lb->first)->prev = NULL;
756         ((Link *)lb->last)->next = NULL;
757 }
758
759 /* create a generic list node containing link to provided data */
760 LinkData *BLI_genericNodeN(void *data)
761 {
762         LinkData *ld;
763         
764         if (data == NULL)
765                 return NULL;
766                 
767         /* create new link, and make it hold the given data */
768         ld = MEM_callocN(sizeof(LinkData), __func__);
769         ld->data = data;
770         
771         return ld;
772