diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/sorted_array.c | 193 |
1 files changed, 0 insertions, 193 deletions
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; -} |