Mercurial > hg > ucx / file comparison

comparison: src/array_list.c

src/array_list.c

changeset 1040
1ecf4dbbc60c
parent 1022
2911c1f4a570
equal deleted inserted replaced
1039:ec62453fc8a6 1040:1ecf4dbbc60c
38 void *array, 38 void *array,
39 size_t capacity, 39 size_t capacity,
40 size_t elem_size, 40 size_t elem_size,
41 cx_attr_unused CxArrayReallocator *alloc 41 cx_attr_unused CxArrayReallocator *alloc
42 ) { 42 ) {
43 return realloc(array, capacity * elem_size); 43 size_t n;
44 if (cx_szmul(capacity, elem_size, &n)) {
45 errno = EOVERFLOW;
46 return NULL;
47 }
48 return realloc(array, n);
44 } 49 }
45 50
46 CxArrayReallocator cx_array_default_reallocator_impl = { 51 CxArrayReallocator cx_array_default_reallocator_impl = {
47 cx_array_default_realloc, NULL, NULL, 0, 0 52 cx_array_default_realloc, NULL, NULL, 0, 0
48 }; 53 };
55 void *array, 60 void *array,
56 size_t capacity, 61 size_t capacity,
57 size_t elem_size, 62 size_t elem_size,
58 cx_attr_unused CxArrayReallocator *alloc 63 cx_attr_unused CxArrayReallocator *alloc
59 ) { 64 ) {
65 // check for overflow
66 size_t n;
67 if (cx_szmul(capacity, elem_size, &n)) {
68 errno = EOVERFLOW;
69 return NULL;
70 }
71
60 // retrieve the pointer to the actual allocator 72 // retrieve the pointer to the actual allocator
61 const CxAllocator *al = alloc->ptr1; 73 const CxAllocator *al = alloc->ptr1;
62 74
63 // check if the array is still located on the stack 75 // check if the array is still located on the stack
64 void *newmem; 76 void *newmem;
65 if (array == alloc->ptr2) { 77 if (array == alloc->ptr2) {
66 newmem = cxMalloc(al, capacity * elem_size); 78 newmem = cxMalloc(al, n);
67 if (newmem != NULL && array != NULL) { 79 if (newmem != NULL && array != NULL) {
68 memcpy(newmem, array, capacity * elem_size); 80 memcpy(newmem, array, n);
69 } 81 }
70 } else { 82 } else {
71 newmem = cxRealloc(al, array, capacity * elem_size); 83 newmem = cxRealloc(al, array, n);
72 } 84 }
73 return newmem; 85 return newmem;
74 } 86 }
75 87
76 struct cx_array_reallocator_s cx_array_reallocator( 88 struct cx_array_reallocator_s cx_array_reallocator(
86 0, 0 98 0, 0
87 }; 99 };
88 } 100 }
89 101
90 // LOW LEVEL ARRAY LIST FUNCTIONS 102 // LOW LEVEL ARRAY LIST FUNCTIONS
103
104 static size_t cx_array_align_capacity(
105 size_t cap,
106 size_t alignment,
107 size_t max
108 ) {
109 if (cap > max - alignment) {
110 return cap;
111 } else {
112 return cap - (cap % alignment) + alignment;
113 }
114 }
91 115
92 int cx_array_reserve( 116 int cx_array_reserve(
93 void **array, 117 void **array,
94 void *size, 118 void *size,
95 void *capacity, 119 void *capacity,
134 } 158 }
135 159
136 // assert that the array is allocated when it has capacity 160 // assert that the array is allocated when it has capacity
137 assert(*array != NULL || oldcap == 0); 161 assert(*array != NULL || oldcap == 0);
138 162
163 // check for overflow
164 if (elem_count > max_size - oldsize) {
165 errno = EOVERFLOW;
166 return 1;
167 }
168
139 // determine new capacity 169 // determine new capacity
140 size_t newcap = oldsize + elem_count; 170 size_t newcap = oldsize + elem_count;
141
142 // check for overflow
143 if (newcap > max_size) {
144 errno = EOVERFLOW;
145 return 1;
146 }
147 171
148 // reallocate if possible 172 // reallocate if possible
149 if (newcap > oldcap) { 173 if (newcap > oldcap) {
150 // calculate new capacity (next number divisible by 16) 174 // calculate new capacity (next number divisible by 16)
151 newcap = newcap - (newcap % 16) + 16; 175 newcap = cx_array_align_capacity(newcap, 16, max_size);
152 176
153 // perform reallocation 177 // perform reallocation
154 void *newmem = reallocator->realloc( 178 void *newmem = reallocator->realloc(
155 *array, newcap, elem_size, reallocator 179 *array, newcap, elem_size, reallocator
156 ); 180 );
227 } 251 }
228 252
229 // assert that the array is allocated when it has capacity 253 // assert that the array is allocated when it has capacity
230 assert(*target != NULL || oldcap == 0); 254 assert(*target != NULL || oldcap == 0);
231 255
256 // check for overflow
257 if (index > max_size || elem_count > max_size - index) {
258 errno = EOVERFLOW;
259 return 1;
260 }
261
232 // check if resize is required 262 // check if resize is required
233 size_t minsize = index + elem_count; 263 size_t minsize = index + elem_count;
234 size_t newsize = oldsize < minsize ? minsize : oldsize; 264 size_t newsize = oldsize < minsize ? minsize : oldsize;
235
236 // check for overflow
237 if (newsize > max_size) {
238 errno = EOVERFLOW;
239 return 1;
240 }
241 265
242 // reallocate if possible 266 // reallocate if possible
243 size_t newcap = oldcap; 267 size_t newcap = oldcap;
244 if (newsize > oldcap) { 268 if (newsize > oldcap) {
245 // check, if we need to repair the src pointer 269 // check, if we need to repair the src pointer
247 uintptr_t srcaddr = (uintptr_t) src; 271 uintptr_t srcaddr = (uintptr_t) src;
248 bool repairsrc = targetaddr <= srcaddr 272 bool repairsrc = targetaddr <= srcaddr
249 && srcaddr < targetaddr + oldcap * elem_size; 273 && srcaddr < targetaddr + oldcap * elem_size;
250 274
251 // calculate new capacity (next number divisible by 16) 275 // calculate new capacity (next number divisible by 16)
252 newcap = newsize - (newsize % 16) + 16; 276 newcap = cx_array_align_capacity(newsize, 16, max_size);
253 assert(newcap > newsize); 277 assert(newcap > newsize);
254 278
255 // perform reallocation 279 // perform reallocation
256 void *newmem = reallocator->realloc( 280 void *newmem = reallocator->realloc(
257 *target, newcap, elem_size, reallocator 281 *target, newcap, elem_size, reallocator
272 // determine target pointer 296 // determine target pointer
273 char *start = *target; 297 char *start = *target;
274 start += index * elem_size; 298 start += index * elem_size;
275 299
276 // copy elements and set new size 300 // copy elements and set new size
301 // note: no overflow check here, b/c we cannot get here w/o allocation
277 memmove(start, src, elem_count * elem_size); 302 memmove(start, src, elem_count * elem_size);
278 303
279 // if any of size or capacity changed, store them back 304 // if any of size or capacity changed, store them back
280 if (newsize != oldsize || newcap != oldcap) { 305 if (newsize != oldsize || newcap != oldcap) {
281 if (width == 0 || width == CX_WORDSIZE) { 306 if (width == 0 || width == CX_WORDSIZE) {
319 assert(reallocator != NULL); 344 assert(reallocator != NULL);
320 345
321 // corner case 346 // corner case
322 if (elem_count == 0) return 0; 347 if (elem_count == 0) return 0;
323 348
349 // overflow check
350 if (elem_count > SIZE_MAX - *size) {
351 errno = EOVERFLOW;
352 return 1;
353 }
354
324 // store some counts 355 // store some counts
325 size_t old_size = *size; 356 size_t old_size = *size;
326 size_t needed_capacity = old_size + elem_count; 357 size_t needed_capacity = old_size + elem_count;
327 358
328 // if we need more than we have, try a reallocation 359 // if we need more than we have, try a reallocation
329 if (needed_capacity > *capacity) { 360 if (needed_capacity > *capacity) {
330 size_t new_capacity = needed_capacity - (needed_capacity % 16) + 16; 361 size_t new_capacity = cx_array_align_capacity(needed_capacity, 16, SIZE_MAX);
331 void *new_mem = reallocator->realloc( 362 void *new_mem = reallocator->realloc(
332 *target, new_capacity, elem_size, reallocator 363 *target, new_capacity, elem_size, reallocator
333 ); 364 );
334 if (new_mem == NULL) { 365 if (new_mem == NULL) {
335 // give it up right away, there is no contract 366 // give it up right away, there is no contract

Mercurial Repository: ucx

mercurial