comparison: src/linked_list.c
src/linked_list.c
- changeset 1419
- e46406fd1b3c
- parent 1387
- 9bdd053820b7
equal
deleted
inserted
replaced
| 1418:5e1579713bcf | 1419:e46406fd1b3c |
|---|---|
| 28 | 28 |
| 29 #include "cx/linked_list.h" | 29 #include "cx/linked_list.h" |
| 30 #include "cx/compare.h" | 30 #include "cx/compare.h" |
| 31 #include <string.h> | 31 #include <string.h> |
| 32 #include <assert.h> | 32 #include <assert.h> |
| 33 #include <unistd.h> | |
| 33 | 34 |
| 34 // LOW LEVEL LINKED LIST FUNCTIONS | 35 // LOW LEVEL LINKED LIST FUNCTIONS |
| 35 | 36 |
| 36 #define CX_LL_PTR(cur, off) (*(void**)(((char*)(cur))+(off))) | 37 #define CX_LL_PTR(cur, off) (*(void**)(((char*)(cur))+(off))) |
| 37 #define ll_prev(node) CX_LL_PTR(node, loc_prev) | 38 #define ll_prev(node) CX_LL_PTR(node, loc_prev) |
| 242 assert(ll_next(new_node) == NULL); | 243 assert(ll_next(new_node) == NULL); |
| 243 cx_linked_list_insert_sorted_chain( | 244 cx_linked_list_insert_sorted_chain( |
| 244 begin, end, loc_prev, loc_next, new_node, cmp_func); | 245 begin, end, loc_prev, loc_next, new_node, cmp_func); |
| 245 } | 246 } |
| 246 | 247 |
| 247 void cx_linked_list_insert_sorted_chain( | 248 static void *cx_linked_list_insert_sorted_chain_impl( |
| 248 void **begin, | 249 void **begin, |
| 249 void **end, | 250 void **end, |
| 250 ptrdiff_t loc_prev, | 251 ptrdiff_t loc_prev, |
| 251 ptrdiff_t loc_next, | 252 ptrdiff_t loc_next, |
| 252 void *insert_begin, | 253 void *insert_begin, |
| 253 cx_compare_func cmp_func | 254 cx_compare_func cmp_func, |
| 255 bool allow_duplicates | |
| 254 ) { | 256 ) { |
| 255 assert(begin != NULL); | 257 assert(begin != NULL); |
| 256 assert(loc_next >= 0); | 258 assert(loc_next >= 0); |
| 257 assert(insert_begin != NULL); | 259 assert(insert_begin != NULL); |
| 258 | 260 |
| 259 // track currently observed nodes | 261 // track currently observed nodes |
| 262 void *dup_start = NULL; | |
| 263 void *dup_last = NULL; | |
| 260 void *dest_prev = NULL; | 264 void *dest_prev = NULL; |
| 261 void *dest = *begin; | 265 void *dest = *begin; |
| 262 void *src = insert_begin; | 266 void *src = insert_begin; |
| 263 | 267 |
| 264 // special case: list is empty | 268 // special case: list is empty |
| 265 if (dest == NULL) { | 269 if (dest == NULL) { |
| 266 *begin = src; | 270 *begin = src; |
| 267 if (end != NULL) { | 271 if (end != NULL) { |
| 268 *end = cx_linked_list_last(src, loc_next); | 272 *end = cx_linked_list_last(src, loc_next); |
| 269 } | 273 } |
| 270 return; | 274 return NULL; |
| 271 } | 275 } |
| 272 | 276 |
| 273 // search the list for insertion points | 277 // search the list for insertion points |
| 274 while (dest != NULL && src != NULL) { | 278 while (dest != NULL && src != NULL) { |
| 275 // compare current list node with source node | 279 // compare current list node with source node |
| 276 // if less or equal, skip | 280 // if less or equal, skip |
| 277 if (cmp_func(dest, src) <= 0) { | 281 { |
| 278 dest_prev = dest; | 282 int d = cmp_func(dest, src); |
| 279 dest = ll_next(dest); | 283 if (d <= 0) { |
| 280 continue; | 284 if (!allow_duplicates && d == 0) { |
| 285 if (dup_last == NULL) { | |
| 286 dup_start = src; | |
| 287 dup_last = src; | |
| 288 if (loc_prev >= 0) { | |
| 289 ll_prev(dup_start) = NULL; | |
| 290 } | |
| 291 } else { | |
| 292 cx_linked_list_link(dup_last, src, loc_prev, loc_next); | |
| 293 dup_last = src; | |
| 294 } | |
| 295 src = ll_next(src); | |
| 296 while (src != NULL && cmp_func(dest, src) == 0) { | |
| 297 dup_last = src; | |
| 298 src = ll_next(src); | |
| 299 } | |
| 300 } | |
| 301 | |
| 302 dest_prev = dest; | |
| 303 dest = ll_next(dest); | |
| 304 continue; | |
| 305 } | |
| 281 } | 306 } |
| 282 | 307 |
| 283 // determine chain of elements that can be inserted | 308 // determine chain of elements that can be inserted |
| 284 void *end_of_chain = src; | 309 void *end_of_chain = src; |
| 285 void *next_in_chain = ll_next(src); | 310 void *next_in_chain = ll_next(src); |
| 306 src = next_in_chain; | 331 src = next_in_chain; |
| 307 dest_prev = dest; | 332 dest_prev = dest; |
| 308 dest = ll_next(dest); | 333 dest = ll_next(dest); |
| 309 } | 334 } |
| 310 | 335 |
| 336 // skip duplicates in the remaining items | |
| 337 if (!allow_duplicates && src != NULL) { | |
| 338 if (cmp_func(dest_prev, src) == 0) { | |
| 339 if (dup_last == NULL) { | |
| 340 dup_start = src; | |
| 341 dup_last = src; | |
| 342 if (loc_prev >= 0) { | |
| 343 ll_prev(dup_start) = NULL; | |
| 344 } | |
| 345 } else { | |
| 346 cx_linked_list_link(dup_last, src, loc_prev, loc_next); | |
| 347 dup_last = src; | |
| 348 } | |
| 349 src = ll_next(src); | |
| 350 while (src != NULL && cmp_func(dest_prev, src) == 0) { | |
| 351 dup_last = src; | |
| 352 src = ll_next(src); | |
| 353 } | |
| 354 } | |
| 355 } | |
| 356 | |
| 311 // insert remaining items | 357 // insert remaining items |
| 312 if (src != NULL) { | 358 if (src != NULL) { |
| 313 cx_linked_list_link(dest_prev, src, loc_prev, loc_next); | 359 cx_linked_list_link(dest_prev, src, loc_prev, loc_next); |
| 314 } | 360 } |
| 315 | 361 |
| 316 // determine new end of list, if requested | 362 // determine new end of list, if requested |
| 317 if (end != NULL) { | 363 if (end != NULL) { |
| 318 *end = cx_linked_list_last( | 364 *end = cx_linked_list_last( |
| 319 dest != NULL ? dest : dest_prev, loc_next); | 365 dest != NULL ? dest : dest_prev, loc_next); |
| 320 } | 366 } |
| 367 | |
| 368 if (dup_last != NULL) { | |
| 369 ll_next(dup_last) = NULL; | |
| 370 } | |
| 371 return dup_start; | |
| 372 } | |
| 373 | |
| 374 void cx_linked_list_insert_sorted_chain( | |
| 375 void **begin, | |
| 376 void **end, | |
| 377 ptrdiff_t loc_prev, | |
| 378 ptrdiff_t loc_next, | |
| 379 void *insert_begin, | |
| 380 cx_compare_func cmp_func | |
| 381 ) { | |
| 382 void *ret = cx_linked_list_insert_sorted_chain_impl( | |
| 383 begin, end, loc_prev, loc_next, | |
| 384 insert_begin, cmp_func, true); | |
| 385 assert(ret == NULL); | |
| 386 } | |
| 387 | |
| 388 int cx_linked_list_insert_unique( | |
| 389 void **begin, | |
| 390 void **end, | |
| 391 ptrdiff_t loc_prev, | |
| 392 ptrdiff_t loc_next, | |
| 393 void *new_node, | |
| 394 cx_compare_func cmp_func | |
| 395 ) { | |
| 396 assert(ll_next(new_node) == NULL); | |
| 397 return NULL != cx_linked_list_insert_unique_chain( | |
| 398 begin, end, loc_prev, loc_next, new_node, cmp_func); | |
| 399 } | |
| 400 | |
| 401 void *cx_linked_list_insert_unique_chain( | |
| 402 void **begin, | |
| 403 void **end, | |
| 404 ptrdiff_t loc_prev, | |
| 405 ptrdiff_t loc_next, | |
| 406 void *insert_begin, | |
| 407 cx_compare_func cmp_func | |
| 408 ) { | |
| 409 return cx_linked_list_insert_sorted_chain_impl( | |
| 410 begin, end, loc_prev, loc_next, | |
| 411 insert_begin, cmp_func, false); | |
| 321 } | 412 } |
| 322 | 413 |
| 323 size_t cx_linked_list_remove_chain( | 414 size_t cx_linked_list_remove_chain( |
| 324 void **begin, | 415 void **begin, |
| 325 void **end, | 416 void **end, |
| 675 const char *left = (const char*)l + cx_ll_insert_sorted_loc_data; | 766 const char *left = (const char*)l + cx_ll_insert_sorted_loc_data; |
| 676 const char *right = (const char*)r + cx_ll_insert_sorted_loc_data; | 767 const char *right = (const char*)r + cx_ll_insert_sorted_loc_data; |
| 677 return cx_ll_insert_sorted_cmp_func(left, right); | 768 return cx_ll_insert_sorted_cmp_func(left, right); |
| 678 } | 769 } |
| 679 | 770 |
| 680 static size_t cx_ll_insert_sorted( | 771 static size_t cx_ll_insert_sorted_impl( |
| 681 struct cx_list_s *list, | 772 struct cx_list_s *list, |
| 682 const void *array, | 773 const void *array, |
| 683 size_t n | 774 size_t n, |
| 775 bool allow_duplicates | |
| 684 ) { | 776 ) { |
| 685 cx_linked_list *ll = (cx_linked_list *) list; | 777 cx_linked_list *ll = (cx_linked_list *) list; |
| 686 | 778 |
| 687 // special case | 779 // special case |
| 688 if (n == 0) return 0; | 780 if (n == 0) return 0; |
| 709 CX_LL_PTR(prev, ll->loc_next) = NULL; | 801 CX_LL_PTR(prev, ll->loc_next) = NULL; |
| 710 | 802 |
| 711 // invoke the low level function | 803 // invoke the low level function |
| 712 cx_ll_insert_sorted_cmp_func = list->collection.cmpfunc; | 804 cx_ll_insert_sorted_cmp_func = list->collection.cmpfunc; |
| 713 cx_ll_insert_sorted_loc_data = ll->loc_data; | 805 cx_ll_insert_sorted_loc_data = ll->loc_data; |
| 714 cx_linked_list_insert_sorted_chain( | 806 if (allow_duplicates) { |
| 715 &ll->begin, | 807 cx_linked_list_insert_sorted_chain( |
| 716 &ll->end, | 808 &ll->begin, |
| 717 ll->loc_prev, | 809 &ll->end, |
| 718 ll->loc_next, | 810 ll->loc_prev, |
| 719 chain, | 811 ll->loc_next, |
| 720 cx_ll_insert_sorted_cmp_helper | 812 chain, |
| 721 ); | 813 cx_ll_insert_sorted_cmp_helper |
| 722 | 814 ); |
| 723 // adjust the list metadata | 815 list->collection.size += inserted; |
| 724 list->collection.size += inserted; | 816 } else { |
| 817 void *duplicates = cx_linked_list_insert_unique_chain( | |
| 818 &ll->begin, | |
| 819 &ll->end, | |
| 820 ll->loc_prev, | |
| 821 ll->loc_next, | |
| 822 chain, | |
| 823 cx_ll_insert_sorted_cmp_helper | |
| 824 ); | |
| 825 list->collection.size += inserted; | |
| 826 // free the nodes that did not make it into the list | |
| 827 while (duplicates != NULL) { | |
| 828 void *next = CX_LL_PTR(duplicates, ll->loc_next); | |
| 829 cxFree(list->collection.allocator, duplicates); | |
| 830 duplicates = next; | |
| 831 list->collection.size--; | |
| 832 } | |
| 833 } | |
| 725 | 834 |
| 726 return inserted; | 835 return inserted; |
| 836 } | |
| 837 | |
| 838 static size_t cx_ll_insert_sorted( | |
| 839 struct cx_list_s *list, | |
| 840 const void *array, | |
| 841 size_t n | |
| 842 ) { | |
| 843 return cx_ll_insert_sorted_impl(list, array, n, true); | |
| 844 } | |
| 845 | |
| 846 static size_t cx_ll_insert_unique( | |
| 847 struct cx_list_s *list, | |
| 848 const void *array, | |
| 849 size_t n | |
| 850 ) { | |
| 851 return cx_ll_insert_sorted_impl(list, array, n, false); | |
| 727 } | 852 } |
| 728 | 853 |
| 729 static size_t cx_ll_remove( | 854 static size_t cx_ll_remove( |
| 730 struct cx_list_s *list, | 855 struct cx_list_s *list, |
| 731 size_t index, | 856 size_t index, |
| 1092 static cx_list_class cx_linked_list_class = { | 1217 static cx_list_class cx_linked_list_class = { |
| 1093 cx_ll_destructor, | 1218 cx_ll_destructor, |
| 1094 cx_ll_insert_element, | 1219 cx_ll_insert_element, |
| 1095 cx_ll_insert_array, | 1220 cx_ll_insert_array, |
| 1096 cx_ll_insert_sorted, | 1221 cx_ll_insert_sorted, |
| 1222 cx_ll_insert_unique, | |
| 1097 cx_ll_insert_iter, | 1223 cx_ll_insert_iter, |
| 1098 cx_ll_remove, | 1224 cx_ll_remove, |
| 1099 cx_ll_clear, | 1225 cx_ll_clear, |
| 1100 cx_ll_swap, | 1226 cx_ll_swap, |
| 1101 cx_ll_at, | 1227 cx_ll_at, |
