lib/gl_carray_list.c

   1 /* Sequential list data type implemented by a circular array.
   2    Copyright (C) 2006-2020 Free Software Foundation, Inc.
   3    Written by Bruno Haible <bruno@clisp.org>, 2006.
   4
   5    This program is free software: you can redistribute it and/or modify
   6    it under the terms of the GNU General Public License as published by
   7    the Free Software Foundation; either version 3 of the License, or
   8    (at your option) any later version.
   9
  10    This program is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13    GNU General Public License for more details.
  14
  15    You should have received a copy of the GNU General Public License
  16    along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
  17
  18 #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 const void * _GL_ATTRIBUTE_PURE
 185 gl_carray_get_at (gl_list_t list, size_t position)
 186 {
 187   size_t count = list->count;
 188   size_t i;
 189
 190   if (!(position < count))
 191     /* Invalid argument.  */
 192     abort ();
 193   i = list->offset + position;
 194   if (i >= list->allocated)
 195     i -= list->allocated;
 196   return list->elements[i];
 197 }
 198
 199 static gl_list_node_t
 200 gl_carray_nx_set_at (gl_list_t list, size_t position, const void *elt)
 201 {
 202   size_t count = list->count;
 203   size_t i;
 204
 205   if (!(position < count))
 206     /* Invalid argument.  */
 207     abort ();
 208   i = list->offset + position;
 209   if (i >= list->allocated)
 210     i -= list->allocated;
 211   list->elements[i] = elt;
 212   return INDEX_TO_NODE (position);
 213 }
 214
 215 static size_t _GL_ATTRIBUTE_PURE
 216 gl_carray_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
 217                            const void *elt)
 218 {
 219   size_t count = list->count;
 220
 221   if (!(start_index <= end_index && end_index <= count))
 222     /* Invalid arguments.  */
 223     abort ();
 224
 225   if (start_index < end_index)
 226     {
 227       gl_listelement_equals_fn equals = list->base.equals_fn;
 228       size_t allocated = list->allocated;
 229       size_t i_end;
 230
 231       i_end = list->offset + end_index;
 232       if (i_end >= allocated)
 233         i_end -= allocated;
 234
 235       if (equals != NULL)
 236         {
 237           size_t i;
 238
 239           i = list->offset + start_index;
 240           if (i >= allocated) /* can only happen if start_index > 0 */
 241             i -= allocated;
 242
 243           for (;;)
 244             {
 245               if (equals (elt, list->elements[i]))
 246                 return (i >= list->offset ? i : i + allocated) - list->offset;
 247               i++;
 248               if (i == allocated)
 249                 i = 0;
 250               if (i == i_end)
 251                 break;
 252             }
 253         }
 254       else
 255         {
 256           size_t i;
 257
 258           i = list->offset + start_index;
 259           if (i >= allocated) /* can only happen if start_index > 0 */
 260             i -= allocated;
 261
 262           for (;;)
 263             {
 264               if (elt == list->elements[i])
 265                 return (i >= list->offset ? i : i + allocated) - list->offset;
 266               i++;
 267               if (i == allocated)
 268                 i = 0;
 269               if (i == i_end)
 270                 break;
 271             }
 272         }
 273     }
 274   return (size_t)(-1);
 275 }
 276
 277 static gl_list_node_t _GL_ATTRIBUTE_PURE
 278 gl_carray_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
 279                           const void *elt)
 280 {
 281   size_t index = gl_carray_indexof_from_to (list, start_index, end_index, elt);
 282   return INDEX_TO_NODE (index);
 283 }
 284
 285 /* Ensure that list->allocated > list->count.
 286    Return 0 upon success, -1 upon out-of-memory.  */
 287 static int
 288 grow (gl_list_t list)
 289 {
 290   size_t new_allocated;
 291   size_t memory_size;
 292   const void **memory;
 293
 294   new_allocated = xtimes (list->allocated, 2);
 295   new_allocated = xsum (new_allocated, 1);
 296   memory_size = xtimes (new_allocated, sizeof (const void *));
 297   if (size_overflow_p (memory_size))
 298     /* Overflow, would lead to out of memory.  */
 299     return -1;
 300   if (list->offset > 0 && list->count > 0)
 301     {
 302       memory = (const void **) malloc (memory_size);
 303       if (memory == NULL)
 304         /* Out of memory.  */
 305         return -1;
 306       if (list->offset + list->count > list->allocated)
 307         {
 308           memcpy (memory, &list->elements[list->offset],
 309                   (list->allocated - list->offset) * sizeof (const void *));
 310           memcpy (memory + (list->allocated - list->offset), list->elements,
 311                   (list->offset + list->count - list->allocated)
 312                   * sizeof (const void *));
 313
 314         }
 315       else
 316         memcpy (memory, &list->elements[list->offset],
 317                 list->count * sizeof (const void *));
 318       if (list->elements != NULL)
 319         free (list->elements);
 320     }
 321   else
 322     {
 323       memory = (const void **) realloc (list->elements, memory_size);
 324       if (memory == NULL)
 325         /* Out of memory.  */
 326         return -1;
 327     }
 328   list->elements = memory;
 329   list->offset = 0;
 330   list->allocated = new_allocated;
 331   return 0;
 332 }
 333
 334 static gl_list_node_t
 335 gl_carray_nx_add_first (gl_list_t list, const void *elt)
 336 {
 337   size_t count = list->count;
 338
 339   if (count == list->allocated)
 340     if (grow (list) < 0)
 341       return NULL;
 342   list->offset = (list->offset == 0 ? list->allocated : list->offset) - 1;
 343   list->elements[list->offset] = elt;
 344   list->count = count + 1;
 345   return INDEX_TO_NODE (0);
 346 }
 347
 348 static gl_list_node_t
 349 gl_carray_nx_add_last (gl_list_t list, const void *elt)
 350 {
 351   size_t count = list->count;
 352   size_t i;
 353
 354   if (count == list->allocated)
 355     if (grow (list) < 0)
 356       return NULL;
 357   i = list->offset + count;
 358   if (i >= list->allocated)
 359     i -= list->allocated;
 360   list->elements[i] = elt;
 361   list->count = count + 1;
 362   return INDEX_TO_NODE (count);
 363 }
 364
 365 static gl_list_node_t
 366 gl_carray_nx_add_at (gl_list_t list, size_t position, const void *elt)
 367 {
 368   size_t count = list->count;
 369   const void **elements;
 370
 371   if (!(position <= count))
 372     /* Invalid argument.  */
 373     abort ();
 374   if (count == list->allocated)
 375     if (grow (list) < 0)
 376       return NULL;
 377   elements = list->elements;
 378   if (position <= (count / 2))
 379     {
 380       /* Shift at most count/2 elements to the left.  */
 381       size_t i2, i;
 382
 383       list->offset = (list->offset == 0 ? list->allocated : list->offset) - 1;
 384
 385       i2 = list->offset + position;
 386       if (i2 >= list->allocated)
 387         {
 388           /* Here we must have list->offset > 0, hence list->allocated > 0.  */
 389           size_t i1 = list->allocated - 1;
 390           i2 -= list->allocated;
 391           for (i = list->offset; i < i1; i++)
 392             elements[i] = elements[i + 1];
 393           elements[i1] = elements[0];
 394           for (i = 0; i < i2; i++)
 395             elements[i] = elements[i + 1];
 396         }
 397       else
 398         {
 399           for (i = list->offset; i < i2; i++)
 400             elements[i] = elements[i + 1];
 401         }
 402       elements[i2] = elt;
 403     }
 404   else
 405     {
 406       /* Shift at most (count+1)/2 elements to the right.  */
 407       size_t i1, i3, i;
 408
 409       i1 = list->offset + position;
 410       i3 = list->offset + count;
 411       if (i1 >= list->allocated)
 412         {
 413           i1 -= list->allocated;
 414           i3 -= list->allocated;
 415           for (i = i3; i > i1; i--)
 416             elements[i] = elements[i - 1];
 417         }
 418       else if (i3 >= list->allocated)
 419         {
 420           /* Here we must have list->offset > 0, hence list->allocated > 0.  */
 421           size_t i2 = list->allocated - 1;
 422           i3 -= list->allocated;
 423           for (i = i3; i > 0; i--)
 424             elements[i] = elements[i - 1];
 425           elements[0] = elements[i2];
 426           for (i = i2; i > i1; i--)
 427             elements[i] = elements[i - 1];
 428         }
 429       else
 430         {
 431           for (i = i3; i > i1; i--)
 432             elements[i] = elements[i - 1];
 433         }
 434       elements[i1] = elt;
 435     }
 436   list->count = count + 1;
 437   return INDEX_TO_NODE (position);
 438 }
 439
 440 static gl_list_node_t
 441 gl_carray_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
 442 {
 443   size_t count = list->count;
 444   uintptr_t index = NODE_TO_INDEX (node);
 445
 446   if (!(index < count))
 447     /* Invalid argument.  */
 448     abort ();
 449   return gl_carray_nx_add_at (list, index, elt);
 450 }
 451
 452 static gl_list_node_t
 453 gl_carray_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
 454 {
 455   size_t count = list->count;
 456   uintptr_t index = NODE_TO_INDEX (node);
 457
 458   if (!(index < count))
 459     /* Invalid argument.  */
 460     abort ();
 461   return gl_carray_nx_add_at (list, index + 1, elt);
 462 }
 463
 464 static bool
 465 gl_carray_remove_at (gl_list_t list, size_t position)
 466 {
 467   size_t count = list->count;
 468   const void **elements;
 469
 470   if (!(position < count))
 471     /* Invalid argument.  */
 472     abort ();
 473   /* Here we know count > 0.  */
 474   elements = list->elements;
 475   if (position <= ((count - 1) / 2))
 476     {
 477       /* Shift at most (count-1)/2 elements to the right.  */
 478       size_t i0, i2, i;
 479
 480       i0 = list->offset;
 481       i2 = list->offset + position;
 482       if (i2 >= list->allocated)
 483         {
 484           /* Here we must have list->offset > 0, hence list->allocated > 0.  */
 485           size_t i1 = list->allocated - 1;
 486           i2 -= list->allocated;
 487           if (list->base.dispose_fn != NULL)
 488             list->base.dispose_fn (elements[i2]);
 489           for (i = i2; i > 0; i--)
 490             elements[i] = elements[i - 1];
 491           elements[0] = elements[i1];
 492           for (i = i1; i > i0; i--)
 493             elements[i] = elements[i - 1];
 494         }
 495       else
 496         {
 497           if (list->base.dispose_fn != NULL)
 498             list->base.dispose_fn (elements[i2]);
 499           for (i = i2; i > i0; i--)
 500             elements[i] = elements[i - 1];
 501         }
 502
 503       i0++;
 504       list->offset = (i0 == list->allocated ? 0 : i0);
 505     }
 506   else
 507     {
 508       /* Shift at most count/2 elements to the left.  */
 509       size_t i1, i3, i;
 510
 511       i1 = list->offset + position;
 512       i3 = list->offset + count - 1;
 513       if (i1 >= list->allocated)
 514         {
 515           i1 -= list->allocated;
 516           i3 -= list->allocated;
 517           if (list->base.dispose_fn != NULL)
 518             list->base.dispose_fn (elements[i1]);
 519           for (i = i1; i < i3; i++)
 520             elements[i] = elements[i + 1];
 521         }
 522       else if (i3 >= list->allocated)
 523         {
 524           /* Here we must have list->offset > 0, hence list->allocated > 0.  */
 525           size_t i2 = list->allocated - 1;
 526           i3 -= list->allocated;
 527           if (list->base.dispose_fn != NULL)
 528             list->base.dispose_fn (elements[i1]);
 529           for (i = i1; i < i2; i++)
 530             elements[i] = elements[i + 1];
 531           elements[i2] = elements[0];
 532           for (i = 0; i < i3; i++)
 533             elements[i] = elements[i + 1];
 534         }
 535       else
 536         {
 537           if (list->base.dispose_fn != NULL)
 538             list->base.dispose_fn (elements[i1]);
 539           for (i = i1; i < i3; i++)
 540             elements[i] = elements[i + 1];
 541         }
 542     }
 543   list->count = count - 1;
 544   return true;
 545 }
 546
 547 static bool
 548 gl_carray_remove_node (gl_list_t list, gl_list_node_t node)
 549 {
 550   size_t count = list->count;
 551   uintptr_t index = NODE_TO_INDEX (node);
 552
 553   if (!(index < count))
 554     /* Invalid argument.  */
 555     abort ();
 556   return gl_carray_remove_at (list, index);
 557 }
 558
 559 static bool
 560 gl_carray_remove (gl_list_t list, const void *elt)
 561 {
 562   size_t position = gl_carray_indexof_from_to (list, 0, list->count, elt);
 563   if (position == (size_t)(-1))
 564     return false;
 565   else
 566     return gl_carray_remove_at (list, position);
 567 }
 568
 569 static void
 570 gl_carray_list_free (gl_list_t list)
 571 {
 572   if (list->elements != NULL)
 573     {
 574       if (list->base.dispose_fn != NULL)
 575         {
 576           size_t count = list->count;
 577
 578           if (count > 0)
 579             {
 580               gl_listelement_dispose_fn dispose = list->base.dispose_fn;
 581               const void **elements = list->elements;
 582               size_t i1 = list->offset;
 583               size_t i3 = list->offset + count - 1;
 584
 585               if (i3 >= list->allocated)
 586                 {
 587                   /* Here we must have list->offset > 0, hence
 588                      list->allocated > 0.  */
 589                   size_t i2 = list->allocated - 1;
 590                   size_t i;
 591
 592                   i3 -= list->allocated;
 593                   for (i = i1; i <= i2; i++)
 594                     dispose (elements[i]);
 595                   for (i = 0; i <= i3; i++)
 596                     dispose (elements[i]);
 597                 }
 598               else
 599                 {
 600                   size_t i;
 601
 602                   for (i = i1; i <= i3; i++)
 603                     dispose (elements[i]);
 604                 }
 605             }
 606         }
 607       free (list->elements);
 608     }
 609   free (list);
 610 }
 611
 612 /* --------------------- gl_list_iterator_t Data Type --------------------- */
 613
 614 static gl_list_iterator_t _GL_ATTRIBUTE_PURE
 615 gl_carray_iterator (gl_list_t list)
 616 {
 617   gl_list_iterator_t result;
 618
 619   result.vtable = list->base.vtable;
 620   result.list = list;
 621   result.count = list->count;
 622   result.i = 0;
 623   result.j = list->count;
 624 #if defined GCC_LINT || defined lint
 625   result.p = 0;
 626   result.q = 0;
 627 #endif
 628
 629   return result;
 630 }
 631
 632 static gl_list_iterator_t _GL_ATTRIBUTE_PURE
 633 gl_carray_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index)
 634 {
 635   gl_list_iterator_t result;
 636
 637   if (!(start_index <= end_index && end_index <= list->count))
 638     /* Invalid arguments.  */
 639     abort ();
 640   result.vtable = list->base.vtable;
 641   result.list = list;
 642   result.count = list->count;
 643   result.i = start_index;
 644   result.j = end_index;
 645 #if defined GCC_LINT || defined lint
 646   result.p = 0;
 647   result.q = 0;
 648 #endif
 649
 650   return result;
 651 }
 652
 653 static bool
 654 gl_carray_iterator_next (gl_list_iterator_t *iterator,
 655                          const void **eltp, gl_list_node_t *nodep)
 656 {
 657   gl_list_t list = iterator->list;
 658   if (iterator->count != list->count)
 659     {
 660       if (iterator->count != list->count + 1)
 661         /* Concurrent modifications were done on the list.  */
 662         abort ();
 663       /* The last returned element was removed.  */
 664       iterator->count--;
 665       iterator->i--;
 666       iterator->j--;
 667     }
 668   if (iterator->i < iterator->j)
 669     {
 670       size_t i = list->offset + iterator->i;
 671       if (i >= list->allocated)
 672         i -= list->allocated;
 673       *eltp = list->elements[i];
 674       if (nodep != NULL)
 675         *nodep = INDEX_TO_NODE (iterator->i);
 676       iterator->i++;
 677       return true;
 678     }
 679   else
 680     return false;
 681 }
 682
 683 static void
 684 gl_carray_iterator_free (gl_list_iterator_t *iterator _GL_ATTRIBUTE_MAYBE_UNUSED)
 685 {
 686 }
 687
 688 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
 689
 690 static size_t _GL_ATTRIBUTE_PURE
 691 gl_carray_sortedlist_indexof_from_to (gl_list_t list,
 692                                       gl_listelement_compar_fn compar,
 693                                       size_t low, size_t high,
 694                                       const void *elt)
 695 {
 696   if (!(low <= high && high <= list->count))
 697     /* Invalid arguments.  */
 698     abort ();
 699   if (low < high)
 700     {
 701       /* At each loop iteration, low < high; for indices < low the values
 702          are smaller than ELT; for indices >= high the values are greater
 703          than ELT.  So, if the element occurs in the list, it is at
 704          low <= position < high.  */
 705       do
 706         {
 707           size_t mid = low + (high - low) / 2; /* low <= mid < high */
 708           size_t i_mid;
 709           int cmp;
 710
 711           i_mid = list->offset + mid;
 712           if (i_mid >= list->allocated)
 713             i_mid -= list->allocated;
 714
 715           cmp = compar (list->elements[i_mid], elt);
 716
 717           if (cmp < 0)
 718             low = mid + 1;
 719           else if (cmp > 0)
 720             high = mid;
 721           else /* cmp == 0 */
 722             {
 723               /* We have an element equal to ELT at index MID.  But we need
 724                  the minimal such index.  */
 725               high = mid;
 726               /* At each loop iteration, low <= high and
 727                    compar (list->elements[i_high], elt) == 0,
 728                  and we know that the first occurrence of the element is at
 729                  low <= position <= high.  */
 730               while (low < high)
 731                 {
 732                   size_t mid2 = low + (high - low) / 2; /* low <= mid2 < high */
 733                   size_t i_mid2;
 734                   int cmp2;
 735
 736                   i_mid2 = list->offset + mid2;
 737                   if (i_mid2 >= list->allocated)
 738                     i_mid2 -= list->allocated;
 739
 740                   cmp2 = compar (list->elements[i_mid2], elt);
 741
 742                   if (cmp2 < 0)
 743                     low = mid2 + 1;
 744                   else if (cmp2 > 0)
 745                     /* The list was not sorted.  */
 746                     abort ();
 747                   else /* cmp2 == 0 */
 748                     {
 749                       if (mid2 == low)
 750                         break;
 751                       high = mid2 - 1;
 752                     }
 753                 }
 754               return low;
 755             }
 756         }
 757       while (low < high);
 758       /* Here low == high.  */
 759     }
 760   return (size_t)(-1);
 761 }
 762
 763 static size_t _GL_ATTRIBUTE_PURE
 764 gl_carray_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
 765                               const void *elt)
 766 {
 767   return gl_carray_sortedlist_indexof_from_to (list, compar, 0, list->count,
 768                                                elt);
 769 }
 770
 771 static gl_list_node_t _GL_ATTRIBUTE_PURE
 772 gl_carray_sortedlist_search_from_to (gl_list_t list,
 773                                      gl_listelement_compar_fn compar,
 774                                      size_t low, size_t high,
 775                                      const void *elt)
 776 {
 777   size_t index =
 778     gl_carray_sortedlist_indexof_from_to (list, compar, low, high, elt);
 779   return INDEX_TO_NODE (index);
 780 }
 781
 782 static gl_list_node_t _GL_ATTRIBUTE_PURE
 783 gl_carray_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
 784                              const void *elt)
 785 {
 786   size_t index =
 787     gl_carray_sortedlist_indexof_from_to (list, compar, 0, list->count, elt);
 788   return INDEX_TO_NODE (index);
 789 }
 790
 791 static gl_list_node_t
 792 gl_carray_sortedlist_nx_add (gl_list_t list, gl_listelement_compar_fn compar,
 793                              const void *elt)
 794 {
 795   size_t count = list->count;
 796   size_t low = 0;
 797   size_t high = count;
 798
 799   /* At each loop iteration, low <= high; for indices < low the values are
 800      smaller than ELT; for indices >= high the values are greater than ELT.  */
 801   while (low < high)
 802     {
 803       size_t mid = low + (high - low) / 2; /* low <= mid < high */
 804       size_t i_mid;
 805       int cmp;
 806
 807       i_mid = list->offset + mid;
 808       if (i_mid >= list->allocated)
 809         i_mid -= list->allocated;
 810
 811       cmp = compar (list->elements[i_mid], elt);
 812
 813       if (cmp < 0)
 814         low = mid + 1;
 815       else if (cmp > 0)
 816         high = mid;
 817       else /* cmp == 0 */
 818         {
 819           low = mid;
 820           break;
 821         }
 822     }
 823   return gl_carray_nx_add_at (list, low, elt);
 824 }
 825
 826 static bool
 827 gl_carray_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
 828                              const void *elt)
 829 {
 830   size_t index = gl_carray_sortedlist_indexof (list, compar, elt);
 831   if (index == (size_t)(-1))
 832     return false;
 833   else
 834     return gl_carray_remove_at (list, index);
 835 }
 836
 837
 838 const struct gl_list_implementation gl_carray_list_implementation =
 839   {
 840     gl_carray_nx_create_empty,
 841     gl_carray_nx_create,
 842     gl_carray_size,
 843     gl_carray_node_value,
 844     gl_carray_node_nx_set_value,
 845     gl_carray_next_node,
 846     gl_carray_previous_node,
 847     gl_carray_get_at,
 848     gl_carray_nx_set_at,
 849     gl_carray_search_from_to,
 850     gl_carray_indexof_from_to,
 851     gl_carray_nx_add_first,
 852     gl_carray_nx_add_last,
 853     gl_carray_nx_add_before,
 854     gl_carray_nx_add_after,
 855     gl_carray_nx_add_at,
 856     gl_carray_remove_node,
 857     gl_carray_remove_at,
 858     gl_carray_remove,
 859     gl_carray_list_free,
 860     gl_carray_iterator,
 861     gl_carray_iterator_from_to,
 862     gl_carray_iterator_next,
 863     gl_carray_iterator_free,
 864     gl_carray_sortedlist_search,
 865     gl_carray_sortedlist_search_from_to,
 866     gl_carray_sortedlist_indexof,
 867     gl_carray_sortedlist_indexof_from_to,
 868     gl_carray_sortedlist_nx_add,
 869     gl_carray_sortedlist_remove
 870   };