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 }