lib/gl_anylinked_list2.h

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