X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=src%2Flibpspp%2Farray.c;h=a0ac943af66bc8fceffce5ca8babcd7d3d5dbfe6;hb=81579d9e9f994fb2908f50af41c3eb033d216e58;hp=945874cf1d2993395427aea102e0175a6f08dff7;hpb=dcf9b154cbcaa35c3d8459a201b77eec8bcb30bd;p=pspp-builds.git diff --git a/src/libpspp/array.c b/src/libpspp/array.c index 945874cf..a0ac943a 100644 --- a/src/libpspp/array.c +++ b/src/libpspp/array.c @@ -1,24 +1,21 @@ -/* PSPP - computes sample statistics. - Copyright (C) 1997-9, 2000 Free Software Foundation, Inc. - Written by Ben Pfaff . +/* 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. - + This file is part of the GNU ISO C++ Library. This library is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the @@ -30,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 @@ -85,26 +80,20 @@ 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" - -/* Some of the assertions in this file are very expensive. We - don't use them by default. */ -#ifdef EXTRA_CHECKS -#define expensive_assert(X) assert(X) -#else -#define expensive_assert(X) ((void) 0) -#endif -#include "message.h" +#include "libpspp/assertion.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 @@ -114,11 +103,11 @@ void * find (const void *array, size_t count, size_t size, const void *target, - algo_compare_func *compare, void *aux) + algo_compare_func *compare, const void *aux) { const char *element = array; - while (count-- > 0) + while (count-- > 0) { if (compare (target, element, aux) == 0) return (void *) element; @@ -136,16 +125,16 @@ find (const void *array, size_t count, size_t size, size_t count_equal (const void *array, size_t count, size_t size, const void *element, - algo_compare_func *compare, void *aux) + algo_compare_func *compare, const void *aux) { const char *first = array; size_t equal_cnt = 0; - while (count-- > 0) + while (count-- > 0) { if (compare (element, first, aux) == 0) equal_cnt++; - + first += size; } @@ -154,24 +143,24 @@ count_equal (const void *array, size_t count, size_t size, /* 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 returns true. 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) + algo_predicate_func *predicate, const void *aux) { const char *first = array; - size_t nonzero_cnt = 0; + size_t true_cnt = 0; - while (count-- > 0) + while (count-- > 0) { if (predicate (first, aux) != 0) - nonzero_cnt++; - + true_cnt++; + first += size; } - return nonzero_cnt; + return true_cnt; } /* Byte-wise swap two items of size SIZE. */ @@ -193,29 +182,29 @@ count_if (const void *array, size_t count, size_t size, arrays only. Arguments same as for sort() above. */ size_t unique (void *array, size_t count, size_t size, - algo_compare_func *compare, void *aux) + algo_compare_func *compare, const void *aux) { char *first = array; char *last = first + size * count; char *result = array; - for (;;) + for (;;) { first += size; - if (first >= last) + if (first >= last) { assert (adjacent_find_equal (array, count, size, compare, aux) == NULL); - return count; + return count; } - if (compare (result, first, aux)) + if (compare (result, first, aux)) { result += size; if (result != first) memcpy (result, first, size); } - else + else count--; } } @@ -223,55 +212,55 @@ unique (void *array, size_t count, size_t size, /* Helper function that calls sort(), then unique(). */ size_t sort_unique (void *array, size_t count, size_t size, - algo_compare_func *compare, void *aux) + algo_compare_func *compare, const void *aux) { sort (array, count, size, compare, aux); return unique (array, count, size, compare, aux); } /* Reorders ARRAY, which contains COUNT elements of SIZE bytes - each, so that the elements for which PREDICATE returns nonzero + each, so that the elements for which PREDICATE returns true precede those for which PREDICATE returns zero. AUX is passed to each predicate as auxiliary data. Returns the - number of elements for which PREDICATE returns nonzero. Not + number of elements for which PREDICATE returns true. Not stable. */ -size_t +size_t partition (void *array, size_t count, size_t size, - algo_predicate_func *predicate, void *aux) + algo_predicate_func *predicate, const void *aux) { - size_t nonzero_cnt = count; + size_t true_cnt = count; char *first = array; - char *last = first + nonzero_cnt * size; + char *last = first + true_cnt * size; for (;;) { /* Move FIRST forward to point to first element that fails PREDICATE. */ - for (;;) + for (;;) { if (first == last) goto done; - else if (!predicate (first, aux)) + else if (!predicate (first, aux)) break; - first += size; + first += size; } - nonzero_cnt--; + true_cnt--; /* Move LAST backward to point to last element that passes PREDICATE. */ - for (;;) + for (;;) { last -= size; if (first == last) goto done; - else if (predicate (last, aux)) + else if (predicate (last, aux)) break; else - nonzero_cnt--; + true_cnt--; } - + /* By swapping FIRST and LAST we extend the starting and ending sequences that pass and fail, respectively, PREDICATE. */ @@ -280,49 +269,49 @@ partition (void *array, size_t count, size_t size, } done: - assert (is_partitioned (array, count, size, nonzero_cnt, predicate, aux)); - return nonzero_cnt; + assert (is_partitioned (array, count, size, true_cnt, predicate, aux)); + return true_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 + bytes each, is partitioned such that PREDICATE returns true + for the first TRUE_CNT elements and zero for the remaining elements. AUX is passed as auxiliary data to PREDICATE. */ -int +bool is_partitioned (const void *array, size_t count, size_t size, - size_t nonzero_cnt, - algo_predicate_func *predicate, void *aux) + size_t true_cnt, + algo_predicate_func *predicate, const void *aux) { const char *first = array; size_t idx; - assert (nonzero_cnt <= count); - for (idx = 0; idx < nonzero_cnt; idx++) + assert (true_cnt <= count); + for (idx = 0; idx < true_cnt; idx++) if (predicate (first + idx * size, aux) == 0) - return 0; - for (idx = nonzero_cnt; idx < count; idx++) + return false; + for (idx = true_cnt; idx < count; idx++) if (predicate (first + idx * size, aux) != 0) - return 0; - return 1; + return false; + return true; } /* Copies the COUNT elements of SIZE bytes each from ARRAY to RESULT, except that elements for which PREDICATE is false are not copied. Returns the number of elements copied. AUX is passed to PREDICATE as auxiliary data. */ -size_t +size_t copy_if (const void *array, size_t count, size_t size, void *result, - algo_predicate_func *predicate, void *aux) + algo_predicate_func *predicate, const void *aux) { const char *input = array; const char *last = input + size * count; char *output = result; size_t nonzero_cnt = 0; - + while (input < last) { - if (predicate (input, aux)) + if (predicate (input, aux)) { memcpy (output, input, size); output += size; @@ -343,10 +332,10 @@ copy_if (const void *array, size_t count, size_t size, following them, if any, into its position. */ void remove_range (void *array_, size_t count, size_t size, - size_t idx, size_t n) + size_t idx, size_t n) { char *array = array_; - + assert (array != NULL); assert (idx <= count); assert (idx + n <= count); @@ -361,24 +350,49 @@ remove_range (void *array_, size_t count, size_t size, following it, if any, into its position. */ void remove_element (void *array, size_t count, size_t size, - size_t idx) + size_t idx) { remove_range (array, count, size, idx, 1); } +/* Makes room for N elements starting at IDX in ARRAY, which + initially consists of COUNT elements of SIZE bytes each, by + shifting elements IDX...COUNT (exclusive) to the right by N + positions. */ +void +insert_range (void *array_, size_t count, size_t size, + size_t idx, size_t n) +{ + char *array = array_; + + assert (idx <= count); + memmove (array + (idx + n) * size, array + idx * size, (count - idx) * 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 + position. */ +void +insert_element (void *array, size_t count, size_t size, + size_t idx) +{ + insert_range (array, count, size, idx, 1); +} + /* Moves an element in ARRAY, which consists of COUNT elements of SIZE bytes each, from OLD_IDX to NEW_IDX, shifting around other elements as needed. Runs in O(abs(OLD_IDX - NEW_IDX)) time. */ void move_element (void *array_, size_t count, size_t size, - size_t old_idx, size_t new_idx) + size_t old_idx, size_t new_idx) { assert (array_ != NULL || count == 0); assert (old_idx < count); assert (new_idx < count); - - if (old_idx != new_idx) + + if (old_idx != new_idx) { char *array = array_; char *element = xmalloc (size); @@ -396,15 +410,45 @@ move_element (void *array_, size_t count, size_t size, } } +/* Moves N elements in ARRAY starting at OLD_IDX, which consists + of COUNT elements of SIZE bytes each, so that they now start + at NEW_IDX, shifting around other elements as needed. */ +void +move_range (void *array_, size_t count, size_t size, + size_t old_idx, size_t new_idx, size_t n) +{ + assert (array_ != NULL || count == 0); + assert (n <= count); + assert (old_idx + n <= count); + assert (new_idx + n <= count); + + if (old_idx != new_idx && n > 0) + { + char *array = array_; + char *range = xmalloc (size * n); + char *new = array + new_idx * size; + char *old = array + old_idx * size; + + memcpy (range, old, size * n); + if (new < old) + memmove (new + size * n, new, (old_idx - new_idx) * size); + else + memmove (old, old + size * n, (new_idx - old_idx) * size); + memcpy (new, range, size * n); + + free (range); + } +} + /* A predicate and its auxiliary data. */ -struct pred_aux +struct pred_aux { algo_predicate_func *predicate; - void *aux; + const void *aux; }; -static int -not (const void *data, void *pred_aux_) +static bool +not (const void *data, const void *pred_aux_) { const struct pred_aux *pred_aux = pred_aux_; @@ -418,7 +462,7 @@ not (const void *data, void *pred_aux_) size_t remove_equal (void *array, size_t count, size_t size, void *element, - algo_compare_func *compare, void *aux) + algo_compare_func *compare, const void *aux) { char *first = array; char *last = first + count * size; @@ -436,18 +480,18 @@ remove_equal (void *array, size_t count, size_t size, result = first; count--; - for (;;) + for (;;) { first += size; if (first >= last) goto done; - if (compare (first, element, aux) == 0) + if (compare (first, element, aux) == 0) { - count--; + count--; continue; } - + memcpy (result, first, size); result += size; } @@ -461,10 +505,10 @@ remove_equal (void *array, size_t count, size_t size, RESULT, except that elements for which PREDICATE is true are not copied. Returns the number of elements copied. AUX is passed to PREDICATE as auxiliary data. */ -size_t +size_t remove_copy_if (const void *array, size_t count, size_t size, void *result, - algo_predicate_func *predicate, void *aux) + algo_predicate_func *predicate, const void *aux) { struct pred_aux pred_aux; pred_aux.predicate = predicate; @@ -480,25 +524,25 @@ remove_copy_if (const void *array, size_t count, size_t size, void * binary_search (const void *array, size_t count, size_t size, void *value, - algo_compare_func *compare, void *aux) + algo_compare_func *compare, const void *aux) { - assert (array != NULL); + assert (array != NULL || count == 0); assert (count <= INT_MAX); assert (compare != NULL); - if (count != 0) + if (count != 0) { const char *first = array; int low = 0; int high = count - 1; - while (low <= high) + while (low <= high) { int middle = (low + high) / 2; const char *element = first + middle * size; int cmp = compare (value, element, aux); - if (cmp > 0) + if (cmp > 0) low = middle + 1; else if (cmp < 0) high = middle - 1; @@ -520,7 +564,7 @@ int lexicographical_compare_3way (const void *array1, size_t count1, const void *array2, size_t count2, size_t size, - algo_compare_func *compare, void *aux) + algo_compare_func *compare, const void *aux) { const char *first1 = array1; const char *first2 = array2; @@ -596,7 +640,7 @@ typedef struct void sort (void *array, size_t count, size_t size, - algo_compare_func *compare, void *aux) + algo_compare_func *compare, const void *aux) { char *const first = array; const size_t max_thresh = MAX_THRESH * size; @@ -706,12 +750,10 @@ sort (void *array, size_t count, size_t size, 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 = &first[size * (count - 1)]; char *tmp_ptr = first; - char *thresh = min(end_ptr, first + max_thresh); + char *thresh = MIN (end_ptr, first + max_thresh); register char *run_ptr; /* Find smallest element in first threshold and place it at the @@ -759,18 +801,18 @@ sort (void *array, size_t count, size_t size, /* 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 +bool is_sorted (const void *array, size_t count, size_t size, - algo_compare_func *compare, void *aux) + algo_compare_func *compare, const void *aux) { const 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; + return false; + + return true; } /* Computes the generalized set difference, ARRAY1 minus ARRAY2, @@ -785,7 +827,7 @@ 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) + algo_compare_func *compare, const void *aux) { const char *first1 = array1; const char *last1 = first1 + count1 * size; @@ -793,8 +835,8 @@ size_t set_difference (const void *array1, size_t count1, const char *last2 = first2 + count2 * size; char *result = result_; size_t result_count = 0; - - while (first1 != last1 && first2 != last2) + + while (first1 != last1 && first2 != last2) { int cmp = compare (first1, first2, aux); if (cmp < 0) @@ -813,7 +855,7 @@ size_t set_difference (const void *array1, size_t count1, } } - while (first1 != last1) + while (first1 != last1) { memcpy (result, first1, size); first1 += size; @@ -832,12 +874,12 @@ size_t set_difference (const void *array1, size_t count1, data. */ void * adjacent_find_equal (const void *array, size_t count, size_t size, - algo_compare_func *compare, void *aux) + algo_compare_func *compare, const void *aux) { const char *first = array; const char *last = first + count * size; - while (first < last && first + size < last) + while (first < last && first + size < last) { if (compare (first, first + size, aux) == 0) return (void *) first; @@ -855,21 +897,21 @@ adjacent_find_equal (const void *array, size_t count, size_t size, data. */ void push_heap (void *array, size_t count, size_t size, - algo_compare_func *compare, void *aux) + algo_compare_func *compare, const void *aux) { char *first = array; size_t i; - + expensive_assert (count < 1 || is_heap (array, count - 1, size, compare, aux)); - for (i = count; i > 1; i /= 2) + for (i = count; i > 1; i /= 2) { char *parent = first + (i / 2 - 1) * size; char *element = first + (i - 1) * size; if (compare (parent, element, aux) < 0) SWAP (parent, element, size); else - break; + break; } expensive_assert (is_heap (array, count, size, compare, aux)); } @@ -882,11 +924,11 @@ push_heap (void *array, size_t count, size_t size, static void heapify (void *array, size_t count, size_t size, size_t idx, - algo_compare_func *compare, void *aux) + algo_compare_func *compare, const void *aux) { char *first = array; - - for (;;) + + for (;;) { size_t left = 2 * idx; size_t right = left + 1; @@ -918,7 +960,7 @@ heapify (void *array, size_t count, size_t size, AUX as auxiliary data. */ void pop_heap (void *array, size_t count, size_t size, - algo_compare_func *compare, void *aux) + algo_compare_func *compare, const void *aux) { char *first = array; @@ -934,10 +976,10 @@ pop_heap (void *array, size_t count, size_t size, auxiliary data. */ void make_heap (void *array, size_t count, size_t size, - algo_compare_func *compare, void *aux) + algo_compare_func *compare, const void *aux) { size_t idx; - + for (idx = count / 2; idx >= 1; idx--) heapify (array, count, size, idx, compare, aux); expensive_assert (count < 1 || is_heap (array, count, size, compare, aux)); @@ -949,7 +991,7 @@ make_heap (void *array, size_t count, size_t size, passing AUX as auxiliary data. */ void sort_heap (void *array, size_t count, size_t size, - algo_compare_func *compare, void *aux) + algo_compare_func *compare, const void *aux) { char *first = array; size_t idx; @@ -964,24 +1006,24 @@ sort_heap (void *array, size_t count, size_t size, } /* 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 + function tests whether ARRAY is a heap and returns true if so, + false otherwise. Uses COMPARE to compare elements, passing + AUX as auxiliary data. */ +bool is_heap (const void *array, size_t count, size_t size, - algo_compare_func *compare, void *aux) + algo_compare_func *compare, const void *aux) { const 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 false; } - return 1; + return true; }