X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=src%2Falgorithm.c;h=cfb1ba9fbf533ef55baefbeb06c594eaf9220611;hb=92fb12eb06716d14c05b781f5d9dcde956d77c30;hp=3c1aed90e2be95ed75b8a9033aadd5b1cb5c47f2;hpb=6ccbd384363db2e304ffe8cc51fcd2eac0a5349a;p=pspp diff --git a/src/algorithm.c b/src/algorithm.c index 3c1aed90e2..cfb1ba9fbf 100644 --- a/src/algorithm.c +++ b/src/algorithm.c @@ -14,8 +14,8 @@ 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., 59 Temple Place - Suite 330, Boston, MA - 02111-1307, USA. */ + Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA + 02110-1301, USA. */ /* Copyright (C) 2001 Free Software Foundation, Inc. @@ -32,7 +32,7 @@ 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307, + Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. As a special exception, you may use this file as part of a free software @@ -86,8 +86,8 @@ 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., 59 Temple Place, Suite 330, Boston, MA - 02111-1307 USA. */ + Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA + 02110-1301 USA. */ #include #include "algorithm.h" @@ -96,7 +96,6 @@ #include #include #include "alloc.h" -#include "settings.h" /* Some of the assertions in this file are very expensive. We don't use them by default. */ @@ -117,7 +116,7 @@ find (const void *array, size_t count, size_t size, const void *target, algo_compare_func *compare, void *aux) { - const unsigned char *element = array; + const char *element = array; while (count-- > 0) { @@ -139,7 +138,7 @@ count_equal (const void *array, size_t count, size_t size, const void *element, algo_compare_func *compare, void *aux) { - const unsigned char *first = array; + const char *first = array; size_t equal_cnt = 0; while (count-- > 0) @@ -161,7 +160,7 @@ size_t count_if (const void *array, size_t count, size_t size, algo_predicate_func *predicate, void *aux) { - const unsigned char *first = array; + const char *first = array; size_t nonzero_cnt = 0; while (count-- > 0) @@ -294,7 +293,7 @@ is_partitioned (const void *array, size_t count, size_t size, size_t nonzero_cnt, algo_predicate_func *predicate, void *aux) { - const unsigned char *first = array; + const char *first = array; size_t idx; assert (nonzero_cnt <= count); @@ -307,32 +306,6 @@ is_partitioned (const void *array, size_t count, size_t size, return 1; } -/* A algo_random_func that uses random.h. */ -unsigned -algo_default_random (unsigned max, void *aux UNUSED) -{ - unsigned long r_min = gsl_rng_min (get_rng ()); - return (gsl_rng_get (get_rng ()) - r_min) % max; -} - -/* Randomly reorders ARRAY, which contains COUNT elements of SIZE - bytes each. Uses RANDOM as a source of random data, passing - AUX as the auxiliary data. RANDOM may be null to use a - default random source. */ -void -random_shuffle (void *array_, size_t count, size_t size, - algo_random_func *random, void *aux) -{ - unsigned char *array = array_; - int i; - - if (random == NULL) - random = algo_default_random; - - for (i = 1; i < count; i++) - SWAP (array + i * size, array + random (i + 1, aux) * size, size); -} - /* 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 @@ -342,9 +315,9 @@ copy_if (const void *array, size_t count, size_t size, void *result, algo_predicate_func *predicate, void *aux) { - const unsigned char *input = array; - const unsigned char *last = input + size * count; - unsigned char *output = result; + const char *input = array; + const char *last = input + size * count; + char *output = result; size_t nonzero_cnt = 0; while (input < last) @@ -393,6 +366,36 @@ remove_element (void *array, size_t count, size_t size, remove_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) +{ + assert (array_ != NULL || count == 0); + assert (old_idx < count); + assert (new_idx < count); + + if (old_idx != new_idx) + { + char *array = array_; + char *element = xmalloc (size); + char *new = array + new_idx * size; + char *old = array + old_idx * size; + + memcpy (element, old, size); + if (new < old) + memmove (new + size, new, (old_idx - new_idx) * size); + else + memmove (old, old + size, (new_idx - old_idx) * size); + memcpy (new, element, size); + + free (element); + } +} + /* A predicate and its auxiliary data. */ struct pred_aux { @@ -417,9 +420,9 @@ remove_equal (void *array, size_t count, size_t size, void *element, algo_compare_func *compare, void *aux) { - unsigned char *first = array; - unsigned char *last = first + count * size; - unsigned char *result; + char *first = array; + char *last = first + count * size; + char *result; for (;;) { @@ -485,14 +488,14 @@ binary_search (const void *array, size_t count, size_t size, if (count != 0) { - const unsigned char *first = array; + const char *first = array; int low = 0; int high = count - 1; while (low <= high) { int middle = (low + high) / 2; - const unsigned char *element = first + middle * size; + const char *element = first + middle * size; int cmp = compare (value, element, aux); if (cmp > 0) @@ -519,8 +522,8 @@ lexicographical_compare_3way (const void *array1, size_t count1, size_t size, algo_compare_func *compare, void *aux) { - const unsigned char *first1 = array1; - const unsigned char *first2 = array2; + const char *first1 = array1; + const char *first2 = array2; size_t min_count = count1 < count2 ? count1 : count2; while (min_count > 0) @@ -541,10 +544,6 @@ lexicographical_compare_3way (const void *array1, size_t count1, Engineering a sort function; Jon Bentley and M. Douglas McIlroy; Software - Practice and Experience; Vol. 23 (11), 1249-1265, 1993. */ -#ifdef HAVE_ALLOCA_H -#include -#endif - #include #include #include @@ -764,7 +763,7 @@ int is_sorted (const void *array, size_t count, size_t size, algo_compare_func *compare, void *aux) { - const unsigned char *first = array; + const char *first = array; size_t idx; for (idx = 0; idx + 1 < count; idx++) @@ -788,11 +787,11 @@ size_t set_difference (const void *array1, size_t count1, void *result_, algo_compare_func *compare, void *aux) { - const unsigned char *first1 = array1; - const unsigned char *last1 = first1 + count1 * size; - const unsigned char *first2 = array2; - const unsigned char *last2 = first2 + count2 * size; - unsigned char *result = result_; + const char *first1 = array1; + const char *last1 = first1 + count1 * size; + const char *first2 = array2; + const char *last2 = first2 + count2 * size; + char *result = result_; size_t result_count = 0; while (first1 != last1 && first2 != last2) @@ -835,8 +834,8 @@ void * adjacent_find_equal (const void *array, size_t count, size_t size, algo_compare_func *compare, void *aux) { - const unsigned char *first = array; - const unsigned char *last = first + count * size; + const char *first = array; + const char *last = first + count * size; while (first < last && first + size < last) { @@ -858,15 +857,15 @@ void push_heap (void *array, size_t count, size_t size, algo_compare_func *compare, void *aux) { - unsigned char *first = array; + 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) { - unsigned char *parent = first + (i / 2 - 1) * size; - unsigned char *element = first + (i - 1) * size; + char *parent = first + (i / 2 - 1) * size; + char *element = first + (i - 1) * size; if (compare (parent, element, aux) < 0) SWAP (parent, element, size); else @@ -885,7 +884,7 @@ heapify (void *array, size_t count, size_t size, size_t idx, algo_compare_func *compare, void *aux) { - unsigned char *first = array; + char *first = array; for (;;) { @@ -921,7 +920,7 @@ void pop_heap (void *array, size_t count, size_t size, algo_compare_func *compare, void *aux) { - unsigned char *first = array; + char *first = array; expensive_assert (is_heap (array, count, size, compare, aux)); SWAP (first, first + (count - 1) * size, size); @@ -952,7 +951,7 @@ void sort_heap (void *array, size_t count, size_t size, algo_compare_func *compare, void *aux) { - unsigned char *first = array; + char *first = array; size_t idx; expensive_assert (is_heap (array, count, size, compare, aux)); @@ -972,7 +971,7 @@ int is_heap (const void *array, size_t count, size_t size, algo_compare_func *compare, void *aux) { - const unsigned char *first = array; + const char *first = array; size_t child; for (child = 2; child <= count; child++)