lib/gl_anylinked_list2.h

   1 /* Sequential list data type implemented by a linked list.
   2    Copyright (C) 2006-2007 Free Software Foundation, Inc.
   3    Written by Bruno Haible <bruno@clisp.org>, 2006.
   4
   5    This program is free software: you can redistribute it and/or modify
   6    it under the terms of the GNU General Public License as published by
   7    the Free Software Foundation; either version 3 of the License, or
   8    (at your option) any later version.
   9
  10    This program is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13    GNU General Public License for more details.
  14
  15    You should have received a copy of the GNU General Public License
  16    along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
  17
  18 /* Common code of gl_linked_list.c and gl_linkedhash_list.c.  */
  19
  20 /* If the symbol SIGNAL_SAFE_LIST is defined, the code is compiled in such
  21    a way that a gl_list_t data structure may be used from within a signal
  22    handler.  The operations allowed in the signal handler are:
  23      gl_list_iterator, gl_list_iterator_next, gl_list_iterator_free.
  24    The list and node fields that are therefore accessed from the signal handler
  25    are:
  26      list->root, node->next, node->value.
  27    We are careful to make modifications to these fields only in an order
  28    that maintains the consistency of the list data structure at any moment,
  29    and we use 'volatile' assignments to prevent the compiler from reordering
  30    such assignments.  */
  31 #ifdef SIGNAL_SAFE_LIST
  32 # define ASYNCSAFE(type) *(volatile type *)&
  33 #else
  34 # define ASYNCSAFE(type)
  35 #endif
  36
  37 /* -------------------------- gl_list_t Data Type -------------------------- */
  38
  39 static gl_list_t
  40 gl_linked_create_empty (gl_list_implementation_t implementation,
  41                         gl_listelement_equals_fn equals_fn,
  42                         gl_listelement_hashcode_fn hashcode_fn,
  43                         gl_listelement_dispose_fn dispose_fn,
  44                         bool allow_duplicates)
  45 {
  46   struct gl_list_impl *list = XMALLOC (struct gl_list_impl);
  47
  48   list->base.vtable = implementation;
  49   list->base.equals_fn = equals_fn;
  50   list->base.hashcode_fn = hashcode_fn;
  51   list->base.dispose_fn = dispose_fn;
  52   list->base.allow_duplicates = allow_duplicates;
  53 #if WITH_HASHTABLE
  54   list->table_size = 11;
  55   list->table = XCALLOC (list->table_size, gl_hash_entry_t);
  56 #endif
  57   list->root.next = &list->root;
  58   list->root.prev = &list->root;
  59   list->count = 0;
  60
  61   return list;
  62 }
  63
  64 static gl_list_t
  65 gl_linked_create (gl_list_implementation_t implementation,
  66                   gl_listelement_equals_fn equals_fn,
  67                   gl_listelement_hashcode_fn hashcode_fn,
  68                   gl_listelement_dispose_fn dispose_fn,
  69                   bool allow_duplicates,
  70                   size_t count, const void **contents)
  71 {
  72   struct gl_list_impl *list = XMALLOC (struct gl_list_impl);
  73   gl_list_node_t tail;
  74
  75   list->base.vtable = implementation;
  76   list->base.equals_fn = equals_fn;
  77   list->base.hashcode_fn = hashcode_fn;
  78   list->base.dispose_fn = dispose_fn;
  79   list->base.allow_duplicates = allow_duplicates;
  80 #if WITH_HASHTABLE
  81   {
  82     size_t estimate = xsum (count, count / 2); /* 1.5 * count */
  83     if (estimate < 10)
  84       estimate = 10;
  85     list->table_size = next_prime (estimate);
  86     list->table = XCALLOC (list->table_size, gl_hash_entry_t);
  87   }
  88 #endif
  89   list->count = count;
  90   tail = &list->root;
  91   for (; count > 0; contents++, count--)
  92     {
  93       gl_list_node_t node = XMALLOC (struct gl_list_node_impl);
  94
  95       node->value = *contents;
  96 #if WITH_HASHTABLE
  97       node->h.hashcode =
  98         (list->base.hashcode_fn != NULL
  99          ? list->base.hashcode_fn (node->value)
 100          : (size_t)(uintptr_t) node->value);
 101
 102       /* Add node to the hash table.  */
 103       add_to_bucket (list, node);
 104 #endif
 105
 106       /* Add node to the list.  */
 107       node->prev = tail;
 108       tail->next = node;
 109       tail = node;
 110     }
 111   tail->next = &list->root;
 112   list->root.prev = tail;
 113
 114   return list;
 115 }
 116
 117 static size_t
 118 gl_linked_size (gl_list_t list)
 119 {
 120   return list->count;
 121 }
 122
 123 static const void *
 124 gl_linked_node_value (gl_list_t list, gl_list_node_t node)
 125 {
 126   return node->value;
 127 }
 128
 129 static gl_list_node_t
 130 gl_linked_next_node (gl_list_t list, gl_list_node_t node)
 131 {
 132   return (node->next != &list->root ? node->next : NULL);
 133 }
 134
 135 static gl_list_node_t
 136 gl_linked_previous_node (gl_list_t list, gl_list_node_t node)
 137 {
 138   return (node->prev != &list->root ? node->prev : NULL);
 139 }
 140
 141 static const void *
 142 gl_linked_get_at (gl_list_t list, size_t position)
 143 {
 144   size_t count = list->count;
 145   gl_list_node_t node;
 146
 147   if (!(position < count))
 148     /* Invalid argument.  */
 149     abort ();
 150   /* Here we know count > 0.  */
 151   if (position <= ((count - 1) / 2))
 152     {
 153       node = list->root.next;
 154       for (; position > 0; position--)
 155         node = node->next;
 156     }
 157   else
 158     {
 159       position = count - 1 - position;
 160       node = list->root.prev;
 161       for (; position > 0; position--)
 162         node = node->prev;
 163     }
 164   return node->value;
 165 }
 166
 167 static gl_list_node_t
 168 gl_linked_set_at (gl_list_t list, size_t position, const void *elt)
 169 {
 170   size_t count = list->count;
 171   gl_list_node_t node;
 172
 173   if (!(position < count))
 174     /* Invalid argument.  */
 175     abort ();
 176   /* Here we know count > 0.  */
 177   if (position <= ((count - 1) / 2))
 178     {
 179       node = list->root.next;
 180       for (; position > 0; position--)
 181         node = node->next;
 182     }
 183   else
 184     {
 185       position = count - 1 - position;
 186       node = list->root.prev;
 187       for (; position > 0; position--)
 188         node = node->prev;
 189     }
 190 #if WITH_HASHTABLE
 191   if (elt != node->value)
 192     {
 193       size_t new_hashcode =
 194         (list->base.hashcode_fn != NULL
 195          ? list->base.hashcode_fn (elt)
 196          : (size_t)(uintptr_t) elt);
 197
 198       if (new_hashcode != node->h.hashcode)
 199         {
 200           remove_from_bucket (list, node);
 201           node->value = elt;
 202           node->h.hashcode = new_hashcode;
 203           add_to_bucket (list, node);
 204         }
 205       else
 206         node->value = elt;
 207     }
 208 #else
 209   node->value = elt;
 210 #endif
 211   return node;
 212 }
 213
 214 static gl_list_node_t
 215 gl_linked_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
 216                           const void *elt)
 217 {
 218   size_t count = list->count;
 219
 220   if (!(start_index <= end_index && end_index <= count))
 221     /* Invalid arguments.  */
 222     abort ();
 223   {
 224 #if WITH_HASHTABLE
 225     size_t hashcode =
 226       (list->base.hashcode_fn != NULL
 227        ? list->base.hashcode_fn (elt)
 228        : (size_t)(uintptr_t) elt);
 229     size_t bucket = hashcode % list->table_size;
 230     gl_listelement_equals_fn equals = list->base.equals_fn;
 231
 232     if (!list->base.allow_duplicates)
 233       {
 234         /* Look for the first match in the hash bucket.  */
 235         gl_list_node_t found = NULL;
 236         gl_list_node_t node;
 237
 238         for (node = (gl_list_node_t) list->table[bucket];
 239              node != NULL;
 240              node = (gl_list_node_t) node->h.hash_next)
 241           if (node->h.hashcode == hashcode
 242               && (equals != NULL
 243                   ? equals (elt, node->value)
 244                   : elt == node->value))
 245             {
 246               found = node;
 247               break;
 248             }
 249         if (start_index > 0)
 250           /* Look whether found's index is < start_index.  */
 251           for (node = list->root.next; ; node = node->next)
 252             {
 253               if (node == found)
 254                 return NULL;
 255               if (--start_index == 0)
 256                 break;
 257             }
 258         if (end_index < count)
 259           /* Look whether found's index is >= end_index.  */
 260           {
 261             end_index = count - end_index;
 262             for (node = list->root.prev; ; node = node->prev)
 263               {
 264                 if (node == found)
 265                   return NULL;
 266                 if (--end_index == 0)
 267                   break;
 268               }
 269           }
 270         return found;
 271       }
 272     else
 273       {
 274         /* Look whether there is more than one match in the hash bucket.  */
 275         bool multiple_matches = false;
 276         gl_list_node_t first_match = NULL;
 277         gl_list_node_t node;
 278
 279         for (node = (gl_list_node_t) list->table[bucket];
 280              node != NULL;
 281              node = (gl_list_node_t) node->h.hash_next)
 282           if (node->h.hashcode == hashcode
 283               && (equals != NULL
 284                   ? equals (elt, node->value)
 285                   : elt == node->value))
 286             {
 287               if (first_match == NULL)
 288                 first_match = node;
 289               else
 290                 {
 291                   multiple_matches = true;
 292                   break;
 293                 }
 294             }
 295         if (multiple_matches)
 296           {
 297             /* We need the match with the smallest index.  But we don't have
 298                a fast mapping node -> index.  So we have to walk the list.  */
 299             end_index -= start_index;
 300             node = list->root.next;
 301             for (; start_index > 0; start_index--)
 302               node = node->next;
 303
 304             for (;
 305                  end_index > 0;
 306                  node = node->next, end_index--)
 307               if (node->h.hashcode == hashcode
 308                   && (equals != NULL
 309                       ? equals (elt, node->value)
 310                       : elt == node->value))
 311                 return node;
 312             /* The matches must have all been at indices < start_index or
 313                >= end_index.  */
 314             return NULL;
 315           }
 316         else
 317           {
 318             if (start_index > 0)
 319               /* Look whether first_match's index is < start_index.  */
 320               for (node = list->root.next; node != &list->root; node = node->next)
 321                 {
 322                   if (node == first_match)
 323                     return NULL;
 324                   if (--start_index == 0)
 325                     break;
 326                 }
 327             if (end_index < list->count)
 328               /* Look whether first_match's index is >= end_index.  */
 329               {
 330                 end_index = list->count - end_index;
 331                 for (node = list->root.prev; ; node = node->prev)
 332                   {
 333                     if (node == first_match)
 334                       return NULL;
 335                     if (--end_index == 0)
 336                       break;
 337                   }
 338               }
 339             return first_match;
 340           }
 341       }
 342 #else
 343     gl_listelement_equals_fn equals = list->base.equals_fn;
 344     gl_list_node_t node = list->root.next;
 345
 346     end_index -= start_index;
 347     for (; start_index > 0; start_index--)
 348       node = node->next;
 349
 350     if (equals != NULL)
 351       {
 352         for (; end_index > 0; node = node->next, end_index--)
 353           if (equals (elt, node->value))
 354             return node;
 355       }
 356     else
 357       {
 358         for (; end_index > 0; node = node->next, end_index--)
 359           if (elt == node->value)
 360             return node;
 361       }
 362     return NULL;
 363 #endif
 364   }
 365 }
 366
 367 static size_t
 368 gl_linked_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
 369                            const void *elt)
 370 {
 371   size_t count = list->count;
 372
 373   if (!(start_index <= end_index && end_index <= count))
 374     /* Invalid arguments.  */
 375     abort ();
 376   {
 377 #if WITH_HASHTABLE
 378     /* Here the hash table doesn't help much.  It only allows us to minimize
 379        the number of equals() calls, by looking up first the node and then
 380        its index.  */
 381     size_t hashcode =
 382       (list->base.hashcode_fn != NULL
 383        ? list->base.hashcode_fn (elt)
 384        : (size_t)(uintptr_t) elt);
 385     size_t bucket = hashcode % list->table_size;
 386     gl_listelement_equals_fn equals = list->base.equals_fn;
 387     gl_list_node_t node;
 388
 389     /* First step: Look up the node.  */
 390     if (!list->base.allow_duplicates)
 391       {
 392         /* Look for the first match in the hash bucket.  */
 393         for (node = (gl_list_node_t) list->table[bucket];
 394              node != NULL;
 395              node = (gl_list_node_t) node->h.hash_next)
 396           if (node->h.hashcode == hashcode
 397               && (equals != NULL
 398                   ? equals (elt, node->value)
 399                   : elt == node->value))
 400             break;
 401       }
 402     else
 403       {
 404         /* Look whether there is more than one match in the hash bucket.  */
 405         bool multiple_matches = false;
 406         gl_list_node_t first_match = NULL;
 407
 408         for (node = (gl_list_node_t) list->table[bucket];
 409              node != NULL;
 410              node = (gl_list_node_t) node->h.hash_next)
 411           if (node->h.hashcode == hashcode
 412               && (equals != NULL
 413                   ? equals (elt, node->value)
 414                   : elt == node->value))
 415             {
 416               if (first_match == NULL)
 417                 first_match = node;
 418               else
 419                 {
 420                   multiple_matches = true;
 421                   break;
 422                 }
 423             }
 424         if (multiple_matches)
 425           {
 426             /* We need the match with the smallest index.  But we don't have
 427                a fast mapping node -> index.  So we have to walk the list.  */
 428             size_t index;
 429
 430             index = start_index;
 431             node = list->root.next;
 432             for (; start_index > 0; start_index--)
 433               node = node->next;
 434
 435             for (;
 436                  index < end_index;
 437                  node = node->next, index++)
 438               if (node->h.hashcode == hashcode
 439                   && (equals != NULL
 440                       ? equals (elt, node->value)
 441                       : elt == node->value))
 442                 return index;
 443             /* The matches must have all been at indices < start_index or
 444                >= end_index.  */
 445             return (size_t)(-1);
 446           }
 447         node = first_match;
 448       }
 449
 450     /* Second step: Look up the index of the node.  */
 451     if (node == NULL)
 452       return (size_t)(-1);
 453     else
 454       {
 455         size_t index = 0;
 456
 457         for (; node->prev != &list->root; node = node->prev)
 458           index++;
 459
 460         if (index >= start_index && index < end_index)
 461           return index;
 462         else
 463           return (size_t)(-1);
 464       }
 465 #else
 466     gl_listelement_equals_fn equals = list->base.equals_fn;
 467     size_t index = start_index;
 468     gl_list_node_t node = list->root.next;
 469
 470     for (; start_index > 0; start_index--)
 471       node = node->next;
 472
 473     if (equals != NULL)
 474       {
 475         for (;
 476              index < end_index;
 477              node = node->next, index++)
 478           if (equals (elt, node->value))
 479             return index;
 480       }
 481     else
 482       {
 483         for (;
 484              index < end_index;
 485              node = node->next, index++)
 486           if (elt == node->value)
 487             return index;
 488       }
 489     return (size_t)(-1);
 490 #endif
 491   }
 492 }
 493
 494 static gl_list_node_t
 495 gl_linked_add_first (gl_list_t list, const void *elt)
 496 {
 497   gl_list_node_t node = XMALLOC (struct gl_list_node_impl);
 498
 499   ASYNCSAFE(const void *) node->value = elt;
 500 #if WITH_HASHTABLE
 501   node->h.hashcode =
 502     (list->base.hashcode_fn != NULL
 503      ? list->base.hashcode_fn (node->value)
 504      : (size_t)(uintptr_t) node->value);
 505
 506   /* Add node to the hash table.  */
 507   add_to_bucket (list, node);
 508 #endif
 509
 510   /* Add node to the list.  */
 511   node->prev = &list->root;
 512   ASYNCSAFE(gl_list_node_t) node->next = list->root.next;
 513   node->next->prev = node;
 514   ASYNCSAFE(gl_list_node_t) list->root.next = node;
 515   list->count++;
 516
 517 #if WITH_HASHTABLE
 518   hash_resize_after_add (list);
 519 #endif
 520
 521   return node;
 522 }
 523
 524 static gl_list_node_t
 525 gl_linked_add_last (gl_list_t list, const void *elt)
 526 {
 527   gl_list_node_t node = XMALLOC (struct gl_list_node_impl);
 528
 529   ASYNCSAFE(const void *) node->value = elt;
 530 #if WITH_HASHTABLE
 531   node->h.hashcode =
 532     (list->base.hashcode_fn != NULL
 533      ? list->base.hashcode_fn (node->value)
 534      : (size_t)(uintptr_t) node->value);
 535
 536   /* Add node to the hash table.  */
 537   add_to_bucket (list, node);
 538 #endif
 539
 540   /* Add node to the list.  */
 541   ASYNCSAFE(gl_list_node_t) node->next = &list->root;
 542   node->prev = list->root.prev;
 543   ASYNCSAFE(gl_list_node_t) node->prev->next = node;
 544   list->root.prev = node;
 545   list->count++;
 546
 547 #if WITH_HASHTABLE
 548   hash_resize_after_add (list);
 549 #endif
 550
 551   return node;
 552 }
 553
 554 static gl_list_node_t
 555 gl_linked_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
 556 {
 557   gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
 558
 559   ASYNCSAFE(const void *) new_node->value = elt;
 560 #if WITH_HASHTABLE
 561   new_node->h.hashcode =
 562     (list->base.hashcode_fn != NULL
 563      ? list->base.hashcode_fn (new_node->value)
 564      : (size_t)(uintptr_t) new_node->value);
 565
 566   /* Add new_node to the hash table.  */
 567   add_to_bucket (list, new_node);
 568 #endif
 569
 570   /* Add new_node to the list.  */
 571   ASYNCSAFE(gl_list_node_t) new_node->next = node;
 572   new_node->prev = node->prev;
 573   ASYNCSAFE(gl_list_node_t) new_node->prev->next = new_node;
 574   node->prev = new_node;
 575   list->count++;
 576
 577 #if WITH_HASHTABLE
 578   hash_resize_after_add (list);
 579 #endif
 580
 581   return new_node;
 582 }
 583
 584 static gl_list_node_t
 585 gl_linked_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
 586 {
 587   gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
 588
 589   ASYNCSAFE(const void *) new_node->value = elt;
 590 #if WITH_HASHTABLE
 591   new_node->h.hashcode =
 592     (list->base.hashcode_fn != NULL
 593      ? list->base.hashcode_fn (new_node->value)
 594      : (size_t)(uintptr_t) new_node->value);
 595
 596   /* Add new_node to the hash table.  */
 597   add_to_bucket (list, new_node);
 598 #endif
 599
 600   /* Add new_node to the list.  */
 601   new_node->prev = node;
 602   ASYNCSAFE(gl_list_node_t) new_node->next = node->next;
 603   new_node->next->prev = new_node;
 604   ASYNCSAFE(gl_list_node_t) node->next = new_node;
 605   list->count++;
 606
 607 #if WITH_HASHTABLE
 608   hash_resize_after_add (list);
 609 #endif
 610
 611   return new_node;
 612 }
 613
 614 static gl_list_node_t
 615 gl_linked_add_at (gl_list_t list, size_t position, const void *elt)
 616 {
 617   size_t count = list->count;
 618   gl_list_node_t new_node;
 619
 620   if (!(position <= count))
 621     /* Invalid argument.  */
 622     abort ();
 623
 624   new_node = XMALLOC (struct gl_list_node_impl);
 625   ASYNCSAFE(const void *) new_node->value = elt;
 626 #if WITH_HASHTABLE
 627   new_node->h.hashcode =
 628     (list->base.hashcode_fn != NULL
 629      ? list->base.hashcode_fn (new_node->value)
 630      : (size_t)(uintptr_t) new_node->value);
 631
 632   /* Add new_node to the hash table.  */
 633   add_to_bucket (list, new_node);
 634 #endif
 635
 636   /* Add new_node to the list.  */
 637   if (position <= (count / 2))
 638     {
 639       gl_list_node_t node;
 640
 641       node = &list->root;
 642       for (; position > 0; position--)
 643         node = node->next;
 644       new_node->prev = node;
 645       ASYNCSAFE(gl_list_node_t) new_node->next = node->next;
 646       new_node->next->prev = new_node;
 647       ASYNCSAFE(gl_list_node_t) node->next = new_node;
 648     }
 649   else
 650     {
 651       gl_list_node_t node;
 652
 653       position = count - position;
 654       node = &list->root;
 655       for (; position > 0; position--)
 656         node = node->prev;
 657       ASYNCSAFE(gl_list_node_t) new_node->next = node;
 658       new_node->prev = node->prev;
 659       ASYNCSAFE(gl_list_node_t) new_node->prev->next = new_node;
 660       node->prev = new_node;
 661     }
 662   list->count++;
 663
 664 #if WITH_HASHTABLE
 665   hash_resize_after_add (list);
 666 #endif
 667
 668   return new_node;
 669 }
 670
 671 static bool
 672 gl_linked_remove_node (gl_list_t list, gl_list_node_t node)
 673 {
 674   gl_list_node_t prev;
 675   gl_list_node_t next;
 676
 677 #if WITH_HASHTABLE
 678   /* Remove node from the hash table.  */
 679   remove_from_bucket (list, node);
 680 #endif
 681
 682   /* Remove node from the list.  */
 683   prev = node->prev;
 684   next = node->next;
 685
 686   ASYNCSAFE(gl_list_node_t) prev->next = next;
 687   next->prev = prev;
 688   list->count--;
 689
 690   if (list->base.dispose_fn != NULL)
 691     list->base.dispose_fn (node->value);
 692   free (node);
 693   return true;
 694 }
 695
 696 static bool
 697 gl_linked_remove_at (gl_list_t list, size_t position)
 698 {
 699   size_t count = list->count;
 700   gl_list_node_t removed_node;
 701
 702   if (!(position < count))
 703     /* Invalid argument.  */
 704     abort ();
 705   /* Here we know count > 0.  */
 706   if (position <= ((count - 1) / 2))
 707     {
 708       gl_list_node_t node;
 709       gl_list_node_t after_removed;
 710
 711       node = &list->root;
 712       for (; position > 0; position--)
 713         node = node->next;
 714       removed_node = node->next;
 715       after_removed = node->next->next;
 716       ASYNCSAFE(gl_list_node_t) node->next = after_removed;
 717       after_removed->prev = node;
 718     }
 719   else
 720     {
 721       gl_list_node_t node;
 722       gl_list_node_t before_removed;
 723
 724       position = count - 1 - position;
 725       node = &list->root;
 726       for (; position > 0; position--)
 727         node = node->prev;
 728       removed_node = node->prev;
 729       before_removed = node->prev->prev;
 730       node->prev = before_removed;
 731       ASYNCSAFE(gl_list_node_t) before_removed->next = node;
 732     }
 733 #if WITH_HASHTABLE
 734   remove_from_bucket (list, removed_node);
 735 #endif
 736   list->count--;
 737
 738   if (list->base.dispose_fn != NULL)
 739     list->base.dispose_fn (removed_node->value);
 740   free (removed_node);
 741   return true;
 742 }
 743
 744 static bool
 745 gl_linked_remove (gl_list_t list, const void *elt)
 746 {
 747   gl_list_node_t node = gl_linked_search_from_to (list, 0, list->count, elt);
 748
 749   if (node != NULL)
 750     return gl_linked_remove_node (list, node);
 751   else
 752     return false;
 753 }
 754
 755 static void
 756 gl_linked_list_free (gl_list_t list)
 757 {
 758   gl_listelement_dispose_fn dispose = list->base.dispose_fn;
 759   gl_list_node_t node;
 760
 761   for (node = list->root.next; node != &list->root; )
 762     {
 763       gl_list_node_t next = node->next;
 764       if (dispose != NULL)
 765         dispose (node->value);
 766       free (node);
 767       node = next;
 768     }
 769 #if WITH_HASHTABLE
 770   free (list->table);
 771 #endif
 772   free (list);
 773 }
 774
 775 /* --------------------- gl_list_iterator_t Data Type --------------------- */
 776
 777 static gl_list_iterator_t
 778 gl_linked_iterator (gl_list_t list)
 779 {
 780   gl_list_iterator_t result;
 781
 782   result.vtable = list->base.vtable;
 783   result.list = list;
 784   result.p = list->root.next;
 785   result.q = &list->root;
 786 #ifdef lint
 787   result.i = 0;
 788   result.j = 0;
 789   result.count = 0;
 790 #endif
 791
 792   return result;
 793 }
 794
 795 static gl_list_iterator_t
 796 gl_linked_iterator_from_to (gl_list_t list,
 797                             size_t start_index, size_t end_index)
 798 {
 799   gl_list_iterator_t result;
 800   size_t n1, n2, n3;
 801
 802   if (!(start_index <= end_index && end_index <= list->count))
 803     /* Invalid arguments.  */
 804     abort ();
 805   result.vtable = list->base.vtable;
 806   result.list = list;
 807   n1 = start_index;
 808   n2 = end_index - start_index;
 809   n3 = list->count - end_index;
 810   /* Find the maximum among n1, n2, n3, so as to reduce the number of
 811      loop iterations to n1 + n2 + n3 - max(n1,n2,n3).  */
 812   if (n1 > n2 && n1 > n3)
 813     {
 814       /* n1 is the maximum, use n2 and n3.  */
 815       gl_list_node_t node;
 816       size_t i;
 817
 818       node = &list->root;
 819       for (i = n3; i > 0; i--)
 820         node = node->prev;
 821       result.q = node;
 822       for (i = n2; i > 0; i--)
 823         node = node->prev;
 824       result.p = node;
 825     }
 826   else if (n2 > n3)
 827     {
 828       /* n2 is the maximum, use n1 and n3.  */
 829       gl_list_node_t node;
 830       size_t i;
 831
 832       node = list->root.next;
 833       for (i = n1; i > 0; i--)
 834         node = node->next;
 835       result.p = node;
 836
 837       node = &list->root;
 838       for (i = n3; i > 0; i--)
 839         node = node->prev;
 840       result.q = node;
 841     }
 842   else
 843     {
 844       /* n3 is the maximum, use n1 and n2.  */
 845       gl_list_node_t node;
 846       size_t i;
 847
 848       node = list->root.next;
 849       for (i = n1; i > 0; i--)
 850         node = node->next;
 851       result.p = node;
 852       for (i = n2; i > 0; i--)
 853         node = node->next;
 854       result.q = node;
 855     }
 856
 857 #ifdef lint
 858   result.i = 0;
 859   result.j = 0;
 860   result.count = 0;
 861 #endif
 862
 863   return result;
 864 }
 865
 866 static bool
 867 gl_linked_iterator_next (gl_list_iterator_t *iterator,
 868                          const void **eltp, gl_list_node_t *nodep)
 869 {
 870   if (iterator->p != iterator->q)
 871     {
 872       gl_list_node_t node = (gl_list_node_t) iterator->p;
 873       *eltp = node->value;
 874       if (nodep != NULL)
 875         *nodep = node;
 876       iterator->p = node->next;
 877       return true;
 878     }
 879   else
 880     return false;
 881 }
 882
 883 static void
 884 gl_linked_iterator_free (gl_list_iterator_t *iterator)
 885 {
 886 }
 887
 888 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
 889
 890 static gl_list_node_t
 891 gl_linked_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
 892                              const void *elt)
 893 {
 894   gl_list_node_t node;
 895
 896   for (node = list->root.next; node != &list->root; node = node->next)
 897     {
 898       int cmp = compar (node->value, elt);
 899
 900       if (cmp > 0)
 901         break;
 902       if (cmp == 0)
 903         return node;
 904     }
 905   return NULL;
 906 }
 907
 908 static gl_list_node_t
 909 gl_linked_sortedlist_search_from_to (gl_list_t list,
 910                                      gl_listelement_compar_fn compar,
 911                                      size_t low, size_t high,
 912                                      const void *elt)
 913 {
 914   size_t count = list->count;
 915
 916   if (!(low <= high && high <= list->count))
 917     /* Invalid arguments.  */
 918     abort ();
 919
 920   high -= low;
 921   if (high > 0)
 922     {
 923       /* Here we know low < count.  */
 924       size_t position = low;
 925       gl_list_node_t node;
 926
 927       if (position <= ((count - 1) / 2))
 928         {
 929           node = list->root.next;
 930           for (; position > 0; position--)
 931             node = node->next;
 932         }
 933       else
 934         {
 935           position = count - 1 - position;
 936           node = list->root.prev;
 937           for (; position > 0; position--)
 938             node = node->prev;
 939         }
 940
 941       do
 942         {
 943           int cmp = compar (node->value, elt);
 944
 945           if (cmp > 0)
 946             break;
 947           if (cmp == 0)
 948             return node;
 949           node = node->next;
 950         }
 951       while (--high > 0);
 952     }
 953   return NULL;
 954 }
 955
 956 static size_t
 957 gl_linked_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
 958                               const void *elt)
 959 {
 960   gl_list_node_t node;
 961   size_t index;
 962
 963   for (node = list->root.next, index = 0;
 964        node != &list->root;
 965        node = node->next, index++)
 966     {
 967       int cmp = compar (node->value, elt);
 968
 969       if (cmp > 0)
 970         break;
 971       if (cmp == 0)
 972         return index;
 973     }
 974   return (size_t)(-1);
 975 }
 976
 977 static size_t
 978 gl_linked_sortedlist_indexof_from_to (gl_list_t list,
 979                                       gl_listelement_compar_fn compar,
 980                                       size_t low, size_t high,
 981                                       const void *elt)
 982 {
 983   size_t count = list->count;
 984
 985   if (!(low <= high && high <= list->count))
 986     /* Invalid arguments.  */
 987     abort ();
 988
 989   high -= low;
 990   if (high > 0)
 991     {
 992       /* Here we know low < count.  */
 993       size_t index = low;
 994       size_t position = low;
 995       gl_list_node_t node;
 996
 997       if (position <= ((count - 1) / 2))
 998         {
 999           node = list->root.next;
1000           for (; position > 0; position--)
1001             node = node->next;
1002         }
1003       else
1004         {
1005           position = count - 1 - position;
1006           node = list->root.prev;
1007           for (; position > 0; position--)
1008             node = node->prev;
1009         }
1010
1011       do
1012         {
1013           int cmp = compar (node->value, elt);
1014
1015           if (cmp > 0)
1016             break;
1017           if (cmp == 0)
1018             return index;
1019           node = node->next;
1020           index++;
1021         }
1022       while (--high > 0);
1023     }
1024   return (size_t)(-1);
1025 }
1026
1027 static gl_list_node_t
1028 gl_linked_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar,
1029                           const void *elt)
1030 {
1031   gl_list_node_t node;
1032
1033   for (node = list->root.next; node != &list->root; node = node->next)
1034     if (compar (node->value, elt) >= 0)
1035       return gl_linked_add_before (list, node, elt);
1036   return gl_linked_add_last (list, elt);
1037 }
1038
1039 static bool
1040 gl_linked_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
1041                              const void *elt)
1042 {
1043   gl_list_node_t node;
1044
1045   for (node = list->root.next; node != &list->root; node = node->next)
1046     {
1047       int cmp = compar (node->value, elt);
1048
1049       if (cmp > 0)
1050         break;
1051       if (cmp == 0)
1052         return gl_linked_remove_node (list, node);
1053     }
1054   return false;
1055 }