comparison: src/array_list.c
src/array_list.c
- changeset 1494
- f027a95d93f2
- parent 1482
- 6769cb72521b
- child 1496
- 1a982f6f2407
equal
deleted
inserted
replaced
| 1493:33f556a7eca6 | 1494:f027a95d93f2 |
|---|---|
| 40 size_t new_capacity, | 40 size_t new_capacity, |
| 41 size_t elem_size, | 41 size_t elem_size, |
| 42 cx_attr_unused CxArrayReallocator *alloc | 42 cx_attr_unused CxArrayReallocator *alloc |
| 43 ) { | 43 ) { |
| 44 size_t n; | 44 size_t n; |
| 45 // LCOV_EXCL_START | |
| 45 if (cx_szmul(new_capacity, elem_size, &n)) { | 46 if (cx_szmul(new_capacity, elem_size, &n)) { |
| 46 errno = EOVERFLOW; | 47 errno = EOVERFLOW; |
| 47 return NULL; | 48 return NULL; |
| 48 } | 49 } // LCOV_EXCL_STOP |
| 49 return cxReallocDefault(array, n); | 50 return cxReallocDefault(array, n); |
| 50 } | 51 } |
| 51 | 52 |
| 52 CxArrayReallocator cx_array_default_reallocator_impl = { | 53 CxArrayReallocator cx_array_default_reallocator_impl = { |
| 53 cx_array_default_realloc, NULL, NULL | 54 cx_array_default_realloc, NULL, NULL |
| 64 size_t elem_size, | 65 size_t elem_size, |
| 65 cx_attr_unused CxArrayReallocator *alloc | 66 cx_attr_unused CxArrayReallocator *alloc |
| 66 ) { | 67 ) { |
| 67 // check for overflow | 68 // check for overflow |
| 68 size_t n; | 69 size_t n; |
| 70 // LCOV_EXCL_START | |
| 69 if (cx_szmul(new_capacity, elem_size, &n)) { | 71 if (cx_szmul(new_capacity, elem_size, &n)) { |
| 70 errno = EOVERFLOW; | 72 errno = EOVERFLOW; |
| 71 return NULL; | 73 return NULL; |
| 72 } | 74 } // LCOV_EXCL_STOP |
| 73 | 75 |
| 74 // retrieve the pointer to the actual allocator | 76 // retrieve the pointer to the actual allocator |
| 75 const CxAllocator *al = alloc->allocator; | 77 const CxAllocator *al = alloc->allocator; |
| 76 | 78 |
| 77 // check if the array is still located on the stack | 79 // check if the array is still located on the stack |
| 106 * Intelligently calculates a new capacity, reserving some more | 108 * Intelligently calculates a new capacity, reserving some more |
| 107 * elements than required to prevent too many allocations. | 109 * elements than required to prevent too many allocations. |
| 108 * | 110 * |
| 109 * @param current_capacity the current capacity of the array | 111 * @param current_capacity the current capacity of the array |
| 110 * @param needed_capacity the required capacity of the array | 112 * @param needed_capacity the required capacity of the array |
| 111 * @param maximum_capacity the maximum capacity (given by the data type) | |
| 112 * @return the new capacity | 113 * @return the new capacity |
| 113 */ | 114 */ |
| 114 static size_t cx_array_grow_capacity( | 115 static size_t cx_array_grow_capacity( |
| 115 size_t current_capacity, | 116 size_t current_capacity, |
| 116 size_t needed_capacity, | 117 size_t needed_capacity |
| 117 size_t maximum_capacity | |
| 118 ) { | 118 ) { |
| 119 if (current_capacity >= needed_capacity) { | 119 if (current_capacity >= needed_capacity) { |
| 120 return current_capacity; | 120 return current_capacity; |
| 121 } | 121 } |
| 122 size_t cap = needed_capacity; | 122 size_t cap = needed_capacity; |
| 123 size_t alignment; | 123 size_t alignment; |
| 124 if (cap < 128) alignment = 16; | 124 if (cap < 128) alignment = 16; |
| 125 else if (cap < 1024) alignment = 64; | 125 else if (cap < 1024) alignment = 64; |
| 126 else if (cap < 8192) alignment = 512; | 126 else if (cap < 8192) alignment = 512; |
| 127 else alignment = 1024; | 127 else alignment = 1024; |
| 128 | 128 return cap - (cap % alignment) + alignment; |
| 129 if (cap - 1 > maximum_capacity - alignment) { | |
| 130 return maximum_capacity; | |
| 131 } else { | |
| 132 return cap - (cap % alignment) + alignment; | |
| 133 } | |
| 134 } | 129 } |
| 135 | 130 |
| 136 int cx_array_reserve( | 131 int cx_array_reserve( |
| 137 void **array, | 132 void **array, |
| 138 void *size, | 133 void *size, |
| 286 // check if resize is required | 281 // check if resize is required |
| 287 const size_t minsize = index + elem_count; | 282 const size_t minsize = index + elem_count; |
| 288 const size_t newsize = oldsize < minsize ? minsize : oldsize; | 283 const size_t newsize = oldsize < minsize ? minsize : oldsize; |
| 289 | 284 |
| 290 // reallocate if necessary | 285 // reallocate if necessary |
| 291 const size_t newcap = cx_array_grow_capacity(oldcap, newsize, max_size); | 286 const size_t newcap = cx_array_grow_capacity(oldcap, newsize); |
| 292 if (newcap > oldcap) { | 287 if (newcap > oldcap) { |
| 293 // check if we need to repair the src pointer | 288 // check if we need to repair the src pointer |
| 294 uintptr_t targetaddr = (uintptr_t) *target; | 289 uintptr_t targetaddr = (uintptr_t) *target; |
| 295 uintptr_t srcaddr = (uintptr_t) src; | 290 uintptr_t srcaddr = (uintptr_t) src; |
| 296 bool repairsrc = targetaddr <= srcaddr | 291 bool repairsrc = targetaddr <= srcaddr |
| 379 | 374 |
| 380 // store some counts | 375 // store some counts |
| 381 const size_t old_size = *size; | 376 const size_t old_size = *size; |
| 382 const size_t old_capacity = *capacity; | 377 const size_t old_capacity = *capacity; |
| 383 // the necessary capacity is the worst case assumption, including duplicates | 378 // the necessary capacity is the worst case assumption, including duplicates |
| 384 const size_t needed_capacity = cx_array_grow_capacity(old_capacity, | 379 const size_t needed_capacity = cx_array_grow_capacity(old_capacity, old_size + elem_count); |
| 385 old_size + elem_count, SIZE_MAX); | |
| 386 | 380 |
| 387 // if we need more than we have, try a reallocation | 381 // if we need more than we have, try a reallocation |
| 388 if (needed_capacity > old_capacity) { | 382 if (needed_capacity > old_capacity) { |
| 389 void *new_mem = reallocator->realloc( | 383 void *new_mem = reallocator->realloc( |
| 390 *target, old_capacity, needed_capacity, elem_size, reallocator | 384 *target, old_capacity, needed_capacity, elem_size, reallocator |
| 790 // get a correctly typed pointer to the list | 784 // get a correctly typed pointer to the list |
| 791 cx_array_list *arl = (cx_array_list *) list; | 785 cx_array_list *arl = (cx_array_list *) list; |
| 792 | 786 |
| 793 // guarantee enough capacity | 787 // guarantee enough capacity |
| 794 if (arl->capacity < list->collection.size + n) { | 788 if (arl->capacity < list->collection.size + n) { |
| 795 const size_t new_capacity = cx_array_grow_capacity(arl->capacity, | 789 const size_t new_capacity = cx_array_grow_capacity(arl->capacity,list->collection.size + n); |
| 796 list->collection.size + n, SIZE_MAX); | |
| 797 if (cxReallocateArray( | 790 if (cxReallocateArray( |
| 798 list->collection.allocator, | 791 list->collection.allocator, |
| 799 &arl->data, new_capacity, | 792 &arl->data, new_capacity, |
| 800 list->collection.elem_size) | 793 list->collection.elem_size) |
| 801 ) { | 794 ) { |
