lib/gl_carray_list.c

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