Mercurial > hg > octave-nkf > gnulib-hg

comparison lib/gl_array_list.c @ 12421:e8d2c6fc33ad

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Use spaces for indentation, not tabs.
author Bruno Haible <bruno@clisp.org>
date Thu, 10 Dec 2009 20:28:30 +0100
parents 25f7280c9cf0
children a8c91b846640
comparison
equal deleted inserted replaced
12420:5850b9a81029 12421:e8d2c6fc33ad
51 #define INDEX_TO_NODE(index) (gl_list_node_t)(uintptr_t)(size_t)((index) + 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) 52 #define NODE_TO_INDEX(node) ((uintptr_t)(node) - 1)
53 53
54 static gl_list_t 54 static gl_list_t
55 gl_array_create_empty (gl_list_implementation_t implementation, 55 gl_array_create_empty (gl_list_implementation_t implementation,
56 gl_listelement_equals_fn equals_fn, 56 gl_listelement_equals_fn equals_fn,
57 gl_listelement_hashcode_fn hashcode_fn, 57 gl_listelement_hashcode_fn hashcode_fn,
58 gl_listelement_dispose_fn dispose_fn, 58 gl_listelement_dispose_fn dispose_fn,
59 bool allow_duplicates) 59 bool allow_duplicates)
60 { 60 {
61 struct gl_list_impl *list = XMALLOC (struct gl_list_impl); 61 struct gl_list_impl *list = XMALLOC (struct gl_list_impl);
62 62
63 list->base.vtable = implementation; 63 list->base.vtable = implementation;
64 list->base.equals_fn = equals_fn; 64 list->base.equals_fn = equals_fn;
72 return list; 72 return list;
73 } 73 }
74 74
75 static gl_list_t 75 static gl_list_t
76 gl_array_create (gl_list_implementation_t implementation, 76 gl_array_create (gl_list_implementation_t implementation,
77 gl_listelement_equals_fn equals_fn, 77 gl_listelement_equals_fn equals_fn,
78 gl_listelement_hashcode_fn hashcode_fn, 78 gl_listelement_hashcode_fn hashcode_fn,
79 gl_listelement_dispose_fn dispose_fn, 79 gl_listelement_dispose_fn dispose_fn,
80 bool allow_duplicates, 80 bool allow_duplicates,
81 size_t count, const void **contents) 81 size_t count, const void **contents)
82 { 82 {
83 struct gl_list_impl *list = XMALLOC (struct gl_list_impl); 83 struct gl_list_impl *list = XMALLOC (struct gl_list_impl);
84 84
85 list->base.vtable = implementation; 85 list->base.vtable = implementation;
86 list->base.equals_fn = equals_fn; 86 list->base.equals_fn = equals_fn;
176 return INDEX_TO_NODE (position); 176 return INDEX_TO_NODE (position);
177 } 177 }
178 178
179 static size_t 179 static size_t
180 gl_array_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index, 180 gl_array_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
181 const void *elt) 181 const void *elt)
182 { 182 {
183 size_t count = list->count; 183 size_t count = list->count;
184 184
185 if (!(start_index <= end_index && end_index <= count)) 185 if (!(start_index <= end_index && end_index <= count))
186 /* Invalid arguments. */ 186 /* Invalid arguments. */
188 188
189 if (start_index < end_index) 189 if (start_index < end_index)
190 { 190 {
191 gl_listelement_equals_fn equals = list->base.equals_fn; 191 gl_listelement_equals_fn equals = list->base.equals_fn;
192 if (equals != NULL) 192 if (equals != NULL)
193 { 193 {
194 size_t i; 194 size_t i;
195 195
196 for (i = start_index;;) 196 for (i = start_index;;)
197 { 197 {
198 if (equals (elt, list->elements[i])) 198 if (equals (elt, list->elements[i]))
199 return i; 199 return i;
200 i++; 200 i++;
201 if (i == end_index) 201 if (i == end_index)
202 break; 202 break;
203 } 203 }
204 } 204 }
205 else 205 else
206 { 206 {
207 size_t i; 207 size_t i;
208 208
209 for (i = start_index;;) 209 for (i = start_index;;)
210 { 210 {
211 if (elt == list->elements[i]) 211 if (elt == list->elements[i])
212 return i; 212 return i;
213 i++; 213 i++;
214 if (i == end_index) 214 if (i == end_index)
215 break; 215 break;
216 } 216 }
217 } 217 }
218 } 218 }
219 return (size_t)(-1); 219 return (size_t)(-1);
220 } 220 }
221 221
222 static gl_list_node_t 222 static gl_list_node_t
223 gl_array_search_from_to (gl_list_t list, size_t start_index, size_t end_index, 223 gl_array_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
224 const void *elt) 224 const void *elt)
225 { 225 {
226 size_t index = gl_array_indexof_from_to (list, start_index, end_index, elt); 226 size_t index = gl_array_indexof_from_to (list, start_index, end_index, elt);
227 return INDEX_TO_NODE (index); 227 return INDEX_TO_NODE (index);
228 } 228 }
229 229
399 gl_array_list_free (gl_list_t list) 399 gl_array_list_free (gl_list_t list)
400 { 400 {
401 if (list->elements != NULL) 401 if (list->elements != NULL)
402 { 402 {
403 if (list->base.dispose_fn != NULL) 403 if (list->base.dispose_fn != NULL)
404 { 404 {
405 size_t count = list->count; 405 size_t count = list->count;
406 406
407 if (count > 0) 407 if (count > 0)
408 { 408 {
409 gl_listelement_dispose_fn dispose = list->base.dispose_fn; 409 gl_listelement_dispose_fn dispose = list->base.dispose_fn;
410 const void **elements = list->elements; 410 const void **elements = list->elements;
411 411
412 do 412 do
413 dispose (*elements++); 413 dispose (*elements++);
414 while (--count > 0); 414 while (--count > 0);
415 } 415 }
416 } 416 }
417 free (list->elements); 417 free (list->elements);
418 } 418 }
419 free (list); 419 free (list);
420 } 420 }
421 421
460 return result; 460 return result;
461 } 461 }
462 462
463 static bool 463 static bool
464 gl_array_iterator_next (gl_list_iterator_t *iterator, 464 gl_array_iterator_next (gl_list_iterator_t *iterator,
465 const void **eltp, gl_list_node_t *nodep) 465 const void **eltp, gl_list_node_t *nodep)
466 { 466 {
467 gl_list_t list = iterator->list; 467 gl_list_t list = iterator->list;
468 if (iterator->count != list->count) 468 if (iterator->count != list->count)
469 { 469 {
470 if (iterator->count != list->count + 1) 470 if (iterator->count != list->count + 1)
471 /* Concurrent modifications were done on the list. */ 471 /* Concurrent modifications were done on the list. */
472 abort (); 472 abort ();
473 /* The last returned element was removed. */ 473 /* The last returned element was removed. */
474 iterator->count--; 474 iterator->count--;
475 iterator->p = (const void **) iterator->p - 1; 475 iterator->p = (const void **) iterator->p - 1;
476 iterator->q = (const void **) iterator->q - 1; 476 iterator->q = (const void **) iterator->q - 1;
477 } 477 }
478 if (iterator->p < iterator->q) 478 if (iterator->p < iterator->q)
479 { 479 {
480 const void **p = (const void **) iterator->p; 480 const void **p = (const void **) iterator->p;
481 *eltp = *p; 481 *eltp = *p;
482 if (nodep != NULL) 482 if (nodep != NULL)
483 *nodep = INDEX_TO_NODE (p - list->elements); 483 *nodep = INDEX_TO_NODE (p - list->elements);
484 iterator->p = p + 1; 484 iterator->p = p + 1;
485 return true; 485 return true;
486 } 486 }
487 else 487 else
488 return false; 488 return false;
495 495
496 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */ 496 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
497 497
498 static size_t 498 static size_t
499 gl_array_sortedlist_indexof_from_to (gl_list_t list, 499 gl_array_sortedlist_indexof_from_to (gl_list_t list,
500 gl_listelement_compar_fn compar, 500 gl_listelement_compar_fn compar,
501 size_t low, size_t high, 501 size_t low, size_t high,
502 const void *elt) 502 const void *elt)
503 { 503 {
504 if (!(low <= high && high <= list->count)) 504 if (!(low <= high && high <= list->count))
505 /* Invalid arguments. */ 505 /* Invalid arguments. */
506 abort (); 506 abort ();
507 if (low < high) 507 if (low < high)
508 { 508 {
509 /* At each loop iteration, low < high; for indices < low the values 509 /* At each loop iteration, low < high; for indices < low the values
510 are smaller than ELT; for indices >= high the values are greater 510 are smaller than ELT; for indices >= high the values are greater
511 than ELT. So, if the element occurs in the list, it is at 511 than ELT. So, if the element occurs in the list, it is at
512 low <= position < high. */ 512 low <= position < high. */
513 do 513 do
514 { 514 {
515 size_t mid = low + (high - low) / 2; /* low <= mid < high */ 515 size_t mid = low + (high - low) / 2; /* low <= mid < high */
516 int cmp = compar (list->elements[mid], elt); 516 int cmp = compar (list->elements[mid], elt);
517 517
518 if (cmp < 0) 518 if (cmp < 0)
519 low = mid + 1; 519 low = mid + 1;
520 else if (cmp > 0) 520 else if (cmp > 0)
521 high = mid; 521 high = mid;
522 else /* cmp == 0 */ 522 else /* cmp == 0 */
523 { 523 {
524 /* We have an element equal to ELT at index MID. But we need 524 /* We have an element equal to ELT at index MID. But we need
525 the minimal such index. */ 525 the minimal such index. */
526 high = mid; 526 high = mid;
527 /* At each loop iteration, low <= high and 527 /* At each loop iteration, low <= high and
528 compar (list->elements[high], elt) == 0, 528 compar (list->elements[high], elt) == 0,
529 and we know that the first occurrence of the element is at 529 and we know that the first occurrence of the element is at
530 low <= position <= high. */ 530 low <= position <= high. */
531 while (low < high) 531 while (low < high)
532 { 532 {
533 size_t mid2 = low + (high - low) / 2; /* low <= mid2 < high */ 533 size_t mid2 = low + (high - low) / 2; /* low <= mid2 < high */
534 int cmp2 = compar (list->elements[mid2], elt); 534 int cmp2 = compar (list->elements[mid2], elt);
535 535
536 if (cmp2 < 0) 536 if (cmp2 < 0)
537 low = mid2 + 1; 537 low = mid2 + 1;
538 else if (cmp2 > 0) 538 else if (cmp2 > 0)
539 /* The list was not sorted. */ 539 /* The list was not sorted. */
540 abort (); 540 abort ();
541 else /* cmp2 == 0 */ 541 else /* cmp2 == 0 */
542 { 542 {
543 if (mid2 == low) 543 if (mid2 == low)
544 break; 544 break;
545 high = mid2 - 1; 545 high = mid2 - 1;
546 } 546 }
547 } 547 }
548 return low; 548 return low;
549 } 549 }
550 } 550 }
551 while (low < high); 551 while (low < high);
552 /* Here low == high. */ 552 /* Here low == high. */
553 } 553 }
554 return (size_t)(-1); 554 return (size_t)(-1);
555 } 555 }
556 556
557 static size_t 557 static size_t
558 gl_array_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, 558 gl_array_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
559 const void *elt) 559 const void *elt)
560 { 560 {
561 return gl_array_sortedlist_indexof_from_to (list, compar, 0, list->count, 561 return gl_array_sortedlist_indexof_from_to (list, compar, 0, list->count,
562 elt); 562 elt);
563 } 563 }
564 564
565 static gl_list_node_t 565 static gl_list_node_t
566 gl_array_sortedlist_search_from_to (gl_list_t list, 566 gl_array_sortedlist_search_from_to (gl_list_t list,
567 gl_listelement_compar_fn compar, 567 gl_listelement_compar_fn compar,
568 size_t low, size_t high, 568 size_t low, size_t high,
569 const void *elt) 569 const void *elt)
570 { 570 {
571 size_t index = 571 size_t index =
572 gl_array_sortedlist_indexof_from_to (list, compar, low, high, elt); 572 gl_array_sortedlist_indexof_from_to (list, compar, low, high, elt);
573 return INDEX_TO_NODE (index); 573 return INDEX_TO_NODE (index);
574 } 574 }
575 575
576 static gl_list_node_t 576 static gl_list_node_t
577 gl_array_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar, 577 gl_array_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
578 const void *elt) 578 const void *elt)
579 { 579 {
580 size_t index = 580 size_t index =
581 gl_array_sortedlist_indexof_from_to (list, compar, 0, list->count, elt); 581 gl_array_sortedlist_indexof_from_to (list, compar, 0, list->count, elt);
582 return INDEX_TO_NODE (index); 582 return INDEX_TO_NODE (index);
583 } 583 }
584 584
585 static gl_list_node_t 585 static gl_list_node_t
586 gl_array_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar, 586 gl_array_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar,
587 const void *elt) 587 const void *elt)
588 { 588 {
589 size_t count = list->count; 589 size_t count = list->count;
590 size_t low = 0; 590 size_t low = 0;
591 size_t high = count; 591 size_t high = count;
592 592
596 { 596 {
597 size_t mid = low + (high - low) / 2; /* low <= mid < high */ 597 size_t mid = low + (high - low) / 2; /* low <= mid < high */
598 int cmp = compar (list->elements[mid], elt); 598 int cmp = compar (list->elements[mid], elt);
599 599
600 if (cmp < 0) 600 if (cmp < 0)
601 low = mid + 1; 601 low = mid + 1;
602 else if (cmp > 0) 602 else if (cmp > 0)
603 high = mid; 603 high = mid;
604 else /* cmp == 0 */ 604 else /* cmp == 0 */
605 { 605 {
606 low = mid; 606 low = mid;
607 break; 607 break;
608 } 608 }
609 } 609 }
610 return gl_array_add_at (list, low, elt); 610 return gl_array_add_at (list, low, elt);
611 } 611 }
612 612
613 static bool 613 static bool
614 gl_array_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar, 614 gl_array_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
615 const void *elt) 615 const void *elt)
616 { 616 {
617 size_t index = gl_array_sortedlist_indexof (list, compar, elt); 617 size_t index = gl_array_sortedlist_indexof (list, compar, elt);
618 if (index == (size_t)(-1)) 618 if (index == (size_t)(-1))
619 return false; 619 return false;
620 else 620 else