X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=src%2Flibpspp%2Farray.c;h=f375f83dfa9851bdb6208d0875d2356031c7501f;hb=d08af71f38b751323cc9506631bf9ce71070a4ae;hp=f4fca27e7d5920d16694f30e1bfffe5d68949c97;hpb=97d4f38945476834fd7fce612b663f19f2b291f8;p=pspp-builds.git diff --git a/src/libpspp/array.c b/src/libpspp/array.c index f4fca27e..f375f83d 100644 --- a/src/libpspp/array.c +++ b/src/libpspp/array.c @@ -1,6 +1,5 @@ /* PSPP - computes sample statistics. Copyright (C) 1997-9, 2000 Free Software Foundation, Inc. - Written by Ben Pfaff . This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as @@ -91,7 +90,6 @@ #include #include "array.h" -#include #include #include #include @@ -99,6 +97,8 @@ #include #include "message.h" + +#include "minmax.h" /* Finds an element in ARRAY, which contains COUNT elements of SIZE bytes each, using COMPARE for comparisons. Returns the @@ -108,7 +108,7 @@ 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; @@ -130,7 +130,7 @@ 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; @@ -148,24 +148,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) { 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. */ @@ -187,7 +187,7 @@ 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; @@ -217,25 +217,25 @@ 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 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 (;;) { @@ -250,7 +250,7 @@ partition (void *array, size_t count, size_t size, first += size; } - nonzero_cnt--; + true_cnt--; /* Move LAST backward to point to last element that passes PREDICATE. */ @@ -263,7 +263,7 @@ partition (void *array, size_t count, size_t size, else if (predicate (last, aux)) break; else - nonzero_cnt--; + true_cnt--; } /* By swapping FIRST and LAST we extend the starting and @@ -274,30 +274,30 @@ 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 @@ -307,7 +307,7 @@ is_partitioned (const void *array, size_t count, size_t size, 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; @@ -360,6 +360,31 @@ remove_element (void *array, size_t count, size_t size, 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 + positions. */ +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)) @@ -390,15 +415,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 { 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_; @@ -412,7 +467,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; @@ -458,7 +513,7 @@ remove_equal (void *array, size_t count, size_t size, 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,7 +529,7 @@ 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 (count <= INT_MAX); @@ -514,7 +569,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 +645,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 +755,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 @@ -753,18 +806,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 false; - return 1; + return true; } /* Computes the generalized set difference, ARRAY1 minus ARRAY2, @@ -779,7 +832,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; @@ -826,7 +879,7 @@ 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; @@ -849,7 +902,7 @@ 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; @@ -876,7 +929,7 @@ 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; @@ -912,7 +965,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,7 +981,7 @@ 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; @@ -943,7 +996,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,12 +1011,12 @@ 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; @@ -973,9 +1026,9 @@ is_heap (const void *array, size_t count, size_t size, 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; }