1/* Sequential list data type implemented by an array. 2 Copyright (C) 2006-2007 Free Software Foundation, Inc. 3 Written by Bruno Haible <bruno@clisp.org>, 2006. 4 5 This program is free software: you can redistribute it and/or modify 6 it under the terms of the GNU General Public License as published by 7 the Free Software Foundation; either version 3 of the License, or 8 (at your option) any later version. 9 10 This program is distributed in the hope that it will be useful, 11 but WITHOUT ANY WARRANTY; without even the implied warranty of 12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13 GNU General Public License for more details. 14 15 You should have received a copy of the GNU General Public License 16 along with this program. If not, see <http://www.gnu.org/licenses/>. */ 17 18#include <config.h> 19 20/* Specification. */ 21#include "gl_array_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. */ 39struct gl_list_impl 40{ 41 struct gl_list_impl_base base; 42 /* An array of ALLOCATED elements, of which the first COUNT are used. 43 0 <= COUNT <= ALLOCATED. */ 44 const void **elements; 45 size_t count; 46 size_t allocated; 47}; 48 49/* struct gl_list_node_impl doesn't exist here. The pointers are actually 50 indices + 1. */ 51#define INDEX_TO_NODE(index) (gl_list_node_t)(uintptr_t)(size_t)((index) + 1) 52#define NODE_TO_INDEX(node) ((uintptr_t)(node) - 1) 53 54static gl_list_t 55gl_array_create_empty (gl_list_implementation_t implementation, 56 gl_listelement_equals_fn equals_fn, 57 gl_listelement_hashcode_fn hashcode_fn, 58 gl_listelement_dispose_fn dispose_fn, 59 bool allow_duplicates) 60{ 61 struct gl_list_impl *list = XMALLOC (struct gl_list_impl); 62 63 list->base.vtable = implementation; 64 list->base.equals_fn = equals_fn; 65 list->base.hashcode_fn = hashcode_fn; 66 list->base.dispose_fn = dispose_fn; 67 list->base.allow_duplicates = allow_duplicates; 68 list->elements = NULL; 69 list->count = 0; 70 list->allocated = 0; 71 72 return list; 73} 74 75static gl_list_t 76gl_array_create (gl_list_implementation_t implementation, 77 gl_listelement_equals_fn equals_fn, 78 gl_listelement_hashcode_fn hashcode_fn, 79 gl_listelement_dispose_fn dispose_fn, 80 bool allow_duplicates, 81 size_t count, const void **contents) 82{ 83 struct gl_list_impl *list = XMALLOC (struct gl_list_impl); 84 85 list->base.vtable = implementation; 86 list->base.equals_fn = equals_fn; 87 list->base.hashcode_fn = hashcode_fn; 88 list->base.dispose_fn = dispose_fn; 89 list->base.allow_duplicates = allow_duplicates; 90 if (count > 0) 91 { 92 list->elements = XNMALLOC (count, const void *); 93 memcpy (list->elements, contents, count * sizeof (const void *)); 94 } 95 else 96 list->elements = NULL; 97 list->count = count; 98 list->allocated = count; 99 100 return list; 101} 102 103static size_t 104gl_array_size (gl_list_t list) 105{ 106 return list->count; 107} 108 109static const void * 110gl_array_node_value (gl_list_t list, gl_list_node_t node) 111{ 112 uintptr_t index = NODE_TO_INDEX (node); 113 if (!(index < list->count)) 114 /* Invalid argument. */ 115 abort (); 116 return list->elements[index]; 117} 118 119static gl_list_node_t 120gl_array_next_node (gl_list_t list, gl_list_node_t node) 121{ 122 uintptr_t index = NODE_TO_INDEX (node); 123 if (!(index < list->count)) 124 /* Invalid argument. */ 125 abort (); 126 index++; 127 if (index < list->count) 128 return INDEX_TO_NODE (index); 129 else 130 return NULL; 131} 132 133static gl_list_node_t 134gl_array_previous_node (gl_list_t list, gl_list_node_t node) 135{ 136 uintptr_t index = NODE_TO_INDEX (node); 137 if (!(index < list->count)) 138 /* Invalid argument. */ 139 abort (); 140 if (index > 0) 141 return INDEX_TO_NODE (index - 1); 142 else 143 return NULL; 144} 145 146static const void * 147gl_array_get_at (gl_list_t list, size_t position) 148{ 149 size_t count = list->count; 150 151 if (!(position < count)) 152 /* Invalid argument. */ 153 abort (); 154 return list->elements[position]; 155} 156 157static gl_list_node_t 158gl_array_set_at (gl_list_t list, size_t position, const void *elt) 159{ 160 size_t count = list->count; 161 162 if (!(position < count)) 163 /* Invalid argument. */ 164 abort (); 165 list->elements[position] = elt; 166 return INDEX_TO_NODE (position); 167} 168 169static size_t 170gl_array_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index, 171 const void *elt) 172{ 173 size_t count = list->count; 174 175 if (!(start_index <= end_index && end_index <= count)) 176 /* Invalid arguments. */ 177 abort (); 178 179 if (start_index < end_index) 180 { 181 gl_listelement_equals_fn equals = list->base.equals_fn; 182 if (equals != NULL) 183 { 184 size_t i; 185 186 for (i = start_index;;) 187 { 188 if (equals (elt, list->elements[i])) 189 return i; 190 i++; 191 if (i == end_index) 192 break; 193 } 194 } 195 else 196 { 197 size_t i; 198 199 for (i = start_index;;) 200 { 201 if (elt == list->elements[i]) 202 return i; 203 i++; 204 if (i == end_index) 205 break; 206 } 207 } 208 } 209 return (size_t)(-1); 210} 211 212static gl_list_node_t 213gl_array_search_from_to (gl_list_t list, size_t start_index, size_t end_index, 214 const void *elt) 215{ 216 size_t index = gl_array_indexof_from_to (list, start_index, end_index, elt); 217 return INDEX_TO_NODE (index); 218} 219 220/* Ensure that list->allocated > list->count. */ 221static void 222grow (gl_list_t list) 223{ 224 size_t new_allocated; 225 size_t memory_size; 226 const void **memory; 227 228 new_allocated = xtimes (list->allocated, 2); 229 new_allocated = xsum (new_allocated, 1); 230 memory_size = xtimes (new_allocated, sizeof (const void *)); 231 if (size_overflow_p (memory_size)) 232 /* Overflow, would lead to out of memory. */ 233 xalloc_die (); 234 memory = (const void **) xrealloc (list->elements, memory_size); 235 if (memory == NULL) 236 /* Out of memory. */ 237 xalloc_die (); 238 list->elements = memory; 239 list->allocated = new_allocated; 240} 241 242static gl_list_node_t 243gl_array_add_first (gl_list_t list, const void *elt) 244{ 245 size_t count = list->count; 246 const void **elements; 247 size_t i; 248 249 if (count == list->allocated) 250 grow (list); 251 elements = list->elements; 252 for (i = count; i > 0; i--) 253 elements[i] = elements[i - 1]; 254 elements[0] = elt; 255 list->count = count + 1; 256 return INDEX_TO_NODE (0); 257} 258 259static gl_list_node_t 260gl_array_add_last (gl_list_t list, const void *elt) 261{ 262 size_t count = list->count; 263 264 if (count == list->allocated) 265 grow (list); 266 list->elements[count] = elt; 267 list->count = count + 1; 268 return INDEX_TO_NODE (count); 269} 270 271static gl_list_node_t 272gl_array_add_before (gl_list_t list, gl_list_node_t node, const void *elt) 273{ 274 size_t count = list->count; 275 uintptr_t index = NODE_TO_INDEX (node); 276 size_t position; 277 const void **elements; 278 size_t i; 279 280 if (!(index < count)) 281 /* Invalid argument. */ 282 abort (); 283 position = index; 284 if (count == list->allocated) 285 grow (list); 286 elements = list->elements; 287 for (i = count; i > position; i--) 288 elements[i] = elements[i - 1]; 289 elements[position] = elt; 290 list->count = count + 1; 291 return INDEX_TO_NODE (position); 292} 293 294static gl_list_node_t 295gl_array_add_after (gl_list_t list, gl_list_node_t node, const void *elt) 296{ 297 size_t count = list->count; 298 uintptr_t index = NODE_TO_INDEX (node); 299 size_t position; 300 const void **elements; 301 size_t i; 302 303 if (!(index < count)) 304 /* Invalid argument. */ 305 abort (); 306 position = index + 1; 307 if (count == list->allocated) 308 grow (list); 309 elements = list->elements; 310 for (i = count; i > position; i--) 311 elements[i] = elements[i - 1]; 312 elements[position] = elt; 313 list->count = count + 1; 314 return INDEX_TO_NODE (position); 315} 316 317static gl_list_node_t 318gl_array_add_at (gl_list_t list, size_t position, const void *elt) 319{ 320 size_t count = list->count; 321 const void **elements; 322 size_t i; 323 324 if (!(position <= count)) 325 /* Invalid argument. */ 326 abort (); 327 if (count == list->allocated) 328 grow (list); 329 elements = list->elements; 330 for (i = count; i > position; i--) 331 elements[i] = elements[i - 1]; 332 elements[position] = elt; 333 list->count = count + 1; 334 return INDEX_TO_NODE (position); 335} 336 337static bool 338gl_array_remove_node (gl_list_t list, gl_list_node_t node) 339{ 340 size_t count = list->count; 341 uintptr_t index = NODE_TO_INDEX (node); 342 size_t position; 343 const void **elements; 344 size_t i; 345 346 if (!(index < count)) 347 /* Invalid argument. */ 348 abort (); 349 position = index; 350 elements = list->elements; 351 if (list->base.dispose_fn != NULL) 352 list->base.dispose_fn (elements[position]); 353 for (i = position + 1; i < count; i++) 354 elements[i - 1] = elements[i]; 355 list->count = count - 1; 356 return true; 357} 358 359static bool 360gl_array_remove_at (gl_list_t list, size_t position) 361{ 362 size_t count = list->count; 363 const void **elements; 364 size_t i; 365 366 if (!(position < count)) 367 /* Invalid argument. */ 368 abort (); 369 elements = list->elements; 370 if (list->base.dispose_fn != NULL) 371 list->base.dispose_fn (elements[position]); 372 for (i = position + 1; i < count; i++) 373 elements[i - 1] = elements[i]; 374 list->count = count - 1; 375 return true; 376} 377 378static bool 379gl_array_remove (gl_list_t list, const void *elt) 380{ 381 size_t position = gl_array_indexof_from_to (list, 0, list->count, elt); 382 if (position == (size_t)(-1)) 383 return false; 384 else 385 return gl_array_remove_at (list, position); 386} 387 388static void 389gl_array_list_free (gl_list_t list) 390{ 391 if (list->elements != NULL) 392 { 393 if (list->base.dispose_fn != NULL) 394 { 395 size_t count = list->count; 396 397 if (count > 0) 398 { 399 gl_listelement_dispose_fn dispose = list->base.dispose_fn; 400 const void **elements = list->elements; 401 402 do 403 dispose (*elements++); 404 while (--count > 0); 405 } 406 } 407 free (list->elements); 408 } 409 free (list); 410} 411 412/* --------------------- gl_list_iterator_t Data Type --------------------- */ 413 414static gl_list_iterator_t 415gl_array_iterator (gl_list_t list) 416{ 417 gl_list_iterator_t result; 418 419 result.vtable = list->base.vtable; 420 result.list = list; 421 result.count = list->count; 422 result.p = list->elements + 0; 423 result.q = list->elements + list->count; 424#ifdef lint 425 result.i = 0; 426 result.j = 0; 427#endif 428 429 return result; 430} 431 432static gl_list_iterator_t 433gl_array_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index) 434{ 435 gl_list_iterator_t result; 436 437 if (!(start_index <= end_index && end_index <= list->count)) 438 /* Invalid arguments. */ 439 abort (); 440 result.vtable = list->base.vtable; 441 result.list = list; 442 result.count = list->count; 443 result.p = list->elements + start_index; 444 result.q = list->elements + end_index; 445#ifdef lint 446 result.i = 0; 447 result.j = 0; 448#endif 449 450 return result; 451} 452 453static bool 454gl_array_iterator_next (gl_list_iterator_t *iterator, 455 const void **eltp, gl_list_node_t *nodep) 456{ 457 gl_list_t list = iterator->list; 458 if (iterator->count != list->count) 459 { 460 if (iterator->count != list->count + 1) 461 /* Concurrent modifications were done on the list. */ 462 abort (); 463 /* The last returned element was removed. */ 464 iterator->count--; 465 iterator->p = (const void **) iterator->p - 1; 466 iterator->q = (const void **) iterator->q - 1; 467 } 468 if (iterator->p < iterator->q) 469 { 470 const void **p = (const void **) iterator->p; 471 *eltp = *p; 472 if (nodep != NULL) 473 *nodep = INDEX_TO_NODE (p - list->elements); 474 iterator->p = p + 1; 475 return true; 476 } 477 else 478 return false; 479} 480 481static void 482gl_array_iterator_free (gl_list_iterator_t *iterator) 483{ 484} 485 486/* ---------------------- Sorted gl_list_t Data Type ---------------------- */ 487 488static size_t 489gl_array_sortedlist_indexof_from_to (gl_list_t list, 490 gl_listelement_compar_fn compar, 491 size_t low, size_t high, 492 const void *elt) 493{ 494 if (!(low <= high && high <= list->count)) 495 /* Invalid arguments. */ 496 abort (); 497 if (low < high) 498 { 499 /* At each loop iteration, low < high; for indices < low the values 500 are smaller than ELT; for indices >= high the values are greater 501 than ELT. So, if the element occurs in the list, it is at 502 low <= position < high. */ 503 do 504 { 505 size_t mid = low + (high - low) / 2; /* low <= mid < high */ 506 int cmp = compar (list->elements[mid], elt); 507 508 if (cmp < 0) 509 low = mid + 1; 510 else if (cmp > 0) 511 high = mid; 512 else /* cmp == 0 */ 513 { 514 /* We have an element equal to ELT at index MID. But we need 515 the minimal such index. */ 516 high = mid; 517 /* At each loop iteration, low <= high and 518 compar (list->elements[high], elt) == 0, 519 and we know that the first occurrence of the element is at 520 low <= position <= high. */ 521 while (low < high) 522 { 523 size_t mid2 = low + (high - low) / 2; /* low <= mid2 < high */ 524 int cmp2 = compar (list->elements[mid2], elt); 525 526 if (cmp2 < 0) 527 low = mid2 + 1; 528 else if (cmp2 > 0) 529 /* The list was not sorted. */ 530 abort (); 531 else /* cmp2 == 0 */ 532 { 533 if (mid2 == low) 534 break; 535 high = mid2 - 1; 536 } 537 } 538 return low; 539 } 540 } 541 while (low < high); 542 /* Here low == high. */ 543 } 544 return (size_t)(-1); 545} 546 547static size_t 548gl_array_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, 549 const void *elt) 550{ 551 return gl_array_sortedlist_indexof_from_to (list, compar, 0, list->count, 552 elt); 553} 554 555static gl_list_node_t 556gl_array_sortedlist_search_from_to (gl_list_t list, 557 gl_listelement_compar_fn compar, 558 size_t low, size_t high, 559 const void *elt) 560{ 561 size_t index = 562 gl_array_sortedlist_indexof_from_to (list, compar, low, high, elt); 563 return INDEX_TO_NODE (index); 564} 565 566static gl_list_node_t 567gl_array_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar, 568 const void *elt) 569{ 570 size_t index = 571 gl_array_sortedlist_indexof_from_to (list, compar, 0, list->count, elt); 572 return INDEX_TO_NODE (index); 573} 574 575static gl_list_node_t 576gl_array_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar, 577 const void *elt) 578{ 579 size_t count = list->count; 580 size_t low = 0; 581 size_t high = count; 582 583 /* At each loop iteration, low <= high; for indices < low the values are 584 smaller than ELT; for indices >= high the values are greater than ELT. */ 585 while (low < high) 586 { 587 size_t mid = low + (high - low) / 2; /* low <= mid < high */ 588 int cmp = compar (list->elements[mid], elt); 589 590 if (cmp < 0) 591 low = mid + 1; 592 else if (cmp > 0) 593 high = mid; 594 else /* cmp == 0 */ 595 { 596 low = mid; 597 break; 598 } 599 } 600 return gl_array_add_at (list, low, elt); 601} 602 603static bool 604gl_array_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar, 605 const void *elt) 606{ 607 size_t index = gl_array_sortedlist_indexof (list, compar, elt); 608 if (index == (size_t)(-1)) 609 return false; 610 else 611 return gl_array_remove_at (list, index); 612} 613 614 615const struct gl_list_implementation gl_array_list_implementation = 616 { 617 gl_array_create_empty, 618 gl_array_create, 619 gl_array_size, 620 gl_array_node_value, 621 gl_array_next_node, 622 gl_array_previous_node, 623 gl_array_get_at, 624 gl_array_set_at, 625 gl_array_search_from_to, 626 gl_array_indexof_from_to, 627 gl_array_add_first, 628 gl_array_add_last, 629 gl_array_add_before, 630 gl_array_add_after, 631 gl_array_add_at, 632 gl_array_remove_node, 633 gl_array_remove_at, 634 gl_array_remove, 635 gl_array_list_free, 636 gl_array_iterator, 637 gl_array_iterator_from_to, 638 gl_array_iterator_next, 639 gl_array_iterator_free, 640 gl_array_sortedlist_search, 641 gl_array_sortedlist_search_from_to, 642 gl_array_sortedlist_indexof, 643 gl_array_sortedlist_indexof_from_to, 644 gl_array_sortedlist_add, 645 gl_array_sortedlist_remove 646 }; 647