lib/gl_carray_list.c

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