diff options
| -rw-r--r-- | benchmark/tree_bench.c | 105 | ||||
| -rw-r--r-- | include/zix/sorted_array.h | 122 | ||||
| -rw-r--r-- | meson.build | 3 | ||||
| -rw-r--r-- | src/sorted_array.c | 193 | ||||
| -rw-r--r-- | test/sorted_array_test.c | 213 |
5 files changed, 0 insertions, 636 deletions
diff --git a/benchmark/tree_bench.c b/benchmark/tree_bench.c index 9e399ba..4da7228 100644 --- a/benchmark/tree_bench.c +++ b/benchmark/tree_bench.c @@ -35,8 +35,6 @@ ZIX_RESTORE_WARNINGS #include <stdlib.h> #include <time.h> -// #define BENCH_SORTED_ARRAY 1 - static int int_cmp(const void* a, const void* b, const void* ZIX_UNUSED(user_data)) { @@ -210,106 +208,6 @@ bench_zix_btree(size_t n_elems, return EXIT_SUCCESS; } -#ifdef BENCH_SORTED_ARRAY - -static int -int_ptr_cmp(const void* a, const void* b, void* user_data) -{ - const intptr_t ia = *(const intptr_t*)a; - const intptr_t ib = *(const intptr_t*)b; - return ia - ib; -} - -static int -bench_zix_sorted_array(size_t n_elems, - FILE* insert_dat, - FILE* search_dat, - FILE* iter_dat, - FILE* del_dat) -{ - start_test("ZixSortedArray"); - - intptr_t r = 0; - ZixSortedArrayIter ti = NULL; - ZixSortedArray* t = - zix_sorted_array_new(true, int_ptr_cmp, NULL, sizeof(intptr_t)); - - // Insert n_elems elements - struct timespec insert_start = bench_start(); - for (size_t i = 0; i < n_elems; ++i) { - r = unique_rand(i); - int status = zix_sorted_array_insert(t, &r, &ti); - if (status) { - return test_fail("Insert failed\n"); - } - - if (*(intptr_t*)zix_sorted_array_get_data(ti) != r) { - return test_fail("Data corrupt (saw %" PRIdPTR ", expected %zu)\n", - *(intptr_t*)zix_sorted_array_get_data(ti), - r); - } - } - fprintf(insert_dat, "\t%lf", bench_end(&insert_start)); - - // Search for all elements - struct timespec search_start = bench_start(); - for (size_t i = 0; i < n_elems; ++i) { - r = unique_rand(i); - if (zix_sorted_array_find(t, &r, &ti)) { - return test_fail("Find failed\n"); - } - - if (*(intptr_t*)zix_sorted_array_get_data(ti) != r) { - return test_fail("Data corrupt (saw %" PRIdPTR ", expected %zu)\n", - *(intptr_t*)zix_sorted_array_get_data(ti), - r); - } - } - fprintf(search_dat, "\t%lf", bench_end(&search_start)); - - // Iterate over all elements - struct timespec iter_start = bench_start(); - 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 = unique_rand(i); - const intptr_t iter_data = *(intptr_t*)zix_sorted_array_get_data(iter); - if (iter_data < last) { - return test_fail("Iter corrupt (%" PRIdPTR " < %zu)\n", iter_data, last); - } - - last = iter_data; - } - fprintf(iter_dat, "\t%lf", bench_end(&iter_start)); - - // Delete all elements - struct timespec del_start = bench_start(); - for (i = 0; i < n_elems; i++) { - r = unique_rand(i); - ZixSortedArrayIter item; - if (zix_sorted_array_find(t, &r, &item) != ZIX_STATUS_SUCCESS) { - return test_fail("Failed to find item to remove\n"); - } - - if (zix_sorted_array_remove(t, item)) { - return test_fail("Error removing item\n"); - } - } - fprintf(del_dat, "\t%lf", bench_end(&del_start)); - - if (zix_sorted_array_size(t) != 0) { - return test_fail("Array is not empty after removing all items\n"); - } - - zix_sorted_array_free(t); - - return EXIT_SUCCESS; -} - -#endif // BENCH_SORTED_ARRAY - static int bench_glib(size_t n_elems, FILE* insert_dat, @@ -401,9 +299,6 @@ main(int argc, char** argv) fprintf(iter_dat, "%zu", n); fprintf(del_dat, "%zu", n); bench_zix_tree(n, insert_dat, search_dat, iter_dat, del_dat); -#ifdef BENCH_SORTED_ARRAY - bench_zix_sorted_array(n, insert_dat, search_dat, iter_dat, del_dat); -#endif bench_zix_btree(n, insert_dat, search_dat, iter_dat, del_dat); bench_glib(n, insert_dat, search_dat, iter_dat, del_dat); fprintf(insert_dat, "\n"); diff --git a/include/zix/sorted_array.h b/include/zix/sorted_array.h deleted file mode 100644 index 580551e..0000000 --- a/include/zix/sorted_array.h +++ /dev/null @@ -1,122 +0,0 @@ -/* - Copyright 2011-2020 David Robillard <d@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 "zix/common.h" - -#include <stdbool.h> -#include <stddef.h> - -#ifdef __cplusplus -extern "C" { -#endif - -/** - @addtogroup zix - @{ - @name SortedArray - @{ -*/ - -/// A sorted array -typedef struct ZixSortedArrayImpl ZixSortedArray; - -/// An iterator over a ZixSortedArray -typedef void* ZixSortedArrayIter; - -/// Create a new (empty) sorted array -ZIX_API -ZixSortedArray* -zix_sorted_array_new(bool allow_duplicates, - ZixComparator cmp, - void* cmp_data, - size_t elem_size); - -/// Free `a` -ZIX_API -void -zix_sorted_array_free(ZixSortedArray* a); - -/// Return the number of elements in `a` -ZIX_PURE_API -size_t -zix_sorted_array_size(const ZixSortedArray* a); - -/// Insert the element `e` into `a` and point `ai` at the new element -ZIX_API -ZixStatus -zix_sorted_array_insert(ZixSortedArray* a, - const void* e, - ZixSortedArrayIter* ai); - -/// Remove the item pointed at by `ai` from `a` -ZIX_API -ZixStatus -zix_sorted_array_remove(ZixSortedArray* a, ZixSortedArrayIter ai); - -/** - Set `ai` to be the largest element <= `e` in `a`. - - If no such item exists, `ai` is set to NULL. -*/ -ZIX_API -ZixStatus -zix_sorted_array_find(const ZixSortedArray* a, - const void* e, - ZixSortedArrayIter* ai); - -/// Return the element at index `index` -ZIX_PURE_API -void* -zix_sorted_array_index(const ZixSortedArray* a, size_t index); - -/// Return the data associated with the given array item -ZIX_CONST_API -void* -zix_sorted_array_get_data(ZixSortedArrayIter ai); - -/// Return an iterator to the first (smallest) element in `a` -ZIX_PURE_API -ZixSortedArrayIter -zix_sorted_array_begin(ZixSortedArray* a); - -/// Return an iterator the the element one past the last element in `a` -ZIX_PURE_API -ZixSortedArrayIter -zix_sorted_array_end(ZixSortedArray* a); - -/// Return true iff `a` is an iterator to the end of its tree -ZIX_PURE_API -bool -zix_sorted_array_iter_is_end(ZixSortedArray* a, ZixSortedArrayIter i); - -/// Return an iterator that points to the element one past `a` -ZIX_PURE_API -ZixSortedArrayIter -zix_sorted_array_iter_next(ZixSortedArray* a, ZixSortedArrayIter i); - -/** - @} - @} -*/ - -#ifdef __cplusplus -} /* extern "C" */ -#endif - -#endif /* ZIX_SORTED_ARRAY_H */ diff --git a/meson.build b/meson.build index d429513..5651c0c 100644 --- a/meson.build +++ b/meson.build @@ -177,7 +177,6 @@ sources = [ 'src/digest.c', 'src/hash.c', 'src/ring.c', - 'src/sorted_array.c', 'src/strindex.c', 'src/tree.c', ] @@ -216,7 +215,6 @@ headers = [ 'include/zix/hash.h', 'include/zix/ring.h', 'include/zix/sem.h', - 'include/zix/sorted_array.h', 'include/zix/strindex.h', 'include/zix/thread.h', 'include/zix/tree.h', @@ -236,7 +234,6 @@ tests = [ 'hash_test', 'ring_test', 'sem_test', - 'sorted_array_test', 'strindex_test', 'tree_test', ] diff --git a/src/sorted_array.c b/src/sorted_array.c deleted file mode 100644 index eb48fe1..0000000 --- a/src/sorted_array.c +++ /dev/null @@ -1,193 +0,0 @@ -/* - Copyright 2011-2020 David Robillard <d@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 "zix/sorted_array.h" - -#include "zix/common.h" - -#include <assert.h> -#include <stdint.h> -#include <stdlib.h> -#include <string.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 - -ZixSortedArray* -zix_sorted_array_new(bool allow_duplicates, - ZixComparator cmp, - void* cmp_data, - size_t elem_size) -{ - ZixSortedArray* a = (ZixSortedArray*)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; -} - -void -zix_sorted_array_free(ZixSortedArray* a) -{ - free(a->array); - free(a); -} - -size_t -zix_sorted_array_size(const ZixSortedArray* a) -{ - return a->num_elems; -} - -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 = (size_t)((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; -} - -ZixStatus -zix_sorted_array_remove(ZixSortedArray* a, ZixSortedArrayIter ai) -{ - const size_t i = (size_t)((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); -} - -ZixStatus -zix_sorted_array_find(const ZixSortedArray* a, - const void* e, - ZixSortedArrayIter* ai) -{ - intptr_t lower = 0; - intptr_t upper = a->num_elems - 1; - while (upper >= lower) { - const intptr_t i = lower + ((upper - lower) / 2); - void* const elem_i = zix_sorted_array_index_unchecked(a, i); - const int cmp = a->cmp(elem_i, e, a->cmp_data); - - if (cmp == 0) { - *ai = elem_i; - return ZIX_STATUS_SUCCESS; - } - - if (cmp > 0) { - upper = i - 1; - } else { - lower = i + 1; - } - } - - *ai = zix_sorted_array_index_unchecked(a, lower); - return ZIX_STATUS_NOT_FOUND; -} - -void* -zix_sorted_array_get_data(ZixSortedArrayIter ai) -{ - return ai; -} - -ZixSortedArrayIter -zix_sorted_array_begin(ZixSortedArray* a) -{ - return a->array; -} - -ZixSortedArrayIter -zix_sorted_array_end(ZixSortedArray* a) -{ - return (char*)a->array + (a->elem_size * a->num_elems); -} - -bool -zix_sorted_array_iter_is_end(ZixSortedArray* a, ZixSortedArrayIter i) -{ - return i >= zix_sorted_array_end(a); -} - -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 deleted file mode 100644 index cc87619..0000000 --- a/test/sorted_array_test.c +++ /dev/null @@ -1,213 +0,0 @@ -/* - Copyright 2011-2020 David Robillard <d@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 "test_data.h" - -#include "zix/common.h" -#include "zix/sorted_array.h" - -#include <inttypes.h> -#include <stdbool.h> -#include <stdint.h> -#include <stdio.h> -#include <stdlib.h> -#include <time.h> - -static unsigned seed = 1; - -static int -int_cmp(const void* a, const void* b, const void* ZIX_UNUSED(user_data)) -{ - const intptr_t ia = *(const intptr_t*)a; - const intptr_t ib = *(const intptr_t*)b; - - return ia < ib ? -1 : ia > ib ? 1 : 0; -} - -static intptr_t -ith_elem(unsigned test_num, unsigned n_elems, unsigned 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 lcg64(seed + i) % 100u; // Pseudo-random - } -} - -static int -test_fail(void) -{ - return EXIT_FAILURE; -} - -static int -stress(unsigned test_num, unsigned n_elems) -{ - intptr_t r = 0; - ZixSortedArrayIter ti = NULL; - - ZixSortedArray* t = - zix_sorted_array_new(true, int_cmp, NULL, sizeof(intptr_t)); - - // Insert n_elems elements - for (unsigned 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 (%" PRIdPTR " != %" PRIdPTR ")\n", - *(intptr_t*)zix_sorted_array_get_data(ti), - r); - return test_fail(); - } - } - - // Search for all elements - for (unsigned 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 (%" PRIdPTR " != %" PRIdPTR ")\n", - *(intptr_t*)zix_sorted_array_get_data(ti), - r); - return test_fail(); - } - } - - // Iterate over all elements - unsigned 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 " < %" PRIdPTR ")\n", - iter_data, - last); - return test_fail(); - } - last = iter_data; - } - - if (i != zix_sorted_array_size(t)) { - fprintf(stderr, - "Iterated over only %u/%" PRIuPTR " elements\n", - i, - zix_sorted_array_size(t)); - return test_fail(); - } - - if (zix_sorted_array_index(t, zix_sorted_array_size(t))) { - fprintf(stderr, "Got element past end\n"); - return test_fail(); - } - - // Iterate over all elements by index - last = -1; - for (i = 0; i < zix_sorted_array_size(t); ++i) { - r = ith_elem(test_num, n_elems, i); - - const intptr_t iter_data = *(intptr_t*)zix_sorted_array_index(t, i); - if (iter_data < last) { - fprintf(stderr, - "Iter corrupt (%" PRIdPTR " < %" PRIdPTR ")\n", - iter_data, - last); - return test_fail(); - } - - last = iter_data; - } - - // Delete all elements - for (unsigned e = 0; e < n_elems; e++) { - r = ith_elem(test_num, n_elems, e); - - ZixSortedArrayIter item = NULL; - 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 unsigned n_tests = 3; - unsigned n_elems = 0; - - if (argc == 1) { - n_elems = 4096; - } else { - n_elems = (unsigned)strtoul(argv[1], NULL, 10); - if (argc > 2) { - seed = (unsigned)strtoul(argv[2], NULL, 10); - } else { - seed = (unsigned)time(NULL); - } - } - - if (n_elems == 0) { - fprintf(stderr, "USAGE: %s [N_ELEMS]\n", argv[0]); - return 1; - } - - printf( - "Running %u tests with %u elements (seed %u)\n", n_tests, n_elems, seed); - - for (unsigned 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; -} |