* purpose. It is provided "as is" without express or implied warranty.
*/
+/* Copyright (C) 1991, 1992, 1996, 1997, 1999 Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
+ Written by Douglas C. Schmidt (schmidt@ics.uci.edu).
+
+ The GNU C Library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Lesser General Public
+ License as published by the Free Software Foundation; either
+ version 2.1 of the License, or (at your option) any later version.
+
+ The GNU C Library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public
+ License along with the GNU C Library; if not, write to the Free
+ Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
+ 02111-1307 USA. */
+
#include <config.h>
-#include <assert.h>
+#include "algorithm.h"
#include <limits.h>
#include <stdlib.h>
#include <string.h>
#include "alloc.h"
-#include "algorithm.h"
#include "random.h"
+
+/* Some of the assertions in this file are very expensive. If
+ we're optimizing, don't include them. */
+#if __OPTIMIZE__
+#define NDEBUG
+#endif
+#include <assert.h>
+\f
+/* Finds an element in ARRAY, which contains COUNT elements of
+ SIZE bytes each, using COMPARE for comparisons. Returns the
+ first element in ARRAY that matches TARGET, or a null pointer
+ on failure. AUX is passed to each comparison as auxiliary
+ data. */
+void *
+find (const void *array, size_t count, size_t size,
+ const void *target,
+ algo_compare_func *compare, void *aux)
+{
+ const unsigned char *element = array;
+
+ while (count-- > 0)
+ {
+ if (compare (target, element, aux) == 0)
+ return (void *) element;
+
+ element += size;
+ }
+
+ return NULL;
+}
+
+/* Counts and return the number of elements in ARRAY, which
+ contains COUNT elements of SIZE bytes each, which are equal to
+ ELEMENT as compared with COMPARE. AUX is passed as auxiliary
+ data to COMPARE. */
+size_t
+count_equal (const void *array, size_t count, size_t size,
+ const void *element,
+ algo_compare_func *compare, void *aux)
+{
+ const unsigned char *first = array;
+ size_t equal_cnt = 0;
+
+ while (count-- > 0)
+ {
+ if (compare (element, first, aux) == 0)
+ equal_cnt++;
+
+ first += size;
+ }
+
+ return equal_cnt;
+}
+
+/* Counts and return the number of elements in ARRAY, which
+ contains COUNT elements of SIZE bytes each, for which
+ PREDICATE returns nonzero. AUX is passed as auxiliary data to
+ PREDICATE. */
+size_t
+count_if (const void *array, size_t count, size_t size,
+ algo_predicate_func *predicate, void *aux)
+{
+ const unsigned char *first = array;
+ size_t nonzero_cnt = 0;
+
+ while (count-- > 0)
+ {
+ if (predicate (first, aux) != 0)
+ nonzero_cnt++;
+
+ first += size;
+ }
+
+ return nonzero_cnt;
+}
\f
/* Byte-wise swap two items of size SIZE. */
-#define SWAP(a, b, size) \
- do \
- { \
- register size_t __size = (size); \
- register char *__a = (a), *__b = (b); \
- do \
- { \
- char __tmp = *__a; \
- *__a++ = *__b; \
- *__b++ = __tmp; \
- } while (--__size > 0); \
+#define SWAP(a, b, size) \
+ do \
+ { \
+ register size_t __size = (size); \
+ register char *__a = (a), *__b = (b); \
+ do \
+ { \
+ char __tmp = *__a; \
+ *__a++ = *__b; \
+ *__b++ = __tmp; \
+ } while (--__size > 0); \
} while (0)
/* Makes the elements in ARRAY unique, by moving up duplicates,
for (;;)
{
first += size;
- if (first >= last)
- return count;
+ if (first >= last)
+ {
+ assert (adjacent_find_equal (array, count, size, compare, aux) == NULL);
+ return count;
+ }
if (compare (result, first, aux))
{
sort (array, count, size, compare, aux);
return unique (array, count, size, compare, aux);
}
-
-#ifdef TEST_UNIQUE
-#include <stdio.h>
-
-void *
-xmalloc (size_t size)
-{
- return malloc (size);
-}
-
-int
-compare_ints (const void *a_, const void *b_, void *aux)
-{
- const int *a = a_;
- const int *b = b_;
-
- if (*a > *b)
- return 1;
- else if (*a < *b)
- return 1;
- else
- return 0;
-}
-
-void
-try_unique (const char *title,
- int *in, size_t in_cnt,
- size_t out_cnt)
-{
- size_t i;
-
- in_cnt = unique (in, in_cnt, sizeof *in, compare_ints, NULL);
- if (in_cnt != out_cnt)
- {
- fprintf (stderr, "unique_test: %s: in_cnt %d, expected %d\n",
- title, (int) in_cnt, (int) out_cnt);
- return;
- }
-
- for (i = 0; i < out_cnt; i++)
- {
- if (in[i] != i)
- fprintf (stderr, "unique_test: %s: idx %d = %d, expected %d\n",
- title, (int) i, in[i], i);
- }
-}
-
-int
-main (void)
-{
- int a_in[] = {0, 0, 0, 1, 2, 3, 3, 4, 5, 5};
- int b_in[] = {0, 1, 2, 2, 2, 3};
- int c_in[] = {0};
- int d_in;
-
- try_unique ("a", a_in, sizeof a_in / sizeof *a_in, 6);
- try_unique ("b", b_in, sizeof b_in / sizeof *b_in, 4);
- try_unique ("c", c_in, sizeof c_in / sizeof *c_in, 1);
- try_unique ("d", &d_in, 0, 0);
-
-}
-#endif /* TEST_UNIQUE */
\f
/* Reorders ARRAY, which contains COUNT elements of SIZE bytes
each, so that the elements for which PREDICATE returns nonzero
partition (void *array, size_t count, size_t size,
algo_predicate_func *predicate, void *aux)
{
+ size_t nonzero_cnt = count;
char *first = array;
- char *last = first + count * size;
+ char *last = first + nonzero_cnt * size;
for (;;)
{
for (;;)
{
if (first == last)
- return count;
+ goto done;
else if (!predicate (first, aux))
break;
first += size;
}
- count--;
+ nonzero_cnt--;
/* Move LAST backward to point to last element that passes
PREDICATE. */
last -= size;
if (first == last)
- return count;
+ goto done;
else if (predicate (last, aux))
break;
else
- count--;
+ nonzero_cnt--;
}
/* By swapping FIRST and LAST we extend the starting and
SWAP (first, last, size);
first += size;
}
+
+ done:
+ assert (is_partitioned (array, count, size, nonzero_cnt, predicate, aux));
+ return nonzero_cnt;
+}
+
+/* Checks whether ARRAY, which contains COUNT elements of SIZE
+ bytes each, is partitioned such that PREDICATE returns nonzero
+ for the first NONZERO_CNT elements and zero for the remaining
+ elements. AUX is passed as auxiliary data to PREDICATE. */
+int
+is_partitioned (const void *array, size_t count, size_t size,
+ size_t nonzero_cnt,
+ algo_predicate_func *predicate, void *aux)
+{
+ const unsigned char *first = array;
+ size_t idx;
+
+ assert (nonzero_cnt <= count);
+ for (idx = 0; idx < nonzero_cnt; idx++)
+ if (predicate (first + idx * size, aux) == 0)
+ return 0;
+ for (idx = nonzero_cnt; idx < count; idx++)
+ if (predicate (first + idx * size, aux) != 0)
+ return 0;
+ return 1;
}
\f
/* A algo_random_func that uses random.h. */
unsigned
-algo_default_random (unsigned max, void *aux unused)
+algo_default_random (unsigned max, void *aux UNUSED)
{
return rng_get_unsigned (pspp_rng ()) % max;
}
const unsigned char *input = array;
const unsigned char *last = input + size * count;
unsigned char *output = result;
+ size_t nonzero_cnt = 0;
- while (input <= last)
+ while (input < last)
{
if (predicate (input, aux))
{
memcpy (output, input, size);
output += size;
+ nonzero_cnt++;
}
- else
- count--;
input += size;
}
- return count;
+ assert (nonzero_cnt == count_if (array, count, size, predicate, aux));
+ assert (nonzero_cnt == count_if (result, nonzero_cnt, size, predicate, aux));
+
+ return nonzero_cnt;
}
/* A predicate and its auxiliary data. */
return !pred_aux->predicate (data, pred_aux->aux);
}
+/* Removes elements equal to ELEMENT from ARRAY, which consists
+ of COUNT elements of SIZE bytes each. Returns the number of
+ remaining elements. AUX is passed to COMPARE as auxiliary
+ data. */
+size_t
+remove_equal (void *array, size_t count, size_t size,
+ void *element,
+ algo_compare_func *compare, void *aux)
+{
+ unsigned char *first = array;
+ unsigned char *last = first + count * size;
+ unsigned char *result;
+
+ for (;;)
+ {
+ if (first >= last)
+ goto done;
+ if (compare (first, element, aux) == 0)
+ break;
+
+ first += size;
+ }
+
+ result = first;
+ count--;
+ for (;;)
+ {
+ first += size;
+ if (first >= last)
+ goto done;
+
+ if (compare (first, element, aux) == 0)
+ {
+ count--;
+ continue;
+ }
+
+ memcpy (result, first, size);
+ result += size;
+ }
+
+ done:
+ assert (count_equal (array, count, size, element, compare, aux) == 0);
+ return count;
+}
+
/* Copies the COUNT elements of SIZE bytes each from ARRAY to
RESULT, except that elements for which PREDICATE is true are
not copied. Returns the number of elements copied. AUX is
return (void *) element;
}
}
+
+ assert (find (array, count, size, value, compare, aux) == NULL);
return NULL;
}
\f
strcmp()-type result. AUX is passed to COMPARE as auxiliary
data. */
int
-lexicographical_compare (const void *array1, size_t count1,
- const void *array2, size_t count2,
- size_t size,
- algo_compare_func *compare, void *aux)
+lexicographical_compare_3way (const void *array1, size_t count1,
+ const void *array2, size_t count2,
+ size_t size,
+ algo_compare_func *compare, void *aux)
{
const unsigned char *first1 = array1;
const unsigned char *first2 = array2;
return count1 < count2 ? -1 : count1 > count2;
}
-
\f
-/* Copyright (C) 1991, 1992, 1996, 1997, 1999 Free Software Foundation, Inc.
- This file is part of the GNU C Library.
- Written by Douglas C. Schmidt (schmidt@ics.uci.edu).
-
- The GNU C Library is free software; you can redistribute it and/or
- modify it under the terms of the GNU Lesser General Public
- License as published by the Free Software Foundation; either
- version 2.1 of the License, or (at your option) any later version.
-
- The GNU C Library is distributed in the hope that it will be useful,
- but WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- Lesser General Public License for more details.
-
- You should have received a copy of the GNU Lesser General Public
- License along with the GNU C Library; if not, write to the Free
- Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
- 02111-1307 USA. */
-
/* If you consider tuning this algorithm, you should consult first:
Engineering a sort function; Jon Bentley and M. Douglas McIlroy;
Software - Practice and Experience; Vol. 23 (11), 1249-1265, 1993. */
stack size is needed (actually O(1) in this case)! */
void
-sort (void *const pbase, size_t total_elems, size_t size,
- algo_compare_func *cmp, void *aux)
+sort (void *array, size_t count, size_t size,
+ algo_compare_func *compare, void *aux)
{
- register char *base_ptr = (char *) pbase;
-
+ char *const first = array;
const size_t max_thresh = MAX_THRESH * size;
- if (total_elems == 0)
+ if (count == 0)
/* Avoid lossage with unsigned arithmetic below. */
return;
- if (total_elems > MAX_THRESH)
+ if (count > MAX_THRESH)
{
- char *lo = base_ptr;
- char *hi = &lo[size * (total_elems - 1)];
+ char *lo = first;
+ char *hi = &lo[size * (count - 1)];
stack_node stack[STACK_SIZE];
stack_node *top = stack + 1;
char *mid = lo + size * ((hi - lo) / size >> 1);
- if ((*cmp) ((void *) mid, (void *) lo, aux) < 0)
+ if (compare (mid, lo, aux) < 0)
SWAP (mid, lo, size);
- if ((*cmp) ((void *) hi, (void *) mid, aux) < 0)
+ if (compare (hi, mid, aux) < 0)
SWAP (mid, hi, size);
else
goto jump_over;
- if ((*cmp) ((void *) mid, (void *) lo, aux) < 0)
+ if (compare (mid, lo, aux) < 0)
SWAP (mid, lo, size);
jump_over:;
that this algorithm runs much faster than others. */
do
{
- while ((*cmp) ((void *) left_ptr, (void *) mid, aux) < 0)
+ while (compare (left_ptr, mid, aux) < 0)
left_ptr += size;
- while ((*cmp) ((void *) mid, (void *) right_ptr, aux) < 0)
+ while (compare (mid, right_ptr, aux) < 0)
right_ptr -= size;
if (left_ptr < right_ptr)
}
}
- /* Once the BASE_PTR array is partially sorted by quicksort the rest
+ /* Once the FIRST array is partially sorted by quicksort the rest
is completely sorted using insertion sort, since this is efficient
- for partitions below MAX_THRESH size. BASE_PTR points to the beginning
+ for partitions below MAX_THRESH size. FIRST points to the beginning
of the array to sort, and END_PTR points at the very last element in
the array (*not* one beyond it!). */
#define min(x, y) ((x) < (y) ? (x) : (y))
{
- char *const end_ptr = &base_ptr[size * (total_elems - 1)];
- char *tmp_ptr = base_ptr;
- char *thresh = min(end_ptr, base_ptr + max_thresh);
+ char *const end_ptr = &first[size * (count - 1)];
+ char *tmp_ptr = first;
+ char *thresh = min(end_ptr, first + max_thresh);
register char *run_ptr;
/* Find smallest element in first threshold and place it at the
and the operation speeds up insertion sort's inner loop. */
for (run_ptr = tmp_ptr + size; run_ptr <= thresh; run_ptr += size)
- if ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, aux) < 0)
+ if (compare (run_ptr, tmp_ptr, aux) < 0)
tmp_ptr = run_ptr;
- if (tmp_ptr != base_ptr)
- SWAP (tmp_ptr, base_ptr, size);
+ if (tmp_ptr != first)
+ SWAP (tmp_ptr, first, size);
/* Insertion sort, running from left-hand-side up to right-hand-side. */
- run_ptr = base_ptr + size;
+ run_ptr = first + size;
while ((run_ptr += size) <= end_ptr)
{
tmp_ptr = run_ptr - size;
- while ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, aux) < 0)
+ while (compare (run_ptr, tmp_ptr, aux) < 0)
tmp_ptr -= size;
tmp_ptr += size;
}
}
}
+
+ assert (is_sorted (array, count, size, compare, aux));
+}
+
+/* Tests whether ARRAY, which contains COUNT elements of SIZE
+ bytes each, is sorted in order according to COMPARE. AUX is
+ passed to COMPARE as auxiliary data. */
+int
+is_sorted (const void *array, size_t count, size_t size,
+ algo_compare_func *compare, void *aux)
+{
+ const unsigned char *first = array;
+ size_t idx;
+
+ for (idx = 0; idx + 1 < count; idx++)
+ if (compare (first + idx * size, first + (idx + 1) * size, aux) > 0)
+ return 0;
+
+ return 1;
+}
+\f
+/* Computes the generalized set difference, ARRAY1 minus ARRAY2,
+ into RESULT, and returns the number of elements written to
+ RESULT. If a value appears M times in ARRAY1 and N times in
+ ARRAY2, then it will appear max(M - N, 0) in RESULT. ARRAY1
+ and ARRAY2 must be sorted, and RESULT is sorted and stable.
+ ARRAY1 consists of COUNT1 elements, ARRAY2 of COUNT2 elements,
+ each SIZE bytes. AUX is passed to COMPARE as auxiliary
+ data. */
+size_t set_difference (const void *array1, size_t count1,
+ const void *array2, size_t count2,
+ size_t size,
+ void *result_,
+ algo_compare_func *compare, void *aux)
+{
+ const unsigned char *first1 = array1;
+ const unsigned char *last1 = first1 + count1 * size;
+ const unsigned char *first2 = array2;
+ const unsigned char *last2 = first2 + count2 * size;
+ unsigned char *result = result_;
+ size_t result_count = 0;
+
+ while (first1 != last1 && first2 != last2)
+ {
+ int cmp = compare (first1, first2, aux);
+ if (cmp < 0)
+ {
+ memcpy (result, first1, size);
+ first1 += size;
+ result += size;
+ result_count++;
+ }
+ else if (cmp > 0)
+ first2 += size;
+ else
+ {
+ first1 += size;
+ first2 += size;
+ }
+ }
+
+ while (first1 != last1)
+ {
+ memcpy (result, first1, size);
+ first1 += size;
+ result += size;
+ result_count++;
+ }
+
+ return result_count;
+}
+\f
+/* Finds the first pair of adjacent equal elements in ARRAY,
+ which has COUNT elements of SIZE bytes. Returns the first
+ element in ARRAY such that COMPARE returns zero when it and
+ its successor element are compared, or a null pointer if no
+ such element exists. AUX is passed to COMPARE as auxiliary
+ data. */
+void *
+adjacent_find_equal (const void *array, size_t count, size_t size,
+ algo_compare_func *compare, void *aux)
+{
+ const unsigned char *first = array;
+ const unsigned char *last = first + count * size;
+
+ while (first < last && first + size < last)
+ {
+ if (compare (first, first + size, aux) == 0)
+ return (void *) first;
+ first += size;
+ }
+
+ return NULL;
+}
+\f
+/* ARRAY contains COUNT elements of SIZE bytes each. Initially
+ the first COUNT - 1 elements of these form a heap, followed by
+ a single element not part of the heap. This function adds the
+ final element, forming a heap of COUNT elements in ARRAY.
+ Uses COMPARE to compare elements, passing AUX as auxiliary
+ data. */
+void
+push_heap (void *array, size_t count, size_t size,
+ algo_compare_func *compare, void *aux)
+{
+ unsigned char *first = array;
+ size_t i;
+
+ assert (count < 1 || is_heap (array, count - 1, size, compare, aux));
+ for (i = count; i > 1; i /= 2)
+ {
+ unsigned char *parent = first + (i / 2 - 1) * size;
+ unsigned char *element = first + (i - 1) * size;
+ if (compare (parent, element, aux) < 0)
+ SWAP (parent, element, size);
+ else
+ break;
+ }
+ assert (is_heap (array, count, size, compare, aux));
+}
+
+/* ARRAY contains COUNT elements of SIZE bytes each. Initially
+ the children of ARRAY[idx - 1] are heaps, but ARRAY[idx - 1]
+ may be smaller than its children. This function fixes that,
+ so that ARRAY[idx - 1] itself is a heap. Uses COMPARE to
+ compare elements, passing AUX as auxiliary data. */
+static void
+heapify (void *array, size_t count, size_t size,
+ size_t idx,
+ algo_compare_func *compare, void *aux)
+{
+ unsigned char *first = array;
+
+ for (;;)
+ {
+ size_t left = 2 * idx;
+ size_t right = left + 1;
+ size_t largest = idx;
+
+ if (left <= count
+ && compare (first + size * (left - 1),
+ first + size * (idx - 1), aux) > 0)
+ largest = left;
+
+ if (right <= count
+ && compare (first + size * (right - 1),
+ first + size * (largest - 1), aux) > 0)
+ largest = right;
+
+ if (largest == idx)
+ break;
+
+ SWAP (first + size * (idx - 1), first + size * (largest - 1), size);
+ idx = largest;
+ }
+}
+
+/* ARRAY contains COUNT elements of SIZE bytes each. Initially
+ all COUNT elements form a heap. This function moves the
+ largest element in the heap to the final position in ARRAY and
+ reforms a heap of the remaining COUNT - 1 elements at the
+ beginning of ARRAY. Uses COMPARE to compare elements, passing
+ AUX as auxiliary data. */
+void
+pop_heap (void *array, size_t count, size_t size,
+ algo_compare_func *compare, void *aux)
+{
+ unsigned char *first = array;
+
+ assert (is_heap (array, count, size, compare, aux));
+ SWAP (first, first + (count - 1) * size, size);
+ heapify (first, count - 1, size, 1, compare, aux);
+ assert (count < 1 || is_heap (array, count - 1, size, compare, aux));
+}
+
+/* Turns ARRAY, which contains COUNT elements of SIZE bytes, into
+ a heap. Uses COMPARE to compare elements, passing AUX as
+ auxiliary data. */
+void
+make_heap (void *array, size_t count, size_t size,
+ algo_compare_func *compare, void *aux)
+{
+ size_t idx;
+
+ for (idx = count / 2; idx >= 1; idx--)
+ heapify (array, count, size, idx, compare, aux);
+ assert (count < 1 || is_heap (array, count, size, compare, aux));
+}
+
+/* ARRAY contains COUNT elements of SIZE bytes each. Initially
+ all COUNT elements form a heap. This function turns the heap
+ into a fully sorted array. Uses COMPARE to compare elements,
+ passing AUX as auxiliary data. */
+void
+sort_heap (void *array, size_t count, size_t size,
+ algo_compare_func *compare, void *aux)
+{
+ unsigned char *first = array;
+ size_t idx;
+
+ assert (is_heap (array, count, size, compare, aux));
+ for (idx = count; idx >= 2; idx--)
+ {
+ SWAP (first, first + (idx - 1) * size, size);
+ heapify (array, idx - 1, size, 1, compare, aux);
+ }
+ assert (is_sorted (array, count, size, compare, aux));
+}
+
+/* ARRAY contains COUNT elements of SIZE bytes each. This
+ function tests whether ARRAY is a heap and returns 1 if so, 0
+ otherwise. Uses COMPARE to compare elements, passing AUX as
+ auxiliary data. */
+int
+is_heap (const void *array, size_t count, size_t size,
+ algo_compare_func *compare, void *aux)
+{
+ const unsigned char *first = array;
+ size_t child;
+
+ for (child = 2; child <= count; child++)
+ {
+ size_t parent = child / 2;
+ if (compare (first + (parent - 1) * size,
+ first + (child - 1) * size, aux) < 0)
+ return 0;
+ }
+
+ return 1;
}
+
projects / pspp-builds.git / blobdiff