Mercurial > hg > toolkit / file comparison

comparison: ucx/array_list.c

ucx/array_list.c

changeset 1016
ccde46662db7
parent 943
9b5948aa5b90
equal deleted inserted replaced
1015:b459361d98ad 1016:ccde46662db7
30 #include "cx/compare.h" 30 #include "cx/compare.h"
31 #include <assert.h> 31 #include <assert.h>
32 #include <string.h> 32 #include <string.h>
33 #include <errno.h> 33 #include <errno.h>
34 34
35 // Default array reallocator
36
37 static void *cx_array_default_realloc(
38 void *array,
39 cx_attr_unused size_t old_capacity,
40 size_t new_capacity,
41 size_t elem_size,
42 cx_attr_unused CxArrayReallocator *alloc
43 ) {
44 size_t n;
45 // LCOV_EXCL_START
46 if (cx_szmul(new_capacity, elem_size, &n)) {
47 errno = EOVERFLOW;
48 return NULL;
49 } // LCOV_EXCL_STOP
50 return cxReallocDefault(array, n);
51 }
52
53 CxArrayReallocator cx_array_default_reallocator_impl = {
54 cx_array_default_realloc, NULL, NULL
55 };
56
57 CxArrayReallocator *cx_array_default_reallocator = &cx_array_default_reallocator_impl;
58
59 // Stack-aware array reallocator
60
61 static void *cx_array_advanced_realloc(
62 void *array,
63 size_t old_capacity,
64 size_t new_capacity,
65 size_t elem_size,
66 cx_attr_unused CxArrayReallocator *alloc
67 ) {
68 // check for overflow
69 size_t n;
70 // LCOV_EXCL_START
71 if (cx_szmul(new_capacity, elem_size, &n)) {
72 errno = EOVERFLOW;
73 return NULL;
74 } // LCOV_EXCL_STOP
75
76 // retrieve the pointer to the actual allocator
77 const CxAllocator *al = alloc->allocator;
78
79 // check if the array is still located on the stack
80 void *newmem;
81 if (array == alloc->stack_ptr) {
82 newmem = cxMalloc(al, n);
83 if (newmem != NULL && array != NULL) {
84 memcpy(newmem, array, old_capacity*elem_size);
85 }
86 } else {
87 newmem = cxRealloc(al, array, n);
88 }
89 return newmem;
90 }
91
92 struct cx_array_reallocator_s cx_array_reallocator(
93 const struct cx_allocator_s *allocator,
94 const void *stack_ptr
95 ) {
96 if (allocator == NULL) {
97 allocator = cxDefaultAllocator;
98 }
99 return (struct cx_array_reallocator_s) {
100 cx_array_advanced_realloc,
101 allocator, stack_ptr,
102 };
103 }
104
105 // LOW LEVEL ARRAY LIST FUNCTIONS 35 // LOW LEVEL ARRAY LIST FUNCTIONS
106 36
107 /** 37 /**
108 * Intelligently calculates a new capacity, reserving some more 38 * Intelligently calculates a new capacity, reserving some more
109 * elements than required to prevent too many allocations. 39 * elements than required to prevent too many allocations.
126 else if (cap < 8192) alignment = 512; 56 else if (cap < 8192) alignment = 512;
127 else alignment = 1024; 57 else alignment = 1024;
128 return cap - (cap % alignment) + alignment; 58 return cap - (cap % alignment) + alignment;
129 } 59 }
130 60
131 int cx_array_reserve( 61 int cx_array_init_(const CxAllocator *allocator, CxArray *array, size_t elem_size, size_t capacity) {
132 void **array, 62 memset(array, 0, sizeof(CxArray));
133 void *size, 63 return cx_array_reserve_(allocator, array, elem_size, capacity);
134 void *capacity, 64 }
135 unsigned width, 65
66 void cx_array_init_fixed_(CxArray *array, const void *data, size_t capacity, size_t size) {
67 array->data = (void*) data;
68 array->capacity = capacity;
69 array->size = size;
70 }
71
72 int cx_array_reserve_(const CxAllocator *allocator, CxArray *array, size_t elem_size, size_t capacity) {
73 if (cxReallocateArray(allocator, &array->data, capacity, elem_size)) {
74 return -1; // LCOV_EXCL_LINE
75 }
76 array->capacity = capacity;
77 if (array->size > capacity) {
78 array->size = capacity;
79 }
80 return 0;
81 }
82
83 int cx_array_copy_to_new_(const CxAllocator *allocator, CxArray *array, size_t elem_size, size_t capacity) {
84 CxArray heap_array;
85 if (cx_array_init_(allocator, &heap_array, elem_size, capacity)) {
86 return -1; // LCOV_EXCL_LINE
87 }
88 heap_array.size = array->size;
89 memcpy(heap_array.data, array->data, elem_size * array->size);
90 *array = heap_array;
91 return 0;
92 }
93
94 int cx_array_insert_(const CxAllocator *allocator, CxArray *array,
95 size_t elem_size, size_t index, const void *other, size_t n) {
96 // out of bounds and special case check
97 if (index > array->size) return -1;
98 if (n == 0) return 0;
99
100 // guarantee enough capacity
101 if (array->capacity < array->size + n) {
102 const size_t new_capacity = cx_array_grow_capacity(array->capacity,array->size + n);
103 if (cxReallocateArray(allocator, &array->data, new_capacity, elem_size)) {
104 return -1; // LCOV_EXCL_LINE
105 }
106 array->capacity = new_capacity;
107 }
108
109 // determine insert position
110 char *dst = array->data;
111 dst += index * elem_size;
112
113 // do we need to move some elements?
114 if (index < array->size) {
115 size_t elems_to_move = array->size - index;
116 char *target = dst + n * elem_size;
117 memmove(target, dst, elems_to_move * elem_size);
118 }
119
120 // place the new elements, if any
121 // otherwise, this function just reserved the memory (a.k.a emplace)
122 if (other != NULL) {
123 memcpy(dst, other, n * elem_size);
124 }
125 array->size += n;
126
127 return 0;
128 }
129
130 int cx_array_insert_sorted_s_(
131 const CxAllocator *allocator,
132 CxArray *array,
136 size_t elem_size, 133 size_t elem_size,
137 size_t elem_count, 134 const void *sorted_data,
138 CxArrayReallocator *reallocator 135 size_t n,
136 bool allow_duplicates,
137 cx_compare_func2 cmp_func,
138 void *context
139 ) { 139 ) {
140 // assert pointers 140 // assert pointers
141 assert(allocator != NULL);
141 assert(array != NULL); 142 assert(array != NULL);
142 assert(size != NULL); 143 assert(cmp_func != NULL);
143 assert(capacity != NULL); 144 assert(sorted_data != NULL);
144 145
145 // default reallocator 146 // corner case
146 if (reallocator == NULL) { 147 if (n == 0) return 0;
147 reallocator = cx_array_default_reallocator; 148
148 } 149 // overflow check
149 150 // LCOV_EXCL_START
150 // determine size and capacity 151 if (n > SIZE_MAX - array->size) {
151 size_t oldcap;
152 size_t oldsize;
153 size_t max_size;
154 if (width == 0 || width == sizeof(size_t)) {
155 oldcap = *(size_t*) capacity;
156 oldsize = *(size_t*) size;
157 max_size = SIZE_MAX;
158 } else if (width == sizeof(uint16_t)) {
159 oldcap = *(uint16_t*) capacity;
160 oldsize = *(uint16_t*) size;
161 max_size = UINT16_MAX;
162 } else if (width == sizeof(uint8_t)) {
163 oldcap = *(uint8_t*) capacity;
164 oldsize = *(uint8_t*) size;
165 max_size = UINT8_MAX;
166 }
167 #if CX_WORDSIZE == 64
168 else if (width == sizeof(uint32_t)) {
169 oldcap = *(uint32_t*) capacity;
170 oldsize = *(uint32_t*) size;
171 max_size = UINT32_MAX;
172 }
173 #endif
174 else {
175 errno = EINVAL;
176 return 1;
177 }
178
179 // assert that the array is allocated when it has capacity
180 assert(*array != NULL || oldcap == 0);
181
182 // check for overflow
183 if (elem_count > max_size - oldsize) {
184 errno = EOVERFLOW; 152 errno = EOVERFLOW;
185 return 1; 153 return 1;
186 } 154 }
187
188 // determine new capacity
189 size_t newcap = oldsize + elem_count;
190
191 // reallocate if possible
192 if (newcap > oldcap) {
193 void *newmem = reallocator->realloc(
194 *array, oldcap, newcap, elem_size, reallocator
195 );
196 if (newmem == NULL) {
197 return 1; // LCOV_EXCL_LINE
198 }
199
200 // store new pointer
201 *array = newmem;
202
203 // store new capacity
204 if (width == 0 || width == sizeof(size_t)) {
205 *(size_t*) capacity = newcap;
206 } else if (width == sizeof(uint16_t)) {
207 *(uint16_t*) capacity = (uint16_t) newcap;
208 } else if (width == sizeof(uint8_t)) {
209 *(uint8_t*) capacity = (uint8_t) newcap;
210 }
211 #if CX_WORDSIZE == 64
212 else if (width == sizeof(uint32_t)) {
213 *(uint32_t*) capacity = (uint32_t) newcap;
214 }
215 #endif
216 }
217
218 return 0;
219 }
220
221 int cx_array_copy(
222 void **target,
223 void *size,
224 void *capacity,
225 unsigned width,
226 size_t index,
227 const void *src,
228 size_t elem_size,
229 size_t elem_count,
230 CxArrayReallocator *reallocator
231 ) {
232 // assert pointers
233 assert(target != NULL);
234 assert(size != NULL);
235 assert(capacity != NULL);
236 assert(src != NULL);
237
238 // default reallocator
239 if (reallocator == NULL) {
240 reallocator = cx_array_default_reallocator;
241 }
242
243 // determine size and capacity
244 size_t oldcap;
245 size_t oldsize;
246 size_t max_size;
247 if (width == 0 || width == sizeof(size_t)) {
248 oldcap = *(size_t*) capacity;
249 oldsize = *(size_t*) size;
250 max_size = SIZE_MAX;
251 } else if (width == sizeof(uint16_t)) {
252 oldcap = *(uint16_t*) capacity;
253 oldsize = *(uint16_t*) size;
254 max_size = UINT16_MAX;
255 } else if (width == sizeof(uint8_t)) {
256 oldcap = *(uint8_t*) capacity;
257 oldsize = *(uint8_t*) size;
258 max_size = UINT8_MAX;
259 }
260 #if CX_WORDSIZE == 64
261 else if (width == sizeof(uint32_t)) {
262 oldcap = *(uint32_t*) capacity;
263 oldsize = *(uint32_t*) size;
264 max_size = UINT32_MAX;
265 }
266 #endif
267 else {
268 errno = EINVAL;
269 return 1;
270 }
271
272 // assert that the array is allocated when it has capacity
273 assert(*target != NULL || oldcap == 0);
274
275 // check for overflow
276 if (index > max_size || elem_count > max_size - index) {
277 errno = EOVERFLOW;
278 return 1;
279 }
280
281 // check if resize is required
282 const size_t minsize = index + elem_count;
283 const size_t newsize = oldsize < minsize ? minsize : oldsize;
284
285 // reallocate if necessary
286 const size_t newcap = cx_array_grow_capacity(oldcap, newsize);
287 if (newcap > oldcap) {
288 // check if we need to repair the src pointer
289 uintptr_t targetaddr = (uintptr_t) *target;
290 uintptr_t srcaddr = (uintptr_t) src;
291 bool repairsrc = targetaddr <= srcaddr
292 && srcaddr < targetaddr + oldcap * elem_size;
293
294 // perform reallocation
295 void *newmem = reallocator->realloc(
296 *target, oldcap, newcap, elem_size, reallocator
297 );
298 if (newmem == NULL) {
299 return 1; // LCOV_EXCL_LINE
300 }
301
302 // repair src pointer, if necessary
303 if (repairsrc) {
304 src = ((char *) newmem) + (srcaddr - targetaddr);
305 }
306
307 // store new pointer
308 *target = newmem;
309 }
310
311 // determine target pointer
312 char *start = *target;
313 start += index * elem_size;
314
315 // copy elements and set new size
316 // note: no overflow check here, b/c we cannot get here w/o allocation
317 memmove(start, src, elem_count * elem_size);
318
319 // if any of size or capacity changed, store them back
320 if (newsize != oldsize || newcap != oldcap) {
321 if (width == 0 || width == sizeof(size_t)) {
322 *(size_t*) capacity = newcap;
323 *(size_t*) size = newsize;
324 } else if (width == sizeof(uint16_t)) {
325 *(uint16_t*) capacity = (uint16_t) newcap;
326 *(uint16_t*) size = (uint16_t) newsize;
327 } else if (width == sizeof(uint8_t)) {
328 *(uint8_t*) capacity = (uint8_t) newcap;
329 *(uint8_t*) size = (uint8_t) newsize;
330 }
331 #if CX_WORDSIZE == 64
332 else if (width == sizeof(uint32_t)) {
333 *(uint32_t*) capacity = (uint32_t) newcap;
334 *(uint32_t*) size = (uint32_t) newsize;
335 }
336 #endif
337 }
338
339 // return successfully
340 return 0;
341 }
342
343 static int cx_array_insert_sorted_impl(
344 void **target,
345 size_t *size,
346 size_t *capacity,
347 cx_compare_func cmp_func,
348 const void *sorted_data,
349 size_t elem_size,
350 size_t elem_count,
351 CxArrayReallocator *reallocator,
352 bool allow_duplicates
353 ) {
354 // assert pointers
355 assert(target != NULL);
356 assert(size != NULL);
357 assert(capacity != NULL);
358 assert(cmp_func != NULL);
359 assert(sorted_data != NULL);
360
361 // default reallocator
362 if (reallocator == NULL) {
363 reallocator = cx_array_default_reallocator;
364 }
365
366 // corner case
367 if (elem_count == 0) return 0;
368
369 // overflow check
370 // LCOV_EXCL_START
371 if (elem_count > SIZE_MAX - *size) {
372 errno = EOVERFLOW;
373 return 1;
374 }
375 // LCOV_EXCL_STOP 155 // LCOV_EXCL_STOP
376 156
377 // store some counts 157 // store some counts
378 const size_t old_size = *size; 158 const size_t old_size = array->size;
379 const size_t old_capacity = *capacity; 159 const size_t old_capacity = array->capacity;
380 // the necessary capacity is the worst case assumption, including duplicates 160 // the necessary capacity is the worst case assumption, including duplicates
381 const size_t needed_capacity = cx_array_grow_capacity(old_capacity, old_size + elem_count); 161 const size_t needed_capacity = cx_array_grow_capacity(old_capacity, old_size + n);
382 162
383 // if we need more than we have, try a reallocation 163 // if we need more than we have, try a reallocation
384 if (needed_capacity > old_capacity) { 164 if (needed_capacity > old_capacity) {
385 void *new_mem = reallocator->realloc( 165 if (cxReallocateArray(allocator, &array->data, needed_capacity, elem_size)) {
386 *target, old_capacity, needed_capacity, elem_size, reallocator 166 return -1; // LCOV_EXCL_LINE
387 ); 167 }
388 if (new_mem == NULL) { 168 array->capacity = needed_capacity;
389 // give it up right away, there is no contract
390 // that requires us to insert as much as we can
391 return 1; // LCOV_EXCL_LINE
392 }
393 *target = new_mem;
394 *capacity = needed_capacity;
395 } 169 }
396 170
397 // now we have guaranteed that we can insert everything 171 // now we have guaranteed that we can insert everything
398 size_t new_size = old_size + elem_count; 172 size_t new_size = old_size + n;
399 *size = new_size; 173 array->size = new_size;
400 174
401 // declare the source and destination indices/pointers 175 // declare the source and destination indices/pointers
402 size_t si = 0, di = 0; 176 size_t si = 0, di = 0;
403 const char *src = sorted_data; 177 const char *src = sorted_data;
404 char *dest = *target; 178 char *dest = array->data;
405 179
406 // find the first insertion point 180 // find the first insertion point
407 di = cx_array_binary_search_sup(dest, old_size, elem_size, src, cmp_func); 181 di = cx_array_binary_search_sup_c(dest, old_size, elem_size, src, cmp_func, context);
408 dest += di * elem_size; 182 dest += di * elem_size;
409 183
410 // move the remaining elements in the array completely to the right 184 // move the remaining elements in the array completely to the right
411 // we will call it the "buffer" for parked elements 185 // we will call it the "buffer" for parked elements
412 size_t buf_size = old_size - di; 186 size_t buf_size = old_size - di;
413 size_t bi = new_size - buf_size; 187 size_t bi = new_size - buf_size;
414 char *bptr = ((char *) *target) + bi * elem_size; 188 char *bptr = ((char *) array->data) + bi * elem_size;
415 memmove(bptr, dest, buf_size * elem_size); 189 memmove(bptr, dest, buf_size * elem_size);
416 190
417 // while there are both source and buffered elements left, 191 // while there are both source and buffered elements left,
418 // copy them interleaving 192 // copy them interleaving
419 while (si < elem_count && bi < new_size) { 193 while (si < n && bi < new_size) {
420 // determine how many source elements can be inserted. 194 // determine how many source elements can be inserted.
421 // the first element that shall not be inserted is the smallest element 195 // the first element that shall not be inserted is the smallest element
422 // that is strictly larger than the first buffered element 196 // that is strictly larger than the first buffered element
423 // (located at the index of the infimum plus one). 197 // (located at the index of the infimum plus one).
424 // the infimum is guaranteed to exist: 198 // the infimum is guaranteed to exist:
428 // - when all src elements that are smaller are copied, the second part 202 // - when all src elements that are smaller are copied, the second part
429 // of this loop body will copy the remaining buffer (emptying it) 203 // of this loop body will copy the remaining buffer (emptying it)
430 // Therefore, the buffer can never contain an element that is smaller 204 // Therefore, the buffer can never contain an element that is smaller
431 // than any element in the source and the infimum exists. 205 // than any element in the source and the infimum exists.
432 size_t copy_len, bytes_copied; 206 size_t copy_len, bytes_copied;
433 copy_len = cx_array_binary_search_inf( 207 copy_len = cx_array_binary_search_inf_c(
434 src, elem_count - si, elem_size, bptr, cmp_func 208 src, n - si, elem_size, bptr, cmp_func, context
435 ); 209 );
436 copy_len++; 210 copy_len++;
437 211
438 // copy the source elements 212 // copy the source elements
439 if (copy_len > 0) { 213 if (copy_len > 0) {
448 } else { 222 } else {
449 // first, check the end of the source chunk 223 // first, check the end of the source chunk
450 // for being a duplicate of the bptr 224 // for being a duplicate of the bptr
451 const char *end_of_src = src + (copy_len - 1) * elem_size; 225 const char *end_of_src = src + (copy_len - 1) * elem_size;
452 size_t skip_len = 0; 226 size_t skip_len = 0;
453 while (copy_len > 0 && cmp_func(bptr, end_of_src) == 0) { 227 while (copy_len > 0 && cmp_func(bptr, end_of_src, context) == 0) {
454 end_of_src -= elem_size; 228 end_of_src -= elem_size;
455 skip_len++; 229 skip_len++;
456 copy_len--; 230 copy_len--;
457 } 231 }
458 char *last = dest == *target ? NULL : dest - elem_size; 232 char *last = dest == array->data ? NULL : dest - elem_size;
459 // then iterate through the source chunk 233 // then iterate through the source chunk
460 // and skip all duplicates with the last element in the array 234 // and skip all duplicates with the last element in the array
461 size_t more_skipped = 0; 235 size_t more_skipped = 0;
462 for (unsigned j = 0; j < copy_len; j++) { 236 for (unsigned j = 0; j < copy_len; j++) {
463 if (last != NULL && cmp_func(last, src) == 0) { 237 if (last != NULL && cmp_func(last, src, context) == 0) {
464 // duplicate - skip 238 // duplicate - skip
465 src += elem_size; 239 src += elem_size;
466 si++; 240 si++;
467 more_skipped++; 241 more_skipped++;
468 } else { 242 } else {
477 // skip the previously identified elements as well 251 // skip the previously identified elements as well
478 src += skip_len * elem_size; 252 src += skip_len * elem_size;
479 si += skip_len; 253 si += skip_len;
480 skip_len += more_skipped; 254 skip_len += more_skipped;
481 // reduce the actual size by the number of skipped elements 255 // reduce the actual size by the number of skipped elements
482 *size -= skip_len; 256 array->size -= skip_len;
483 } 257 }
484 } 258 }
485 259
486 // when all source elements are in place, we are done 260 // when all source elements are in place, we are done
487 if (si >= elem_count) break; 261 if (si >= n) break;
488 262
489 // determine how many buffered elements need to be restored 263 // determine how many buffered elements need to be restored
490 copy_len = cx_array_binary_search_sup( 264 copy_len = cx_array_binary_search_sup_c(
491 bptr, 265 bptr,
492 new_size - bi, 266 new_size - bi,
493 elem_size, 267 elem_size,
494 src, 268 src,
495 cmp_func 269 cmp_func,
270 context
496 ); 271 );
497 272
498 // restore the buffered elements 273 // restore the buffered elements
499 bytes_copied = copy_len * elem_size; 274 bytes_copied = copy_len * elem_size;
500 memmove(dest, bptr, bytes_copied); 275 memmove(dest, bptr, bytes_copied);
503 di += copy_len; 278 di += copy_len;
504 bi += copy_len; 279 bi += copy_len;
505 } 280 }
506 281
507 // still source elements left? 282 // still source elements left?
508 if (si < elem_count) { 283 if (si < n) {
509 if (allow_duplicates) { 284 if (allow_duplicates) {
510 // duplicates allowed or nothing inserted yet: simply copy everything 285 // duplicates allowed or nothing inserted yet: simply copy everything
511 memcpy(dest, src, elem_size * (elem_count - si)); 286 memcpy(dest, src, elem_size * (n - si));
512 } else { 287 } else {
513 // we must check the remaining source elements one by one 288 // we must check the remaining source elements one by one
514 // to skip the duplicates. 289 // to skip the duplicates.
515 // Note that no source element can equal the last element in the 290 // Note that no source element can equal the last element in the
516 // destination, because that would have created an insertion point 291 // destination, because that would have created an insertion point
517 // and a buffer, s.t. the above loop already handled the duplicates 292 // and a buffer, s.t. the above loop already handled the duplicates
518 while (si < elem_count) { 293 while (si < n) {
519 // find a chain of elements that can be copied 294 // find a chain of elements that can be copied
520 size_t copy_len = 1, skip_len = 0; 295 size_t copy_len = 1, skip_len = 0;
521 { 296 {
522 const char *left_src = src; 297 const char *left_src = src;
523 while (si + copy_len + skip_len < elem_count) { 298 while (si + copy_len + skip_len < n) {
524 const char *right_src = left_src + elem_size; 299 const char *right_src = left_src + elem_size;
525 int d = cmp_func(left_src, right_src); 300 int d = cmp_func(left_src, right_src, context);
526 if (d < 0) { 301 if (d < 0) {
527 if (skip_len > 0) { 302 if (skip_len > 0) {
528 // new larger element found; 303 // new larger element found;
529 // handle it in the next cycle 304 // handle it in the next cycle
530 break; 305 break;
543 memcpy(dest, src, bytes_copied); 318 memcpy(dest, src, bytes_copied);
544 dest += bytes_copied; 319 dest += bytes_copied;
545 src += bytes_copied + skip_len * elem_size; 320 src += bytes_copied + skip_len * elem_size;
546 si += copy_len + skip_len; 321 si += copy_len + skip_len;
547 di += copy_len; 322 di += copy_len;
548 *size -= skip_len; 323 array->size -= skip_len;
549 } 324 }
550 } 325 }
551 } 326 }
552 327
553 // buffered elements need to be moved when we skipped duplicates 328 // buffered elements need to be moved when we skipped duplicates
554 size_t total_skipped = new_size - *size; 329 size_t total_skipped = new_size - array->size;
555 if (bi < new_size && total_skipped > 0) { 330 if (bi < new_size && total_skipped > 0) {
556 // move the remaining buffer to the end of the array 331 // move the remaining buffer to the end of the array
557 memmove(dest, bptr, elem_size * (new_size - bi)); 332 memmove(dest, bptr, elem_size * (new_size - bi));
558 } 333 }
559 334
560 return 0; 335 return 0;
561 } 336 }
562 337
563 int cx_array_insert_sorted( 338 int cx_array_insert_sorted_(
564 void **target, 339 const CxAllocator *allocator,
565 size_t *size, 340 CxArray *array,
566 size_t *capacity, 341 size_t elem_size,
567 cx_compare_func cmp_func, 342 cx_compare_func cmp_func,
568 const void *sorted_data, 343 const void *sorted_data,
569 size_t elem_size, 344 size_t n,
570 size_t elem_count, 345 bool allow_duplicates
571 CxArrayReallocator *reallocator 346 ) {
572 ) { 347 cx_compare_func_wrapper wrapper = {cmp_func};
573 return cx_array_insert_sorted_impl(target, size, capacity, 348 return cx_array_insert_sorted_s_(allocator, array, elem_size, sorted_data,
574 cmp_func, sorted_data, elem_size, elem_count, reallocator, true); 349 n, allow_duplicates, cx_acmp_wrap, &wrapper);
575 } 350 }
576 351
577 int cx_array_insert_unique( 352 CxIterator cx_array_iterator_(CxArray *array, size_t elem_size) {
578 void **target, 353 return cxIterator(array->data, elem_size, array->size);
579 size_t *size, 354 }
580 size_t *capacity, 355
581 cx_compare_func cmp_func, 356 CxIterator cx_array_iterator_ptr_(CxArray *array) {
582 const void *sorted_data, 357 return cxIteratorPtr(array->data, array->size);
583 size_t elem_size, 358 }
584 size_t elem_count, 359
585 CxArrayReallocator *reallocator 360 void cx_array_free_(const CxAllocator *allocator, CxArray *array) {
586 ) { 361 cxFree(allocator, array->data);
587 return cx_array_insert_sorted_impl(target, size, capacity, 362 array->data = NULL;
588 cmp_func, sorted_data, elem_size, elem_count, reallocator, false); 363 array->size = array->capacity = 0;
589 } 364 }
365
590 366
591 // implementation that finds ANY index 367 // implementation that finds ANY index
592 static size_t cx_array_binary_search_inf_impl( 368 static size_t cx_array_binary_search_inf_impl(
593 const void *arr, 369 const void *arr,
594 size_t size, 370 size_t size,
595 size_t elem_size, 371 size_t elem_size,
596 const void *elem, 372 const void *elem,
597 cx_compare_func cmp_func 373 cx_compare_func2 cmp_func,
374 void *context
598 ) { 375 ) {
599 // special case: empty array 376 // special case: empty array
600 if (size == 0) return 0; 377 if (size == 0) return 0;
601 378
602 // declare a variable that will contain the compare results 379 // declare a variable that will contain the compare results
604 381
605 // cast the array pointer to something we can use offsets with 382 // cast the array pointer to something we can use offsets with
606 const char *array = arr; 383 const char *array = arr;
607 384
608 // check the first array element 385 // check the first array element
609 result = cmp_func(elem, array); 386 result = cmp_func(elem, array, context);
610 if (result < 0) { 387 if (result < 0) {
611 return size; 388 return size;
612 } else if (result == 0) { 389 } else if (result == 0) {
613 return 0; 390 return 0;
614 } 391 }
615 392
616 // special case: there is only one element and that is smaller 393 // special case: there is only one element and that is smaller
617 if (size == 1) return 0; 394 if (size == 1) return 0;
618 395
619 // check the last array element 396 // check the last array element
620 result = cmp_func(elem, array + elem_size * (size - 1)); 397 result = cmp_func(elem, array + elem_size * (size - 1), context);
621 if (result >= 0) { 398 if (result >= 0) {
622 return size - 1; 399 return size - 1;
623 } 400 }
624 401
625 // the element is now guaranteed to be somewhere in the list 402 // the element is now guaranteed to be somewhere in the list
626 // so start the binary search 403 // so start the binary search
627 size_t left_index = 1; 404 size_t left_index = 1;
628 size_t right_index = size - 1; 405 size_t right_index = size - 1;
629 size_t pivot_index; 406 size_t pivot_index = 0;
630 407
631 while (left_index <= right_index) { 408 while (left_index <= right_index) {
632 pivot_index = left_index + (right_index - left_index) / 2; 409 pivot_index = left_index + (right_index - left_index) / 2;
633 const char *arr_elem = array + pivot_index * elem_size; 410 const char *arr_elem = array + pivot_index * elem_size;
634 result = cmp_func(elem, arr_elem); 411 result = cmp_func(elem, arr_elem, context);
635 if (result == 0) { 412 if (result == 0) {
636 // found it! 413 // found it!
637 return pivot_index; 414 return pivot_index;
638 } else if (result < 0) { 415 } else if (result < 0) {
639 // element is smaller than pivot, continue search left 416 // element is smaller than pivot, continue search left
646 423
647 // report the largest upper bound 424 // report the largest upper bound
648 return result < 0 ? (pivot_index - 1) : pivot_index; 425 return result < 0 ? (pivot_index - 1) : pivot_index;
649 } 426 }
650 427
428 size_t cx_array_binary_search_inf_c(
429 const void *arr,
430 size_t size,
431 size_t elem_size,
432 const void *elem,
433 cx_compare_func2 cmp_func,
434 void *context
435 ) {
436 size_t index = cx_array_binary_search_inf_impl(
437 arr, size, elem_size, elem, cmp_func, context);
438 // in case of equality, report the largest index
439 const char *e = ((const char *) arr) + (index + 1) * elem_size;
440 while (index + 1 < size && cmp_func(e, elem, context) == 0) {
441 e += elem_size;
442 index++;
443 }
444 return index;
445 }
446
447 size_t cx_array_binary_search_c(
448 const void *arr,
449 size_t size,
450 size_t elem_size,
451 const void *elem,
452 cx_compare_func2 cmp_func,
453 void *context
454 ) {
455 size_t index = cx_array_binary_search_inf_c(
456 arr, size, elem_size, elem, cmp_func, context
457 );
458 if (index < size && cmp_func(((const char *) arr) + index * elem_size,
459 elem, context) == 0) {
460 return index;
461 } else {
462 return size;
463 }
464 }
465
466 size_t cx_array_binary_search_sup_c(
467 const void *arr,
468 size_t size,
469 size_t elem_size,
470 const void *elem,
471 cx_compare_func2 cmp_func,
472 void *context
473 ) {
474 size_t index = cx_array_binary_search_inf_impl(
475 arr, size, elem_size, elem, cmp_func, context
476 );
477 const char *e = ((const char *) arr) + index * elem_size;
478 if (index == size) {
479 // no infimum means the first element is supremum
480 return 0;
481 } else if (cmp_func(e, elem, context) == 0) {
482 // found an equal element, search the smallest index
483 e -= elem_size; // e now contains the element at index-1
484 while (index > 0 && cmp_func(e, elem, context) == 0) {
485 e -= elem_size;
486 index--;
487 }
488 return index;
489 } else {
490 // we already have the largest index of the infimum (by design)
491 // the next element is the supremum (or there is no supremum)
492 return index + 1;
493 }
494 }
495
651 size_t cx_array_binary_search_inf( 496 size_t cx_array_binary_search_inf(
652 const void *arr, 497 const void *arr,
653 size_t size, 498 size_t size,
654 size_t elem_size, 499 size_t elem_size,
655 const void *elem, 500 const void *elem,
656 cx_compare_func cmp_func 501 cx_compare_func cmp_func
657 ) { 502 ) {
658 size_t index = cx_array_binary_search_inf_impl( 503 cx_compare_func_wrapper wrapper = {cmp_func};
659 arr, size, elem_size, elem, cmp_func); 504 return cx_array_binary_search_inf_c(arr, size, elem_size, elem, cx_acmp_wrap, &wrapper);
660 // in case of equality, report the largest index
661 const char *e = ((const char *) arr) + (index + 1) * elem_size;
662 while (index + 1 < size && cmp_func(e, elem) == 0) {
663 e += elem_size;
664 index++;
665 }
666 return index;
667 } 505 }
668 506
669 size_t cx_array_binary_search( 507 size_t cx_array_binary_search(
670 const void *arr, 508 const void *arr,
671 size_t size, 509 size_t size,
672 size_t elem_size, 510 size_t elem_size,
673 const void *elem, 511 const void *elem,
674 cx_compare_func cmp_func 512 cx_compare_func cmp_func
675 ) { 513 ) {
676 size_t index = cx_array_binary_search_inf( 514 cx_compare_func_wrapper wrapper = {cmp_func};
677 arr, size, elem_size, elem, cmp_func 515 return cx_array_binary_search_c(arr, size, elem_size, elem, cx_acmp_wrap, &wrapper);
678 );
679 if (index < size &&
680 cmp_func(((const char *) arr) + index * elem_size, elem) == 0) {
681 return index;
682 } else {
683 return size;
684 }
685 } 516 }
686 517
687 size_t cx_array_binary_search_sup( 518 size_t cx_array_binary_search_sup(
688 const void *arr, 519 const void *arr,
689 size_t size, 520 size_t size,
690 size_t elem_size, 521 size_t elem_size,
691 const void *elem, 522 const void *elem,
692 cx_compare_func cmp_func 523 cx_compare_func cmp_func
693 ) { 524 ) {
694 size_t index = cx_array_binary_search_inf_impl( 525 cx_compare_func_wrapper wrapper = {cmp_func};
695 arr, size, elem_size, elem, cmp_func 526 return cx_array_binary_search_sup_c(arr, size, elem_size, elem, cx_acmp_wrap, &wrapper);
696 );
697 const char *e = ((const char *) arr) + index * elem_size;
698 if (index == size) {
699 // no infimum means the first element is supremum
700 return 0;
701 } else if (cmp_func(e, elem) == 0) {
702 // found an equal element, search the smallest index
703 e -= elem_size; // e now contains the element at index-1
704 while (index > 0 && cmp_func(e, elem) == 0) {
705 e -= elem_size;
706 index--;
707 }
708 return index;
709 } else {
710 // we already have the largest index of the infimum (by design)
711 // the next element is the supremum (or there is no supremum)
712 return index + 1;
713 }
714 } 527 }
715 528
716 #ifndef CX_ARRAY_SWAP_SBO_SIZE 529 #ifndef CX_ARRAY_SWAP_SBO_SIZE
717 #define CX_ARRAY_SWAP_SBO_SIZE 128 530 #define CX_ARRAY_SWAP_SBO_SIZE 128
718 #endif 531 #endif
761 574
762 typedef struct { 575 typedef struct {
763 struct cx_list_s base; 576 struct cx_list_s base;
764 void *data; 577 void *data;
765 size_t capacity; 578 size_t capacity;
766 CxArrayReallocator reallocator;
767 } cx_array_list; 579 } cx_array_list;
768 580
769 static void cx_arl_destructor(struct cx_list_s *list) { 581 static void cx_arl_destructor(struct cx_list_s *list) {
770 cx_array_list *arl = (cx_array_list *) list; 582 cx_array_list *arl = (cx_array_list *) list;
771 583
792 struct cx_list_s *list, 604 struct cx_list_s *list,
793 size_t index, 605 size_t index,
794 const void *array, 606 const void *array,
795 size_t n 607 size_t n
796 ) { 608 ) {
797 // out of bounds and special case check
798 if (index > list->collection.size || n == 0) return 0;
799
800 // get a correctly typed pointer to the list
801 cx_array_list *arl = (cx_array_list *) list; 609 cx_array_list *arl = (cx_array_list *) list;
802 610 CxArray wrap = {
803 // guarantee enough capacity 611 arl->data, list->collection.size, arl->capacity
804 if (arl->capacity < list->collection.size + n) { 612 };
805 const size_t new_capacity = cx_array_grow_capacity(arl->capacity,list->collection.size + n); 613 if (cx_array_insert_(list->collection.allocator, &wrap,
806 if (cxReallocateArray( 614 list->collection.elem_size, index, array, n)) {
807 list->collection.allocator, 615 return 0;
808 &arl->data, new_capacity, 616 }
809 list->collection.elem_size) 617 arl->data = wrap.data;
810 ) { 618 arl->capacity = wrap.capacity;
811 return 0; // LCOV_EXCL_LINE 619 list->collection.size = wrap.size;
812 } 620 return n;
813 arl->capacity = new_capacity; 621 }
814 } 622
815 623 static size_t cx_arl_insert_sorted_impl(
816 // determine insert position 624 struct cx_list_s *list,
817 char *arl_data = arl->data; 625 const void *sorted_data,
818 char *insert_pos = arl_data + index * list->collection.elem_size; 626 size_t n,
819 627 bool allow_duplicates
820 // do we need to move some elements? 628 ) {
821 if (index < list->collection.size) { 629 cx_array_list *arl = (cx_array_list *) list;
822 size_t elems_to_move = list->collection.size - index; 630 CxArray wrap = {
823 char *target = insert_pos + n * list->collection.elem_size; 631 arl->data, list->collection.size, arl->capacity
824 memmove(target, insert_pos, elems_to_move * list->collection.elem_size); 632 };
825 } 633
826 634 if (cx_array_insert_sorted_s_(
827 // place the new elements, if any 635 list->collection.allocator,
828 if (array != NULL) { 636 &wrap,
829 memcpy(insert_pos, array, n * list->collection.elem_size); 637 list->collection.elem_size,
830 } 638 sorted_data,
831 list->collection.size += n; 639 n,
832 640 allow_duplicates,
641 cx_list_compare_wrapper,
642 list
643 )) {
644 // array list implementation is "all or nothing"
645 return 0; // LCOV_EXCL_LINE
646 }
647 arl->data = wrap.data;
648 arl->capacity = wrap.capacity;
649 list->collection.size = wrap.size;
833 return n; 650 return n;
834 } 651 }
835 652
836 static size_t cx_arl_insert_sorted( 653 static size_t cx_arl_insert_sorted(
837 struct cx_list_s *list, 654 struct cx_list_s *list,
838 const void *sorted_data, 655 const void *sorted_data,
839 size_t n 656 size_t n
840 ) { 657 ) {
841 // get a correctly typed pointer to the list 658 return cx_arl_insert_sorted_impl(list, sorted_data, n, true);
842 cx_array_list *arl = (cx_array_list *) list;
843
844 if (cx_array_insert_sorted(
845 &arl->data,
846 &list->collection.size,
847 &arl->capacity,
848 list->collection.cmpfunc,
849 sorted_data,
850 list->collection.elem_size,
851 n,
852 &arl->reallocator
853 )) {
854 // array list implementation is "all or nothing"
855 return 0; // LCOV_EXCL_LINE
856 } else {
857 return n;
858 }
859 } 659 }
860 660
861 static size_t cx_arl_insert_unique( 661 static size_t cx_arl_insert_unique(
862 struct cx_list_s *list, 662 struct cx_list_s *list,
863 const void *sorted_data, 663 const void *sorted_data,
864 size_t n 664 size_t n
865 ) { 665 ) {
866 // get a correctly typed pointer to the list 666 return cx_arl_insert_sorted_impl(list, sorted_data, n, false);
867 cx_array_list *arl = (cx_array_list *) list;
868
869 if (cx_array_insert_unique(
870 &arl->data,
871 &list->collection.size,
872 &arl->capacity,
873 list->collection.cmpfunc,
874 sorted_data,
875 list->collection.elem_size,
876 n,
877 &arl->reallocator
878 )) {
879 // array list implementation is "all or nothing"
880 return 0; // LCOV_EXCL_LINE
881 } else {
882 return n;
883 }
884 } 667 }
885 668
886 static void *cx_arl_insert_element( 669 static void *cx_arl_insert_element(
887 struct cx_list_s *list, 670 struct cx_list_s *list,
888 size_t index, 671 size_t index,
957 ((char *) arl->data) + index * list->collection.elem_size, 740 ((char *) arl->data) + index * list->collection.elem_size,
958 remove * list->collection.elem_size 741 remove * list->collection.elem_size
959 ); 742 );
960 } 743 }
961 744
745 // calculate how many elements would need to be moved
746 size_t remaining = list->collection.size - index - remove;
747
962 // short-circuit removal of last elements 748 // short-circuit removal of last elements
963 if (index + remove == list->collection.size) { 749 if (remaining == 0) {
964 list->collection.size -= remove; 750 list->collection.size -= remove;
965 return remove; 751 return remove;
966 } 752 }
967 753
968 // just move the elements to the left 754 // just move the elements to the left
969 cx_array_copy( 755 char *first_remaining = arl->data;
970 &arl->data, 756 first_remaining += (index + remove) * list->collection.elem_size;
971 &list->collection.size, 757 char *dst_move = arl->data;
972 &arl->capacity, 758 dst_move += index * list->collection.elem_size;
973 0, 759 memmove(dst_move, first_remaining, remaining * list->collection.elem_size);
974 index,
975 ((char *) arl->data) + (index + remove) * list->collection.elem_size,
976 list->collection.elem_size,
977 list->collection.size - index - remove,
978 &arl->reallocator
979 );
980 760
981 // decrease the size 761 // decrease the size
982 list->collection.size -= remove; 762 list->collection.size -= remove;
983 763
984 return remove; 764 return remove;
1035 struct cx_list_s *list, 815 struct cx_list_s *list,
1036 const void *elem, 816 const void *elem,
1037 bool remove 817 bool remove
1038 ) { 818 ) {
1039 assert(list != NULL); 819 assert(list != NULL);
1040 assert(list->collection.cmpfunc != NULL);
1041 if (list->collection.size == 0) return 0; 820 if (list->collection.size == 0) return 0;
1042 char *cur = ((const cx_array_list *) list)->data; 821 char *cur = ((const cx_array_list *) list)->data;
1043 822
1044 // optimize with binary search, when sorted 823 // optimize with binary search, when sorted
1045 if (list->collection.sorted) { 824 if (list->collection.sorted) {
1046 size_t i = cx_array_binary_search( 825 size_t i = cx_array_binary_search_c(
1047 cur, 826 cur,
1048 list->collection.size, 827 list->collection.size,
1049 list->collection.elem_size, 828 list->collection.elem_size,
1050 elem, 829 elem,
1051 list->collection.cmpfunc 830 cx_list_compare_wrapper,
831 list
1052 ); 832 );
1053 if (remove && i < list->collection.size) { 833 if (remove && i < list->collection.size) {
1054 cx_arl_remove(list, i, 1, NULL); 834 cx_arl_remove(list, i, 1, NULL);
1055 } 835 }
1056 return i; 836 return i;
1057 } 837 }
1058 838
1059 // fallback: linear search 839 // fallback: linear search
1060 for (size_t i = 0; i < list->collection.size; i++) { 840 for (size_t i = 0; i < list->collection.size; i++) {
1061 if (0 == list->collection.cmpfunc(elem, cur)) { 841 if (0 == cx_list_compare_wrapper(elem, cur, list)) {
1062 if (remove) { 842 if (remove) {
1063 cx_arl_remove(list, i, 1, NULL); 843 cx_arl_remove(list, i, 1, NULL);
1064 } 844 }
1065 return i; 845 return i;
1066 } 846 }
1067 cur += list->collection.elem_size; 847 cur += list->collection.elem_size;
1068 } 848 }
1069 return list->collection.size; 849 return list->collection.size;
1070 } 850 }
1071 851
852 // TODO: remove this hack once we have a solution for qsort() / qsort_s()
853 static _Thread_local CxList *cx_hack_for_qsort_list;
854 static int cx_hack_cmp_for_qsort(const void *l, const void *r) {
855 return cx_list_compare_wrapper(l, r, cx_hack_for_qsort_list);
856 }
857
1072 static void cx_arl_sort(struct cx_list_s *list) { 858 static void cx_arl_sort(struct cx_list_s *list) {
1073 assert(list->collection.cmpfunc != NULL); 859 // TODO: think about if we can somehow use qsort()_s
860 cx_hack_for_qsort_list = list;
1074 qsort(((cx_array_list *) list)->data, 861 qsort(((cx_array_list *) list)->data,
1075 list->collection.size, 862 list->collection.size,
1076 list->collection.elem_size, 863 list->collection.elem_size,
1077 list->collection.cmpfunc 864 cx_hack_cmp_for_qsort
1078 ); 865 );
1079 } 866 }
1080 867
1081 static int cx_arl_compare( 868 static int cx_arl_compare(
1082 const struct cx_list_s *list, 869 const struct cx_list_s *list,
1083 const struct cx_list_s *other 870 const struct cx_list_s *other
1084 ) { 871 ) {
1085 assert(list->collection.cmpfunc != NULL);
1086 if (list->collection.size == other->collection.size) { 872 if (list->collection.size == other->collection.size) {
1087 const char *left = ((const cx_array_list *) list)->data; 873 const char *left = ((const cx_array_list *) list)->data;
1088 const char *right = ((const cx_array_list *) other)->data; 874 const char *right = ((const cx_array_list *) other)->data;
1089 for (size_t i = 0; i < list->collection.size; i++) { 875 for (size_t i = 0; i < list->collection.size; i++) {
1090 int d = list->collection.cmpfunc(left, right); 876 int d = cx_list_compare_wrapper(left, right, (void*)list);
1091 if (d != 0) { 877 if (d != 0) {
1092 return d; 878 return d;
1093 } 879 }
1094 left += list->collection.elem_size; 880 left += list->collection.elem_size;
1095 right += other->collection.elem_size; 881 right += other->collection.elem_size;
1198 cx_arl_iterator, 984 cx_arl_iterator,
1199 }; 985 };
1200 986
1201 CxList *cxArrayListCreate( 987 CxList *cxArrayListCreate(
1202 const CxAllocator *allocator, 988 const CxAllocator *allocator,
1203 cx_compare_func comparator,
1204 size_t elem_size, 989 size_t elem_size,
1205 size_t initial_capacity 990 size_t initial_capacity
1206 ) { 991 ) {
1207 if (allocator == NULL) { 992 if (allocator == NULL) {
1208 allocator = cxDefaultAllocator; 993 allocator = cxDefaultAllocator;
1209 } 994 }
1210 995
1211 cx_array_list *list = cxCalloc(allocator, 1, sizeof(cx_array_list)); 996 cx_array_list *list = cxCalloc(allocator, 1, sizeof(cx_array_list));
1212 if (list == NULL) return NULL; 997 if (list == NULL) return NULL;
1213 cx_list_init((CxList*)list, &cx_array_list_class, 998 cx_list_init((CxList*)list, &cx_array_list_class,
1214 allocator, comparator, elem_size); 999 allocator, elem_size);
1215 list->capacity = initial_capacity; 1000 list->capacity = initial_capacity;
1216 1001
1217 // allocate the array after the real elem_size is known 1002 // allocate the array after the real elem_size is known
1218 list->data = cxCalloc(allocator, initial_capacity, 1003 list->data = cxCalloc(allocator, initial_capacity,
1219 list->base.collection.elem_size); 1004 list->base.collection.elem_size);
1220 if (list->data == NULL) { // LCOV_EXCL_START 1005 if (list->data == NULL) { // LCOV_EXCL_START
1221 cxFree(allocator, list); 1006 cxFree(allocator, list);
1222 return NULL; 1007 return NULL;
1223 } // LCOV_EXCL_STOP 1008 } // LCOV_EXCL_STOP
1224 1009
1225 // configure the reallocator
1226 list->reallocator = cx_array_reallocator(allocator, NULL);
1227
1228 return (CxList *) list; 1010 return (CxList *) list;
1229 } 1011 }

Mercurial Repository: toolkit

mercurial