lib/gl_anylinked_list2.h

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