lib/gl_anylinked_list2.h

   1 /* Sequential list data type implemented by a linked list.
   2    Copyright (C) 2006 Free Software Foundation, Inc.
   3    Written by Bruno Haible <bruno@clisp.org>, 2006.
   4
   5    This program is free software; you can redistribute it and/or modify
   6    it under the terms of the GNU General Public License as published by
   7    the Free Software Foundation; either version 2, or (at your option)
   8    any later version.
   9
  10    This program is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13    GNU General Public License for more details.
  14
  15    You should have received a copy of the GNU General Public License
  16    along with this program; if not, write to the Free Software Foundation,
  17    Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
  18
  19 /* Common code of gl_linked_list.c and gl_linkedhash_list.c.  */
  20
  21 /* If the symbol SIGNAL_SAFE_LIST is defined, the code is compiled in such
  22    a way that a gl_list_t data structure may be used from within a signal
  23    handler.  The operations allowed in the signal handler are:
  24      gl_list_iterator, gl_list_iterator_next, gl_list_iterator_free.
  25    The list and node fields that are therefore accessed from the signal handler
  26    are:
  27      list->root, node->next, node->value.
  28    We are careful to make modifications to these fields only in an order
  29    that maintains the consistency of the list data structure at any moment,
  30    and we use 'volatile' assignments to prevent the compiler from reordering
  31    such assignments.  */
  32 #ifdef SIGNAL_SAFE_LIST
  33 # define ASYNCSAFE(type) *(volatile type *)&
  34 #else
  35 # define ASYNCSAFE(type)
  36 #endif
  37
  38 /* -------------------------- gl_list_t Data Type -------------------------- */
  39
  40 static gl_list_t
  41 gl_linked_create_empty (gl_list_implementation_t implementation,
  42                         gl_listelement_equals_fn equals_fn,
  43                         gl_listelement_hashcode_fn hashcode_fn,
  44                         bool allow_duplicates)
  45 {
  46   struct gl_list_impl *list =
  47     (struct gl_list_impl *) xmalloc (sizeof (struct gl_list_impl));
  48
  49   list->base.vtable = implementation;
  50   list->base.equals_fn = equals_fn;
  51   list->base.hashcode_fn = hashcode_fn;
  52   list->base.allow_duplicates = allow_duplicates;
  53 #if WITH_HASHTABLE
  54   list->table_size = 11;
  55   list->table =
  56     (gl_hash_entry_t *) xzalloc (list->table_size * sizeof (gl_hash_entry_t));
  57 #endif
  58   list->root.next = &list->root;
  59   list->root.prev = &list->root;
  60   list->count = 0;
  61
  62   return list;
  63 }
  64
  65 static gl_list_t
  66 gl_linked_create (gl_list_implementation_t implementation,
  67                   gl_listelement_equals_fn equals_fn,
  68                   gl_listelement_hashcode_fn hashcode_fn,
  69                   bool allow_duplicates,
  70                   size_t count, const void **contents)
  71 {
  72   struct gl_list_impl *list =
  73     (struct gl_list_impl *) xmalloc (sizeof (struct gl_list_impl));
  74   gl_list_node_t tail;
  75
  76   list->base.vtable = implementation;
  77   list->base.equals_fn = equals_fn;
  78   list->base.hashcode_fn = hashcode_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 =
  87       (gl_hash_entry_t *) xzalloc (list->table_size * sizeof (gl_hash_entry_t));
  88   }
  89 #endif
  90   list->count = count;
  91   tail = &list->root;
  92   for (; count > 0; contents++, count--)
  93     {
  94       gl_list_node_t node =
  95         (struct gl_list_node_impl *)
  96         xmalloc (sizeof (struct gl_list_node_impl));
  97
  98       node->value = *contents;
  99 #if WITH_HASHTABLE
 100       node->h.hashcode =
 101         (list->base.hashcode_fn != NULL
 102          ? list->base.hashcode_fn (node->value)
 103          : (size_t)(uintptr_t) node->value);
 104
 105       /* Add node to the hash table.  */
 106       add_to_bucket (list, node);
 107 #endif
 108
 109       /* Add node to the list.  */
 110       node->prev = tail;
 111       tail->next = node;
 112       tail = node;
 113     }
 114   tail->next = &list->root;
 115   list->root.prev = tail;
 116
 117   return list;
 118 }
 119
 120 static size_t
 121 gl_linked_size (gl_list_t list)
 122 {
 123   return list->count;
 124 }
 125
 126 static const void *
 127 gl_linked_node_value (gl_list_t list, gl_list_node_t node)
 128 {
 129   return node->value;
 130 }
 131
 132 static gl_list_node_t
 133 gl_linked_next_node (gl_list_t list, gl_list_node_t node)
 134 {
 135   return (node->next != &list->root ? node->next : NULL);
 136 }
 137
 138 static gl_list_node_t
 139 gl_linked_previous_node (gl_list_t list, gl_list_node_t node)
 140 {
 141   return (node->prev != &list->root ? node->prev : NULL);
 142 }
 143
 144 static const void *
 145 gl_linked_get_at (gl_list_t list, size_t position)
 146 {
 147   size_t count = list->count;
 148   gl_list_node_t node;
 149
 150   if (!(position < count))
 151     /* Invalid argument.  */
 152     abort ();
 153   /* Here we know count > 0.  */
 154   if (position <= ((count - 1) / 2))
 155     {
 156       node = list->root.next;
 157       for (; position > 0; position--)
 158         node = node->next;
 159     }
 160   else
 161     {
 162       position = count - 1 - position;
 163       node = list->root.prev;
 164       for (; position > 0; position--)
 165         node = node->prev;
 166     }
 167   return node->value;
 168 }
 169
 170 static gl_list_node_t
 171 gl_linked_set_at (gl_list_t list, size_t position, const void *elt)
 172 {
 173   size_t count = list->count;
 174   gl_list_node_t node;
 175
 176   if (!(position < count))
 177     /* Invalid argument.  */
 178     abort ();
 179   /* Here we know count > 0.  */
 180   if (position <= ((count - 1) / 2))
 181     {
 182       node = list->root.next;
 183       for (; position > 0; position--)
 184         node = node->next;
 185     }
 186   else
 187     {
 188       position = count - 1 - position;
 189       node = list->root.prev;
 190       for (; position > 0; position--)
 191         node = node->prev;
 192     }
 193 #if WITH_HASHTABLE
 194   if (elt != node->value)
 195     {
 196       size_t new_hashcode =
 197         (list->base.hashcode_fn != NULL
 198          ? list->base.hashcode_fn (elt)
 199          : (size_t)(uintptr_t) elt);
 200
 201       if (new_hashcode != node->h.hashcode)
 202         {
 203           remove_from_bucket (list, node);
 204           node->value = elt;
 205           node->h.hashcode = new_hashcode;
 206           add_to_bucket (list, node);
 207         }
 208       else
 209         node->value = elt;
 210     }
 211 #else
 212   node->value = elt;
 213 #endif
 214   return node;
 215 }
 216
 217 static gl_list_node_t
 218 gl_linked_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
 219                           const void *elt)
 220 {
 221   size_t count = list->count;
 222
 223   if (!(start_index <= end_index && end_index <= count))
 224     /* Invalid arguments.  */
 225     abort ();
 226   {
 227 #if WITH_HASHTABLE
 228     size_t hashcode =
 229       (list->base.hashcode_fn != NULL
 230        ? list->base.hashcode_fn (elt)
 231        : (size_t)(uintptr_t) elt);
 232     size_t index = hashcode % list->table_size;
 233     gl_listelement_equals_fn equals = list->base.equals_fn;
 234
 235     if (!list->base.allow_duplicates)
 236       {
 237         /* Look for the first match in the hash bucket.  */
 238         gl_list_node_t found = NULL;
 239         gl_list_node_t node;
 240
 241         for (node = (gl_list_node_t) list->table[index];
 242              node != NULL;
 243              node = (gl_list_node_t) node->h.hash_next)
 244           if (node->h.hashcode == hashcode
 245               && (equals != NULL
 246                   ? equals (elt, node->value)
 247                   : elt == node->value))
 248             {
 249               found = node;
 250               break;
 251             }
 252         if (start_index > 0)
 253           /* Look whether found's index is < start_index.  */
 254           for (node = list->root.next; ; node = node->next)
 255             {
 256               if (node == found)
 257                 return NULL;
 258               if (--start_index == 0)
 259                 break;
 260             }
 261         if (end_index < count)
 262           /* Look whether found's index is >= end_index.  */
 263           {
 264             end_index = count - end_index;
 265             for (node = list->root.prev; ; node = node->prev)
 266               {
 267                 if (node == found)
 268                   return NULL;
 269                 if (--end_index == 0)
 270                   break;
 271               }
 272           }
 273         return found;
 274       }
 275     else
 276       {
 277         /* Look whether there is more than one match in the hash bucket.  */
 278         bool multiple_matches = false;
 279         gl_list_node_t first_match = NULL;
 280         gl_list_node_t node;
 281
 282         for (node = (gl_list_node_t) list->table[index];
 283              node != NULL;
 284              node = (gl_list_node_t) node->h.hash_next)
 285           if (node->h.hashcode == hashcode
 286               && (equals != NULL
 287                   ? equals (elt, node->value)
 288                   : elt == node->value))
 289             {
 290               if (first_match == NULL)
 291                 first_match = node;
 292               else
 293                 {
 294                   multiple_matches = true;
 295                   break;
 296                 }
 297             }
 298         if (multiple_matches)
 299           {
 300             /* We need the match with the smallest index.  But we don't have
 301                a fast mapping node -> index.  So we have to walk the list.  */
 302             end_index -= start_index;
 303             node = list->root.next;
 304             for (; start_index > 0; start_index--)
 305               node = node->next;
 306
 307             for (;
 308                  end_index > 0;
 309                  node = node->next, end_index--)
 310               if (node->h.hashcode == hashcode
 311                   && (equals != NULL
 312                       ? equals (elt, node->value)
 313                       : elt == node->value))
 314                 return node;
 315             /* The matches must have all been at indices < start_index or
 316                >= end_index.  */
 317             return NULL;
 318           }
 319         else
 320           {
 321             if (start_index > 0)
 322               /* Look whether first_match's index is < start_index.  */
 323               for (node = list->root.next; node != &list->root; node = node->next)
 324                 {
 325                   if (node == first_match)
 326                     return NULL;
 327                   if (--start_index == 0)
 328                     break;
 329                 }
 330             if (end_index < list->count)
 331               /* Look whether first_match's index is >= end_index.  */
 332               {
 333                 end_index = list->count - end_index;
 334                 for (node = list->root.prev; ; node = node->prev)
 335                   {
 336                     if (node == first_match)
 337                       return NULL;
 338                     if (--end_index == 0)
 339                       break;
 340                   }
 341               }
 342             return first_match;
 343           }
 344       }
 345 #else
 346     gl_listelement_equals_fn equals = list->base.equals_fn;
 347     gl_list_node_t node = list->root.next;
 348
 349     end_index -= start_index;
 350     for (; start_index > 0; start_index--)
 351       node = node->next;
 352
 353     if (equals != NULL)
 354       {
 355         for (; end_index > 0; node = node->next, end_index--)
 356           if (equals (elt, node->value))
 357             return node;
 358       }
 359     else
 360       {
 361         for (; end_index > 0; node = node->next, end_index--)
 362           if (elt == node->value)
 363             return node;
 364       }
 365     return NULL;
 366 #endif
 367   }
 368 }
 369
 370 static size_t
 371 gl_linked_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
 372                            const void *elt)
 373 {
 374   size_t count = list->count;
 375
 376   if (!(start_index <= end_index && end_index <= count))
 377     /* Invalid arguments.  */
 378     abort ();
 379   {
 380 #if WITH_HASHTABLE
 381     /* Here the hash table doesn't help much.  It only allows us to minimize
 382        the number of equals() calls, by looking up first the node and then
 383        its index.  */
 384     size_t hashcode =
 385       (list->base.hashcode_fn != NULL
 386        ? list->base.hashcode_fn (elt)
 387        : (size_t)(uintptr_t) elt);
 388     size_t index = hashcode % list->table_size;
 389     gl_listelement_equals_fn equals = list->base.equals_fn;
 390     gl_list_node_t node;
 391
 392     /* First step: Look up the node.  */
 393     if (!list->base.allow_duplicates)
 394       {
 395         /* Look for the first match in the hash bucket.  */
 396         for (node = (gl_list_node_t) list->table[index];
 397              node != NULL;
 398              node = (gl_list_node_t) node->h.hash_next)
 399           if (node->h.hashcode == hashcode
 400               && (equals != NULL
 401                   ? equals (elt, node->value)
 402                   : elt == node->value))
 403             break;
 404       }
 405     else
 406       {
 407         /* Look whether there is more than one match in the hash bucket.  */
 408         bool multiple_matches = false;
 409         gl_list_node_t first_match = NULL;
 410
 411         for (node = (gl_list_node_t) list->table[index];
 412              node != NULL;
 413              node = (gl_list_node_t) node->h.hash_next)
 414           if (node->h.hashcode == hashcode
 415               && (equals != NULL
 416                   ? equals (elt, node->value)
 417                   : elt == node->value))
 418             {
 419               if (first_match == NULL)
 420                 first_match = node;
 421               else
 422                 {
 423                   multiple_matches = true;
 424                   break;
 425                 }
 426             }
 427         if (multiple_matches)
 428           {
 429             /* We need the match with the smallest index.  But we don't have
 430                a fast mapping node -> index.  So we have to walk the list.  */
 431             size_t index;
 432
 433             index = start_index;
 434             node = list->root.next;
 435             for (; start_index > 0; start_index--)
 436               node = node->next;
 437
 438             for (;
 439                  index < end_index;
 440                  node = node->next, index++)
 441               if (node->h.hashcode == hashcode
 442                   && (equals != NULL
 443                       ? equals (elt, node->value)
 444                       : elt == node->value))
 445                 return index;
 446             /* The matches must have all been at indices < start_index or
 447                >= end_index.  */
 448             return (size_t)(-1);
 449           }
 450         node = first_match;
 451       }
 452
 453     /* Second step: Look up the index of the node.  */
 454     if (node == NULL)
 455       return (size_t)(-1);
 456     else
 457       {
 458         size_t index = 0;
 459
 460         for (; node->prev != &list->root; node = node->prev)
 461           index++;
 462
 463         if (index >= start_index && index < end_index)
 464           return index;
 465         else
 466           return (size_t)(-1);
 467       }
 468 #else
 469     gl_listelement_equals_fn equals = list->base.equals_fn;
 470     size_t index = start_index;
 471     gl_list_node_t node = list->root.next;
 472
 473     for (; start_index > 0; start_index--)
 474       node = node->next;
 475
 476     if (equals != NULL)
 477       {
 478         for (;
 479              index < end_index;
 480              node = node->next, index++)
 481           if (equals (elt, node->value))
 482             return index;
 483       }
 484     else
 485       {
 486         for (;
 487              index < end_index;
 488              node = node->next, index++)
 489           if (elt == node->value)
 490             return index;
 491       }
 492     return (size_t)(-1);
 493 #endif
 494   }
 495 }
 496
 497 static gl_list_node_t
 498 gl_linked_add_first (gl_list_t list, const void *elt)
 499 {
 500   gl_list_node_t node =
 501     (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
 502
 503   ASYNCSAFE(const void *) node->value = elt;
 504 #if WITH_HASHTABLE
 505   node->h.hashcode =
 506     (list->base.hashcode_fn != NULL
 507      ? list->base.hashcode_fn (node->value)
 508      : (size_t)(uintptr_t) node->value);
 509
 510   /* Add node to the hash table.  */
 511   add_to_bucket (list, node);
 512 #endif
 513
 514   /* Add node to the list.  */
 515   node->prev = &list->root;
 516   ASYNCSAFE(gl_list_node_t) node->next = list->root.next;
 517   node->next->prev = node;
 518   ASYNCSAFE(gl_list_node_t) list->root.next = node;
 519   list->count++;
 520
 521 #if WITH_HASHTABLE
 522   hash_resize_after_add (list);
 523 #endif
 524
 525   return node;
 526 }
 527
 528 static gl_list_node_t
 529 gl_linked_add_last (gl_list_t list, const void *elt)
 530 {
 531   gl_list_node_t node =
 532     (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
 533
 534   ASYNCSAFE(const void *) node->value = elt;
 535 #if WITH_HASHTABLE
 536   node->h.hashcode =
 537     (list->base.hashcode_fn != NULL
 538      ? list->base.hashcode_fn (node->value)
 539      : (size_t)(uintptr_t) node->value);
 540
 541   /* Add node to the hash table.  */
 542   add_to_bucket (list, node);
 543 #endif
 544
 545   /* Add node to the list.  */
 546   ASYNCSAFE(gl_list_node_t) node->next = &list->root;
 547   node->prev = list->root.prev;
 548   ASYNCSAFE(gl_list_node_t) node->prev->next = node;
 549   list->root.prev = node;
 550   list->count++;
 551
 552 #if WITH_HASHTABLE
 553   hash_resize_after_add (list);
 554 #endif
 555
 556   return node;
 557 }
 558
 559 static gl_list_node_t
 560 gl_linked_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
 561 {
 562   gl_list_node_t new_node =
 563     (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
 564
 565   ASYNCSAFE(const void *) new_node->value = elt;
 566 #if WITH_HASHTABLE
 567   new_node->h.hashcode =
 568     (list->base.hashcode_fn != NULL
 569      ? list->base.hashcode_fn (new_node->value)
 570      : (size_t)(uintptr_t) new_node->value);
 571
 572   /* Add new_node to the hash table.  */
 573   add_to_bucket (list, new_node);
 574 #endif
 575
 576   /* Add new_node to the list.  */
 577   ASYNCSAFE(gl_list_node_t) new_node->next = node;
 578   new_node->prev = node->prev;
 579   ASYNCSAFE(gl_list_node_t) new_node->prev->next = new_node;
 580   node->prev = new_node;
 581   list->count++;
 582
 583 #if WITH_HASHTABLE
 584   hash_resize_after_add (list);
 585 #endif
 586
 587   return new_node;
 588 }
 589
 590 static gl_list_node_t
 591 gl_linked_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
 592 {
 593   gl_list_node_t new_node =
 594     (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
 595
 596   ASYNCSAFE(const void *) new_node->value = elt;
 597 #if WITH_HASHTABLE
 598   new_node->h.hashcode =
 599     (list->base.hashcode_fn != NULL
 600      ? list->base.hashcode_fn (new_node->value)
 601      : (size_t)(uintptr_t) new_node->value);
 602
 603   /* Add new_node to the hash table.  */
 604   add_to_bucket (list, new_node);
 605 #endif
 606
 607   /* Add new_node to the list.  */
 608   new_node->prev = node;
 609   ASYNCSAFE(gl_list_node_t) new_node->next = node->next;
 610   new_node->next->prev = new_node;
 611   ASYNCSAFE(gl_list_node_t) node->next = new_node;
 612   list->count++;
 613
 614 #if WITH_HASHTABLE
 615   hash_resize_after_add (list);
 616 #endif
 617
 618   return new_node;
 619 }
 620
 621 static gl_list_node_t
 622 gl_linked_add_at (gl_list_t list, size_t position, const void *elt)
 623 {
 624   size_t count = list->count;
 625   gl_list_node_t new_node;
 626
 627   if (!(position <= count))
 628     /* Invalid argument.  */
 629     abort ();
 630
 631   new_node =
 632     (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
 633   ASYNCSAFE(const void *) new_node->value = elt;
 634 #if WITH_HASHTABLE
 635   new_node->h.hashcode =
 636     (list->base.hashcode_fn != NULL
 637      ? list->base.hashcode_fn (new_node->value)
 638      : (size_t)(uintptr_t) new_node->value);
 639
 640   /* Add new_node to the hash table.  */
 641   add_to_bucket (list, new_node);
 642 #endif
 643
 644   /* Add new_node to the list.  */
 645   if (position <= (count / 2))
 646     {
 647       gl_list_node_t node;
 648
 649       node = &list->root;
 650       for (; position > 0; position--)
 651         node = node->next;
 652       new_node->prev = node;
 653       ASYNCSAFE(gl_list_node_t) new_node->next = node->next;
 654       new_node->next->prev = new_node;
 655       ASYNCSAFE(gl_list_node_t) node->next = new_node;
 656     }
 657   else
 658     {
 659       gl_list_node_t node;
 660
 661       position = count - position;
 662       node = &list->root;
 663       for (; position > 0; position--)
 664         node = node->prev;
 665       ASYNCSAFE(gl_list_node_t) new_node->next = node;
 666       new_node->prev = node->prev;
 667       ASYNCSAFE(gl_list_node_t) new_node->prev->next = new_node;
 668       node->prev = new_node;
 669     }
 670   list->count++;
 671
 672 #if WITH_HASHTABLE
 673   hash_resize_after_add (list);
 674 #endif
 675
 676   return new_node;
 677 }
 678
 679 static bool
 680 gl_linked_remove_node (gl_list_t list, gl_list_node_t node)
 681 {
 682   gl_list_node_t prev;
 683   gl_list_node_t next;
 684
 685 #if WITH_HASHTABLE
 686   /* Remove node from the hash table.  */
 687   remove_from_bucket (list, node);
 688 #endif
 689
 690   /* Remove node from the list.  */
 691   prev = node->prev;
 692   next = node->next;
 693
 694   ASYNCSAFE(gl_list_node_t) prev->next = next;
 695   next->prev = prev;
 696   list->count--;
 697
 698   free (node);
 699   return true;
 700 }
 701
 702 static bool
 703 gl_linked_remove_at (gl_list_t list, size_t position)
 704 {
 705   size_t count = list->count;
 706   gl_list_node_t removed_node;
 707
 708   if (!(position < count))
 709     /* Invalid argument.  */
 710     abort ();
 711   /* Here we know count > 0.  */
 712   if (position <= ((count - 1) / 2))
 713     {
 714       gl_list_node_t node;
 715       gl_list_node_t after_removed;
 716
 717       node = &list->root;
 718       for (; position > 0; position--)
 719         node = node->next;
 720       removed_node = node->next;
 721       after_removed = node->next->next;
 722       ASYNCSAFE(gl_list_node_t) node->next = after_removed;
 723       after_removed->prev = node;
 724     }
 725   else
 726     {
 727       gl_list_node_t node;
 728       gl_list_node_t before_removed;
 729
 730       position = count - 1 - position;
 731       node = &list->root;
 732       for (; position > 0; position--)
 733         node = node->prev;
 734       removed_node = node->prev;
 735       before_removed = node->prev->prev;
 736       node->prev = before_removed;
 737       ASYNCSAFE(gl_list_node_t) before_removed->next = node;
 738     }
 739 #if WITH_HASHTABLE
 740   remove_from_bucket (list, removed_node);
 741 #endif
 742   list->count--;
 743
 744   free (removed_node);
 745   return true;
 746 }
 747
 748 static bool
 749 gl_linked_remove (gl_list_t list, const void *elt)
 750 {
 751   gl_list_node_t node = gl_linked_search_from_to (list, 0, list->count, elt);
 752
 753   if (node != NULL)
 754     return gl_linked_remove_node (list, node);
 755   else
 756     return false;
 757 }
 758
 759 static void
 760 gl_linked_list_free (gl_list_t list)
 761 {
 762   gl_list_node_t node;
 763
 764   for (node = list->root.next; node != &list->root; )
 765     {
 766       gl_list_node_t next = node->next;
 767       free (node);
 768       node = next;
 769     }
 770 #if WITH_HASHTABLE
 771   free (list->table);
 772 #endif
 773   free (list);
 774 }
 775
 776 /* --------------------- gl_list_iterator_t Data Type --------------------- */
 777
 778 static gl_list_iterator_t
 779 gl_linked_iterator (gl_list_t list)
 780 {
 781   gl_list_iterator_t result;
 782
 783   result.vtable = list->base.vtable;
 784   result.list = list;
 785   result.p = list->root.next;
 786   result.q = &list->root;
 787 #ifdef lint
 788   result.i = 0;
 789   result.j = 0;
 790   result.count = 0;
 791 #endif
 792
 793   return result;
 794 }
 795
 796 static gl_list_iterator_t
 797 gl_linked_iterator_from_to (gl_list_t list,
 798                             size_t start_index, size_t end_index)
 799 {
 800   gl_list_iterator_t result;
 801   size_t n1, n2, n3;
 802
 803   if (!(start_index <= end_index && end_index <= list->count))
 804     /* Invalid arguments.  */
 805     abort ();
 806   result.vtable = list->base.vtable;
 807   result.list = list;
 808   n1 = start_index;
 809   n2 = end_index - start_index;
 810   n3 = list->count - end_index;
 811   /* Find the maximum among n1, n2, n3, so as to reduce the number of
 812      loop iterations to n1 + n2 + n3 - max(n1,n2,n3).  */
 813   if (n1 > n2 && n1 > n3)
 814     {
 815       /* n1 is the maximum, use n2 and n3.  */
 816       gl_list_node_t node;
 817       size_t i;
 818
 819       node = &list->root;
 820       for (i = n3; i > 0; i--)
 821         node = node->prev;
 822       result.q = node;
 823       for (i = n2; i > 0; i--)
 824         node = node->prev;
 825       result.p = node;
 826     }
 827   else if (n2 > n3)
 828     {
 829       /* n2 is the maximum, use n1 and n3.  */
 830       gl_list_node_t node;
 831       size_t i;
 832
 833       node = list->root.next;
 834       for (i = n1; i > 0; i--)
 835         node = node->next;
 836       result.p = node;
 837
 838       node = &list->root;
 839       for (i = n3; i > 0; i--)
 840         node = node->prev;
 841       result.q = node;
 842     }
 843   else
 844     {
 845       /* n3 is the maximum, use n1 and n2.  */
 846       gl_list_node_t node;
 847       size_t i;
 848
 849       node = list->root.next;
 850       for (i = n1; i > 0; i--)
 851         node = node->next;
 852       result.p = node;
 853       for (i = n2; i > 0; i--)
 854         node = node->next;
 855       result.q = node;
 856     }
 857
 858 #ifdef lint
 859   result.i = 0;
 860   result.j = 0;
 861   result.count = 0;
 862 #endif
 863
 864   return result;
 865 }
 866
 867 static bool
 868 gl_linked_iterator_next (gl_list_iterator_t *iterator,
 869                          const void **eltp, gl_list_node_t *nodep)
 870 {
 871   if (iterator->p != iterator->q)
 872     {
 873       gl_list_node_t node = (gl_list_node_t) iterator->p;
 874       *eltp = node->value;
 875       if (nodep != NULL)
 876         *nodep = node;
 877       iterator->p = node->next;
 878       return true;
 879     }
 880   else
 881     return false;
 882 }
 883
 884 static void
 885 gl_linked_iterator_free (gl_list_iterator_t *iterator)
 886 {
 887 }
 888
 889 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
 890
 891 static gl_list_node_t
 892 gl_linked_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
 893                              const void *elt)
 894 {
 895   gl_list_node_t node;
 896
 897   for (node = list->root.next; node != &list->root; node = node->next)
 898     {
 899       int cmp = compar (node->value, elt);
 900
 901       if (cmp > 0)
 902         break;
 903       if (cmp == 0)
 904         return node;
 905     }
 906   return NULL;
 907 }
 908
 909 static size_t
 910 gl_linked_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
 911                               const void *elt)
 912 {
 913   gl_list_node_t node;
 914   size_t index;
 915
 916   for (node = list->root.next, index = 0;
 917        node != &list->root;
 918        node = node->next, index++)
 919     {
 920       int cmp = compar (node->value, elt);
 921
 922       if (cmp > 0)
 923         break;
 924       if (cmp == 0)
 925         return index;
 926     }
 927   return (size_t)(-1);
 928 }
 929
 930 static gl_list_node_t
 931 gl_linked_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar,
 932                           const void *elt)
 933 {
 934   gl_list_node_t node;
 935
 936   for (node = list->root.next; node != &list->root; node = node->next)
 937     if (compar (node->value, elt) >= 0)
 938       return gl_linked_add_before (list, node, elt);
 939   return gl_linked_add_last (list, elt);
 940 }
 941
 942 static bool
 943 gl_linked_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
 944                              const void *elt)
 945 {
 946   gl_list_node_t node;
 947
 948   for (node = list->root.next; node != &list->root; node = node->next)
 949     {
 950       int cmp = compar (node->value, elt);
 951
 952       if (cmp > 0)
 953         break;
 954       if (cmp == 0)
 955         return gl_linked_remove_node (list, node);
 956     }
 957   return false;
 958 }