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 /* Embedded, circular doubly linked list. */
22 /* These library routines have no external dependencies other
23 than the standard C library.
25 If you add routines in this file, please add a corresponding
26 test to ll-test.c. This test program should achieve 100%
27 coverage of lines and branches in this code, as reported by
34 #include <libpspp/ll.h>
37 /* Returns the number of nodes in LIST (not counting the null
38 node). Executes in O(n) time in the length of the list. */
40 ll_count (const struct ll_list *list)
42 return ll_count_range (ll_head (list), ll_null (list));
45 /* Removes R0...R1 from their current list
46 and inserts them just before BEFORE. */
48 ll_splice (struct ll *before, struct ll *r0, struct ll *r1)
50 if (before != r0 && r0 != r1)
52 /* Change exclusive range to inclusive. */
55 /* Remove R0...R1 from its list. */
56 r0->prev->next = r1->next;
57 r1->next->prev = r0->prev;
59 /* Insert R0...R1 before BEFORE. */
60 r0->prev = before->prev;
62 before->prev->next = r0;
67 /* Exchanges the positions of A and B,
68 which may be in the same list or different lists. */
70 ll_swap (struct ll *a, struct ll *b)
76 struct ll *a_next = ll_remove (a);
77 struct ll *b_next = ll_remove (b);
78 ll_insert (b_next, a);
79 ll_insert (a_next, b);
89 /* Exchanges the positions of A0...A1 and B0...B1,
90 which may be in the same list or different lists but must not
93 ll_swap_range (struct ll *a0, struct ll *a1, struct ll *b0, struct ll *b1)
95 if (a0 == a1 || a1 == b0)
96 ll_splice (a0, b0, b1);
97 else if (b0 == b1 || b1 == a0)
98 ll_splice (b0, a0, a1);
101 struct ll *x0 = ll_prev (a0), *x1 = a1;
102 struct ll *y0 = ll_prev (b0), *y1 = b1;
116 /* Removes from R0...R1 all the nodes that equal TARGET
117 according to COMPARE given auxiliary data AUX.
118 Returns the number of nodes removed. */
120 ll_remove_equal (struct ll *r0, struct ll *r1, struct ll *target,
121 ll_compare_func *compare, void *aux)
127 for (x = r0; x != r1; )
128 if (compare (x, target, aux) == 0)
139 /* Removes from R0...R1 all the nodes for which PREDICATE returns
140 true given auxiliary data AUX.
141 Returns the number of nodes removed. */
143 ll_remove_if (struct ll *r0, struct ll *r1,
144 ll_predicate_func *predicate, void *aux)
150 for (x = r0; x != r1; )
151 if (predicate (x, aux))
162 /* Returns the first node in R0...R1 that equals TARGET
163 according to COMPARE given auxiliary data AUX.
164 Returns R1 if no node in R0...R1 equals TARGET. */
166 ll_find_equal (const struct ll *r0, const struct ll *r1,
167 const struct ll *target,
168 ll_compare_func *compare, void *aux)
172 for (x = r0; x != r1; x = ll_next (x))
173 if (compare (x, target, aux) == 0)
175 return (struct ll *) x;
178 /* Returns the first node in R0...R1 for which PREDICATE returns
179 true given auxiliary data AUX.
180 Returns R1 if PREDICATE does not return true for any node in
183 ll_find_if (const struct ll *r0, const struct ll *r1,
184 ll_predicate_func *predicate, void *aux)
188 for (x = r0; x != r1; x = ll_next (x))
189 if (predicate (x, aux))
191 return (struct ll *) x;
194 /* Compares each pair of adjacent nodes in R0...R1
195 using COMPARE with auxiliary data AUX
196 and returns the first node of the first pair that compares
198 Returns R1 if no pair compares equal. */
200 ll_find_adjacent_equal (const struct ll *r0, const struct ll *r1,
201 ll_compare_func *compare, void *aux)
205 const struct ll *x, *y;
207 for (x = r0, y = ll_next (x); y != r1; x = y, y = ll_next (y))
208 if (compare (x, y, aux) == 0)
209 return (struct ll *) x;
212 return (struct ll *) r1;
215 /* Returns the number of nodes in R0...R1.
216 Executes in O(n) time in the return value. */
218 ll_count_range (const struct ll *r0, const struct ll *r1)
224 for (x = r0; x != r1; x = ll_next (x))
229 /* Counts and returns the number of nodes in R0...R1 that equal
230 TARGET according to COMPARE given auxiliary data AUX. */
232 ll_count_equal (const struct ll *r0, const struct ll *r1,
233 const struct ll *target,
234 ll_compare_func *compare, void *aux)
240 for (x = r0; x != r1; x = ll_next (x))
241 if (compare (x, target, aux) == 0)
246 /* Counts and returns the number of nodes in R0...R1 for which
247 PREDICATE returns true given auxiliary data AUX. */
249 ll_count_if (const struct ll *r0, const struct ll *r1,
250 ll_predicate_func *predicate, void *aux)
256 for (x = r0; x != r1; x = ll_next (x))
257 if (predicate (x, aux))
262 /* Returns the greatest node in R0...R1 according to COMPARE
263 given auxiliary data AUX.
264 Returns the first of multiple, equal maxima. */
266 ll_max (const struct ll *r0, const struct ll *r1,
267 ll_compare_func *compare, void *aux)
269 const struct ll *max = r0;
274 for (x = ll_next (r0); x != r1; x = ll_next (x))
275 if (compare (x, max, aux) > 0)
278 return (struct ll *) max;
281 /* Returns the least node in R0...R1 according to COMPARE given
283 Returns the first of multiple, equal minima. */
285 ll_min (const struct ll *r0, const struct ll *r1,
286 ll_compare_func *compare, void *aux)
288 const struct ll *min = r0;
293 for (x = ll_next (r0); x != r1; x = ll_next (x))
294 if (compare (x, min, aux) < 0)
297 return (struct ll *) min;
300 /* Lexicographically compares A0...A1 to B0...B1.
301 Returns negative if A0...A1 < B0...B1,
302 zero if A0...A1 == B0...B1, and
303 positive if A0...A1 > B0...B1
304 according to COMPARE given auxiliary data AUX. */
306 ll_lexicographical_compare_3way (const struct ll *a0, const struct ll *a1,
307 const struct ll *b0, const struct ll *b1,
308 ll_compare_func *compare, void *aux)
317 int cmp = compare (a0, b0, aux);
326 /* Calls ACTION with auxiliary data AUX
327 for every node in R0...R1 in order. */
329 ll_apply (struct ll *r0, struct ll *r1, ll_action_func *action, void *aux)
333 for (ll = r0; ll != r1; ll = ll_next (ll))
337 /* Reverses the order of nodes R0...R1. */
339 ll_reverse (struct ll *r0, struct ll *r1)
341 if (r0 != r1 && ll_next (r0) != r1)
345 for (ll = r0; ll != r1; ll = ll->prev)
347 struct ll *tmp = ll->next;
351 r0->next->next = r1->prev;
352 r1->prev->prev = r0->next;
358 /* Arranges R0...R1 into the lexicographically next greater
359 permutation. Returns true if successful.
360 If R0...R1 is already the lexicographically greatest
361 permutation of its elements (i.e. ordered from greatest to
362 smallest), arranges them into the lexicographically least
363 permutation (i.e. ordered from smallest to largest) and
365 COMPARE with auxiliary data AUX is used to compare nodes. */
367 ll_next_permutation (struct ll *r0, struct ll *r1,
368 ll_compare_func *compare, void *aux)
372 struct ll *i = ll_prev (r1);
376 if (compare (i, ll_next (i), aux) < 0)
379 for (j = ll_prev (r1); compare (i, j, aux) >= 0; j = ll_prev (j))
382 ll_reverse (ll_next (j), r1);
393 /* Arranges R0...R1 into the lexicographically next lesser
394 permutation. Returns true if successful.
395 If R0...R1 is already the lexicographically least
396 permutation of its elements (i.e. ordered from smallest to
397 greatest), arranges them into the lexicographically greatest
398 permutation (i.e. ordered from largest to smallest) and
400 COMPARE with auxiliary data AUX is used to compare nodes. */
402 ll_prev_permutation (struct ll *r0, struct ll *r1,
403 ll_compare_func *compare, void *aux)
407 struct ll *i = ll_prev (r1);
411 if (compare (i, ll_next (i), aux) > 0)
414 for (j = ll_prev (r1); compare (i, j, aux) <= 0; j = ll_prev (j))
417 ll_reverse (ll_next (j), r1);
428 /* Sorts R0...R1 into ascending order
429 according to COMPARE given auxiliary data AUX.
430 In use, keep in mind that R0 may move during the sort, so that
431 afterward R0...R1 may denote a different range.
432 (On the other hand, R1 is fixed in place.)
433 Runs in O(n lg n) time in the number of nodes in the range. */
435 ll_sort (struct ll *r0, struct ll *r1, ll_compare_func *compare, void *aux)
438 size_t output_run_cnt;
440 if (r0 == r1 || ll_next (r0) == r1)
443 pre_r0 = ll_prev (r0);
446 struct ll *a0 = ll_next (pre_r0);
447 for (output_run_cnt = 1; ; output_run_cnt++)
449 struct ll *a1 = ll_find_run (a0, r1, compare, aux);
450 struct ll *a2 = ll_find_run (a1, r1, compare, aux);
454 a0 = ll_merge (a0, a1, a1, a2, compare, aux);
457 while (output_run_cnt > 1);
460 /* Finds the extent of a run of nodes of increasing value
461 starting at R0 and extending no farther than R1.
462 Returns the first node in R0...R1 that is less than the
463 preceding node, or R1 if R0...R1 are arranged in nondecreasing
466 ll_find_run (const struct ll *r0, const struct ll *r1,
467 ll_compare_func *compare, void *aux)
475 while (r0 != r1 && compare (ll_prev (r0), r0, aux) <= 0);
478 return (struct ll *) r0;
481 /* Merges B0...B1 into A0...A1 according to COMPARE given
483 The ranges may be in the same list or different lists, but
485 Returns the end of the merged range.
486 The merge is "stable" if A0...A1 is considered to precede
487 B0...B1, regardless of their actual ordering.
488 Runs in O(n) time in the total number of nodes in the ranges. */
490 ll_merge (struct ll *a0, struct ll *a1, struct ll *b0, struct ll *b1,
491 ll_compare_func *compare, void *aux)
493 if (a0 != a1 && b0 != b1)
498 if (compare (a0, b0, aux) <= 0)
502 ll_splice (ll_next (a0), b0, ll_next (b1));
517 ll_splice (a0, b0, ll_next (b0));
524 ll_splice (a0, b0, b1);
529 /* Returns true if R0...R1 is sorted in ascending order according
530 to COMPARE given auxiliary data AUX, false otherwise. */
532 ll_is_sorted (const struct ll *r0, const struct ll *r1,
533 ll_compare_func *compare, void *aux)
535 return ll_find_run (r0, r1, compare, aux) == r1;
538 /* Removes all but the first in each group of sequential
539 duplicates in R0...R1. Duplicates are determined using
540 COMPARE given auxiliary data AUX. Removed duplicates are
541 inserted before DUPS if it is nonnull; otherwise, their
543 Only sequential duplicates are removed. ll_sort() may be used
544 to bring duplicates together, or ll_sort_unique() can do both
547 ll_unique (struct ll *r0, struct ll *r1, struct ll *dups,
548 ll_compare_func *compare, void *aux)
557 struct ll *y = ll_next (x);
564 if (compare (x, y, aux) == 0)
581 /* Sorts R0...R1 and removes duplicates.
582 Removed duplicates are inserted before DUPS if it is nonnull;
583 otherwise, their identities are lost.
584 Comparisons are made with COMPARE given auxiliary data AUX.
585 In use, keep in mind that R0 may move during the sort, so that
586 afterward R0...R1 may denote a different range.
587 (On the other hand, R1 is fixed in place.)
588 Runs in O(n lg n) time in the number of nodes in the range. */
590 ll_sort_unique (struct ll *r0, struct ll *r1, struct ll *dups,
591 ll_compare_func *compare, void *aux)
593 struct ll *pre_r0 = ll_prev (r0);
594 ll_sort (r0, r1, compare, aux);
595 ll_unique (ll_next (pre_r0), r1, dups, compare, aux);
598 /* Inserts NEW_ELEM in the proper position in R0...R1, which must
599 be sorted according to COMPARE given auxiliary data AUX.
600 If NEW_ELEM is equal to one or more existing nodes in R0...R1,
601 then it is inserted after the existing nodes it equals.
602 Runs in O(n) time in the number of nodes in the range. */
604 ll_insert_ordered (struct ll *r0, struct ll *r1, struct ll *new_elem,
605 ll_compare_func *compare, void *aux)
609 for (x = r0; x != r1; x = ll_next (x))
610 if (compare (x, new_elem, aux) > 0)
612 ll_insert (x, new_elem);
615 /* Partitions R0...R1 into those nodes for which PREDICATE given
616 auxiliary data AUX returns true, followed by those for which
617 PREDICATE returns false.
618 Returns the first node in the "false" group, or R1 if
619 PREDICATE is true for every node in R0...R1.
620 The partition is "stable" in that the nodes in each group
621 retain their original relative order.
622 Runs in O(n) time in the number of nodes in the range. */
624 ll_partition (struct ll *r0, struct ll *r1,
625 ll_predicate_func *predicate, void *aux)
633 else if (!predicate (r0, aux))
639 for (t0 = r0;; t0 = t1)
647 while (!predicate (t0, aux));
655 ll_splice (r0, t0, t1);
659 while (predicate (t1, aux));
661 ll_splice (r0, t0, t1);
665 /* Verifies that R0...R1 is parititioned into a sequence of nodes
666 for which PREDICATE given auxiliary data AUX returns true,
667 followed by those for which PREDICATE returns false.
668 Returns a null pointer if R0...R1 is not partitioned this way.
669 Otherwise, returns the first node in the "false" group, or R1
670 if PREDICATE is true for every node in R0...R1. */
672 ll_find_partition (const struct ll *r0, const struct ll *r1,
673 ll_predicate_func *predicate, void *aux)
675 const struct ll *partition, *x;
677 for (partition = r0; partition != r1; partition = ll_next (partition))
678 if (!predicate (partition, aux))
681 for (x = partition; x != r1; x = ll_next (x))
682 if (predicate (x, aux))
685 return (struct ll *) partition;