X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;ds=inline;f=src%2Flibpspp%2Farray.c;h=376bd681dbfa586807c160908cd74b2adb4dd325;hb=96db814fbc3a1ec3bf063e447999444e695c6f93;hp=f4a1ef6d953843591f9f77881160981e7f69bdd6;hpb=f5c108becd49d78f4898cab11352291f5689d24e;p=pspp
diff --git a/src/libpspp/array.c b/src/libpspp/array.c
index f4a1ef6d95..376bd681db 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
@@ -168,19 +164,19 @@ count_if (const void *array, size_t count, size_t size,
return true_cnt;
}
-/* 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
@@ -269,7 +265,7 @@ partition (void *array, size_t count, size_t size,
/* 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;
}
@@ -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;
+ }
+}