X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=src%2Flibpspp%2Farray.c;h=9ae278027bca0ff21432ed718106ec64ba75285d;hb=46d5b8be272fca7206f3f1cb280a90dca1785744;hp=f4a1ef6d953843591f9f77881160981e7f69bdd6;hpb=f5c108becd49d78f4898cab11352291f5689d24e;p=pspp
diff --git a/src/libpspp/array.c b/src/libpspp/array.c
index f4a1ef6d95..9ae278027b 100644
--- a/src/libpspp/array.c
+++ b/src/libpspp/array.c
@@ -1,20 +1,18 @@
-/* PSPP - computes sample statistics.
- Copyright (C) 1997-9, 2000 Free Software Foundation, Inc.
+/* PSPP - a program for statistical analysis.
+ 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 the Free Software Foundation; either version 2 of the
- License, or (at your option) any later version.
+ 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
+ the Free Software Foundation, either version 3 of the License, or
+ (at your option) any later version.
- This program 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
- General Public License for more details.
+ This program 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 General Public License for more details.
You should have received a copy of the GNU General Public License
- along with this program; if not, write to the Free Software
- Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
- 02110-1301, USA. */
+ along with this program. If not, see . */
/* Copyright (C) 2001 Free Software Foundation, Inc.
@@ -29,10 +27,8 @@
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
- You should have received a copy of the GNU General Public License along
- with this library; see the file COPYING. If not, write to the Free
- Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
- USA.
+ You should have received a copy of the GNU General Public License
+ along with this program. If not, see .
As a special exception, you may use this file as part of a free software
library without restriction. Specifically, if other files instantiate
@@ -84,21 +80,21 @@
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., 51 Franklin Street, Fifth Floor, Boston, MA
- 02110-1301 USA. */
+ License along with the GNU C Library. If not, see
+ . */
#include
+
#include "array.h"
+
#include
#include
+#include
#include
-#include "alloc.h"
-#include
-
-#include "message.h"
+#include "libpspp/assertion.h"
-#include "minmax.h"
+#include "gl/xalloc.h"
+#include "gl/minmax.h"
/* Finds an element in ARRAY, which contains COUNT elements of
SIZE bytes each, using COMPARE for comparisons. Returns the
@@ -133,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
@@ -155,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
@@ -233,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 (;;)
{
@@ -250,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. */
@@ -263,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
@@ -284,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;
@@ -312,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)
{
@@ -320,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
@@ -377,7 +373,7 @@ insert_range (void *array_, size_t count, size_t size,
/* 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)
@@ -645,7 +641,7 @@ typedef struct
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;
@@ -675,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;
@@ -700,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)
@@ -770,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. */
@@ -914,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;
}
@@ -952,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;
}
}
@@ -970,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));
@@ -1004,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));
@@ -1032,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;
+ }
+}