X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=src%2Flibpspp%2Farray.c;h=8af5d8fecec7ce1ccd5891cae5de6364ea3f8c89;hb=19f2bec879b9b03eebc8b32b67332c9ea586188d;hp=3d834ff5e4f4a7c0f343fc578d088caf58f437bd;hpb=ebccf00cbddbcadb5883fa98ddbccbea67642295;p=pspp-builds.git diff --git a/src/libpspp/array.c b/src/libpspp/array.c index 3d834ff5..8af5d8fe 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,20 +90,15 @@ #include #include "array.h" -#include #include #include #include #include "alloc.h" +#include -/* 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 "minmax.h" /* Finds an element in ARRAY, which contains COUNT elements of SIZE bytes each, using COMPARE for comparisons. Returns the @@ -114,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; @@ -136,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; @@ -154,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. */ @@ -193,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; @@ -223,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 (;;) { @@ -256,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. */ @@ -269,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 @@ -280,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 @@ -313,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; @@ -366,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)) @@ -400,11 +419,11 @@ move_element (void *array_, size_t count, size_t size, 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 +437,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; @@ -464,7 +483,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; @@ -480,7 +499,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); @@ -520,7 +539,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; @@ -595,8 +614,8 @@ typedef struct stack size is needed (actually O(1) in this case)! */ void -sort (const void *array, size_t count, size_t size, - algo_compare_func *compare, void *aux) +sort (void *array, size_t count, size_t size, + algo_compare_func *compare, const void *aux) { char *const first = array; const size_t max_thresh = MAX_THRESH * size; @@ -706,12 +725,10 @@ sort (const 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 +776,18 @@ sort (const 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, @@ -785,7 +802,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; @@ -832,7 +849,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; @@ -855,7 +872,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; @@ -882,7 +899,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; @@ -918,7 +935,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,7 +951,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; @@ -949,7 +966,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,12 +981,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; @@ -979,9 +996,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; }