comparison: src/array_list.c
src/array_list.c
- changeset 1508
- dfc0ddd9571e
- parent 1507
- f4010cda9a2a
- child 1509
- 0437871200d6
equal
deleted
inserted
replaced
| 1507:f4010cda9a2a | 1508:dfc0ddd9571e |
|---|---|
| 415 memmove(bptr, dest, buf_size * elem_size); | 415 memmove(bptr, dest, buf_size * elem_size); |
| 416 | 416 |
| 417 // while there are both source and buffered elements left, | 417 // while there are both source and buffered elements left, |
| 418 // copy them interleaving | 418 // copy them interleaving |
| 419 while (si < elem_count && bi < new_size) { | 419 while (si < elem_count && bi < new_size) { |
| 420 // determine how many source elements can be inserted | 420 // determine how many source elements can be inserted. |
| 421 // the first element that shall not be inserted is the smallest element | |
| 422 // that is strictly larger than the first buffered element | |
| 423 // (located at the index of the infimum plus one). | |
| 424 // the infimum is guaranteed to exist: | |
| 425 // - if all src elements are larger, | |
| 426 // there is no buffer, and this loop is skipped | |
| 427 // - if any src element is smaller or equal, the infimum exists | |
| 428 // - when all src elements that are smaller are copied, the second part | |
| 429 // of this loop body will copy the remaining buffer (emptying it) | |
| 430 // Therefore, the buffer can never contain an element that is smaller | |
| 431 // than any element in the source and the infimum exists. | |
| 421 size_t copy_len, bytes_copied; | 432 size_t copy_len, bytes_copied; |
| 422 copy_len = cx_array_binary_search_sup( | 433 copy_len = cx_array_binary_search_inf( |
| 423 src, | 434 src, elem_count - si, elem_size, bptr, cmp_func |
| 424 elem_count - si, | |
| 425 elem_size, | |
| 426 bptr, | |
| 427 cmp_func | |
| 428 ); | 435 ); |
| 429 // binary search gives us the smallest index; | 436 copy_len++; |
| 430 // we also want to include equal elements here | |
| 431 while (si + copy_len < elem_count | |
| 432 && cmp_func(bptr, src+copy_len*elem_size) == 0) { | |
| 433 copy_len++; | |
| 434 } | |
| 435 | 437 |
| 436 // copy the source elements | 438 // copy the source elements |
| 437 if (copy_len > 0) { | 439 if (copy_len > 0) { |
| 438 if (allow_duplicates) { | 440 if (allow_duplicates) { |
| 439 // we can copy the entire chunk | 441 // we can copy the entire chunk |
