comparison: src/array_list.c
src/array_list.c
- changeset 855
- 35bcb3216c0d
- parent 854
- fe0d69d72bcd
- child 856
- 6bbbf219251d
equal
deleted
inserted
replaced
| 854:fe0d69d72bcd | 855:35bcb3216c0d |
|---|---|
| 192 char *ptr = arl->data; | 192 char *ptr = arl->data; |
| 193 | 193 |
| 194 if (list->base.simple_destructor) { | 194 if (list->base.simple_destructor) { |
| 195 for (size_t i = 0; i < list->base.size; i++) { | 195 for (size_t i = 0; i < list->base.size; i++) { |
| 196 cx_invoke_simple_destructor(list, ptr); | 196 cx_invoke_simple_destructor(list, ptr); |
| 197 ptr += list->base.item_size; | 197 ptr += list->base.elem_size; |
| 198 } | 198 } |
| 199 } | 199 } |
| 200 if (list->base.advanced_destructor) { | 200 if (list->base.advanced_destructor) { |
| 201 for (size_t i = 0; i < list->base.size; i++) { | 201 for (size_t i = 0; i < list->base.size; i++) { |
| 202 cx_invoke_advanced_destructor(list, ptr); | 202 cx_invoke_advanced_destructor(list, ptr); |
| 203 ptr += list->base.item_size; | 203 ptr += list->base.elem_size; |
| 204 } | 204 } |
| 205 } | 205 } |
| 206 | 206 |
| 207 cxFree(list->base.allocator, arl->data); | 207 cxFree(list->base.allocator, arl->data); |
| 208 cxFree(list->base.allocator, list); | 208 cxFree(list->base.allocator, list); |
| 221 cx_array_list *arl = (cx_array_list *) list; | 221 cx_array_list *arl = (cx_array_list *) list; |
| 222 | 222 |
| 223 // do we need to move some elements? | 223 // do we need to move some elements? |
| 224 if (index < list->base.size) { | 224 if (index < list->base.size) { |
| 225 char const *first_to_move = (char const *) arl->data; | 225 char const *first_to_move = (char const *) arl->data; |
| 226 first_to_move += index * list->base.item_size; | 226 first_to_move += index * list->base.elem_size; |
| 227 size_t elems_to_move = list->base.size - index; | 227 size_t elems_to_move = list->base.size - index; |
| 228 size_t start_of_moved = index + n; | 228 size_t start_of_moved = index + n; |
| 229 | 229 |
| 230 if (CX_ARRAY_SUCCESS != cx_array_copy( | 230 if (CX_ARRAY_SUCCESS != cx_array_copy( |
| 231 &arl->data, | 231 &arl->data, |
| 232 &list->base.size, | 232 &list->base.size, |
| 233 &arl->capacity, | 233 &arl->capacity, |
| 234 start_of_moved, | 234 start_of_moved, |
| 235 first_to_move, | 235 first_to_move, |
| 236 list->base.item_size, | 236 list->base.elem_size, |
| 237 elems_to_move, | 237 elems_to_move, |
| 238 &arl->reallocator | 238 &arl->reallocator |
| 239 )) { | 239 )) { |
| 240 // if moving existing elems is unsuccessful, abort | 240 // if moving existing elems is unsuccessful, abort |
| 241 return 0; | 241 return 0; |
| 251 &arl->data, | 251 &arl->data, |
| 252 &list->base.size, | 252 &list->base.size, |
| 253 &arl->capacity, | 253 &arl->capacity, |
| 254 index, | 254 index, |
| 255 array, | 255 array, |
| 256 list->base.item_size, | 256 list->base.elem_size, |
| 257 n, | 257 n, |
| 258 &arl->reallocator | 258 &arl->reallocator |
| 259 )) { | 259 )) { |
| 260 return n; | 260 return n; |
| 261 } else { | 261 } else { |
| 284 iter->index + 1 - prepend, | 284 iter->index + 1 - prepend, |
| 285 elem | 285 elem |
| 286 ); | 286 ); |
| 287 if (result == 0 && prepend != 0) { | 287 if (result == 0 && prepend != 0) { |
| 288 iter->index++; | 288 iter->index++; |
| 289 iter->elem_handle = ((char *) iter->elem_handle) + list->base.item_size; | 289 iter->elem_handle = ((char *) iter->elem_handle) + list->base.elem_size; |
| 290 } | 290 } |
| 291 return result; | 291 return result; |
| 292 } else { | 292 } else { |
| 293 int result = cx_arl_insert_element(list, list->base.size, elem); | 293 int result = cx_arl_insert_element(list, list->base.size, elem); |
| 294 iter->index = list->base.size; | 294 iter->index = list->base.size; |
| 306 if (index >= list->base.size) { | 306 if (index >= list->base.size) { |
| 307 return 1; | 307 return 1; |
| 308 } | 308 } |
| 309 | 309 |
| 310 // content destruction | 310 // content destruction |
| 311 cx_invoke_destructor(list, ((char *) arl->data) + index * list->base.item_size); | 311 cx_invoke_destructor(list, ((char *) arl->data) + index * list->base.elem_size); |
| 312 | 312 |
| 313 // short-circuit removal of last element | 313 // short-circuit removal of last element |
| 314 if (index == list->base.size - 1) { | 314 if (index == list->base.size - 1) { |
| 315 list->base.size--; | 315 list->base.size--; |
| 316 return 0; | 316 return 0; |
| 320 int result = cx_array_copy( | 320 int result = cx_array_copy( |
| 321 &arl->data, | 321 &arl->data, |
| 322 &list->base.size, | 322 &list->base.size, |
| 323 &arl->capacity, | 323 &arl->capacity, |
| 324 index, | 324 index, |
| 325 ((char *) arl->data) + (index + 1) * list->base.item_size, | 325 ((char *) arl->data) + (index + 1) * list->base.elem_size, |
| 326 list->base.item_size, | 326 list->base.elem_size, |
| 327 list->base.size - index - 1, | 327 list->base.size - index - 1, |
| 328 &arl->reallocator | 328 &arl->reallocator |
| 329 ); | 329 ); |
| 330 | 330 |
| 331 // cx_array_copy cannot fail, array cannot grow | 331 // cx_array_copy cannot fail, array cannot grow |
| 344 char *ptr = arl->data; | 344 char *ptr = arl->data; |
| 345 | 345 |
| 346 if (list->base.simple_destructor) { | 346 if (list->base.simple_destructor) { |
| 347 for (size_t i = 0; i < list->base.size; i++) { | 347 for (size_t i = 0; i < list->base.size; i++) { |
| 348 cx_invoke_simple_destructor(list, ptr); | 348 cx_invoke_simple_destructor(list, ptr); |
| 349 ptr += list->base.item_size; | 349 ptr += list->base.elem_size; |
| 350 } | 350 } |
| 351 } | 351 } |
| 352 if (list->base.advanced_destructor) { | 352 if (list->base.advanced_destructor) { |
| 353 for (size_t i = 0; i < list->base.size; i++) { | 353 for (size_t i = 0; i < list->base.size; i++) { |
| 354 cx_invoke_advanced_destructor(list, ptr); | 354 cx_invoke_advanced_destructor(list, ptr); |
| 355 ptr += list->base.item_size; | 355 ptr += list->base.elem_size; |
| 356 } | 356 } |
| 357 } | 357 } |
| 358 | 358 |
| 359 memset(arl->data, 0, list->base.size * list->base.item_size); | 359 memset(arl->data, 0, list->base.size * list->base.elem_size); |
| 360 list->base.size = 0; | 360 list->base.size = 0; |
| 361 } | 361 } |
| 362 | 362 |
| 363 static int cx_arl_swap( | 363 static int cx_arl_swap( |
| 364 struct cx_list_s *list, | 364 struct cx_list_s *list, |
| 365 size_t i, | 365 size_t i, |
| 366 size_t j | 366 size_t j |
| 367 ) { | 367 ) { |
| 368 if (i >= list->base.size || j >= list->base.size) return 1; | 368 if (i >= list->base.size || j >= list->base.size) return 1; |
| 369 cx_array_list *arl = (cx_array_list *) list; | 369 cx_array_list *arl = (cx_array_list *) list; |
| 370 cx_array_swap(arl->data, list->base.item_size, i, j); | 370 cx_array_swap(arl->data, list->base.elem_size, i, j); |
| 371 return 0; | 371 return 0; |
| 372 } | 372 } |
| 373 | 373 |
| 374 static void *cx_arl_at( | 374 static void *cx_arl_at( |
| 375 struct cx_list_s const *list, | 375 struct cx_list_s const *list, |
| 376 size_t index | 376 size_t index |
| 377 ) { | 377 ) { |
| 378 if (index < list->base.size) { | 378 if (index < list->base.size) { |
| 379 cx_array_list const *arl = (cx_array_list const *) list; | 379 cx_array_list const *arl = (cx_array_list const *) list; |
| 380 char *space = arl->data; | 380 char *space = arl->data; |
| 381 return space + index * list->base.item_size; | 381 return space + index * list->base.elem_size; |
| 382 } else { | 382 } else { |
| 383 return NULL; | 383 return NULL; |
| 384 } | 384 } |
| 385 } | 385 } |
| 386 | 386 |
| 403 } | 403 } |
| 404 } else { | 404 } else { |
| 405 return i; | 405 return i; |
| 406 } | 406 } |
| 407 } | 407 } |
| 408 cur += list->base.item_size; | 408 cur += list->base.elem_size; |
| 409 } | 409 } |
| 410 | 410 |
| 411 return -1; | 411 return -1; |
| 412 } | 412 } |
| 413 | 413 |
| 414 static void cx_arl_sort(struct cx_list_s *list) { | 414 static void cx_arl_sort(struct cx_list_s *list) { |
| 415 assert(list->base.cmpfunc != NULL); | 415 assert(list->base.cmpfunc != NULL); |
| 416 qsort(((cx_array_list *) list)->data, | 416 qsort(((cx_array_list *) list)->data, |
| 417 list->base.size, | 417 list->base.size, |
| 418 list->base.item_size, | 418 list->base.elem_size, |
| 419 list->base.cmpfunc | 419 list->base.cmpfunc |
| 420 ); | 420 ); |
| 421 } | 421 } |
| 422 | 422 |
| 423 static int cx_arl_compare( | 423 static int cx_arl_compare( |
| 431 for (size_t i = 0; i < list->base.size; i++) { | 431 for (size_t i = 0; i < list->base.size; i++) { |
| 432 int d = list->base.cmpfunc(left, right); | 432 int d = list->base.cmpfunc(left, right); |
| 433 if (d != 0) { | 433 if (d != 0) { |
| 434 return d; | 434 return d; |
| 435 } | 435 } |
| 436 left += list->base.item_size; | 436 left += list->base.elem_size; |
| 437 right += other->base.item_size; | 437 right += other->base.elem_size; |
| 438 } | 438 } |
| 439 return 0; | 439 return 0; |
| 440 } else { | 440 } else { |
| 441 return list->base.size < other->base.size ? -1 : 1; | 441 return list->base.size < other->base.size ? -1 : 1; |
| 442 } | 442 } |
| 445 static void cx_arl_reverse(struct cx_list_s *list) { | 445 static void cx_arl_reverse(struct cx_list_s *list) { |
| 446 if (list->base.size < 2) return; | 446 if (list->base.size < 2) return; |
| 447 void *data = ((cx_array_list const *) list)->data; | 447 void *data = ((cx_array_list const *) list)->data; |
| 448 size_t half = list->base.size / 2; | 448 size_t half = list->base.size / 2; |
| 449 for (size_t i = 0; i < half; i++) { | 449 for (size_t i = 0; i < half; i++) { |
| 450 cx_array_swap(data, list->base.item_size, i, list->base.size - 1 - i); | 450 cx_array_swap(data, list->base.elem_size, i, list->base.size - 1 - i); |
| 451 } | 451 } |
| 452 } | 452 } |
| 453 | 453 |
| 454 static bool cx_arl_iter_valid(void const *it) { | 454 static bool cx_arl_iter_valid(void const *it) { |
| 455 struct cx_iterator_s const *iter = it; | 455 struct cx_iterator_s const *iter = it; |
| 469 cx_arl_remove(iter->src_handle.m, iter->index); | 469 cx_arl_remove(iter->src_handle.m, iter->index); |
| 470 } else { | 470 } else { |
| 471 iter->index++; | 471 iter->index++; |
| 472 iter->elem_handle = | 472 iter->elem_handle = |
| 473 ((char *) iter->elem_handle) | 473 ((char *) iter->elem_handle) |
| 474 + ((struct cx_list_s const *) iter->src_handle.c)->base.item_size; | 474 + ((struct cx_list_s const *) iter->src_handle.c)->base.elem_size; |
| 475 } | 475 } |
| 476 } | 476 } |
| 477 | 477 |
| 478 static void cx_arl_iter_prev(void *it) { | 478 static void cx_arl_iter_prev(void *it) { |
| 479 struct cx_iterator_s *iter = it; | 479 struct cx_iterator_s *iter = it; |
| 483 cx_arl_remove(iter->src_handle.m, iter->index); | 483 cx_arl_remove(iter->src_handle.m, iter->index); |
| 484 } | 484 } |
| 485 iter->index--; | 485 iter->index--; |
| 486 if (iter->index < list->base.base.size) { | 486 if (iter->index < list->base.base.size) { |
| 487 iter->elem_handle = ((char *) list->data) | 487 iter->elem_handle = ((char *) list->data) |
| 488 + iter->index * list->base.base.item_size; | 488 + iter->index * list->base.base.elem_size; |
| 489 } | 489 } |
| 490 } | 490 } |
| 491 | 491 |
| 492 | 492 |
| 493 static struct cx_iterator_s cx_arl_iterator( | 493 static struct cx_iterator_s cx_arl_iterator( |
| 498 struct cx_iterator_s iter; | 498 struct cx_iterator_s iter; |
| 499 | 499 |
| 500 iter.index = index; | 500 iter.index = index; |
| 501 iter.src_handle.c = list; | 501 iter.src_handle.c = list; |
| 502 iter.elem_handle = cx_arl_at(list, index); | 502 iter.elem_handle = cx_arl_at(list, index); |
| 503 iter.elem_size = list->base.item_size; | 503 iter.elem_size = list->base.elem_size; |
| 504 iter.elem_count = list->base.size; | 504 iter.elem_count = list->base.size; |
| 505 iter.base.valid = cx_arl_iter_valid; | 505 iter.base.valid = cx_arl_iter_valid; |
| 506 iter.base.current = cx_arl_iter_current; | 506 iter.base.current = cx_arl_iter_current; |
| 507 iter.base.next = backwards ? cx_arl_iter_prev : cx_arl_iter_next; | 507 iter.base.next = backwards ? cx_arl_iter_prev : cx_arl_iter_next; |
| 508 iter.base.remove = false; | 508 iter.base.remove = false; |
| 528 }; | 528 }; |
| 529 | 529 |
| 530 CxList *cxArrayListCreate( | 530 CxList *cxArrayListCreate( |
| 531 CxAllocator const *allocator, | 531 CxAllocator const *allocator, |
| 532 cx_compare_func comparator, | 532 cx_compare_func comparator, |
| 533 size_t item_size, | 533 size_t elem_size, |
| 534 size_t initial_capacity | 534 size_t initial_capacity |
| 535 ) { | 535 ) { |
| 536 if (allocator == NULL) { | 536 if (allocator == NULL) { |
| 537 allocator = cxDefaultAllocator; | 537 allocator = cxDefaultAllocator; |
| 538 } | 538 } |
| 542 | 542 |
| 543 list->base.cl = &cx_array_list_class; | 543 list->base.cl = &cx_array_list_class; |
| 544 list->base.base.allocator = allocator; | 544 list->base.base.allocator = allocator; |
| 545 list->capacity = initial_capacity; | 545 list->capacity = initial_capacity; |
| 546 | 546 |
| 547 if (item_size > 0) { | 547 if (elem_size > 0) { |
| 548 list->base.base.item_size = item_size; | 548 list->base.base.elem_size = elem_size; |
| 549 list->base.base.cmpfunc = comparator; | 549 list->base.base.cmpfunc = comparator; |
| 550 } else { | 550 } else { |
| 551 item_size = sizeof(void *); | 551 elem_size = sizeof(void *); |
| 552 list->base.base.cmpfunc = comparator == NULL ? cx_cmp_ptr : comparator; | 552 list->base.base.cmpfunc = comparator == NULL ? cx_cmp_ptr : comparator; |
| 553 cxListStorePointers((CxList *) list); | 553 cxListStorePointers((CxList *) list); |
| 554 } | 554 } |
| 555 | 555 |
| 556 // allocate the array after the real item_size is known | 556 // allocate the array after the real elem_size is known |
| 557 list->data = cxCalloc(allocator, initial_capacity, item_size); | 557 list->data = cxCalloc(allocator, initial_capacity, elem_size); |
| 558 if (list->data == NULL) { | 558 if (list->data == NULL) { |
| 559 cxFree(allocator, list); | 559 cxFree(allocator, list); |
| 560 return NULL; | 560 return NULL; |
| 561 } | 561 } |
| 562 | 562 |
