comparison: src/array_list.c
src/array_list.c
- changeset 1423
- 9a72258446cd
- parent 1419
- e46406fd1b3c
equal
deleted
inserted
replaced
| 1422:8bfccb342895 | 1423:9a72258446cd |
|---|---|
| 289 // perform reallocation | 289 // perform reallocation |
| 290 void *newmem = reallocator->realloc( | 290 void *newmem = reallocator->realloc( |
| 291 *target, oldcap, newcap, elem_size, reallocator | 291 *target, oldcap, newcap, elem_size, reallocator |
| 292 ); | 292 ); |
| 293 if (newmem == NULL) { | 293 if (newmem == NULL) { |
| 294 return 1; | 294 return 1; // LCOV_EXCL_LINE |
| 295 } | 295 } |
| 296 | 296 |
| 297 // repair src pointer, if necessary | 297 // repair src pointer, if necessary |
| 298 if (repairsrc) { | 298 if (repairsrc) { |
| 299 src = ((char *) newmem) + (srcaddr - targetaddr); | 299 src = ((char *) newmem) + (srcaddr - targetaddr); |
| 418 elem_count - si, | 418 elem_count - si, |
| 419 elem_size, | 419 elem_size, |
| 420 bptr, | 420 bptr, |
| 421 cmp_func | 421 cmp_func |
| 422 ); | 422 ); |
| 423 // handle the identical elements | 423 // binary search gives us the smallest index; |
| 424 size_t skip_len = 0; | 424 // we also want to include equal elements here |
| 425 while (copy_len < elem_count - si | 425 while (si + copy_len < elem_count |
| 426 && cmp_func(bptr, src+copy_len*elem_size) == 0) { | 426 && cmp_func(bptr, src+copy_len*elem_size) == 0) { |
| 427 copy_len++; | 427 copy_len++; |
| 428 if (!allow_duplicates) { | 428 } |
| 429 skip_len++; | 429 |
| 430 // copy the source elements | |
| 431 if (copy_len > 0) { | |
| 432 if (allow_duplicates) { | |
| 433 // we can copy the entire chunk | |
| 434 bytes_copied = copy_len * elem_size; | |
| 435 memcpy(dest, src, bytes_copied); | |
| 436 dest += bytes_copied; | |
| 437 src += bytes_copied; | |
| 438 si += copy_len; | |
| 439 di += copy_len; | |
| 440 } else { | |
| 441 // first, check the end of the source chunk | |
| 442 // for being a duplicate of the bptr | |
| 443 const char *end_of_src = src + (copy_len - 1) * elem_size; | |
| 444 size_t skip_len = 0; | |
| 445 while (copy_len > 0 && cmp_func(bptr, end_of_src) == 0) { | |
| 446 end_of_src -= elem_size; | |
| 447 skip_len++; | |
| 448 copy_len--; | |
| 449 } | |
| 450 char *last = dest == *target ? NULL : dest - elem_size; | |
| 451 // then iterate through the source chunk | |
| 452 // and skip all duplicates with the last element in the array | |
| 453 size_t more_skipped = 0; | |
| 454 for (unsigned j = 0; j < copy_len; j++) { | |
| 455 if (last != NULL && cmp_func(last, src) == 0) { | |
| 456 // duplicate - skip | |
| 457 src += elem_size; | |
| 458 si++; | |
| 459 more_skipped++; | |
| 460 } else { | |
| 461 memcpy(dest, src, elem_size); | |
| 462 src += elem_size; | |
| 463 last = dest; | |
| 464 dest += elem_size; | |
| 465 si++; | |
| 466 di++; | |
| 467 } | |
| 468 } | |
| 469 // skip the previously identified elements as well | |
| 470 src += skip_len * elem_size; | |
| 471 si += skip_len; | |
| 472 skip_len += more_skipped; | |
| 473 // reduce the actual size by the number of skipped elements | |
| 474 *size -= skip_len; | |
| 430 } | 475 } |
| 431 } | 476 } |
| 432 copy_len -= skip_len; | |
| 433 | |
| 434 // copy the source elements | |
| 435 bytes_copied = copy_len * elem_size; | |
| 436 memcpy(dest, src, bytes_copied); | |
| 437 dest += bytes_copied; | |
| 438 src += bytes_copied; | |
| 439 si += copy_len; | |
| 440 di += copy_len; | |
| 441 | |
| 442 // skip duplicates when they are not allowed | |
| 443 src += skip_len * elem_size; | |
| 444 si += skip_len; | |
| 445 *size -= skip_len; | |
| 446 | 477 |
| 447 // when all source elements are in place, we are done | 478 // when all source elements are in place, we are done |
| 448 if (si >= elem_count) break; | 479 if (si >= elem_count) break; |
| 449 | 480 |
| 450 // determine how many buffered elements need to be restored | 481 // determine how many buffered elements need to be restored |
| 461 memmove(dest, bptr, bytes_copied); | 492 memmove(dest, bptr, bytes_copied); |
| 462 dest += bytes_copied; | 493 dest += bytes_copied; |
| 463 bptr += bytes_copied; | 494 bptr += bytes_copied; |
| 464 di += copy_len; | 495 di += copy_len; |
| 465 bi += copy_len; | 496 bi += copy_len; |
| 466 | 497 } |
| 467 // check if the last restored element is a duplicate of the next source | 498 |
| 468 if (!allow_duplicates && copy_len > 0) { | 499 // still source elements left? |
| 469 char *last = dest - elem_size; | 500 if (si < elem_count) { |
| 470 while (si < elem_count && cmp_func(last, src) == 0) { | 501 if (allow_duplicates) { |
| 471 src += elem_size; | 502 // duplicates allowed or nothing inserted yet: simply copy everything |
| 472 si++; | 503 memcpy(dest, src, elem_size * (elem_count - si)); |
| 473 (*size)--; | 504 } else { |
| 505 if (dest != *target) { | |
| 506 // skip all source elements that equal the last element | |
| 507 char *last = dest - elem_size; | |
| 508 while (si < elem_count) { | |
| 509 if (last != NULL && cmp_func(last, src) == 0) { | |
| 510 src += elem_size; | |
| 511 si++; | |
| 512 (*size)--; | |
| 513 } else { | |
| 514 break; | |
| 515 } | |
| 516 } | |
| 474 } | 517 } |
| 475 } | 518 // we must check the elements in the chunk one by one |
| 476 } | 519 while (si < elem_count) { |
| 477 | 520 // find a chain of elements that can be copied |
| 478 // still source elements left? simply append them | 521 size_t copy_len = 1, skip_len = 0; |
| 479 if (si < elem_count) { | 522 { |
| 480 memcpy(dest, src, elem_size * (elem_count - si)); | 523 const char *left_src = src; |
| 524 while (si + copy_len < elem_count) { | |
| 525 const char *right_src = left_src + elem_size; | |
| 526 int d = cmp_func(left_src, right_src); | |
| 527 if (d < 0) { | |
| 528 if (skip_len > 0) { | |
| 529 // new larger element found; | |
| 530 // handle it in the next cycle | |
| 531 break; | |
| 532 } | |
| 533 left_src += elem_size; | |
| 534 copy_len++; | |
| 535 } else if (d == 0) { | |
| 536 left_src += elem_size; | |
| 537 skip_len++; | |
| 538 } else { | |
| 539 break; | |
| 540 } | |
| 541 } | |
| 542 } | |
| 543 size_t bytes_copied = copy_len * elem_size; | |
| 544 memcpy(dest, src, bytes_copied); | |
| 545 dest += bytes_copied; | |
| 546 src += bytes_copied + skip_len * elem_size; | |
| 547 si += copy_len + skip_len; | |
| 548 di += copy_len; | |
| 549 *size -= skip_len; | |
| 550 } | |
| 551 } | |
| 481 } | 552 } |
| 482 | 553 |
| 483 // buffered elements need to be moved when we skipped duplicates | 554 // buffered elements need to be moved when we skipped duplicates |
| 484 size_t total_skipped = new_size - *size; | 555 size_t total_skipped = new_size - *size; |
| 485 if (bi < new_size && total_skipped > 0) { | 556 if (bi < new_size && total_skipped > 0) { |
