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 =
  47     (struct gl_list_impl *) xmalloc (sizeof (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.allow_duplicates = allow_duplicates;
  53 #if WITH_HASHTABLE
  54   list->table_size = 11;
  55   list->table =
  56     (gl_hash_entry_t *) xzalloc (list->table_size * sizeof (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                   bool allow_duplicates,
  70                   size_t count, const void **contents)
  71 {
  72   struct gl_list_impl *list =
  73     (struct gl_list_impl *) xmalloc (sizeof (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.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 =
  87       (gl_hash_entry_t *) xzalloc (list->table_size * sizeof (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 =
  95         (struct gl_list_node_impl *)
  96         xmalloc (sizeof (struct gl_list_node_impl));
  97
  98       node->value = *contents;
  99 #if WITH_HASHTABLE
 100       node->h.hashcode =
 101         (list->base.hashcode_fn != NULL
 102          ? list->base.hashcode_fn (node->value)
 103          : (size_t)(uintptr_t) node->value);
 104
 105       /* Add node to the hash table.  */
 106       add_to_bucket (list, node);
 107 #endif
 108
 109       /* Add node to the list.  */
 110       node->prev = tail;
 111       tail->next = node;
 112       tail = node;
 113     }
 114   tail->next = &list->root;
 115   list->root.prev = tail;
 116
 117   return list;
 118 }
 119
 120 static size_t
 121 gl_linked_size (gl_list_t list)
 122 {
 123   return list->count;
 124 }
 125
 126 static const void *
 127 gl_linked_node_value (gl_list_t list, gl_list_node_t node)
 128 {
 129   return node->value;
 130 }
 131
 132 static gl_list_node_t
 133 gl_linked_next_node (gl_list_t list, gl_list_node_t node)
 134 {
 135   return (node->next != &list->root ? node->next : NULL);
 136 }
 137
 138 static gl_list_node_t
 139 gl_linked_previous_node (gl_list_t list, gl_list_node_t node)
 140 {
 141   return (node->prev != &list->root ? node->prev : NULL);
 142 }
 143
 144 static const void *
 145 gl_linked_get_at (gl_list_t list, size_t position)
 146 {
 147   size_t count = list->count;
 148   gl_list_node_t node;
 149
 150   if (!(position < count))
 151     /* Invalid argument.  */
 152     abort ();
 153   /* Here we know count > 0.  */
 154   if (position <= ((count - 1) / 2))
 155     {
 156       node = list->root.next;
 157       for (; position > 0; position--)
 158         node = node->next;
 159     }
 160   else
 161     {
 162       position = count - 1 - position;
 163       node = list->root.prev;
 164       for (; position > 0; position--)
 165         node = node->prev;
 166     }
 167   return node->value;
 168 }
 169
 170 static gl_list_node_t
 171 gl_linked_set_at (gl_list_t list, size_t position, const void *elt)
 172 {
 173   size_t count = list->count;
 174   gl_list_node_t node;
 175
 176   if (!(position < count))
 177     /* Invalid argument.  */
 178     abort ();
 179   /* Here we know count > 0.  */
 180   if (position <= ((count - 1) / 2))
 181     {
 182       node = list->root.next;
 183       for (; position > 0; position--)
 184         node = node->next;
 185     }
 186   else
 187     {
 188       position = count - 1 - position;
 189       node = list->root.prev;
 190       for (; position > 0; position--)
 191         node = node->prev;
 192     }
 193 #if WITH_HASHTABLE
 194   if (elt != node->value)
 195     {
 196       size_t new_hashcode =
 197         (list->base.hashcode_fn != NULL
 198          ? list->base.hashcode_fn (elt)
 199          : (size_t)(uintptr_t) elt);
 200
 201       if (new_hashcode != node->h.hashcode)
 202         {
 203           remove_from_bucket (list, node);
 204           node->value = elt;
 205           node->h.hashcode = new_hashcode;
 206           add_to_bucket (list, node);
 207         }
 208       else
 209         node->value = elt;
 210     }
 211 #else
 212   node->value = elt;
 213 #endif
 214   return node;
 215 }
 216
 217 static gl_list_node_t
 218 gl_linked_search (gl_list_t list, const void *elt)
 219 {
 220 #if WITH_HASHTABLE
 221   size_t hashcode =
 222     (list->base.hashcode_fn != NULL
 223      ? list->base.hashcode_fn (elt)
 224      : (size_t)(uintptr_t) elt);
 225   size_t index = hashcode % list->table_size;
 226   gl_listelement_equals_fn equals = list->base.equals_fn;
 227
 228   if (!list->base.allow_duplicates)
 229     {
 230       /* Look for the first match in the hash bucket.  */
 231       gl_list_node_t node;
 232
 233       for (node = (gl_list_node_t) list->table[index];
 234            node != NULL;
 235            node = (gl_list_node_t) node->h.hash_next)
 236         if (node->h.hashcode == hashcode
 237             && (equals != NULL
 238                 ? equals (elt, node->value)
 239                 : elt == node->value))
 240           return node;
 241       return NULL;
 242     }
 243   else
 244     {
 245       /* Look whether there is more than one match in the hash bucket.  */
 246       bool multiple_matches = false;
 247       gl_list_node_t first_match = NULL;
 248       gl_list_node_t node;
 249
 250       for (node = (gl_list_node_t) list->table[index];
 251            node != NULL;
 252            node = (gl_list_node_t) node->h.hash_next)
 253         if (node->h.hashcode == hashcode
 254             && (equals != NULL
 255                 ? equals (elt, node->value)
 256                 : elt == node->value))
 257           {
 258             if (first_match == NULL)
 259               first_match = node;
 260             else
 261               {
 262                 multiple_matches = true;
 263                 break;
 264               }
 265           }
 266       if (!multiple_matches)
 267         return first_match;
 268       else
 269         {
 270           /* We need the match with the smallest index.  But we don't have
 271              a fast mapping node -> index.  So we have to walk the list.  */
 272           for (node = list->root.next; node != &list->root; node = node->next)
 273             if (node->h.hashcode == hashcode
 274                 && (equals != NULL
 275                     ? equals (elt, node->value)
 276                     : elt == node->value))
 277               return node;
 278           /* We know there are at least two matches.  */
 279           abort ();
 280         }
 281     }
 282 #else
 283   gl_listelement_equals_fn equals = list->base.equals_fn;
 284   gl_list_node_t node;
 285
 286   if (equals != NULL)
 287     {
 288       for (node = list->root.next; node != &list->root; node = node->next)
 289         if (equals (elt, node->value))
 290           return node;
 291     }
 292   else
 293     {
 294       for (node = list->root.next; node != &list->root; node = node->next)
 295         if (elt == node->value)
 296           return node;
 297     }
 298   return NULL;
 299 #endif
 300 }
 301
 302 static size_t
 303 gl_linked_indexof (gl_list_t list, const void *elt)
 304 {
 305 #if WITH_HASHTABLE
 306   /* Here the hash table doesn't help much.  It only allows us to minimize
 307      the number of equals() calls, by looking up first the node and then
 308      its index.  */
 309   size_t hashcode =
 310     (list->base.hashcode_fn != NULL
 311      ? list->base.hashcode_fn (elt)
 312      : (size_t)(uintptr_t) elt);
 313   size_t index = hashcode % list->table_size;
 314   gl_listelement_equals_fn equals = list->base.equals_fn;
 315   gl_list_node_t node;
 316
 317   /* First step: Look up the node.  */
 318   if (!list->base.allow_duplicates)
 319     {
 320       /* Look for the first match in the hash bucket.  */
 321       for (node = (gl_list_node_t) list->table[index];
 322            node != NULL;
 323            node = (gl_list_node_t) node->h.hash_next)
 324         if (node->h.hashcode == hashcode
 325             && (equals != NULL
 326                 ? equals (elt, node->value)
 327                 : elt == node->value))
 328           break;
 329     }
 330   else
 331     {
 332       /* Look whether there is more than one match in the hash bucket.  */
 333       bool multiple_matches = false;
 334       gl_list_node_t first_match = NULL;
 335
 336       for (node = (gl_list_node_t) list->table[index];
 337            node != NULL;
 338            node = (gl_list_node_t) node->h.hash_next)
 339         if (node->h.hashcode == hashcode
 340             && (equals != NULL
 341                 ? equals (elt, node->value)
 342                 : elt == node->value))
 343           {
 344             if (first_match == NULL)
 345               first_match = node;
 346             else
 347               {
 348                 multiple_matches = true;
 349                 break;
 350               }
 351           }
 352       if (multiple_matches)
 353         {
 354           /* We need the match with the smallest index.  But we don't have
 355              a fast mapping node -> index.  So we have to walk the list.  */
 356           size_t index;
 357
 358           for (node = list->root.next, index = 0;
 359                node != &list->root;
 360                node = node->next, index++)
 361             if (node->h.hashcode == hashcode
 362                 && (equals != NULL
 363                     ? equals (elt, node->value)
 364                     : elt == node->value))
 365               return index;
 366           /* We know there are at least two matches.  */
 367           abort ();
 368         }
 369       node = first_match;
 370     }
 371
 372   /* Second step: Look up the index of the node.  */
 373   if (node == NULL)
 374     return (size_t)(-1);
 375   else
 376     {
 377       size_t index = 0;
 378
 379       for (; node->prev != &list->root; node = node->prev)
 380         index++;
 381
 382       return index;
 383     }
 384 #else
 385   gl_listelement_equals_fn equals = list->base.equals_fn;
 386   gl_list_node_t node;
 387
 388   if (equals != NULL)
 389     {
 390       size_t index;
 391       for (node = list->root.next, index = 0;
 392            node != &list->root;
 393            node = node->next, index++)
 394         if (equals (elt, node->value))
 395           return index;
 396     }
 397   else
 398     {
 399       size_t index;
 400       for (node = list->root.next, index = 0;
 401            node != &list->root;
 402            node = node->next, index++)
 403         if (elt == node->value)
 404           return index;
 405     }
 406   return (size_t)(-1);
 407 #endif
 408 }
 409
 410 static gl_list_node_t
 411 gl_linked_add_first (gl_list_t list, const void *elt)
 412 {
 413   gl_list_node_t node =
 414     (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
 415
 416   ASYNCSAFE(const void *) node->value = elt;
 417 #if WITH_HASHTABLE
 418   node->h.hashcode =
 419     (list->base.hashcode_fn != NULL
 420      ? list->base.hashcode_fn (node->value)
 421      : (size_t)(uintptr_t) node->value);
 422
 423   /* Add node to the hash table.  */
 424   add_to_bucket (list, node);
 425 #endif
 426
 427   /* Add node to the list.  */
 428   node->prev = &list->root;
 429   ASYNCSAFE(gl_list_node_t) node->next = list->root.next;
 430   node->next->prev = node;
 431   ASYNCSAFE(gl_list_node_t) list->root.next = node;
 432   list->count++;
 433
 434 #if WITH_HASHTABLE
 435   hash_resize_after_add (list);
 436 #endif
 437
 438   return node;
 439 }
 440
 441 static gl_list_node_t
 442 gl_linked_add_last (gl_list_t list, const void *elt)
 443 {
 444   gl_list_node_t node =
 445     (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
 446
 447   ASYNCSAFE(const void *) node->value = elt;
 448 #if WITH_HASHTABLE
 449   node->h.hashcode =
 450     (list->base.hashcode_fn != NULL
 451      ? list->base.hashcode_fn (node->value)
 452      : (size_t)(uintptr_t) node->value);
 453
 454   /* Add node to the hash table.  */
 455   add_to_bucket (list, node);
 456 #endif
 457
 458   /* Add node to the list.  */
 459   ASYNCSAFE(gl_list_node_t) node->next = &list->root;
 460   node->prev = list->root.prev;
 461   ASYNCSAFE(gl_list_node_t) node->prev->next = node;
 462   list->root.prev = node;
 463   list->count++;
 464
 465 #if WITH_HASHTABLE
 466   hash_resize_after_add (list);
 467 #endif
 468
 469   return node;
 470 }
 471
 472 static gl_list_node_t
 473 gl_linked_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
 474 {
 475   gl_list_node_t new_node =
 476     (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
 477
 478   ASYNCSAFE(const void *) new_node->value = elt;
 479 #if WITH_HASHTABLE
 480   new_node->h.hashcode =
 481     (list->base.hashcode_fn != NULL
 482      ? list->base.hashcode_fn (new_node->value)
 483      : (size_t)(uintptr_t) new_node->value);
 484
 485   /* Add new_node to the hash table.  */
 486   add_to_bucket (list, new_node);
 487 #endif
 488
 489   /* Add new_node to the list.  */
 490   ASYNCSAFE(gl_list_node_t) new_node->next = node;
 491   new_node->prev = node->prev;
 492   ASYNCSAFE(gl_list_node_t) new_node->prev->next = new_node;
 493   node->prev = new_node;
 494   list->count++;
 495
 496 #if WITH_HASHTABLE
 497   hash_resize_after_add (list);
 498 #endif
 499
 500   return new_node;
 501 }
 502
 503 static gl_list_node_t
 504 gl_linked_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
 505 {
 506   gl_list_node_t new_node =
 507     (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
 508
 509   ASYNCSAFE(const void *) new_node->value = elt;
 510 #if WITH_HASHTABLE
 511   new_node->h.hashcode =
 512     (list->base.hashcode_fn != NULL
 513      ? list->base.hashcode_fn (new_node->value)
 514      : (size_t)(uintptr_t) new_node->value);
 515
 516   /* Add new_node to the hash table.  */
 517   add_to_bucket (list, new_node);
 518 #endif
 519
 520   /* Add new_node to the list.  */
 521   new_node->prev = node;
 522   ASYNCSAFE(gl_list_node_t) new_node->next = node->next;
 523   new_node->next->prev = new_node;
 524   ASYNCSAFE(gl_list_node_t) node->next = new_node;
 525   list->count++;
 526
 527 #if WITH_HASHTABLE
 528   hash_resize_after_add (list);
 529 #endif
 530
 531   return new_node;
 532 }
 533
 534 static gl_list_node_t
 535 gl_linked_add_at (gl_list_t list, size_t position, const void *elt)
 536 {
 537   size_t count = list->count;
 538   gl_list_node_t new_node;
 539
 540   if (!(position <= count))
 541     /* Invalid argument.  */
 542     abort ();
 543
 544   new_node =
 545     (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
 546   ASYNCSAFE(const void *) new_node->value = elt;
 547 #if WITH_HASHTABLE
 548   new_node->h.hashcode =
 549     (list->base.hashcode_fn != NULL
 550      ? list->base.hashcode_fn (new_node->value)
 551      : (size_t)(uintptr_t) new_node->value);
 552
 553   /* Add new_node to the hash table.  */
 554   add_to_bucket (list, new_node);
 555 #endif
 556
 557   /* Add new_node to the list.  */
 558   if (position <= (count / 2))
 559     {
 560       gl_list_node_t node;
 561
 562       node = &list->root;
 563       for (; position > 0; position--)
 564         node = node->next;
 565       new_node->prev = node;
 566       ASYNCSAFE(gl_list_node_t) new_node->next = node->next;
 567       new_node->next->prev = new_node;
 568       ASYNCSAFE(gl_list_node_t) node->next = new_node;
 569     }
 570   else
 571     {
 572       gl_list_node_t node;
 573
 574       position = count - position;
 575       node = &list->root;
 576       for (; position > 0; position--)
 577         node = node->prev;
 578       ASYNCSAFE(gl_list_node_t) new_node->next = node;
 579       new_node->prev = node->prev;
 580       ASYNCSAFE(gl_list_node_t) new_node->prev->next = new_node;
 581       node->prev = new_node;
 582     }
 583   list->count++;
 584
 585 #if WITH_HASHTABLE
 586   hash_resize_after_add (list);
 587 #endif
 588
 589   return new_node;
 590 }
 591
 592 static bool
 593 gl_linked_remove_node (gl_list_t list, gl_list_node_t node)
 594 {
 595   gl_list_node_t prev;
 596   gl_list_node_t next;
 597
 598 #if WITH_HASHTABLE
 599   /* Remove node from the hash table.  */
 600   remove_from_bucket (list, node);
 601 #endif
 602
 603   /* Remove node from the list.  */
 604   prev = node->prev;
 605   next = node->next;
 606
 607   ASYNCSAFE(gl_list_node_t) prev->next = next;
 608   next->prev = prev;
 609   list->count--;
 610
 611   free (node);
 612   return true;
 613 }
 614
 615 static bool
 616 gl_linked_remove_at (gl_list_t list, size_t position)
 617 {
 618   size_t count = list->count;
 619   gl_list_node_t removed_node;
 620
 621   if (!(position < count))
 622     /* Invalid argument.  */
 623     abort ();
 624   /* Here we know count > 0.  */
 625   if (position <= ((count - 1) / 2))
 626     {
 627       gl_list_node_t node;
 628       gl_list_node_t after_removed;
 629
 630       node = &list->root;
 631       for (; position > 0; position--)
 632         node = node->next;
 633       removed_node = node->next;
 634       after_removed = node->next->next;
 635       ASYNCSAFE(gl_list_node_t) node->next = after_removed;
 636       after_removed->prev = node;
 637     }
 638   else
 639     {
 640       gl_list_node_t node;
 641       gl_list_node_t before_removed;
 642
 643       position = count - 1 - position;
 644       node = &list->root;
 645       for (; position > 0; position--)
 646         node = node->prev;
 647       removed_node = node->prev;
 648       before_removed = node->prev->prev;
 649       node->prev = before_removed;
 650       ASYNCSAFE(gl_list_node_t) before_removed->next = node;
 651     }
 652 #if WITH_HASHTABLE
 653   remove_from_bucket (list, removed_node);
 654 #endif
 655   list->count--;
 656
 657   free (removed_node);
 658   return true;
 659 }
 660
 661 static bool
 662 gl_linked_remove (gl_list_t list, const void *elt)
 663 {
 664   gl_list_node_t node = gl_linked_search (list, elt);
 665
 666   if (node != NULL)
 667     return gl_linked_remove_node (list, node);
 668   else
 669     return false;
 670 }
 671
 672 static void
 673 gl_linked_list_free (gl_list_t list)
 674 {
 675   gl_list_node_t node;
 676
 677   for (node = list->root.next; node != &list->root; )
 678     {
 679       gl_list_node_t next = node->next;
 680       free (node);
 681       node = next;
 682     }
 683 #if WITH_HASHTABLE
 684   free (list->table);
 685 #endif
 686   free (list);
 687 }
 688
 689 /* --------------------- gl_list_iterator_t Data Type --------------------- */
 690
 691 static gl_list_iterator_t
 692 gl_linked_iterator (gl_list_t list)
 693 {
 694   gl_list_iterator_t result;
 695
 696   result.vtable = list->base.vtable;
 697   result.list = list;
 698   result.p = list->root.next;
 699   result.q = &list->root;
 700
 701   return result;
 702 }
 703
 704 static gl_list_iterator_t
 705 gl_linked_iterator_from_to (gl_list_t list,
 706                             size_t start_index, size_t end_index)
 707 {
 708   gl_list_iterator_t result;
 709   size_t n1, n2, n3;
 710
 711   if (!(start_index <= end_index && end_index <= list->count))
 712     /* Invalid arguments.  */
 713     abort ();
 714   result.vtable = list->base.vtable;
 715   result.list = list;
 716   n1 = start_index;
 717   n2 = end_index - start_index;
 718   n3 = list->count - end_index;
 719   /* Find the maximum among n1, n2, n3, so as to reduce the number of
 720      loop iterations to n1 + n2 + n3 - max(n1,n2,n3).  */
 721   if (n1 > n2 && n1 > n3)
 722     {
 723       /* n1 is the maximum, use n2 and n3.  */
 724       gl_list_node_t node;
 725       size_t i;
 726
 727       node = &list->root;
 728       for (i = n3; i > 0; i--)
 729         node = node->prev;
 730       result.q = node;
 731       for (i = n2; i > 0; i--)
 732         node = node->prev;
 733       result.p = node;
 734     }
 735   else if (n2 > n3)
 736     {
 737       /* n2 is the maximum, use n1 and n3.  */
 738       gl_list_node_t node;
 739       size_t i;
 740
 741       node = list->root.next;
 742       for (i = n1; i > 0; i--)
 743         node = node->next;
 744       result.p = node;
 745
 746       node = &list->root;
 747       for (i = n3; i > 0; i--)
 748         node = node->prev;
 749       result.q = node;
 750     }
 751   else
 752     {
 753       /* n3 is the maximum, use n1 and n2.  */
 754       gl_list_node_t node;
 755       size_t i;
 756
 757       node = list->root.next;
 758       for (i = n1; i > 0; i--)
 759         node = node->next;
 760       result.p = node;
 761       for (i = n2; i > 0; i--)
 762         node = node->next;
 763       result.q = node;
 764     }
 765
 766   return result;
 767 }
 768
 769 static bool
 770 gl_linked_iterator_next (gl_list_iterator_t *iterator,
 771                          const void **eltp, gl_list_node_t *nodep)
 772 {
 773   if (iterator->p != iterator->q)
 774     {
 775       gl_list_node_t node = (gl_list_node_t) iterator->p;
 776       *eltp = node->value;
 777       if (nodep != NULL)
 778         *nodep = node;
 779       iterator->p = node->next;
 780       return true;
 781     }
 782   else
 783     return false;
 784 }
 785
 786 static void
 787 gl_linked_iterator_free (gl_list_iterator_t *iterator)
 788 {
 789 }
 790
 791 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
 792
 793 static gl_list_node_t
 794 gl_linked_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
 795                              const void *elt)
 796 {
 797   gl_list_node_t node;
 798
 799   for (node = list->root.next; node != &list->root; node = node->next)
 800     {
 801       int cmp = compar (node->value, elt);
 802
 803       if (cmp > 0)
 804         break;
 805       if (cmp == 0)
 806         return node;
 807     }
 808   return NULL;
 809 }
 810
 811 static size_t
 812 gl_linked_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
 813                               const void *elt)
 814 {
 815   gl_list_node_t node;
 816   size_t index;
 817
 818   for (node = list->root.next, index = 0;
 819        node != &list->root;
 820        node = node->next, index++)
 821     {
 822       int cmp = compar (node->value, elt);
 823
 824       if (cmp > 0)
 825         break;
 826       if (cmp == 0)
 827         return index;
 828     }
 829   return (size_t)(-1);
 830 }
 831
 832 static gl_list_node_t
 833 gl_linked_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar,
 834                           const void *elt)
 835 {
 836   gl_list_node_t node;
 837
 838   for (node = list->root.next; node != &list->root; node = node->next)
 839     if (compar (node->value, elt) >= 0)
 840       return gl_linked_add_before (list, node, elt);
 841   return gl_linked_add_last (list, elt);
 842 }
 843
 844 static bool
 845 gl_linked_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
 846                              const void *elt)
 847 {
 848   gl_list_node_t node;
 849
 850   for (node = list->root.next; node != &list->root; node = node->next)
 851     {
 852       int cmp = compar (node->value, elt);
 853
 854       if (cmp > 0)
 855         break;
 856       if (cmp == 0)
 857         return gl_linked_remove_node (list, node);
 858     }
 859   return false;
 860 }