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