/* PSPP - a program for statistical analysis.
- Copyright (C) 1997-9, 2000 Free Software Foundation, Inc.
+ Copyright (C) 1997-9, 2000, 2010, 2011 Free Software Foundation, Inc.
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
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, see
+ License along with the GNU C Library. If not, see
<http://www.gnu.org/licenses/>. */
#include <config.h>
+
#include "array.h"
+
#include <limits.h>
#include <stdlib.h>
+#include <stdint.h>
#include <string.h>
-#include <libpspp/assertion.h>
+#include "libpspp/assertion.h"
-#include "xalloc.h"
-#include "minmax.h"
+#include "gl/xalloc.h"
+#include "gl/minmax.h"
\f
/* Finds an element in ARRAY, which contains COUNT elements of
SIZE bytes each, using COMPARE for comparisons. Returns the
algo_compare_func *compare, const void *aux)
{
const char *first = array;
- size_t equal_cnt = 0;
+ size_t n_equals = 0;
while (count-- > 0)
{
if (compare (element, first, aux) == 0)
- equal_cnt++;
+ n_equals++;
first += size;
}
- return equal_cnt;
+ return n_equals;
}
/* Counts and return the number of elements in ARRAY, which
algo_predicate_func *predicate, const void *aux)
{
const char *first = array;
- size_t true_cnt = 0;
+ size_t n_trues = 0;
while (count-- > 0)
{
if (predicate (first, aux) != 0)
- true_cnt++;
+ n_trues++;
first += size;
}
- return true_cnt;
+ return n_trues;
}
\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); \
- } while (0)
+/* Byte-wise swap objects A and B, each SIZE bytes. */
+static void
+swap (void *a_, void *b_, size_t size)
+{
+ uint8_t *a = a_;
+ uint8_t *b = b_;
+ while (size-- > 0)
+ {
+ uint8_t tmp = *a;
+ *a++ = *b;
+ *b++ = tmp;
+ }
+}
/* Makes the elements in ARRAY unique, by moving up duplicates,
and returns the new number of elements in the array. Sorted
partition (void *array, size_t count, size_t size,
algo_predicate_func *predicate, const void *aux)
{
- size_t true_cnt = count;
+ size_t n_trues = count;
char *first = array;
- char *last = first + true_cnt * size;
+ char *last = first + n_trues * size;
for (;;)
{
first += size;
}
- true_cnt--;
+ n_trues--;
/* Move LAST backward to point to last element that passes
PREDICATE. */
else if (predicate (last, aux))
break;
else
- true_cnt--;
+ n_trues--;
}
/* By swapping FIRST and LAST we extend the starting and
ending sequences that pass and fail, respectively,
PREDICATE. */
- SWAP (first, last, size);
+ swap (first, last, size);
first += size;
}
done:
- assert (is_partitioned (array, count, size, true_cnt, predicate, aux));
- return true_cnt;
+ assert (is_partitioned (array, count, size, n_trues, predicate, aux));
+ return n_trues;
}
/* Checks whether ARRAY, which contains COUNT elements of SIZE
elements. AUX is passed as auxiliary data to PREDICATE. */
bool
is_partitioned (const void *array, size_t count, size_t size,
- size_t true_cnt,
+ size_t n_trues,
algo_predicate_func *predicate, const void *aux)
{
const char *first = array;
size_t idx;
- assert (true_cnt <= count);
- for (idx = 0; idx < true_cnt; idx++)
+ assert (n_trues <= count);
+ for (idx = 0; idx < n_trues; idx++)
if (predicate (first + idx * size, aux) == 0)
return false;
- for (idx = true_cnt; idx < count; idx++)
+ for (idx = n_trues; idx < count; idx++)
if (predicate (first + idx * size, aux) != 0)
return false;
return true;
const char *input = array;
const char *last = input + size * count;
char *output = result;
- size_t nonzero_cnt = 0;
+ size_t n_nonzeros = 0;
while (input < last)
{
{
memcpy (output, input, size);
output += size;
- nonzero_cnt++;
+ n_nonzeros++;
}
input += size;
}
- assert (nonzero_cnt == count_if (array, count, size, predicate, aux));
- assert (nonzero_cnt == count_if (result, nonzero_cnt, size, predicate, aux));
+ assert (n_nonzeros == count_if (array, count, size, predicate, aux));
+ assert (n_nonzeros == count_if (result, n_nonzeros, size, predicate, aux));
- return nonzero_cnt;
+ return n_nonzeros;
}
/* Removes N elements starting at IDX from ARRAY, which consists
/* Makes room for a new element at IDX in ARRAY, which initially
consists of COUNT elements of SIZE bytes each, by shifting
elements IDX...COUNT (exclusive) to the right by one
- positions. */
+ position. */
void
insert_element (void *array, size_t count, size_t size,
size_t idx)
void
sort (void *array, size_t count, size_t size,
- algo_compare_func *compare, const void *aux)
+ algo_compare_func *compare, const void *aux)
{
char *const first = array;
const size_t max_thresh = MAX_THRESH * size;
char *mid = lo + size * ((hi - lo) / size >> 1);
if (compare (mid, lo, aux) < 0)
- SWAP (mid, lo, size);
+ swap (mid, lo, size);
if (compare (hi, mid, aux) < 0)
- SWAP (mid, hi, size);
+ swap (mid, hi, size);
else
goto jump_over;
if (compare (mid, lo, aux) < 0)
- SWAP (mid, lo, size);
+ swap (mid, lo, size);
jump_over:;
left_ptr = lo + size;
if (left_ptr < right_ptr)
{
- SWAP (left_ptr, right_ptr, size);
+ swap (left_ptr, right_ptr, size);
if (mid == left_ptr)
mid = right_ptr;
else if (mid == right_ptr)
tmp_ptr = run_ptr;
if (tmp_ptr != first)
- SWAP (tmp_ptr, first, size);
+ swap (tmp_ptr, first, size);
/* Insertion sort, running from left-hand-side up to right-hand-side. */
char *parent = first + (i / 2 - 1) * size;
char *element = first + (i - 1) * size;
if (compare (parent, element, aux) < 0)
- SWAP (parent, element, size);
+ swap (parent, element, size);
else
break;
}
if (largest == idx)
break;
- SWAP (first + size * (idx - 1), first + size * (largest - 1), size);
+ swap (first + size * (idx - 1), first + size * (largest - 1), size);
idx = largest;
}
}
char *first = array;
expensive_assert (is_heap (array, count, size, compare, aux));
- SWAP (first, first + (count - 1) * size, size);
+ swap (first, first + (count - 1) * size, size);
heapify (first, count - 1, size, 1, compare, aux);
expensive_assert (count < 1 || is_heap (array, count - 1,
size, compare, aux));
expensive_assert (is_heap (array, count, size, compare, aux));
for (idx = count; idx >= 2; idx--)
{
- SWAP (first, first + (idx - 1) * size, size);
+ swap (first, first + (idx - 1) * size, size);
heapify (array, idx - 1, size, 1, compare, aux);
}
expensive_assert (is_sorted (array, count, size, compare, aux));
return true;
}
+/* Reverses the order of ARRAY, which contains COUNT elements of SIZE bytes
+ each. */
+void
+reverse_array (void *array_, size_t count, size_t size)
+{
+ uint8_t *array = array_;
+ uint8_t *first = array;
+ uint8_t *last = array + (count - 1) * size;
+ for (size_t i = 0; i < count / 2; i++)
+ {
+ swap (first, last, size);
+ first += size;
+ last -= size;
+ }
+}
projects / pspp / blobdiff