diff options
| -rw-r--r-- | src/sorted_array.c | 204 | ||||
| -rw-r--r-- | test/sorted_array_test.c | 180 | ||||
| -rw-r--r-- | wscript | 6 | ||||
| -rw-r--r-- | zix/sorted_array.h | 125 |
4 files changed, 513 insertions, 2 deletions
diff --git a/src/sorted_array.c b/src/sorted_array.c new file mode 100644 index 0000000..e41797d --- /dev/null +++ b/src/sorted_array.c @@ -0,0 +1,204 @@ +/* + Copyright 2011 David Robillard <http://drobilla.net> + + Permission to use, copy, modify, and/or distribute this software for any + purpose with or without fee is hereby granted, provided that the above + copyright notice and this permission notice appear in all copies. + + THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. +*/ + +#include <assert.h> +#include <inttypes.h> +#include <stdint.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include "zix/common.h" +#include "zix/sorted_array.h" + +// #define ZIX_SORTED_ARRAY_DUMP 1 + +struct ZixSortedArrayImpl { + void* array; + ZixComparator cmp; + void* cmp_data; + size_t elem_size; + size_t num_elems; + bool allow_duplicates; +}; + +#ifdef ZIX_SORTED_ARRAY_DUMP +static void +zix_sorted_array_print(ZixSortedArray* a) +{ + for (size_t i = 0; i < a->num_elems; ++i) { + printf(" %ld", *(intptr_t*)((char*)a->array + (i * a->elem_size))); + } + printf("\n"); +} +# define DUMP(a) zix_sorted_array_print(a) +#else +# define DUMP(a) +#endif + +ZIX_API +ZixSortedArray* +zix_sorted_array_new(bool allow_duplicates, ZixComparator cmp, void* cmp_data, + size_t elem_size) +{ + ZixSortedArray* a = malloc(sizeof(ZixSortedArray)); + a->array = NULL; + a->cmp = cmp; + a->cmp_data = cmp_data; + a->elem_size = elem_size; + a->num_elems = 0; + a->allow_duplicates = allow_duplicates; + return a; +} + +ZIX_API +void +zix_sorted_array_free(ZixSortedArray* a) +{ + free(a->array); + free(a); +} + +ZIX_API +size_t +zix_sorted_array_size(ZixSortedArray* a) +{ + return a->num_elems; +} + +ZIX_API +ZixStatus +zix_sorted_array_insert(ZixSortedArray* a, const void* e, ZixSortedArrayIter* ai) +{ + if (a->num_elems == 0) { + assert(!a->array); + a->array = malloc(a->elem_size); + memcpy(a->array, e, a->elem_size); + ++a->num_elems; + *ai = a->array; + return ZIX_STATUS_SUCCESS; + } + + zix_sorted_array_find(a, e, ai); + assert(*ai); + const size_t i = ((char*)*ai - (char*)a->array) / a->elem_size; + + a->array = realloc(a->array, ++a->num_elems * a->elem_size); + memmove((char*)a->array + ((i + 1) * a->elem_size), + (char*)a->array + (i * a->elem_size), + (a->num_elems - i - 1) * a->elem_size); + memcpy((char*)a->array + (i * a->elem_size), + e, + a->elem_size); + + *ai = (char*)a->array + (i * a->elem_size); + DUMP(t); + return ZIX_STATUS_SUCCESS; +} + +ZIX_API +ZixStatus +zix_sorted_array_remove(ZixSortedArray* a, ZixSortedArrayIter ai) +{ + const size_t i = ((char*)ai - (char*)a->array) / a->elem_size; + memmove((char*)a->array + (i * a->elem_size), + (char*)a->array + ((i + 1) * a->elem_size), + (a->num_elems - i - 1) * a->elem_size); + --a->num_elems; + DUMP(a); + return ZIX_STATUS_SUCCESS; +} + +static inline void* +zix_sorted_array_index_unchecked(const ZixSortedArray* a, size_t index) +{ + return (char*)a->array + (a->elem_size * index); +} + +void* +zix_sorted_array_index(const ZixSortedArray* a, size_t index) +{ + if (index >= a->num_elems) { + return NULL; + } + + return zix_sorted_array_index_unchecked(a, index); +} + +ZIX_API +ZixStatus +zix_sorted_array_find(const ZixSortedArray* a, const void* e, ZixSortedArrayIter* ai) +{ + if (a->num_elems == 0) { + *ai = NULL; + return ZIX_STATUS_NOT_FOUND; + } + + intptr_t lower = 0; + intptr_t upper = a->num_elems - 1; + while (upper >= lower) { + const size_t i = lower + ((upper - lower) / 2); + void* elem_i = zix_sorted_array_index(a, i); + const int cmp = a->cmp(elem_i, e, a->cmp_data); + + if (cmp == 0) { + *ai = elem_i; + return ZIX_STATUS_SUCCESS; + } else if (cmp > 0) { + upper = i - 1; + } else { + lower = i + 1; + } + } + + *ai = zix_sorted_array_index_unchecked(a, lower); + return ZIX_STATUS_NOT_FOUND; +} + +ZIX_API +void* +zix_sorted_array_get_data(ZixSortedArrayIter ai) +{ + return ai; +} + +ZIX_API +ZixSortedArrayIter +zix_sorted_array_begin(ZixSortedArray* a) +{ + return a->array; +} + +ZIX_API +ZixSortedArrayIter +zix_sorted_array_end(ZixSortedArray* a) +{ + return (char*)a->array + (a->elem_size * a->num_elems); +} + +ZIX_API +bool +zix_sorted_array_iter_is_end(ZixSortedArray* a, ZixSortedArrayIter i) +{ + return i != zix_sorted_array_end(a); +} + +ZIX_API +ZixSortedArrayIter +zix_sorted_array_iter_next(ZixSortedArray* a, ZixSortedArrayIter i) +{ + return (char*)i + a->elem_size; +} diff --git a/test/sorted_array_test.c b/test/sorted_array_test.c new file mode 100644 index 0000000..e8c2fdd --- /dev/null +++ b/test/sorted_array_test.c @@ -0,0 +1,180 @@ +/* + Copyright 2011 David Robillard <http://drobilla.net> + + Permission to use, copy, modify, and/or distribute this software for any + purpose with or without fee is hereby granted, provided that the above + copyright notice and this permission notice appear in all copies. + + THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. +*/ + +#include <inttypes.h> +#include <stdint.h> +#include <stdio.h> +#include <stdlib.h> +#include <limits.h> + +#include <sys/time.h> + +#include "zix/common.h" +#include "zix/sorted_array.h" + +unsigned seed = 1; + +static int +int_cmp(const void* a, const void* b, void* user_data) +{ + const intptr_t ia = *(intptr_t*)a; + const intptr_t ib = *(intptr_t*)b; + return ia - ib; +} + +static int +ith_elem(int test_num, size_t n_elems, int i) +{ + switch (test_num % 3) { + case 0: + return i; // Increasing (worst case) + case 1: + return n_elems - i; // Decreasing (worse case) + case 2: + default: + return rand() % 100; // Random + } +} + +static int +test_fail() +{ + return EXIT_FAILURE; +} + +static int +stress(int test_num, size_t n_elems) +{ + intptr_t r; + ZixSortedArrayIter ti; + + ZixSortedArray* t = zix_sorted_array_new(true, int_cmp, NULL, sizeof(intptr_t)); + + srand(seed); + + // Insert n_elems elements + for (size_t i = 0; i < n_elems; ++i) { + r = ith_elem(test_num, n_elems, i); + int status = zix_sorted_array_insert(t, &r, &ti); + if (status) { + fprintf(stderr, "Insert failed\n"); + return test_fail(); + } + if (*(intptr_t*)zix_sorted_array_get_data(ti) != r) { + fprintf(stderr, "Data corrupt (saw %" PRIdPTR ", expected %zu)\n", + *(intptr_t*)zix_sorted_array_get_data(ti), r); + return test_fail(); + } + } + + srand(seed); + + // Search for all elements + for (size_t i = 0; i < n_elems; ++i) { + r = ith_elem(test_num, n_elems, i); + if (zix_sorted_array_find(t, &r, &ti)) { + fprintf(stderr, "Find failed\n"); + return test_fail(); + } + if (*(intptr_t*)zix_sorted_array_get_data(ti) != r) { + fprintf(stderr, "Data corrupt (saw %" PRIdPTR ", expected %zu)\n", + *(intptr_t*)zix_sorted_array_get_data(ti), r); + return test_fail(); + } + } + + srand(seed); + + // Iterate over all elements + size_t i = 0; + intptr_t last = -1; + for (ZixSortedArrayIter iter = zix_sorted_array_begin(t); + !zix_sorted_array_iter_is_end(t, iter); + iter = zix_sorted_array_iter_next(t, iter), ++i) { + r = ith_elem(test_num, n_elems, i); + const intptr_t iter_data = *(intptr_t*)zix_sorted_array_get_data(iter); + if (iter_data < last) { + fprintf(stderr, "Iter corrupt (%" PRIdPTR " < %zu)\n", + iter_data, last); + return test_fail(); + } + last = iter_data; + } + + srand(seed); + + // Delete all elements + for (size_t i = 0; i < n_elems; i++) { + r = ith_elem(test_num, n_elems, i); + ZixSortedArrayIter item; + if (zix_sorted_array_find(t, &r, &item) != ZIX_STATUS_SUCCESS) { + fprintf(stderr, "Failed to find item to remove\n"); + return test_fail(); + } + if (zix_sorted_array_remove(t, item)) { + fprintf(stderr, "Error removing item\n"); + } + } + + if (zix_sorted_array_size(t) != 0) { + fprintf(stderr, "Array is not empty after removing all items\n"); + return test_fail(); + } + + zix_sorted_array_free(t); + + return EXIT_SUCCESS; +} + +int +main(int argc, char** argv) +{ + const size_t n_tests = 3; + size_t n_elems = 0; + + struct timeval time; + gettimeofday(&time, NULL); + + if (argc == 1) { + n_elems = 4096; + } else { + n_elems = atol(argv[1]); + if (argc > 2) { + seed = atol(argv[2]); + } else { + seed = time.tv_sec + time.tv_usec; + } + } + + if (n_elems == 0) { + fprintf(stderr, "USAGE: %s [N_ELEMS]\n", argv[0]); + return 1; + } + + printf("Running %zu tests with %zu elements (seed %d)", + n_tests, n_elems, seed); + + for (size_t i = 0; i < n_tests; ++i) { + printf("."); + fflush(stdout); + if (stress(i, n_elems)) { + fprintf(stderr, "FAIL: Random seed %u\n", seed); + return test_fail(); + } + } + printf("\n"); + return EXIT_SUCCESS; +} @@ -65,6 +65,7 @@ def build(bld): lib_source = ''' src/tree.c + src/sorted_array.c ''' # Library @@ -89,7 +90,7 @@ def build(bld): obj.cflags = [ '-fprofile-arcs', '-ftest-coverage' ] # Unit test programs - for i in ['tree_test']: + for i in ['tree_test', 'sorted_array_test']: obj = bld(features = 'c cprogram') obj.source = 'test/%s.c' % i obj.includes = ['.'] @@ -138,5 +139,6 @@ def upload_docs(ctx): def test(ctx): autowaf.pre_test(ctx, APPNAME) - autowaf.run_tests(ctx, APPNAME, ['test/tree_test'], dirs=['./src','./test']) + for i in ['tree_test', 'sorted_array_test']: + autowaf.run_tests(ctx, APPNAME, ['test/%s' % i], dirs=['./src','./test']) autowaf.post_test(ctx, APPNAME) diff --git a/zix/sorted_array.h b/zix/sorted_array.h new file mode 100644 index 0000000..355bdf2 --- /dev/null +++ b/zix/sorted_array.h @@ -0,0 +1,125 @@ +/* + Copyright 2011 David Robillard <http://drobilla.net> + + Permission to use, copy, modify, and/or distribute this software for any + purpose with or without fee is hereby granted, provided that the above + copyright notice and this permission notice appear in all copies. + + THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. +*/ + +#ifndef ZIX_SORTED_ARRAY_H +#define ZIX_SORTED_ARRAY_H + +#include <stdbool.h> + +#include "zix/common.h" + +#ifdef __cplusplus +extern "C" { +#endif + +/** + @addtogroup zix + @{ + @name SortedArray + @{ +*/ + +/** + A sorted array. +*/ +typedef struct ZixSortedArrayImpl ZixSortedArray; + +/** + An iterator over a @ref ZixSortedArray. +*/ +typedef void* ZixSortedArrayIter; + +/** + Create a new (empty) sorted array. +*/ +ZixSortedArray* +zix_sorted_array_new(bool allow_duplicates, ZixComparator cmp, void* cmp_data, + size_t elem_size); + +/** + Free @a a. +*/ +void +zix_sorted_array_free(ZixSortedArray* a); + +/** + Return the number of elements in @a a. +*/ +size_t +zix_sorted_array_size(ZixSortedArray* a); + +/** + Insert the element @a e into @a a and point @a ai at the new element. +*/ +ZixStatus +zix_sorted_array_insert(ZixSortedArray* a, const void* e, ZixSortedArrayIter* ai); + +/** + Remove the item pointed at by @a ai from @a a. +*/ +ZixStatus +zix_sorted_array_remove(ZixSortedArray* a, ZixSortedArrayIter ai); + +/** + Set @a ai to be the largest element <= @a e in @a a. + If no such item exists, @a ai is set to NULL. +*/ +ZixStatus +zix_sorted_array_find(const ZixSortedArray* a, const void* e, ZixSortedArrayIter* ai); + +void* +zix_sorted_array_index(const ZixSortedArray* a, size_t index); + +/** + Return the data associated with the given array item. +*/ +void* +zix_sorted_array_get_data(ZixSortedArrayIter ai); + +/** + Return an iterator to the first (smallest) element in @a a. +*/ +ZixSortedArrayIter +zix_sorted_array_begin(ZixSortedArray* a); + +/** + Return an iterator the the element one past the last element in @a a. +*/ +ZixSortedArrayIter +zix_sorted_array_end(ZixSortedArray* a); + +/** + Return true iff @a a is an iterator to the end of its tree. +*/ +bool +zix_sorted_array_iter_is_end(ZixSortedArray* a, ZixSortedArrayIter i); + +/** + Return an iterator that points to the element one past @a a. +*/ +ZixSortedArrayIter +zix_sorted_array_iter_next(ZixSortedArray* a, ZixSortedArrayIter i); + +/** + @} + @} +*/ + +#ifdef __cplusplus +} /* extern "C" */ +#endif + +#endif /* ZIX_SORTED_ARRAY_H */ |