1 /* PSPP - computes sample statistics.
2 Copyright (C) 2006 Free Software Foundation, Inc.
4 This program is free software; you can redistribute it and/or
5 modify it under the terms of the GNU General Public License as
6 published by the Free Software Foundation; either version 2 of the
7 License, or (at your option) any later version.
9 This program is distributed in the hope that it will be useful, but
10 WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 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, write to the Free Software
16 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
19 /* Embedded, circular doubly linked list. */
21 /* These library routines have no external dependencies other
22 than the standard C library.
24 If you add routines in this file, please add a corresponding
25 test to ll-test.c. This test program should achieve 100%
26 coverage of lines and branches in this code, as reported by
33 #include <libpspp/ll.h>
36 /* Returns the number of nodes in LIST (not counting the null
37 node). Executes in O(n) time in the length of the list. */
39 ll_count (const struct ll_list *list)
41 return ll_count_range (ll_head (list), ll_null (list));
44 /* Removes R0...R1 from their current list
45 and inserts them just before BEFORE. */
47 ll_splice (struct ll *before, struct ll *r0, struct ll *r1)
49 if (before != r0 && r0 != r1)
51 /* Change exclusive range to inclusive. */
54 /* Remove R0...R1 from its list. */
55 r0->prev->next = r1->next;
56 r1->next->prev = r0->prev;
58 /* Insert R0...R1 before BEFORE. */
59 r0->prev = before->prev;
61 before->prev->next = r0;
66 /* Exchanges the positions of A and B,
67 which may be in the same list or different lists. */
69 ll_swap (struct ll *a, struct ll *b)
75 struct ll *a_next = ll_remove (a);
76 struct ll *b_next = ll_remove (b);
77 ll_insert (b_next, a);
78 ll_insert (a_next, b);
88 /* Exchanges the positions of A0...A1 and B0...B1,
89 which may be in the same list or different lists but must not
92 ll_swap_range (struct ll *a0, struct ll *a1, struct ll *b0, struct ll *b1)
94 if (a0 == a1 || a1 == b0)
95 ll_splice (a0, b0, b1);
96 else if (b0 == b1 || b1 == a0)
97 ll_splice (b0, a0, a1);
100 struct ll *x0 = ll_prev (a0), *x1 = a1;
101 struct ll *y0 = ll_prev (b0), *y1 = b1;
115 /* Removes from R0...R1 all the nodes that equal TARGET
116 according to COMPARE given auxiliary data AUX.
117 Returns the number of nodes removed. */
119 ll_remove_equal (struct ll *r0, struct ll *r1, struct ll *target,
120 ll_compare_func *compare, void *aux)
126 for (x = r0; x != r1; )
127 if (compare (x, target, aux) == 0)
138 /* Removes from R0...R1 all the nodes for which PREDICATE returns
139 true given auxiliary data AUX.
140 Returns the number of nodes removed. */
142 ll_remove_if (struct ll *r0, struct ll *r1,
143 ll_predicate_func *predicate, void *aux)
149 for (x = r0; x != r1; )
150 if (predicate (x, aux))
161 /* Returns the first node in R0...R1 that equals TARGET
162 according to COMPARE given auxiliary data AUX.
163 Returns R1 if no node in R0...R1 equals TARGET. */
165 ll_find_equal (const struct ll *r0, const struct ll *r1,
166 const struct ll *target,
167 ll_compare_func *compare, void *aux)
171 for (x = r0; x != r1; x = ll_next (x))
172 if (compare (x, target, aux) == 0)
174 return (struct ll *) x;
177 /* Returns the first node in R0...R1 for which PREDICATE returns
178 true given auxiliary data AUX.
179 Returns R1 if PREDICATE does not return true for any node in
182 ll_find_if (const struct ll *r0, const struct ll *r1,
183 ll_predicate_func *predicate, void *aux)
187 for (x = r0; x != r1; x = ll_next (x))
188 if (predicate (x, aux))
190 return (struct ll *) x;
193 /* Compares each pair of adjacent nodes in R0...R1
194 using COMPARE with auxiliary data AUX
195 and returns the first node of the first pair that compares
197 Returns R1 if no pair compares equal. */
199 ll_find_adjacent_equal (const struct ll *r0, const struct ll *r1,
200 ll_compare_func *compare, void *aux)
204 const struct ll *x, *y;
206 for (x = r0, y = ll_next (x); y != r1; x = y, y = ll_next (y))
207 if (compare (x, y, aux) == 0)
208 return (struct ll *) x;
211 return (struct ll *) r1;
214 /* Returns the number of nodes in R0...R1.
215 Executes in O(n) time in the return value. */
217 ll_count_range (const struct ll *r0, const struct ll *r1)
223 for (x = r0; x != r1; x = ll_next (x))
228 /* Counts and returns the number of nodes in R0...R1 that equal
229 TARGET according to COMPARE given auxiliary data AUX. */
231 ll_count_equal (const struct ll *r0, const struct ll *r1,
232 const struct ll *target,
233 ll_compare_func *compare, void *aux)
239 for (x = r0; x != r1; x = ll_next (x))
240 if (compare (x, target, aux) == 0)
245 /* Counts and returns the number of nodes in R0...R1 for which
246 PREDICATE returns true given auxiliary data AUX. */
248 ll_count_if (const struct ll *r0, const struct ll *r1,
249 ll_predicate_func *predicate, void *aux)
255 for (x = r0; x != r1; x = ll_next (x))
256 if (predicate (x, aux))
261 /* Returns the greatest node in R0...R1 according to COMPARE
262 given auxiliary data AUX.
263 Returns the first of multiple, equal maxima. */
265 ll_max (const struct ll *r0, const struct ll *r1,
266 ll_compare_func *compare, void *aux)
268 const struct ll *max = r0;
273 for (x = ll_next (r0); x != r1; x = ll_next (x))
274 if (compare (x, max, aux) > 0)
277 return (struct ll *) max;
280 /* Returns the least node in R0...R1 according to COMPARE given
282 Returns the first of multiple, equal minima. */
284 ll_min (const struct ll *r0, const struct ll *r1,
285 ll_compare_func *compare, void *aux)
287 const struct ll *min = r0;
292 for (x = ll_next (r0); x != r1; x = ll_next (x))
293 if (compare (x, min, aux) < 0)
296 return (struct ll *) min;
299 /* Lexicographically compares A0...A1 to B0...B1.
300 Returns negative if A0...A1 < B0...B1,
301 zero if A0...A1 == B0...B1, and
302 positive if A0...A1 > B0...B1
303 according to COMPARE given auxiliary data AUX. */
305 ll_lexicographical_compare_3way (const struct ll *a0, const struct ll *a1,
306 const struct ll *b0, const struct ll *b1,
307 ll_compare_func *compare, void *aux)
316 int cmp = compare (a0, b0, aux);
325 /* Calls ACTION with auxiliary data AUX
326 for every node in R0...R1 in order. */
328 ll_apply (struct ll *r0, struct ll *r1, ll_action_func *action, void *aux)
332 for (ll = r0; ll != r1; ll = ll_next (ll))
336 /* Reverses the order of nodes R0...R1. */
338 ll_reverse (struct ll *r0, struct ll *r1)
340 if (r0 != r1 && ll_next (r0) != r1)
344 for (ll = r0; ll != r1; ll = ll->prev)
346 struct ll *tmp = ll->next;
350 r0->next->next = r1->prev;
351 r1->prev->prev = r0->next;
357 /* Arranges R0...R1 into the lexicographically next greater
358 permutation. Returns true if successful.
359 If R0...R1 is already the lexicographically greatest
360 permutation of its elements (i.e. ordered from greatest to
361 smallest), arranges them into the lexicographically least
362 permutation (i.e. ordered from smallest to largest) and
364 COMPARE with auxiliary data AUX is used to compare nodes. */
366 ll_next_permutation (struct ll *r0, struct ll *r1,
367 ll_compare_func *compare, void *aux)
371 struct ll *i = ll_prev (r1);
375 if (compare (i, ll_next (i), aux) < 0)
378 for (j = ll_prev (r1); compare (i, j, aux) >= 0; j = ll_prev (j))
381 ll_reverse (ll_next (j), r1);
392 /* Arranges R0...R1 into the lexicographically next lesser
393 permutation. Returns true if successful.
394 If R0...R1 is already the lexicographically least
395 permutation of its elements (i.e. ordered from smallest to
396 greatest), arranges them into the lexicographically greatest
397 permutation (i.e. ordered from largest to smallest) and
399 COMPARE with auxiliary data AUX is used to compare nodes. */
401 ll_prev_permutation (struct ll *r0, struct ll *r1,
402 ll_compare_func *compare, void *aux)
406 struct ll *i = ll_prev (r1);
410 if (compare (i, ll_next (i), aux) > 0)
413 for (j = ll_prev (r1); compare (i, j, aux) <= 0; j = ll_prev (j))
416 ll_reverse (ll_next (j), r1);
427 /* Sorts R0...R1 into ascending order
428 according to COMPARE given auxiliary data AUX.
429 In use, keep in mind that R0 may move during the sort, so that
430 afterward R0...R1 may denote a different range.
431 (On the other hand, R1 is fixed in place.)
432 Runs in O(n lg n) time in the number of nodes in the range. */
434 ll_sort (struct ll *r0, struct ll *r1, ll_compare_func *compare, void *aux)
437 size_t output_run_cnt;
439 if (r0 == r1 || ll_next (r0) == r1)
442 pre_r0 = ll_prev (r0);
445 struct ll *a0 = ll_next (pre_r0);
446 for (output_run_cnt = 1; ; output_run_cnt++)
448 struct ll *a1 = ll_find_run (a0, r1, compare, aux);
449 struct ll *a2 = ll_find_run (a1, r1, compare, aux);
453 a0 = ll_merge (a0, a1, a1, a2, compare, aux);
456 while (output_run_cnt > 1);
459 /* Finds the extent of a run of nodes of increasing value
460 starting at R0 and extending no farther than R1.
461 Returns the first node in R0...R1 that is less than the
462 preceding node, or R1 if R0...R1 are arranged in nondecreasing
465 ll_find_run (const struct ll *r0, const struct ll *r1,
466 ll_compare_func *compare, void *aux)
474 while (r0 != r1 && compare (ll_prev (r0), r0, aux) <= 0);
477 return (struct ll *) r0;
480 /* Merges B0...B1 into A0...A1 according to COMPARE given
482 The ranges may be in the same list or different lists, but
484 Returns the end of the merged range.
485 The merge is "stable" if A0...A1 is considered to precede
486 B0...B1, regardless of their actual ordering.
487 Runs in O(n) time in the total number of nodes in the ranges. */
489 ll_merge (struct ll *a0, struct ll *a1, struct ll *b0, struct ll *b1,
490 ll_compare_func *compare, void *aux)
492 if (a0 != a1 && b0 != b1)
497 if (compare (a0, b0, aux) <= 0)
501 ll_splice (ll_next (a0), b0, ll_next (b1));
516 ll_splice (a0, b0, ll_next (b0));
523 ll_splice (a0, b0, b1);
528 /* Returns true if R0...R1 is sorted in ascending order according
529 to COMPARE given auxiliary data AUX, false otherwise. */
531 ll_is_sorted (const struct ll *r0, const struct ll *r1,
532 ll_compare_func *compare, void *aux)
534 return ll_find_run (r0, r1, compare, aux) == r1;
537 /* Removes all but the first in each group of sequential
538 duplicates in R0...R1. Duplicates are determined using
539 COMPARE given auxiliary data AUX. Removed duplicates are
540 inserted before DUPS if it is nonnull; otherwise, their
542 Only sequential duplicates are removed. ll_sort() may be used
543 to bring duplicates together, or ll_sort_unique() can do both
546 ll_unique (struct ll *r0, struct ll *r1, struct ll *dups,
547 ll_compare_func *compare, void *aux)
556 struct ll *y = ll_next (x);
563 if (compare (x, y, aux) == 0)
580 /* Sorts R0...R1 and removes duplicates.
581 Removed duplicates are inserted before DUPS if it is nonnull;
582 otherwise, their identities are lost.
583 Comparisons are made with COMPARE given auxiliary data AUX.
584 In use, keep in mind that R0 may move during the sort, so that
585 afterward R0...R1 may denote a different range.
586 (On the other hand, R1 is fixed in place.)
587 Runs in O(n lg n) time in the number of nodes in the range. */
589 ll_sort_unique (struct ll *r0, struct ll *r1, struct ll *dups,
590 ll_compare_func *compare, void *aux)
592 struct ll *pre_r0 = ll_prev (r0);
593 ll_sort (r0, r1, compare, aux);
594 ll_unique (ll_next (pre_r0), r1, dups, compare, aux);
597 /* Inserts NEW_ELEM in the proper position in R0...R1, which must
598 be sorted according to COMPARE given auxiliary data AUX.
599 If NEW_ELEM is equal to one or more existing nodes in R0...R1,
600 then it is inserted after the existing nodes it equals.
601 Runs in O(n) time in the number of nodes in the range. */
603 ll_insert_ordered (struct ll *r0, struct ll *r1, struct ll *new_elem,
604 ll_compare_func *compare, void *aux)
608 for (x = r0; x != r1; x = ll_next (x))
609 if (compare (x, new_elem, aux) > 0)
611 ll_insert (x, new_elem);
614 /* Partitions R0...R1 into those nodes for which PREDICATE given
615 auxiliary data AUX returns true, followed by those for which
616 PREDICATE returns false.
617 Returns the first node in the "false" group, or R1 if
618 PREDICATE is true for every node in R0...R1.
619 The partition is "stable" in that the nodes in each group
620 retain their original relative order.
621 Runs in O(n) time in the number of nodes in the range. */
623 ll_partition (struct ll *r0, struct ll *r1,
624 ll_predicate_func *predicate, void *aux)
632 else if (!predicate (r0, aux))
638 for (t0 = r0;; t0 = t1)
646 while (!predicate (t0, aux));
654 ll_splice (r0, t0, t1);
658 while (predicate (t1, aux));
660 ll_splice (r0, t0, t1);
664 /* Verifies that R0...R1 is parititioned into a sequence of nodes
665 for which PREDICATE given auxiliary data AUX returns true,
666 followed by those for which PREDICATE returns false.
667 Returns a null pointer if R0...R1 is not partitioned this way.
668 Otherwise, returns the first node in the "false" group, or R1
669 if PREDICATE is true for every node in R0...R1. */
671 ll_find_partition (const struct ll *r0, const struct ll *r1,
672 ll_predicate_func *predicate, void *aux)
674 const struct ll *partition, *x;
676 for (partition = r0; partition != r1; partition = ll_next (partition))
677 if (!predicate (partition, aux))
680 for (x = partition; x != r1; x = ll_next (x))
681 if (predicate (x, aux))
684 return (struct ll *) partition;