1 /* PSPP - computes sample statistics.
2 Copyright (C) 2006 Free Software Foundation, Inc.
3 Written by Ben Pfaff <blp@gnu.org>
5 This program is free software; you can redistribute it and/or
6 modify it under the terms of the GNU General Public License as
7 published by the Free Software Foundation; either version 2 of the
8 License, or (at your option) any later version.
10 This program is distributed in the hope that it will be useful, but
11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 General Public License for more details.
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
17 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
20 /* External, circular doubly linked list. */
22 /* These library routines have no external dependencies, other
23 than ll.c and the standard C library.
25 If you add routines in this file, please add a corresponding
26 test to llx-test.c. This test program should achieve 100%
27 coverage of lines and branches in this code, as reported by
34 #include <libpspp/llx.h>
38 #if __GNUC__ >= 2 && !defined UNUSED
39 #define UNUSED __attribute__ ((unused))
44 /* Destroys LIST and frees all of its nodes using MANAGER.
45 If DESTRUCTOR is non-null, each node in the list will be
46 passed to it in list order, with AUX as auxiliary data, before
47 that node is destroyed. */
49 llx_destroy (struct llx_list *list, llx_action_func *destructor, void *aux,
50 const struct llx_manager *manager)
52 struct llx *llx, *next;
54 for (llx = llx_head (list); llx != llx_null (list); llx = next)
56 next = llx_next (llx);
57 if (destructor != NULL)
58 destructor (llx_data (llx), aux);
59 manager->release (llx, manager->aux);
63 /* Returns the number of nodes in LIST (not counting the null
64 node). Executes in O(n) time in the length of the list. */
66 llx_count (const struct llx_list *list)
68 return llx_count_range (llx_head (list), llx_null (list));
71 /* Inserts DATA at the head of LIST.
72 Returns the new node (allocated with MANAGER), or a null
73 pointer if memory allocation failed. */
75 llx_push_head (struct llx_list *list, void *data,
76 const struct llx_manager *manager)
78 return llx_insert (llx_head (list), data, manager);
81 /* Inserts DATA at the tail of LIST.
82 Returns the new node (allocated with MANAGER), or a null
83 pointer if memory allocation failed. */
85 llx_push_tail (struct llx_list *list, void *data,
86 const struct llx_manager *manager)
88 return llx_insert (llx_null (list), data, manager);
91 /* Removes the first node in LIST, which must not be empty,
92 and returns the data that the node contained.
93 Frees the node removed with MANAGER. */
95 llx_pop_head (struct llx_list *list, const struct llx_manager *manager)
97 struct llx *llx = llx_from_ll (ll_head (&list->ll_list));
98 void *data = llx_data (llx);
99 llx_remove (llx, manager);
103 /* Removes the last node in LIST, which must not be empty,
104 and returns the data that the node contained.
105 Frees the node removed with MANAGER. */
107 llx_pop_tail (struct llx_list *list, const struct llx_manager *manager)
109 struct llx *llx = llx_from_ll (ll_tail (&list->ll_list));
110 void *data = llx_data (llx);
111 llx_remove (llx, manager);
115 /* Inserts DATA before BEFORE.
116 Returns the new node (allocated with MANAGER), or a null
117 pointer if memory allocation failed. */
119 llx_insert (struct llx *before, void *data, const struct llx_manager *manager)
121 struct llx *llx = manager->allocate (manager->aux);
125 ll_insert (&before->ll, &llx->ll);
130 /* Removes R0...R1 from their current list
131 and inserts them just before BEFORE. */
133 llx_splice (struct llx *before, struct llx *r0, struct llx *r1)
135 ll_splice (&before->ll, &r0->ll, &r1->ll);
138 /* Exchanges the positions of A and B,
139 which may be in the same list or different lists. */
141 llx_swap (struct llx *a, struct llx *b)
143 ll_swap (&a->ll, &b->ll);
146 /* Exchanges the positions of A0...A1 and B0...B1,
147 which may be in the same list or different lists but must not
150 llx_swap_range (struct llx *a0, struct llx *a1,
151 struct llx *b0, struct llx *b1)
153 ll_swap_range (&a0->ll, &a1->ll, &b0->ll, &b1->ll);
156 /* Removes LLX from its list
157 and returns the node that formerly followed it.
158 Frees the node removed with MANAGER. */
160 llx_remove (struct llx *llx, const struct llx_manager *manager)
162 struct llx *next = llx_next (llx);
163 ll_remove (&llx->ll);
164 manager->release (llx, manager->aux);
168 /* Removes R0...R1 from their list.
169 Frees the removed nodes with MANAGER. */
171 llx_remove_range (struct llx *r0, struct llx *r1,
172 const struct llx_manager *manager)
176 for (llx = r0; llx != r1; )
177 llx = llx_remove (llx, manager);
180 /* Removes from R0...R1 all the nodes that equal TARGET
181 according to COMPARE given auxiliary data AUX.
182 Frees the removed nodes with MANAGER.
183 Returns the number of nodes removed. */
185 llx_remove_equal (struct llx *r0, struct llx *r1, const void *target,
186 llx_compare_func *compare, void *aux,
187 const struct llx_manager *manager)
193 for (x = r0; x != r1; )
194 if (compare (llx_data (x), target, aux) == 0)
196 x = llx_remove (x, manager);
205 /* Removes from R0...R1 all the nodes for which PREDICATE returns
206 true given auxiliary data AUX.
207 Frees the removed nodes with MANAGER.
208 Returns the number of nodes removed. */
210 llx_remove_if (struct llx *r0, struct llx *r1,
211 llx_predicate_func *predicate, void *aux,
212 const struct llx_manager *manager)
218 for (x = r0; x != r1; )
219 if (predicate (llx_data (x), aux))
221 x = llx_remove (x, manager);
230 /* Returns the first node in R0...R1 that equals TARGET
231 according to COMPARE given auxiliary data AUX.
232 Returns R1 if no node in R0...R1 equals TARGET. */
234 llx_find_equal (const struct llx *r0, const struct llx *r1,
236 llx_compare_func *compare, void *aux)
240 for (x = r0; x != r1; x = llx_next (x))
241 if (compare (llx_data (x), target, aux) == 0)
243 return (struct llx *) x;
246 /* Returns the first node in R0...R1 for which PREDICATE returns
247 true given auxiliary data AUX.
248 Returns R1 if PREDICATE does not return true for any node in
251 llx_find_if (const struct llx *r0, const struct llx *r1,
252 llx_predicate_func *predicate, void *aux)
256 for (x = r0; x != r1; x = llx_next (x))
257 if (predicate (llx_data (x), aux))
259 return (struct llx *) x;
262 /* Compares each pair of adjacent nodes in R0...R1
263 using COMPARE with auxiliary data AUX
264 and returns the first node of the first pair that compares
266 Returns R1 if no pair compares equal. */
268 llx_find_adjacent_equal (const struct llx *r0, const struct llx *r1,
269 llx_compare_func *compare, void *aux)
273 const struct llx *x, *y;
275 for (x = r0, y = llx_next (x); y != r1; x = y, y = llx_next (y))
276 if (compare (llx_data (x), llx_data (y), aux) == 0)
277 return (struct llx *) x;
280 return (struct llx *) r1;
283 /* Returns the number of nodes in R0...R1.
284 Executes in O(n) time in the return value. */
286 llx_count_range (const struct llx *r0, const struct llx *r1)
288 return ll_count_range (&r0->ll, &r1->ll);
291 /* Counts and returns the number of nodes in R0...R1 that equal
292 TARGET according to COMPARE given auxiliary data AUX. */
294 llx_count_equal (const struct llx *r0, const struct llx *r1,
296 llx_compare_func *compare, void *aux)
302 for (x = r0; x != r1; x = llx_next (x))
303 if (compare (llx_data (x), target, aux) == 0)
308 /* Counts and returns the number of nodes in R0...R1 for which
309 PREDICATE returns true given auxiliary data AUX. */
311 llx_count_if (const struct llx *r0, const struct llx *r1,
312 llx_predicate_func *predicate, void *aux)
318 for (x = r0; x != r1; x = llx_next (x))
319 if (predicate (llx_data (x), aux))
324 /* Returns the greatest node in R0...R1 according to COMPARE
325 given auxiliary data AUX.
326 Returns the first of multiple, equal maxima. */
328 llx_max (const struct llx *r0, const struct llx *r1,
329 llx_compare_func *compare, void *aux)
331 const struct llx *max = r0;
336 for (x = llx_next (r0); x != r1; x = llx_next (x))
337 if (compare (llx_data (x), llx_data (max), aux) > 0)
340 return (struct llx *) max;
343 /* Returns the least node in R0...R1 according to COMPARE given
345 Returns the first of multiple, equal minima. */
347 llx_min (const struct llx *r0, const struct llx *r1,
348 llx_compare_func *compare, void *aux)
350 const struct llx *min = r0;
355 for (x = llx_next (r0); x != r1; x = llx_next (x))
356 if (compare (llx_data (x), llx_data (min), aux) < 0)
359 return (struct llx *) min;
362 /* Lexicographically compares A0...A1 to B0...B1.
363 Returns negative if A0...A1 < B0...B1,
364 zero if A0...A1 == B0...B1, and
365 positive if A0...A1 > B0...B1
366 according to COMPARE given auxiliary data AUX. */
368 llx_lexicographical_compare_3way (const struct llx *a0, const struct llx *a1,
369 const struct llx *b0, const struct llx *b1,
370 llx_compare_func *compare, void *aux)
379 int cmp = compare (llx_data (a0), llx_data (b0), aux);
388 /* Calls ACTION with auxiliary data AUX
389 for every node in R0...R1 in order. */
391 llx_apply (struct llx *r0, struct llx *r1,
392 llx_action_func *action, void *aux)
396 for (llx = r0; llx != r1; llx = llx_next (llx))
397 action (llx_data (llx), aux);
400 /* Reverses the order of nodes R0...R1. */
402 llx_reverse (struct llx *r0, struct llx *r1)
404 ll_reverse (&r0->ll, &r1->ll);
407 /* Arranges R0...R1 into the lexicographically next greater
408 permutation. Returns true if successful.
409 If R0...R1 is already the lexicographically greatest
410 permutation of its elements (i.e. ordered from greatest to
411 smallest), arranges them into the lexicographically least
412 permutation (i.e. ordered from smallest to largest) and
414 COMPARE with auxiliary data AUX is used to compare nodes. */
416 llx_next_permutation (struct llx *r0, struct llx *r1,
417 llx_compare_func *compare, void *aux)
421 struct llx *i = llx_prev (r1);
425 if (compare (llx_data (i), llx_data (llx_next (i)), aux) < 0)
428 for (j = llx_prev (r1);
429 compare (llx_data (i), llx_data (j), aux) >= 0;
433 llx_reverse (llx_next (j), r1);
438 llx_reverse (r0, r1);
444 /* Arranges R0...R1 into the lexicographically next lesser
445 permutation. Returns true if successful.
446 If R0...R1 is already the lexicographically least
447 permutation of its elements (i.e. ordered from smallest to
448 greatest), arranges them into the lexicographically greatest
449 permutation (i.e. ordered from largest to smallest) and
451 COMPARE with auxiliary data AUX is used to compare nodes. */
453 llx_prev_permutation (struct llx *r0, struct llx *r1,
454 llx_compare_func *compare, void *aux)
458 struct llx *i = llx_prev (r1);
462 if (compare (llx_data (i), llx_data (llx_next (i)), aux) > 0)
465 for (j = llx_prev (r1);
466 compare (llx_data (i), llx_data (j), aux) <= 0;
470 llx_reverse (llx_next (j), r1);
475 llx_reverse (r0, r1);
481 /* Sorts R0...R1 into ascending order
482 according to COMPARE given auxiliary data AUX.
483 In use, keep in mind that R0 may move during the sort, so that
484 afterward R0...R1 may denote a different range.
485 (On the other hand, R1 is fixed in place.)
486 Runs in O(n lg n) time in the number of nodes in the range. */
488 llx_sort (struct llx *r0, struct llx *r1, llx_compare_func *compare, void *aux)
491 size_t output_run_cnt;
493 if (r0 == r1 || llx_next (r0) == r1)
496 pre_r0 = llx_prev (r0);
499 struct llx *a0 = llx_next (pre_r0);
500 for (output_run_cnt = 1; ; output_run_cnt++)
502 struct llx *a1 = llx_find_run (a0, r1, compare, aux);
503 struct llx *a2 = llx_find_run (a1, r1, compare, aux);
507 a0 = llx_merge (a0, a1, a1, a2, compare, aux);
510 while (output_run_cnt > 1);
513 /* Finds the extent of a run of nodes of increasing value
514 starting at R0 and extending no farther than R1.
515 Returns the first node in R0...R1 that is less than the
516 preceding node, or R1 if R0...R1 are arranged in nondecreasing
519 llx_find_run (const struct llx *r0, const struct llx *r1,
520 llx_compare_func *compare, void *aux)
528 while (r0 != r1 && compare (llx_data (llx_prev (r0)),
529 llx_data (r0), aux) <= 0);
532 return (struct llx *) r0;
535 /* Merges B0...B1 into A0...A1 according to COMPARE given
537 The ranges may be in the same list or different lists, but
539 The merge is "stable" if A0...A1 is considered to precede
540 B0...B1, regardless of their actual ordering.
541 Runs in O(n) time in the total number of nodes in the ranges. */
543 llx_merge (struct llx *a0, struct llx *a1, struct llx *b0, struct llx *b1,
544 llx_compare_func *compare, void *aux)
546 if (a0 != a1 && b0 != b1)
551 if (compare (llx_data (a0), llx_data (b0), aux) <= 0)
555 llx_splice (llx_next (a0), b0, llx_next (b1));
556 return llx_next (b1);
566 llx_splice (a0, x, b0);
570 llx_splice (a0, b0, llx_next (b0));
571 return llx_next (a1);
577 llx_splice (a0, b0, b1);
582 /* Returns true if R0...R1 is sorted in ascending order according
583 to COMPARE given auxiliary data AUX,
586 llx_is_sorted (const struct llx *r0, const struct llx *r1,
587 llx_compare_func *compare, void *aux)
589 return llx_find_run (r0, r1, compare, aux) == r1;
592 /* Removes all but the first in each group of sequential
593 duplicates in R0...R1. Duplicates are determined using
594 COMPARE given auxiliary data AUX. Removed duplicates are
595 inserted before DUPS if it is nonnull; otherwise, the removed
596 duplicates are freed with MANAGER.
597 Only sequential duplicates are removed. llx_sort() may be used
598 to bring duplicates together, or llx_sort_unique() can do both
601 llx_unique (struct llx *r0, struct llx *r1, struct llx *dups,
602 llx_compare_func *compare, void *aux,
603 const struct llx_manager *manager)
612 struct llx *y = llx_next (x);
619 if (compare (llx_data (x), llx_data (y), aux) == 0)
622 llx_splice (dups, y, llx_next (y));
624 llx_remove (y, manager);
637 /* Sorts R0...R1 and removes duplicates.
638 Removed duplicates are inserted before DUPS if it is nonnull;
639 otherwise, the removed duplicates are freed with MANAGER.
640 Comparisons are made with COMPARE given auxiliary data AUX.
641 In use, keep in mind that R0 may move during the sort, so that
642 afterward R0...R1 may denote a different range.
643 (On the other hand, R1 is fixed in place.)
644 Runs in O(n lg n) time in the number of nodes in the range. */
646 llx_sort_unique (struct llx *r0, struct llx *r1, struct llx *dups,
647 llx_compare_func *compare, void *aux,
648 const struct llx_manager *manager)
650 struct llx *pre_r0 = llx_prev (r0);
651 llx_sort (r0, r1, compare, aux);
652 llx_unique (llx_next (pre_r0), r1, dups, compare, aux, manager);
655 /* Inserts DATA in the proper position in R0...R1, which must
656 be sorted according to COMPARE given auxiliary data AUX.
657 If DATA is equal to one or more existing nodes in R0...R1,
658 then it is inserted after the existing nodes it equals.
659 Returns the new node (allocated with MANAGER), or a null
660 pointer if memory allocation failed.
661 Runs in O(n) time in the number of nodes in the range. */
663 llx_insert_ordered (struct llx *r0, struct llx *r1, void *data,
664 llx_compare_func *compare, void *aux,
665 const struct llx_manager *manager)
669 for (x = r0; x != r1; x = llx_next (x))
670 if (compare (llx_data (x), data, aux) > 0)
672 return llx_insert (x, data, manager);
675 /* Partitions R0...R1 into those nodes for which PREDICATE given
676 auxiliary data AUX returns true, followed by those for which
677 PREDICATE returns false.
678 Returns the first node in the "false" group, or R1 if
679 PREDICATE is true for every node in R0...R1.
680 The partition is "stable" in that the nodes in each group
681 retain their original relative order.
682 Runs in O(n) time in the number of nodes in the range. */
684 llx_partition (struct llx *r0, struct llx *r1,
685 llx_predicate_func *predicate, void *aux)
693 else if (!predicate (llx_data (r0), aux))
699 for (t0 = r0;; t0 = t1)
707 while (!predicate (llx_data (t0), aux));
715 llx_splice (r0, t0, t1);
719 while (predicate (llx_data (t1), aux));
721 llx_splice (r0, t0, t1);
725 /* Verifies that R0...R1 is parititioned into a sequence of nodes
726 for which PREDICATE given auxiliary data AUX returns true,
727 followed by those for which PREDICATE returns false.
728 Returns a null pointer if R0...R1 is not partitioned this way.
729 Otherwise, returns the first node in the "false" group, or R1
730 if PREDICATE is true for every node in R0...R1. */
732 llx_find_partition (const struct llx *r0, const struct llx *r1,
733 llx_predicate_func *predicate, void *aux)
735 const struct llx *partition, *x;
737 for (partition = r0; partition != r1; partition = llx_next (partition))
738 if (!predicate (llx_data (partition), aux))
741 for (x = partition; x != r1; x = llx_next (x))
742 if (predicate (llx_data (x), aux))
745 return (struct llx *) partition;
748 /* Allocates and returns a node using malloc. */
750 malloc_allocate_node (void *aux UNUSED)
752 return malloc (sizeof (struct llx));
755 /* Releases node LLX with free. */
757 malloc_release_node (struct llx *llx, void *aux UNUSED)
762 /* Manager that uses the standard malloc and free routines. */
763 const struct llx_manager llx_malloc_mgr =
765 malloc_allocate_node,