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