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