lib/gl_anylinked_list2.h

   1 /* Sequential list data type implemented by a linked list.
   2    Copyright (C) 2006-2021 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 gl_list_node_t _GL_ATTRIBUTE_PURE
 233 gl_linked_first_node (gl_list_t list)
 234 {
 235   if (list->count > 0)
 236     return list->root.next;
 237   else
 238     return NULL;
 239 }
 240
 241 static gl_list_node_t _GL_ATTRIBUTE_PURE
 242 gl_linked_last_node (gl_list_t list)
 243 {
 244   if (list->count > 0)
 245     return list->root.prev;
 246   else
 247     return NULL;
 248 }
 249
 250 static const void * _GL_ATTRIBUTE_PURE
 251 gl_linked_get_at (gl_list_t list, size_t position)
 252 {
 253   size_t count = list->count;
 254   gl_list_node_t node;
 255
 256   if (!(position < count))
 257     /* Invalid argument.  */
 258     abort ();
 259   /* Here we know count > 0.  */
 260   if (position <= ((count - 1) / 2))
 261     {
 262       node = list->root.next;
 263       for (; position > 0; position--)
 264         node = node->next;
 265     }
 266   else
 267     {
 268       position = count - 1 - position;
 269       node = list->root.prev;
 270       for (; position > 0; position--)
 271         node = node->prev;
 272     }
 273   return node->value;
 274 }
 275
 276 static gl_list_node_t
 277 gl_linked_nx_set_at (gl_list_t list, size_t position, const void *elt)
 278 {
 279   size_t count = list->count;
 280   gl_list_node_t node;
 281
 282   if (!(position < count))
 283     /* Invalid argument.  */
 284     abort ();
 285   /* Here we know count > 0.  */
 286   if (position <= ((count - 1) / 2))
 287     {
 288       node = list->root.next;
 289       for (; position > 0; position--)
 290         node = node->next;
 291     }
 292   else
 293     {
 294       position = count - 1 - position;
 295       node = list->root.prev;
 296       for (; position > 0; position--)
 297         node = node->prev;
 298     }
 299 #if WITH_HASHTABLE
 300   if (elt != node->value)
 301     {
 302       size_t new_hashcode =
 303         (list->base.hashcode_fn != NULL
 304          ? list->base.hashcode_fn (elt)
 305          : (size_t)(uintptr_t) elt);
 306
 307       if (new_hashcode != node->h.hashcode)
 308         {
 309           remove_from_bucket (list, node);
 310           node->value = elt;
 311           node->h.hashcode = new_hashcode;
 312           if (add_to_bucket (list, node) < 0)
 313             {
 314               /* Out of memory.  We removed node from a bucket but cannot add
 315                  it to another bucket.  In order to avoid inconsistencies, we
 316                  must remove node entirely from the list.  */
 317               gl_list_node_t before_removed = node->prev;
 318               gl_list_node_t after_removed = node->next;
 319               ASYNCSAFE(gl_list_node_t) before_removed->next = after_removed;
 320               after_removed->prev = before_removed;
 321               list->count--;
 322               free (node);
 323               return NULL;
 324             }
 325         }
 326       else
 327         node->value = elt;
 328     }
 329 #else
 330   node->value = elt;
 331 #endif
 332   return node;
 333 }
 334
 335 static gl_list_node_t _GL_ATTRIBUTE_PURE
 336 gl_linked_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
 337                           const void *elt)
 338 {
 339   size_t count = list->count;
 340
 341   if (!(start_index <= end_index && end_index <= count))
 342     /* Invalid arguments.  */
 343     abort ();
 344   {
 345 #if WITH_HASHTABLE
 346     size_t hashcode =
 347       (list->base.hashcode_fn != NULL
 348        ? list->base.hashcode_fn (elt)
 349        : (size_t)(uintptr_t) elt);
 350     size_t bucket = hashcode % list->table_size;
 351     gl_listelement_equals_fn equals = list->base.equals_fn;
 352
 353     if (!list->base.allow_duplicates)
 354       {
 355         /* Look for the first match in the hash bucket.  */
 356         gl_list_node_t found = NULL;
 357         gl_list_node_t node;
 358
 359         for (node = (gl_list_node_t) list->table[bucket];
 360              node != NULL;
 361              node = (gl_list_node_t) node->h.hash_next)
 362           if (node->h.hashcode == hashcode
 363               && (equals != NULL
 364                   ? equals (elt, node->value)
 365                   : elt == node->value))
 366             {
 367               found = node;
 368               break;
 369             }
 370         if (start_index > 0)
 371           /* Look whether found's index is < start_index.  */
 372           for (node = list->root.next; ; node = node->next)
 373             {
 374               if (node == found)
 375                 return NULL;
 376               if (--start_index == 0)
 377                 break;
 378             }
 379         if (end_index < count)
 380           /* Look whether found's index is >= end_index.  */
 381           {
 382             end_index = count - end_index;
 383             for (node = list->root.prev; ; node = node->prev)
 384               {
 385                 if (node == found)
 386                   return NULL;
 387                 if (--end_index == 0)
 388                   break;
 389               }
 390           }
 391         return found;
 392       }
 393     else
 394       {
 395         /* Look whether there is more than one match in the hash bucket.  */
 396         bool multiple_matches = false;
 397         gl_list_node_t first_match = NULL;
 398         gl_list_node_t node;
 399
 400         for (node = (gl_list_node_t) list->table[bucket];
 401              node != NULL;
 402              node = (gl_list_node_t) node->h.hash_next)
 403           if (node->h.hashcode == hashcode
 404               && (equals != NULL
 405                   ? equals (elt, node->value)
 406                   : elt == node->value))
 407             {
 408               if (first_match == NULL)
 409                 first_match = node;
 410               else
 411                 {
 412                   multiple_matches = true;
 413                   break;
 414                 }
 415             }
 416         if (multiple_matches)
 417           {
 418             /* We need the match with the smallest index.  But we don't have
 419                a fast mapping node -> index.  So we have to walk the list.  */
 420             end_index -= start_index;
 421             node = list->root.next;
 422             for (; start_index > 0; start_index--)
 423               node = node->next;
 424
 425             for (;
 426                  end_index > 0;
 427                  node = node->next, end_index--)
 428               if (node->h.hashcode == hashcode
 429                   && (equals != NULL
 430                       ? equals (elt, node->value)
 431                       : elt == node->value))
 432                 return node;
 433             /* The matches must have all been at indices < start_index or
 434                >= end_index.  */
 435             return NULL;
 436           }
 437         else
 438           {
 439             if (start_index > 0)
 440               /* Look whether first_match's index is < start_index.  */
 441               for (node = list->root.next; node != &list->root; node = node->next)
 442                 {
 443                   if (node == first_match)
 444                     return NULL;
 445                   if (--start_index == 0)
 446                     break;
 447                 }
 448             if (end_index < list->count)
 449               /* Look whether first_match's index is >= end_index.  */
 450               {
 451                 end_index = list->count - end_index;
 452                 for (node = list->root.prev; ; node = node->prev)
 453                   {
 454                     if (node == first_match)
 455                       return NULL;
 456                     if (--end_index == 0)
 457                       break;
 458                   }
 459               }
 460             return first_match;
 461           }
 462       }
 463 #else
 464     gl_listelement_equals_fn equals = list->base.equals_fn;
 465     gl_list_node_t node = list->root.next;
 466
 467     end_index -= start_index;
 468     for (; start_index > 0; start_index--)
 469       node = node->next;
 470
 471     if (equals != NULL)
 472       {
 473         for (; end_index > 0; node = node->next, end_index--)
 474           if (equals (elt, node->value))
 475             return node;
 476       }
 477     else
 478       {
 479         for (; end_index > 0; node = node->next, end_index--)
 480           if (elt == node->value)
 481             return node;
 482       }
 483     return NULL;
 484 #endif
 485   }
 486 }
 487
 488 static size_t _GL_ATTRIBUTE_PURE
 489 gl_linked_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
 490                            const void *elt)
 491 {
 492   size_t count = list->count;
 493
 494   if (!(start_index <= end_index && end_index <= count))
 495     /* Invalid arguments.  */
 496     abort ();
 497   {
 498 #if WITH_HASHTABLE
 499     /* Here the hash table doesn't help much.  It only allows us to minimize
 500        the number of equals() calls, by looking up first the node and then
 501        its index.  */
 502     size_t hashcode =
 503       (list->base.hashcode_fn != NULL
 504        ? list->base.hashcode_fn (elt)
 505        : (size_t)(uintptr_t) elt);
 506     size_t bucket = hashcode % list->table_size;
 507     gl_listelement_equals_fn equals = list->base.equals_fn;
 508     gl_list_node_t node;
 509
 510     /* First step: Look up the node.  */
 511     if (!list->base.allow_duplicates)
 512       {
 513         /* Look for the first match in the hash bucket.  */
 514         for (node = (gl_list_node_t) list->table[bucket];
 515              node != NULL;
 516              node = (gl_list_node_t) node->h.hash_next)
 517           if (node->h.hashcode == hashcode
 518               && (equals != NULL
 519                   ? equals (elt, node->value)
 520                   : elt == node->value))
 521             break;
 522       }
 523     else
 524       {
 525         /* Look whether there is more than one match in the hash bucket.  */
 526         bool multiple_matches = false;
 527         gl_list_node_t first_match = NULL;
 528
 529         for (node = (gl_list_node_t) list->table[bucket];
 530              node != NULL;
 531              node = (gl_list_node_t) node->h.hash_next)
 532           if (node->h.hashcode == hashcode
 533               && (equals != NULL
 534                   ? equals (elt, node->value)
 535                   : elt == node->value))
 536             {
 537               if (first_match == NULL)
 538                 first_match = node;
 539               else
 540                 {
 541                   multiple_matches = true;
 542                   break;
 543                 }
 544             }
 545         if (multiple_matches)
 546           {
 547             /* We need the match with the smallest index.  But we don't have
 548                a fast mapping node -> index.  So we have to walk the list.  */
 549             size_t index;
 550
 551             index = start_index;
 552             node = list->root.next;
 553             for (; start_index > 0; start_index--)
 554               node = node->next;
 555
 556             for (;
 557                  index < end_index;
 558                  node = node->next, index++)
 559               if (node->h.hashcode == hashcode
 560                   && (equals != NULL
 561                       ? equals (elt, node->value)
 562                       : elt == node->value))
 563                 return index;
 564             /* The matches must have all been at indices < start_index or
 565                >= end_index.  */
 566             return (size_t)(-1);
 567           }
 568         node = first_match;
 569       }
 570
 571     /* Second step: Look up the index of the node.  */
 572     if (node == NULL)
 573       return (size_t)(-1);
 574     else
 575       {
 576         size_t index = 0;
 577
 578         for (; node->prev != &list->root; node = node->prev)
 579           index++;
 580
 581         if (index >= start_index && index < end_index)
 582           return index;
 583         else
 584           return (size_t)(-1);
 585       }
 586 #else
 587     gl_listelement_equals_fn equals = list->base.equals_fn;
 588     size_t index = start_index;
 589     gl_list_node_t node = list->root.next;
 590
 591     for (; start_index > 0; start_index--)
 592       node = node->next;
 593
 594     if (equals != NULL)
 595       {
 596         for (;
 597              index < end_index;
 598              node = node->next, index++)
 599           if (equals (elt, node->value))
 600             return index;
 601       }
 602     else
 603       {
 604         for (;
 605              index < end_index;
 606              node = node->next, index++)
 607           if (elt == node->value)
 608             return index;
 609       }
 610     return (size_t)(-1);
 611 #endif
 612   }
 613 }
 614
 615 static gl_list_node_t
 616 gl_linked_nx_add_first (gl_list_t list, const void *elt)
 617 {
 618   gl_list_node_t node =
 619     (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
 620
 621   if (node == NULL)
 622     return NULL;
 623
 624   ASYNCSAFE(const void *) node->value = elt;
 625 #if WITH_HASHTABLE
 626   node->h.hashcode =
 627     (list->base.hashcode_fn != NULL
 628      ? list->base.hashcode_fn (node->value)
 629      : (size_t)(uintptr_t) node->value);
 630
 631   /* Add node to the hash table.  */
 632   if (add_to_bucket (list, node) < 0)
 633     {
 634       free (node);
 635       return NULL;
 636     }
 637 #endif
 638
 639   /* Add node to the list.  */
 640   node->prev = &list->root;
 641   ASYNCSAFE(gl_list_node_t) node->next = list->root.next;
 642   node->next->prev = node;
 643   ASYNCSAFE(gl_list_node_t) list->root.next = node;
 644   list->count++;
 645
 646 #if WITH_HASHTABLE
 647   hash_resize_after_add (list);
 648 #endif
 649
 650   return node;
 651 }
 652
 653 static gl_list_node_t
 654 gl_linked_nx_add_last (gl_list_t list, const void *elt)
 655 {
 656   gl_list_node_t node =
 657     (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
 658
 659   if (node == NULL)
 660     return NULL;
 661
 662   ASYNCSAFE(const void *) node->value = elt;
 663 #if WITH_HASHTABLE
 664   node->h.hashcode =
 665     (list->base.hashcode_fn != NULL
 666      ? list->base.hashcode_fn (node->value)
 667      : (size_t)(uintptr_t) node->value);
 668
 669   /* Add node to the hash table.  */
 670   if (add_to_bucket (list, node) < 0)
 671     {
 672       free (node);
 673       return NULL;
 674     }
 675 #endif
 676
 677   /* Add node to the list.  */
 678   ASYNCSAFE(gl_list_node_t) node->next = &list->root;
 679   node->prev = list->root.prev;
 680   ASYNCSAFE(gl_list_node_t) node->prev->next = node;
 681   list->root.prev = node;
 682   list->count++;
 683
 684 #if WITH_HASHTABLE
 685   hash_resize_after_add (list);
 686 #endif
 687
 688   return node;
 689 }
 690
 691 static gl_list_node_t
 692 gl_linked_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
 693 {
 694   gl_list_node_t new_node =
 695     (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
 696
 697   if (new_node == NULL)
 698     return NULL;
 699
 700   ASYNCSAFE(const void *) new_node->value = elt;
 701 #if WITH_HASHTABLE
 702   new_node->h.hashcode =
 703     (list->base.hashcode_fn != NULL
 704      ? list->base.hashcode_fn (new_node->value)
 705      : (size_t)(uintptr_t) new_node->value);
 706
 707   /* Add new_node to the hash table.  */
 708   if (add_to_bucket (list, new_node) < 0)
 709     {
 710       free (new_node);
 711       return NULL;
 712     }
 713 #endif
 714
 715   /* Add new_node to the list.  */
 716   ASYNCSAFE(gl_list_node_t) new_node->next = node;
 717   new_node->prev = node->prev;
 718   ASYNCSAFE(gl_list_node_t) new_node->prev->next = new_node;
 719   node->prev = new_node;
 720   list->count++;
 721
 722 #if WITH_HASHTABLE
 723   hash_resize_after_add (list);
 724 #endif
 725
 726   return new_node;
 727 }
 728
 729 static gl_list_node_t
 730 gl_linked_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
 731 {
 732   gl_list_node_t new_node =
 733     (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
 734
 735   if (new_node == NULL)
 736     return NULL;
 737
 738   ASYNCSAFE(const void *) new_node->value = elt;
 739 #if WITH_HASHTABLE
 740   new_node->h.hashcode =
 741     (list->base.hashcode_fn != NULL
 742      ? list->base.hashcode_fn (new_node->value)
 743      : (size_t)(uintptr_t) new_node->value);
 744
 745   /* Add new_node to the hash table.  */
 746   if (add_to_bucket (list, new_node) < 0)
 747     {
 748       free (new_node);
 749       return NULL;
 750     }
 751 #endif
 752
 753   /* Add new_node to the list.  */
 754   new_node->prev = node;
 755   ASYNCSAFE(gl_list_node_t) new_node->next = node->next;
 756   new_node->next->prev = new_node;
 757   ASYNCSAFE(gl_list_node_t) node->next = new_node;
 758   list->count++;
 759
 760 #if WITH_HASHTABLE
 761   hash_resize_after_add (list);
 762 #endif
 763
 764   return new_node;
 765 }
 766
 767 static gl_list_node_t
 768 gl_linked_nx_add_at (gl_list_t list, size_t position, const void *elt)
 769 {
 770   size_t count = list->count;
 771   gl_list_node_t new_node;
 772
 773   if (!(position <= count))
 774     /* Invalid argument.  */
 775     abort ();
 776
 777   new_node = (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
 778   if (new_node == NULL)
 779     return NULL;
 780
 781   ASYNCSAFE(const void *) new_node->value = elt;
 782 #if WITH_HASHTABLE
 783   new_node->h.hashcode =
 784     (list->base.hashcode_fn != NULL
 785      ? list->base.hashcode_fn (new_node->value)
 786      : (size_t)(uintptr_t) new_node->value);
 787
 788   /* Add new_node to the hash table.  */
 789   if (add_to_bucket (list, new_node) < 0)
 790     {
 791       free (new_node);
 792       return NULL;
 793     }
 794 #endif
 795
 796   /* Add new_node to the list.  */
 797   if (position <= (count / 2))
 798     {
 799       gl_list_node_t node;
 800
 801       node = &list->root;
 802       for (; position > 0; position--)
 803         node = node->next;
 804       new_node->prev = node;
 805       ASYNCSAFE(gl_list_node_t) new_node->next = node->next;
 806       new_node->next->prev = new_node;
 807       ASYNCSAFE(gl_list_node_t) node->next = new_node;
 808     }
 809   else
 810     {
 811       gl_list_node_t node;
 812
 813       position = count - position;
 814       node = &list->root;
 815       for (; position > 0; position--)
 816         node = node->prev;
 817       ASYNCSAFE(gl_list_node_t) new_node->next = node;
 818       new_node->prev = node->prev;
 819       ASYNCSAFE(gl_list_node_t) new_node->prev->next = new_node;
 820       node->prev = new_node;
 821     }
 822   list->count++;
 823
 824 #if WITH_HASHTABLE
 825   hash_resize_after_add (list);
 826 #endif
 827
 828   return new_node;
 829 }
 830
 831 static bool
 832 gl_linked_remove_node (gl_list_t list, gl_list_node_t node)
 833 {
 834   gl_list_node_t prev;
 835   gl_list_node_t next;
 836
 837 #if WITH_HASHTABLE
 838   /* Remove node from the hash table.  */
 839   remove_from_bucket (list, node);
 840 #endif
 841
 842   /* Remove node from the list.  */
 843   prev = node->prev;
 844   next = node->next;
 845
 846   ASYNCSAFE(gl_list_node_t) prev->next = next;
 847   next->prev = prev;
 848   list->count--;
 849
 850   if (list->base.dispose_fn != NULL)
 851     list->base.dispose_fn (node->value);
 852   free (node);
 853   return true;
 854 }
 855
 856 static bool
 857 gl_linked_remove_at (gl_list_t list, size_t position)
 858 {
 859   size_t count = list->count;
 860   gl_list_node_t removed_node;
 861
 862   if (!(position < count))
 863     /* Invalid argument.  */
 864     abort ();
 865   /* Here we know count > 0.  */
 866   if (position <= ((count - 1) / 2))
 867     {
 868       gl_list_node_t node;
 869       gl_list_node_t after_removed;
 870
 871       node = &list->root;
 872       for (; position > 0; position--)
 873         node = node->next;
 874       removed_node = node->next;
 875       after_removed = node->next->next;
 876       ASYNCSAFE(gl_list_node_t) node->next = after_removed;
 877       after_removed->prev = node;
 878     }
 879   else
 880     {
 881       gl_list_node_t node;
 882       gl_list_node_t before_removed;
 883
 884       position = count - 1 - position;
 885       node = &list->root;
 886       for (; position > 0; position--)
 887         node = node->prev;
 888       removed_node = node->prev;
 889       before_removed = node->prev->prev;
 890       node->prev = before_removed;
 891       ASYNCSAFE(gl_list_node_t) before_removed->next = node;
 892     }
 893 #if WITH_HASHTABLE
 894   remove_from_bucket (list, removed_node);
 895 #endif
 896   list->count--;
 897
 898   if (list->base.dispose_fn != NULL)
 899     list->base.dispose_fn (removed_node->value);
 900   free (removed_node);
 901   return true;
 902 }
 903
 904 static bool
 905 gl_linked_remove (gl_list_t list, const void *elt)
 906 {
 907   gl_list_node_t node = gl_linked_search_from_to (list, 0, list->count, elt);
 908
 909   if (node != NULL)
 910     return gl_linked_remove_node (list, node);
 911   else
 912     return false;
 913 }
 914
 915 static void
 916 gl_linked_list_free (gl_list_t list)
 917 {
 918   gl_listelement_dispose_fn dispose = list->base.dispose_fn;
 919   gl_list_node_t node;
 920
 921   for (node = list->root.next; node != &list->root; )
 922     {
 923       gl_list_node_t next = node->next;
 924       if (dispose != NULL)
 925         dispose (node->value);
 926       free (node);
 927       node = next;
 928     }
 929 #if WITH_HASHTABLE
 930   free (list->table);
 931 #endif
 932   free (list);
 933 }
 934
 935 /* --------------------- gl_list_iterator_t Data Type --------------------- */
 936
 937 static gl_list_iterator_t _GL_ATTRIBUTE_PURE
 938 gl_linked_iterator (gl_list_t list)
 939 {
 940   gl_list_iterator_t result;
 941
 942   result.vtable = list->base.vtable;
 943   result.list = list;
 944   result.p = list->root.next;
 945   result.q = &list->root;
 946 #if defined GCC_LINT || defined lint
 947   result.i = 0;
 948   result.j = 0;
 949   result.count = 0;
 950 #endif
 951
 952   return result;
 953 }
 954
 955 static gl_list_iterator_t _GL_ATTRIBUTE_PURE
 956 gl_linked_iterator_from_to (gl_list_t list,
 957                             size_t start_index, size_t end_index)
 958 {
 959   gl_list_iterator_t result;
 960   size_t n1, n2, n3;
 961
 962   if (!(start_index <= end_index && end_index <= list->count))
 963     /* Invalid arguments.  */
 964     abort ();
 965   result.vtable = list->base.vtable;
 966   result.list = list;
 967   n1 = start_index;
 968   n2 = end_index - start_index;
 969   n3 = list->count - end_index;
 970   /* Find the maximum among n1, n2, n3, so as to reduce the number of
 971      loop iterations to n1 + n2 + n3 - max(n1,n2,n3).  */
 972   if (n1 > n2 && n1 > n3)
 973     {
 974       /* n1 is the maximum, use n2 and n3.  */
 975       gl_list_node_t node;
 976       size_t i;
 977
 978       node = &list->root;
 979       for (i = n3; i > 0; i--)
 980         node = node->prev;
 981       result.q = node;
 982       for (i = n2; i > 0; i--)
 983         node = node->prev;
 984       result.p = node;
 985     }
 986   else if (n2 > n3)
 987     {
 988       /* n2 is the maximum, use n1 and n3.  */
 989       gl_list_node_t node;
 990       size_t i;
 991
 992       node = list->root.next;
 993       for (i = n1; i > 0; i--)
 994         node = node->next;
 995       result.p = node;
 996
 997       node = &list->root;
 998       for (i = n3; i > 0; i--)
 999         node = node->prev;
1000       result.q = node;
1001     }
1002   else
1003     {
1004       /* n3 is the maximum, use n1 and n2.  */
1005       gl_list_node_t node;
1006       size_t i;
1007
1008       node = list->root.next;
1009       for (i = n1; i > 0; i--)
1010         node = node->next;
1011       result.p = node;
1012       for (i = n2; i > 0; i--)
1013         node = node->next;
1014       result.q = node;
1015     }
1016
1017 #if defined GCC_LINT || defined lint
1018   result.i = 0;
1019   result.j = 0;
1020   result.count = 0;
1021 #endif
1022
1023   return result;
1024 }
1025
1026 static bool
1027 gl_linked_iterator_next (gl_list_iterator_t *iterator,
1028                          const void **eltp, gl_list_node_t *nodep)
1029 {
1030   if (iterator->p != iterator->q)
1031     {
1032       gl_list_node_t node = (gl_list_node_t) iterator->p;
1033       *eltp = node->value;
1034       if (nodep != NULL)
1035         *nodep = node;
1036       iterator->p = node->next;
1037       return true;
1038     }
1039   else
1040     return false;
1041 }
1042
1043 static void
1044 gl_linked_iterator_free (gl_list_iterator_t *iterator _GL_ATTRIBUTE_MAYBE_UNUSED)
1045 {
1046 }
1047
1048 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
1049
1050 static gl_list_node_t _GL_ATTRIBUTE_PURE
1051 gl_linked_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
1052                              const void *elt)
1053 {
1054   gl_list_node_t node;
1055
1056   for (node = list->root.next; node != &list->root; node = node->next)
1057     {
1058       int cmp = compar (node->value, elt);
1059
1060       if (cmp > 0)
1061         break;
1062       if (cmp == 0)
1063         return node;
1064     }
1065   return NULL;
1066 }
1067
1068 static gl_list_node_t _GL_ATTRIBUTE_PURE
1069 gl_linked_sortedlist_search_from_to (gl_list_t list,
1070                                      gl_listelement_compar_fn compar,
1071                                      size_t low, size_t high,
1072                                      const void *elt)
1073 {
1074   size_t count = list->count;
1075
1076   if (!(low <= high && high <= list->count))
1077     /* Invalid arguments.  */
1078     abort ();
1079
1080   high -= low;
1081   if (high > 0)
1082     {
1083       /* Here we know low < count.  */
1084       size_t position = low;
1085       gl_list_node_t node;
1086
1087       if (position <= ((count - 1) / 2))
1088         {
1089           node = list->root.next;
1090           for (; position > 0; position--)
1091             node = node->next;
1092         }
1093       else
1094         {
1095           position = count - 1 - position;
1096           node = list->root.prev;
1097           for (; position > 0; position--)
1098             node = node->prev;
1099         }
1100
1101       do
1102         {
1103           int cmp = compar (node->value, elt);
1104
1105           if (cmp > 0)
1106             break;
1107           if (cmp == 0)
1108             return node;
1109           node = node->next;
1110         }
1111       while (--high > 0);
1112     }
1113   return NULL;
1114 }
1115
1116 static size_t _GL_ATTRIBUTE_PURE
1117 gl_linked_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
1118                               const void *elt)
1119 {
1120   gl_list_node_t node;
1121   size_t index;
1122
1123   for (node = list->root.next, index = 0;
1124        node != &list->root;
1125        node = node->next, index++)
1126     {
1127       int cmp = compar (node->value, elt);
1128
1129       if (cmp > 0)
1130         break;
1131       if (cmp == 0)
1132         return index;
1133     }
1134   return (size_t)(-1);
1135 }
1136
1137 static size_t _GL_ATTRIBUTE_PURE
1138 gl_linked_sortedlist_indexof_from_to (gl_list_t list,
1139                                       gl_listelement_compar_fn compar,
1140                                       size_t low, size_t high,
1141                                       const void *elt)
1142 {
1143   size_t count = list->count;
1144
1145   if (!(low <= high && high <= list->count))
1146     /* Invalid arguments.  */
1147     abort ();
1148
1149   high -= low;
1150   if (high > 0)
1151     {
1152       /* Here we know low < count.  */
1153       size_t index = low;
1154       size_t position = low;
1155       gl_list_node_t node;
1156
1157       if (position <= ((count - 1) / 2))
1158         {
1159           node = list->root.next;
1160           for (; position > 0; position--)
1161             node = node->next;
1162         }
1163       else
1164         {
1165           position = count - 1 - position;
1166           node = list->root.prev;
1167           for (; position > 0; position--)
1168             node = node->prev;
1169         }
1170
1171       do
1172         {
1173           int cmp = compar (node->value, elt);
1174
1175           if (cmp > 0)
1176             break;
1177           if (cmp == 0)
1178             return index;
1179           node = node->next;
1180           index++;
1181         }
1182       while (--high > 0);
1183     }
1184   return (size_t)(-1);
1185 }
1186
1187 static gl_list_node_t
1188 gl_linked_sortedlist_nx_add (gl_list_t list, gl_listelement_compar_fn compar,
1189                              const void *elt)
1190 {
1191   gl_list_node_t node;
1192
1193   for (node = list->root.next; node != &list->root; node = node->next)
1194     if (compar (node->value, elt) >= 0)
1195       return gl_linked_nx_add_before (list, node, elt);
1196   return gl_linked_nx_add_last (list, elt);
1197 }
1198
1199 static bool
1200 gl_linked_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
1201                              const void *elt)
1202 {
1203   gl_list_node_t node;
1204
1205   for (node = list->root.next; node != &list->root; node = node->next)
1206     {
1207       int cmp = compar (node->value, elt);
1208
1209       if (cmp > 0)
1210         break;
1211       if (cmp == 0)
1212         return gl_linked_remove_node (list, node);
1213     }
1214   return false;
1215 }