lib/gl_carray_list.c

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