lib/gl_anylinked_list2.h

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