comparison: src/array_list.c
src/array_list.c
- changeset 881
- 1dbbf8c1c42f
- parent 876
- f4ce7df9cff0
- child 883
- 3012e9b4214e
equal
deleted
inserted
replaced
| 880:54133f14043f | 881:1dbbf8c1c42f |
|---|---|
| 262 // array list implementation is "all or nothing" | 262 // array list implementation is "all or nothing" |
| 263 return 0; | 263 return 0; |
| 264 } | 264 } |
| 265 } | 265 } |
| 266 | 266 |
| 267 static size_t cx_arl_insert_sorted( | |
| 268 struct cx_list_s *list, | |
| 269 void const *sorted_data, | |
| 270 size_t n | |
| 271 ) { | |
| 272 // corner case | |
| 273 if (n == 0) return 0; | |
| 274 | |
| 275 // define some handy pointers | |
| 276 cx_array_list *arl = (cx_array_list *) list; | |
| 277 cx_compare_func cmp = list->collection.cmpfunc; | |
| 278 | |
| 279 // store some counts | |
| 280 size_t old_size = list->collection.size; | |
| 281 size_t capacity = arl->capacity; | |
| 282 size_t needed_capacity = old_size + n; | |
| 283 size_t elem_size = list->collection.elem_size; | |
| 284 | |
| 285 // if we need more than we have, try a reallocation | |
| 286 if (needed_capacity > capacity) { | |
| 287 capacity = needed_capacity - (needed_capacity % 16) + 16; | |
| 288 if (0 != cxReallocate(list->collection.allocator, | |
| 289 &(arl->data), | |
| 290 capacity * elem_size)) { | |
| 291 // give it up right away, there is no contract | |
| 292 // that requires us to insert as much as we can | |
| 293 return 0; | |
| 294 } | |
| 295 arl->capacity = capacity; | |
| 296 } | |
| 297 | |
| 298 // now we have guaranteed that we can insert everything | |
| 299 size_t new_size = list->collection.size + n; | |
| 300 list->collection.size = new_size; | |
| 301 | |
| 302 // declare the source and destination indices/pointers | |
| 303 size_t si = 0, di = 0; | |
| 304 char const *src = sorted_data; | |
| 305 char *dest = arl->data; | |
| 306 | |
| 307 // find the first insertion point | |
| 308 while (di < old_size) { | |
| 309 if (cmp(src, dest) < 0) { | |
| 310 break; | |
| 311 } | |
| 312 di++; | |
| 313 dest += elem_size; | |
| 314 } | |
| 315 | |
| 316 // move the remaining elements in the array completely to the right | |
| 317 // we will call it the "buffer" for parked elements | |
| 318 size_t buf_size = old_size - di; | |
| 319 size_t bi = new_size - buf_size; | |
| 320 char *bptr = ((char *) arl->data) + bi * elem_size; | |
| 321 memmove(bptr, dest, buf_size * elem_size); | |
| 322 | |
| 323 // while there are both source and buffered elements left, | |
| 324 // copy them interleaving | |
| 325 while (si < n && bi < new_size) { | |
| 326 // determine how many source elements can be inserted | |
| 327 size_t copy_len = 1; | |
| 328 si++; | |
| 329 char const *next_src = src + elem_size; | |
| 330 while (si < n) { | |
| 331 if (cmp(bptr, next_src) < 0) { | |
| 332 break; | |
| 333 } | |
| 334 copy_len++; | |
| 335 si++; | |
| 336 next_src += elem_size; | |
| 337 } | |
| 338 | |
| 339 // copy the source elements | |
| 340 memcpy(dest, src, copy_len * elem_size); | |
| 341 dest += copy_len * elem_size; | |
| 342 src = next_src; | |
| 343 | |
| 344 // determine how many buffered elements need to be restored | |
| 345 copy_len = 1; | |
| 346 bi++; | |
| 347 char *next_bptr = bptr + elem_size; | |
| 348 while (bi < new_size) { | |
| 349 if (cmp(src, next_bptr) < 0) { | |
| 350 break; | |
| 351 } | |
| 352 copy_len++; | |
| 353 bi++; | |
| 354 next_bptr += elem_size; | |
| 355 } | |
| 356 | |
| 357 // restore the buffered elements | |
| 358 memmove(dest, bptr, copy_len * elem_size); | |
| 359 dest += copy_len * elem_size; | |
| 360 bptr = next_bptr; | |
| 361 } | |
| 362 | |
| 363 // still source elements left? simply append them | |
| 364 if (si < n) { | |
| 365 memcpy(dest, src, elem_size * (n - si)); | |
| 366 } | |
| 367 | |
| 368 // still buffer elements left? | |
| 369 // don't worry, we already moved them to the correct place | |
| 370 | |
| 371 return n; | |
| 372 } | |
| 373 | |
| 267 static int cx_arl_insert_element( | 374 static int cx_arl_insert_element( |
| 268 struct cx_list_s *list, | 375 struct cx_list_s *list, |
| 269 size_t index, | 376 size_t index, |
| 270 void const *element | 377 void const *element |
| 271 ) { | 378 ) { |
| 519 | 626 |
| 520 static cx_list_class cx_array_list_class = { | 627 static cx_list_class cx_array_list_class = { |
| 521 cx_arl_destructor, | 628 cx_arl_destructor, |
| 522 cx_arl_insert_element, | 629 cx_arl_insert_element, |
| 523 cx_arl_insert_array, | 630 cx_arl_insert_array, |
| 524 cx_list_default_insert_sorted, | 631 cx_arl_insert_sorted, |
| 525 cx_arl_insert_iter, | 632 cx_arl_insert_iter, |
| 526 cx_arl_remove, | 633 cx_arl_remove, |
| 527 cx_arl_clear, | 634 cx_arl_clear, |
| 528 cx_arl_swap, | 635 cx_arl_swap, |
| 529 cx_arl_at, | 636 cx_arl_at, |
