comparison: src/linked_list.c
src/linked_list.c
- changeset 1423
- 9a72258446cd
- parent 1419
- e46406fd1b3c
equal
deleted
inserted
replaced
| 1422:8bfccb342895 | 1423:9a72258446cd |
|---|---|
| 256 ) { | 256 ) { |
| 257 assert(begin != NULL); | 257 assert(begin != NULL); |
| 258 assert(loc_next >= 0); | 258 assert(loc_next >= 0); |
| 259 assert(insert_begin != NULL); | 259 assert(insert_begin != NULL); |
| 260 | 260 |
| 261 // track currently observed nodes | 261 // strategy: build completely new chains from scratch |
| 262 void *dup_start = NULL; | 262 void *source_original = *begin; |
| 263 void *dup_last = NULL; | 263 void *source_argument = insert_begin; |
| 264 void *dest_prev = NULL; | 264 void *new_begin = NULL; |
| 265 void *dest = *begin; | 265 void *new_end = NULL; |
| 266 void *src = insert_begin; | 266 void *dup_begin = NULL; |
| 267 | 267 void *dup_end = NULL; |
| 268 // special case: list is empty | 268 |
| 269 if (dest == NULL) { | 269 // determine the new start |
| 270 *begin = src; | 270 { |
| 271 if (end != NULL) { | 271 int d = source_original == NULL ? 1 : cmp_func(source_original, source_argument); |
| 272 *end = cx_linked_list_last(src, loc_next); | 272 if (d <= 0) { |
| 273 } | 273 // the new chain starts with the original chain |
| 274 return NULL; | 274 new_begin = new_end = source_original; |
| 275 } | 275 source_original = ll_next(source_original); |
| 276 | 276 if (d == 0) { |
| 277 // search the list for insertion points | 277 if (allow_duplicates) { |
| 278 while (dest != NULL && src != NULL) { | 278 // duplicate allowed, append it to the chain |
| 279 // compare current list node with source node | 279 cx_linked_list_link(new_end, source_argument, loc_prev, loc_next); |
| 280 // if less or equal, skip | 280 new_end = source_argument; |
| 281 { | 281 } else { |
| 282 int d = cmp_func(dest, src); | 282 // duplicate is not allowed, start a duplicate chain with the argument |
| 283 if (d <= 0) { | 283 dup_begin = dup_end = source_argument; |
| 284 if (!allow_duplicates && d == 0) { | 284 } |
| 285 if (dup_last == NULL) { | 285 source_argument = ll_next(source_argument); |
| 286 dup_start = src; | 286 } |
| 287 dup_last = src; | 287 } else { |
| 288 if (loc_prev >= 0) { | 288 // input is smaller, or there is no original chain; |
| 289 ll_prev(dup_start) = NULL; | 289 // start the new chain with the source argument |
| 290 } | 290 new_begin = new_end = source_argument; |
| 291 source_argument = ll_next(source_argument); | |
| 292 } | |
| 293 } | |
| 294 | |
| 295 // now successively compare the elements and add them to the correct chains | |
| 296 while (source_original != NULL && source_argument != NULL) { | |
| 297 int d = cmp_func(source_original, source_argument); | |
| 298 if (d <= 0) { | |
| 299 // the original is not larger, add it to the chain | |
| 300 cx_linked_list_link(new_end, source_original, loc_prev, loc_next); | |
| 301 new_end = source_original; | |
| 302 source_original = ll_next(source_original); | |
| 303 if (d == 0) { | |
| 304 if (allow_duplicates) { | |
| 305 // duplicate allowed, append it to the chain | |
| 306 cx_linked_list_link(new_end, source_argument, loc_prev, loc_next); | |
| 307 new_end = source_argument; | |
| 308 } else { | |
| 309 // duplicate is not allowed, append it to the duplicate chain | |
| 310 if (dup_end == NULL) { | |
| 311 dup_begin = dup_end = source_argument; | |
| 291 } else { | 312 } else { |
| 292 cx_linked_list_link(dup_last, src, loc_prev, loc_next); | 313 cx_linked_list_link(dup_end, source_argument, loc_prev, loc_next); |
| 293 dup_last = src; | 314 dup_end = source_argument; |
| 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 } | 315 } |
| 300 } | 316 } |
| 301 | 317 source_argument = ll_next(source_argument); |
| 302 dest_prev = dest; | |
| 303 dest = ll_next(dest); | |
| 304 continue; | |
| 305 } | 318 } |
| 306 } | |
| 307 | |
| 308 // determine chain of elements that can be inserted | |
| 309 void *end_of_chain = src; | |
| 310 void *next_in_chain = ll_next(src); | |
| 311 while (next_in_chain != NULL) { | |
| 312 // once we become larger than the list elem, break | |
| 313 if (cmp_func(dest, next_in_chain) <= 0) { | |
| 314 break; | |
| 315 } | |
| 316 // otherwise, we can insert one more | |
| 317 end_of_chain = next_in_chain; | |
| 318 next_in_chain = ll_next(next_in_chain); | |
| 319 } | |
| 320 | |
| 321 // insert the elements | |
| 322 if (dest_prev == NULL) { | |
| 323 // new begin | |
| 324 *begin = src; | |
| 325 } else { | 319 } else { |
| 326 cx_linked_list_link(dest_prev, src, loc_prev, loc_next); | 320 // the original is larger, append the source argument to the chain |
| 327 } | 321 // check if we must discard the source argument as duplicate |
| 328 cx_linked_list_link(end_of_chain, dest, loc_prev, loc_next); | 322 if (!allow_duplicates && cmp_func(new_end, source_argument) == 0) { |
| 329 | 323 if (dup_end == NULL) { |
| 330 // continue with next | 324 dup_begin = dup_end = source_argument; |
| 331 src = next_in_chain; | 325 } else { |
| 332 dest_prev = dest; | 326 cx_linked_list_link(dup_end, source_argument, loc_prev, loc_next); |
| 333 dest = ll_next(dest); | 327 dup_end = source_argument; |
| 334 } | |
| 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 } | 328 } |
| 345 } else { | 329 } else { |
| 346 cx_linked_list_link(dup_last, src, loc_prev, loc_next); | 330 // no duplicate or duplicates allowed |
| 347 dup_last = src; | 331 cx_linked_list_link(new_end, source_argument, loc_prev, loc_next); |
| 332 new_end = source_argument; | |
| 348 } | 333 } |
| 349 src = ll_next(src); | 334 source_argument = ll_next(source_argument); |
| 350 while (src != NULL && cmp_func(dest_prev, src) == 0) { | 335 } |
| 351 dup_last = src; | 336 } |
| 352 src = ll_next(src); | 337 |
| 338 if (source_original != NULL) { | |
| 339 // something is left from the original chain, append it | |
| 340 cx_linked_list_link(new_end, source_original, loc_prev, loc_next); | |
| 341 new_end = cx_linked_list_last(source_original, loc_next); | |
| 342 } else if (source_argument != NULL) { | |
| 343 // something is left from the input chain; | |
| 344 // when we allow duplicates, append it | |
| 345 if (allow_duplicates) { | |
| 346 cx_linked_list_link(new_end, source_argument, loc_prev, loc_next); | |
| 347 new_end = cx_linked_list_last(source_argument, loc_next); | |
| 348 } else { | |
| 349 // otherwise we must check one-by-one | |
| 350 while (source_argument != NULL) { | |
| 351 if (cmp_func(new_end, source_argument) == 0) { | |
| 352 if (dup_end == NULL) { | |
| 353 dup_begin = dup_end = source_argument; | |
| 354 } else { | |
| 355 cx_linked_list_link(dup_end, source_argument, loc_prev, loc_next); | |
| 356 dup_end = source_argument; | |
| 357 } | |
| 358 } else { | |
| 359 cx_linked_list_link(new_end, source_argument, loc_prev, loc_next); | |
| 360 new_end = source_argument; | |
| 361 } | |
| 362 source_argument = ll_next(source_argument); | |
| 353 } | 363 } |
| 354 } | 364 } |
| 355 } | 365 } |
| 356 | 366 |
| 357 // insert remaining items | 367 // null the next pointers at the end of the chain |
| 358 if (src != NULL) { | 368 ll_next(new_end) = NULL; |
| 359 cx_linked_list_link(dest_prev, src, loc_prev, loc_next); | 369 if (dup_end != NULL) { |
| 360 } | 370 ll_next(dup_end) = NULL; |
| 361 | 371 } |
| 362 // determine new end of list, if requested | 372 |
| 373 // null the optional prev pointers | |
| 374 if (loc_prev >= 0) { | |
| 375 ll_prev(new_begin) = NULL; | |
| 376 if (dup_begin != NULL) { | |
| 377 ll_prev(dup_begin) = NULL; | |
| 378 } | |
| 379 } | |
| 380 | |
| 381 // output | |
| 382 *begin = new_begin; | |
| 363 if (end != NULL) { | 383 if (end != NULL) { |
| 364 *end = cx_linked_list_last( | 384 *end = new_end; |
| 365 dest != NULL ? dest : dest_prev, loc_next); | 385 } |
| 366 } | 386 return dup_begin; |
| 367 | |
| 368 if (dup_last != NULL) { | |
| 369 ll_next(dup_last) = NULL; | |
| 370 } | |
| 371 return dup_start; | |
| 372 } | 387 } |
| 373 | 388 |
| 374 void cx_linked_list_insert_sorted_chain( | 389 void cx_linked_list_insert_sorted_chain( |
| 375 void **begin, | 390 void **begin, |
| 376 void **end, | 391 void **end, |
| 377 ptrdiff_t loc_prev, | 392 ptrdiff_t loc_prev, |
| 378 ptrdiff_t loc_next, | 393 ptrdiff_t loc_next, |
| 379 void *insert_begin, | 394 void *insert_begin, |
| 380 cx_compare_func cmp_func | 395 cx_compare_func cmp_func |
| 381 ) { | 396 ) { |
| 382 void *ret = cx_linked_list_insert_sorted_chain_impl( | 397 cx_linked_list_insert_sorted_chain_impl( |
| 383 begin, end, loc_prev, loc_next, | 398 begin, end, loc_prev, loc_next, |
| 384 insert_begin, cmp_func, true); | 399 insert_begin, cmp_func, true); |
| 385 assert(ret == NULL); | |
| 386 } | 400 } |
| 387 | 401 |
| 388 int cx_linked_list_insert_unique( | 402 int cx_linked_list_insert_unique( |
| 389 void **begin, | 403 void **begin, |
| 390 void **end, | 404 void **end, |
