1 /* PSPP - a program for statistical analysis.
2 Copyright (C) 2006, 2009, 2011 Free Software Foundation, Inc.
4 This program is free software: you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation, either version 3 of the License, or
7 (at your option) any later version.
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
14 You should have received a copy of the GNU General Public License
15 along with this program. If not, see <http://www.gnu.org/licenses/>. */
17 /* External, circular doubly linked list. */
19 /* These library routines have no external dependencies, other
20 than ll.c and the standard C library.
22 If you add routines in this file, please add a corresponding
23 test to llx-test.c. This test program should achieve 100%
24 coverage of lines and branches in this code, as reported by
31 #include "libpspp/llx.h"
32 #include "libpspp/compiler.h"
35 /* Destroys LIST and frees all of its nodes using MANAGER.
36 If DESTRUCTOR is non-null, each node in the list will be
37 passed to it in list order, with AUX as auxiliary data, before
38 that node is destroyed. */
40 llx_destroy (struct llx_list *list, llx_action_func *destructor, void *aux,
41 const struct llx_manager *manager)
43 struct llx *llx, *next;
45 for (llx = llx_head (list); llx != llx_null (list); llx = next)
47 next = llx_next (llx);
48 if (destructor != NULL)
49 destructor (llx_data (llx), aux);
50 manager->release (llx, manager->aux);
54 /* Returns the number of nodes in LIST (not counting the null
55 node). Executes in O(n) time in the length of the list. */
57 llx_count (const struct llx_list *list)
59 return llx_count_range (llx_head (list), llx_null (list));
62 /* Inserts DATA at the head of LIST.
63 Returns the new node (allocated with MANAGER), or a null
64 pointer if memory allocation failed. */
66 llx_push_head (struct llx_list *list, void *data,
67 const struct llx_manager *manager)
69 return llx_insert (llx_head (list), data, manager);
72 /* Inserts DATA at the tail of LIST.
73 Returns the new node (allocated with MANAGER), or a null
74 pointer if memory allocation failed. */
76 llx_push_tail (struct llx_list *list, void *data,
77 const struct llx_manager *manager)
79 return llx_insert (llx_null (list), data, manager);
82 /* Removes the first node in LIST, which must not be empty,
83 and returns the data that the node contained.
84 Frees the node removed with MANAGER. */
86 llx_pop_head (struct llx_list *list, const struct llx_manager *manager)
88 struct llx *llx = llx_from_ll (ll_head (&list->ll_list));
89 void *data = llx_data (llx);
90 llx_remove (llx, manager);
94 /* Removes the last node in LIST, which must not be empty,
95 and returns the data that the node contained.
96 Frees the node removed with MANAGER. */
98 llx_pop_tail (struct llx_list *list, const struct llx_manager *manager)
100 struct llx *llx = llx_from_ll (ll_tail (&list->ll_list));
101 void *data = llx_data (llx);
102 llx_remove (llx, manager);
106 /* Inserts DATA before BEFORE.
107 Returns the new node (allocated with MANAGER), or a null
108 pointer if memory allocation failed. */
110 llx_insert (struct llx *before, void *data, const struct llx_manager *manager)
112 struct llx *llx = manager->allocate (manager->aux);
116 ll_insert (&before->ll, &llx->ll);
121 /* Removes R0...R1 from their current list
122 and inserts them just before BEFORE. */
124 llx_splice (struct llx *before, struct llx *r0, struct llx *r1)
126 ll_splice (&before->ll, &r0->ll, &r1->ll);
129 /* Exchanges the positions of A and B,
130 which may be in the same list or different lists. */
132 llx_swap (struct llx *a, struct llx *b)
134 ll_swap (&a->ll, &b->ll);
137 /* Exchanges the positions of A0...A1 and B0...B1,
138 which may be in the same list or different lists but must not
141 llx_swap_range (struct llx *a0, struct llx *a1,
142 struct llx *b0, struct llx *b1)
144 ll_swap_range (&a0->ll, &a1->ll, &b0->ll, &b1->ll);
147 /* Removes LLX from its list
148 and returns the node that formerly followed it.
149 Frees the node removed with MANAGER. */
151 llx_remove (struct llx *llx, const struct llx_manager *manager)
153 struct llx *next = llx_next (llx);
154 ll_remove (&llx->ll);
155 manager->release (llx, manager->aux);
159 /* Removes R0...R1 from their list.
160 Frees the removed nodes with MANAGER. */
162 llx_remove_range (struct llx *r0, struct llx *r1,
163 const struct llx_manager *manager)
167 for (llx = r0; llx != r1;)
168 llx = llx_remove (llx, manager);
171 /* Removes from R0...R1 all the nodes that equal TARGET
172 according to COMPARE given auxiliary data AUX.
173 Frees the removed nodes with MANAGER.
174 Returns the number of nodes removed. */
176 llx_remove_equal (struct llx *r0, struct llx *r1, const void *target,
177 llx_compare_func *compare, void *aux,
178 const struct llx_manager *manager)
184 for (x = r0; x != r1;)
185 if (compare (llx_data (x), target, aux) == 0)
187 x = llx_remove (x, manager);
196 /* Removes from R0...R1 all the nodes for which PREDICATE returns
197 true given auxiliary data AUX.
198 Frees the removed nodes with MANAGER.
199 Returns the number of nodes removed. */
201 llx_remove_if (struct llx *r0, struct llx *r1,
202 llx_predicate_func *predicate, void *aux,
203 const struct llx_manager *manager)
209 for (x = r0; x != r1;)
210 if (predicate (llx_data (x), aux))
212 x = llx_remove (x, manager);
221 /* Returns the first node in R0...R1 that has data TARGET.
222 Returns NULL if no node in R0...R1 equals TARGET. */
224 llx_find (const struct llx *r0, const struct llx *r1, const void *target)
228 for (x = r0; x != r1; x = llx_next (x))
229 if (llx_data (x) == target)
230 return CONST_CAST (struct llx *, x);
235 /* Returns the first node in R0...R1 that equals TARGET
236 according to COMPARE given auxiliary data AUX.
237 Returns R1 if no node in R0...R1 equals TARGET. */
239 llx_find_equal (const struct llx *r0, const struct llx *r1,
241 llx_compare_func *compare, void *aux)
245 for (x = r0; x != r1; x = llx_next (x))
246 if (compare (llx_data (x), target, aux) == 0)
248 return CONST_CAST (struct llx *, x);
251 /* Returns the first node in R0...R1 for which PREDICATE returns
252 true given auxiliary data AUX.
253 Returns R1 if PREDICATE does not return true for any node in
256 llx_find_if (const struct llx *r0, const struct llx *r1,
257 llx_predicate_func *predicate, void *aux)
261 for (x = r0; x != r1; x = llx_next (x))
262 if (predicate (llx_data (x), aux))
264 return CONST_CAST (struct llx *, x);
267 /* Compares each pair of adjacent nodes in R0...R1
268 using COMPARE with auxiliary data AUX
269 and returns the first node of the first pair that compares
271 Returns R1 if no pair compares equal. */
273 llx_find_adjacent_equal (const struct llx *r0, const struct llx *r1,
274 llx_compare_func *compare, void *aux)
278 const struct llx *x, *y;
280 for (x = r0, y = llx_next (x); y != r1; x = y, y = llx_next (y))
281 if (compare (llx_data (x), llx_data (y), aux) == 0)
282 return CONST_CAST (struct llx *, x);
285 return CONST_CAST (struct llx *, r1);
288 /* Returns the number of nodes in R0...R1.
289 Executes in O(n) time in the return value. */
291 llx_count_range (const struct llx *r0, const struct llx *r1)
293 return ll_count_range (&r0->ll, &r1->ll);
296 /* Counts and returns the number of nodes in R0...R1 that equal
297 TARGET according to COMPARE given auxiliary data AUX. */
299 llx_count_equal (const struct llx *r0, const struct llx *r1,
301 llx_compare_func *compare, void *aux)
307 for (x = r0; x != r1; x = llx_next (x))
308 if (compare (llx_data (x), target, aux) == 0)
313 /* Counts and returns the number of nodes in R0...R1 for which
314 PREDICATE returns true given auxiliary data AUX. */
316 llx_count_if (const struct llx *r0, const struct llx *r1,
317 llx_predicate_func *predicate, void *aux)
323 for (x = r0; x != r1; x = llx_next (x))
324 if (predicate (llx_data (x), aux))
329 /* Returns the greatest node in R0...R1 according to COMPARE
330 given auxiliary data AUX.
331 Returns the first of multiple, equal maxima. */
333 llx_max (const struct llx *r0, const struct llx *r1,
334 llx_compare_func *compare, void *aux)
336 const struct llx *max = r0;
341 for (x = llx_next (r0); x != r1; x = llx_next (x))
342 if (compare (llx_data (x), llx_data (max), aux) > 0)
345 return CONST_CAST (struct llx *, max);
348 /* Returns the least node in R0...R1 according to COMPARE given
350 Returns the first of multiple, equal minima. */
352 llx_min (const struct llx *r0, const struct llx *r1,
353 llx_compare_func *compare, void *aux)
355 const struct llx *min = r0;
360 for (x = llx_next (r0); x != r1; x = llx_next (x))
361 if (compare (llx_data (x), llx_data (min), aux) < 0)
364 return CONST_CAST (struct llx *, min);
367 /* Lexicographically compares A0...A1 to B0...B1.
368 Returns negative if A0...A1 < B0...B1,
369 zero if A0...A1 == B0...B1, and
370 positive if A0...A1 > B0...B1
371 according to COMPARE given auxiliary data AUX. */
373 llx_lexicographical_compare_3way (const struct llx *a0, const struct llx *a1,
374 const struct llx *b0, const struct llx *b1,
375 llx_compare_func *compare, void *aux)
384 int cmp = compare (llx_data (a0), llx_data (b0), aux);
393 /* Calls ACTION with auxiliary data AUX
394 for every node in R0...R1 in order. */
396 llx_apply (struct llx *r0, struct llx *r1,
397 llx_action_func *action, void *aux)
401 for (llx = r0; llx != r1; llx = llx_next (llx))
402 action (llx_data (llx), aux);
405 /* Reverses the order of nodes R0...R1. */
407 llx_reverse (struct llx *r0, struct llx *r1)
409 ll_reverse (&r0->ll, &r1->ll);
412 /* Arranges R0...R1 into the lexicographically next greater
413 permutation. Returns true if successful.
414 If R0...R1 is already the lexicographically greatest
415 permutation of its elements (i.e. ordered from greatest to
416 smallest), arranges them into the lexicographically least
417 permutation (i.e. ordered from smallest to largest) and
419 COMPARE with auxiliary data AUX is used to compare nodes. */
421 llx_next_permutation (struct llx *r0, struct llx *r1,
422 llx_compare_func *compare, void *aux)
426 struct llx *i = llx_prev (r1);
430 if (compare (llx_data (i), llx_data (llx_next (i)), aux) < 0)
433 for (j = llx_prev (r1);
434 compare (llx_data (i), llx_data (j), aux) >= 0;
438 llx_reverse (llx_next (j), r1);
443 llx_reverse (r0, r1);
449 /* Arranges R0...R1 into the lexicographically next lesser
450 permutation. Returns true if successful.
451 If R0...R1 is already the lexicographically least
452 permutation of its elements (i.e. ordered from smallest to
453 greatest), arranges them into the lexicographically greatest
454 permutation (i.e. ordered from largest to smallest) and
456 COMPARE with auxiliary data AUX is used to compare nodes. */
458 llx_prev_permutation (struct llx *r0, struct llx *r1,
459 llx_compare_func *compare, void *aux)
463 struct llx *i = llx_prev (r1);
467 if (compare (llx_data (i), llx_data (llx_next (i)), aux) > 0)
470 for (j = llx_prev (r1);
471 compare (llx_data (i), llx_data (j), aux) <= 0;
475 llx_reverse (llx_next (j), r1);
480 llx_reverse (r0, r1);
486 /* Sorts R0...R1 into ascending order
487 according to COMPARE given auxiliary data AUX.
488 In use, keep in mind that R0 may move during the sort, so that
489 afterward R0...R1 may denote a different range.
490 (On the other hand, R1 is fixed in place.)
491 Runs in O(n lg n) time in the number of nodes in the range. */
493 llx_sort (struct llx *r0, struct llx *r1, llx_compare_func *compare, void *aux)
496 size_t output_run_cnt;
498 if (r0 == r1 || llx_next (r0) == r1)
501 pre_r0 = llx_prev (r0);
504 struct llx *a0 = llx_next (pre_r0);
505 for (output_run_cnt = 1; ; output_run_cnt++)
507 struct llx *a1 = llx_find_run (a0, r1, compare, aux);
508 struct llx *a2 = llx_find_run (a1, r1, compare, aux);
512 a0 = llx_merge (a0, a1, a1, a2, compare, aux);
515 while (output_run_cnt > 1);
518 /* Finds the extent of a run of nodes of increasing value
519 starting at R0 and extending no farther than R1.
520 Returns the first node in R0...R1 that is less than the
521 preceding node, or R1 if R0...R1 are arranged in nondecreasing
524 llx_find_run (const struct llx *r0, const struct llx *r1,
525 llx_compare_func *compare, void *aux)
533 while (r0 != r1 && compare (llx_data (llx_prev (r0)),
534 llx_data (r0), aux) <= 0);
537 return CONST_CAST (struct llx *, r0);
540 /* Merges B0...B1 into A0...A1 according to COMPARE given
542 The ranges may be in the same list or different lists, but
544 The merge is "stable" if A0...A1 is considered to precede
545 B0...B1, regardless of their actual ordering.
546 Runs in O(n) time in the total number of nodes in the ranges. */
548 llx_merge (struct llx *a0, struct llx *a1, struct llx *b0, struct llx *b1,
549 llx_compare_func *compare, void *aux)
551 if (a0 != a1 && b0 != b1)
556 if (compare (llx_data (a0), llx_data (b0), aux) <= 0)
560 llx_splice (llx_next (a0), b0, llx_next (b1));
561 return llx_next (b1);
571 llx_splice (a0, x, b0);
575 llx_splice (a0, b0, llx_next (b0));
576 return llx_next (a1);
582 llx_splice (a0, b0, b1);
587 /* Returns true if R0...R1 is sorted in ascending order according
588 to COMPARE given auxiliary data AUX,
591 llx_is_sorted (const struct llx *r0, const struct llx *r1,
592 llx_compare_func *compare, void *aux)
594 return llx_find_run (r0, r1, compare, aux) == r1;
597 /* Removes all but the first in each group of sequential
598 duplicates in R0...R1. Duplicates are determined using
599 COMPARE given auxiliary data AUX. Removed duplicates are
600 inserted before DUPS if it is nonnull; otherwise, the removed
601 duplicates are freed with MANAGER.
602 Only sequential duplicates are removed. llx_sort() may be used
603 to bring duplicates together, or llx_sort_unique() can do both
606 llx_unique (struct llx *r0, struct llx *r1, struct llx *dups,
607 llx_compare_func *compare, void *aux,
608 const struct llx_manager *manager)
617 struct llx *y = llx_next (x);
624 if (compare (llx_data (x), llx_data (y), aux) == 0)
627 llx_splice (dups, y, llx_next (y));
629 llx_remove (y, manager);
642 /* Sorts R0...R1 and removes duplicates.
643 Removed duplicates are inserted before DUPS if it is nonnull;
644 otherwise, the removed duplicates are freed with MANAGER.
645 Comparisons are made with COMPARE given auxiliary data AUX.
646 In use, keep in mind that R0 may move during the sort, so that
647 afterward R0...R1 may denote a different range.
648 (On the other hand, R1 is fixed in place.)
649 Runs in O(n lg n) time in the number of nodes in the range. */
651 llx_sort_unique (struct llx *r0, struct llx *r1, struct llx *dups,
652 llx_compare_func *compare, void *aux,
653 const struct llx_manager *manager)
655 struct llx *pre_r0 = llx_prev (r0);
656 llx_sort (r0, r1, compare, aux);
657 llx_unique (llx_next (pre_r0), r1, dups, compare, aux, manager);
660 /* Inserts DATA in the proper position in R0...R1, which must
661 be sorted according to COMPARE given auxiliary data AUX.
662 If DATA is equal to one or more existing nodes in R0...R1,
663 then it is inserted after the existing nodes it equals.
664 Returns the new node (allocated with MANAGER), or a null
665 pointer if memory allocation failed.
666 Runs in O(n) time in the number of nodes in the range. */
668 llx_insert_ordered (struct llx *r0, struct llx *r1, void *data,
669 llx_compare_func *compare, void *aux,
670 const struct llx_manager *manager)
674 for (x = r0; x != r1; x = llx_next (x))
675 if (compare (llx_data (x), data, aux) > 0)
677 return llx_insert (x, data, manager);
680 /* Partitions R0...R1 into those nodes for which PREDICATE given
681 auxiliary data AUX returns true, followed by those for which
682 PREDICATE returns false.
683 Returns the first node in the "false" group, or R1 if
684 PREDICATE is true for every node in R0...R1.
685 The partition is "stable" in that the nodes in each group
686 retain their original relative order.
687 Runs in O(n) time in the number of nodes in the range. */
689 llx_partition (struct llx *r0, struct llx *r1,
690 llx_predicate_func *predicate, void *aux)
698 else if (!predicate (llx_data (r0), aux))
704 for (t0 = r0;; t0 = t1)
712 while (!predicate (llx_data (t0), aux));
720 llx_splice (r0, t0, t1);
724 while (predicate (llx_data (t1), aux));
726 llx_splice (r0, t0, t1);
730 /* Verifies that R0...R1 is parititioned into a sequence of nodes
731 for which PREDICATE given auxiliary data AUX returns true,
732 followed by those for which PREDICATE returns false.
733 Returns a null pointer if R0...R1 is not partitioned this way.
734 Otherwise, returns the first node in the "false" group, or R1
735 if PREDICATE is true for every node in R0...R1. */
737 llx_find_partition (const struct llx *r0, const struct llx *r1,
738 llx_predicate_func *predicate, void *aux)
740 const struct llx *partition, *x;
742 for (partition = r0; partition != r1; partition = llx_next (partition))
743 if (!predicate (llx_data (partition), aux))
746 for (x = partition; x != r1; x = llx_next (x))
747 if (predicate (llx_data (x), aux))
750 return CONST_CAST (struct llx *, partition);
753 /* Allocates and returns a node using malloc. */
755 malloc_allocate_node (void *aux UNUSED)
757 return malloc (sizeof (struct llx));
760 /* Releases node LLX with free. */
762 malloc_release_node (struct llx *llx, void *aux UNUSED)
767 /* Manager that uses the standard malloc and free routines. */
768 const struct llx_manager llx_malloc_mgr =
770 malloc_allocate_node,