| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | /* | ||
| 2 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. | ||
| 3 | * | ||
| 4 | * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved. | ||
| 5 | * | ||
| 6 | * Redistribution and use in source and binary forms, with or without | ||
| 7 | * modification, are permitted provided that the following conditions are met: | ||
| 8 | * | ||
| 9 | * 1. Redistributions of source code must retain the above copyright | ||
| 10 | * notice, this list of conditions and the following disclaimer. | ||
| 11 | * | ||
| 12 | * 2. Redistributions in binary form must reproduce the above copyright | ||
| 13 | * notice, this list of conditions and the following disclaimer in the | ||
| 14 | * documentation and/or other materials provided with the distribution. | ||
| 15 | * | ||
| 16 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" | ||
| 17 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | ||
| 18 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | ||
| 19 | * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE | ||
| 20 | * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR | ||
| 21 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF | ||
| 22 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS | ||
| 23 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN | ||
| 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 | ||
| 26 | * POSSIBILITY OF SUCH DAMAGE. | ||
| 27 | */ | ||
| 28 | |||
| 29 | #include "cx/array_list.h" | ||
| 30 | #include "cx/compare.h" | ||
| 31 | #include <assert.h> | ||
| 32 | #include <string.h> | ||
| 33 | #include <errno.h> | ||
| 34 | |||
| 35 | // Default array reallocator | ||
| 36 | |||
| 37 | 5 | static void *cx_array_default_realloc( | |
| 38 | void *array, | ||
| 39 | size_t capacity, | ||
| 40 | size_t elem_size, | ||
| 41 | cx_attr_unused CxArrayReallocator *alloc | ||
| 42 | ) { | ||
| 43 | size_t n; | ||
| 44 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 5 times.
|
5 | if (cx_szmul(capacity, elem_size, &n)) { |
| 45 | ✗ | errno = EOVERFLOW; | |
| 46 | ✗ | return NULL; | |
| 47 | } | ||
| 48 | 5 | return realloc(array, n); | |
| 49 | } | ||
| 50 | |||
| 51 | CxArrayReallocator cx_array_default_reallocator_impl = { | ||
| 52 | cx_array_default_realloc, NULL, NULL, 0, 0 | ||
| 53 | }; | ||
| 54 | |||
| 55 | CxArrayReallocator *cx_array_default_reallocator = &cx_array_default_reallocator_impl; | ||
| 56 | |||
| 57 | // Stack-aware array reallocator | ||
| 58 | |||
| 59 | 239 | static void *cx_array_advanced_realloc( | |
| 60 | void *array, | ||
| 61 | size_t capacity, | ||
| 62 | size_t elem_size, | ||
| 63 | cx_attr_unused CxArrayReallocator *alloc | ||
| 64 | ) { | ||
| 65 | // check for overflow | ||
| 66 | size_t n; | ||
| 67 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 239 times.
|
239 | if (cx_szmul(capacity, elem_size, &n)) { |
| 68 | ✗ | errno = EOVERFLOW; | |
| 69 | ✗ | return NULL; | |
| 70 | } | ||
| 71 | |||
| 72 | // retrieve the pointer to the actual allocator | ||
| 73 | 239 | const CxAllocator *al = alloc->ptr1; | |
| 74 | |||
| 75 | // check if the array is still located on the stack | ||
| 76 | void *newmem; | ||
| 77 |
2/2✓ Branch 0 taken 2 times.
✓ Branch 1 taken 237 times.
|
239 | if (array == alloc->ptr2) { |
| 78 | 2 | newmem = cxMalloc(al, n); | |
| 79 |
2/4✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
|
2 | if (newmem != NULL && array != NULL) { |
| 80 | 2 | memcpy(newmem, array, n); | |
| 81 | } | ||
| 82 | } else { | ||
| 83 | 237 | newmem = cxRealloc(al, array, n); | |
| 84 | } | ||
| 85 | 239 | return newmem; | |
| 86 | } | ||
| 87 | |||
| 88 | 499 | struct cx_array_reallocator_s cx_array_reallocator( | |
| 89 | const struct cx_allocator_s *allocator, | ||
| 90 | const void *stackmem | ||
| 91 | ) { | ||
| 92 |
2/2✓ Branch 0 taken 265 times.
✓ Branch 1 taken 234 times.
|
499 | if (allocator == NULL) { |
| 93 | 265 | allocator = cxDefaultAllocator; | |
| 94 | } | ||
| 95 | 499 | return (struct cx_array_reallocator_s) { | |
| 96 | cx_array_advanced_realloc, | ||
| 97 | (void*) allocator, (void*) stackmem, | ||
| 98 | 0, 0 | ||
| 99 | }; | ||
| 100 | } | ||
| 101 | |||
| 102 | // LOW LEVEL ARRAY LIST FUNCTIONS | ||
| 103 | |||
| 104 | 244 | static size_t cx_array_align_capacity( | |
| 105 | size_t cap, | ||
| 106 | size_t alignment, | ||
| 107 | size_t max | ||
| 108 | ) { | ||
| 109 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 244 times.
|
244 | if (cap > max - alignment) { |
| 110 | ✗ | return cap; | |
| 111 | } else { | ||
| 112 | 244 | return cap - (cap % alignment) + alignment; | |
| 113 | } | ||
| 114 | } | ||
| 115 | |||
| 116 | 327 | int cx_array_reserve( | |
| 117 | void **array, | ||
| 118 | void *size, | ||
| 119 | void *capacity, | ||
| 120 | unsigned width, | ||
| 121 | size_t elem_size, | ||
| 122 | size_t elem_count, | ||
| 123 | CxArrayReallocator *reallocator | ||
| 124 | ) { | ||
| 125 | // assert pointers | ||
| 126 | assert(array != NULL); | ||
| 127 | assert(size != NULL); | ||
| 128 | assert(capacity != NULL); | ||
| 129 | |||
| 130 | // default reallocator | ||
| 131 |
2/2✓ Branch 0 taken 2 times.
✓ Branch 1 taken 325 times.
|
327 | if (reallocator == NULL) { |
| 132 | 2 | reallocator = cx_array_default_reallocator; | |
| 133 | } | ||
| 134 | |||
| 135 | // determine size and capacity | ||
| 136 | size_t oldcap; | ||
| 137 | size_t oldsize; | ||
| 138 | size_t max_size; | ||
| 139 |
3/4✓ Branch 0 taken 327 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 92 times.
✓ Branch 3 taken 235 times.
|
327 | if (width == 0 || width == sizeof(size_t)) { |
| 140 | 92 | oldcap = *(size_t*) capacity; | |
| 141 | 92 | oldsize = *(size_t*) size; | |
| 142 | 92 | max_size = SIZE_MAX; | |
| 143 |
2/2✓ Branch 0 taken 2 times.
✓ Branch 1 taken 233 times.
|
235 | } else if (width == sizeof(uint16_t)) { |
| 144 | 2 | oldcap = *(uint16_t*) capacity; | |
| 145 | 2 | oldsize = *(uint16_t*) size; | |
| 146 | 2 | max_size = UINT16_MAX; | |
| 147 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 233 times.
|
233 | } else if (width == sizeof(uint8_t)) { |
| 148 | ✗ | oldcap = *(uint8_t*) capacity; | |
| 149 | ✗ | oldsize = *(uint8_t*) size; | |
| 150 | ✗ | max_size = UINT8_MAX; | |
| 151 | } | ||
| 152 | #if CX_WORDSIZE == 64 | ||
| 153 |
1/2✓ Branch 0 taken 233 times.
✗ Branch 1 not taken.
|
233 | else if (width == sizeof(uint32_t)) { |
| 154 | 233 | oldcap = *(uint32_t*) capacity; | |
| 155 | 233 | oldsize = *(uint32_t*) size; | |
| 156 | 233 | max_size = UINT32_MAX; | |
| 157 | } | ||
| 158 | #endif | ||
| 159 | else { | ||
| 160 | ✗ | errno = EINVAL; | |
| 161 | ✗ | return 1; | |
| 162 | } | ||
| 163 | |||
| 164 | // assert that the array is allocated when it has capacity | ||
| 165 | assert(*array != NULL || oldcap == 0); | ||
| 166 | |||
| 167 | // check for overflow | ||
| 168 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 327 times.
|
327 | if (elem_count > max_size - oldsize) { |
| 169 | ✗ | errno = EOVERFLOW; | |
| 170 | ✗ | return 1; | |
| 171 | } | ||
| 172 | |||
| 173 | // determine new capacity | ||
| 174 | 327 | size_t newcap = oldsize + elem_count; | |
| 175 | |||
| 176 | // reallocate if possible | ||
| 177 |
2/2✓ Branch 0 taken 2 times.
✓ Branch 1 taken 325 times.
|
327 | if (newcap > oldcap) { |
| 178 | // calculate new capacity (next number divisible by 16) | ||
| 179 | 2 | newcap = cx_array_align_capacity(newcap, 16, max_size); | |
| 180 | |||
| 181 | // perform reallocation | ||
| 182 | 2 | void *newmem = reallocator->realloc( | |
| 183 | *array, newcap, elem_size, reallocator | ||
| 184 | ); | ||
| 185 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 2 times.
|
2 | if (newmem == NULL) { |
| 186 | − | return 1; // LCOV_EXCL_LINE | |
| 187 | } | ||
| 188 | |||
| 189 | // store new pointer | ||
| 190 | 2 | *array = newmem; | |
| 191 | |||
| 192 | // store new capacity | ||
| 193 |
2/4✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 2 times.
|
2 | if (width == 0 || width == sizeof(size_t)) { |
| 194 | ✗ | *(size_t*) capacity = newcap; | |
| 195 |
2/2✓ Branch 0 taken 1 times.
✓ Branch 1 taken 1 times.
|
2 | } else if (width == sizeof(uint16_t)) { |
| 196 | 1 | *(uint16_t*) capacity = (uint16_t) newcap; | |
| 197 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1 times.
|
1 | } else if (width == sizeof(uint8_t)) { |
| 198 | ✗ | *(uint8_t*) capacity = (uint8_t) newcap; | |
| 199 | } | ||
| 200 | #if CX_WORDSIZE == 64 | ||
| 201 |
1/2✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
|
1 | else if (width == sizeof(uint32_t)) { |
| 202 | 1 | *(uint32_t*) capacity = (uint32_t) newcap; | |
| 203 | } | ||
| 204 | #endif | ||
| 205 | } | ||
| 206 | |||
| 207 | 327 | return 0; | |
| 208 | } | ||
| 209 | |||
| 210 | 4348 | int cx_array_copy( | |
| 211 | void **target, | ||
| 212 | void *size, | ||
| 213 | void *capacity, | ||
| 214 | unsigned width, | ||
| 215 | size_t index, | ||
| 216 | const void *src, | ||
| 217 | size_t elem_size, | ||
| 218 | size_t elem_count, | ||
| 219 | CxArrayReallocator *reallocator | ||
| 220 | ) { | ||
| 221 | // assert pointers | ||
| 222 | assert(target != NULL); | ||
| 223 | assert(size != NULL); | ||
| 224 | assert(capacity != NULL); | ||
| 225 | assert(src != NULL); | ||
| 226 | |||
| 227 | // default reallocator | ||
| 228 |
2/2✓ Branch 0 taken 1 times.
✓ Branch 1 taken 4347 times.
|
4348 | if (reallocator == NULL) { |
| 229 | 1 | reallocator = cx_array_default_reallocator; | |
| 230 | } | ||
| 231 | |||
| 232 | // determine size and capacity | ||
| 233 | size_t oldcap; | ||
| 234 | size_t oldsize; | ||
| 235 | size_t max_size; | ||
| 236 |
4/4✓ Branch 0 taken 333 times.
✓ Branch 1 taken 4015 times.
✓ Branch 2 taken 297 times.
✓ Branch 3 taken 36 times.
|
4348 | if (width == 0 || width == sizeof(size_t)) { |
| 237 | 4312 | oldcap = *(size_t*) capacity; | |
| 238 | 4312 | oldsize = *(size_t*) size; | |
| 239 | 4312 | max_size = SIZE_MAX; | |
| 240 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 36 times.
|
36 | } else if (width == sizeof(uint16_t)) { |
| 241 | ✗ | oldcap = *(uint16_t*) capacity; | |
| 242 | ✗ | oldsize = *(uint16_t*) size; | |
| 243 | ✗ | max_size = UINT16_MAX; | |
| 244 |
2/2✓ Branch 0 taken 3 times.
✓ Branch 1 taken 33 times.
|
36 | } else if (width == sizeof(uint8_t)) { |
| 245 | 3 | oldcap = *(uint8_t*) capacity; | |
| 246 | 3 | oldsize = *(uint8_t*) size; | |
| 247 | 3 | max_size = UINT8_MAX; | |
| 248 | } | ||
| 249 | #if CX_WORDSIZE == 64 | ||
| 250 |
2/2✓ Branch 0 taken 32 times.
✓ Branch 1 taken 1 times.
|
33 | else if (width == sizeof(uint32_t)) { |
| 251 | 32 | oldcap = *(uint32_t*) capacity; | |
| 252 | 32 | oldsize = *(uint32_t*) size; | |
| 253 | 32 | max_size = UINT32_MAX; | |
| 254 | } | ||
| 255 | #endif | ||
| 256 | else { | ||
| 257 | 1 | errno = EINVAL; | |
| 258 | 1 | return 1; | |
| 259 | } | ||
| 260 | |||
| 261 | // assert that the array is allocated when it has capacity | ||
| 262 | assert(*target != NULL || oldcap == 0); | ||
| 263 | |||
| 264 | // check for overflow | ||
| 265 |
3/4✓ Branch 0 taken 4346 times.
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 4346 times.
|
4347 | if (index > max_size || elem_count > max_size - index) { |
| 266 | 1 | errno = EOVERFLOW; | |
| 267 | 1 | return 1; | |
| 268 | } | ||
| 269 | |||
| 270 | // check if resize is required | ||
| 271 | 4346 | size_t minsize = index + elem_count; | |
| 272 | 4346 | size_t newsize = oldsize < minsize ? minsize : oldsize; | |
| 273 | |||
| 274 | // reallocate if possible | ||
| 275 | 4346 | size_t newcap = oldcap; | |
| 276 |
2/2✓ Branch 0 taken 236 times.
✓ Branch 1 taken 4110 times.
|
4346 | if (newsize > oldcap) { |
| 277 | // check, if we need to repair the src pointer | ||
| 278 | 236 | uintptr_t targetaddr = (uintptr_t) *target; | |
| 279 | 236 | uintptr_t srcaddr = (uintptr_t) src; | |
| 280 | 236 | bool repairsrc = targetaddr <= srcaddr | |
| 281 |
4/4✓ Branch 0 taken 204 times.
✓ Branch 1 taken 32 times.
✓ Branch 2 taken 16 times.
✓ Branch 3 taken 188 times.
|
236 | && srcaddr < targetaddr + oldcap * elem_size; |
| 282 | |||
| 283 | // calculate new capacity (next number divisible by 16) | ||
| 284 | 236 | newcap = cx_array_align_capacity(newsize, 16, max_size); | |
| 285 | assert(newcap > newsize); | ||
| 286 | |||
| 287 | // perform reallocation | ||
| 288 | 236 | void *newmem = reallocator->realloc( | |
| 289 | *target, newcap, elem_size, reallocator | ||
| 290 | ); | ||
| 291 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 236 times.
|
236 | if (newmem == NULL) { |
| 292 | ✗ | return 1; | |
| 293 | } | ||
| 294 | |||
| 295 | // repair src pointer, if necessary | ||
| 296 |
2/2✓ Branch 0 taken 16 times.
✓ Branch 1 taken 220 times.
|
236 | if (repairsrc) { |
| 297 | 16 | src = ((char *) newmem) + (srcaddr - targetaddr); | |
| 298 | } | ||
| 299 | |||
| 300 | // store new pointer | ||
| 301 | 236 | *target = newmem; | |
| 302 | } | ||
| 303 | |||
| 304 | // determine target pointer | ||
| 305 | 4346 | char *start = *target; | |
| 306 | 4346 | start += index * elem_size; | |
| 307 | |||
| 308 | // copy elements and set new size | ||
| 309 | // note: no overflow check here, b/c we cannot get here w/o allocation | ||
| 310 | 4346 | memmove(start, src, elem_count * elem_size); | |
| 311 | |||
| 312 | // if any of size or capacity changed, store them back | ||
| 313 |
3/4✓ Branch 0 taken 158 times.
✓ Branch 1 taken 4188 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 158 times.
|
4346 | if (newsize != oldsize || newcap != oldcap) { |
| 314 |
4/4✓ Branch 0 taken 331 times.
✓ Branch 1 taken 3857 times.
✓ Branch 2 taken 297 times.
✓ Branch 3 taken 34 times.
|
4188 | if (width == 0 || width == sizeof(size_t)) { |
| 315 | 4154 | *(size_t*) capacity = newcap; | |
| 316 | 4154 | *(size_t*) size = newsize; | |
| 317 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 34 times.
|
34 | } else if (width == sizeof(uint16_t)) { |
| 318 | ✗ | *(uint16_t*) capacity = (uint16_t) newcap; | |
| 319 | ✗ | *(uint16_t*) size = (uint16_t) newsize; | |
| 320 |
2/2✓ Branch 0 taken 2 times.
✓ Branch 1 taken 32 times.
|
34 | } else if (width == sizeof(uint8_t)) { |
| 321 | 2 | *(uint8_t*) capacity = (uint8_t) newcap; | |
| 322 | 2 | *(uint8_t*) size = (uint8_t) newsize; | |
| 323 | } | ||
| 324 | #if CX_WORDSIZE == 64 | ||
| 325 |
1/2✓ Branch 0 taken 32 times.
✗ Branch 1 not taken.
|
32 | else if (width == sizeof(uint32_t)) { |
| 326 | 32 | *(uint32_t*) capacity = (uint32_t) newcap; | |
| 327 | 32 | *(uint32_t*) size = (uint32_t) newsize; | |
| 328 | } | ||
| 329 | #endif | ||
| 330 | } | ||
| 331 | |||
| 332 | // return successfully | ||
| 333 | 4346 | return 0; | |
| 334 | } | ||
| 335 | |||
| 336 | 24 | int cx_array_insert_sorted( | |
| 337 | void **target, | ||
| 338 | size_t *size, | ||
| 339 | size_t *capacity, | ||
| 340 | cx_compare_func cmp_func, | ||
| 341 | const void *sorted_data, | ||
| 342 | size_t elem_size, | ||
| 343 | size_t elem_count, | ||
| 344 | CxArrayReallocator *reallocator | ||
| 345 | ) { | ||
| 346 | // assert pointers | ||
| 347 | assert(target != NULL); | ||
| 348 | assert(size != NULL); | ||
| 349 | assert(capacity != NULL); | ||
| 350 | assert(cmp_func != NULL); | ||
| 351 | assert(sorted_data != NULL); | ||
| 352 | |||
| 353 | // default reallocator | ||
| 354 |
2/2✓ Branch 0 taken 8 times.
✓ Branch 1 taken 16 times.
|
24 | if (reallocator == NULL) { |
| 355 | 8 | reallocator = cx_array_default_reallocator; | |
| 356 | } | ||
| 357 | |||
| 358 | // corner case | ||
| 359 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
|
24 | if (elem_count == 0) return 0; |
| 360 | |||
| 361 | // overflow check | ||
| 362 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
|
24 | if (elem_count > SIZE_MAX - *size) { |
| 363 | ✗ | errno = EOVERFLOW; | |
| 364 | ✗ | return 1; | |
| 365 | } | ||
| 366 | |||
| 367 | // store some counts | ||
| 368 | 24 | size_t old_size = *size; | |
| 369 | 24 | size_t needed_capacity = old_size + elem_count; | |
| 370 | |||
| 371 | // if we need more than we have, try a reallocation | ||
| 372 |
2/2✓ Branch 0 taken 6 times.
✓ Branch 1 taken 18 times.
|
24 | if (needed_capacity > *capacity) { |
| 373 | 6 | size_t new_capacity = cx_array_align_capacity(needed_capacity, 16, SIZE_MAX); | |
| 374 | 6 | void *new_mem = reallocator->realloc( | |
| 375 | *target, new_capacity, elem_size, reallocator | ||
| 376 | ); | ||
| 377 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
|
6 | if (new_mem == NULL) { |
| 378 | // give it up right away, there is no contract | ||
| 379 | // that requires us to insert as much as we can | ||
| 380 | − | return 1; // LCOV_EXCL_LINE | |
| 381 | } | ||
| 382 | 6 | *target = new_mem; | |
| 383 | 6 | *capacity = new_capacity; | |
| 384 | } | ||
| 385 | |||
| 386 | // now we have guaranteed that we can insert everything | ||
| 387 | 24 | size_t new_size = old_size + elem_count; | |
| 388 | 24 | *size = new_size; | |
| 389 | |||
| 390 | // declare the source and destination indices/pointers | ||
| 391 | 24 | size_t si = 0, di = 0; | |
| 392 | 24 | const char *src = sorted_data; | |
| 393 | 24 | char *dest = *target; | |
| 394 | |||
| 395 | // find the first insertion point | ||
| 396 | 24 | di = cx_array_binary_search_sup(dest, old_size, elem_size, src, cmp_func); | |
| 397 | 24 | dest += di * elem_size; | |
| 398 | |||
| 399 | // move the remaining elements in the array completely to the right | ||
| 400 | // we will call it the "buffer" for parked elements | ||
| 401 | 24 | size_t buf_size = old_size - di; | |
| 402 | 24 | size_t bi = new_size - buf_size; | |
| 403 | 24 | char *bptr = ((char *) *target) + bi * elem_size; | |
| 404 | 24 | memmove(bptr, dest, buf_size * elem_size); | |
| 405 | |||
| 406 | // while there are both source and buffered elements left, | ||
| 407 | // copy them interleaving | ||
| 408 |
3/4✓ Branch 0 taken 39 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 30 times.
✓ Branch 3 taken 9 times.
|
39 | while (si < elem_count && bi < new_size) { |
| 409 | // determine how many source elements can be inserted | ||
| 410 | size_t copy_len, bytes_copied; | ||
| 411 | 30 | copy_len = cx_array_binary_search_sup( | |
| 412 | src, | ||
| 413 | elem_count - si, | ||
| 414 | elem_size, | ||
| 415 | bptr, | ||
| 416 | cmp_func | ||
| 417 | ); | ||
| 418 | |||
| 419 | // copy the source elements | ||
| 420 | 30 | bytes_copied = copy_len * elem_size; | |
| 421 | 30 | memcpy(dest, src, bytes_copied); | |
| 422 | 30 | dest += bytes_copied; | |
| 423 | 30 | src += bytes_copied; | |
| 424 | 30 | si += copy_len; | |
| 425 | |||
| 426 | // when all source elements are in place, we are done | ||
| 427 |
2/2✓ Branch 0 taken 15 times.
✓ Branch 1 taken 15 times.
|
30 | if (si >= elem_count) break; |
| 428 | |||
| 429 | // determine how many buffered elements need to be restored | ||
| 430 | 15 | copy_len = cx_array_binary_search_sup( | |
| 431 | bptr, | ||
| 432 | new_size - bi, | ||
| 433 | elem_size, | ||
| 434 | src, | ||
| 435 | cmp_func | ||
| 436 | ); | ||
| 437 | |||
| 438 | // restore the buffered elements | ||
| 439 | 15 | bytes_copied = copy_len * elem_size; | |
| 440 | 15 | memmove(dest, bptr, bytes_copied); | |
| 441 | 15 | dest += bytes_copied; | |
| 442 | 15 | bptr += bytes_copied; | |
| 443 | 15 | bi += copy_len; | |
| 444 | } | ||
| 445 | |||
| 446 | // still source elements left? simply append them | ||
| 447 |
2/2✓ Branch 0 taken 9 times.
✓ Branch 1 taken 15 times.
|
24 | if (si < elem_count) { |
| 448 | 9 | memcpy(dest, src, elem_size * (elem_count - si)); | |
| 449 | } | ||
| 450 | |||
| 451 | // still buffer elements left? | ||
| 452 | // don't worry, we already moved them to the correct place | ||
| 453 | |||
| 454 | 24 | return 0; | |
| 455 | } | ||
| 456 | |||
| 457 | 253 | size_t cx_array_binary_search_inf( | |
| 458 | const void *arr, | ||
| 459 | size_t size, | ||
| 460 | size_t elem_size, | ||
| 461 | const void *elem, | ||
| 462 | cx_compare_func cmp_func | ||
| 463 | ) { | ||
| 464 | // special case: empty array | ||
| 465 |
2/2✓ Branch 0 taken 44 times.
✓ Branch 1 taken 209 times.
|
253 | if (size == 0) return 0; |
| 466 | |||
| 467 | // declare a variable that will contain the compare results | ||
| 468 | int result; | ||
| 469 | |||
| 470 | // cast the array pointer to something we can use offsets with | ||
| 471 | 209 | const char *array = arr; | |
| 472 | |||
| 473 | // check the first array element | ||
| 474 | 209 | result = cmp_func(elem, array); | |
| 475 |
2/2✓ Branch 0 taken 27 times.
✓ Branch 1 taken 182 times.
|
209 | if (result < 0) { |
| 476 | 27 | return size; | |
| 477 |
2/2✓ Branch 0 taken 17 times.
✓ Branch 1 taken 165 times.
|
182 | } else if (result == 0) { |
| 478 | 17 | return 0; | |
| 479 | } | ||
| 480 | |||
| 481 | // special case: there is only one element and that is smaller | ||
| 482 |
2/2✓ Branch 0 taken 30 times.
✓ Branch 1 taken 135 times.
|
165 | if (size == 1) return 0; |
| 483 | |||
| 484 | // check the last array element | ||
| 485 | 135 | result = cmp_func(elem, array + elem_size * (size - 1)); | |
| 486 |
2/2✓ Branch 0 taken 25 times.
✓ Branch 1 taken 110 times.
|
135 | if (result >= 0) { |
| 487 | 25 | return size - 1; | |
| 488 | } | ||
| 489 | |||
| 490 | // the element is now guaranteed to be somewhere in the list | ||
| 491 | // so start the binary search | ||
| 492 | 110 | size_t left_index = 1; | |
| 493 | 110 | size_t right_index = size - 1; | |
| 494 | size_t pivot_index; | ||
| 495 | |||
| 496 |
2/2✓ Branch 0 taken 300 times.
✓ Branch 1 taken 75 times.
|
375 | while (left_index <= right_index) { |
| 497 | 300 | pivot_index = left_index + (right_index - left_index) / 2; | |
| 498 | 300 | const char *arr_elem = array + pivot_index * elem_size; | |
| 499 | 300 | result = cmp_func(elem, arr_elem); | |
| 500 |
2/2✓ Branch 0 taken 35 times.
✓ Branch 1 taken 265 times.
|
300 | if (result == 0) { |
| 501 | // found it! | ||
| 502 | 35 | return pivot_index; | |
| 503 |
2/2✓ Branch 0 taken 134 times.
✓ Branch 1 taken 131 times.
|
265 | } else if (result < 0) { |
| 504 | // element is smaller than pivot, continue search left | ||
| 505 | 134 | right_index = pivot_index - 1; | |
| 506 | } else { | ||
| 507 | // element is larger than pivot, continue search right | ||
| 508 | 131 | left_index = pivot_index + 1; | |
| 509 | } | ||
| 510 | } | ||
| 511 | |||
| 512 | // report the largest upper bound | ||
| 513 |
2/2✓ Branch 0 taken 58 times.
✓ Branch 1 taken 17 times.
|
75 | return result < 0 ? (pivot_index - 1) : pivot_index; |
| 514 | } | ||
| 515 | |||
| 516 | 68 | size_t cx_array_binary_search( | |
| 517 | const void *arr, | ||
| 518 | size_t size, | ||
| 519 | size_t elem_size, | ||
| 520 | const void *elem, | ||
| 521 | cx_compare_func cmp_func | ||
| 522 | ) { | ||
| 523 | 68 | size_t index = cx_array_binary_search_inf( | |
| 524 | arr, size, elem_size, elem, cmp_func | ||
| 525 | ); | ||
| 526 |
4/4✓ Branch 0 taken 63 times.
✓ Branch 1 taken 5 times.
✓ Branch 2 taken 55 times.
✓ Branch 3 taken 8 times.
|
131 | if (index < size && |
| 527 | 63 | cmp_func(((const char *) arr) + index * elem_size, elem) == 0) { | |
| 528 | 55 | return index; | |
| 529 | } else { | ||
| 530 | 13 | return size; | |
| 531 | } | ||
| 532 | } | ||
| 533 | |||
| 534 | 173 | size_t cx_array_binary_search_sup( | |
| 535 | const void *arr, | ||
| 536 | size_t size, | ||
| 537 | size_t elem_size, | ||
| 538 | const void *elem, | ||
| 539 | cx_compare_func cmp_func | ||
| 540 | ) { | ||
| 541 | 173 | size_t inf = cx_array_binary_search_inf( | |
| 542 | arr, size, elem_size, elem, cmp_func | ||
| 543 | ); | ||
| 544 |
2/2✓ Branch 0 taken 63 times.
✓ Branch 1 taken 110 times.
|
173 | if (inf == size) { |
| 545 | // no infimum means, first element is supremum | ||
| 546 | 63 | return 0; | |
| 547 |
2/2✓ Branch 1 taken 3 times.
✓ Branch 2 taken 107 times.
|
110 | } else if (cmp_func(((const char *) arr) + inf * elem_size, elem) == 0) { |
| 548 | 3 | return inf; | |
| 549 | } else { | ||
| 550 | 107 | return inf + 1; | |
| 551 | } | ||
| 552 | } | ||
| 553 | |||
| 554 | #ifndef CX_ARRAY_SWAP_SBO_SIZE | ||
| 555 | #define CX_ARRAY_SWAP_SBO_SIZE 128 | ||
| 556 | #endif | ||
| 557 | const unsigned cx_array_swap_sbo_size = CX_ARRAY_SWAP_SBO_SIZE; | ||
| 558 | |||
| 559 | 74 | void cx_array_swap( | |
| 560 | void *arr, | ||
| 561 | size_t elem_size, | ||
| 562 | size_t idx1, | ||
| 563 | size_t idx2 | ||
| 564 | ) { | ||
| 565 | assert(arr != NULL); | ||
| 566 | |||
| 567 | // short circuit | ||
| 568 |
2/2✓ Branch 0 taken 3 times.
✓ Branch 1 taken 71 times.
|
74 | if (idx1 == idx2) return; |
| 569 | |||
| 570 | char sbo_mem[CX_ARRAY_SWAP_SBO_SIZE]; | ||
| 571 | void *tmp; | ||
| 572 | |||
| 573 | // decide if we can use the local buffer | ||
| 574 |
2/2✓ Branch 0 taken 7 times.
✓ Branch 1 taken 64 times.
|
71 | if (elem_size > CX_ARRAY_SWAP_SBO_SIZE) { |
| 575 | 7 | tmp = malloc(elem_size); | |
| 576 | // we don't want to enforce error handling | ||
| 577 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 7 times.
|
7 | if (tmp == NULL) abort(); |
| 578 | } else { | ||
| 579 | 64 | tmp = sbo_mem; | |
| 580 | } | ||
| 581 | |||
| 582 | // calculate memory locations | ||
| 583 | 71 | char *left = arr, *right = arr; | |
| 584 | 71 | left += idx1 * elem_size; | |
| 585 | 71 | right += idx2 * elem_size; | |
| 586 | |||
| 587 | // three-way swap | ||
| 588 | 71 | memcpy(tmp, left, elem_size); | |
| 589 | 71 | memcpy(left, right, elem_size); | |
| 590 | 71 | memcpy(right, tmp, elem_size); | |
| 591 | |||
| 592 | // free dynamic memory, if it was needed | ||
| 593 |
2/2✓ Branch 0 taken 7 times.
✓ Branch 1 taken 64 times.
|
71 | if (tmp != sbo_mem) { |
| 594 | 7 | free(tmp); | |
| 595 | } | ||
| 596 | } | ||
| 597 | |||
| 598 | // HIGH LEVEL ARRAY LIST FUNCTIONS | ||
| 599 | |||
| 600 | typedef struct { | ||
| 601 | struct cx_list_s base; | ||
| 602 | void *data; | ||
| 603 | size_t capacity; | ||
| 604 | CxArrayReallocator reallocator; | ||
| 605 | } cx_array_list; | ||
| 606 | |||
| 607 | 80 | static void cx_arl_destructor(struct cx_list_s *list) { | |
| 608 | 80 | cx_array_list *arl = (cx_array_list *) list; | |
| 609 | |||
| 610 | 80 | char *ptr = arl->data; | |
| 611 | |||
| 612 |
2/2✓ Branch 0 taken 5 times.
✓ Branch 1 taken 75 times.
|
80 | if (list->collection.simple_destructor) { |
| 613 |
2/2✓ Branch 0 taken 25 times.
✓ Branch 1 taken 5 times.
|
30 | for (size_t i = 0; i < list->collection.size; i++) { |
| 614 |
2/2✓ Branch 0 taken 13 times.
✓ Branch 1 taken 12 times.
|
25 | cx_invoke_simple_destructor(list, ptr); |
| 615 | 25 | ptr += list->collection.elem_size; | |
| 616 | } | ||
| 617 | } | ||
| 618 |
2/2✓ Branch 0 taken 3 times.
✓ Branch 1 taken 77 times.
|
80 | if (list->collection.advanced_destructor) { |
| 619 |
2/2✓ Branch 0 taken 1 times.
✓ Branch 1 taken 3 times.
|
4 | for (size_t i = 0; i < list->collection.size; i++) { |
| 620 |
1/2✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
|
1 | cx_invoke_advanced_destructor(list, ptr); |
| 621 | 1 | ptr += list->collection.elem_size; | |
| 622 | } | ||
| 623 | } | ||
| 624 | |||
| 625 | 80 | cxFree(list->collection.allocator, arl->data); | |
| 626 | 80 | cxFree(list->collection.allocator, list); | |
| 627 | 80 | } | |
| 628 | |||
| 629 | 3859 | static size_t cx_arl_insert_array( | |
| 630 | struct cx_list_s *list, | ||
| 631 | size_t index, | ||
| 632 | const void *array, | ||
| 633 | size_t n | ||
| 634 | ) { | ||
| 635 | // out of bounds and special case check | ||
| 636 |
3/4✓ Branch 0 taken 3857 times.
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 3857 times.
|
3859 | if (index > list->collection.size || n == 0) return 0; |
| 637 | |||
| 638 | // get a correctly typed pointer to the list | ||
| 639 | 3857 | cx_array_list *arl = (cx_array_list *) list; | |
| 640 | |||
| 641 | // do we need to move some elements? | ||
| 642 |
2/2✓ Branch 0 taken 80 times.
✓ Branch 1 taken 3777 times.
|
3857 | if (index < list->collection.size) { |
| 643 | 80 | const char *first_to_move = (const char *) arl->data; | |
| 644 | 80 | first_to_move += index * list->collection.elem_size; | |
| 645 | 80 | size_t elems_to_move = list->collection.size - index; | |
| 646 | 80 | size_t start_of_moved = index + n; | |
| 647 | |||
| 648 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 80 times.
|
80 | if (cx_array_copy( |
| 649 | &arl->data, | ||
| 650 | 80 | &list->collection.size, | |
| 651 | 80 | &arl->capacity, | |
| 652 | 0, | ||
| 653 | start_of_moved, | ||
| 654 | first_to_move, | ||
| 655 | list->collection.elem_size, | ||
| 656 | elems_to_move, | ||
| 657 | &arl->reallocator | ||
| 658 | )) { | ||
| 659 | // if moving existing elems is unsuccessful, abort | ||
| 660 | ✗ | return 0; | |
| 661 | } | ||
| 662 | } | ||
| 663 | |||
| 664 | // note that if we had to move the elements, the following operation | ||
| 665 | // is guaranteed to succeed, because we have the memory already allocated | ||
| 666 | // therefore, it is impossible to leave this function with an invalid array | ||
| 667 | |||
| 668 | // place the new elements | ||
| 669 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 3857 times.
|
3857 | if (cx_array_copy( |
| 670 | &arl->data, | ||
| 671 | 3857 | &list->collection.size, | |
| 672 | 3857 | &arl->capacity, | |
| 673 | 0, | ||
| 674 | index, | ||
| 675 | array, | ||
| 676 | list->collection.elem_size, | ||
| 677 | n, | ||
| 678 | &arl->reallocator | ||
| 679 | )) { | ||
| 680 | // array list implementation is "all or nothing" | ||
| 681 | ✗ | return 0; | |
| 682 | } else { | ||
| 683 | 3857 | return n; | |
| 684 | } | ||
| 685 | } | ||
| 686 | |||
| 687 | 16 | static size_t cx_arl_insert_sorted( | |
| 688 | struct cx_list_s *list, | ||
| 689 | const void *sorted_data, | ||
| 690 | size_t n | ||
| 691 | ) { | ||
| 692 | // get a correctly typed pointer to the list | ||
| 693 | 16 | cx_array_list *arl = (cx_array_list *) list; | |
| 694 | |||
| 695 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 16 times.
|
16 | if (cx_array_insert_sorted( |
| 696 | &arl->data, | ||
| 697 | &list->collection.size, | ||
| 698 | &arl->capacity, | ||
| 699 | list->collection.cmpfunc, | ||
| 700 | sorted_data, | ||
| 701 | list->collection.elem_size, | ||
| 702 | n, | ||
| 703 | &arl->reallocator | ||
| 704 | )) { | ||
| 705 | // array list implementation is "all or nothing" | ||
| 706 | ✗ | return 0; | |
| 707 | } else { | ||
| 708 | 16 | return n; | |
| 709 | } | ||
| 710 | } | ||
| 711 | |||
| 712 | 3838 | static int cx_arl_insert_element( | |
| 713 | struct cx_list_s *list, | ||
| 714 | size_t index, | ||
| 715 | const void *element | ||
| 716 | ) { | ||
| 717 | 3838 | return 1 != cx_arl_insert_array(list, index, element, 1); | |
| 718 | } | ||
| 719 | |||
| 720 | 10 | static int cx_arl_insert_iter( | |
| 721 | struct cx_iterator_s *iter, | ||
| 722 | const void *elem, | ||
| 723 | int prepend | ||
| 724 | ) { | ||
| 725 | 10 | struct cx_list_s *list = iter->src_handle.m; | |
| 726 |
2/2✓ Branch 0 taken 6 times.
✓ Branch 1 taken 4 times.
|
10 | if (iter->index < list->collection.size) { |
| 727 | 6 | int result = cx_arl_insert_element( | |
| 728 | list, | ||
| 729 | 6 | iter->index + 1 - prepend, | |
| 730 | elem | ||
| 731 | ); | ||
| 732 |
1/2✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
|
6 | if (result == 0) { |
| 733 | 6 | iter->elem_count++; | |
| 734 |
2/2✓ Branch 0 taken 4 times.
✓ Branch 1 taken 2 times.
|
6 | if (prepend != 0) { |
| 735 | 4 | iter->index++; | |
| 736 | 4 | iter->elem_handle = ((char *) iter->elem_handle) + list->collection.elem_size; | |
| 737 | } | ||
| 738 | } | ||
| 739 | 6 | return result; | |
| 740 | } else { | ||
| 741 | 4 | int result = cx_arl_insert_element(list, list->collection.size, elem); | |
| 742 |
1/2✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
|
4 | if (result == 0) { |
| 743 | 4 | iter->elem_count++; | |
| 744 | 4 | iter->index = list->collection.size; | |
| 745 | } | ||
| 746 | 4 | return result; | |
| 747 | } | ||
| 748 | } | ||
| 749 | |||
| 750 | 84 | static size_t cx_arl_remove( | |
| 751 | struct cx_list_s *list, | ||
| 752 | size_t index, | ||
| 753 | size_t num, | ||
| 754 | void *targetbuf | ||
| 755 | ) { | ||
| 756 | 84 | cx_array_list *arl = (cx_array_list *) list; | |
| 757 | |||
| 758 | // out-of-bounds check | ||
| 759 | size_t remove; | ||
| 760 |
2/2✓ Branch 0 taken 2 times.
✓ Branch 1 taken 82 times.
|
84 | if (index >= list->collection.size) { |
| 761 | 2 | remove = 0; | |
| 762 |
2/2✓ Branch 0 taken 2 times.
✓ Branch 1 taken 80 times.
|
82 | } else if (index + num > list->collection.size) { |
| 763 | 2 | remove = list->collection.size - index; | |
| 764 | } else { | ||
| 765 | 80 | remove = num; | |
| 766 | } | ||
| 767 | |||
| 768 | // easy exit | ||
| 769 |
2/2✓ Branch 0 taken 2 times.
✓ Branch 1 taken 82 times.
|
84 | if (remove == 0) return 0; |
| 770 | |||
| 771 | // destroy or copy contents | ||
| 772 |
2/2✓ Branch 0 taken 78 times.
✓ Branch 1 taken 4 times.
|
82 | if (targetbuf == NULL) { |
| 773 |
2/2✓ Branch 0 taken 92 times.
✓ Branch 1 taken 78 times.
|
170 | for (size_t idx = index; idx < index + remove; idx++) { |
| 774 |
8/8✓ Branch 0 taken 24 times.
✓ Branch 1 taken 68 times.
✓ Branch 2 taken 12 times.
✓ Branch 3 taken 12 times.
✓ Branch 5 taken 8 times.
✓ Branch 6 taken 84 times.
✓ Branch 7 taken 4 times.
✓ Branch 8 taken 4 times.
|
92 | cx_invoke_destructor( |
| 775 | list, | ||
| 776 | ((char *) arl->data) + idx * list->collection.elem_size | ||
| 777 | ); | ||
| 778 | } | ||
| 779 | } else { | ||
| 780 | 4 | memcpy( | |
| 781 | targetbuf, | ||
| 782 | 4 | ((char *) arl->data) + index * list->collection.elem_size, | |
| 783 | 4 | remove * list->collection.elem_size | |
| 784 | ); | ||
| 785 | } | ||
| 786 | |||
| 787 | // short-circuit removal of last elements | ||
| 788 |
2/2✓ Branch 0 taken 4 times.
✓ Branch 1 taken 78 times.
|
82 | if (index + remove == list->collection.size) { |
| 789 | 4 | list->collection.size -= remove; | |
| 790 | 4 | return remove; | |
| 791 | } | ||
| 792 | |||
| 793 | // just move the elements to the left | ||
| 794 | 78 | cx_array_copy( | |
| 795 | &arl->data, | ||
| 796 | 78 | &list->collection.size, | |
| 797 | 78 | &arl->capacity, | |
| 798 | 0, | ||
| 799 | index, | ||
| 800 | 78 | ((char *) arl->data) + (index + remove) * list->collection.elem_size, | |
| 801 | list->collection.elem_size, | ||
| 802 | 78 | list->collection.size - index - remove, | |
| 803 | &arl->reallocator | ||
| 804 | ); | ||
| 805 | |||
| 806 | // decrease the size | ||
| 807 | 78 | list->collection.size -= remove; | |
| 808 | |||
| 809 | 78 | return remove; | |
| 810 | } | ||
| 811 | |||
| 812 | 6 | static void cx_arl_clear(struct cx_list_s *list) { | |
| 813 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
|
6 | if (list->collection.size == 0) return; |
| 814 | |||
| 815 | 6 | cx_array_list *arl = (cx_array_list *) list; | |
| 816 | 6 | char *ptr = arl->data; | |
| 817 | |||
| 818 |
2/2✓ Branch 0 taken 2 times.
✓ Branch 1 taken 4 times.
|
6 | if (list->collection.simple_destructor) { |
| 819 |
2/2✓ Branch 0 taken 112 times.
✓ Branch 1 taken 2 times.
|
114 | for (size_t i = 0; i < list->collection.size; i++) { |
| 820 |
2/2✓ Branch 0 taken 56 times.
✓ Branch 1 taken 56 times.
|
112 | cx_invoke_simple_destructor(list, ptr); |
| 821 | 112 | ptr += list->collection.elem_size; | |
| 822 | } | ||
| 823 | } | ||
| 824 |
2/2✓ Branch 0 taken 2 times.
✓ Branch 1 taken 4 times.
|
6 | if (list->collection.advanced_destructor) { |
| 825 |
2/2✓ Branch 0 taken 142 times.
✓ Branch 1 taken 2 times.
|
144 | for (size_t i = 0; i < list->collection.size; i++) { |
| 826 |
2/2✓ Branch 0 taken 71 times.
✓ Branch 1 taken 71 times.
|
142 | cx_invoke_advanced_destructor(list, ptr); |
| 827 | 142 | ptr += list->collection.elem_size; | |
| 828 | } | ||
| 829 | } | ||
| 830 | |||
| 831 | 6 | memset(arl->data, 0, list->collection.size * list->collection.elem_size); | |
| 832 | 6 | list->collection.size = 0; | |
| 833 | } | ||
| 834 | |||
| 835 | 33 | static int cx_arl_swap( | |
| 836 | struct cx_list_s *list, | ||
| 837 | size_t i, | ||
| 838 | size_t j | ||
| 839 | ) { | ||
| 840 |
4/4✓ Branch 0 taken 27 times.
✓ Branch 1 taken 6 times.
✓ Branch 2 taken 3 times.
✓ Branch 3 taken 24 times.
|
33 | if (i >= list->collection.size || j >= list->collection.size) return 1; |
| 841 | 24 | cx_array_list *arl = (cx_array_list *) list; | |
| 842 | 24 | cx_array_swap(arl->data, list->collection.elem_size, i, j); | |
| 843 | 24 | return 0; | |
| 844 | } | ||
| 845 | |||
| 846 | 3964 | static void *cx_arl_at( | |
| 847 | const struct cx_list_s *list, | ||
| 848 | size_t index | ||
| 849 | ) { | ||
| 850 |
2/2✓ Branch 0 taken 3956 times.
✓ Branch 1 taken 8 times.
|
3964 | if (index < list->collection.size) { |
| 851 | 3956 | const cx_array_list *arl = (const cx_array_list *) list; | |
| 852 | 3956 | char *space = arl->data; | |
| 853 | 3956 | return space + index * list->collection.elem_size; | |
| 854 | } else { | ||
| 855 | 8 | return NULL; | |
| 856 | } | ||
| 857 | } | ||
| 858 | |||
| 859 | 68 | static size_t cx_arl_find_remove( | |
| 860 | struct cx_list_s *list, | ||
| 861 | const void *elem, | ||
| 862 | bool remove | ||
| 863 | ) { | ||
| 864 | assert(list != NULL); | ||
| 865 | assert(list->collection.cmpfunc != NULL); | ||
| 866 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 68 times.
|
68 | if (list->collection.size == 0) return 0; |
| 867 | 68 | char *cur = ((const cx_array_list *) list)->data; | |
| 868 | |||
| 869 | // optimize with binary search, when sorted | ||
| 870 |
2/2✓ Branch 0 taken 8 times.
✓ Branch 1 taken 60 times.
|
68 | if (list->collection.sorted) { |
| 871 | 8 | size_t i = cx_array_binary_search( | |
| 872 | cur, | ||
| 873 | list->collection.size, | ||
| 874 | list->collection.elem_size, | ||
| 875 | elem, | ||
| 876 | list->collection.cmpfunc | ||
| 877 | ); | ||
| 878 |
4/4✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
✓ Branch 2 taken 2 times.
✓ Branch 3 taken 2 times.
|
8 | if (remove && i < list->collection.size) { |
| 879 | 2 | cx_arl_remove(list, i, 1, NULL); | |
| 880 | } | ||
| 881 | 8 | return i; | |
| 882 | } | ||
| 883 | |||
| 884 | // fallback: linear search | ||
| 885 |
2/2✓ Branch 0 taken 16048 times.
✓ Branch 1 taken 6 times.
|
16054 | for (size_t i = 0; i < list->collection.size; i++) { |
| 886 |
2/2✓ Branch 1 taken 54 times.
✓ Branch 2 taken 15994 times.
|
16048 | if (0 == list->collection.cmpfunc(elem, cur)) { |
| 887 |
2/2✓ Branch 0 taken 2 times.
✓ Branch 1 taken 52 times.
|
54 | if (remove) { |
| 888 | 2 | cx_arl_remove(list, i, 1, NULL); | |
| 889 | } | ||
| 890 | 54 | return i; | |
| 891 | } | ||
| 892 | 15994 | cur += list->collection.elem_size; | |
| 893 | } | ||
| 894 | 6 | return list->collection.size; | |
| 895 | } | ||
| 896 | |||
| 897 | 4 | static void cx_arl_sort(struct cx_list_s *list) { | |
| 898 | assert(list->collection.cmpfunc != NULL); | ||
| 899 | 4 | qsort(((cx_array_list *) list)->data, | |
| 900 | list->collection.size, | ||
| 901 | list->collection.elem_size, | ||
| 902 | 4 | list->collection.cmpfunc | |
| 903 | ); | ||
| 904 | 4 | } | |
| 905 | |||
| 906 | 14 | static int cx_arl_compare( | |
| 907 | const struct cx_list_s *list, | ||
| 908 | const struct cx_list_s *other | ||
| 909 | ) { | ||
| 910 | assert(list->collection.cmpfunc != NULL); | ||
| 911 |
2/2✓ Branch 0 taken 10 times.
✓ Branch 1 taken 4 times.
|
14 | if (list->collection.size == other->collection.size) { |
| 912 | 10 | const char *left = ((const cx_array_list *) list)->data; | |
| 913 | 10 | const char *right = ((const cx_array_list *) other)->data; | |
| 914 |
2/2✓ Branch 0 taken 352 times.
✓ Branch 1 taken 6 times.
|
358 | for (size_t i = 0; i < list->collection.size; i++) { |
| 915 | 352 | int d = list->collection.cmpfunc(left, right); | |
| 916 |
2/2✓ Branch 0 taken 4 times.
✓ Branch 1 taken 348 times.
|
352 | if (d != 0) { |
| 917 | 4 | return d; | |
| 918 | } | ||
| 919 | 348 | left += list->collection.elem_size; | |
| 920 | 348 | right += other->collection.elem_size; | |
| 921 | } | ||
| 922 | 6 | return 0; | |
| 923 | } else { | ||
| 924 |
2/2✓ Branch 0 taken 2 times.
✓ Branch 1 taken 2 times.
|
4 | return list->collection.size < other->collection.size ? -1 : 1; |
| 925 | } | ||
| 926 | } | ||
| 927 | |||
| 928 | 2 | static void cx_arl_reverse(struct cx_list_s *list) { | |
| 929 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 2 times.
|
2 | if (list->collection.size < 2) return; |
| 930 | 2 | void *data = ((const cx_array_list *) list)->data; | |
| 931 | 2 | size_t half = list->collection.size / 2; | |
| 932 |
2/2✓ Branch 0 taken 50 times.
✓ Branch 1 taken 2 times.
|
52 | for (size_t i = 0; i < half; i++) { |
| 933 | 50 | cx_array_swap(data, list->collection.elem_size, i, list->collection.size - 1 - i); | |
| 934 | } | ||
| 935 | } | ||
| 936 | |||
| 937 | 490 | static bool cx_arl_iter_valid(const void *it) { | |
| 938 | 490 | const struct cx_iterator_s *iter = it; | |
| 939 | 490 | const struct cx_list_s *list = iter->src_handle.c; | |
| 940 | 490 | return iter->index < list->collection.size; | |
| 941 | } | ||
| 942 | |||
| 943 | 4188 | static void *cx_arl_iter_current(const void *it) { | |
| 944 | 4188 | const struct cx_iterator_s *iter = it; | |
| 945 | 4188 | return iter->elem_handle; | |
| 946 | } | ||
| 947 | |||
| 948 | 3910 | static void cx_arl_iter_next(void *it) { | |
| 949 | 3910 | struct cx_iterator_s *iter = it; | |
| 950 |
2/2✓ Branch 0 taken 30 times.
✓ Branch 1 taken 3880 times.
|
3910 | if (iter->base.remove) { |
| 951 | 30 | iter->base.remove = false; | |
| 952 | 30 | cx_arl_remove(iter->src_handle.m, iter->index, 1, NULL); | |
| 953 | } else { | ||
| 954 | 3880 | iter->index++; | |
| 955 | 3880 | iter->elem_handle = | |
| 956 | 3880 | ((char *) iter->elem_handle) | |
| 957 | 3880 | + ((const struct cx_list_s *) iter->src_handle.c)->collection.elem_size; | |
| 958 | } | ||
| 959 | 3910 | } | |
| 960 | |||
| 961 | 238 | static void cx_arl_iter_prev(void *it) { | |
| 962 | 238 | struct cx_iterator_s *iter = it; | |
| 963 | 238 | const cx_array_list *list = iter->src_handle.c; | |
| 964 |
2/2✓ Branch 0 taken 28 times.
✓ Branch 1 taken 210 times.
|
238 | if (iter->base.remove) { |
| 965 | 28 | iter->base.remove = false; | |
| 966 | 28 | cx_arl_remove(iter->src_handle.m, iter->index, 1, NULL); | |
| 967 | } | ||
| 968 | 238 | iter->index--; | |
| 969 |
2/2✓ Branch 0 taken 229 times.
✓ Branch 1 taken 9 times.
|
238 | if (iter->index < list->base.collection.size) { |
| 970 | 229 | iter->elem_handle = ((char *) list->data) | |
| 971 | 229 | + iter->index * list->base.collection.elem_size; | |
| 972 | } | ||
| 973 | 238 | } | |
| 974 | |||
| 975 | |||
| 976 | 156 | static struct cx_iterator_s cx_arl_iterator( | |
| 977 | const struct cx_list_s *list, | ||
| 978 | size_t index, | ||
| 979 | bool backwards | ||
| 980 | ) { | ||
| 981 | struct cx_iterator_s iter; | ||
| 982 | |||
| 983 | 156 | iter.index = index; | |
| 984 | 156 | iter.src_handle.c = list; | |
| 985 | 156 | iter.elem_handle = cx_arl_at(list, index); | |
| 986 | 156 | iter.elem_size = list->collection.elem_size; | |
| 987 | 156 | iter.elem_count = list->collection.size; | |
| 988 | 156 | iter.base.valid = cx_arl_iter_valid; | |
| 989 | 156 | iter.base.current = cx_arl_iter_current; | |
| 990 |
2/2✓ Branch 0 taken 13 times.
✓ Branch 1 taken 143 times.
|
156 | iter.base.next = backwards ? cx_arl_iter_prev : cx_arl_iter_next; |
| 991 | 156 | iter.base.remove = false; | |
| 992 | 156 | iter.base.mutating = false; | |
| 993 | |||
| 994 | 156 | return iter; | |
| 995 | } | ||
| 996 | |||
| 997 | static cx_list_class cx_array_list_class = { | ||
| 998 | cx_arl_destructor, | ||
| 999 | cx_arl_insert_element, | ||
| 1000 | cx_arl_insert_array, | ||
| 1001 | cx_arl_insert_sorted, | ||
| 1002 | cx_arl_insert_iter, | ||
| 1003 | cx_arl_remove, | ||
| 1004 | cx_arl_clear, | ||
| 1005 | cx_arl_swap, | ||
| 1006 | cx_arl_at, | ||
| 1007 | cx_arl_find_remove, | ||
| 1008 | cx_arl_sort, | ||
| 1009 | cx_arl_compare, | ||
| 1010 | cx_arl_reverse, | ||
| 1011 | cx_arl_iterator, | ||
| 1012 | }; | ||
| 1013 | |||
| 1014 | 80 | CxList *cxArrayListCreate( | |
| 1015 | const CxAllocator *allocator, | ||
| 1016 | cx_compare_func comparator, | ||
| 1017 | size_t elem_size, | ||
| 1018 | size_t initial_capacity | ||
| 1019 | ) { | ||
| 1020 |
2/2✓ Branch 0 taken 3 times.
✓ Branch 1 taken 77 times.
|
80 | if (allocator == NULL) { |
| 1021 | 3 | allocator = cxDefaultAllocator; | |
| 1022 | } | ||
| 1023 | |||
| 1024 | 80 | cx_array_list *list = cxCalloc(allocator, 1, sizeof(cx_array_list)); | |
| 1025 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 80 times.
|
80 | if (list == NULL) return NULL; |
| 1026 | 80 | cx_list_init((CxList*)list, &cx_array_list_class, | |
| 1027 | allocator, comparator, elem_size); | ||
| 1028 | 80 | list->capacity = initial_capacity; | |
| 1029 | |||
| 1030 | // allocate the array after the real elem_size is known | ||
| 1031 | 80 | list->data = cxCalloc(allocator, initial_capacity, | |
| 1032 | list->base.collection.elem_size); | ||
| 1033 | − | if (list->data == NULL) { // LCOV_EXCL_START | |
| 1034 | − | cxFree(allocator, list); | |
| 1035 | − | return NULL; | |
| 1036 | } // LCOV_EXCL_STOP | ||
| 1037 | |||
| 1038 | // configure the reallocator | ||
| 1039 | 80 | list->reallocator = cx_array_reallocator(allocator, NULL); | |
| 1040 | |||
| 1041 | 80 | return (CxList *) list; | |
| 1042 | } | ||
| 1043 |