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 /* External, circular doubly linked list. */
21 /* These library routines have no external dependencies, other
22 than ll.c and the standard C library.
24 If you add routines in this file, please add a corresponding
25 test to llx-test.c. This test program should achieve 100%
26 coverage of lines and branches in this code, as reported by
33 #include <libpspp/llx.h>
38 /* Destroys LIST and frees all of its nodes using MANAGER.
39 If DESTRUCTOR is non-null, each node in the list will be
40 passed to it in list order, with AUX as auxiliary data, before
41 that node is destroyed. */
43 llx_destroy (struct llx_list *list, llx_action_func *destructor, void *aux,
44 const struct llx_manager *manager)
46 struct llx *llx, *next;
48 for (llx = llx_head (list); llx != llx_null (list); llx = next)
50 next = llx_next (llx);
51 if (destructor != NULL)
52 destructor (llx_data (llx), aux);
53 manager->release (llx, manager->aux);
57 /* Returns the number of nodes in LIST (not counting the null
58 node). Executes in O(n) time in the length of the list. */
60 llx_count (const struct llx_list *list)
62 return llx_count_range (llx_head (list), llx_null (list));
65 /* Inserts DATA at the head of LIST.
66 Returns the new node (allocated with MANAGER), or a null
67 pointer if memory allocation failed. */
69 llx_push_head (struct llx_list *list, void *data,
70 const struct llx_manager *manager)
72 return llx_insert (llx_head (list), data, manager);
75 /* Inserts DATA at the tail of LIST.
76 Returns the new node (allocated with MANAGER), or a null
77 pointer if memory allocation failed. */
79 llx_push_tail (struct llx_list *list, void *data,
80 const struct llx_manager *manager)
82 return llx_insert (llx_null (list), data, manager);
85 /* Removes the first node in LIST, which must not be empty,
86 and returns the data that the node contained.
87 Frees the node removed with MANAGER. */
89 llx_pop_head (struct llx_list *list, const struct llx_manager *manager)
91 struct llx *llx = llx_from_ll (ll_head (&list->ll_list));
92 void *data = llx_data (llx);
93 llx_remove (llx, manager);
97 /* Removes the last node in LIST, which must not be empty,
98 and returns the data that the node contained.
99 Frees the node removed with MANAGER. */
101 llx_pop_tail (struct llx_list *list, const struct llx_manager *manager)
103 struct llx *llx = llx_from_ll (ll_tail (&list->ll_list));
104 void *data = llx_data (llx);
105 llx_remove (llx, manager);
109 /* Inserts DATA before BEFORE.
110 Returns the new node (allocated with MANAGER), or a null
111 pointer if memory allocation failed. */
113 llx_insert (struct llx *before, void *data, const struct llx_manager *manager)
115 struct llx *llx = manager->allocate (manager->aux);
119 ll_insert (&before->ll, &llx->ll);
124 /* Removes R0...R1 from their current list
125 and inserts them just before BEFORE. */
127 llx_splice (struct llx *before, struct llx *r0, struct llx *r1)
129 ll_splice (&before->ll, &r0->ll, &r1->ll);
132 /* Exchanges the positions of A and B,
133 which may be in the same list or different lists. */
135 llx_swap (struct llx *a, struct llx *b)
137 ll_swap (&a->ll, &b->ll);
140 /* Exchanges the positions of A0...A1 and B0...B1,
141 which may be in the same list or different lists but must not
144 llx_swap_range (struct llx *a0, struct llx *a1,
145 struct llx *b0, struct llx *b1)
147 ll_swap_range (&a0->ll, &a1->ll, &b0->ll, &b1->ll);
150 /* Removes LLX from its list
151 and returns the node that formerly followed it.
152 Frees the node removed with MANAGER. */
154 llx_remove (struct llx *llx, const struct llx_manager *manager)
156 struct llx *next = llx_next (llx);
157 ll_remove (&llx->ll);
158 manager->release (llx, manager->aux);
162 /* Removes R0...R1 from their list.
163 Frees the removed nodes with MANAGER. */
165 llx_remove_range (struct llx *r0, struct llx *r1,
166 const struct llx_manager *manager)
170 for (llx = r0; llx != r1; )
171 llx = llx_remove (llx, manager);
174 /* Removes from R0...R1 all the nodes that equal TARGET
175 according to COMPARE given auxiliary data AUX.
176 Frees the removed nodes with MANAGER.
177 Returns the number of nodes removed. */
179 llx_remove_equal (struct llx *r0, struct llx *r1, const void *target,
180 llx_compare_func *compare, void *aux,
181 const struct llx_manager *manager)
187 for (x = r0; x != r1; )
188 if (compare (llx_data (x), target, aux) == 0)
190 x = llx_remove (x, manager);
199 /* Removes from R0...R1 all the nodes for which PREDICATE returns
200 true given auxiliary data AUX.
201 Frees the removed nodes with MANAGER.
202 Returns the number of nodes removed. */
204 llx_remove_if (struct llx *r0, struct llx *r1,
205 llx_predicate_func *predicate, void *aux,
206 const struct llx_manager *manager)
212 for (x = r0; x != r1; )
213 if (predicate (llx_data (x), aux))
215 x = llx_remove (x, manager);
224 /* Returns the first node in R0...R1 that equals TARGET
225 according to COMPARE given auxiliary data AUX.
226 Returns R1 if no node in R0...R1 equals TARGET. */
228 llx_find_equal (const struct llx *r0, const struct llx *r1,
230 llx_compare_func *compare, void *aux)
234 for (x = r0; x != r1; x = llx_next (x))
235 if (compare (llx_data (x), target, aux) == 0)
237 return (struct llx *) x;
240 /* Returns the first node in R0...R1 for which PREDICATE returns
241 true given auxiliary data AUX.
242 Returns R1 if PREDICATE does not return true for any node in
245 llx_find_if (const struct llx *r0, const struct llx *r1,
246 llx_predicate_func *predicate, void *aux)
250 for (x = r0; x != r1; x = llx_next (x))
251 if (predicate (llx_data (x), aux))
253 return (struct llx *) x;
256 /* Compares each pair of adjacent nodes in R0...R1
257 using COMPARE with auxiliary data AUX
258 and returns the first node of the first pair that compares
260 Returns R1 if no pair compares equal. */
262 llx_find_adjacent_equal (const struct llx *r0, const struct llx *r1,
263 llx_compare_func *compare, void *aux)
267 const struct llx *x, *y;
269 for (x = r0, y = llx_next (x); y != r1; x = y, y = llx_next (y))
270 if (compare (llx_data (x), llx_data (y), aux) == 0)
271 return (struct llx *) x;
274 return (struct llx *) r1;
277 /* Returns the number of nodes in R0...R1.
278 Executes in O(n) time in the return value. */
280 llx_count_range (const struct llx *r0, const struct llx *r1)
282 return ll_count_range (&r0->ll, &r1->ll);
285 /* Counts and returns the number of nodes in R0...R1 that equal
286 TARGET according to COMPARE given auxiliary data AUX. */
288 llx_count_equal (const struct llx *r0, const struct llx *r1,
290 llx_compare_func *compare, void *aux)
296 for (x = r0; x != r1; x = llx_next (x))
297 if (compare (llx_data (x), target, aux) == 0)
302 /* Counts and returns the number of nodes in R0...R1 for which
303 PREDICATE returns true given auxiliary data AUX. */
305 llx_count_if (const struct llx *r0, const struct llx *r1,
306 llx_predicate_func *predicate, void *aux)
312 for (x = r0; x != r1; x = llx_next (x))
313 if (predicate (llx_data (x), aux))
318 /* Returns the greatest node in R0...R1 according to COMPARE
319 given auxiliary data AUX.
320 Returns the first of multiple, equal maxima. */
322 llx_max (const struct llx *r0, const struct llx *r1,
323 llx_compare_func *compare, void *aux)
325 const struct llx *max = r0;
330 for (x = llx_next (r0); x != r1; x = llx_next (x))
331 if (compare (llx_data (x), llx_data (max), aux) > 0)
334 return (struct llx *) max;
337 /* Returns the least node in R0...R1 according to COMPARE given
339 Returns the first of multiple, equal minima. */
341 llx_min (const struct llx *r0, const struct llx *r1,
342 llx_compare_func *compare, void *aux)
344 const struct llx *min = r0;
349 for (x = llx_next (r0); x != r1; x = llx_next (x))
350 if (compare (llx_data (x), llx_data (min), aux) < 0)
353 return (struct llx *) min;
356 /* Lexicographically compares A0...A1 to B0...B1.
357 Returns negative if A0...A1 < B0...B1,
358 zero if A0...A1 == B0...B1, and
359 positive if A0...A1 > B0...B1
360 according to COMPARE given auxiliary data AUX. */
362 llx_lexicographical_compare_3way (const struct llx *a0, const struct llx *a1,
363 const struct llx *b0, const struct llx *b1,
364 llx_compare_func *compare, void *aux)
373 int cmp = compare (llx_data (a0), llx_data (b0), aux);
382 /* Calls ACTION with auxiliary data AUX
383 for every node in R0...R1 in order. */
385 llx_apply (struct llx *r0, struct llx *r1,
386 llx_action_func *action, void *aux)
390 for (llx = r0; llx != r1; llx = llx_next (llx))
391 action (llx_data (llx), aux);
394 /* Reverses the order of nodes R0...R1. */
396 llx_reverse (struct llx *r0, struct llx *r1)
398 ll_reverse (&r0->ll, &r1->ll);
401 /* Arranges R0...R1 into the lexicographically next greater
402 permutation. Returns true if successful.
403 If R0...R1 is already the lexicographically greatest
404 permutation of its elements (i.e. ordered from greatest to
405 smallest), arranges them into the lexicographically least
406 permutation (i.e. ordered from smallest to largest) and
408 COMPARE with auxiliary data AUX is used to compare nodes. */
410 llx_next_permutation (struct llx *r0, struct llx *r1,
411 llx_compare_func *compare, void *aux)
415 struct llx *i = llx_prev (r1);
419 if (compare (llx_data (i), llx_data (llx_next (i)), aux) < 0)
422 for (j = llx_prev (r1);
423 compare (llx_data (i), llx_data (j), aux) >= 0;
427 llx_reverse (llx_next (j), r1);
432 llx_reverse (r0, r1);
438 /* Arranges R0...R1 into the lexicographically next lesser
439 permutation. Returns true if successful.
440 If R0...R1 is already the lexicographically least
441 permutation of its elements (i.e. ordered from smallest to
442 greatest), arranges them into the lexicographically greatest
443 permutation (i.e. ordered from largest to smallest) and
445 COMPARE with auxiliary data AUX is used to compare nodes. */
447 llx_prev_permutation (struct llx *r0, struct llx *r1,
448 llx_compare_func *compare, void *aux)
452 struct llx *i = llx_prev (r1);
456 if (compare (llx_data (i), llx_data (llx_next (i)), aux) > 0)
459 for (j = llx_prev (r1);
460 compare (llx_data (i), llx_data (j), aux) <= 0;
464 llx_reverse (llx_next (j), r1);
469 llx_reverse (r0, r1);
475 /* Sorts R0...R1 into ascending order
476 according to COMPARE given auxiliary data AUX.
477 In use, keep in mind that R0 may move during the sort, so that
478 afterward R0...R1 may denote a different range.
479 (On the other hand, R1 is fixed in place.)
480 Runs in O(n lg n) time in the number of nodes in the range. */
482 llx_sort (struct llx *r0, struct llx *r1, llx_compare_func *compare, void *aux)
485 size_t output_run_cnt;
487 if (r0 == r1 || llx_next (r0) == r1)
490 pre_r0 = llx_prev (r0);
493 struct llx *a0 = llx_next (pre_r0);
494 for (output_run_cnt = 1; ; output_run_cnt++)
496 struct llx *a1 = llx_find_run (a0, r1, compare, aux);
497 struct llx *a2 = llx_find_run (a1, r1, compare, aux);
501 a0 = llx_merge (a0, a1, a1, a2, compare, aux);
504 while (output_run_cnt > 1);
507 /* Finds the extent of a run of nodes of increasing value
508 starting at R0 and extending no farther than R1.
509 Returns the first node in R0...R1 that is less than the
510 preceding node, or R1 if R0...R1 are arranged in nondecreasing
513 llx_find_run (const struct llx *r0, const struct llx *r1,
514 llx_compare_func *compare, void *aux)
522 while (r0 != r1 && compare (llx_data (llx_prev (r0)),
523 llx_data (r0), aux) <= 0);
526 return (struct llx *) r0;
529 /* Merges B0...B1 into A0...A1 according to COMPARE given
531 The ranges may be in the same list or different lists, but
533 The merge is "stable" if A0...A1 is considered to precede
534 B0...B1, regardless of their actual ordering.
535 Runs in O(n) time in the total number of nodes in the ranges. */
537 llx_merge (struct llx *a0, struct llx *a1, struct llx *b0, struct llx *b1,
538 llx_compare_func *compare, void *aux)
540 if (a0 != a1 && b0 != b1)
545 if (compare (llx_data (a0), llx_data (b0), aux) <= 0)
549 llx_splice (llx_next (a0), b0, llx_next (b1));
550 return llx_next (b1);
560 llx_splice (a0, x, b0);
564 llx_splice (a0, b0, llx_next (b0));
565 return llx_next (a1);
571 llx_splice (a0, b0, b1);
576 /* Returns true if R0...R1 is sorted in ascending order according
577 to COMPARE given auxiliary data AUX,
580 llx_is_sorted (const struct llx *r0, const struct llx *r1,
581 llx_compare_func *compare, void *aux)
583 return llx_find_run (r0, r1, compare, aux) == r1;
586 /* Removes all but the first in each group of sequential
587 duplicates in R0...R1. Duplicates are determined using
588 COMPARE given auxiliary data AUX. Removed duplicates are
589 inserted before DUPS if it is nonnull; otherwise, the removed
590 duplicates are freed with MANAGER.
591 Only sequential duplicates are removed. llx_sort() may be used
592 to bring duplicates together, or llx_sort_unique() can do both
595 llx_unique (struct llx *r0, struct llx *r1, struct llx *dups,
596 llx_compare_func *compare, void *aux,
597 const struct llx_manager *manager)
606 struct llx *y = llx_next (x);
613 if (compare (llx_data (x), llx_data (y), aux) == 0)
616 llx_splice (dups, y, llx_next (y));
618 llx_remove (y, manager);
631 /* Sorts R0...R1 and removes duplicates.
632 Removed duplicates are inserted before DUPS if it is nonnull;
633 otherwise, the removed duplicates are freed with MANAGER.
634 Comparisons are made with COMPARE given auxiliary data AUX.
635 In use, keep in mind that R0 may move during the sort, so that
636 afterward R0...R1 may denote a different range.
637 (On the other hand, R1 is fixed in place.)
638 Runs in O(n lg n) time in the number of nodes in the range. */
640 llx_sort_unique (struct llx *r0, struct llx *r1, struct llx *dups,
641 llx_compare_func *compare, void *aux,
642 const struct llx_manager *manager)
644 struct llx *pre_r0 = llx_prev (r0);
645 llx_sort (r0, r1, compare, aux);
646 llx_unique (llx_next (pre_r0), r1, dups, compare, aux, manager);
649 /* Inserts DATA in the proper position in R0...R1, which must
650 be sorted according to COMPARE given auxiliary data AUX.
651 If DATA is equal to one or more existing nodes in R0...R1,
652 then it is inserted after the existing nodes it equals.
653 Returns the new node (allocated with MANAGER), or a null
654 pointer if memory allocation failed.
655 Runs in O(n) time in the number of nodes in the range. */
657 llx_insert_ordered (struct llx *r0, struct llx *r1, void *data,
658 llx_compare_func *compare, void *aux,
659 const struct llx_manager *manager)
663 for (x = r0; x != r1; x = llx_next (x))
664 if (compare (llx_data (x), data, aux) > 0)
666 return llx_insert (x, data, manager);
669 /* Partitions R0...R1 into those nodes for which PREDICATE given
670 auxiliary data AUX returns true, followed by those for which
671 PREDICATE returns false.
672 Returns the first node in the "false" group, or R1 if
673 PREDICATE is true for every node in R0...R1.
674 The partition is "stable" in that the nodes in each group
675 retain their original relative order.
676 Runs in O(n) time in the number of nodes in the range. */
678 llx_partition (struct llx *r0, struct llx *r1,
679 llx_predicate_func *predicate, void *aux)
687 else if (!predicate (llx_data (r0), aux))
693 for (t0 = r0;; t0 = t1)
701 while (!predicate (llx_data (t0), aux));
709 llx_splice (r0, t0, t1);
713 while (predicate (llx_data (t1), aux));
715 llx_splice (r0, t0, t1);
719 /* Verifies that R0...R1 is parititioned into a sequence of nodes
720 for which PREDICATE given auxiliary data AUX returns true,
721 followed by those for which PREDICATE returns false.
722 Returns a null pointer if R0...R1 is not partitioned this way.
723 Otherwise, returns the first node in the "false" group, or R1
724 if PREDICATE is true for every node in R0...R1. */
726 llx_find_partition (const struct llx *r0, const struct llx *r1,
727 llx_predicate_func *predicate, void *aux)
729 const struct llx *partition, *x;
731 for (partition = r0; partition != r1; partition = llx_next (partition))
732 if (!predicate (llx_data (partition), aux))
735 for (x = partition; x != r1; x = llx_next (x))
736 if (predicate (llx_data (x), aux))
739 return (struct llx *) partition;
742 /* Allocates and returns a node using malloc. */
744 malloc_allocate_node (void *aux UNUSED)
746 return malloc (sizeof (struct llx));
749 /* Releases node LLX with free. */
751 malloc_release_node (struct llx *llx, void *aux UNUSED)
756 /* Manager that uses the standard malloc and free routines. */
757 const struct llx_manager llx_malloc_mgr =
759 malloc_allocate_node,