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