src/libgame/list.c

   1 // ============================================================================
   2 // list.c
   3 // ============================================================================
   4
   5 /* GLIB - Library of useful routines for C programming
   6  * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
   7  *
   8  * SPDX-License-Identifier: LGPL-2.1-or-later
   9  *
  10  * This library is free software; you can redistribute it and/or
  11  * modify it under the terms of the GNU Lesser General Public
  12  * License as published by the Free Software Foundation; either
  13  * version 2.1 of the License, or (at your option) any later version.
  14  *
  15  * This library is distributed in the hope that it will be useful,
  16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18  * Lesser General Public License for more details.
  19  *
  20  * You should have received a copy of the GNU Lesser General Public
  21  * License along with this library; if not, see <http://www.gnu.org/licenses/>.
  22  */
  23
  24 /*
  25  * Modified by the GLib Team and others 1997-2000.  See the AUTHORS
  26  * file for a list of people on the GLib Team.  See the ChangeLog
  27  * files for a list of changes.  These files are distributed with
  28  * GLib at ftp://ftp.gtk.org/pub/gtk/.
  29  */
  30
  31 #include <stdlib.h>
  32 #include <stddef.h>
  33
  34 #include "list.h"
  35
  36
  37 /**
  38  * List:
  39  * @data: holds the element's data, which can be a pointer to any kind
  40  *        of data, or any integer value using the
  41  *        [Type Conversion Macros][glib-Type-Conversion-Macros]
  42  * @next: contains the link to the next element in the list
  43  * @prev: contains the link to the previous element in the list
  44  *
  45  * The #List struct is used for each element in a doubly-linked list.
  46  **/
  47
  48 /**
  49  * list_previous:
  50  * @list: an element in a #List
  51  *
  52  * A convenience macro to get the previous element in a #List.
  53  * Note that it is considered perfectly acceptable to access
  54  * @list->prev directly.
  55  *
  56  * Returns: the previous element, or %NULL if there are no previous
  57  *          elements
  58  **/
  59
  60 /**
  61  * list_next:
  62  * @list: an element in a #List
  63  *
  64  * A convenience macro to get the next element in a #List.
  65  * Note that it is considered perfectly acceptable to access
  66  * @list->next directly.
  67  *
  68  * Returns: the next element, or %NULL if there are no more elements
  69  **/
  70
  71 /**
  72  * list_alloc:
  73  *
  74  * Allocates space for one #List element. It is called by
  75  * list_append(), list_prepend(), list_insert() and
  76  * list_insert_sorted() and so is rarely used on its own.
  77  *
  78  * Returns: a pointer to the newly-allocated #List element
  79  **/
  80 List *
  81 list_alloc (void)
  82 {
  83   return checked_calloc(sizeof(List));
  84 }
  85
  86 /**
  87  * list_free:
  88  * @list: the first link of a #List
  89  *
  90  * Frees all of the memory used by a #List.
  91  * The freed elements are returned to the slice allocator.
  92  *
  93  * If list elements contain dynamically-allocated memory, you should
  94  * either use list_free_full() or free them manually first.
  95  *
  96  * It can be combined with steal_pointer() to ensure the list head pointer
  97  * is not left dangling:
  98  * |[<!-- language="C" -->
  99  * List *list_of_borrowed_things = …;  /<!-- -->* (transfer container) *<!-- -->/
 100  * list_free (steal_pointer (&list_of_borrowed_things));
 101  * ]|
 102  */
 103 void
 104 list_free (List *list)
 105 {
 106   void *slice = list;
 107   size_t next_offset = offsetof(List, next);
 108
 109   while (slice)
 110   {
 111     void *current = slice;
 112     slice = *(void**) (current + next_offset);
 113     checked_free(current);
 114   }
 115 }
 116
 117 /**
 118  * list_free_1:
 119  * @list: a #List element
 120  *
 121  * Frees one #List element, but does not update links from the next and
 122  * previous elements in the list, so you should not call this function on an
 123  * element that is currently part of a list.
 124  *
 125  * It is usually used after list_remove_link().
 126  */
 127 /**
 128  * list_free1:
 129  *
 130  * Another name for list_free_1().
 131  **/
 132 void
 133 list_free_1 (List *list)
 134 {
 135   checked_free(list);
 136 }
 137
 138 /**
 139  * list_append:
 140  * @list: a pointer to a #List
 141  * @data: the data for the new element
 142  *
 143  * Adds a new element on to the end of the list.
 144  *
 145  * Note that the return value is the new start of the list,
 146  * if @list was empty; make sure you store the new value.
 147  *
 148  * list_append() has to traverse the entire list to find the end,
 149  * which is inefficient when adding multiple elements. A common idiom
 150  * to avoid the inefficiency is to use list_prepend() and reverse
 151  * the list with list_reverse() when all elements have been added.
 152  *
 153  * |[<!-- language="C" -->
 154  * // Notice that these are initialized to the empty list.
 155  * List *strinlist = NULL, *number_list = NULL;
 156  *
 157  * // This is a list of strings.
 158  * strinlist = list_append (strinlist, "first");
 159  * strinlist = list_append (strinlist, "second");
 160  *
 161  * // This is a list of integers.
 162  * number_list = list_append (number_list, INT_TO_PTR (27));
 163  * number_list = list_append (number_list, INT_TO_PTR (14));
 164  * ]|
 165  *
 166  * Returns: either @list or the new start of the #List if @list was %NULL
 167  */
 168 List *
 169 list_append (List *list, void *data)
 170 {
 171   List *new_list;
 172   List *last;
 173
 174   new_list = checked_malloc(sizeof(List));
 175   new_list->data = data;
 176   new_list->next = NULL;
 177
 178   if (list)
 179   {
 180     last = list_last(list);
 181     last->next = new_list;
 182     new_list->prev = last;
 183
 184     return list;
 185   }
 186   else
 187   {
 188     new_list->prev = NULL;
 189
 190     return new_list;
 191   }
 192 }
 193
 194 /**
 195  * list_prepend:
 196  * @list: a pointer to a #List, this must point to the top of the list
 197  * @data: the data for the new element
 198  *
 199  * Prepends a new element on to the start of the list.
 200  *
 201  * Note that the return value is the new start of the list,
 202  * which will have changed, so make sure you store the new value.
 203  *
 204  * |[<!-- language="C" -->
 205  * // Notice that it is initialized to the empty list.
 206  * List *list = NULL;
 207  *
 208  * list = list_prepend (list, "last");
 209  * list = list_prepend (list, "first");
 210  * ]|
 211  *
 212  * Do not use this function to prepend a new element to a different
 213  * element than the start of the list. Use list_insert_before() instead.
 214  *
 215  * Returns: a pointer to the newly prepended element, which is the new
 216  *     start of the #List
 217  */
 218 List *
 219 list_prepend (List *list, void *data)
 220 {
 221   List *new_list;
 222
 223   new_list = checked_malloc(sizeof(List));
 224   new_list->data = data;
 225   new_list->next = list;
 226
 227   if (list)
 228   {
 229     new_list->prev = list->prev;
 230     if (list->prev)
 231       list->prev->next = new_list;
 232     list->prev = new_list;
 233   }
 234   else
 235   {
 236     new_list->prev = NULL;
 237   }
 238
 239   return new_list;
 240 }
 241
 242 /**
 243  * list_insert:
 244  * @list: a pointer to a #List, this must point to the top of the list
 245  * @data: the data for the new element
 246  * @position: the position to insert the element. If this is
 247  *     negative, or is larger than the number of elements in the
 248  *     list, the new element is added on to the end of the list.
 249  *
 250  * Inserts a new element into the list at the given position.
 251  *
 252  * Returns: the (possibly changed) start of the #List
 253  */
 254 List *
 255 list_insert (List *list, void *data, int position)
 256 {
 257   List *new_list;
 258   List *tmp_list;
 259
 260   if (position < 0)
 261     return list_append(list, data);
 262   else if (position == 0)
 263     return list_prepend(list, data);
 264
 265   tmp_list = list_nth(list, position);
 266   if (!tmp_list)
 267     return list_append(list, data);
 268
 269   new_list = checked_malloc(sizeof(List));
 270   new_list->data = data;
 271   new_list->prev = tmp_list->prev;
 272   tmp_list->prev->next = new_list;
 273   new_list->next = tmp_list;
 274   tmp_list->prev = new_list;
 275
 276   return list;
 277 }
 278
 279 static inline List *
 280 _list_remove_link (List *list, List *link)
 281 {
 282   if (link == NULL)
 283     return list;
 284
 285   if (link->prev)
 286   {
 287     if (link->prev->next == link)
 288       link->prev->next = link->next;
 289     else
 290       Warn("corrupted double-linked list detected");
 291   }
 292
 293   if (link->next)
 294   {
 295     if (link->next->prev == link)
 296       link->next->prev = link->prev;
 297     else
 298       Warn("corrupted double-linked list detected");
 299   }
 300
 301   if (link == list)
 302     list = list->next;
 303
 304   link->next = NULL;
 305   link->prev = NULL;
 306
 307   return list;
 308 }
 309
 310 /**
 311  * list_remove:
 312  * @list: a #List, this must point to the top of the list
 313  * @data: the data of the element to remove
 314  *
 315  * Removes an element from a #List.
 316  * If two elements contain the same data, only the first is removed.
 317  * If none of the elements contain the data, the #List is unchanged.
 318  *
 319  * Returns: the (possibly changed) start of the #List
 320  */
 321 List *
 322 list_remove (List *list, const void *data)
 323 {
 324   List *tmp;
 325
 326   tmp = list;
 327   while (tmp)
 328   {
 329     if (tmp->data != data)
 330     {
 331       tmp = tmp->next;
 332     }
 333     else
 334     {
 335       list = _list_remove_link (list, tmp);
 336       free (tmp);
 337
 338       break;
 339     }
 340   }
 341
 342   return list;
 343 }
 344
 345 /**
 346  * list_remove_all:
 347  * @list: a #List, this must point to the top of the list
 348  * @data: data to remove
 349  *
 350  * Removes all list nodes with data equal to @data.
 351  * Returns the new head of the list. Contrast with
 352  * list_remove() which removes only the first node
 353  * matching the given data.
 354  *
 355  * Returns: the (possibly changed) start of the #List
 356  */
 357 List *
 358 list_remove_all (List *list, const void *data)
 359 {
 360   List *tmp = list;
 361
 362   while (tmp)
 363   {
 364     if (tmp->data != data)
 365     {
 366       tmp = tmp->next;
 367     }
 368     else
 369     {
 370       List *next = tmp->next;
 371
 372       if (tmp->prev)
 373         tmp->prev->next = next;
 374       else
 375         list = next;
 376
 377       if (next)
 378         next->prev = tmp->prev;
 379
 380       free (tmp);
 381       tmp = next;
 382     }
 383   }
 384
 385   return list;
 386 }
 387
 388 /**
 389  * list_remove_link:
 390  * @list: a #List, this must point to the top of the list
 391  * @llink: an element in the #List
 392  *
 393  * Removes an element from a #List, without freeing the element.
 394  * The removed element's prev and next links are set to %NULL, so
 395  * that it becomes a self-contained list with one element.
 396  *
 397  * This function is for example used to move an element in the list
 398  * (see the example for list_concat()) or to remove an element in
 399  * the list before freeing its data:
 400  * |[<!-- language="C" -->
 401  * list = list_remove_link (list, llink);
 402  * free_some_data_that_may_access_the_list_again (llink->data);
 403  * list_free (llink);
 404  * ]|
 405  *
 406  * Returns: the (possibly changed) start of the #List
 407  */
 408 List *
 409 list_remove_link (List *list, List *llink)
 410 {
 411   return _list_remove_link(list, llink);
 412 }
 413
 414 /**
 415  * list_delete_link:
 416  * @list: a #List, this must point to the top of the list
 417  * @link_: node to delete from @list
 418  *
 419  * Removes the node link_ from the list and frees it.
 420  * Compare this to list_remove_link() which removes the node
 421  * without freeing it.
 422  *
 423  * Returns: the (possibly changed) start of the #List
 424  */
 425 List *
 426 list_delete_link (List *list, List *link_)
 427 {
 428   list = _list_remove_link(list, link_);
 429   checked_free(link_);
 430
 431   return list;
 432 }
 433
 434 /**
 435  * list_copy:
 436  * @list: a #List, this must point to the top of the list
 437  *
 438  * Copies a #List.
 439  *
 440  * Note that this is a "shallow" copy. If the list elements
 441  * consist of pointers to data, the pointers are copied but
 442  * the actual data is not. See list_copy_deep() if you need
 443  * to copy the data as well.
 444  *
 445  * Returns: the start of the new list that holds the same data as @list
 446  */
 447 List *
 448 list_copy (List *list)
 449 {
 450   return list_copy_deep(list, NULL, NULL);
 451 }
 452
 453 /**
 454  * g_list_copy_deep:
 455  * @list: a #List, this must point to the top of the list
 456  * @func: (scope call): a copy function used to copy every element in the list
 457  * @user_data: user data passed to the copy function @func, or %NULL
 458  *
 459  * Makes a full (deep) copy of a #List.
 460  *
 461  * In contrast with g_list_copy(), this function uses @func to make
 462  * a copy of each list element, in addition to copying the list
 463  * container itself.
 464  *
 465  * @func, as a #GCopyFunc, takes two arguments, the data to be copied
 466  * and a @user_data pointer. On common processor architectures, it's safe to
 467  * pass %NULL as @user_data if the copy function takes only one argument. You
 468  * may get compiler warnings from this though if compiling with GCC’s
 469  * `-Wcast-function-type` warning.
 470  *
 471  * For instance, if @list holds a list of GObjects, you can do:
 472  * |[<!-- language="C" -->
 473  * another_list = g_list_copy_deep (list, (GCopyFunc) g_object_ref, NULL);
 474  * ]|
 475  *
 476  * And, to entirely free the new list, you could do:
 477  * |[<!-- language="C" -->
 478  * g_list_free_full (another_list, g_object_unref);
 479  * ]|
 480  *
 481  * Returns: the start of the new list that holds a full copy of @list,
 482  *     use g_list_free_full() to free it
 483  *
 484  * Since: 2.34
 485  */
 486 List *
 487 list_copy_deep (List *list, list_copy_fn func, void *user_data)
 488 {
 489   List *new_list = NULL;
 490
 491   if (list)
 492   {
 493     List *last;
 494
 495     new_list = checked_malloc(sizeof(List));
 496
 497     if (func)
 498       new_list->data = func (list->data, user_data);
 499     else
 500       new_list->data = list->data;
 501
 502     new_list->prev = NULL;
 503     last = new_list;
 504     list = list->next;
 505
 506     while (list)
 507     {
 508       last->next = checked_malloc(sizeof(List));
 509       last->next->prev = last;
 510       last = last->next;
 511
 512       if (func)
 513         last->data = func (list->data, user_data);
 514       else
 515         last->data = list->data;
 516
 517       list = list->next;
 518     }
 519
 520     last->next = NULL;
 521   }
 522
 523   return new_list;
 524 }
 525
 526 /**
 527  * list_reverse:
 528  * @list: a #List, this must point to the top of the list
 529  *
 530  * Reverses a #List.
 531  * It simply switches the next and prev pointers of each element.
 532  *
 533  * Returns: the start of the reversed #List
 534  */
 535 List *
 536 list_reverse (List *list)
 537 {
 538   List *last;
 539
 540   last = NULL;
 541
 542   while (list)
 543   {
 544     last = list;
 545     list = last->next;
 546     last->next = last->prev;
 547     last->prev = list;
 548   }
 549
 550   return last;
 551 }
 552
 553 /**
 554  * list_nth:
 555  * @list: a #List, this must point to the top of the list
 556  * @n: the position of the element, counting from 0
 557  *
 558  * Gets the element at the given position in a #List.
 559  *
 560  * This iterates over the list until it reaches the @n-th position. If you
 561  * intend to iterate over every element, it is better to use a for-loop as
 562  * described in the #List introduction.
 563  *
 564  * Returns: the element, or %NULL if the position is off
 565  *     the end of the #List
 566  */
 567 List *
 568 list_nth (List *list, unsigned int  n)
 569 {
 570   while ((n-- > 0) && list)
 571     list = list->next;
 572
 573   return list;
 574 }
 575
 576 /**
 577  * list_nth_prev:
 578  * @list: a #List
 579  * @n: the position of the element, counting from 0
 580  *
 581  * Gets the element @n places before @list.
 582  *
 583  * Returns: the element, or %NULL if the position is
 584  *     off the end of the #List
 585  */
 586 List *
 587 list_nth_prev (List *list, unsigned int n)
 588 {
 589   while ((n-- > 0) && list)
 590     list = list->prev;
 591
 592   return list;
 593 }
 594
 595 /**
 596  * list_nth_data:
 597  * @list: a #List, this must point to the top of the list
 598  * @n: the position of the element
 599  *
 600  * Gets the data of the element at the given position.
 601  *
 602  * This iterates over the list until it reaches the @n-th position. If you
 603  * intend to iterate over every element, it is better to use a for-loop as
 604  * described in the #List introduction.
 605  *
 606  * Returns: the element's data, or %NULL if the position
 607  *     is off the end of the #List
 608  */
 609 void *
 610 list_nth_data (List *list, unsigned int n)
 611 {
 612   while ((n-- > 0) && list)
 613     list = list->next;
 614
 615   return list ? list->data : NULL;
 616 }
 617
 618 /**
 619  * list_position:
 620  * @list: a #List, this must point to the top of the list
 621  * @llink: an element in the #List
 622  *
 623  * Gets the position of the given element
 624  * in the #List (starting from 0).
 625  *
 626  * Returns: the position of the element in the #List,
 627  *     or -1 if the element is not found
 628  */
 629 int
 630 list_position (List *list, List *llink)
 631 {
 632   int i;
 633
 634   i = 0;
 635   while (list)
 636   {
 637     if (list == llink)
 638       return i;
 639
 640     i++;
 641     list = list->next;
 642   }
 643
 644   return -1;
 645 }
 646
 647 /**
 648  * list_index:
 649  * @list: a #List, this must point to the top of the list
 650  * @data: the data to find
 651  *
 652  * Gets the position of the element containing
 653  * the given data (starting from 0).
 654  *
 655  * Returns: the index of the element containing the data,
 656  *     or -1 if the data is not found
 657  */
 658 int
 659 list_index (List *list, const void *data)
 660 {
 661   int i;
 662
 663   i = 0;
 664   while (list)
 665   {
 666     if (list->data == data)
 667       return i;
 668
 669     i++;
 670     list = list->next;
 671   }
 672
 673   return -1;
 674 }
 675
 676 /**
 677  * list_last:
 678  * @list: any #List element
 679  *
 680  * Gets the last element in a #List.
 681  *
 682  * Returns: the last element in the #List,
 683  *     or %NULL if the #List has no elements
 684  */
 685 List *
 686 list_last (List *list)
 687 {
 688   if (list)
 689   {
 690     while (list->next)
 691       list = list->next;
 692   }
 693
 694   return list;
 695 }
 696
 697 /**
 698  * list_first:
 699  * @list: any #List element
 700  *
 701  * Gets the first element in a #List.
 702  *
 703  * Returns: the first element in the #List,
 704  *     or %NULL if the #List has no elements
 705  */
 706 List *
 707 list_first (List *list)
 708 {
 709   if (list)
 710   {
 711     while (list->prev)
 712       list = list->prev;
 713   }
 714
 715   return list;
 716 }
 717
 718 /**
 719  * list_length:
 720  * @list: a #List, this must point to the top of the list
 721  *
 722  * Gets the number of elements in a #List.
 723  *
 724  * This function iterates over the whole list to count its elements.
 725  * Use a #GQueue instead of a List if you regularly need the number
 726  * of items. To check whether the list is non-empty, it is faster to check
 727  * @list against %NULL.
 728  *
 729  * Returns: the number of elements in the #List
 730  */
 731 unsigned int
 732 list_length (List *list)
 733 {
 734   unsigned int length;
 735
 736   length = 0;
 737   while (list)
 738   {
 739     length++;
 740     list = list->next;
 741   }
 742
 743   return length;
 744 }
 745
 746 /**
 747  * list_foreach:
 748  * @list: a #List, this must point to the top of the list
 749  * @func: (scope call): the function to call with each element's data
 750  * @user_data: user data to pass to the function
 751  *
 752  * Calls a function for each element of a #List.
 753  *
 754  * It is safe for @func to remove the element from @list, but it must
 755  * not modify any part of the list after that element.
 756  */
 757 /**
 758  * list_fn:
 759  * @data: the element's data
 760  * @user_data: user data passed to list_foreach() or slist_foreach()
 761  *
 762  * Specifies the type of functions passed to list_foreach() and
 763  * slist_foreach().
 764  */
 765 void
 766 list_foreach (List *list, list_fn func, void *user_data)
 767 {
 768   while (list)
 769   {
 770     List *next = list->next;
 771
 772     (*func) (list->data, user_data);
 773     list = next;
 774   }
 775 }