Mercurial > hg > dbutils / file comparison

comparison: ucx/array_list.c

ucx/array_list.c

changeset 16
04c9f8d8f03b
parent 11
0aa8cbd7912e
child 21
5ea41679e15d
equal deleted inserted replaced
15:862ab606ee06 16:04c9f8d8f03b
124 ) { 124 ) {
125 // assert pointers 125 // assert pointers
126 assert(array != NULL); 126 assert(array != NULL);
127 assert(size != NULL); 127 assert(size != NULL);
128 assert(capacity != NULL); 128 assert(capacity != NULL);
129 assert(reallocator != NULL); 129
130 // default reallocator
131 if (reallocator == NULL) {
132 reallocator = cx_array_default_reallocator;
133 }
130 134
131 // determine size and capacity 135 // determine size and capacity
132 size_t oldcap; 136 size_t oldcap;
133 size_t oldsize; 137 size_t oldsize;
134 size_t max_size; 138 size_t max_size;
135 if (width == 0 || width == 8*sizeof(size_t)) { 139 if (width == 0 || width == sizeof(size_t)) {
136 oldcap = *(size_t*) capacity; 140 oldcap = *(size_t*) capacity;
137 oldsize = *(size_t*) size; 141 oldsize = *(size_t*) size;
138 max_size = SIZE_MAX; 142 max_size = SIZE_MAX;
139 } else if (width == 16) { 143 } else if (width == sizeof(uint16_t)) {
140 oldcap = *(uint16_t*) capacity; 144 oldcap = *(uint16_t*) capacity;
141 oldsize = *(uint16_t*) size; 145 oldsize = *(uint16_t*) size;
142 max_size = UINT16_MAX; 146 max_size = UINT16_MAX;
143 } else if (width == 8) { 147 } else if (width == sizeof(uint8_t)) {
144 oldcap = *(uint8_t*) capacity; 148 oldcap = *(uint8_t*) capacity;
145 oldsize = *(uint8_t*) size; 149 oldsize = *(uint8_t*) size;
146 max_size = UINT8_MAX; 150 max_size = UINT8_MAX;
147 } 151 }
148 #if CX_WORDSIZE == 64 152 #if CX_WORDSIZE == 64
149 else if (width == 32) { 153 else if (width == sizeof(uint32_t)) {
150 oldcap = *(uint32_t*) capacity; 154 oldcap = *(uint32_t*) capacity;
151 oldsize = *(uint32_t*) size; 155 oldsize = *(uint32_t*) size;
152 max_size = UINT32_MAX; 156 max_size = UINT32_MAX;
153 } 157 }
154 #endif 158 #endif
184 188
185 // store new pointer 189 // store new pointer
186 *array = newmem; 190 *array = newmem;
187 191
188 // store new capacity 192 // store new capacity
189 if (width == 0 || width == 8*sizeof(size_t)) { 193 if (width == 0 || width == sizeof(size_t)) {
190 *(size_t*) capacity = newcap; 194 *(size_t*) capacity = newcap;
191 } else if (width == 16) { 195 } else if (width == sizeof(uint16_t)) {
192 *(uint16_t*) capacity = (uint16_t) newcap; 196 *(uint16_t*) capacity = (uint16_t) newcap;
193 } else if (width == 8) { 197 } else if (width == sizeof(uint8_t)) {
194 *(uint8_t*) capacity = (uint8_t) newcap; 198 *(uint8_t*) capacity = (uint8_t) newcap;
195 } 199 }
196 #if CX_WORDSIZE == 64 200 #if CX_WORDSIZE == 64
197 else if (width == 32) { 201 else if (width == sizeof(uint32_t)) {
198 *(uint32_t*) capacity = (uint32_t) newcap; 202 *(uint32_t*) capacity = (uint32_t) newcap;
199 } 203 }
200 #endif 204 #endif
201 } 205 }
202 206
217 // assert pointers 221 // assert pointers
218 assert(target != NULL); 222 assert(target != NULL);
219 assert(size != NULL); 223 assert(size != NULL);
220 assert(capacity != NULL); 224 assert(capacity != NULL);
221 assert(src != NULL); 225 assert(src != NULL);
222 assert(reallocator != NULL); 226
227 // default reallocator
228 if (reallocator == NULL) {
229 reallocator = cx_array_default_reallocator;
230 }
223 231
224 // determine size and capacity 232 // determine size and capacity
225 size_t oldcap; 233 size_t oldcap;
226 size_t oldsize; 234 size_t oldsize;
227 size_t max_size; 235 size_t max_size;
228 if (width == 0 || width == 8*sizeof(size_t)) { 236 if (width == 0 || width == sizeof(size_t)) {
229 oldcap = *(size_t*) capacity; 237 oldcap = *(size_t*) capacity;
230 oldsize = *(size_t*) size; 238 oldsize = *(size_t*) size;
231 max_size = SIZE_MAX; 239 max_size = SIZE_MAX;
232 } else if (width == 16) { 240 } else if (width == sizeof(uint16_t)) {
233 oldcap = *(uint16_t*) capacity; 241 oldcap = *(uint16_t*) capacity;
234 oldsize = *(uint16_t*) size; 242 oldsize = *(uint16_t*) size;
235 max_size = UINT16_MAX; 243 max_size = UINT16_MAX;
236 } else if (width == 8) { 244 } else if (width == sizeof(uint8_t)) {
237 oldcap = *(uint8_t*) capacity; 245 oldcap = *(uint8_t*) capacity;
238 oldsize = *(uint8_t*) size; 246 oldsize = *(uint8_t*) size;
239 max_size = UINT8_MAX; 247 max_size = UINT8_MAX;
240 } 248 }
241 #if CX_WORDSIZE == 64 249 #if CX_WORDSIZE == 64
242 else if (width == 32) { 250 else if (width == sizeof(uint32_t)) {
243 oldcap = *(uint32_t*) capacity; 251 oldcap = *(uint32_t*) capacity;
244 oldsize = *(uint32_t*) size; 252 oldsize = *(uint32_t*) size;
245 max_size = UINT32_MAX; 253 max_size = UINT32_MAX;
246 } 254 }
247 #endif 255 #endif
301 // note: no overflow check here, b/c we cannot get here w/o allocation 309 // note: no overflow check here, b/c we cannot get here w/o allocation
302 memmove(start, src, elem_count * elem_size); 310 memmove(start, src, elem_count * elem_size);
303 311
304 // if any of size or capacity changed, store them back 312 // if any of size or capacity changed, store them back
305 if (newsize != oldsize || newcap != oldcap) { 313 if (newsize != oldsize || newcap != oldcap) {
306 if (width == 0 || width == 8*sizeof(size_t)) { 314 if (width == 0 || width == sizeof(size_t)) {
307 *(size_t*) capacity = newcap; 315 *(size_t*) capacity = newcap;
308 *(size_t*) size = newsize; 316 *(size_t*) size = newsize;
309 } else if (width == 16) { 317 } else if (width == sizeof(uint16_t)) {
310 *(uint16_t*) capacity = (uint16_t) newcap; 318 *(uint16_t*) capacity = (uint16_t) newcap;
311 *(uint16_t*) size = (uint16_t) newsize; 319 *(uint16_t*) size = (uint16_t) newsize;
312 } else if (width == 8) { 320 } else if (width == sizeof(uint8_t)) {
313 *(uint8_t*) capacity = (uint8_t) newcap; 321 *(uint8_t*) capacity = (uint8_t) newcap;
314 *(uint8_t*) size = (uint8_t) newsize; 322 *(uint8_t*) size = (uint8_t) newsize;
315 } 323 }
316 #if CX_WORDSIZE == 64 324 #if CX_WORDSIZE == 64
317 else if (width == 32) { 325 else if (width == sizeof(uint32_t)) {
318 *(uint32_t*) capacity = (uint32_t) newcap; 326 *(uint32_t*) capacity = (uint32_t) newcap;
319 *(uint32_t*) size = (uint32_t) newsize; 327 *(uint32_t*) size = (uint32_t) newsize;
320 } 328 }
321 #endif 329 #endif
322 } 330 }
339 assert(target != NULL); 347 assert(target != NULL);
340 assert(size != NULL); 348 assert(size != NULL);
341 assert(capacity != NULL); 349 assert(capacity != NULL);
342 assert(cmp_func != NULL); 350 assert(cmp_func != NULL);
343 assert(sorted_data != NULL); 351 assert(sorted_data != NULL);
344 assert(reallocator != NULL); 352
353 // default reallocator
354 if (reallocator == NULL) {
355 reallocator = cx_array_default_reallocator;
356 }
345 357
346 // corner case 358 // corner case
347 if (elem_count == 0) return 0; 359 if (elem_count == 0) return 0;
348 360
349 // overflow check 361 // overflow check
842 } else { 854 } else {
843 return NULL; 855 return NULL;
844 } 856 }
845 } 857 }
846 858
847 static ssize_t cx_arl_find_remove( 859 static size_t cx_arl_find_remove(
848 struct cx_list_s *list, 860 struct cx_list_s *list,
849 const void *elem, 861 const void *elem,
850 bool remove 862 bool remove
851 ) { 863 ) {
864 assert(list != NULL);
852 assert(list->collection.cmpfunc != NULL); 865 assert(list->collection.cmpfunc != NULL);
853 assert(list->collection.size < SIZE_MAX / 2); 866 if (list->collection.size == 0) return 0;
854 char *cur = ((const cx_array_list *) list)->data; 867 char *cur = ((const cx_array_list *) list)->data;
855 868
856 for (ssize_t i = 0; i < (ssize_t) list->collection.size; i++) { 869 // optimize with binary search, when sorted
870 if (list->collection.sorted) {
871 size_t i = cx_array_binary_search(
872 cur,
873 list->collection.size,
874 list->collection.elem_size,
875 elem,
876 list->collection.cmpfunc
877 );
878 if (remove && i < list->collection.size) {
879 cx_arl_remove(list, i, 1, NULL);
880 }
881 return i;
882 }
883
884 // fallback: linear search
885 for (size_t i = 0; i < list->collection.size; i++) {
857 if (0 == list->collection.cmpfunc(elem, cur)) { 886 if (0 == list->collection.cmpfunc(elem, cur)) {
858 if (remove) { 887 if (remove) {
859 if (1 == cx_arl_remove(list, i, 1, NULL)) { 888 cx_arl_remove(list, i, 1, NULL);
860 return i;
861 } else {
862 // should be unreachable
863 return -1; // LCOV_EXCL_LINE
864 }
865 } else {
866 return i;
867 } 889 }
890 return i;
868 } 891 }
869 cur += list->collection.elem_size; 892 cur += list->collection.elem_size;
870 } 893 }
871 894 return list->collection.size;
872 return -1;
873 } 895 }
874 896
875 static void cx_arl_sort(struct cx_list_s *list) { 897 static void cx_arl_sort(struct cx_list_s *list) {
876 assert(list->collection.cmpfunc != NULL); 898 assert(list->collection.cmpfunc != NULL);
877 qsort(((cx_array_list *) list)->data, 899 qsort(((cx_array_list *) list)->data,
999 allocator = cxDefaultAllocator; 1021 allocator = cxDefaultAllocator;
1000 } 1022 }
1001 1023
1002 cx_array_list *list = cxCalloc(allocator, 1, sizeof(cx_array_list)); 1024 cx_array_list *list = cxCalloc(allocator, 1, sizeof(cx_array_list));
1003 if (list == NULL) return NULL; 1025 if (list == NULL) return NULL;
1004 1026 cx_list_init((CxList*)list, &cx_array_list_class,
1005 list->base.cl = &cx_array_list_class; 1027 allocator, comparator, elem_size);
1006 list->base.collection.allocator = allocator;
1007 list->capacity = initial_capacity; 1028 list->capacity = initial_capacity;
1008 1029
1009 if (elem_size > 0) {
1010 list->base.collection.elem_size = elem_size;
1011 list->base.collection.cmpfunc = comparator;
1012 } else {
1013 elem_size = sizeof(void *);
1014 list->base.collection.cmpfunc = comparator == NULL ? cx_cmp_ptr : comparator;
1015 cxListStorePointers((CxList *) list);
1016 }
1017
1018 // allocate the array after the real elem_size is known 1030 // allocate the array after the real elem_size is known
1019 list->data = cxCalloc(allocator, initial_capacity, elem_size); 1031 list->data = cxCalloc(allocator, initial_capacity,
1032 list->base.collection.elem_size);
1020 if (list->data == NULL) { // LCOV_EXCL_START 1033 if (list->data == NULL) { // LCOV_EXCL_START
1021 cxFree(allocator, list); 1034 cxFree(allocator, list);
1022 return NULL; 1035 return NULL;
1023 } // LCOV_EXCL_STOP 1036 } // LCOV_EXCL_STOP
1024 1037

Mercurial Repository: dbutils

mercurial