1/* Sequential list data type implemented by a linked list. 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/* Common code of gl_linked_list.c and gl_linkedhash_list.c. */ 19 20/* If the symbol SIGNAL_SAFE_LIST is defined, the code is compiled in such 21 a way that a gl_list_t data structure may be used from within a signal 22 handler. The operations allowed in the signal handler are: 23 gl_list_iterator, gl_list_iterator_next, gl_list_iterator_free. 24 The list and node fields that are therefore accessed from the signal handler 25 are: 26 list->root, node->next, node->value. 27 We are careful to make modifications to these fields only in an order 28 that maintains the consistency of the list data structure at any moment, 29 and we use 'volatile' assignments to prevent the compiler from reordering 30 such assignments. */ 31#ifdef SIGNAL_SAFE_LIST 32# define ASYNCSAFE(type) *(volatile type *)& 33#else 34# define ASYNCSAFE(type) 35#endif 36 37/* -------------------------- gl_list_t Data Type -------------------------- */ 38 39static gl_list_t 40gl_linked_create_empty (gl_list_implementation_t implementation, 41 gl_listelement_equals_fn equals_fn, 42 gl_listelement_hashcode_fn hashcode_fn, 43 gl_listelement_dispose_fn dispose_fn, 44 bool allow_duplicates) 45{ 46 struct gl_list_impl *list = XMALLOC (struct gl_list_impl); 47 48 list->base.vtable = implementation; 49 list->base.equals_fn = equals_fn; 50 list->base.hashcode_fn = hashcode_fn; 51 list->base.dispose_fn = dispose_fn; 52 list->base.allow_duplicates = allow_duplicates; 53#if WITH_HASHTABLE 54 list->table_size = 11; 55 list->table = XCALLOC (list->table_size, gl_hash_entry_t); 56#endif 57 list->root.next = &list->root; 58 list->root.prev = &list->root; 59 list->count = 0; 60 61 return list; 62} 63 64static gl_list_t 65gl_linked_create (gl_list_implementation_t implementation, 66 gl_listelement_equals_fn equals_fn, 67 gl_listelement_hashcode_fn hashcode_fn, 68 gl_listelement_dispose_fn dispose_fn, 69 bool allow_duplicates, 70 size_t count, const void **contents) 71{ 72 struct gl_list_impl *list = XMALLOC (struct gl_list_impl); 73 gl_list_node_t tail; 74 75 list->base.vtable = implementation; 76 list->base.equals_fn = equals_fn; 77 list->base.hashcode_fn = hashcode_fn; 78 list->base.dispose_fn = dispose_fn; 79 list->base.allow_duplicates = allow_duplicates; 80#if WITH_HASHTABLE 81 { 82 size_t estimate = xsum (count, count / 2); /* 1.5 * count */ 83 if (estimate < 10) 84 estimate = 10; 85 list->table_size = next_prime (estimate); 86 list->table = XCALLOC (list->table_size, gl_hash_entry_t); 87 } 88#endif 89 list->count = count; 90 tail = &list->root; 91 for (; count > 0; contents++, count--) 92 { 93 gl_list_node_t node = XMALLOC (struct gl_list_node_impl); 94 95 node->value = *contents; 96#if WITH_HASHTABLE 97 node->h.hashcode = 98 (list->base.hashcode_fn != NULL 99 ? list->base.hashcode_fn (node->value) 100 : (size_t)(uintptr_t) node->value); 101 102 /* Add node to the hash table. */ 103 add_to_bucket (list, node); 104#endif 105 106 /* Add node to the list. */ 107 node->prev = tail; 108 tail->next = node; 109 tail = node; 110 } 111 tail->next = &list->root; 112 list->root.prev = tail; 113 114 return list; 115} 116 117static size_t 118gl_linked_size (gl_list_t list) 119{ 120 return list->count; 121} 122 123static const void * 124gl_linked_node_value (gl_list_t list, gl_list_node_t node) 125{ 126 return node->value; 127} 128 129static gl_list_node_t 130gl_linked_next_node (gl_list_t list, gl_list_node_t node) 131{ 132 return (node->next != &list->root ? node->next : NULL); 133} 134 135static gl_list_node_t 136gl_linked_previous_node (gl_list_t list, gl_list_node_t node) 137{ 138 return (node->prev != &list->root ? node->prev : NULL); 139} 140 141static const void * 142gl_linked_get_at (gl_list_t list, size_t position) 143{ 144 size_t count = list->count; 145 gl_list_node_t node; 146 147 if (!(position < count)) 148 /* Invalid argument. */ 149 abort (); 150 /* Here we know count > 0. */ 151 if (position <= ((count - 1) / 2)) 152 { 153 node = list->root.next; 154 for (; position > 0; position--) 155 node = node->next; 156 } 157 else 158 { 159 position = count - 1 - position; 160 node = list->root.prev; 161 for (; position > 0; position--) 162 node = node->prev; 163 } 164 return node->value; 165} 166 167static gl_list_node_t 168gl_linked_set_at (gl_list_t list, size_t position, const void *elt) 169{ 170 size_t count = list->count; 171 gl_list_node_t node; 172 173 if (!(position < count)) 174 /* Invalid argument. */ 175 abort (); 176 /* Here we know count > 0. */ 177 if (position <= ((count - 1) / 2)) 178 { 179 node = list->root.next; 180 for (; position > 0; position--) 181 node = node->next; 182 } 183 else 184 { 185 position = count - 1 - position; 186 node = list->root.prev; 187 for (; position > 0; position--) 188 node = node->prev; 189 } 190#if WITH_HASHTABLE 191 if (elt != node->value) 192 { 193 size_t new_hashcode = 194 (list->base.hashcode_fn != NULL 195 ? list->base.hashcode_fn (elt) 196 : (size_t)(uintptr_t) elt); 197 198 if (new_hashcode != node->h.hashcode) 199 { 200 remove_from_bucket (list, node); 201 node->value = elt; 202 node->h.hashcode = new_hashcode; 203 add_to_bucket (list, node); 204 } 205 else 206 node->value = elt; 207 } 208#else 209 node->value = elt; 210#endif 211 return node; 212} 213 214static gl_list_node_t 215gl_linked_search_from_to (gl_list_t list, size_t start_index, size_t end_index, 216 const void *elt) 217{ 218 size_t count = list->count; 219 220 if (!(start_index <= end_index && end_index <= count)) 221 /* Invalid arguments. */ 222 abort (); 223 { 224#if WITH_HASHTABLE 225 size_t hashcode = 226 (list->base.hashcode_fn != NULL 227 ? list->base.hashcode_fn (elt) 228 : (size_t)(uintptr_t) elt); 229 size_t bucket = hashcode % list->table_size; 230 gl_listelement_equals_fn equals = list->base.equals_fn; 231 232 if (!list->base.allow_duplicates) 233 { 234 /* Look for the first match in the hash bucket. */ 235 gl_list_node_t found = NULL; 236 gl_list_node_t node; 237 238 for (node = (gl_list_node_t) list->table[bucket]; 239 node != NULL; 240 node = (gl_list_node_t) node->h.hash_next) 241 if (node->h.hashcode == hashcode 242 && (equals != NULL 243 ? equals (elt, node->value) 244 : elt == node->value)) 245 { 246 found = node; 247 break; 248 } 249 if (start_index > 0) 250 /* Look whether found's index is < start_index. */ 251 for (node = list->root.next; ; node = node->next) 252 { 253 if (node == found) 254 return NULL; 255 if (--start_index == 0) 256 break; 257 } 258 if (end_index < count) 259 /* Look whether found's index is >= end_index. */ 260 { 261 end_index = count - end_index; 262 for (node = list->root.prev; ; node = node->prev) 263 { 264 if (node == found) 265 return NULL; 266 if (--end_index == 0) 267 break; 268 } 269 } 270 return found; 271 } 272 else 273 { 274 /* Look whether there is more than one match in the hash bucket. */ 275 bool multiple_matches = false; 276 gl_list_node_t first_match = NULL; 277 gl_list_node_t node; 278 279 for (node = (gl_list_node_t) list->table[bucket]; 280 node != NULL; 281 node = (gl_list_node_t) node->h.hash_next) 282 if (node->h.hashcode == hashcode 283 && (equals != NULL 284 ? equals (elt, node->value) 285 : elt == node->value)) 286 { 287 if (first_match == NULL) 288 first_match = node; 289 else 290 { 291 multiple_matches = true; 292 break; 293 } 294 } 295 if (multiple_matches) 296 { 297 /* We need the match with the smallest index. But we don't have 298 a fast mapping node -> index. So we have to walk the list. */ 299 end_index -= start_index; 300 node = list->root.next; 301 for (; start_index > 0; start_index--) 302 node = node->next; 303 304 for (; 305 end_index > 0; 306 node = node->next, end_index--) 307 if (node->h.hashcode == hashcode 308 && (equals != NULL 309 ? equals (elt, node->value) 310 : elt == node->value)) 311 return node; 312 /* The matches must have all been at indices < start_index or 313 >= end_index. */ 314 return NULL; 315 } 316 else 317 { 318 if (start_index > 0) 319 /* Look whether first_match's index is < start_index. */ 320 for (node = list->root.next; node != &list->root; node = node->next) 321 { 322 if (node == first_match) 323 return NULL; 324 if (--start_index == 0) 325 break; 326 } 327 if (end_index < list->count) 328 /* Look whether first_match's index is >= end_index. */ 329 { 330 end_index = list->count - end_index; 331 for (node = list->root.prev; ; node = node->prev) 332 { 333 if (node == first_match) 334 return NULL; 335 if (--end_index == 0) 336 break; 337 } 338 } 339 return first_match; 340 } 341 } 342#else 343 gl_listelement_equals_fn equals = list->base.equals_fn; 344 gl_list_node_t node = list->root.next; 345 346 end_index -= start_index; 347 for (; start_index > 0; start_index--) 348 node = node->next; 349 350 if (equals != NULL) 351 { 352 for (; end_index > 0; node = node->next, end_index--) 353 if (equals (elt, node->value)) 354 return node; 355 } 356 else 357 { 358 for (; end_index > 0; node = node->next, end_index--) 359 if (elt == node->value) 360 return node; 361 } 362 return NULL; 363#endif 364 } 365} 366 367static size_t 368gl_linked_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index, 369 const void *elt) 370{ 371 size_t count = list->count; 372 373 if (!(start_index <= end_index && end_index <= count)) 374 /* Invalid arguments. */ 375 abort (); 376 { 377#if WITH_HASHTABLE 378 /* Here the hash table doesn't help much. It only allows us to minimize 379 the number of equals() calls, by looking up first the node and then 380 its index. */ 381 size_t hashcode = 382 (list->base.hashcode_fn != NULL 383 ? list->base.hashcode_fn (elt) 384 : (size_t)(uintptr_t) elt); 385 size_t bucket = hashcode % list->table_size; 386 gl_listelement_equals_fn equals = list->base.equals_fn; 387 gl_list_node_t node; 388 389 /* First step: Look up the node. */ 390 if (!list->base.allow_duplicates) 391 { 392 /* Look for the first match in the hash bucket. */ 393 for (node = (gl_list_node_t) list->table[bucket]; 394 node != NULL; 395 node = (gl_list_node_t) node->h.hash_next) 396 if (node->h.hashcode == hashcode 397 && (equals != NULL 398 ? equals (elt, node->value) 399 : elt == node->value)) 400 break; 401 } 402 else 403 { 404 /* Look whether there is more than one match in the hash bucket. */ 405 bool multiple_matches = false; 406 gl_list_node_t first_match = NULL; 407 408 for (node = (gl_list_node_t) list->table[bucket]; 409 node != NULL; 410 node = (gl_list_node_t) node->h.hash_next) 411 if (node->h.hashcode == hashcode 412 && (equals != NULL 413 ? equals (elt, node->value) 414 : elt == node->value)) 415 { 416 if (first_match == NULL) 417 first_match = node; 418 else 419 { 420 multiple_matches = true; 421 break; 422 } 423 } 424 if (multiple_matches) 425 { 426 /* We need the match with the smallest index. But we don't have 427 a fast mapping node -> index. So we have to walk the list. */ 428 size_t index; 429 430 index = start_index; 431 node = list->root.next; 432 for (; start_index > 0; start_index--) 433 node = node->next; 434 435 for (; 436 index < end_index; 437 node = node->next, index++) 438 if (node->h.hashcode == hashcode 439 && (equals != NULL 440 ? equals (elt, node->value) 441 : elt == node->value)) 442 return index; 443 /* The matches must have all been at indices < start_index or 444 >= end_index. */ 445 return (size_t)(-1); 446 } 447 node = first_match; 448 } 449 450 /* Second step: Look up the index of the node. */ 451 if (node == NULL) 452 return (size_t)(-1); 453 else 454 { 455 size_t index = 0; 456 457 for (; node->prev != &list->root; node = node->prev) 458 index++; 459 460 if (index >= start_index && index < end_index) 461 return index; 462 else 463 return (size_t)(-1); 464 } 465#else 466 gl_listelement_equals_fn equals = list->base.equals_fn; 467 size_t index = start_index; 468 gl_list_node_t node = list->root.next; 469 470 for (; start_index > 0; start_index--) 471 node = node->next; 472 473 if (equals != NULL) 474 { 475 for (; 476 index < end_index; 477 node = node->next, index++) 478 if (equals (elt, node->value)) 479 return index; 480 } 481 else 482 { 483 for (; 484 index < end_index; 485 node = node->next, index++) 486 if (elt == node->value) 487 return index; 488 } 489 return (size_t)(-1); 490#endif 491 } 492} 493 494static gl_list_node_t 495gl_linked_add_first (gl_list_t list, const void *elt) 496{ 497 gl_list_node_t node = XMALLOC (struct gl_list_node_impl); 498 499 ASYNCSAFE(const void *) node->value = elt; 500#if WITH_HASHTABLE 501 node->h.hashcode = 502 (list->base.hashcode_fn != NULL 503 ? list->base.hashcode_fn (node->value) 504 : (size_t)(uintptr_t) node->value); 505 506 /* Add node to the hash table. */ 507 add_to_bucket (list, node); 508#endif 509 510 /* Add node to the list. */ 511 node->prev = &list->root; 512 ASYNCSAFE(gl_list_node_t) node->next = list->root.next; 513 node->next->prev = node; 514 ASYNCSAFE(gl_list_node_t) list->root.next = node; 515 list->count++; 516 517#if WITH_HASHTABLE 518 hash_resize_after_add (list); 519#endif 520 521 return node; 522} 523 524static gl_list_node_t 525gl_linked_add_last (gl_list_t list, const void *elt) 526{ 527 gl_list_node_t node = XMALLOC (struct gl_list_node_impl); 528 529 ASYNCSAFE(const void *) node->value = elt; 530#if WITH_HASHTABLE 531 node->h.hashcode = 532 (list->base.hashcode_fn != NULL 533 ? list->base.hashcode_fn (node->value) 534 : (size_t)(uintptr_t) node->value); 535 536 /* Add node to the hash table. */ 537 add_to_bucket (list, node); 538#endif 539 540 /* Add node to the list. */ 541 ASYNCSAFE(gl_list_node_t) node->next = &list->root; 542 node->prev = list->root.prev; 543 ASYNCSAFE(gl_list_node_t) node->prev->next = node; 544 list->root.prev = node; 545 list->count++; 546 547#if WITH_HASHTABLE 548 hash_resize_after_add (list); 549#endif 550 551 return node; 552} 553 554static gl_list_node_t 555gl_linked_add_before (gl_list_t list, gl_list_node_t node, const void *elt) 556{ 557 gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl); 558 559 ASYNCSAFE(const void *) new_node->value = elt; 560#if WITH_HASHTABLE 561 new_node->h.hashcode = 562 (list->base.hashcode_fn != NULL 563 ? list->base.hashcode_fn (new_node->value) 564 : (size_t)(uintptr_t) new_node->value); 565 566 /* Add new_node to the hash table. */ 567 add_to_bucket (list, new_node); 568#endif 569 570 /* Add new_node to the list. */ 571 ASYNCSAFE(gl_list_node_t) new_node->next = node; 572 new_node->prev = node->prev; 573 ASYNCSAFE(gl_list_node_t) new_node->prev->next = new_node; 574 node->prev = new_node; 575 list->count++; 576 577#if WITH_HASHTABLE 578 hash_resize_after_add (list); 579#endif 580 581 return new_node; 582} 583 584static gl_list_node_t 585gl_linked_add_after (gl_list_t list, gl_list_node_t node, const void *elt) 586{ 587 gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl); 588 589 ASYNCSAFE(const void *) new_node->value = elt; 590#if WITH_HASHTABLE 591 new_node->h.hashcode = 592 (list->base.hashcode_fn != NULL 593 ? list->base.hashcode_fn (new_node->value) 594 : (size_t)(uintptr_t) new_node->value); 595 596 /* Add new_node to the hash table. */ 597 add_to_bucket (list, new_node); 598#endif 599 600 /* Add new_node to the list. */ 601 new_node->prev = node; 602 ASYNCSAFE(gl_list_node_t) new_node->next = node->next; 603 new_node->next->prev = new_node; 604 ASYNCSAFE(gl_list_node_t) node->next = new_node; 605 list->count++; 606 607#if WITH_HASHTABLE 608 hash_resize_after_add (list); 609#endif 610 611 return new_node; 612} 613 614static gl_list_node_t 615gl_linked_add_at (gl_list_t list, size_t position, const void *elt) 616{ 617 size_t count = list->count; 618 gl_list_node_t new_node; 619 620 if (!(position <= count)) 621 /* Invalid argument. */ 622 abort (); 623 624 new_node = XMALLOC (struct gl_list_node_impl); 625 ASYNCSAFE(const void *) new_node->value = elt; 626#if WITH_HASHTABLE 627 new_node->h.hashcode = 628 (list->base.hashcode_fn != NULL 629 ? list->base.hashcode_fn (new_node->value) 630 : (size_t)(uintptr_t) new_node->value); 631 632 /* Add new_node to the hash table. */ 633 add_to_bucket (list, new_node); 634#endif 635 636 /* Add new_node to the list. */ 637 if (position <= (count / 2)) 638 { 639 gl_list_node_t node; 640 641 node = &list->root; 642 for (; position > 0; position--) 643 node = node->next; 644 new_node->prev = node; 645 ASYNCSAFE(gl_list_node_t) new_node->next = node->next; 646 new_node->next->prev = new_node; 647 ASYNCSAFE(gl_list_node_t) node->next = new_node; 648 } 649 else 650 { 651 gl_list_node_t node; 652 653 position = count - position; 654 node = &list->root; 655 for (; position > 0; position--) 656 node = node->prev; 657 ASYNCSAFE(gl_list_node_t) new_node->next = node; 658 new_node->prev = node->prev; 659 ASYNCSAFE(gl_list_node_t) new_node->prev->next = new_node; 660 node->prev = new_node; 661 } 662 list->count++; 663 664#if WITH_HASHTABLE 665 hash_resize_after_add (list); 666#endif 667 668 return new_node; 669} 670 671static bool 672gl_linked_remove_node (gl_list_t list, gl_list_node_t node) 673{ 674 gl_list_node_t prev; 675 gl_list_node_t next; 676 677#if WITH_HASHTABLE 678 /* Remove node from the hash table. */ 679 remove_from_bucket (list, node); 680#endif 681 682 /* Remove node from the list. */ 683 prev = node->prev; 684 next = node->next; 685 686 ASYNCSAFE(gl_list_node_t) prev->next = next; 687 next->prev = prev; 688 list->count--; 689 690 if (list->base.dispose_fn != NULL) 691 list->base.dispose_fn (node->value); 692 free (node); 693 return true; 694} 695 696static bool 697gl_linked_remove_at (gl_list_t list, size_t position) 698{ 699 size_t count = list->count; 700 gl_list_node_t removed_node; 701 702 if (!(position < count)) 703 /* Invalid argument. */ 704 abort (); 705 /* Here we know count > 0. */ 706 if (position <= ((count - 1) / 2)) 707 { 708 gl_list_node_t node; 709 gl_list_node_t after_removed; 710 711 node = &list->root; 712 for (; position > 0; position--) 713 node = node->next; 714 removed_node = node->next; 715 after_removed = node->next->next; 716 ASYNCSAFE(gl_list_node_t) node->next = after_removed; 717 after_removed->prev = node; 718 } 719 else 720 { 721 gl_list_node_t node; 722 gl_list_node_t before_removed; 723 724 position = count - 1 - position; 725 node = &list->root; 726 for (; position > 0; position--) 727 node = node->prev; 728 removed_node = node->prev; 729 before_removed = node->prev->prev; 730 node->prev = before_removed; 731 ASYNCSAFE(gl_list_node_t) before_removed->next = node; 732 } 733#if WITH_HASHTABLE 734 remove_from_bucket (list, removed_node); 735#endif 736 list->count--; 737 738 if (list->base.dispose_fn != NULL) 739 list->base.dispose_fn (removed_node->value); 740 free (removed_node); 741 return true; 742} 743 744static bool 745gl_linked_remove (gl_list_t list, const void *elt) 746{ 747 gl_list_node_t node = gl_linked_search_from_to (list, 0, list->count, elt); 748 749 if (node != NULL) 750 return gl_linked_remove_node (list, node); 751 else 752 return false; 753} 754 755static void 756gl_linked_list_free (gl_list_t list) 757{ 758 gl_listelement_dispose_fn dispose = list->base.dispose_fn; 759 gl_list_node_t node; 760 761 for (node = list->root.next; node != &list->root; ) 762 { 763 gl_list_node_t next = node->next; 764 if (dispose != NULL) 765 dispose (node->value); 766 free (node); 767 node = next; 768 } 769#if WITH_HASHTABLE 770 free (list->table); 771#endif 772 free (list); 773} 774 775/* --------------------- gl_list_iterator_t Data Type --------------------- */ 776 777static gl_list_iterator_t 778gl_linked_iterator (gl_list_t list) 779{ 780 gl_list_iterator_t result; 781 782 result.vtable = list->base.vtable; 783 result.list = list; 784 result.p = list->root.next; 785 result.q = &list->root; 786#ifdef lint 787 result.i = 0; 788 result.j = 0; 789 result.count = 0; 790#endif 791 792 return result; 793} 794 795static gl_list_iterator_t 796gl_linked_iterator_from_to (gl_list_t list, 797 size_t start_index, size_t end_index) 798{ 799 gl_list_iterator_t result; 800 size_t n1, n2, n3; 801 802 if (!(start_index <= end_index && end_index <= list->count)) 803 /* Invalid arguments. */ 804 abort (); 805 result.vtable = list->base.vtable; 806 result.list = list; 807 n1 = start_index; 808 n2 = end_index - start_index; 809 n3 = list->count - end_index; 810 /* Find the maximum among n1, n2, n3, so as to reduce the number of 811 loop iterations to n1 + n2 + n3 - max(n1,n2,n3). */ 812 if (n1 > n2 && n1 > n3) 813 { 814 /* n1 is the maximum, use n2 and n3. */ 815 gl_list_node_t node; 816 size_t i; 817 818 node = &list->root; 819 for (i = n3; i > 0; i--) 820 node = node->prev; 821 result.q = node; 822 for (i = n2; i > 0; i--) 823 node = node->prev; 824 result.p = node; 825 } 826 else if (n2 > n3) 827 { 828 /* n2 is the maximum, use n1 and n3. */ 829 gl_list_node_t node; 830 size_t i; 831 832 node = list->root.next; 833 for (i = n1; i > 0; i--) 834 node = node->next; 835 result.p = node; 836 837 node = &list->root; 838 for (i = n3; i > 0; i--) 839 node = node->prev; 840 result.q = node; 841 } 842 else 843 { 844 /* n3 is the maximum, use n1 and n2. */ 845 gl_list_node_t node; 846 size_t i; 847 848 node = list->root.next; 849 for (i = n1; i > 0; i--) 850 node = node->next; 851 result.p = node; 852 for (i = n2; i > 0; i--) 853 node = node->next; 854 result.q = node; 855 } 856 857#ifdef lint 858 result.i = 0; 859 result.j = 0; 860 result.count = 0; 861#endif 862 863 return result; 864} 865 866static bool 867gl_linked_iterator_next (gl_list_iterator_t *iterator, 868 const void **eltp, gl_list_node_t *nodep) 869{ 870 if (iterator->p != iterator->q) 871 { 872 gl_list_node_t node = (gl_list_node_t) iterator->p; 873 *eltp = node->value; 874 if (nodep != NULL) 875 *nodep = node; 876 iterator->p = node->next; 877 return true; 878 } 879 else 880 return false; 881} 882 883static void 884gl_linked_iterator_free (gl_list_iterator_t *iterator) 885{ 886} 887 888/* ---------------------- Sorted gl_list_t Data Type ---------------------- */ 889 890static gl_list_node_t 891gl_linked_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar, 892 const void *elt) 893{ 894 gl_list_node_t node; 895 896 for (node = list->root.next; node != &list->root; node = node->next) 897 { 898 int cmp = compar (node->value, elt); 899 900 if (cmp > 0) 901 break; 902 if (cmp == 0) 903 return node; 904 } 905 return NULL; 906} 907 908static gl_list_node_t 909gl_linked_sortedlist_search_from_to (gl_list_t list, 910 gl_listelement_compar_fn compar, 911 size_t low, size_t high, 912 const void *elt) 913{ 914 size_t count = list->count; 915 916 if (!(low <= high && high <= list->count)) 917 /* Invalid arguments. */ 918 abort (); 919 920 high -= low; 921 if (high > 0) 922 { 923 /* Here we know low < count. */ 924 size_t position = low; 925 gl_list_node_t node; 926 927 if (position <= ((count - 1) / 2)) 928 { 929 node = list->root.next; 930 for (; position > 0; position--) 931 node = node->next; 932 } 933 else 934 { 935 position = count - 1 - position; 936 node = list->root.prev; 937 for (; position > 0; position--) 938 node = node->prev; 939 } 940 941 do 942 { 943 int cmp = compar (node->value, elt); 944 945 if (cmp > 0) 946 break; 947 if (cmp == 0) 948 return node; 949 node = node->next; 950 } 951 while (--high > 0); 952 } 953 return NULL; 954} 955 956static size_t 957gl_linked_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, 958 const void *elt) 959{ 960 gl_list_node_t node; 961 size_t index; 962 963 for (node = list->root.next, index = 0; 964 node != &list->root; 965 node = node->next, index++) 966 { 967 int cmp = compar (node->value, elt); 968 969 if (cmp > 0) 970 break; 971 if (cmp == 0) 972 return index; 973 } 974 return (size_t)(-1); 975} 976 977static size_t 978gl_linked_sortedlist_indexof_from_to (gl_list_t list, 979 gl_listelement_compar_fn compar, 980 size_t low, size_t high, 981 const void *elt) 982{ 983 size_t count = list->count; 984 985 if (!(low <= high && high <= list->count)) 986 /* Invalid arguments. */ 987 abort (); 988 989 high -= low; 990 if (high > 0) 991 { 992 /* Here we know low < count. */ 993 size_t index = low; 994 size_t position = low; 995 gl_list_node_t node; 996 997 if (position <= ((count - 1) / 2)) 998 { 999 node = list->root.next; 1000 for (; position > 0; position--) 1001 node = node->next; 1002 } 1003 else 1004 { 1005 position = count - 1 - position; 1006 node = list->root.prev; 1007 for (; position > 0; position--) 1008 node = node->prev; 1009 } 1010 1011 do 1012 { 1013 int cmp = compar (node->value, elt); 1014 1015 if (cmp > 0) 1016 break; 1017 if (cmp == 0) 1018 return index; 1019 node = node->next; 1020 index++; 1021 } 1022 while (--high > 0); 1023 } 1024 return (size_t)(-1); 1025} 1026 1027static gl_list_node_t 1028gl_linked_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar, 1029 const void *elt) 1030{ 1031 gl_list_node_t node; 1032 1033 for (node = list->root.next; node != &list->root; node = node->next) 1034 if (compar (node->value, elt) >= 0) 1035 return gl_linked_add_before (list, node, elt); 1036 return gl_linked_add_last (list, elt); 1037} 1038 1039static bool 1040gl_linked_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar, 1041 const void *elt) 1042{ 1043 gl_list_node_t node; 1044 1045 for (node = list->root.next; node != &list->root; node = node->next) 1046 { 1047 int cmp = compar (node->value, elt); 1048 1049 if (cmp > 0) 1050 break; 1051 if (cmp == 0) 1052 return gl_linked_remove_node (list, node); 1053 } 1054 return false; 1055} 1056