UNIXworkcode

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 <assert.h> 31 #include <string.h> 32 33 // LOW LEVEL ARRAY LIST FUNCTIONS 34 35 enum cx_array_copy_result cx_array_copy( 36 void **target, 37 size_t *size, 38 size_t *capacity, 39 size_t index, 40 void const *src, 41 size_t elem_size, 42 size_t elem_count, 43 struct cx_array_reallocator_s *reallocator 44 ) { 45 // assert pointers 46 assert(target != NULL); 47 assert(size != NULL); 48 assert(src != NULL); 49 50 // determine capacity 51 size_t cap = capacity == NULL ? *size : *capacity; 52 53 // check if resize is required 54 size_t minsize = index + elem_count; 55 size_t newsize = *size < minsize ? minsize : *size; 56 bool needrealloc = newsize > cap; 57 58 // reallocate if possible 59 if (needrealloc) { 60 // a reallocator and a capacity variable must be available 61 if (reallocator == NULL || capacity == NULL) { 62 return CX_ARRAY_COPY_REALLOC_NOT_SUPPORTED; 63 } 64 65 // check, if we need to repair the src pointer 66 uintptr_t targetaddr = (uintptr_t) *target; 67 uintptr_t srcaddr = (uintptr_t) src; 68 bool repairsrc = targetaddr <= srcaddr 69 && srcaddr < targetaddr + cap * elem_size; 70 71 // calculate new capacity (next number divisible by 16) 72 cap = newsize - (newsize % 16) + 16; 73 assert(cap > newsize); 74 75 // perform reallocation 76 void *newmem = reallocator->realloc( 77 *target, cap, elem_size, reallocator 78 ); 79 if (newmem == NULL) { 80 return CX_ARRAY_COPY_REALLOC_FAILED; 81 } 82 83 // repair src pointer, if necessary 84 if (repairsrc) { 85 src = ((char *) newmem) + (srcaddr - targetaddr); 86 } 87 88 // store new pointer and capacity 89 *target = newmem; 90 *capacity = cap; 91 } 92 93 // determine target pointer 94 char *start = *target; 95 start += index * elem_size; 96 97 // copy elements and set new size 98 memmove(start, src, elem_count * elem_size); 99 *size = newsize; 100 101 // return successfully 102 return CX_ARRAY_COPY_SUCCESS; 103 } 104 105 #ifndef CX_ARRAY_SWAP_SBO_SIZE 106 #define CX_ARRAY_SWAP_SBO_SIZE 128 107 #endif 108 109 void cx_array_swap( 110 void *arr, 111 size_t elem_size, 112 size_t idx1, 113 size_t idx2 114 ) { 115 assert(arr != NULL); 116 117 // short circuit 118 if (idx1 == idx2) return; 119 120 char sbo_mem[CX_ARRAY_SWAP_SBO_SIZE]; 121 void *tmp; 122 123 // decide if we can use the local buffer 124 if (elem_size > CX_ARRAY_SWAP_SBO_SIZE) { 125 tmp = malloc(elem_size); 126 // we don't want to enforce error handling 127 if (tmp == NULL) abort(); 128 } else { 129 tmp = sbo_mem; 130 } 131 132 // calculate memory locations 133 char *left = arr, *right = arr; 134 left += idx1 * elem_size; 135 right += idx2 * elem_size; 136 137 // three-way swap 138 memcpy(tmp, left, elem_size); 139 memcpy(left, right, elem_size); 140 memcpy(right, tmp, elem_size); 141 142 // free dynamic memory, if it was needed 143 if (tmp != sbo_mem) { 144 free(tmp); 145 } 146 } 147 148 // HIGH LEVEL ARRAY LIST FUNCTIONS 149 150 typedef struct { 151 struct cx_list_s base; 152 void *data; 153 size_t capacity; 154 struct cx_array_reallocator_s reallocator; 155 } cx_array_list; 156 157 static void *cx_arl_realloc( 158 void *array, 159 size_t capacity, 160 size_t elem_size, 161 struct cx_array_reallocator_s *alloc 162 ) { 163 // retrieve the pointer to the list allocator 164 CxAllocator const *al = alloc->ptr1; 165 166 // use the list allocator to reallocate the memory 167 return cxRealloc(al, array, capacity * elem_size); 168 } 169 170 static void cx_arl_destructor(struct cx_list_s *list) { 171 cx_array_list *arl = (cx_array_list *) list; 172 173 char *ptr = arl->data; 174 175 if (list->simple_destructor) { 176 for (size_t i = 0; i < list->size; i++) { 177 cx_invoke_simple_destructor(list, ptr); 178 ptr += list->item_size; 179 } 180 } 181 if (list->advanced_destructor) { 182 for (size_t i = 0; i < list->size; i++) { 183 cx_invoke_advanced_destructor(list, ptr); 184 ptr += list->item_size; 185 } 186 } 187 188 cxFree(list->allocator, arl->data); 189 cxFree(list->allocator, list); 190 } 191 192 static size_t cx_arl_insert_array( 193 struct cx_list_s *list, 194 size_t index, 195 void const *array, 196 size_t n 197 ) { 198 // out of bounds and special case check 199 if (index > list->size || n == 0) return 0; 200 201 // get a correctly typed pointer to the list 202 cx_array_list *arl = (cx_array_list *) list; 203 204 // do we need to move some elements? 205 if (index < list->size) { 206 char const *first_to_move = (char const *) arl->data; 207 first_to_move += index * list->item_size; 208 size_t elems_to_move = list->size - index; 209 size_t start_of_moved = index + n; 210 211 if (CX_ARRAY_COPY_SUCCESS != cx_array_copy( 212 &arl->data, 213 &list->size, 214 &arl->capacity, 215 start_of_moved, 216 first_to_move, 217 list->item_size, 218 elems_to_move, 219 &arl->reallocator 220 )) { 221 // if moving existing elems is unsuccessful, abort 222 return 0; 223 } 224 } 225 226 // note that if we had to move the elements, the following operation 227 // is guaranteed to succeed, because we have the memory already allocated 228 // therefore, it is impossible to leave this function with an invalid array 229 230 // place the new elements 231 if (CX_ARRAY_COPY_SUCCESS == cx_array_copy( 232 &arl->data, 233 &list->size, 234 &arl->capacity, 235 index, 236 array, 237 list->item_size, 238 n, 239 &arl->reallocator 240 )) { 241 return n; 242 } else { 243 // array list implementation is "all or nothing" 244 return 0; 245 } 246 } 247 248 static int cx_arl_insert_element( 249 struct cx_list_s *list, 250 size_t index, 251 void const *element 252 ) { 253 return 1 != cx_arl_insert_array(list, index, element, 1); 254 } 255 256 static int cx_arl_insert_iter( 257 struct cx_mut_iterator_s *iter, 258 void const *elem, 259 int prepend 260 ) { 261 struct cx_list_s *list = iter->src_handle; 262 if (iter->index < list->size) { 263 int result = cx_arl_insert_element( 264 list, 265 iter->index + 1 - prepend, 266 elem 267 ); 268 if (result == 0 && prepend != 0) { 269 iter->index++; 270 iter->elem_handle = ((char *) iter->elem_handle) + list->item_size; 271 } 272 return result; 273 } else { 274 int result = cx_arl_insert_element(list, list->size, elem); 275 iter->index = list->size; 276 return result; 277 } 278 } 279 280 static int cx_arl_remove( 281 struct cx_list_s *list, 282 size_t index 283 ) { 284 cx_array_list *arl = (cx_array_list *) list; 285 286 // out-of-bounds check 287 if (index >= list->size) { 288 return 1; 289 } 290 291 // content destruction 292 cx_invoke_destructor(list, ((char *) arl->data) + index * list->item_size); 293 294 // short-circuit removal of last element 295 if (index == list->size - 1) { 296 list->size--; 297 return 0; 298 } 299 300 // just move the elements starting at index to the left 301 int result = cx_array_copy( 302 &arl->data, 303 &list->size, 304 &arl->capacity, 305 index, 306 ((char *) arl->data) + (index + 1) * list->item_size, 307 list->item_size, 308 list->size - index - 1, 309 &arl->reallocator 310 ); 311 if (result == 0) { 312 // decrease the size 313 list->size--; 314 } 315 return result; 316 } 317 318 static void cx_arl_clear(struct cx_list_s *list) { 319 if (list->size == 0) return; 320 321 cx_array_list *arl = (cx_array_list *) list; 322 char *ptr = arl->data; 323 324 if (list->simple_destructor) { 325 for (size_t i = 0; i < list->size; i++) { 326 cx_invoke_simple_destructor(list, ptr); 327 ptr += list->item_size; 328 } 329 } 330 if (list->advanced_destructor) { 331 for (size_t i = 0; i < list->size; i++) { 332 cx_invoke_advanced_destructor(list, ptr); 333 ptr += list->item_size; 334 } 335 } 336 337 memset(arl->data, 0, list->size * list->item_size); 338 list->size = 0; 339 } 340 341 static int cx_arl_swap( 342 struct cx_list_s *list, 343 size_t i, 344 size_t j 345 ) { 346 if (i >= list->size || j >= list->size) return 1; 347 cx_array_list *arl = (cx_array_list *) list; 348 cx_array_swap(arl->data, list->item_size, i, j); 349 return 0; 350 } 351 352 static void *cx_arl_at( 353 struct cx_list_s const *list, 354 size_t index 355 ) { 356 if (index < list->size) { 357 cx_array_list const *arl = (cx_array_list const *) list; 358 char *space = arl->data; 359 return space + index * list->item_size; 360 } else { 361 return NULL; 362 } 363 } 364 365 static ssize_t cx_arl_find( 366 struct cx_list_s const *list, 367 void const *elem 368 ) { 369 assert(list->cmpfunc != NULL); 370 assert(list->size < SIZE_MAX / 2); 371 char *cur = ((cx_array_list const *) list)->data; 372 373 for (ssize_t i = 0; i < (ssize_t) list->size; i++) { 374 if (0 == list->cmpfunc(elem, cur)) { 375 return i; 376 } 377 cur += list->item_size; 378 } 379 380 return -1; 381 } 382 383 static void cx_arl_sort(struct cx_list_s *list) { 384 assert(list->cmpfunc != NULL); 385 qsort(((cx_array_list *) list)->data, 386 list->size, 387 list->item_size, 388 list->cmpfunc 389 ); 390 } 391 392 static int cx_arl_compare( 393 struct cx_list_s const *list, 394 struct cx_list_s const *other 395 ) { 396 assert(list->cmpfunc != NULL); 397 if (list->size == other->size) { 398 char const *left = ((cx_array_list const *) list)->data; 399 char const *right = ((cx_array_list const *) other)->data; 400 for (size_t i = 0; i < list->size; i++) { 401 int d = list->cmpfunc(left, right); 402 if (d != 0) { 403 return d; 404 } 405 left += list->item_size; 406 right += other->item_size; 407 } 408 return 0; 409 } else { 410 return list->size < other->size ? -1 : 1; 411 } 412 } 413 414 static void cx_arl_reverse(struct cx_list_s *list) { 415 if (list->size < 2) return; 416 void *data = ((cx_array_list const *) list)->data; 417 size_t half = list->size / 2; 418 for (size_t i = 0; i < half; i++) { 419 cx_array_swap(data, list->item_size, i, list->size - 1 - i); 420 } 421 } 422 423 static bool cx_arl_iter_valid(void const *it) { 424 struct cx_iterator_s const *iter = it; 425 struct cx_list_s const *list = iter->src_handle; 426 return iter->index < list->size; 427 } 428 429 static void *cx_arl_iter_current(void const *it) { 430 struct cx_iterator_s const *iter = it; 431 return iter->elem_handle; 432 } 433 434 static void cx_arl_iter_next(void *it) { 435 struct cx_iterator_base_s *itbase = it; 436 if (itbase->remove) { 437 struct cx_mut_iterator_s *iter = it; 438 itbase->remove = false; 439 cx_arl_remove(iter->src_handle, iter->index); 440 } else { 441 struct cx_iterator_s *iter = it; 442 iter->index++; 443 iter->elem_handle = 444 ((char *) iter->elem_handle) 445 + ((struct cx_list_s const *) iter->src_handle)->item_size; 446 } 447 } 448 449 static void cx_arl_iter_prev(void *it) { 450 struct cx_iterator_base_s *itbase = it; 451 struct cx_mut_iterator_s *iter = it; 452 cx_array_list *const list = iter->src_handle; 453 if (itbase->remove) { 454 itbase->remove = false; 455 cx_arl_remove(iter->src_handle, iter->index); 456 } 457 iter->index--; 458 if (iter->index < list->base.size) { 459 iter->elem_handle = ((char *) list->data) 460 + iter->index * list->base.item_size; 461 } 462 } 463 464 static bool cx_arl_iter_flag_rm(void *it) { 465 struct cx_iterator_base_s *iter = it; 466 if (iter->mutating) { 467 iter->remove = true; 468 return true; 469 } else { 470 return false; 471 } 472 } 473 474 static struct cx_iterator_s cx_arl_iterator( 475 struct cx_list_s const *list, 476 size_t index, 477 bool backwards 478 ) { 479 struct cx_iterator_s iter; 480 481 iter.index = index; 482 iter.src_handle = list; 483 iter.elem_handle = cx_arl_at(list, index); 484 iter.base.valid = cx_arl_iter_valid; 485 iter.base.current = cx_arl_iter_current; 486 iter.base.next = backwards ? cx_arl_iter_prev : cx_arl_iter_next; 487 iter.base.flag_removal = cx_arl_iter_flag_rm; 488 iter.base.remove = false; 489 iter.base.mutating = false; 490 491 return iter; 492 } 493 494 static cx_list_class cx_array_list_class = { 495 cx_arl_destructor, 496 cx_arl_insert_element, 497 cx_arl_insert_array, 498 cx_arl_insert_iter, 499 cx_arl_remove, 500 cx_arl_clear, 501 cx_arl_swap, 502 cx_arl_at, 503 cx_arl_find, 504 cx_arl_sort, 505 cx_arl_compare, 506 cx_arl_reverse, 507 cx_arl_iterator, 508 }; 509 510 CxList *cxArrayListCreate( 511 CxAllocator const *allocator, 512 cx_compare_func comparator, 513 size_t item_size, 514 size_t initial_capacity 515 ) { 516 if (allocator == NULL) { 517 allocator = cxDefaultAllocator; 518 } 519 520 cx_array_list *list = cxCalloc(allocator, 1, sizeof(cx_array_list)); 521 if (list == NULL) return NULL; 522 523 list->base.cl = &cx_array_list_class; 524 list->base.allocator = allocator; 525 list->base.cmpfunc = comparator; 526 list->capacity = initial_capacity; 527 528 if (item_size > 0) { 529 list->base.item_size = item_size; 530 } else { 531 item_size = sizeof(void *); 532 cxListStorePointers((CxList *) list); 533 } 534 535 // allocate the array after the real item_size is known 536 list->data = cxCalloc(allocator, initial_capacity, item_size); 537 if (list->data == NULL) { 538 cxFree(allocator, list); 539 return NULL; 540 } 541 542 // configure the reallocator 543 list->reallocator.realloc = cx_arl_realloc; 544 list->reallocator.ptr1 = (void *) allocator; 545 546 return (CxList *) list; 547 } 548