lib/gl_carray_list.c

   1 /* Sequential list data type implemented by a circular array.
   2    Copyright (C) 2006-2024 Free Software Foundation, Inc.
   3    Written by Bruno Haible <bruno@clisp.org>, 2006.
   4
   5    This file is free software: you can redistribute it and/or modify
   6    it under the terms of the GNU Lesser General Public License as
   7    published by the Free Software Foundation; either version 2.1 of the
   8    License, or (at your option) any later version.
   9
  10    This file 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 Lesser General Public License for more details.
  14
  15    You should have received a copy of the GNU Lesser General Public License
  16    along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
  17
  18 #include <config.h>
  19
  20 /* Specification.  */
  21 #include "gl_carray_list.h"
  22
  23 #include <stdint.h>
  24 #include <stdlib.h>
  25 /* Get memcpy.  */
  26 #include <string.h>
  27
  28 /* Checked size_t computations.  */
  29 #include "xsize.h"
  30
  31 /* -------------------------- gl_list_t Data Type -------------------------- */
  32
  33 /* Concrete gl_list_impl type, valid for this file only.  */
  34 struct gl_list_impl
  35 {
  36   struct gl_list_impl_base base;
  37   /* An array of ALLOCATED elements, of which the elements
  38      OFFSET, (OFFSET + 1) % ALLOCATED, ..., (OFFSET + COUNT - 1) % ALLOCATED
  39      are used.  0 <= COUNT <= ALLOCATED.  Either OFFSET = ALLOCATED = 0 or
  40      0 <= OFFSET < ALLOCATED.  */
  41   const void **elements;
  42   size_t offset;
  43   size_t count;
  44   size_t allocated;
  45 };
  46
  47 /* struct gl_list_node_impl doesn't exist here.  The pointers are actually
  48    indices + 1.  */
  49 #define INDEX_TO_NODE(index) (gl_list_node_t)(uintptr_t)(size_t)((index) + 1)
  50 #define NODE_TO_INDEX(node) ((uintptr_t)(node) - 1)
  51
  52 static gl_list_t
  53 gl_carray_nx_create_empty (gl_list_implementation_t implementation,
  54                            gl_listelement_equals_fn equals_fn,
  55                            gl_listelement_hashcode_fn hashcode_fn,
  56                            gl_listelement_dispose_fn dispose_fn,
  57                            bool allow_duplicates)
  58 {
  59   struct gl_list_impl *list =
  60     (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl));
  61
  62   if (list == NULL)
  63     return NULL;
  64
  65   list->base.vtable = implementation;
  66   list->base.equals_fn = equals_fn;
  67   list->base.hashcode_fn = hashcode_fn;
  68   list->base.dispose_fn = dispose_fn;
  69   list->base.allow_duplicates = allow_duplicates;
  70   list->elements = NULL;
  71   list->offset = 0;
  72   list->count = 0;
  73   list->allocated = 0;
  74
  75   return list;
  76 }
  77
  78 static gl_list_t
  79 gl_carray_nx_create (gl_list_implementation_t implementation,
  80                   gl_listelement_equals_fn equals_fn,
  81                   gl_listelement_hashcode_fn hashcode_fn,
  82                   gl_listelement_dispose_fn dispose_fn,
  83                   bool allow_duplicates,
  84                   size_t count, const void **contents)
  85 {
  86   struct gl_list_impl *list =
  87     (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl));
  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 (count > 0)
  98     {
  99       if (size_overflow_p (xtimes (count, sizeof (const void *))))
 100         goto fail;
 101       list->elements = (const void **) malloc (count * sizeof (const void *));
 102       if (list->elements == NULL)
 103         goto fail;
 104       memcpy (list->elements, contents, count * sizeof (const void *));
 105     }
 106   else
 107     list->elements = NULL;
 108   list->offset = 0;
 109   list->count = count;
 110   list->allocated = count;
 111
 112   return list;
 113
 114  fail:
 115   free (list);
 116   return NULL;
 117 }
 118
 119 static size_t _GL_ATTRIBUTE_PURE
 120 gl_carray_size (gl_list_t list)
 121 {
 122   return list->count;
 123 }
 124
 125 static const void * _GL_ATTRIBUTE_PURE
 126 gl_carray_node_value (gl_list_t list, gl_list_node_t node)
 127 {
 128   uintptr_t index = NODE_TO_INDEX (node);
 129   size_t i;
 130
 131   if (!(index < list->count))
 132     /* Invalid argument.  */
 133     abort ();
 134   i = list->offset + index;
 135   if (i >= list->allocated)
 136     i -= list->allocated;
 137   return list->elements[i];
 138 }
 139
 140 static int
 141 gl_carray_node_nx_set_value (gl_list_t list, gl_list_node_t node,
 142                              const void *elt)
 143 {
 144   uintptr_t index = NODE_TO_INDEX (node);
 145   size_t i;
 146
 147   if (!(index < list->count))
 148     /* Invalid argument.  */
 149     abort ();
 150   i = list->offset + index;
 151   if (i >= list->allocated)
 152     i -= list->allocated;
 153   list->elements[i] = elt;
 154   return 0;
 155 }
 156
 157 static gl_list_node_t _GL_ATTRIBUTE_PURE
 158 gl_carray_next_node (gl_list_t list, gl_list_node_t node)
 159 {
 160   uintptr_t index = NODE_TO_INDEX (node);
 161   if (!(index < list->count))
 162     /* Invalid argument.  */
 163     abort ();
 164   index++;
 165   if (index < list->count)
 166     return INDEX_TO_NODE (index);
 167   else
 168     return NULL;
 169 }
 170
 171 static gl_list_node_t _GL_ATTRIBUTE_PURE
 172 gl_carray_previous_node (gl_list_t list, gl_list_node_t node)
 173 {
 174   uintptr_t index = NODE_TO_INDEX (node);
 175   if (!(index < list->count))
 176     /* Invalid argument.  */
 177     abort ();
 178   if (index > 0)
 179     return INDEX_TO_NODE (index - 1);
 180   else
 181     return NULL;
 182 }
 183
 184 static gl_list_node_t _GL_ATTRIBUTE_PURE
 185 gl_carray_first_node (gl_list_t list)
 186 {
 187   if (list->count > 0)
 188     return INDEX_TO_NODE (0);
 189   else
 190     return NULL;
 191 }
 192
 193 static gl_list_node_t _GL_ATTRIBUTE_PURE
 194 gl_carray_last_node (gl_list_t list)
 195 {
 196   if (list->count > 0)
 197     return INDEX_TO_NODE (list->count - 1);
 198   else
 199     return NULL;
 200 }
 201
 202 static const void * _GL_ATTRIBUTE_PURE
 203 gl_carray_get_at (gl_list_t list, size_t position)
 204 {
 205   size_t count = list->count;
 206   size_t i;
 207
 208   if (!(position < count))
 209     /* Invalid argument.  */
 210     abort ();
 211   i = list->offset + position;
 212   if (i >= list->allocated)
 213     i -= list->allocated;
 214   return list->elements[i];
 215 }
 216
 217 static gl_list_node_t
 218 gl_carray_nx_set_at (gl_list_t list, size_t position, const void *elt)
 219 {
 220   size_t count = list->count;
 221   size_t i;
 222
 223   if (!(position < count))
 224     /* Invalid argument.  */
 225     abort ();
 226   i = list->offset + position;
 227   if (i >= list->allocated)
 228     i -= list->allocated;
 229   list->elements[i] = elt;
 230   return INDEX_TO_NODE (position);
 231 }
 232
 233 static size_t _GL_ATTRIBUTE_PURE
 234 gl_carray_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
 235                            const void *elt)
 236 {
 237   size_t count = list->count;
 238
 239   if (!(start_index <= end_index && end_index <= count))
 240     /* Invalid arguments.  */
 241     abort ();
 242
 243   if (start_index < end_index)
 244     {
 245       gl_listelement_equals_fn equals = list->base.equals_fn;
 246       size_t allocated = list->allocated;
 247       size_t i_end;
 248
 249       i_end = list->offset + end_index;
 250       if (i_end >= allocated)
 251         i_end -= allocated;
 252
 253       if (equals != NULL)
 254         {
 255           size_t i;
 256
 257           i = list->offset + start_index;
 258           if (i >= allocated) /* can only happen if start_index > 0 */
 259             i -= allocated;
 260
 261           for (;;)
 262             {
 263               if (equals (elt, list->elements[i]))
 264                 return (i >= list->offset ? i : i + allocated) - list->offset;
 265               i++;
 266               if (i == allocated)
 267                 i = 0;
 268               if (i == i_end)
 269                 break;
 270             }
 271         }
 272       else
 273         {
 274           size_t i;
 275
 276           i = list->offset + start_index;
 277           if (i >= allocated) /* can only happen if start_index > 0 */
 278             i -= allocated;
 279
 280           for (;;)
 281             {
 282               if (elt == list->elements[i])
 283                 return (i >= list->offset ? i : i + allocated) - list->offset;
 284               i++;
 285               if (i == allocated)
 286                 i = 0;
 287               if (i == i_end)
 288                 break;
 289             }
 290         }
 291     }
 292   return (size_t)(-1);
 293 }
 294
 295 static gl_list_node_t _GL_ATTRIBUTE_PURE
 296 gl_carray_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
 297                           const void *elt)
 298 {
 299   size_t index = gl_carray_indexof_from_to (list, start_index, end_index, elt);
 300   return INDEX_TO_NODE (index);
 301 }
 302
 303 /* Ensure that list->allocated > list->count.
 304    Return 0 upon success, -1 upon out-of-memory.  */
 305 static int
 306 grow (gl_list_t list)
 307 {
 308   size_t new_allocated;
 309   size_t memory_size;
 310   const void **memory;
 311
 312   new_allocated = xtimes (list->allocated, 2);
 313   new_allocated = xsum (new_allocated, 1);
 314   memory_size = xtimes (new_allocated, sizeof (const void *));
 315   if (size_overflow_p (memory_size))
 316     /* Overflow, would lead to out of memory.  */
 317     return -1;
 318   if (list->offset > 0 && list->count > 0)
 319     {
 320       memory = (const void **) malloc (memory_size);
 321       if (memory == NULL)
 322         /* Out of memory.  */
 323         return -1;
 324       if (list->offset + list->count > list->allocated)
 325         {
 326           memcpy (memory, &list->elements[list->offset],
 327                   (list->allocated - list->offset) * sizeof (const void *));
 328           memcpy (memory + (list->allocated - list->offset), list->elements,
 329                   (list->offset + list->count - list->allocated)
 330                   * sizeof (const void *));
 331
 332         }
 333       else
 334         memcpy (memory, &list->elements[list->offset],
 335                 list->count * sizeof (const void *));
 336       if (list->elements != NULL)
 337         free (list->elements);
 338     }
 339   else
 340     {
 341       memory = (const void **) realloc (list->elements, memory_size);
 342       if (memory == NULL)
 343         /* Out of memory.  */
 344         return -1;
 345     }
 346   list->elements = memory;
 347   list->offset = 0;
 348   list->allocated = new_allocated;
 349   return 0;
 350 }
 351
 352 static gl_list_node_t
 353 gl_carray_nx_add_first (gl_list_t list, const void *elt)
 354 {
 355   size_t count = list->count;
 356
 357   if (count == list->allocated)
 358     if (grow (list) < 0)
 359       return NULL;
 360   list->offset = (list->offset == 0 ? list->allocated : list->offset) - 1;
 361   list->elements[list->offset] = elt;
 362   list->count = count + 1;
 363   return INDEX_TO_NODE (0);
 364 }
 365
 366 static gl_list_node_t
 367 gl_carray_nx_add_last (gl_list_t list, const void *elt)
 368 {
 369   size_t count = list->count;
 370   size_t i;
 371
 372   if (count == list->allocated)
 373     if (grow (list) < 0)
 374       return NULL;
 375   i = list->offset + count;
 376   if (i >= list->allocated)
 377     i -= list->allocated;
 378   list->elements[i] = elt;
 379   list->count = count + 1;
 380   return INDEX_TO_NODE (count);
 381 }
 382
 383 static gl_list_node_t
 384 gl_carray_nx_add_at (gl_list_t list, size_t position, const void *elt)
 385 {
 386   size_t count = list->count;
 387   const void **elements;
 388
 389   if (!(position <= count))
 390     /* Invalid argument.  */
 391     abort ();
 392   if (count == list->allocated)
 393     if (grow (list) < 0)
 394       return NULL;
 395   elements = list->elements;
 396   if (position <= (count / 2))
 397     {
 398       /* Shift at most count/2 elements to the left.  */
 399       size_t i2, i;
 400
 401       list->offset = (list->offset == 0 ? list->allocated : list->offset) - 1;
 402
 403       i2 = list->offset + position;
 404       if (i2 >= list->allocated)
 405         {
 406           /* Here we must have list->offset > 0, hence list->allocated > 0.  */
 407           size_t i1 = list->allocated - 1;
 408           i2 -= list->allocated;
 409           for (i = list->offset; i < i1; i++)
 410             elements[i] = elements[i + 1];
 411           elements[i1] = elements[0];
 412           for (i = 0; i < i2; i++)
 413             elements[i] = elements[i + 1];
 414         }
 415       else
 416         {
 417           for (i = list->offset; i < i2; i++)
 418             elements[i] = elements[i + 1];
 419         }
 420       elements[i2] = elt;
 421     }
 422   else
 423     {
 424       /* Shift at most (count+1)/2 elements to the right.  */
 425       size_t i1, i3, i;
 426
 427       i1 = list->offset + position;
 428       i3 = list->offset + count;
 429       if (i1 >= list->allocated)
 430         {
 431           i1 -= list->allocated;
 432           i3 -= list->allocated;
 433           for (i = i3; i > i1; i--)
 434             elements[i] = elements[i - 1];
 435         }
 436       else if (i3 >= list->allocated)
 437         {
 438           /* Here we must have list->offset > 0, hence list->allocated > 0.  */
 439           size_t i2 = list->allocated - 1;
 440           i3 -= list->allocated;
 441           for (i = i3; i > 0; i--)
 442             elements[i] = elements[i - 1];
 443           elements[0] = elements[i2];
 444           for (i = i2; i > i1; i--)
 445             elements[i] = elements[i - 1];
 446         }
 447       else
 448         {
 449           for (i = i3; i > i1; i--)
 450             elements[i] = elements[i - 1];
 451         }
 452       elements[i1] = elt;
 453     }
 454   list->count = count + 1;
 455   return INDEX_TO_NODE (position);
 456 }
 457
 458 static gl_list_node_t
 459 gl_carray_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
 460 {
 461   size_t count = list->count;
 462   uintptr_t index = NODE_TO_INDEX (node);
 463
 464   if (!(index < count))
 465     /* Invalid argument.  */
 466     abort ();
 467   return gl_carray_nx_add_at (list, index, elt);
 468 }
 469
 470 static gl_list_node_t
 471 gl_carray_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
 472 {
 473   size_t count = list->count;
 474   uintptr_t index = NODE_TO_INDEX (node);
 475
 476   if (!(index < count))
 477     /* Invalid argument.  */
 478     abort ();
 479   return gl_carray_nx_add_at (list, index + 1, elt);
 480 }
 481
 482 static bool
 483 gl_carray_remove_at (gl_list_t list, size_t position)
 484 {
 485   size_t count = list->count;
 486   const void **elements;
 487
 488   if (!(position < count))
 489     /* Invalid argument.  */
 490     abort ();
 491   /* Here we know count > 0.  */
 492   elements = list->elements;
 493   if (position <= ((count - 1) / 2))
 494     {
 495       /* Shift at most (count-1)/2 elements to the right.  */
 496       size_t i0, i2, i;
 497
 498       i0 = list->offset;
 499       i2 = list->offset + position;
 500       if (i2 >= list->allocated)
 501         {
 502           /* Here we must have list->offset > 0, hence list->allocated > 0.  */
 503           size_t i1 = list->allocated - 1;
 504           i2 -= list->allocated;
 505           if (list->base.dispose_fn != NULL)
 506             list->base.dispose_fn (elements[i2]);
 507           for (i = i2; i > 0; i--)
 508             elements[i] = elements[i - 1];
 509           elements[0] = elements[i1];
 510           for (i = i1; i > i0; i--)
 511             elements[i] = elements[i - 1];
 512         }
 513       else
 514         {
 515           if (list->base.dispose_fn != NULL)
 516             list->base.dispose_fn (elements[i2]);
 517           for (i = i2; i > i0; i--)
 518             elements[i] = elements[i - 1];
 519         }
 520
 521       i0++;
 522       list->offset = (i0 == list->allocated ? 0 : i0);
 523     }
 524   else
 525     {
 526       /* Shift at most count/2 elements to the left.  */
 527       size_t i1, i3, i;
 528
 529       i1 = list->offset + position;
 530       i3 = list->offset + count - 1;
 531       if (i1 >= list->allocated)
 532         {
 533           i1 -= list->allocated;
 534           i3 -= list->allocated;
 535           if (list->base.dispose_fn != NULL)
 536             list->base.dispose_fn (elements[i1]);
 537           for (i = i1; i < i3; i++)
 538             elements[i] = elements[i + 1];
 539         }
 540       else if (i3 >= list->allocated)
 541         {
 542           /* Here we must have list->offset > 0, hence list->allocated > 0.  */
 543           size_t i2 = list->allocated - 1;
 544           i3 -= list->allocated;
 545           if (list->base.dispose_fn != NULL)
 546             list->base.dispose_fn (elements[i1]);
 547           for (i = i1; i < i2; i++)
 548             elements[i] = elements[i + 1];
 549           elements[i2] = elements[0];
 550           for (i = 0; i < i3; i++)
 551             elements[i] = elements[i + 1];
 552         }
 553       else
 554         {
 555           if (list->base.dispose_fn != NULL)
 556             list->base.dispose_fn (elements[i1]);
 557           for (i = i1; i < i3; i++)
 558             elements[i] = elements[i + 1];
 559         }
 560     }
 561   list->count = count - 1;
 562   return true;
 563 }
 564
 565 static bool
 566 gl_carray_remove_node (gl_list_t list, gl_list_node_t node)
 567 {
 568   size_t count = list->count;
 569   uintptr_t index = NODE_TO_INDEX (node);
 570
 571   if (!(index < count))
 572     /* Invalid argument.  */
 573     abort ();
 574   return gl_carray_remove_at (list, index);
 575 }
 576
 577 static bool
 578 gl_carray_remove (gl_list_t list, const void *elt)
 579 {
 580   size_t position = gl_carray_indexof_from_to (list, 0, list->count, elt);
 581   if (position == (size_t)(-1))
 582     return false;
 583   else
 584     return gl_carray_remove_at (list, position);
 585 }
 586
 587 static void
 588 gl_carray_list_free (gl_list_t list)
 589 {
 590   if (list->elements != NULL)
 591     {
 592       if (list->base.dispose_fn != NULL)
 593         {
 594           size_t count = list->count;
 595
 596           if (count > 0)
 597             {
 598               gl_listelement_dispose_fn dispose = list->base.dispose_fn;
 599               const void **elements = list->elements;
 600               size_t i1 = list->offset;
 601               size_t i3 = list->offset + count - 1;
 602
 603               if (i3 >= list->allocated)
 604                 {
 605                   /* Here we must have list->offset > 0, hence
 606                      list->allocated > 0.  */
 607                   size_t i2 = list->allocated - 1;
 608                   size_t i;
 609
 610                   i3 -= list->allocated;
 611                   for (i = i1; i <= i2; i++)
 612                     dispose (elements[i]);
 613                   for (i = 0; i <= i3; i++)
 614                     dispose (elements[i]);
 615                 }
 616               else
 617                 {
 618                   size_t i;
 619
 620                   for (i = i1; i <= i3; i++)
 621                     dispose (elements[i]);
 622                 }
 623             }
 624         }
 625       free (list->elements);
 626     }
 627   free (list);
 628 }
 629
 630 /* --------------------- gl_list_iterator_t Data Type --------------------- */
 631
 632 static gl_list_iterator_t _GL_ATTRIBUTE_PURE
 633 gl_carray_iterator (gl_list_t list)
 634 {
 635   gl_list_iterator_t result;
 636
 637   result.vtable = list->base.vtable;
 638   result.list = list;
 639   result.count = list->count;
 640   result.i = 0;
 641   result.j = list->count;
 642 #if defined GCC_LINT || defined lint
 643   result.p = 0;
 644   result.q = 0;
 645 #endif
 646
 647   return result;
 648 }
 649
 650 static gl_list_iterator_t _GL_ATTRIBUTE_PURE
 651 gl_carray_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index)
 652 {
 653   gl_list_iterator_t result;
 654
 655   if (!(start_index <= end_index && end_index <= list->count))
 656     /* Invalid arguments.  */
 657     abort ();
 658   result.vtable = list->base.vtable;
 659   result.list = list;
 660   result.count = list->count;
 661   result.i = start_index;
 662   result.j = end_index;
 663 #if defined GCC_LINT || defined lint
 664   result.p = 0;
 665   result.q = 0;
 666 #endif
 667
 668   return result;
 669 }
 670
 671 static bool
 672 gl_carray_iterator_next (gl_list_iterator_t *iterator,
 673                          const void **eltp, gl_list_node_t *nodep)
 674 {
 675   gl_list_t list = iterator->list;
 676   if (iterator->count != list->count)
 677     {
 678       if (iterator->count != list->count + 1)
 679         /* Concurrent modifications were done on the list.  */
 680         abort ();
 681       /* The last returned element was removed.  */
 682       iterator->count--;
 683       iterator->i--;
 684       iterator->j--;
 685     }
 686   if (iterator->i < iterator->j)
 687     {
 688       size_t i = list->offset + iterator->i;
 689       if (i >= list->allocated)
 690         i -= list->allocated;
 691       *eltp = list->elements[i];
 692       if (nodep != NULL)
 693         *nodep = INDEX_TO_NODE (iterator->i);
 694       iterator->i++;
 695       return true;
 696     }
 697   else
 698     return false;
 699 }
 700
 701 static void
 702 gl_carray_iterator_free (_GL_ATTRIBUTE_MAYBE_UNUSED gl_list_iterator_t *iterator)
 703 {
 704 }
 705
 706 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
 707
 708 static size_t _GL_ATTRIBUTE_PURE
 709 gl_carray_sortedlist_indexof_from_to (gl_list_t list,
 710                                       gl_listelement_compar_fn compar,
 711                                       size_t low, size_t high,
 712                                       const void *elt)
 713 {
 714   if (!(low <= high && high <= list->count))
 715     /* Invalid arguments.  */
 716     abort ();
 717   if (low < high)
 718     {
 719       /* At each loop iteration, low < high; for indices < low the values
 720          are smaller than ELT; for indices >= high the values are greater
 721          than ELT.  So, if the element occurs in the list, it is at
 722          low <= position < high.  */
 723       do
 724         {
 725           size_t mid = low + (high - low) / 2; /* low <= mid < high */
 726           size_t i_mid;
 727           int cmp;
 728
 729           i_mid = list->offset + mid;
 730           if (i_mid >= list->allocated)
 731             i_mid -= list->allocated;
 732
 733           cmp = compar (list->elements[i_mid], elt);
 734
 735           if (cmp < 0)
 736             low = mid + 1;
 737           else if (cmp > 0)
 738             high = mid;
 739           else /* cmp == 0 */
 740             {
 741               /* We have an element equal to ELT at index MID.  But we need
 742                  the minimal such index.  */
 743               high = mid;
 744               /* At each loop iteration, low <= high and
 745                    compar (list->elements[i_high], elt) == 0,
 746                  and we know that the first occurrence of the element is at
 747                  low <= position <= high.  */
 748               while (low < high)
 749                 {
 750                   size_t mid2 = low + (high - low) / 2; /* low <= mid2 < high */
 751                   size_t i_mid2;
 752                   int cmp2;
 753
 754                   i_mid2 = list->offset + mid2;
 755                   if (i_mid2 >= list->allocated)
 756                     i_mid2 -= list->allocated;
 757
 758                   cmp2 = compar (list->elements[i_mid2], elt);
 759
 760                   if (cmp2 < 0)
 761                     low = mid2 + 1;
 762                   else if (cmp2 > 0)
 763                     /* The list was not sorted.  */
 764                     abort ();
 765                   else /* cmp2 == 0 */
 766                     {
 767                       if (mid2 == low)
 768                         break;
 769                       high = mid2 - 1;
 770                     }
 771                 }
 772               return low;
 773             }
 774         }
 775       while (low < high);
 776       /* Here low == high.  */
 777     }
 778   return (size_t)(-1);
 779 }
 780
 781 static size_t _GL_ATTRIBUTE_PURE
 782 gl_carray_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
 783                               const void *elt)
 784 {
 785   return gl_carray_sortedlist_indexof_from_to (list, compar, 0, list->count,
 786                                                elt);
 787 }
 788
 789 static gl_list_node_t _GL_ATTRIBUTE_PURE
 790 gl_carray_sortedlist_search_from_to (gl_list_t list,
 791                                      gl_listelement_compar_fn compar,
 792                                      size_t low, size_t high,
 793                                      const void *elt)
 794 {
 795   size_t index =
 796     gl_carray_sortedlist_indexof_from_to (list, compar, low, high, elt);
 797   return INDEX_TO_NODE (index);
 798 }
 799
 800 static gl_list_node_t _GL_ATTRIBUTE_PURE
 801 gl_carray_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
 802                              const void *elt)
 803 {
 804   size_t index =
 805     gl_carray_sortedlist_indexof_from_to (list, compar, 0, list->count, elt);
 806   return INDEX_TO_NODE (index);
 807 }
 808
 809 static gl_list_node_t
 810 gl_carray_sortedlist_nx_add (gl_list_t list, gl_listelement_compar_fn compar,
 811                              const void *elt)
 812 {
 813   size_t count = list->count;
 814   size_t low = 0;
 815   size_t high = count;
 816
 817   /* At each loop iteration, low <= high; for indices < low the values are
 818      smaller than ELT; for indices >= high the values are greater than ELT.  */
 819   while (low < high)
 820     {
 821       size_t mid = low + (high - low) / 2; /* low <= mid < high */
 822       size_t i_mid;
 823       int cmp;
 824
 825       i_mid = list->offset + mid;
 826       if (i_mid >= list->allocated)
 827         i_mid -= list->allocated;
 828
 829       cmp = compar (list->elements[i_mid], elt);
 830
 831       if (cmp < 0)
 832         low = mid + 1;
 833       else if (cmp > 0)
 834         high = mid;
 835       else /* cmp == 0 */
 836         {
 837           low = mid;
 838           break;
 839         }
 840     }
 841   return gl_carray_nx_add_at (list, low, elt);
 842 }
 843
 844 static bool
 845 gl_carray_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
 846                              const void *elt)
 847 {
 848   size_t index = gl_carray_sortedlist_indexof (list, compar, elt);
 849   if (index == (size_t)(-1))
 850     return false;
 851   else
 852     return gl_carray_remove_at (list, index);
 853 }
 854
 855
 856 const struct gl_list_implementation gl_carray_list_implementation =
 857   {
 858     gl_carray_nx_create_empty,
 859     gl_carray_nx_create,
 860     gl_carray_size,
 861     gl_carray_node_value,
 862     gl_carray_node_nx_set_value,
 863     gl_carray_next_node,
 864     gl_carray_previous_node,
 865     gl_carray_first_node,
 866     gl_carray_last_node,
 867     gl_carray_get_at,
 868     gl_carray_nx_set_at,
 869     gl_carray_search_from_to,
 870     gl_carray_indexof_from_to,
 871     gl_carray_nx_add_first,
 872     gl_carray_nx_add_last,
 873     gl_carray_nx_add_before,
 874     gl_carray_nx_add_after,
 875     gl_carray_nx_add_at,
 876     gl_carray_remove_node,
 877     gl_carray_remove_at,
 878     gl_carray_remove,
 879     gl_carray_list_free,
 880     gl_carray_iterator,
 881     gl_carray_iterator_from_to,
 882     gl_carray_iterator_next,
 883     gl_carray_iterator_free,
 884     gl_carray_sortedlist_search,
 885     gl_carray_sortedlist_search_from_to,
 886     gl_carray_sortedlist_indexof,
 887     gl_carray_sortedlist_indexof_from_to,
 888     gl_carray_sortedlist_nx_add,
 889     gl_carray_sortedlist_remove
 890   };