1 /* PSPP - computes sample statistics.
2 Copyright (C) 1997-9, 2000 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 /* Copyright (C) 2001 Free Software Foundation, Inc.
21 This file is part of the GNU ISO C++ Library. This library is free
22 software; you can redistribute it and/or modify it under the
23 terms of the GNU General Public License as published by the
24 Free Software Foundation; either version 2, or (at your option)
27 This library is distributed in the hope that it will be useful,
28 but WITHOUT ANY WARRANTY; without even the implied warranty of
29 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
30 GNU General Public License for more details.
32 You should have received a copy of the GNU General Public License along
33 with this library; see the file COPYING. If not, write to the Free
34 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
37 As a special exception, you may use this file as part of a free software
38 library without restriction. Specifically, if other files instantiate
39 templates or use macros or inline functions from this file, or you compile
40 this file and link it with other files to produce an executable, this
41 file does not by itself cause the resulting executable to be covered by
42 the GNU General Public License. This exception does not however
43 invalidate any other reasons why the executable file might be covered by
44 the GNU General Public License. */
49 * Hewlett-Packard Company
51 * Permission to use, copy, modify, distribute and sell this software
52 * and its documentation for any purpose is hereby granted without fee,
53 * provided that the above copyright notice appear in all copies and
54 * that both that copyright notice and this permission notice appear
55 * in supporting documentation. Hewlett-Packard Company makes no
56 * representations about the suitability of this software for any
57 * purpose. It is provided "as is" without express or implied warranty.
61 * Silicon Graphics Computer Systems, Inc.
63 * Permission to use, copy, modify, distribute and sell this software
64 * and its documentation for any purpose is hereby granted without fee,
65 * provided that the above copyright notice appear in all copies and
66 * that both that copyright notice and this permission notice appear
67 * in supporting documentation. Silicon Graphics makes no
68 * representations about the suitability of this software for any
69 * purpose. It is provided "as is" without express or implied warranty.
72 /* Copyright (C) 1991, 1992, 1996, 1997, 1999 Free Software Foundation, Inc.
73 This file is part of the GNU C Library.
74 Written by Douglas C. Schmidt (schmidt@ics.uci.edu).
76 The GNU C Library is free software; you can redistribute it and/or
77 modify it under the terms of the GNU Lesser General Public
78 License as published by the Free Software Foundation; either
79 version 2.1 of the License, or (at your option) any later version.
81 The GNU C Library is distributed in the hope that it will be useful,
82 but WITHOUT ANY WARRANTY; without even the implied warranty of
83 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
84 Lesser General Public License for more details.
86 You should have received a copy of the GNU Lesser General Public
87 License along with the GNU C Library; if not, write to the Free
88 Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
97 #include <libpspp/assertion.h>
103 /* Finds an element in ARRAY, which contains COUNT elements of
104 SIZE bytes each, using COMPARE for comparisons. Returns the
105 first element in ARRAY that matches TARGET, or a null pointer
106 on failure. AUX is passed to each comparison as auxiliary
109 find (const void *array, size_t count, size_t size,
111 algo_compare_func *compare, const void *aux)
113 const char *element = array;
117 if (compare (target, element, aux) == 0)
118 return (void *) element;
126 /* Counts and return the number of elements in ARRAY, which
127 contains COUNT elements of SIZE bytes each, which are equal to
128 ELEMENT as compared with COMPARE. AUX is passed as auxiliary
131 count_equal (const void *array, size_t count, size_t size,
133 algo_compare_func *compare, const void *aux)
135 const char *first = array;
136 size_t equal_cnt = 0;
140 if (compare (element, first, aux) == 0)
149 /* Counts and return the number of elements in ARRAY, which
150 contains COUNT elements of SIZE bytes each, for which
151 PREDICATE returns true. AUX is passed as auxiliary data to
154 count_if (const void *array, size_t count, size_t size,
155 algo_predicate_func *predicate, const void *aux)
157 const char *first = array;
162 if (predicate (first, aux) != 0)
171 /* Byte-wise swap two items of size SIZE. */
172 #define SWAP(a, b, size) \
175 register size_t __size = (size); \
176 register char *__a = (a), *__b = (b); \
182 } while (--__size > 0); \
185 /* Makes the elements in ARRAY unique, by moving up duplicates,
186 and returns the new number of elements in the array. Sorted
187 arrays only. Arguments same as for sort() above. */
189 unique (void *array, size_t count, size_t size,
190 algo_compare_func *compare, const void *aux)
193 char *last = first + size * count;
194 char *result = array;
201 assert (adjacent_find_equal (array, count,
202 size, compare, aux) == NULL);
206 if (compare (result, first, aux))
210 memcpy (result, first, size);
217 /* Helper function that calls sort(), then unique(). */
219 sort_unique (void *array, size_t count, size_t size,
220 algo_compare_func *compare, const void *aux)
222 sort (array, count, size, compare, aux);
223 return unique (array, count, size, compare, aux);
226 /* Reorders ARRAY, which contains COUNT elements of SIZE bytes
227 each, so that the elements for which PREDICATE returns true
228 precede those for which PREDICATE returns zero. AUX is
229 passed to each predicate as auxiliary data. Returns the
230 number of elements for which PREDICATE returns true. Not
233 partition (void *array, size_t count, size_t size,
234 algo_predicate_func *predicate, const void *aux)
236 size_t true_cnt = count;
238 char *last = first + true_cnt * size;
242 /* Move FIRST forward to point to first element that fails
248 else if (!predicate (first, aux))
255 /* Move LAST backward to point to last element that passes
263 else if (predicate (last, aux))
269 /* By swapping FIRST and LAST we extend the starting and
270 ending sequences that pass and fail, respectively,
272 SWAP (first, last, size);
277 assert (is_partitioned (array, count, size, true_cnt, predicate, aux));
281 /* Checks whether ARRAY, which contains COUNT elements of SIZE
282 bytes each, is partitioned such that PREDICATE returns true
283 for the first TRUE_CNT elements and zero for the remaining
284 elements. AUX is passed as auxiliary data to PREDICATE. */
286 is_partitioned (const void *array, size_t count, size_t size,
288 algo_predicate_func *predicate, const void *aux)
290 const char *first = array;
293 assert (true_cnt <= count);
294 for (idx = 0; idx < true_cnt; idx++)
295 if (predicate (first + idx * size, aux) == 0)
297 for (idx = true_cnt; idx < count; idx++)
298 if (predicate (first + idx * size, aux) != 0)
303 /* Copies the COUNT elements of SIZE bytes each from ARRAY to
304 RESULT, except that elements for which PREDICATE is false are
305 not copied. Returns the number of elements copied. AUX is
306 passed to PREDICATE as auxiliary data. */
308 copy_if (const void *array, size_t count, size_t size,
310 algo_predicate_func *predicate, const void *aux)
312 const char *input = array;
313 const char *last = input + size * count;
314 char *output = result;
315 size_t nonzero_cnt = 0;
319 if (predicate (input, aux))
321 memcpy (output, input, size);
329 assert (nonzero_cnt == count_if (array, count, size, predicate, aux));
330 assert (nonzero_cnt == count_if (result, nonzero_cnt, size, predicate, aux));
335 /* Removes N elements starting at IDX from ARRAY, which consists
336 of COUNT elements of SIZE bytes each, by shifting the elements
337 following them, if any, into its position. */
339 remove_range (void *array_, size_t count, size_t size,
340 size_t idx, size_t n)
342 char *array = array_;
344 assert (array != NULL);
345 assert (idx <= count);
346 assert (idx + n <= count);
349 memmove (array + idx * size, array + (idx + n) * size,
350 size * (count - idx - n));
353 /* Removes element IDX from ARRAY, which consists of COUNT
354 elements of SIZE bytes each, by shifting the elements
355 following it, if any, into its position. */
357 remove_element (void *array, size_t count, size_t size,
360 remove_range (array, count, size, idx, 1);
363 /* Makes room for N elements starting at IDX in ARRAY, which
364 initially consists of COUNT elements of SIZE bytes each, by
365 shifting elements IDX...COUNT (exclusive) to the right by N
368 insert_range (void *array_, size_t count, size_t size,
369 size_t idx, size_t n)
371 char *array = array_;
373 assert (idx <= count);
374 memmove (array + (idx + n) * size, array + idx * size, (count - idx) * size);
377 /* Makes room for a new element at IDX in ARRAY, which initially
378 consists of COUNT elements of SIZE bytes each, by shifting
379 elements IDX...COUNT (exclusive) to the right by one
382 insert_element (void *array, size_t count, size_t size,
385 insert_range (array, count, size, idx, 1);
388 /* Moves an element in ARRAY, which consists of COUNT elements of
389 SIZE bytes each, from OLD_IDX to NEW_IDX, shifting around
390 other elements as needed. Runs in O(abs(OLD_IDX - NEW_IDX))
393 move_element (void *array_, size_t count, size_t size,
394 size_t old_idx, size_t new_idx)
396 assert (array_ != NULL || count == 0);
397 assert (old_idx < count);
398 assert (new_idx < count);
400 if (old_idx != new_idx)
402 char *array = array_;
403 char *element = xmalloc (size);
404 char *new = array + new_idx * size;
405 char *old = array + old_idx * size;
407 memcpy (element, old, size);
409 memmove (new + size, new, (old_idx - new_idx) * size);
411 memmove (old, old + size, (new_idx - old_idx) * size);
412 memcpy (new, element, size);
418 /* Moves N elements in ARRAY starting at OLD_IDX, which consists
419 of COUNT elements of SIZE bytes each, so that they now start
420 at NEW_IDX, shifting around other elements as needed. */
422 move_range (void *array_, size_t count, size_t size,
423 size_t old_idx, size_t new_idx, size_t n)
425 assert (array_ != NULL || count == 0);
427 assert (old_idx + n <= count);
428 assert (new_idx + n <= count);
430 if (old_idx != new_idx && n > 0)
432 char *array = array_;
433 char *range = xmalloc (size * n);
434 char *new = array + new_idx * size;
435 char *old = array + old_idx * size;
437 memcpy (range, old, size * n);
439 memmove (new + size * n, new, (old_idx - new_idx) * size);
441 memmove (old, old + size * n, (new_idx - old_idx) * size);
442 memcpy (new, range, size * n);
448 /* A predicate and its auxiliary data. */
451 algo_predicate_func *predicate;
456 not (const void *data, const void *pred_aux_)
458 const struct pred_aux *pred_aux = pred_aux_;
460 return !pred_aux->predicate (data, pred_aux->aux);
463 /* Removes elements equal to ELEMENT from ARRAY, which consists
464 of COUNT elements of SIZE bytes each. Returns the number of
465 remaining elements. AUX is passed to COMPARE as auxiliary
468 remove_equal (void *array, size_t count, size_t size,
470 algo_compare_func *compare, const void *aux)
473 char *last = first + count * size;
480 if (compare (first, element, aux) == 0)
494 if (compare (first, element, aux) == 0)
500 memcpy (result, first, size);
505 assert (count_equal (array, count, size, element, compare, aux) == 0);
509 /* Copies the COUNT elements of SIZE bytes each from ARRAY to
510 RESULT, except that elements for which PREDICATE is true are
511 not copied. Returns the number of elements copied. AUX is
512 passed to PREDICATE as auxiliary data. */
514 remove_copy_if (const void *array, size_t count, size_t size,
516 algo_predicate_func *predicate, const void *aux)
518 struct pred_aux pred_aux;
519 pred_aux.predicate = predicate;
521 return copy_if (array, count, size, result, not, &pred_aux);
524 /* Searches ARRAY, which contains COUNT of SIZE bytes each, using
525 a binary search. Returns any element that equals VALUE, if
526 one exists, or a null pointer otherwise. ARRAY must ordered
527 according to COMPARE. AUX is passed to COMPARE as auxiliary
530 binary_search (const void *array, size_t count, size_t size,
532 algo_compare_func *compare, const void *aux)
534 assert (array != NULL);
535 assert (count <= INT_MAX);
536 assert (compare != NULL);
540 const char *first = array;
542 int high = count - 1;
546 int middle = (low + high) / 2;
547 const char *element = first + middle * size;
548 int cmp = compare (value, element, aux);
555 return (void *) element;
559 expensive_assert (find (array, count, size, value, compare, aux) == NULL);
563 /* Lexicographically compares ARRAY1, which contains COUNT1
564 elements of SIZE bytes each, to ARRAY2, which contains COUNT2
565 elements of SIZE bytes, according to COMPARE. Returns a
566 strcmp()-type result. AUX is passed to COMPARE as auxiliary
569 lexicographical_compare_3way (const void *array1, size_t count1,
570 const void *array2, size_t count2,
572 algo_compare_func *compare, const void *aux)
574 const char *first1 = array1;
575 const char *first2 = array2;
576 size_t min_count = count1 < count2 ? count1 : count2;
578 while (min_count > 0)
580 int cmp = compare (first1, first2, aux);
589 return count1 < count2 ? -1 : count1 > count2;
592 /* If you consider tuning this algorithm, you should consult first:
593 Engineering a sort function; Jon Bentley and M. Douglas McIlroy;
594 Software - Practice and Experience; Vol. 23 (11), 1249-1265, 1993. */
600 /* Discontinue quicksort algorithm when partition gets below this size.
601 This particular magic number was chosen to work best on a Sun 4/260. */
604 /* Stack node declarations used to store unfulfilled partition obligations. */
611 /* The next 4 #defines implement a very fast in-line stack abstraction. */
612 /* The stack needs log (total_elements) entries (we could even subtract
613 log(MAX_THRESH)). Since total_elements has type size_t, we get as
614 upper bound for log (total_elements):
615 bits per byte (CHAR_BIT) * sizeof(size_t). */
616 #define STACK_SIZE (CHAR_BIT * sizeof(size_t))
617 #define PUSH(low, high) ((void) ((top->lo = (low)), (top->hi = (high)), ++top))
618 #define POP(low, high) ((void) (--top, (low = top->lo), (high = top->hi)))
619 #define STACK_NOT_EMPTY (stack < top)
622 /* Order size using quicksort. This implementation incorporates
623 four optimizations discussed in Sedgewick:
625 1. Non-recursive, using an explicit stack of pointer that store the
626 next array partition to sort. To save time, this maximum amount
627 of space required to store an array of SIZE_MAX is allocated on the
628 stack. Assuming a 32-bit (64 bit) integer for size_t, this needs
629 only 32 * sizeof(stack_node) == 256 bytes (for 64 bit: 1024 bytes).
630 Pretty cheap, actually.
632 2. Chose the pivot element using a median-of-three decision tree.
633 This reduces the probability of selecting a bad pivot value and
634 eliminates certain extraneous comparisons.
636 3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving
637 insertion sort to order the MAX_THRESH items within each partition.
638 This is a big win, since insertion sort is faster for small, mostly
639 sorted array segments.
641 4. The larger of the two sub-partitions is always pushed onto the
642 stack first, with the algorithm then concentrating on the
643 smaller partition. This *guarantees* no more than log (total_elems)
644 stack size is needed (actually O(1) in this case)! */
647 sort (void *array, size_t count, size_t size,
648 algo_compare_func *compare, const void *aux)
650 char *const first = array;
651 const size_t max_thresh = MAX_THRESH * size;
654 /* Avoid lossage with unsigned arithmetic below. */
657 if (count > MAX_THRESH)
660 char *hi = &lo[size * (count - 1)];
661 stack_node stack[STACK_SIZE];
662 stack_node *top = stack + 1;
664 while (STACK_NOT_EMPTY)
669 /* Select median value from among LO, MID, and HI. Rearrange
670 LO and HI so the three values are sorted. This lowers the
671 probability of picking a pathological pivot value and
672 skips a comparison for both the LEFT_PTR and RIGHT_PTR in
675 char *mid = lo + size * ((hi - lo) / size >> 1);
677 if (compare (mid, lo, aux) < 0)
678 SWAP (mid, lo, size);
679 if (compare (hi, mid, aux) < 0)
680 SWAP (mid, hi, size);
683 if (compare (mid, lo, aux) < 0)
684 SWAP (mid, lo, size);
687 left_ptr = lo + size;
688 right_ptr = hi - size;
690 /* Here's the famous ``collapse the walls'' section of quicksort.
691 Gotta like those tight inner loops! They are the main reason
692 that this algorithm runs much faster than others. */
695 while (compare (left_ptr, mid, aux) < 0)
698 while (compare (mid, right_ptr, aux) < 0)
701 if (left_ptr < right_ptr)
703 SWAP (left_ptr, right_ptr, size);
706 else if (mid == right_ptr)
711 else if (left_ptr == right_ptr)
718 while (left_ptr <= right_ptr);
720 /* Set up pointers for next iteration. First determine whether
721 left and right partitions are below the threshold size. If so,
722 ignore one or both. Otherwise, push the larger partition's
723 bounds on the stack and continue sorting the smaller one. */
725 if ((size_t) (right_ptr - lo) <= max_thresh)
727 if ((size_t) (hi - left_ptr) <= max_thresh)
728 /* Ignore both small partitions. */
731 /* Ignore small left partition. */
734 else if ((size_t) (hi - left_ptr) <= max_thresh)
735 /* Ignore small right partition. */
737 else if ((right_ptr - lo) > (hi - left_ptr))
739 /* Push larger left partition indices. */
740 PUSH (lo, right_ptr);
745 /* Push larger right partition indices. */
752 /* Once the FIRST array is partially sorted by quicksort the rest
753 is completely sorted using insertion sort, since this is efficient
754 for partitions below MAX_THRESH size. FIRST points to the beginning
755 of the array to sort, and END_PTR points at the very last element in
756 the array (*not* one beyond it!). */
759 char *const end_ptr = &first[size * (count - 1)];
760 char *tmp_ptr = first;
761 char *thresh = MIN (end_ptr, first + max_thresh);
762 register char *run_ptr;
764 /* Find smallest element in first threshold and place it at the
765 array's beginning. This is the smallest array element,
766 and the operation speeds up insertion sort's inner loop. */
768 for (run_ptr = tmp_ptr + size; run_ptr <= thresh; run_ptr += size)
769 if (compare (run_ptr, tmp_ptr, aux) < 0)
772 if (tmp_ptr != first)
773 SWAP (tmp_ptr, first, size);
775 /* Insertion sort, running from left-hand-side up to right-hand-side. */
777 run_ptr = first + size;
778 while ((run_ptr += size) <= end_ptr)
780 tmp_ptr = run_ptr - size;
781 while (compare (run_ptr, tmp_ptr, aux) < 0)
785 if (tmp_ptr != run_ptr)
789 trav = run_ptr + size;
790 while (--trav >= run_ptr)
795 for (hi = lo = trav; (lo -= size) >= tmp_ptr; hi = lo)
803 assert (is_sorted (array, count, size, compare, aux));
806 /* Tests whether ARRAY, which contains COUNT elements of SIZE
807 bytes each, is sorted in order according to COMPARE. AUX is
808 passed to COMPARE as auxiliary data. */
810 is_sorted (const void *array, size_t count, size_t size,
811 algo_compare_func *compare, const void *aux)
813 const char *first = array;
816 for (idx = 0; idx + 1 < count; idx++)
817 if (compare (first + idx * size, first + (idx + 1) * size, aux) > 0)
823 /* Computes the generalized set difference, ARRAY1 minus ARRAY2,
824 into RESULT, and returns the number of elements written to
825 RESULT. If a value appears M times in ARRAY1 and N times in
826 ARRAY2, then it will appear max(M - N, 0) in RESULT. ARRAY1
827 and ARRAY2 must be sorted, and RESULT is sorted and stable.
828 ARRAY1 consists of COUNT1 elements, ARRAY2 of COUNT2 elements,
829 each SIZE bytes. AUX is passed to COMPARE as auxiliary
831 size_t set_difference (const void *array1, size_t count1,
832 const void *array2, size_t count2,
835 algo_compare_func *compare, const void *aux)
837 const char *first1 = array1;
838 const char *last1 = first1 + count1 * size;
839 const char *first2 = array2;
840 const char *last2 = first2 + count2 * size;
841 char *result = result_;
842 size_t result_count = 0;
844 while (first1 != last1 && first2 != last2)
846 int cmp = compare (first1, first2, aux);
849 memcpy (result, first1, size);
863 while (first1 != last1)
865 memcpy (result, first1, size);
874 /* Finds the first pair of adjacent equal elements in ARRAY,
875 which has COUNT elements of SIZE bytes. Returns the first
876 element in ARRAY such that COMPARE returns zero when it and
877 its successor element are compared, or a null pointer if no
878 such element exists. AUX is passed to COMPARE as auxiliary
881 adjacent_find_equal (const void *array, size_t count, size_t size,
882 algo_compare_func *compare, const void *aux)
884 const char *first = array;
885 const char *last = first + count * size;
887 while (first < last && first + size < last)
889 if (compare (first, first + size, aux) == 0)
890 return (void *) first;
897 /* ARRAY contains COUNT elements of SIZE bytes each. Initially
898 the first COUNT - 1 elements of these form a heap, followed by
899 a single element not part of the heap. This function adds the
900 final element, forming a heap of COUNT elements in ARRAY.
901 Uses COMPARE to compare elements, passing AUX as auxiliary
904 push_heap (void *array, size_t count, size_t size,
905 algo_compare_func *compare, const void *aux)
910 expensive_assert (count < 1 || is_heap (array, count - 1,
911 size, compare, aux));
912 for (i = count; i > 1; i /= 2)
914 char *parent = first + (i / 2 - 1) * size;
915 char *element = first + (i - 1) * size;
916 if (compare (parent, element, aux) < 0)
917 SWAP (parent, element, size);
921 expensive_assert (is_heap (array, count, size, compare, aux));
924 /* ARRAY contains COUNT elements of SIZE bytes each. Initially
925 the children of ARRAY[idx - 1] are heaps, but ARRAY[idx - 1]
926 may be smaller than its children. This function fixes that,
927 so that ARRAY[idx - 1] itself is a heap. Uses COMPARE to
928 compare elements, passing AUX as auxiliary data. */
930 heapify (void *array, size_t count, size_t size,
932 algo_compare_func *compare, const void *aux)
938 size_t left = 2 * idx;
939 size_t right = left + 1;
940 size_t largest = idx;
943 && compare (first + size * (left - 1),
944 first + size * (idx - 1), aux) > 0)
948 && compare (first + size * (right - 1),
949 first + size * (largest - 1), aux) > 0)
955 SWAP (first + size * (idx - 1), first + size * (largest - 1), size);
960 /* ARRAY contains COUNT elements of SIZE bytes each. Initially
961 all COUNT elements form a heap. This function moves the
962 largest element in the heap to the final position in ARRAY and
963 reforms a heap of the remaining COUNT - 1 elements at the
964 beginning of ARRAY. Uses COMPARE to compare elements, passing
965 AUX as auxiliary data. */
967 pop_heap (void *array, size_t count, size_t size,
968 algo_compare_func *compare, const void *aux)
972 expensive_assert (is_heap (array, count, size, compare, aux));
973 SWAP (first, first + (count - 1) * size, size);
974 heapify (first, count - 1, size, 1, compare, aux);
975 expensive_assert (count < 1 || is_heap (array, count - 1,
976 size, compare, aux));
979 /* Turns ARRAY, which contains COUNT elements of SIZE bytes, into
980 a heap. Uses COMPARE to compare elements, passing AUX as
983 make_heap (void *array, size_t count, size_t size,
984 algo_compare_func *compare, const void *aux)
988 for (idx = count / 2; idx >= 1; idx--)
989 heapify (array, count, size, idx, compare, aux);
990 expensive_assert (count < 1 || is_heap (array, count, size, compare, aux));
993 /* ARRAY contains COUNT elements of SIZE bytes each. Initially
994 all COUNT elements form a heap. This function turns the heap
995 into a fully sorted array. Uses COMPARE to compare elements,
996 passing AUX as auxiliary data. */
998 sort_heap (void *array, size_t count, size_t size,
999 algo_compare_func *compare, const void *aux)
1001 char *first = array;
1004 expensive_assert (is_heap (array, count, size, compare, aux));
1005 for (idx = count; idx >= 2; idx--)
1007 SWAP (first, first + (idx - 1) * size, size);
1008 heapify (array, idx - 1, size, 1, compare, aux);
1010 expensive_assert (is_sorted (array, count, size, compare, aux));
1013 /* ARRAY contains COUNT elements of SIZE bytes each. This
1014 function tests whether ARRAY is a heap and returns true if so,
1015 false otherwise. Uses COMPARE to compare elements, passing
1016 AUX as auxiliary data. */
1018 is_heap (const void *array, size_t count, size_t size,
1019 algo_compare_func *compare, const void *aux)
1021 const char *first = array;
1024 for (child = 2; child <= count; child++)
1026 size_t parent = child / 2;
1027 if (compare (first + (parent - 1) * size,
1028 first + (child - 1) * size, aux) < 0)