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