X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=src%2Flibpspp%2Farray.c;h=a0ac943af66bc8fceffce5ca8babcd7d3d5dbfe6;hb=81579d9e9f994fb2908f50af41c3eb033d216e58;hp=1349f25380bc3943ea7defd1fb0b7ba42ac8efd5;hpb=c708736bdd0fea4b79f3ee4a10e00c3abb95d9e3;p=pspp-builds.git diff --git a/src/libpspp/array.c b/src/libpspp/array.c index 1349f253..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,20 +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" -#include +#include "libpspp/assertion.h" -#include "message.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 @@ -108,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; @@ -130,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; } @@ -152,16 +147,16 @@ count_equal (const void *array, size_t count, size_t size, 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 true_cnt = 0; - while (count-- > 0) + while (count-- > 0) { if (predicate (first, aux) != 0) true_cnt++; - + first += size; } @@ -187,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--; } } @@ -217,7 +212,7 @@ 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); @@ -229,9 +224,9 @@ sort_unique (void *array, size_t count, size_t size, passed to each predicate as auxiliary data. Returns the 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 true_cnt = count; char *first = array; @@ -241,31 +236,31 @@ partition (void *array, size_t count, size_t size, { /* 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; } 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 true_cnt--; } - + /* By swapping FIRST and LAST we extend the starting and ending sequences that pass and fail, respectively, PREDICATE. */ @@ -275,7 +270,7 @@ partition (void *array, size_t count, size_t size, done: assert (is_partitioned (array, count, size, true_cnt, predicate, aux)); - return true_cnt; + return true_cnt; } /* Checks whether ARRAY, which contains COUNT elements of SIZE @@ -285,7 +280,7 @@ partition (void *array, size_t count, size_t size, bool is_partitioned (const void *array, size_t count, size_t size, size_t true_cnt, - algo_predicate_func *predicate, void *aux) + algo_predicate_func *predicate, const void *aux) { const char *first = array; size_t idx; @@ -304,19 +299,19 @@ is_partitioned (const void *array, size_t count, size_t size, 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; @@ -337,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); @@ -355,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); @@ -390,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 bool -not (const void *data, void *pred_aux_) +not (const void *data, const void *pred_aux_) { const struct pred_aux *pred_aux = pred_aux_; @@ -412,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; @@ -430,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; } @@ -455,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; @@ -474,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; @@ -514,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; @@ -590,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; @@ -700,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 @@ -755,15 +803,15 @@ sort (void *array, size_t count, size_t size, passed to COMPARE as auxiliary data. */ 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 false; - + return false; + return true; } @@ -779,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; @@ -787,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) @@ -807,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; @@ -826,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; @@ -849,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)); } @@ -876,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; @@ -912,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; @@ -928,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)); @@ -943,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; @@ -958,16 +1006,16 @@ 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 true if so, - false otherwise. Uses COMPARE to compare elements, passing + 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;