Mercurial > hg > dav / file comparison

comparison: ucx/array_list.c

ucx/array_list.c

branch
dav-2
changeset 891
4d58cbcc9efa
parent 889
42cdbf9bbd49
equal deleted inserted replaced
890:e77ccf1c4bb3 891:4d58cbcc9efa
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE. 26 * POSSIBILITY OF SUCH DAMAGE.
27 */ 27 */
28 28
29 #ifdef WITH_MEMRCHR
30 #define _GNU_SOURCE
31 #endif
32
29 #include "cx/array_list.h" 33 #include "cx/array_list.h"
30 #include "cx/compare.h" 34 #include "cx/compare.h"
31 #include <assert.h> 35 #include <assert.h>
32 #include <string.h> 36 #include <string.h>
33 #include <errno.h> 37 #include <errno.h>
34 38
35 // Default array reallocator 39 // LOW LEVEL ARRAY LIST FUNCTIONS
36 40
37 static void *cx_array_default_realloc( 41 /**
38 void *array, 42 * Intelligently calculates a new capacity, reserving some more
39 cx_attr_unused size_t old_capacity, 43 * elements than required to prevent too many allocations.
40 size_t new_capacity, 44 *
45 * @param current_capacity the current capacity of the array
46 * @param needed_capacity the required capacity of the array
47 * @return the new capacity
48 */
49 static size_t cx_array_grow_capacity(
50 size_t current_capacity,
51 size_t needed_capacity
52 ) {
53 if (current_capacity >= needed_capacity) {
54 return current_capacity;
55 }
56 size_t cap = needed_capacity;
57 size_t alignment;
58 if (cap < 128) alignment = 16;
59 else if (cap < 1024) alignment = 64;
60 else if (cap < 8192) alignment = 512;
61 else alignment = 1024;
62 return cap - (cap % alignment) + alignment;
63 }
64
65 int cx_array_init_(const CxAllocator *allocator, CxArray *array, size_t elem_size, size_t capacity) {
66 memset(array, 0, sizeof(CxArray));
67 return cx_array_reserve_(allocator, array, elem_size, capacity);
68 }
69
70 void cx_array_init_fixed_(CxArray *array, const void *data, size_t capacity, size_t size) {
71 array->data = (void*) data;
72 array->capacity = capacity;
73 array->size = size;
74 }
75
76 int cx_array_reserve_(const CxAllocator *allocator, CxArray *array, size_t elem_size, size_t capacity) {
77 if (cxReallocateArray(allocator, &array->data, capacity, elem_size)) {
78 return -1; // LCOV_EXCL_LINE
79 }
80 array->capacity = capacity;
81 if (array->size > capacity) {
82 array->size = capacity;
83 }
84 return 0;
85 }
86
87 int cx_array_copy_to_new_(const CxAllocator *allocator, CxArray *array, size_t elem_size, size_t capacity) {
88 CxArray heap_array;
89 if (cx_array_init_(allocator, &heap_array, elem_size, capacity)) {
90 return -1; // LCOV_EXCL_LINE
91 }
92 heap_array.size = array->size;
93 memcpy(heap_array.data, array->data, elem_size * array->size);
94 *array = heap_array;
95 return 0;
96 }
97
98 int cx_array_insert_(const CxAllocator *allocator, CxArray *array,
99 size_t elem_size, size_t index, const void *other, size_t n) {
100 // out of bounds and special case check
101 if (index > array->size) return -1;
102 if (n == 0) return 0;
103
104 // guarantee enough capacity
105 if (array->capacity < array->size + n) {
106 const size_t new_capacity = cx_array_grow_capacity(array->capacity,array->size + n);
107 if (cxReallocateArray(allocator, &array->data, new_capacity, elem_size)) {
108 return -1; // LCOV_EXCL_LINE
109 }
110 array->capacity = new_capacity;
111 }
112
113 // determine insert position
114 char *dst = array->data;
115 dst += index * elem_size;
116
117 // do we need to move some elements?
118 if (index < array->size) {
119 size_t elems_to_move = array->size - index;
120 char *target = dst + n * elem_size;
121 memmove(target, dst, elems_to_move * elem_size);
122 }
123
124 // place the new elements, if any
125 // otherwise, this function just reserved the memory (a.k.a emplace)
126 if (other != NULL) {
127 memcpy(dst, other, n * elem_size);
128 }
129 array->size += n;
130
131 return 0;
132 }
133
134 int cx_array_insert_sorted_c_(
135 const CxAllocator *allocator,
136 CxArray *array,
41 size_t elem_size, 137 size_t elem_size,
42 cx_attr_unused CxArrayReallocator *alloc 138 const void *sorted_data,
43 ) { 139 size_t n,
44 size_t n; 140 cx_compare_func2 cmp_func,
45 if (cx_szmul(new_capacity, elem_size, &n)) { 141 void *context,
46 errno = EOVERFLOW; 142 bool allow_duplicates
47 return NULL;
48 }
49 return cxReallocDefault(array, n);
50 }
51
52 CxArrayReallocator cx_array_default_reallocator_impl = {
53 cx_array_default_realloc, NULL, NULL
54 };
55
56 CxArrayReallocator *cx_array_default_reallocator = &cx_array_default_reallocator_impl;
57
58 // Stack-aware array reallocator
59
60 static void *cx_array_advanced_realloc(
61 void *array,
62 size_t old_capacity,
63 size_t new_capacity,
64 size_t elem_size,
65 cx_attr_unused CxArrayReallocator *alloc
66 ) {
67 // check for overflow
68 size_t n;
69 if (cx_szmul(new_capacity, elem_size, &n)) {
70 errno = EOVERFLOW;
71 return NULL;
72 }
73
74 // retrieve the pointer to the actual allocator
75 const CxAllocator *al = alloc->allocator;
76
77 // check if the array is still located on the stack
78 void *newmem;
79 if (array == alloc->stack_ptr) {
80 newmem = cxMalloc(al, n);
81 if (newmem != NULL && array != NULL) {
82 memcpy(newmem, array, old_capacity*elem_size);
83 }
84 } else {
85 newmem = cxRealloc(al, array, n);
86 }
87 return newmem;
88 }
89
90 struct cx_array_reallocator_s cx_array_reallocator(
91 const struct cx_allocator_s *allocator,
92 const void *stack_ptr
93 ) {
94 if (allocator == NULL) {
95 allocator = cxDefaultAllocator;
96 }
97 return (struct cx_array_reallocator_s) {
98 cx_array_advanced_realloc,
99 allocator, stack_ptr,
100 };
101 }
102
103 // LOW LEVEL ARRAY LIST FUNCTIONS
104
105 /**
106 * Increases the capacity until it is a multiple of a some alignment or reaches the maximum.
107 *
108 * @param cap the required capacity (must not be larger than @p max)
109 * @param alignment the alignment
110 * @param max the maximum capacity
111 * @return the aligned capacity
112 */
113 static size_t cx_array_align_capacity(
114 size_t cap,
115 size_t alignment,
116 size_t max
117 ) {
118 if (cap > max - alignment) {
119 return cap;
120 } else {
121 return cap - (cap % alignment) + alignment;
122 }
123 }
124
125 int cx_array_reserve(
126 void **array,
127 void *size,
128 void *capacity,
129 unsigned width,
130 size_t elem_size,
131 size_t elem_count,
132 CxArrayReallocator *reallocator
133 ) { 143 ) {
134 // assert pointers 144 // assert pointers
145 assert(allocator != NULL);
135 assert(array != NULL); 146 assert(array != NULL);
136 assert(size != NULL); 147 assert(cmp_func != NULL);
137 assert(capacity != NULL); 148 assert(sorted_data != NULL);
138 149
139 // default reallocator 150 // corner case
140 if (reallocator == NULL) { 151 if (n == 0) return 0;
141 reallocator = cx_array_default_reallocator; 152
142 } 153 // overflow check
143 154 // LCOV_EXCL_START
144 // determine size and capacity 155 if (n > SIZE_MAX - array->size) {
145 size_t oldcap;
146 size_t oldsize;
147 size_t max_size;
148 if (width == 0 || width == sizeof(size_t)) {
149 oldcap = *(size_t*) capacity;
150 oldsize = *(size_t*) size;
151 max_size = SIZE_MAX;
152 } else if (width == sizeof(uint16_t)) {
153 oldcap = *(uint16_t*) capacity;
154 oldsize = *(uint16_t*) size;
155 max_size = UINT16_MAX;
156 } else if (width == sizeof(uint8_t)) {
157 oldcap = *(uint8_t*) capacity;
158 oldsize = *(uint8_t*) size;
159 max_size = UINT8_MAX;
160 }
161 #if CX_WORDSIZE == 64
162 else if (width == sizeof(uint32_t)) {
163 oldcap = *(uint32_t*) capacity;
164 oldsize = *(uint32_t*) size;
165 max_size = UINT32_MAX;
166 }
167 #endif
168 else {
169 errno = EINVAL;
170 return 1;
171 }
172
173 // assert that the array is allocated when it has capacity
174 assert(*array != NULL || oldcap == 0);
175
176 // check for overflow
177 if (elem_count > max_size - oldsize) {
178 errno = EOVERFLOW; 156 errno = EOVERFLOW;
179 return 1; 157 return 1;
180 } 158 }
181 159 // LCOV_EXCL_STOP
182 // determine new capacity
183 size_t newcap = oldsize + elem_count;
184
185 // reallocate if possible
186 if (newcap > oldcap) {
187 // calculate new capacity (next number divisible by 16)
188 newcap = cx_array_align_capacity(newcap, 16, max_size);
189
190 // perform reallocation
191 void *newmem = reallocator->realloc(
192 *array, oldcap, newcap, elem_size, reallocator
193 );
194 if (newmem == NULL) {
195 return 1; // LCOV_EXCL_LINE
196 }
197
198 // store new pointer
199 *array = newmem;
200
201 // store new capacity
202 if (width == 0 || width == sizeof(size_t)) {
203 *(size_t*) capacity = newcap;
204 } else if (width == sizeof(uint16_t)) {
205 *(uint16_t*) capacity = (uint16_t) newcap;
206 } else if (width == sizeof(uint8_t)) {
207 *(uint8_t*) capacity = (uint8_t) newcap;
208 }
209 #if CX_WORDSIZE == 64
210 else if (width == sizeof(uint32_t)) {
211 *(uint32_t*) capacity = (uint32_t) newcap;
212 }
213 #endif
214 }
215
216 return 0;
217 }
218
219 int cx_array_copy(
220 void **target,
221 void *size,
222 void *capacity,
223 unsigned width,
224 size_t index,
225 const void *src,
226 size_t elem_size,
227 size_t elem_count,
228 CxArrayReallocator *reallocator
229 ) {
230 // assert pointers
231 assert(target != NULL);
232 assert(size != NULL);
233 assert(capacity != NULL);
234 assert(src != NULL);
235
236 // default reallocator
237 if (reallocator == NULL) {
238 reallocator = cx_array_default_reallocator;
239 }
240
241 // determine size and capacity
242 size_t oldcap;
243 size_t oldsize;
244 size_t max_size;
245 if (width == 0 || width == sizeof(size_t)) {
246 oldcap = *(size_t*) capacity;
247 oldsize = *(size_t*) size;
248 max_size = SIZE_MAX;
249 } else if (width == sizeof(uint16_t)) {
250 oldcap = *(uint16_t*) capacity;
251 oldsize = *(uint16_t*) size;
252 max_size = UINT16_MAX;
253 } else if (width == sizeof(uint8_t)) {
254 oldcap = *(uint8_t*) capacity;
255 oldsize = *(uint8_t*) size;
256 max_size = UINT8_MAX;
257 }
258 #if CX_WORDSIZE == 64
259 else if (width == sizeof(uint32_t)) {
260 oldcap = *(uint32_t*) capacity;
261 oldsize = *(uint32_t*) size;
262 max_size = UINT32_MAX;
263 }
264 #endif
265 else {
266 errno = EINVAL;
267 return 1;
268 }
269
270 // assert that the array is allocated when it has capacity
271 assert(*target != NULL || oldcap == 0);
272
273 // check for overflow
274 if (index > max_size || elem_count > max_size - index) {
275 errno = EOVERFLOW;
276 return 1;
277 }
278
279 // check if resize is required
280 size_t minsize = index + elem_count;
281 size_t newsize = oldsize < minsize ? minsize : oldsize;
282
283 // reallocate if possible
284 size_t newcap = oldcap;
285 if (newsize > oldcap) {
286 // check, if we need to repair the src pointer
287 uintptr_t targetaddr = (uintptr_t) *target;
288 uintptr_t srcaddr = (uintptr_t) src;
289 bool repairsrc = targetaddr <= srcaddr
290 && srcaddr < targetaddr + oldcap * elem_size;
291
292 // calculate new capacity (next number divisible by 16)
293 newcap = cx_array_align_capacity(newsize, 16, max_size);
294 assert(newcap > newsize);
295
296 // perform reallocation
297 void *newmem = reallocator->realloc(
298 *target, oldcap, newcap, elem_size, reallocator
299 );
300 if (newmem == NULL) {
301 return 1; // LCOV_EXCL_LINE
302 }
303
304 // repair src pointer, if necessary
305 if (repairsrc) {
306 src = ((char *) newmem) + (srcaddr - targetaddr);
307 }
308
309 // store new pointer
310 *target = newmem;
311 }
312
313 // determine target pointer
314 char *start = *target;
315 start += index * elem_size;
316
317 // copy elements and set new size
318 // note: no overflow check here, b/c we cannot get here w/o allocation
319 memmove(start, src, elem_count * elem_size);
320
321 // if any of size or capacity changed, store them back
322 if (newsize != oldsize || newcap != oldcap) {
323 if (width == 0 || width == sizeof(size_t)) {
324 *(size_t*) capacity = newcap;
325 *(size_t*) size = newsize;
326 } else if (width == sizeof(uint16_t)) {
327 *(uint16_t*) capacity = (uint16_t) newcap;
328 *(uint16_t*) size = (uint16_t) newsize;
329 } else if (width == sizeof(uint8_t)) {
330 *(uint8_t*) capacity = (uint8_t) newcap;
331 *(uint8_t*) size = (uint8_t) newsize;
332 }
333 #if CX_WORDSIZE == 64
334 else if (width == sizeof(uint32_t)) {
335 *(uint32_t*) capacity = (uint32_t) newcap;
336 *(uint32_t*) size = (uint32_t) newsize;
337 }
338 #endif
339 }
340
341 // return successfully
342 return 0;
343 }
344
345 static int cx_array_insert_sorted_impl(
346 void **target,
347 size_t *size,
348 size_t *capacity,
349 cx_compare_func cmp_func,
350 const void *sorted_data,
351 size_t elem_size,
352 size_t elem_count,
353 CxArrayReallocator *reallocator,
354 bool allow_duplicates
355 ) {
356 // assert pointers
357 assert(target != NULL);
358 assert(size != NULL);
359 assert(capacity != NULL);
360 assert(cmp_func != NULL);
361 assert(sorted_data != NULL);
362
363 // default reallocator
364 if (reallocator == NULL) {
365 reallocator = cx_array_default_reallocator;
366 }
367
368 // corner case
369 if (elem_count == 0) return 0;
370
371 // overflow check
372 if (elem_count > SIZE_MAX - *size) {
373 errno = EOVERFLOW;
374 return 1;
375 }
376 160
377 // store some counts 161 // store some counts
378 size_t old_size = *size; 162 const size_t old_size = array->size;
379 size_t old_capacity = *capacity; 163 const size_t old_capacity = array->capacity;
380 // the necessary capacity is the worst case assumption, including duplicates 164 // the necessary capacity is the worst case assumption, including duplicates
381 size_t needed_capacity = old_size + elem_count; 165 const size_t needed_capacity = cx_array_grow_capacity(old_capacity, old_size + n);
382 166
383 // if we need more than we have, try a reallocation 167 // if we need more than we have, try a reallocation
384 if (needed_capacity > old_capacity) { 168 if (needed_capacity > old_capacity) {
385 size_t new_capacity = cx_array_align_capacity(needed_capacity, 16, SIZE_MAX); 169 if (cxReallocateArray(allocator, &array->data, needed_capacity, elem_size)) {
386 void *new_mem = reallocator->realloc( 170 return -1; // LCOV_EXCL_LINE
387 *target, old_capacity, new_capacity, elem_size, reallocator 171 }
388 ); 172 array->capacity = needed_capacity;
389 if (new_mem == NULL) {
390 // give it up right away, there is no contract
391 // that requires us to insert as much as we can
392 return 1; // LCOV_EXCL_LINE
393 }
394 *target = new_mem;
395 *capacity = new_capacity;
396 } 173 }
397 174
398 // now we have guaranteed that we can insert everything 175 // now we have guaranteed that we can insert everything
399 size_t new_size = old_size + elem_count; 176 size_t new_size = old_size + n;
400 *size = new_size; 177 array->size = new_size;
401 178
402 // declare the source and destination indices/pointers 179 // declare the source and destination indices/pointers
403 size_t si = 0, di = 0; 180 size_t si = 0, di = 0;
404 const char *src = sorted_data; 181 const char *src = sorted_data;
405 char *dest = *target; 182 char *dest = array->data;
406 183
407 // find the first insertion point 184 // find the first insertion point
408 di = cx_array_binary_search_sup(dest, old_size, elem_size, src, cmp_func); 185 di = cx_array_binary_search_sup_c(dest, old_size, elem_size, src, cmp_func, context);
409 dest += di * elem_size; 186 dest += di * elem_size;
410 187
411 // move the remaining elements in the array completely to the right 188 // move the remaining elements in the array completely to the right
412 // we will call it the "buffer" for parked elements 189 // we will call it the "buffer" for parked elements
413 size_t buf_size = old_size - di; 190 size_t buf_size = old_size - di;
414 size_t bi = new_size - buf_size; 191 size_t bi = new_size - buf_size;
415 char *bptr = ((char *) *target) + bi * elem_size; 192 char *bptr = ((char *) array->data) + bi * elem_size;
416 memmove(bptr, dest, buf_size * elem_size); 193 memmove(bptr, dest, buf_size * elem_size);
417 194
418 // while there are both source and buffered elements left, 195 // while there are both source and buffered elements left,
419 // copy them interleaving 196 // copy them interleaving
420 while (si < elem_count && bi < new_size) { 197 while (si < n && bi < new_size) {
421 // determine how many source elements can be inserted 198 // determine how many source elements can be inserted.
199 // the first element that shall not be inserted is the smallest element
200 // that is strictly larger than the first buffered element
201 // (located at the index of the infimum plus one).
202 // the infimum is guaranteed to exist:
203 // - if all src elements are larger,
204 // there is no buffer, and this loop is skipped
205 // - if any src element is smaller or equal, the infimum exists
206 // - when all src elements that are smaller are copied, the second part
207 // of this loop body will copy the remaining buffer (emptying it)
208 // Therefore, the buffer can never contain an element that is smaller
209 // than any element in the source and the infimum exists.
422 size_t copy_len, bytes_copied; 210 size_t copy_len, bytes_copied;
423 copy_len = cx_array_binary_search_sup( 211 copy_len = cx_array_binary_search_inf_c(
424 src, 212 src, n - si, elem_size, bptr, cmp_func, context
425 elem_count - si,
426 elem_size,
427 bptr,
428 cmp_func
429 ); 213 );
430 // binary search gives us the smallest index; 214 copy_len++;
431 // we also want to include equal elements here
432 while (si + copy_len < elem_count
433 && cmp_func(bptr, src+copy_len*elem_size) == 0) {
434 copy_len++;
435 }
436 215
437 // copy the source elements 216 // copy the source elements
438 if (copy_len > 0) { 217 if (copy_len > 0) {
439 if (allow_duplicates) { 218 if (allow_duplicates) {
440 // we can copy the entire chunk 219 // we can copy the entire chunk
447 } else { 226 } else {
448 // first, check the end of the source chunk 227 // first, check the end of the source chunk
449 // for being a duplicate of the bptr 228 // for being a duplicate of the bptr
450 const char *end_of_src = src + (copy_len - 1) * elem_size; 229 const char *end_of_src = src + (copy_len - 1) * elem_size;
451 size_t skip_len = 0; 230 size_t skip_len = 0;
452 while (copy_len > 0 && cmp_func(bptr, end_of_src) == 0) { 231 while (copy_len > 0 && cmp_func(bptr, end_of_src, context) == 0) {
453 end_of_src -= elem_size; 232 end_of_src -= elem_size;
454 skip_len++; 233 skip_len++;
455 copy_len--; 234 copy_len--;
456 } 235 }
457 char *last = dest == *target ? NULL : dest - elem_size; 236 char *last = dest == array->data ? NULL : dest - elem_size;
458 // then iterate through the source chunk 237 // then iterate through the source chunk
459 // and skip all duplicates with the last element in the array 238 // and skip all duplicates with the last element in the array
460 size_t more_skipped = 0; 239 size_t more_skipped = 0;
461 for (unsigned j = 0; j < copy_len; j++) { 240 for (unsigned j = 0; j < copy_len; j++) {
462 if (last != NULL && cmp_func(last, src) == 0) { 241 if (last != NULL && cmp_func(last, src, context) == 0) {
463 // duplicate - skip 242 // duplicate - skip
464 src += elem_size; 243 src += elem_size;
465 si++; 244 si++;
466 more_skipped++; 245 more_skipped++;
467 } else { 246 } else {
476 // skip the previously identified elements as well 255 // skip the previously identified elements as well
477 src += skip_len * elem_size; 256 src += skip_len * elem_size;
478 si += skip_len; 257 si += skip_len;
479 skip_len += more_skipped; 258 skip_len += more_skipped;
480 // reduce the actual size by the number of skipped elements 259 // reduce the actual size by the number of skipped elements
481 *size -= skip_len; 260 array->size -= skip_len;
482 } 261 }
483 } 262 }
484 263
485 // when all source elements are in place, we are done 264 // when all source elements are in place, we are done
486 if (si >= elem_count) break; 265 if (si >= n) break;
487 266
488 // determine how many buffered elements need to be restored 267 // determine how many buffered elements need to be restored
489 copy_len = cx_array_binary_search_sup( 268 copy_len = cx_array_binary_search_sup_c(
490 bptr, 269 bptr,
491 new_size - bi, 270 new_size - bi,
492 elem_size, 271 elem_size,
493 src, 272 src,
494 cmp_func 273 cmp_func,
274 context
495 ); 275 );
496 276
497 // restore the buffered elements 277 // restore the buffered elements
498 bytes_copied = copy_len * elem_size; 278 bytes_copied = copy_len * elem_size;
499 memmove(dest, bptr, bytes_copied); 279 memmove(dest, bptr, bytes_copied);
502 di += copy_len; 282 di += copy_len;
503 bi += copy_len; 283 bi += copy_len;
504 } 284 }
505 285
506 // still source elements left? 286 // still source elements left?
507 if (si < elem_count) { 287 if (si < n) {
508 if (allow_duplicates) { 288 if (allow_duplicates) {
509 // duplicates allowed or nothing inserted yet: simply copy everything 289 // duplicates allowed or nothing inserted yet: simply copy everything
510 memcpy(dest, src, elem_size * (elem_count - si)); 290 memcpy(dest, src, elem_size * (n - si));
511 } else { 291 } else {
512 if (dest != *target) { 292 // we must check the remaining source elements one by one
513 // skip all source elements that equal the last element 293 // to skip the duplicates.
514 char *last = dest - elem_size; 294 // Note that no source element can equal the last element in the
515 while (si < elem_count) { 295 // destination, because that would have created an insertion point
516 if (last != NULL && cmp_func(last, src) == 0) { 296 // and a buffer, s.t. the above loop already handled the duplicates
517 src += elem_size; 297 while (si < n) {
518 si++;
519 (*size)--;
520 } else {
521 break;
522 }
523 }
524 }
525 // we must check the elements in the chunk one by one
526 while (si < elem_count) {
527 // find a chain of elements that can be copied 298 // find a chain of elements that can be copied
528 size_t copy_len = 1, skip_len = 0; 299 size_t copy_len = 1, skip_len = 0;
529 { 300 {
530 const char *left_src = src; 301 const char *left_src = src;
531 while (si + copy_len < elem_count) { 302 while (si + copy_len + skip_len < n) {
532 const char *right_src = left_src + elem_size; 303 const char *right_src = left_src + elem_size;
533 int d = cmp_func(left_src, right_src); 304 int d = cmp_func(left_src, right_src, context);
534 if (d < 0) { 305 if (d < 0) {
535 if (skip_len > 0) { 306 if (skip_len > 0) {
536 // new larger element found; 307 // new larger element found;
537 // handle it in the next cycle 308 // handle it in the next cycle
538 break; 309 break;
551 memcpy(dest, src, bytes_copied); 322 memcpy(dest, src, bytes_copied);
552 dest += bytes_copied; 323 dest += bytes_copied;
553 src += bytes_copied + skip_len * elem_size; 324 src += bytes_copied + skip_len * elem_size;
554 si += copy_len + skip_len; 325 si += copy_len + skip_len;
555 di += copy_len; 326 di += copy_len;
556 *size -= skip_len; 327 array->size -= skip_len;
557 } 328 }
558 } 329 }
559 } 330 }
560 331
561 // buffered elements need to be moved when we skipped duplicates 332 // buffered elements need to be moved when we skipped duplicates
562 size_t total_skipped = new_size - *size; 333 size_t total_skipped = new_size - array->size;
563 if (bi < new_size && total_skipped > 0) { 334 if (bi < new_size && total_skipped > 0) {
564 // move the remaining buffer to the end of the array 335 // move the remaining buffer to the end of the array
565 memmove(dest, bptr, elem_size * (new_size - bi)); 336 memmove(dest, bptr, elem_size * (new_size - bi));
566 } 337 }
567 338
568 return 0; 339 return 0;
569 } 340 }
570 341
571 int cx_array_insert_sorted( 342 int cx_array_insert_sorted_(
572 void **target, 343 const CxAllocator *allocator,
573 size_t *size, 344 CxArray *array,
574 size_t *capacity, 345 size_t elem_size,
346 const void *sorted_data,
347 size_t n,
575 cx_compare_func cmp_func, 348 cx_compare_func cmp_func,
576 const void *sorted_data, 349 bool allow_duplicates
577 size_t elem_size, 350 ) {
578 size_t elem_count, 351 cx_compare_func_wrapper wrapper = {cmp_func};
579 CxArrayReallocator *reallocator 352 return cx_array_insert_sorted_c_(allocator, array, elem_size, sorted_data,
580 ) { 353 n, cx_ccmp_wrap, &wrapper, allow_duplicates);
581 return cx_array_insert_sorted_impl(target, size, capacity, 354 }
582 cmp_func, sorted_data, elem_size, elem_count, reallocator, true); 355
583 } 356 #ifndef WITH_QSORT_R
584 357 static thread_local cx_compare_func2 cx_array_fn_for_qsort;
585 int cx_array_insert_unique( 358 static thread_local void *cx_array_context_for_qsort;
586 void **target, 359 static int cx_array_qsort_wrapper(const void *l, const void *r) {
587 size_t *size, 360 return cx_array_fn_for_qsort(l, r, cx_array_context_for_qsort);
588 size_t *capacity, 361 }
589 cx_compare_func cmp_func, 362 #endif
590 const void *sorted_data, 363
591 size_t elem_size, 364 void cx_array_qsort_c(void *array, size_t nmemb, size_t size,
592 size_t elem_count, 365 cx_compare_func2 fn, void *context) {
593 CxArrayReallocator *reallocator 366 #ifdef WITH_QSORT_R
594 ) { 367 qsort_r(array, nmemb, size, fn, context);
595 return cx_array_insert_sorted_impl(target, size, capacity, 368 #else
596 cmp_func, sorted_data, elem_size, elem_count, reallocator, false); 369 cx_array_fn_for_qsort = fn;
597 } 370 cx_array_context_for_qsort = context;
598 371 qsort(array, nmemb, size, cx_array_qsort_wrapper);
599 size_t cx_array_binary_search_inf( 372 #endif
373 }
374
375 void cx_array_sort_(CxArray *array, size_t elem_size,
376 cx_compare_func fn) {
377 qsort(array->data, array->size, elem_size, fn);
378 }
379
380 void cx_array_sort_c_(CxArray *array, size_t elem_size,
381 cx_compare_func2 fn, void *context) {
382 cx_array_qsort_c(array->data, array->size, elem_size, fn, context);
383 }
384
385 CxIterator cx_array_iterator_(CxArray *array, size_t elem_size) {
386 return cxIterator(array->data, elem_size, array->size);
387 }
388
389 CxIterator cx_array_iterator_ptr_(CxArray *array) {
390 return cxIteratorPtr(array->data, array->size);
391 }
392
393 void cx_array_remove_(CxArray *array, size_t elem_size, size_t index, size_t n, bool fast) {
394 if (n == 0) return;
395 if (index >= array->size) return;
396 if (index + n >= array->size) {
397 // only tail elements are removed
398 array->size = index;
399 return;
400 }
401 array->size -= n;
402 size_t remaining = array->size - index;
403 char *dest = ((char*)array->data) + index * elem_size;
404 if (fast) {
405 char *src = dest + remaining * elem_size;
406 if (n == 1 && elem_size <= CX_WORDSIZE/8) {
407 // try to optimize int-sized values
408 // (from likely to unlikely)
409 if (elem_size == sizeof(int32_t)) {
410 *(int32_t*)dest = *(int32_t*)src;
411 return;
412 }
413 #if CX_WORDSIZE == 64
414 if (elem_size == sizeof(int64_t)) {
415 *(int64_t*)dest = *(int64_t*)src;
416 return;
417 }
418 #endif
419 if (elem_size == sizeof(int8_t)) {
420 *(int8_t*)dest = *(int8_t*)src;
421 return;
422 }
423 if (elem_size == sizeof(int16_t)) {
424 *(int16_t*)dest = *(int16_t*)src;
425 return;
426 }
427 // note we cannot optimize the last branch, because
428 // the elem_size could be crazily misaligned
429 }
430 memcpy(dest, src, n * elem_size);
431 } else {
432 char *src = dest + n * elem_size;
433 memmove(dest, src, remaining * elem_size);
434 }
435 }
436
437 void cx_array_free_(const CxAllocator *allocator, CxArray *array) {
438 cxFree(allocator, array->data);
439 array->data = NULL;
440 array->size = array->capacity = 0;
441 }
442
443
444 // implementation that finds ANY index
445 static size_t cx_array_binary_search_inf_impl(
600 const void *arr, 446 const void *arr,
601 size_t size, 447 size_t size,
602 size_t elem_size, 448 size_t elem_size,
603 const void *elem, 449 const void *elem,
604 cx_compare_func cmp_func 450 cx_compare_func2 cmp_func,
451 void *context
605 ) { 452 ) {
606 // special case: empty array 453 // special case: empty array
607 if (size == 0) return 0; 454 if (size == 0) return 0;
608 455
609 // declare a variable that will contain the compare results 456 // declare a variable that will contain the compare results
611 458
612 // cast the array pointer to something we can use offsets with 459 // cast the array pointer to something we can use offsets with
613 const char *array = arr; 460 const char *array = arr;
614 461
615 // check the first array element 462 // check the first array element
616 result = cmp_func(elem, array); 463 result = cmp_func(elem, array, context);
617 if (result < 0) { 464 if (result < 0) {
618 return size; 465 return size;
619 } else if (result == 0) { 466 } else if (result == 0) {
620 return 0; 467 return 0;
621 } 468 }
622 469
623 // special case: there is only one element and that is smaller 470 // special case: there is only one element and that is smaller
624 if (size == 1) return 0; 471 if (size == 1) return 0;
625 472
626 // check the last array element 473 // check the last array element
627 result = cmp_func(elem, array + elem_size * (size - 1)); 474 result = cmp_func(elem, array + elem_size * (size - 1), context);
628 if (result >= 0) { 475 if (result >= 0) {
629 return size - 1; 476 return size - 1;
630 } 477 }
631 478
632 // the element is now guaranteed to be somewhere in the list 479 // the element is now guaranteed to be somewhere in the list
633 // so start the binary search 480 // so start the binary search
634 size_t left_index = 1; 481 size_t left_index = 1;
635 size_t right_index = size - 1; 482 size_t right_index = size - 1;
636 size_t pivot_index; 483 size_t pivot_index = 0;
637 484
638 while (left_index <= right_index) { 485 while (left_index <= right_index) {
639 pivot_index = left_index + (right_index - left_index) / 2; 486 pivot_index = left_index + (right_index - left_index) / 2;
640 const char *arr_elem = array + pivot_index * elem_size; 487 const char *arr_elem = array + pivot_index * elem_size;
641 result = cmp_func(elem, arr_elem); 488 result = cmp_func(elem, arr_elem, context);
642 if (result == 0) { 489 if (result == 0) {
643 // found it! 490 // found it!
644 // check previous elements;
645 // when they are equal, report the smallest index
646 arr_elem -= elem_size;
647 while (pivot_index > 0 && cmp_func(elem, arr_elem) == 0) {
648 pivot_index--;
649 arr_elem -= elem_size;
650 }
651 return pivot_index; 491 return pivot_index;
652 } else if (result < 0) { 492 } else if (result < 0) {
653 // element is smaller than pivot, continue search left 493 // element is smaller than pivot, continue search left
654 right_index = pivot_index - 1; 494 right_index = pivot_index - 1;
655 } else { 495 } else {
660 500
661 // report the largest upper bound 501 // report the largest upper bound
662 return result < 0 ? (pivot_index - 1) : pivot_index; 502 return result < 0 ? (pivot_index - 1) : pivot_index;
663 } 503 }
664 504
505 size_t cx_array_binary_search_inf_c(
506 const void *arr,
507 size_t size,
508 size_t elem_size,
509 const void *elem,
510 cx_compare_func2 cmp_func,
511 void *context
512 ) {
513 size_t index = cx_array_binary_search_inf_impl(
514 arr, size, elem_size, elem, cmp_func, context);
515 // in case of equality, report the largest index
516 const char *e = ((const char *) arr) + (index + 1) * elem_size;
517 while (index + 1 < size && cmp_func(e, elem, context) == 0) {
518 e += elem_size;
519 index++;
520 }
521 return index;
522 }
523
524 size_t cx_array_binary_search_c(
525 const void *arr,
526 size_t size,
527 size_t elem_size,
528 const void *elem,
529 cx_compare_func2 cmp_func,
530 void *context
531 ) {
532 size_t index = cx_array_binary_search_inf_c(
533 arr, size, elem_size, elem, cmp_func, context
534 );
535 if (index < size && cmp_func(((const char *) arr) + index * elem_size,
536 elem, context) == 0) {
537 return index;
538 } else {
539 return size;
540 }
541 }
542
543 size_t cx_array_binary_search_sup_c(
544 const void *arr,
545 size_t size,
546 size_t elem_size,
547 const void *elem,
548 cx_compare_func2 cmp_func,
549 void *context
550 ) {
551 size_t index = cx_array_binary_search_inf_impl(
552 arr, size, elem_size, elem, cmp_func, context
553 );
554 const char *e = ((const char *) arr) + index * elem_size;
555 if (index == size) {
556 // no infimum means the first element is supremum
557 return 0;
558 } else if (cmp_func(e, elem, context) == 0) {
559 // found an equal element, search the smallest index
560 e -= elem_size; // e now contains the element at index-1
561 while (index > 0 && cmp_func(e, elem, context) == 0) {
562 e -= elem_size;
563 index--;
564 }
565 return index;
566 } else {
567 // we already have the largest index of the infimum (by design)
568 // the next element is the supremum (or there is no supremum)
569 return index + 1;
570 }
571 }
572
573 size_t cx_array_binary_search_inf(
574 const void *arr,
575 size_t size,
576 size_t elem_size,
577 const void *elem,
578 cx_compare_func cmp_func
579 ) {
580 cx_compare_func_wrapper wrapper = {cmp_func};
581 return cx_array_binary_search_inf_c(arr, size, elem_size, elem, cx_ccmp_wrap, &wrapper);
582 }
583
665 size_t cx_array_binary_search( 584 size_t cx_array_binary_search(
666 const void *arr, 585 const void *arr,
667 size_t size, 586 size_t size,
668 size_t elem_size, 587 size_t elem_size,
669 const void *elem, 588 const void *elem,
670 cx_compare_func cmp_func 589 cx_compare_func cmp_func
671 ) { 590 ) {
672 size_t index = cx_array_binary_search_inf( 591 cx_compare_func_wrapper wrapper = {cmp_func};
673 arr, size, elem_size, elem, cmp_func 592 return cx_array_binary_search_c(arr, size, elem_size, elem, cx_ccmp_wrap, &wrapper);
674 );
675 if (index < size &&
676 cmp_func(((const char *) arr) + index * elem_size, elem) == 0) {
677 return index;
678 } else {
679 return size;
680 }
681 } 593 }
682 594
683 size_t cx_array_binary_search_sup( 595 size_t cx_array_binary_search_sup(
684 const void *arr, 596 const void *arr,
685 size_t size, 597 size_t size,
686 size_t elem_size, 598 size_t elem_size,
687 const void *elem, 599 const void *elem,
688 cx_compare_func cmp_func 600 cx_compare_func cmp_func
689 ) { 601 ) {
690 size_t inf = cx_array_binary_search_inf( 602 cx_compare_func_wrapper wrapper = {cmp_func};
691 arr, size, elem_size, elem, cmp_func 603 return cx_array_binary_search_sup_c(arr, size, elem_size, elem, cx_ccmp_wrap, &wrapper);
692 );
693 if (inf == size) {
694 // no infimum means, first element is supremum
695 return 0;
696 } else if (cmp_func(((const char *) arr) + inf * elem_size, elem) == 0) {
697 return inf;
698 } else {
699 return inf + 1;
700 }
701 } 604 }
702 605
703 #ifndef CX_ARRAY_SWAP_SBO_SIZE 606 #ifndef CX_ARRAY_SWAP_SBO_SIZE
704 #define CX_ARRAY_SWAP_SBO_SIZE 128 607 #define CX_ARRAY_SWAP_SBO_SIZE 128
705 #endif 608 #endif
748 651
749 typedef struct { 652 typedef struct {
750 struct cx_list_s base; 653 struct cx_list_s base;
751 void *data; 654 void *data;
752 size_t capacity; 655 size_t capacity;
753 CxArrayReallocator reallocator;
754 } cx_array_list; 656 } cx_array_list;
755 657
756 static void cx_arl_destructor(struct cx_list_s *list) { 658 static void cx_arl_destructor(struct cx_list_s *list) {
757 cx_array_list *arl = (cx_array_list *) list; 659 cx_array_list *arl = (cx_array_list *) list;
758 660
779 struct cx_list_s *list, 681 struct cx_list_s *list,
780 size_t index, 682 size_t index,
781 const void *array, 683 const void *array,
782 size_t n 684 size_t n
783 ) { 685 ) {
784 // out of bounds and special case check
785 if (index > list->collection.size || n == 0) return 0;
786
787 // get a correctly typed pointer to the list
788 cx_array_list *arl = (cx_array_list *) list; 686 cx_array_list *arl = (cx_array_list *) list;
789 687 CxArray wrap = {
790 // guarantee enough capacity 688 arl->data, list->collection.size, arl->capacity
791 if (arl->capacity < list->collection.size + n) { 689 };
792 size_t new_capacity = list->collection.size + n; 690 if (cx_array_insert_(list->collection.allocator, &wrap,
793 new_capacity = cx_array_align_capacity(new_capacity, 16, SIZE_MAX); 691 list->collection.elem_size, index, array, n)) {
794 if (cxReallocateArray( 692 return 0;
795 list->collection.allocator, 693 }
796 &arl->data, new_capacity, 694 arl->data = wrap.data;
797 list->collection.elem_size) 695 arl->capacity = wrap.capacity;
798 ) { 696 list->collection.size = wrap.size;
799 return 0; 697 return n;
800 } 698 }
801 arl->capacity = new_capacity; 699
802 } 700 static size_t cx_arl_insert_sorted_impl(
803 701 struct cx_list_s *list,
804 // determine insert position 702 const void *sorted_data,
805 char *arl_data = arl->data; 703 size_t n,
806 char *insert_pos = arl_data + index * list->collection.elem_size; 704 bool allow_duplicates
807 705 ) {
808 // do we need to move some elements? 706 cx_array_list *arl = (cx_array_list *) list;
809 if (index < list->collection.size) { 707 CxArray wrap = {
810 size_t elems_to_move = list->collection.size - index; 708 arl->data, list->collection.size, arl->capacity
811 char *target = insert_pos + n * list->collection.elem_size; 709 };
812 memmove(target, insert_pos, elems_to_move * list->collection.elem_size); 710
813 } 711 if (cx_array_insert_sorted_c_(
814 712 list->collection.allocator,
815 // place the new elements, if any 713 &wrap,
816 if (array != NULL) { 714 list->collection.elem_size,
817 memcpy(insert_pos, array, n * list->collection.elem_size); 715 sorted_data,
818 } 716 n,
819 list->collection.size += n; 717 cx_list_compare_wrapper,
820 718 list,
719 allow_duplicates
720 )) {
721 // array list implementation is "all or nothing"
722 return 0; // LCOV_EXCL_LINE
723 }
724 arl->data = wrap.data;
725 arl->capacity = wrap.capacity;
726 list->collection.size = wrap.size;
821 return n; 727 return n;
822 } 728 }
823 729
824 static size_t cx_arl_insert_sorted( 730 static size_t cx_arl_insert_sorted(
825 struct cx_list_s *list, 731 struct cx_list_s *list,
826 const void *sorted_data, 732 const void *sorted_data,
827 size_t n 733 size_t n
828 ) { 734 ) {
829 // get a correctly typed pointer to the list 735 return cx_arl_insert_sorted_impl(list, sorted_data, n, true);
830 cx_array_list *arl = (cx_array_list *) list;
831
832 if (cx_array_insert_sorted(
833 &arl->data,
834 &list->collection.size,
835 &arl->capacity,
836 list->collection.cmpfunc,
837 sorted_data,
838 list->collection.elem_size,
839 n,
840 &arl->reallocator
841 )) {
842 // array list implementation is "all or nothing"
843 return 0;
844 } else {
845 return n;
846 }
847 } 736 }
848 737
849 static size_t cx_arl_insert_unique( 738 static size_t cx_arl_insert_unique(
850 struct cx_list_s *list, 739 struct cx_list_s *list,
851 const void *sorted_data, 740 const void *sorted_data,
852 size_t n 741 size_t n
853 ) { 742 ) {
854 // get a correctly typed pointer to the list 743 return cx_arl_insert_sorted_impl(list, sorted_data, n, false);
855 cx_array_list *arl = (cx_array_list *) list;
856
857 if (cx_array_insert_unique(
858 &arl->data,
859 &list->collection.size,
860 &arl->capacity,
861 list->collection.cmpfunc,
862 sorted_data,
863 list->collection.elem_size,
864 n,
865 &arl->reallocator
866 )) {
867 // array list implementation is "all or nothing"
868 return 0;
869 } else {
870 return n;
871 }
872 } 744 }
873 745
874 static void *cx_arl_insert_element( 746 static void *cx_arl_insert_element(
875 struct cx_list_s *list, 747 struct cx_list_s *list,
876 size_t index, 748 size_t index,
890 ) { 762 ) {
891 struct cx_list_s *list = iter->src_handle; 763 struct cx_list_s *list = iter->src_handle;
892 if (iter->index < list->collection.size) { 764 if (iter->index < list->collection.size) {
893 if (cx_arl_insert_element(list, 765 if (cx_arl_insert_element(list,
894 iter->index + 1 - prepend, elem) == NULL) { 766 iter->index + 1 - prepend, elem) == NULL) {
895 return 1; 767 return 1; // LCOV_EXCL_LINE
896 } 768 }
897 iter->elem_count++; 769 iter->elem_count++;
898 if (prepend != 0) { 770 if (prepend != 0) {
899 iter->index++; 771 iter->index++;
900 iter->elem_handle = ((char *) iter->elem_handle) + list->collection.elem_size; 772 iter->elem_handle = ((char *) iter->elem_handle) + list->collection.elem_size;
901 } 773 }
902 return 0; 774 return 0;
903 } else { 775 } else {
904 if (cx_arl_insert_element(list, list->collection.size, elem) == NULL) { 776 if (cx_arl_insert_element(list, list->collection.size, elem) == NULL) {
905 return 1; 777 return 1; // LCOV_EXCL_LINE
906 } 778 }
907 iter->elem_count++; 779 iter->elem_count++;
908 iter->index = list->collection.size; 780 iter->index = list->collection.size;
909 return 0; 781 return 0;
910 } 782 }
945 ((char *) arl->data) + index * list->collection.elem_size, 817 ((char *) arl->data) + index * list->collection.elem_size,
946 remove * list->collection.elem_size 818 remove * list->collection.elem_size
947 ); 819 );
948 } 820 }
949 821
822 // calculate how many elements would need to be moved
823 size_t remaining = list->collection.size - index - remove;
824
950 // short-circuit removal of last elements 825 // short-circuit removal of last elements
951 if (index + remove == list->collection.size) { 826 if (remaining == 0) {
952 list->collection.size -= remove; 827 list->collection.size -= remove;
953 return remove; 828 return remove;
954 } 829 }
955 830
956 // just move the elements to the left 831 // just move the elements to the left
957 cx_array_copy( 832 char *dst_move = arl->data;
958 &arl->data, 833 dst_move += index * list->collection.elem_size;
959 &list->collection.size, 834 char *first_remaining = dst_move + remove * list->collection.elem_size;
960 &arl->capacity, 835 memmove(dst_move, first_remaining, remaining * list->collection.elem_size);
961 0,
962 index,
963 ((char *) arl->data) + (index + remove) * list->collection.elem_size,
964 list->collection.elem_size,
965 list->collection.size - index - remove,
966 &arl->reallocator
967 );
968 836
969 // decrease the size 837 // decrease the size
970 list->collection.size -= remove; 838 list->collection.size -= remove;
971 839
972 return remove; 840 return remove;
1023 struct cx_list_s *list, 891 struct cx_list_s *list,
1024 const void *elem, 892 const void *elem,
1025 bool remove 893 bool remove
1026 ) { 894 ) {
1027 assert(list != NULL); 895 assert(list != NULL);
1028 assert(list->collection.cmpfunc != NULL);
1029 if (list->collection.size == 0) return 0; 896 if (list->collection.size == 0) return 0;
1030 char *cur = ((const cx_array_list *) list)->data; 897 char *cur = ((const cx_array_list *) list)->data;
1031 898
1032 // optimize with binary search, when sorted 899 // optimize with binary search, when sorted
1033 if (list->collection.sorted) { 900 if (list->collection.sorted) {
1034 size_t i = cx_array_binary_search( 901 size_t i = cx_array_binary_search_c(
1035 cur, 902 cur,
1036 list->collection.size, 903 list->collection.size,
1037 list->collection.elem_size, 904 list->collection.elem_size,
1038 elem, 905 elem,
1039 list->collection.cmpfunc 906 cx_list_compare_wrapper,
907 list
1040 ); 908 );
1041 if (remove && i < list->collection.size) { 909 if (remove && i < list->collection.size) {
1042 cx_arl_remove(list, i, 1, NULL); 910 cx_arl_remove(list, i, 1, NULL);
1043 } 911 }
1044 return i; 912 return i;
1045 } 913 }
1046 914
1047 // fallback: linear search 915 // fallback: linear search
1048 for (size_t i = 0; i < list->collection.size; i++) { 916 for (size_t i = 0; i < list->collection.size; i++) {
1049 if (0 == list->collection.cmpfunc(elem, cur)) { 917 if (0 == cx_list_compare_wrapper(elem, cur, list)) {
1050 if (remove) { 918 if (remove) {
1051 cx_arl_remove(list, i, 1, NULL); 919 cx_arl_remove(list, i, 1, NULL);
1052 } 920 }
1053 return i; 921 return i;
1054 } 922 }
1056 } 924 }
1057 return list->collection.size; 925 return list->collection.size;
1058 } 926 }
1059 927
1060 static void cx_arl_sort(struct cx_list_s *list) { 928 static void cx_arl_sort(struct cx_list_s *list) {
1061 assert(list->collection.cmpfunc != NULL); 929 cx_array_qsort_c(((cx_array_list *) list)->data,
1062 qsort(((cx_array_list *) list)->data,
1063 list->collection.size, 930 list->collection.size,
1064 list->collection.elem_size, 931 list->collection.elem_size,
1065 list->collection.cmpfunc 932 cx_list_compare_wrapper,
933 list
1066 ); 934 );
1067 } 935 }
1068 936
1069 static int cx_arl_compare( 937 static int cx_arl_compare(
1070 const struct cx_list_s *list, 938 const struct cx_list_s *list,
1071 const struct cx_list_s *other 939 const struct cx_list_s *other
1072 ) { 940 ) {
1073 assert(list->collection.cmpfunc != NULL);
1074 if (list->collection.size == other->collection.size) { 941 if (list->collection.size == other->collection.size) {
1075 const char *left = ((const cx_array_list *) list)->data; 942 const char *left = ((const cx_array_list *) list)->data;
1076 const char *right = ((const cx_array_list *) other)->data; 943 const char *right = ((const cx_array_list *) other)->data;
1077 for (size_t i = 0; i < list->collection.size; i++) { 944 for (size_t i = 0; i < list->collection.size; i++) {
1078 int d = list->collection.cmpfunc(left, right); 945 int d = cx_list_compare_wrapper(left, right, (void*)list);
1079 if (d != 0) { 946 if (d != 0) {
1080 return d; 947 return d;
1081 } 948 }
1082 left += list->collection.elem_size; 949 left += list->collection.elem_size;
1083 right += other->collection.elem_size; 950 right += other->collection.elem_size;
1135 iter->elem_handle = ((char *) list->data) 1002 iter->elem_handle = ((char *) list->data)
1136 + iter->index * list->base.collection.elem_size; 1003 + iter->index * list->base.collection.elem_size;
1137 } 1004 }
1138 } 1005 }
1139 1006
1007 static int cx_arl_change_capacity(
1008 struct cx_list_s *list,
1009 size_t new_capacity
1010 ) {
1011 cx_array_list *arl = (cx_array_list *)list;
1012 return cxReallocateArray(list->collection.allocator,
1013 &arl->data, new_capacity, list->collection.elem_size);
1014 }
1140 1015
1141 static struct cx_iterator_s cx_arl_iterator( 1016 static struct cx_iterator_s cx_arl_iterator(
1142 const struct cx_list_s *list, 1017 const struct cx_list_s *list,
1143 size_t index, 1018 size_t index,
1144 bool backwards 1019 bool backwards
1172 cx_arl_at, 1047 cx_arl_at,
1173 cx_arl_find_remove, 1048 cx_arl_find_remove,
1174 cx_arl_sort, 1049 cx_arl_sort,
1175 cx_arl_compare, 1050 cx_arl_compare,
1176 cx_arl_reverse, 1051 cx_arl_reverse,
1052 cx_arl_change_capacity,
1177 cx_arl_iterator, 1053 cx_arl_iterator,
1178 }; 1054 };
1179 1055
1180 CxList *cxArrayListCreate( 1056 CxList *cxArrayListCreate(
1181 const CxAllocator *allocator, 1057 const CxAllocator *allocator,
1182 cx_compare_func comparator,
1183 size_t elem_size, 1058 size_t elem_size,
1184 size_t initial_capacity 1059 size_t initial_capacity
1185 ) { 1060 ) {
1186 if (allocator == NULL) { 1061 if (allocator == NULL) {
1187 allocator = cxDefaultAllocator; 1062 allocator = cxDefaultAllocator;
1188 } 1063 }
1189 1064
1190 cx_array_list *list = cxCalloc(allocator, 1, sizeof(cx_array_list)); 1065 cx_array_list *list = cxCalloc(allocator, 1, sizeof(cx_array_list));
1191 if (list == NULL) return NULL; 1066 if (list == NULL) return NULL;
1192 cx_list_init((CxList*)list, &cx_array_list_class, 1067 cx_list_init((CxList*)list, &cx_array_list_class,
1193 allocator, comparator, elem_size); 1068 allocator, elem_size);
1194 list->capacity = initial_capacity; 1069 list->capacity = initial_capacity;
1195 1070
1196 // allocate the array after the real elem_size is known 1071 // allocate the array after the real elem_size is known
1197 list->data = cxCalloc(allocator, initial_capacity, 1072 list->data = cxCalloc(allocator, initial_capacity,
1198 list->base.collection.elem_size); 1073 list->base.collection.elem_size);
1199 if (list->data == NULL) { // LCOV_EXCL_START 1074 if (list->data == NULL) { // LCOV_EXCL_START
1200 cxFree(allocator, list); 1075 cxFree(allocator, list);
1201 return NULL; 1076 return NULL;
1202 } // LCOV_EXCL_STOP 1077 } // LCOV_EXCL_STOP
1203 1078
1204 // configure the reallocator
1205 list->reallocator = cx_array_reallocator(allocator, NULL);
1206
1207 return (CxList *) list; 1079 return (CxList *) list;
1208 } 1080 }

Mercurial Repository: dav

mercurial