comparison: src/list.c
src/list.c
- changeset 1423
- 9a72258446cd
- parent 1422
- 8bfccb342895
equal
deleted
inserted
replaced
| 1422:8bfccb342895 | 1423:9a72258446cd |
|---|---|
| 325 size_t elem_size = list->collection.elem_size; | 325 size_t elem_size = list->collection.elem_size; |
| 326 cx_compare_func cmp = list->collection.cmpfunc; | 326 cx_compare_func cmp = list->collection.cmpfunc; |
| 327 const char *src = sorted_data; | 327 const char *src = sorted_data; |
| 328 | 328 |
| 329 // track indices and number of inserted items | 329 // track indices and number of inserted items |
| 330 size_t di = 0, si = 0, inserted = 0; | 330 size_t di = 0, si = 0, processed = 0; |
| 331 | 331 |
| 332 // search the list for insertion points | 332 // search the list for insertion points |
| 333 for (; di < list->collection.size; di++) { | 333 while (di < list->collection.size) { |
| 334 const void *list_elm = invoke_list_func(at, list, di); | 334 const void *list_elm = invoke_list_func(at, list, di); |
| 335 | 335 |
| 336 // compare current list element with first source element | 336 // compare the current list element with the first source element |
| 337 // if less or equal, skip | 337 // if less, skip the list elements |
| 338 // if equal, skip the list elements and optionally the source elements | |
| 338 { | 339 { |
| 339 int d = cmp(list_elm, src); | 340 int d = cmp(list_elm, src); |
| 340 if (d <= 0) { | 341 if (d <= 0) { |
| 341 if (!allow_duplicates && d == 0) { | 342 if (!allow_duplicates && d == 0) { |
| 342 src += elem_size; | 343 src += elem_size; |
| 343 si++; | 344 si++; |
| 344 inserted++; // we also count duplicates for the return value | 345 processed++; // we also count duplicates for the return value |
| 345 while (si < n && cmp(list_elm, src) == 0) { | 346 while (si < n && cmp(list_elm, src) == 0) { |
| 346 src += elem_size; | 347 src += elem_size; |
| 347 si++; | 348 si++; |
| 348 inserted++; | 349 processed++; |
| 349 } | 350 } |
| 350 if (inserted == n) { | 351 if (processed == n) { |
| 351 return inserted; | 352 return processed; |
| 352 } | 353 } |
| 353 } | 354 } |
| 355 di++; | |
| 354 continue; | 356 continue; |
| 355 } | 357 } |
| 356 } | 358 } |
| 357 | 359 |
| 358 // determine number of consecutive elements that can be inserted | 360 // determine the number of consecutive elements that can be inserted |
| 359 size_t ins = 1; | 361 size_t ins = 1, skip = 0; |
| 360 const char *next = src; | 362 const char *next = src; |
| 361 while (++si < n) { | 363 while (++si < n) { |
| 364 if (!allow_duplicates) { | |
| 365 // skip duplicates within the source | |
| 366 if (cmp(next, next + elem_size) == 0) { | |
| 367 next += elem_size; | |
| 368 skip++; | |
| 369 continue; | |
| 370 } else { | |
| 371 if (skip > 0) { | |
| 372 // if we had to skip something, we must wait for the next run | |
| 373 next += elem_size; | |
| 374 break; | |
| 375 } | |
| 376 } | |
| 377 } | |
| 362 next += elem_size; | 378 next += elem_size; |
| 363 // once we become larger than the list elem, break | 379 // once we become larger than the list elem, break |
| 364 if (cmp(list_elm, next) <= 0) { | 380 if (cmp(list_elm, next) <= 0) { |
| 365 break; | 381 break; |
| 366 } | 382 } |
| 369 } | 385 } |
| 370 | 386 |
| 371 // insert the elements at location si | 387 // insert the elements at location si |
| 372 if (ins == 1) { | 388 if (ins == 1) { |
| 373 if (NULL == invoke_list_func(insert_element, list, di, src)) { | 389 if (NULL == invoke_list_func(insert_element, list, di, src)) { |
| 374 return inserted; // LCOV_EXCL_LINE | 390 return processed; // LCOV_EXCL_LINE |
| 375 } | 391 } |
| 376 } else { | 392 } else { |
| 377 size_t r = invoke_list_func(insert_array, list, di, src, ins); | 393 size_t r = invoke_list_func(insert_array, list, di, src, ins); |
| 378 if (r < ins) { | 394 if (r < ins) { |
| 379 return inserted + r; // LCOV_EXCL_LINE | 395 return processed + r; // LCOV_EXCL_LINE |
| 380 } | 396 } |
| 381 } | 397 } |
| 382 inserted += ins; | 398 processed += ins + skip; |
| 383 di += ins; | 399 di += ins; |
| 384 | 400 |
| 385 // everything inserted? | 401 // everything inserted? |
| 386 if (inserted == n) { | 402 if (processed == n) { |
| 387 return inserted; | 403 return processed; |
| 388 } | 404 } |
| 389 src = next; | 405 src = next; |
| 390 } | 406 } |
| 391 | 407 |
| 392 // insert remaining items | 408 // insert remaining items |
| 393 if (si < n) { | 409 if (si < n) { |
| 394 inserted += invoke_list_func(insert_array, list, di, src, n - si); | 410 if (allow_duplicates) { |
| 395 } | 411 processed += invoke_list_func(insert_array, list, di, src, n - si); |
| 396 | 412 } else { |
| 397 return inserted; | 413 const void *last = di == 0 ? NULL : invoke_list_func(at, list, di - 1); |
| 414 for (; si < n; si++) { | |
| 415 // skip duplicates within the source | |
| 416 if (last == NULL || cmp(last, src) != 0) { | |
| 417 if (NULL == invoke_list_func(insert_element, list, di, src)) { | |
| 418 return processed; // LCOV_EXCL_LINE | |
| 419 } | |
| 420 last = src; | |
| 421 di++; | |
| 422 } | |
| 423 processed++; | |
| 424 src += elem_size; | |
| 425 } | |
| 426 } | |
| 427 } | |
| 428 | |
| 429 return processed; | |
| 398 } | 430 } |
| 399 | 431 |
| 400 size_t cx_list_default_insert_sorted( | 432 size_t cx_list_default_insert_sorted( |
| 401 struct cx_list_s *list, | 433 struct cx_list_s *list, |
| 402 const void *sorted_data, | 434 const void *sorted_data, |
