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