lib/gl_anylinked_list2.h

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