X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=src%2Flibpspp%2Farray.c;h=9ae278027bca0ff21432ed718106ec64ba75285d;hb=06ac0c2d623e9ae54c3e22a2d6740219ab357b21;hp=a0ac943af66bc8fceffce5ca8babcd7d3d5dbfe6;hpb=81579d9e9f994fb2908f50af41c3eb033d216e58;p=pspp
diff --git a/src/libpspp/array.c b/src/libpspp/array.c
index a0ac943af6..9ae278027b 100644
--- a/src/libpspp/array.c
+++ b/src/libpspp/array.c
@@ -80,7 +80,7 @@
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
. */
#include
@@ -89,6 +89,7 @@
#include
#include
+#include
#include
#include "libpspp/assertion.h"
@@ -128,17 +129,17 @@ count_equal (const void *array, size_t count, size_t size,
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
@@ -150,32 +151,32 @@ count_if (const void *array, size_t count, size_t size,
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;
}
-/* 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
@@ -228,9 +229,9 @@ size_t
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 (;;)
{
@@ -245,7 +246,7 @@ partition (void *array, size_t count, size_t size,
first += size;
}
- true_cnt--;
+ n_trues--;
/* Move LAST backward to point to last element that passes
PREDICATE. */
@@ -258,19 +259,19 @@ partition (void *array, size_t count, size_t size,
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
@@ -279,17 +280,17 @@ partition (void *array, size_t count, size_t 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;
@@ -307,7 +308,7 @@ copy_if (const void *array, size_t count, size_t size,
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)
{
@@ -315,16 +316,16 @@ copy_if (const void *array, size_t count, size_t size,
{
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
@@ -670,13 +671,13 @@ sort (void *array, size_t count, size_t 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;
@@ -695,7 +696,7 @@ sort (void *array, size_t count, size_t 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)
@@ -765,7 +766,7 @@ sort (void *array, size_t count, size_t size,
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. */
@@ -909,7 +910,7 @@ push_heap (void *array, size_t count, size_t size,
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;
}
@@ -947,7 +948,7 @@ heapify (void *array, size_t count, size_t size,
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;
}
}
@@ -965,7 +966,7 @@ pop_heap (void *array, size_t count, size_t size,
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));
@@ -999,7 +1000,7 @@ sort_heap (void *array, size_t count, size_t size,
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));
@@ -1027,3 +1028,18 @@ is_heap (const void *array, size_t count, size_t size,
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;
+ }
+}