utility/genlist.c

   1 /**********************************************************************
   2  Freeciv - Copyright (C) 1996 - A Kjeldberg, L Gregersen, P Unold
   3    This program is free software; you can redistribute it and/or modify
   4    it under the terms of the GNU General Public License as published by
   5    the Free Software Foundation; either version 2, or (at your option)
   6    any later version.
   7
   8    This program is distributed in the hope that it will be useful,
   9    but WITHOUT ANY WARRANTY; without even the implied warranty of
  10    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11    GNU General Public License for more details.
  12 ***********************************************************************/
  13
  14 #ifdef HAVE_CONFIG_H
  15 #include <fc_config.h>
  16 #endif
  17
  18 #include <stdlib.h>
  19
  20 /* utility */
  21 #include "fcthread.h"
  22 #include "log.h"
  23 #include "mem.h"
  24 #include "shared.h"  /* array_shuffle */
  25
  26 #include "genlist.h"
  27
  28 /****************************************************************************
  29   Create a new empty genlist.
  30 ****************************************************************************/
  31 struct genlist *genlist_new(void)
  32 {
  33   return genlist_new_full(NULL);
  34 }
  35
  36 /****************************************************************************
  37   Create a new empty genlist with a free data function.
  38 ****************************************************************************/
  39 struct genlist *genlist_new_full(genlist_free_fn_t free_data_func)
  40 {
  41   struct genlist *pgenlist = fc_calloc(1, sizeof(*pgenlist));
  42
  43 #ifdef ZERO_VARIABLES_FOR_SEARCHING
  44   pgenlist->nelements = 0;
  45   pgenlist->head_link = NULL;
  46   pgenlist->tail_link = NULL;
  47 #endif /* ZERO_VARIABLES_FOR_SEARCHING */
  48   fc_init_mutex(&pgenlist->mutex);
  49   pgenlist->free_data_func = free_data_func;
  50
  51   return pgenlist;
  52 }
  53
  54 /****************************************************************************
  55   Destroys the genlist.
  56 ****************************************************************************/
  57 void genlist_destroy(struct genlist *pgenlist)
  58 {
  59   if (pgenlist == NULL) {
  60     return;
  61   }
  62
  63   genlist_clear(pgenlist);
  64   fc_destroy_mutex(&pgenlist->mutex);
  65   free(pgenlist);
  66 }
  67
  68 /****************************************************************************
  69   Create a new link.
  70 ****************************************************************************/
  71 static void genlist_link_new(struct genlist *pgenlist, void *dataptr,
  72                              struct genlist_link *prev,
  73                              struct genlist_link *next)
  74 {
  75   struct genlist_link *plink = fc_malloc(sizeof(*plink));
  76
  77   plink->dataptr = dataptr;
  78   plink->prev = prev;
  79   if (NULL != prev) {
  80     prev->next = plink;
  81   } else {
  82     pgenlist->head_link = plink;
  83   }
  84   plink->next = next;
  85   if (NULL != next) {
  86     next->prev = plink;
  87   } else {
  88     pgenlist->tail_link = plink;
  89   }
  90   pgenlist->nelements++;
  91 }
  92
  93 /****************************************************************************
  94   Free a link.
  95 ****************************************************************************/
  96 static void genlist_link_destroy(struct genlist *pgenlist,
  97                                  struct genlist_link *plink)
  98 {
  99   if (pgenlist->head_link == plink) {
 100     pgenlist->head_link = plink->next;
 101   } else {
 102     plink->prev->next = plink->next;
 103   }
 104
 105   if (pgenlist->tail_link == plink) {
 106     pgenlist->tail_link = plink->prev;
 107   } else {
 108     plink->next->prev = plink->prev;
 109   }
 110
 111   pgenlist->nelements--;
 112
 113   /* NB: detach the link before calling the free function for avoiding
 114    * re-entrant code. */
 115   if (NULL != pgenlist->free_data_func) {
 116     pgenlist->free_data_func(plink->dataptr);
 117   }
 118   free(plink);
 119 }
 120
 121 /****************************************************************************
 122   Returns a pointer to the genlist link structure at the specified
 123   position.  Recall 'pos' -1 refers to the last position.
 124   For pos out of range returns NULL.
 125   Traverses list either forwards or backwards for best efficiency.
 126 ****************************************************************************/
 127 static struct genlist_link *
 128 genlist_link_at_pos(const struct genlist *pgenlist, int pos)
 129 {
 130   struct genlist_link *plink;
 131
 132   if (pos == 0) {
 133     return pgenlist->head_link;
 134   } else if (pos == -1) {
 135     return pgenlist->tail_link;
 136   } else if (pos < -1 || pos >= pgenlist->nelements) {
 137     return NULL;
 138   }
 139
 140   if (pos < pgenlist->nelements / 2) {  /* fastest to do forward search */
 141     for (plink = pgenlist->head_link; pos != 0; pos--) {
 142       plink = plink->next;
 143     }
 144   } else {                              /* fastest to do backward search */
 145     for (plink = pgenlist->tail_link, pos = pgenlist->nelements-pos - 1;
 146          pos != 0; pos--) {
 147       plink = plink->prev;
 148     }
 149   }
 150
 151   return plink;
 152 }
 153
 154 /****************************************************************************
 155   Returns a new genlist that's a copy of the existing one.
 156 ****************************************************************************/
 157 struct genlist *genlist_copy(const struct genlist *pgenlist)
 158 {
 159   return genlist_copy_full(pgenlist, NULL, pgenlist->free_data_func);
 160 }
 161
 162 /****************************************************************************
 163   Returns a new genlist that's a copy of the existing one.
 164 ****************************************************************************/
 165 struct genlist *genlist_copy_full(const struct genlist *pgenlist,
 166                                   genlist_copy_fn_t copy_data_func,
 167                                   genlist_free_fn_t free_data_func)
 168 {
 169   struct genlist *pcopy = genlist_new_full(free_data_func);
 170
 171   if (pgenlist) {
 172     struct genlist_link *plink;
 173
 174     if (NULL != copy_data_func) {
 175       for (plink = pgenlist->head_link; plink; plink = plink->next) {
 176         genlist_link_new(pcopy, copy_data_func(plink->dataptr),
 177                          pcopy->tail_link, NULL);
 178       }
 179     } else {
 180       for (plink = pgenlist->head_link; plink; plink = plink->next) {
 181         genlist_link_new(pcopy, plink->dataptr, pcopy->tail_link, NULL);
 182       }
 183     }
 184   }
 185
 186   return pcopy;
 187 }
 188
 189 /****************************************************************************
 190   Returns the number of elements stored in the genlist.
 191 ****************************************************************************/
 192 int genlist_size(const struct genlist *pgenlist)
 193 {
 194   fc_assert_ret_val(NULL != pgenlist, 0);
 195   return pgenlist->nelements;
 196 }
 197
 198 /****************************************************************************
 199   Returns the link in the genlist at the position given by 'idx'. For idx
 200   out of range (including an empty list), returns NULL.
 201   Recall 'idx' can be -1 meaning the last element.
 202 ****************************************************************************/
 203 struct genlist_link *genlist_link_get(const struct genlist *pgenlist, int idx)
 204 {
 205   fc_assert_ret_val(NULL != pgenlist, NULL);
 206
 207   return genlist_link_at_pos(pgenlist, idx);
 208 }
 209
 210 /****************************************************************************
 211   Returns the tail link of the genlist.
 212 ****************************************************************************/
 213 struct genlist_link *genlist_tail(const struct genlist *pgenlist)
 214 {
 215   return (NULL != pgenlist ? pgenlist->tail_link : NULL);
 216 }
 217
 218 /****************************************************************************
 219   Returns the user-data pointer stored in the genlist at the position
 220   given by 'idx'.  For idx out of range (including an empty list),
 221   returns NULL.
 222   Recall 'idx' can be -1 meaning the last element.
 223 ****************************************************************************/
 224 void *genlist_get(const struct genlist *pgenlist, int idx)
 225 {
 226   return genlist_link_data(genlist_link_get(pgenlist, idx));
 227 }
 228
 229 /****************************************************************************
 230   Returns the user-data pointer stored in the first element of the genlist.
 231 ****************************************************************************/
 232 void *genlist_front(const struct genlist *pgenlist)
 233 {
 234   return genlist_link_data(genlist_head(pgenlist));
 235 }
 236
 237 /****************************************************************************
 238   Returns the user-data pointer stored in the last element of the genlist.
 239 ****************************************************************************/
 240 void *genlist_back(const struct genlist *pgenlist)
 241 {
 242   return genlist_link_data(genlist_tail(pgenlist));
 243 }
 244
 245 /****************************************************************************
 246   Frees all the internal data used by the genlist (but doesn't touch
 247   the user-data).  At the end the state of the genlist will be the
 248   same as when genlist_init() is called on a new genlist.
 249 ****************************************************************************/
 250 void genlist_clear(struct genlist *pgenlist)
 251 {
 252   fc_assert_ret(NULL != pgenlist);
 253
 254   if (0 < pgenlist->nelements) {
 255     genlist_free_fn_t free_data_func = pgenlist->free_data_func;
 256     struct genlist_link *plink = pgenlist->head_link, *plink2;
 257
 258     pgenlist->head_link = NULL;
 259     pgenlist->tail_link = NULL;
 260
 261     pgenlist->nelements = 0;
 262
 263     if (NULL != free_data_func) {
 264       do {
 265         plink2 = plink->next;
 266         free_data_func(plink->dataptr);
 267         free(plink);
 268       } while (NULL != (plink = plink2));
 269     } else {
 270       do {
 271         plink2 = plink->next;
 272         free(plink);
 273       } while (NULL != (plink = plink2));
 274     }
 275   }
 276 }
 277
 278 /****************************************************************************
 279   Remove all duplicates of element from every consecutive group of equal
 280   elements in the list.
 281 ****************************************************************************/
 282 void genlist_unique(struct genlist *pgenlist)
 283 {
 284   genlist_unique_full(pgenlist, NULL);
 285 }
 286
 287 /****************************************************************************
 288   Remove all duplicates of element from every consecutive group of equal
 289   elements in the list (equality is assumed from if the compare function
 290   return TRUE).
 291 ****************************************************************************/
 292 void genlist_unique_full(struct genlist *pgenlist,
 293                          genlist_comp_fn_t comp_data_func)
 294 {
 295   fc_assert_ret(NULL != pgenlist);
 296
 297   if (2 <= pgenlist->nelements) {
 298     struct genlist_link *plink = pgenlist->head_link, *plink2;
 299
 300     if (NULL != comp_data_func) {
 301       do {
 302         plink2 = plink->next;
 303         if (NULL != plink2 && comp_data_func(plink->dataptr,
 304                                              plink2->dataptr)) {
 305           /* Remove this element. */
 306           genlist_link_destroy(pgenlist, plink);
 307         }
 308       } while ((plink = plink2) != NULL);
 309     } else {
 310       do {
 311         plink2 = plink->next;
 312         if (NULL != plink2 && plink->dataptr == plink2->dataptr) {
 313           /* Remove this element. */
 314           genlist_link_destroy(pgenlist, plink);
 315         }
 316       } while ((plink = plink2) != NULL);
 317     }
 318   }
 319 }
 320
 321 /****************************************************************************
 322   Remove an element of the genlist with the specified user-data pointer
 323   given by 'punlink'. If there is no such element, does nothing.
 324   If there are multiple such elements, removes the first one. Return
 325   TRUE if one element has been removed.
 326   See also, genlist_remove_all(), genlist_remove_if() and
 327   genlist_remove_all_if().
 328 ****************************************************************************/
 329 bool genlist_remove(struct genlist *pgenlist, const void *punlink)
 330 {
 331   struct genlist_link *plink;
 332
 333   fc_assert_ret_val(NULL != pgenlist, FALSE);
 334
 335   for (plink = pgenlist->head_link; NULL != plink; plink = plink->next) {
 336     if (plink->dataptr == punlink) {
 337       genlist_link_destroy(pgenlist, plink);
 338       return TRUE;
 339     }
 340   }
 341
 342   return FALSE;
 343 }
 344
 345 /****************************************************************************
 346   Remove all elements of the genlist with the specified user-data pointer
 347   given by 'punlink'. Return the number of removed elements.
 348   See also, genlist_remove(), genlist_remove_if() and
 349   genlist_remove_all_if().
 350 ****************************************************************************/
 351 int genlist_remove_all(struct genlist *pgenlist, const void *punlink)
 352 {
 353   struct genlist_link *plink;
 354   int count = 0;
 355
 356   fc_assert_ret_val(NULL != pgenlist, 0);
 357
 358   for (plink = pgenlist->head_link; NULL != plink;) {
 359     if (plink->dataptr == punlink) {
 360       struct genlist_link *pnext = plink->next;
 361
 362       genlist_link_destroy(pgenlist, plink);
 363       count++;
 364       plink = pnext;
 365     } else {
 366       plink = plink->next;
 367     }
 368   }
 369
 370   return count;
 371 }
 372
 373 /****************************************************************************
 374   Remove the first element of the genlist which fit the function (the
 375   function return TRUE). Return TRUE if one element has been removed.
 376   See also, genlist_remove(), genlist_remove_all(), and
 377   genlist_remove_all_if().
 378 ****************************************************************************/
 379 bool genlist_remove_if(struct genlist *pgenlist,
 380                        genlist_cond_fn_t cond_data_func)
 381 {
 382   fc_assert_ret_val(NULL != pgenlist, FALSE);
 383
 384   if (NULL != cond_data_func) {
 385     struct genlist_link *plink = pgenlist->head_link;
 386
 387     for (; NULL != plink; plink = plink->next) {
 388       if (cond_data_func(plink->dataptr)) {
 389         genlist_link_destroy(pgenlist, plink);
 390         return TRUE;
 391       }
 392     }
 393   }
 394
 395   return FALSE;
 396 }
 397
 398 /****************************************************************************
 399   Remove all elements of the genlist which fit the function (the
 400   function return TRUE). Return the number of removed elements.
 401   See also, genlist_remove(), genlist_remove_all(), and
 402   genlist_remove_if().
 403 ****************************************************************************/
 404 int genlist_remove_all_if(struct genlist *pgenlist,
 405                           genlist_cond_fn_t cond_data_func)
 406 {
 407   fc_assert_ret_val(NULL != pgenlist, 0);
 408
 409   if (NULL != cond_data_func) {
 410     struct genlist_link *plink = pgenlist->head_link;
 411     int count = 0;
 412
 413     while (NULL != plink) {
 414       if (cond_data_func(plink->dataptr)) {
 415         struct genlist_link *pnext = plink->next;
 416
 417         genlist_link_destroy(pgenlist, plink);
 418         count++;
 419         plink = pnext;
 420       } else {
 421         plink = plink->next;
 422       }
 423     }
 424     return count;
 425   }
 426
 427   return 0;
 428 }
 429
 430 /****************************************************************************
 431   Remove the element pointed to plink.
 432
 433   NB: After calling this function 'plink' is no more usable. You should
 434   have saved the next or previous link before.
 435 ****************************************************************************/
 436 void genlist_erase(struct genlist *pgenlist, struct genlist_link *plink)
 437 {
 438   fc_assert_ret(NULL != pgenlist);
 439
 440   if (NULL != plink) {
 441     genlist_link_destroy(pgenlist, plink);
 442   }
 443 }
 444
 445 /****************************************************************************
 446   Remove the first element of the genlist.
 447 ****************************************************************************/
 448 void genlist_pop_front(struct genlist *pgenlist)
 449 {
 450   fc_assert_ret(NULL != pgenlist);
 451
 452   if (NULL != pgenlist->head_link) {
 453     genlist_link_destroy(pgenlist, pgenlist->head_link);
 454   }
 455 }
 456
 457 /****************************************************************************
 458   Remove the last element of the genlist.
 459 ****************************************************************************/
 460 void genlist_pop_back(struct genlist *pgenlist)
 461 {
 462   fc_assert_ret(NULL != pgenlist);
 463
 464   if (NULL != pgenlist->tail_link) {
 465     genlist_link_destroy(pgenlist, pgenlist->tail_link);
 466   }
 467 }
 468
 469 /****************************************************************************
 470   Insert a new element in the list, at position 'pos', with the specified
 471   user-data pointer 'data'.  Existing elements at >= pos are moved one
 472   space to the "right".  Recall 'pos' can be -1 meaning add at the
 473   end of the list.  For an empty list pos has no effect.
 474   A bad 'pos' value for a non-empty list is treated as -1 (is this
 475   a good idea?)
 476 ****************************************************************************/
 477 void genlist_insert(struct genlist *pgenlist, void *data, int pos)
 478 {
 479   fc_assert_ret(NULL != pgenlist);
 480
 481   if (0 == pgenlist->nelements) {
 482     /* List is empty, ignore pos. */
 483     genlist_link_new(pgenlist, data, NULL, NULL);
 484   } else if (0 == pos) {
 485     /* Prepend. */
 486     genlist_link_new(pgenlist, data, NULL, pgenlist->head_link);
 487   } else if (-1 >= pos || pos >= pgenlist->nelements) {
 488     /* Append. */
 489     genlist_link_new(pgenlist, data, pgenlist->tail_link, NULL);
 490   } else {
 491     /* Insert before plink. */
 492     struct genlist_link *plink = genlist_link_at_pos(pgenlist, pos);
 493
 494     fc_assert_ret(NULL != plink);
 495     genlist_link_new(pgenlist, data, plink->prev, plink);
 496   }
 497 }
 498
 499 /****************************************************************************
 500   Insert an item after the link. If plink is NULL, prepend to the list.
 501 ****************************************************************************/
 502 void genlist_insert_after(struct genlist *pgenlist, void *data,
 503                           struct genlist_link *plink)
 504 {
 505   fc_assert_ret(NULL != pgenlist);
 506
 507   genlist_link_new(pgenlist, data, plink,
 508                    NULL != plink ? plink->next : pgenlist->head_link);
 509 }
 510
 511 /****************************************************************************
 512   Insert an item before the link.
 513 ****************************************************************************/
 514 void genlist_insert_before(struct genlist *pgenlist, void *data,
 515                           struct genlist_link *plink)
 516 {
 517   fc_assert_ret(NULL != pgenlist);
 518
 519   genlist_link_new(pgenlist, data,
 520                    NULL != plink ? plink->prev : pgenlist->tail_link, plink);
 521 }
 522
 523 /****************************************************************************
 524   Insert an item at the start of the list.
 525 ****************************************************************************/
 526 void genlist_prepend(struct genlist *pgenlist, void *data)
 527 {
 528   fc_assert_ret(NULL != pgenlist);
 529
 530   genlist_link_new(pgenlist, data, NULL, pgenlist->head_link);
 531 }
 532
 533 /****************************************************************************
 534   Insert an item at the end of the list.
 535 ****************************************************************************/
 536 void genlist_append(struct genlist *pgenlist, void *data)
 537 {
 538   fc_assert_ret(NULL != pgenlist);
 539
 540   genlist_link_new(pgenlist, data, pgenlist->tail_link, NULL);
 541 }
 542
 543 /****************************************************************************
 544   Return the link where data is equal to 'data'. Returns NULL if not found.
 545
 546   This is an O(n) operation.  Hence, "search".
 547 ****************************************************************************/
 548 struct genlist_link *genlist_search(const struct genlist *pgenlist,
 549                                     const void *data)
 550 {
 551   struct genlist_link *plink;
 552
 553   fc_assert_ret_val(NULL != pgenlist, NULL);
 554
 555   for (plink = pgenlist->head_link; plink; plink = plink->next) {
 556     if (plink->dataptr == data) {
 557       return plink;
 558     }
 559   }
 560
 561   return NULL;
 562 }
 563
 564 /****************************************************************************
 565   Return the link which fit the conditional function. Returns NULL if no
 566   match.
 567 ****************************************************************************/
 568 struct genlist_link *genlist_search_if(const struct genlist *pgenlist,
 569                                        genlist_cond_fn_t cond_data_func)
 570 {
 571   fc_assert_ret_val(NULL != pgenlist, NULL);
 572
 573   if (NULL != cond_data_func) {
 574     struct genlist_link *plink = pgenlist->head_link;
 575
 576     for (; NULL != plink; plink = plink->next) {
 577       if (cond_data_func(plink->dataptr)) {
 578         return plink;
 579       }
 580     }
 581   }
 582
 583   return NULL;
 584 }
 585
 586 /****************************************************************************
 587   Sort the elements of a genlist.
 588
 589   The comparison function should be a function usable by qsort; note
 590   that the const void * arguments to compar should really be "pointers to
 591   void*", where the void* being pointed to are the genlist dataptrs.
 592   That is, there are two levels of indirection.
 593   To do the sort we first construct an array of pointers corresponding
 594   the the genlist dataptrs, then sort those and put them back into
 595   the genlist.
 596 ****************************************************************************/
 597 void genlist_sort(struct genlist *pgenlist,
 598                   int (*compar) (const void *, const void *))
 599 {
 600   const size_t n = genlist_size(pgenlist);
 601   void **sortbuf;
 602   struct genlist_link *myiter;
 603   int i;
 604
 605   if (n <= 1) {
 606     return;
 607   }
 608
 609   sortbuf = fc_malloc(n * sizeof(void *));
 610   myiter = genlist_head(pgenlist);
 611   for (i = 0; i < n; i++, myiter = myiter->next) {
 612     sortbuf[i] = myiter->dataptr;
 613   }
 614
 615   qsort(sortbuf, n, sizeof(*sortbuf), compar);
 616
 617   myiter = genlist_head(pgenlist);
 618   for (i = 0; i < n; i++, myiter = myiter->next) {
 619     myiter->dataptr = sortbuf[i];
 620   }
 621   FC_FREE(sortbuf);
 622 }
 623
 624 /****************************************************************************
 625   Randomize the elements of a genlist using the Fisher-Yates shuffle.
 626
 627   see: genlist_sort() and shared.c:array_shuffle()
 628 ****************************************************************************/
 629 void genlist_shuffle(struct genlist *pgenlist)
 630 {
 631   const int n = genlist_size(pgenlist);
 632   void *sortbuf[n];
 633   struct genlist_link *myiter;
 634   int i, shuffle[n];
 635
 636   if (n <= 1) {
 637     return;
 638   }
 639
 640   myiter = genlist_head(pgenlist);
 641   for (i = 0; i < n; i++, myiter = myiter->next) {
 642     sortbuf[i] = myiter->dataptr;
 643     /* also create the shuffle list */
 644     shuffle[i] = i;
 645   }
 646
 647   /* randomize it */
 648   array_shuffle(shuffle, n);
 649
 650   /* create the shuffled list */
 651   myiter = genlist_head(pgenlist);
 652   for (i = 0; i < n; i++, myiter = myiter->next) {
 653     myiter->dataptr = sortbuf[shuffle[i]];
 654   }
 655 }
 656
 657 /****************************************************************************
 658   Reverse the order of the elements in the genlist.
 659 ****************************************************************************/
 660 void genlist_reverse(struct genlist *pgenlist)
 661 {
 662   struct genlist_link *head, *tail;
 663   int counter;
 664
 665   fc_assert_ret(NULL != pgenlist);
 666
 667   head = pgenlist->head_link;
 668   tail = pgenlist->tail_link;
 669   for (counter = pgenlist->nelements / 2; 0 < counter; counter--) {
 670     /* Swap. */
 671     void *temp = head->dataptr;
 672     head->dataptr = tail->dataptr;
 673     tail->dataptr = temp;
 674
 675     head = head->next;
 676     tail = tail->prev;
 677   }
 678 }
 679
 680 /****************************************************************************
 681   Allocates list mutex
 682 ****************************************************************************/
 683 void genlist_allocate_mutex(struct genlist *pgenlist)
 684 {
 685   fc_allocate_mutex(&pgenlist->mutex);
 686 }
 687
 688 /****************************************************************************
 689   Releases list mutex
 690 ****************************************************************************/
 691 void genlist_release_mutex(struct genlist *pgenlist)
 692 {
 693   fc_release_mutex(&pgenlist->mutex);
 694 }