comparison: src/list.c
src/list.c
- changeset 1419
- e46406fd1b3c
- parent 1345
- 79a865252b16
equal
deleted
inserted
replaced
| 1418:5e1579713bcf | 1419:e46406fd1b3c |
|---|---|
| 88 size_t result = list->climpl->insert_sorted(list, array, n); | 88 size_t result = list->climpl->insert_sorted(list, array, n); |
| 89 cx_pl_unhack_cmpfunc(list); | 89 cx_pl_unhack_cmpfunc(list); |
| 90 return result; | 90 return result; |
| 91 } | 91 } |
| 92 | 92 |
| 93 static size_t cx_pl_insert_unique( | |
| 94 struct cx_list_s *list, | |
| 95 const void *array, | |
| 96 size_t n | |
| 97 ) { | |
| 98 cx_pl_hack_cmpfunc(list); | |
| 99 size_t result = list->climpl->insert_unique(list, array, n); | |
| 100 cx_pl_unhack_cmpfunc(list); | |
| 101 return result; | |
| 102 } | |
| 103 | |
| 93 static int cx_pl_insert_iter( | 104 static int cx_pl_insert_iter( |
| 94 struct cx_iterator_s *iter, | 105 struct cx_iterator_s *iter, |
| 95 const void *elem, | 106 const void *elem, |
| 96 int prepend | 107 int prepend |
| 97 ) { | 108 ) { |
| 179 static cx_list_class cx_pointer_list_class = { | 190 static cx_list_class cx_pointer_list_class = { |
| 180 cx_pl_destructor, | 191 cx_pl_destructor, |
| 181 cx_pl_insert_element, | 192 cx_pl_insert_element, |
| 182 cx_pl_insert_array, | 193 cx_pl_insert_array, |
| 183 cx_pl_insert_sorted, | 194 cx_pl_insert_sorted, |
| 195 cx_pl_insert_unique, | |
| 184 cx_pl_insert_iter, | 196 cx_pl_insert_iter, |
| 185 cx_pl_remove, | 197 cx_pl_remove, |
| 186 cx_pl_clear, | 198 cx_pl_clear, |
| 187 cx_pl_swap, | 199 cx_pl_swap, |
| 188 cx_pl_at, | 200 cx_pl_at, |
| 236 NULL, | 248 NULL, |
| 237 NULL, | 249 NULL, |
| 238 NULL, | 250 NULL, |
| 239 NULL, | 251 NULL, |
| 240 NULL, | 252 NULL, |
| 253 NULL, | |
| 241 cx_emptyl_noop, | 254 cx_emptyl_noop, |
| 242 NULL, | 255 NULL, |
| 243 cx_emptyl_at, | 256 cx_emptyl_at, |
| 244 cx_emptyl_find_remove, | 257 cx_emptyl_find_remove, |
| 245 cx_emptyl_noop, | 258 cx_emptyl_noop, |
| 287 src + (i * elem_size))) return i; | 300 src + (i * elem_size))) return i; |
| 288 } | 301 } |
| 289 return i; | 302 return i; |
| 290 } | 303 } |
| 291 | 304 |
| 292 size_t cx_list_default_insert_sorted( | 305 static size_t cx_list_default_insert_sorted_impl( |
| 293 struct cx_list_s *list, | 306 struct cx_list_s *list, |
| 294 const void *sorted_data, | 307 const void *sorted_data, |
| 295 size_t n | 308 size_t n, |
| 309 bool allow_duplicates | |
| 296 ) { | 310 ) { |
| 297 // corner case | 311 // corner case |
| 298 if (n == 0) return 0; | 312 if (n == 0) return 0; |
| 299 | 313 |
| 300 size_t elem_size = list->collection.elem_size; | 314 size_t elem_size = list->collection.elem_size; |
| 308 for (; di < list->collection.size; di++) { | 322 for (; di < list->collection.size; di++) { |
| 309 const void *list_elm = invoke_list_func(at, list, di); | 323 const void *list_elm = invoke_list_func(at, list, di); |
| 310 | 324 |
| 311 // compare current list element with first source element | 325 // compare current list element with first source element |
| 312 // if less or equal, skip | 326 // if less or equal, skip |
| 313 if (cmp(list_elm, src) <= 0) { | 327 { |
| 314 continue; | 328 int d = cmp(list_elm, src); |
| 329 if (d <= 0) { | |
| 330 if (!allow_duplicates && d == 0) { | |
| 331 src += elem_size; | |
| 332 si++; | |
| 333 inserted++; // we also count duplicates for the return value | |
| 334 while (si < n && cmp(list_elm, src) == 0) { | |
| 335 src += elem_size; | |
| 336 si++; | |
| 337 inserted++; | |
| 338 } | |
| 339 if (inserted == n) return inserted; | |
| 340 } | |
| 341 continue; | |
| 342 } | |
| 315 } | 343 } |
| 316 | 344 |
| 317 // determine number of consecutive elements that can be inserted | 345 // determine number of consecutive elements that can be inserted |
| 318 size_t ins = 1; | 346 size_t ins = 1; |
| 319 const char *next = src; | 347 const char *next = src; |
| 347 if (si < n) { | 375 if (si < n) { |
| 348 inserted += invoke_list_func(insert_array, list, di, src, n - si); | 376 inserted += invoke_list_func(insert_array, list, di, src, n - si); |
| 349 } | 377 } |
| 350 | 378 |
| 351 return inserted; | 379 return inserted; |
| 380 } | |
| 381 | |
| 382 size_t cx_list_default_insert_sorted( | |
| 383 struct cx_list_s *list, | |
| 384 const void *sorted_data, | |
| 385 size_t n | |
| 386 ) { | |
| 387 return cx_list_default_insert_sorted_impl(list, sorted_data, n, true); | |
| 388 } | |
| 389 | |
| 390 size_t cx_list_default_insert_unique( | |
| 391 struct cx_list_s *list, | |
| 392 const void *sorted_data, | |
| 393 size_t n | |
| 394 ) { | |
| 395 return cx_list_default_insert_sorted_impl(list, sorted_data, n, false); | |
| 352 } | 396 } |
| 353 | 397 |
| 354 void cx_list_default_sort(struct cx_list_s *list) { | 398 void cx_list_default_sort(struct cx_list_s *list) { |
| 355 size_t elem_size = list->collection.elem_size; | 399 size_t elem_size = list->collection.elem_size; |
| 356 size_t list_size = list->collection.size; | 400 size_t list_size = list->collection.size; |
