1 /* 2 Copyright 2011 David Robillard <http://drobilla.net> 3 4 Permission to use, copy, modify, and/or distribute this software for any 5 purpose with or without fee is hereby granted, provided that the above 6 copyright notice and this permission notice appear in all copies. 7 8 THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 9 WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 10 MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 11 ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 12 WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 13 ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 14 OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 15 */ 16 17 #include <assert.h> 18 #include <stdint.h> 19 #include <stdio.h> 20 #include <stdlib.h> 21 #include <string.h> 22 23 #include "zix/common.h" 24 #include "zix/sorted_array.h" 25 26 // #define ZIX_SORTED_ARRAY_DUMP 1 27 28 struct ZixSortedArrayImpl { 29 void* array; 30 ZixComparator cmp; 31 void* cmp_data; 32 size_t elem_size; 33 size_t num_elems; 34 bool allow_duplicates; 35 }; 36 37 #ifdef ZIX_SORTED_ARRAY_DUMP 38 static void 39 zix_sorted_array_print(ZixSortedArray* a) 40 { 41 for (size_t i = 0; i < a->num_elems; ++i) { 42 printf(" %ld", *(intptr_t*)((char*)a->array + (i * a->elem_size))); 43 } 44 printf("\n"); 45 } 46 # define DUMP(a) zix_sorted_array_print(a) 47 #else 48 # define DUMP(a) 49 #endif 50 51 ZIX_API 52 ZixSortedArray* 53 zix_sorted_array_new(bool allow_duplicates, 54 ZixComparator cmp, 55 void* cmp_data, 56 size_t elem_size) 57 { 58 ZixSortedArray* a = (ZixSortedArray*)malloc(sizeof(ZixSortedArray)); 59 a->array = NULL; 60 a->cmp = cmp; 61 a->cmp_data = cmp_data; 62 a->elem_size = elem_size; 63 a->num_elems = 0; 64 a->allow_duplicates = allow_duplicates; 65 return a; 66 } 67 68 ZIX_API 69 void 70 zix_sorted_array_free(ZixSortedArray* a) 71 { 72 free(a->array); 73 free(a); 74 } 75 76 ZIX_API 77 size_t 78 zix_sorted_array_size(ZixSortedArray* a) 79 { 80 return a->num_elems; 81 } 82 83 ZIX_API 84 ZixStatus 85 zix_sorted_array_insert(ZixSortedArray* a, 86 const void* e, 87 ZixSortedArrayIter* ai) 88 { 89 if (a->num_elems == 0) { 90 assert(!a->array); 91 a->array = malloc(a->elem_size); 92 memcpy(a->array, e, a->elem_size); 93 ++a->num_elems; 94 *ai = a->array; 95 return ZIX_STATUS_SUCCESS; 96 } 97 98 zix_sorted_array_find(a, e, ai); 99 assert(*ai); 100 const size_t i = ((char*)*ai - (char*)a->array) / a->elem_size; 101 102 a->array = realloc(a->array, ++a->num_elems * a->elem_size); 103 memmove((char*)a->array + ((i + 1) * a->elem_size), 104 (char*)a->array + (i * a->elem_size), 105 (a->num_elems - i - 1) * a->elem_size); 106 memcpy((char*)a->array + (i * a->elem_size), 107 e, 108 a->elem_size); 109 110 *ai = (char*)a->array + (i * a->elem_size); 111 DUMP(t); 112 return ZIX_STATUS_SUCCESS; 113 } 114 115 ZIX_API 116 ZixStatus 117 zix_sorted_array_remove(ZixSortedArray* a, ZixSortedArrayIter ai) 118 { 119 const size_t i = ((char*)ai - (char*)a->array) / a->elem_size; 120 memmove((char*)a->array + (i * a->elem_size), 121 (char*)a->array + ((i + 1) * a->elem_size), 122 (a->num_elems - i - 1) * a->elem_size); 123 --a->num_elems; 124 DUMP(a); 125 return ZIX_STATUS_SUCCESS; 126 } 127 128 static inline void* 129 zix_sorted_array_index_unchecked(const ZixSortedArray* a, size_t index) 130 { 131 return (char*)a->array + (a->elem_size * index); 132 } 133 134 ZIX_API 135 void* 136 zix_sorted_array_index(const ZixSortedArray* a, size_t index) 137 { 138 if (index >= a->num_elems) { 139 return NULL; 140 } 141 142 return zix_sorted_array_index_unchecked(a, index); 143 } 144 145 ZIX_API 146 ZixStatus 147 zix_sorted_array_find(const ZixSortedArray* a, 148 const void* e, 149 ZixSortedArrayIter* ai) 150 { 151 intptr_t lower = 0; 152 intptr_t upper = a->num_elems - 1; 153 while (upper >= lower) { 154 const intptr_t i = lower + ((upper - lower) / 2); 155 void* const elem_i = zix_sorted_array_index_unchecked(a, i); 156 const int cmp = a->cmp(elem_i, e, a->cmp_data); 157 158 if (cmp == 0) { 159 *ai = elem_i; 160 return ZIX_STATUS_SUCCESS; 161 } else if (cmp > 0) { 162 upper = i - 1; 163 } else { 164 lower = i + 1; 165 } 166 } 167 168 *ai = zix_sorted_array_index_unchecked(a, lower); 169 return ZIX_STATUS_NOT_FOUND; 170 } 171 172 ZIX_API 173 void* 174 zix_sorted_array_get_data(ZixSortedArrayIter ai) 175 { 176 return ai; 177 } 178 179 ZIX_API 180 ZixSortedArrayIter 181 zix_sorted_array_begin(ZixSortedArray* a) 182 { 183 return a->array; 184 } 185 186 ZIX_API 187 ZixSortedArrayIter 188 zix_sorted_array_end(ZixSortedArray* a) 189 { 190 return (char*)a->array + (a->elem_size * a->num_elems); 191 } 192 193 ZIX_API 194 bool 195 zix_sorted_array_iter_is_end(ZixSortedArray* a, ZixSortedArrayIter i) 196 { 197 return i != zix_sorted_array_end(a); 198 } 199 200 ZIX_API 201 ZixSortedArrayIter 202 zix_sorted_array_iter_next(ZixSortedArray* a, ZixSortedArrayIter i) 203 { 204 return (char*)i + a->elem_size; 205 } 206