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>
39 /* Destroys LIST and frees all of its nodes using MANAGER.
40 If DESTRUCTOR is non-null, each node in the list will be
41 passed to it in list order, with AUX as auxiliary data, before
42 that node is destroyed. */
44 llx_destroy (struct llx_list *list, llx_action_func *destructor, void *aux,
45 const struct llx_manager *manager)
47 struct llx *llx, *next;
49 for (llx = llx_head (list); llx != llx_null (list); llx = next)
51 next = llx_next (llx);
52 if (destructor != NULL)
53 destructor (llx_data (llx), aux);
54 manager->release (llx, manager->aux);
58 /* Returns the number of nodes in LIST (not counting the null
59 node). Executes in O(n) time in the length of the list. */
61 llx_count (const struct llx_list *list)
63 return llx_count_range (llx_head (list), llx_null (list));
66 /* Inserts DATA at the head of LIST.
67 Returns the new node (allocated with MANAGER), or a null
68 pointer if memory allocation failed. */
70 llx_push_head (struct llx_list *list, void *data,
71 const struct llx_manager *manager)
73 return llx_insert (llx_head (list), data, manager);
76 /* Inserts DATA at the tail of LIST.
77 Returns the new node (allocated with MANAGER), or a null
78 pointer if memory allocation failed. */
80 llx_push_tail (struct llx_list *list, void *data,
81 const struct llx_manager *manager)
83 return llx_insert (llx_null (list), data, manager);
86 /* Removes the first node in LIST, which must not be empty,
87 and returns the data that the node contained.
88 Frees the node removed with MANAGER. */
90 llx_pop_head (struct llx_list *list, const struct llx_manager *manager)
92 struct llx *llx = llx_from_ll (ll_head (&list->ll_list));
93 void *data = llx_data (llx);
94 llx_remove (llx, manager);
98 /* Removes the last node in LIST, which must not be empty,
99 and returns the data that the node contained.
100 Frees the node removed with MANAGER. */
102 llx_pop_tail (struct llx_list *list, const struct llx_manager *manager)
104 struct llx *llx = llx_from_ll (ll_tail (&list->ll_list));
105 void *data = llx_data (llx);
106 llx_remove (llx, manager);
110 /* Inserts DATA before BEFORE.
111 Returns the new node (allocated with MANAGER), or a null
112 pointer if memory allocation failed. */
114 llx_insert (struct llx *before, void *data, const struct llx_manager *manager)
116 struct llx *llx = manager->allocate (manager->aux);
120 ll_insert (&before->ll, &llx->ll);
125 /* Removes R0...R1 from their current list
126 and inserts them just before BEFORE. */
128 llx_splice (struct llx *before, struct llx *r0, struct llx *r1)
130 ll_splice (&before->ll, &r0->ll, &r1->ll);
133 /* Exchanges the positions of A and B,
134 which may be in the same list or different lists. */
136 llx_swap (struct llx *a, struct llx *b)
138 ll_swap (&a->ll, &b->ll);
141 /* Exchanges the positions of A0...A1 and B0...B1,
142 which may be in the same list or different lists but must not
145 llx_swap_range (struct llx *a0, struct llx *a1,
146 struct llx *b0, struct llx *b1)
148 ll_swap_range (&a0->ll, &a1->ll, &b0->ll, &b1->ll);
151 /* Removes LLX from its list
152 and returns the node that formerly followed it.
153 Frees the node removed with MANAGER. */
155 llx_remove (struct llx *llx, const struct llx_manager *manager)
157 struct llx *next = llx_next (llx);
158 ll_remove (&llx->ll);
159 manager->release (llx, manager->aux);
163 /* Removes R0...R1 from their list.
164 Frees the removed nodes with MANAGER. */
166 llx_remove_range (struct llx *r0, struct llx *r1,
167 const struct llx_manager *manager)
171 for (llx = r0; llx != r1; )
172 llx = llx_remove (llx, manager);
175 /* Removes from R0...R1 all the nodes that equal TARGET
176 according to COMPARE given auxiliary data AUX.
177 Frees the removed nodes with MANAGER.
178 Returns the number of nodes removed. */
180 llx_remove_equal (struct llx *r0, struct llx *r1, const void *target,
181 llx_compare_func *compare, void *aux,
182 const struct llx_manager *manager)
188 for (x = r0; x != r1; )
189 if (compare (llx_data (x), target, aux) == 0)
191 x = llx_remove (x, manager);
200 /* Removes from R0...R1 all the nodes for which PREDICATE returns
201 true given auxiliary data AUX.
202 Frees the removed nodes with MANAGER.
203 Returns the number of nodes removed. */
205 llx_remove_if (struct llx *r0, struct llx *r1,
206 llx_predicate_func *predicate, void *aux,
207 const struct llx_manager *manager)
213 for (x = r0; x != r1; )
214 if (predicate (llx_data (x), aux))
216 x = llx_remove (x, manager);
225 /* Returns the first node in R0...R1 that equals TARGET
226 according to COMPARE given auxiliary data AUX.
227 Returns R1 if no node in R0...R1 equals TARGET. */
229 llx_find_equal (const struct llx *r0, const struct llx *r1,
231 llx_compare_func *compare, void *aux)
235 for (x = r0; x != r1; x = llx_next (x))
236 if (compare (llx_data (x), target, aux) == 0)
238 return (struct llx *) x;
241 /* Returns the first node in R0...R1 for which PREDICATE returns
242 true given auxiliary data AUX.
243 Returns R1 if PREDICATE does not return true for any node in
246 llx_find_if (const struct llx *r0, const struct llx *r1,
247 llx_predicate_func *predicate, void *aux)
251 for (x = r0; x != r1; x = llx_next (x))
252 if (predicate (llx_data (x), aux))
254 return (struct llx *) x;
257 /* Compares each pair of adjacent nodes in R0...R1
258 using COMPARE with auxiliary data AUX
259 and returns the first node of the first pair that compares
261 Returns R1 if no pair compares equal. */
263 llx_find_adjacent_equal (const struct llx *r0, const struct llx *r1,
264 llx_compare_func *compare, void *aux)
268 const struct llx *x, *y;
270 for (x = r0, y = llx_next (x); y != r1; x = y, y = llx_next (y))
271 if (compare (llx_data (x), llx_data (y), aux) == 0)
272 return (struct llx *) x;
275 return (struct llx *) r1;
278 /* Returns the number of nodes in R0...R1.
279 Executes in O(n) time in the return value. */
281 llx_count_range (const struct llx *r0, const struct llx *r1)
283 return ll_count_range (&r0->ll, &r1->ll);
286 /* Counts and returns the number of nodes in R0...R1 that equal
287 TARGET according to COMPARE given auxiliary data AUX. */
289 llx_count_equal (const struct llx *r0, const struct llx *r1,
291 llx_compare_func *compare, void *aux)
297 for (x = r0; x != r1; x = llx_next (x))
298 if (compare (llx_data (x), target, aux) == 0)
303 /* Counts and returns the number of nodes in R0...R1 for which
304 PREDICATE returns true given auxiliary data AUX. */
306 llx_count_if (const struct llx *r0, const struct llx *r1,
307 llx_predicate_func *predicate, void *aux)
313 for (x = r0; x != r1; x = llx_next (x))
314 if (predicate (llx_data (x), aux))
319 /* Returns the greatest node in R0...R1 according to COMPARE
320 given auxiliary data AUX.
321 Returns the first of multiple, equal maxima. */
323 llx_max (const struct llx *r0, const struct llx *r1,
324 llx_compare_func *compare, void *aux)
326 const struct llx *max = r0;
331 for (x = llx_next (r0); x != r1; x = llx_next (x))
332 if (compare (llx_data (x), llx_data (max), aux) > 0)
335 return (struct llx *) max;
338 /* Returns the least node in R0...R1 according to COMPARE given
340 Returns the first of multiple, equal minima. */
342 llx_min (const struct llx *r0, const struct llx *r1,
343 llx_compare_func *compare, void *aux)
345 const struct llx *min = r0;
350 for (x = llx_next (r0); x != r1; x = llx_next (x))
351 if (compare (llx_data (x), llx_data (min), aux) < 0)
354 return (struct llx *) min;
357 /* Lexicographically compares A0...A1 to B0...B1.
358 Returns negative if A0...A1 < B0...B1,
359 zero if A0...A1 == B0...B1, and
360 positive if A0...A1 > B0...B1
361 according to COMPARE given auxiliary data AUX. */
363 llx_lexicographical_compare_3way (const struct llx *a0, const struct llx *a1,
364 const struct llx *b0, const struct llx *b1,
365 llx_compare_func *compare, void *aux)
374 int cmp = compare (llx_data (a0), llx_data (b0), aux);
383 /* Calls ACTION with auxiliary data AUX
384 for every node in R0...R1 in order. */
386 llx_apply (struct llx *r0, struct llx *r1,
387 llx_action_func *action, void *aux)
391 for (llx = r0; llx != r1; llx = llx_next (llx))
392 action (llx_data (llx), aux);
395 /* Reverses the order of nodes R0...R1. */
397 llx_reverse (struct llx *r0, struct llx *r1)
399 ll_reverse (&r0->ll, &r1->ll);
402 /* Arranges R0...R1 into the lexicographically next greater
403 permutation. Returns true if successful.
404 If R0...R1 is already the lexicographically greatest
405 permutation of its elements (i.e. ordered from greatest to
406 smallest), arranges them into the lexicographically least
407 permutation (i.e. ordered from smallest to largest) and
409 COMPARE with auxiliary data AUX is used to compare nodes. */
411 llx_next_permutation (struct llx *r0, struct llx *r1,
412 llx_compare_func *compare, void *aux)
416 struct llx *i = llx_prev (r1);
420 if (compare (llx_data (i), llx_data (llx_next (i)), aux) < 0)
423 for (j = llx_prev (r1);
424 compare (llx_data (i), llx_data (j), aux) >= 0;
428 llx_reverse (llx_next (j), r1);
433 llx_reverse (r0, r1);
439 /* Arranges R0...R1 into the lexicographically next lesser
440 permutation. Returns true if successful.
441 If R0...R1 is already the lexicographically least
442 permutation of its elements (i.e. ordered from smallest to
443 greatest), arranges them into the lexicographically greatest
444 permutation (i.e. ordered from largest to smallest) and
446 COMPARE with auxiliary data AUX is used to compare nodes. */
448 llx_prev_permutation (struct llx *r0, struct llx *r1,
449 llx_compare_func *compare, void *aux)
453 struct llx *i = llx_prev (r1);
457 if (compare (llx_data (i), llx_data (llx_next (i)), aux) > 0)
460 for (j = llx_prev (r1);
461 compare (llx_data (i), llx_data (j), aux) <= 0;
465 llx_reverse (llx_next (j), r1);
470 llx_reverse (r0, r1);
476 /* Sorts R0...R1 into ascending order
477 according to COMPARE given auxiliary data AUX.
478 In use, keep in mind that R0 may move during the sort, so that
479 afterward R0...R1 may denote a different range.
480 (On the other hand, R1 is fixed in place.)
481 Runs in O(n lg n) time in the number of nodes in the range. */
483 llx_sort (struct llx *r0, struct llx *r1, llx_compare_func *compare, void *aux)
486 size_t output_run_cnt;
488 if (r0 == r1 || llx_next (r0) == r1)
491 pre_r0 = llx_prev (r0);
494 struct llx *a0 = llx_next (pre_r0);
495 for (output_run_cnt = 1; ; output_run_cnt++)
497 struct llx *a1 = llx_find_run (a0, r1, compare, aux);
498 struct llx *a2 = llx_find_run (a1, r1, compare, aux);
502 a0 = llx_merge (a0, a1, a1, a2, compare, aux);
505 while (output_run_cnt > 1);
508 /* Finds the extent of a run of nodes of increasing value
509 starting at R0 and extending no farther than R1.
510 Returns the first node in R0...R1 that is less than the
511 preceding node, or R1 if R0...R1 are arranged in nondecreasing
514 llx_find_run (const struct llx *r0, const struct llx *r1,
515 llx_compare_func *compare, void *aux)
523 while (r0 != r1 && compare (llx_data (llx_prev (r0)),
524 llx_data (r0), aux) <= 0);
527 return (struct llx *) r0;
530 /* Merges B0...B1 into A0...A1 according to COMPARE given
532 The ranges may be in the same list or different lists, but
534 The merge is "stable" if A0...A1 is considered to precede
535 B0...B1, regardless of their actual ordering.
536 Runs in O(n) time in the total number of nodes in the ranges. */
538 llx_merge (struct llx *a0, struct llx *a1, struct llx *b0, struct llx *b1,
539 llx_compare_func *compare, void *aux)
541 if (a0 != a1 && b0 != b1)
546 if (compare (llx_data (a0), llx_data (b0), aux) <= 0)
550 llx_splice (llx_next (a0), b0, llx_next (b1));
551 return llx_next (b1);
561 llx_splice (a0, x, b0);
565 llx_splice (a0, b0, llx_next (b0));
566 return llx_next (a1);
572 llx_splice (a0, b0, b1);
577 /* Returns true if R0...R1 is sorted in ascending order according
578 to COMPARE given auxiliary data AUX,
581 llx_is_sorted (const struct llx *r0, const struct llx *r1,
582 llx_compare_func *compare, void *aux)
584 return llx_find_run (r0, r1, compare, aux) == r1;
587 /* Removes all but the first in each group of sequential
588 duplicates in R0...R1. Duplicates are determined using
589 COMPARE given auxiliary data AUX. Removed duplicates are
590 inserted before DUPS if it is nonnull; otherwise, the removed
591 duplicates are freed with MANAGER.
592 Only sequential duplicates are removed. llx_sort() may be used
593 to bring duplicates together, or llx_sort_unique() can do both
596 llx_unique (struct llx *r0, struct llx *r1, struct llx *dups,
597 llx_compare_func *compare, void *aux,
598 const struct llx_manager *manager)
607 struct llx *y = llx_next (x);
614 if (compare (llx_data (x), llx_data (y), aux) == 0)
617 llx_splice (dups, y, llx_next (y));
619 llx_remove (y, manager);
632 /* Sorts R0...R1 and removes duplicates.
633 Removed duplicates are inserted before DUPS if it is nonnull;
634 otherwise, the removed duplicates are freed with MANAGER.
635 Comparisons are made with COMPARE given auxiliary data AUX.
636 In use, keep in mind that R0 may move during the sort, so that
637 afterward R0...R1 may denote a different range.
638 (On the other hand, R1 is fixed in place.)
639 Runs in O(n lg n) time in the number of nodes in the range. */
641 llx_sort_unique (struct llx *r0, struct llx *r1, struct llx *dups,
642 llx_compare_func *compare, void *aux,
643 const struct llx_manager *manager)
645 struct llx *pre_r0 = llx_prev (r0);
646 llx_sort (r0, r1, compare, aux);
647 llx_unique (llx_next (pre_r0), r1, dups, compare, aux, manager);
650 /* Inserts DATA in the proper position in R0...R1, which must
651 be sorted according to COMPARE given auxiliary data AUX.
652 If DATA is equal to one or more existing nodes in R0...R1,
653 then it is inserted after the existing nodes it equals.
654 Returns the new node (allocated with MANAGER), or a null
655 pointer if memory allocation failed.
656 Runs in O(n) time in the number of nodes in the range. */
658 llx_insert_ordered (struct llx *r0, struct llx *r1, void *data,
659 llx_compare_func *compare, void *aux,
660 const struct llx_manager *manager)
664 for (x = r0; x != r1; x = llx_next (x))
665 if (compare (llx_data (x), data, aux) > 0)
667 return llx_insert (x, data, manager);
670 /* Partitions R0...R1 into those nodes for which PREDICATE given
671 auxiliary data AUX returns true, followed by those for which
672 PREDICATE returns false.
673 Returns the first node in the "false" group, or R1 if
674 PREDICATE is true for every node in R0...R1.
675 The partition is "stable" in that the nodes in each group
676 retain their original relative order.
677 Runs in O(n) time in the number of nodes in the range. */
679 llx_partition (struct llx *r0, struct llx *r1,
680 llx_predicate_func *predicate, void *aux)
688 else if (!predicate (llx_data (r0), aux))
694 for (t0 = r0;; t0 = t1)
702 while (!predicate (llx_data (t0), aux));
710 llx_splice (r0, t0, t1);
714 while (predicate (llx_data (t1), aux));
716 llx_splice (r0, t0, t1);
720 /* Verifies that R0...R1 is parititioned into a sequence of nodes
721 for which PREDICATE given auxiliary data AUX returns true,
722 followed by those for which PREDICATE returns false.
723 Returns a null pointer if R0...R1 is not partitioned this way.
724 Otherwise, returns the first node in the "false" group, or R1
725 if PREDICATE is true for every node in R0...R1. */
727 llx_find_partition (const struct llx *r0, const struct llx *r1,
728 llx_predicate_func *predicate, void *aux)
730 const struct llx *partition, *x;
732 for (partition = r0; partition != r1; partition = llx_next (partition))
733 if (!predicate (llx_data (partition), aux))
736 for (x = partition; x != r1; x = llx_next (x))
737 if (predicate (llx_data (x), aux))
740 return (struct llx *) partition;
743 /* Allocates and returns a node using malloc. */
745 malloc_allocate_node (void *aux UNUSED)
747 return malloc (sizeof (struct llx));
750 /* Releases node LLX with free. */
752 malloc_release_node (struct llx *llx, void *aux UNUSED)
757 /* Manager that uses the standard malloc and free routines. */
758 const struct llx_manager llx_malloc_mgr =
760 malloc_allocate_node,