comparison: src/cx/array_list.h
src/cx/array_list.h
- changeset 886
- 5f5514bb104b
- parent 885
- 878a450e79bd
- child 887
- e5181fe13b9c
equal
deleted
inserted
replaced
| 885:878a450e79bd | 886:5f5514bb104b |
|---|---|
| 346 cx_compare_func cmp_func | 346 cx_compare_func cmp_func |
| 347 ) { | 347 ) { |
| 348 size_t index = cx_array_binary_search_inf( | 348 size_t index = cx_array_binary_search_inf( |
| 349 arr, size, elem_size, elem, cmp_func | 349 arr, size, elem_size, elem, cmp_func |
| 350 ); | 350 ); |
| 351 char const *found = ((char const *) arr) + index * elem_size; | 351 if (index < size && cmp_func(((char const *) arr) + index * elem_size, elem) == 0) { |
| 352 if (cmp_func(found, elem) == 0) { | |
| 353 return index; | 352 return index; |
| 354 } else { | 353 } else { |
| 355 return size; | 354 return size; |
| 355 } | |
| 356 } | |
| 357 | |
| 358 /** | |
| 359 * Searches the smallest upper bound in a sorted array. | |
| 360 * | |
| 361 * In other words, this function returns the index of the smallest element | |
| 362 * in \p arr that is greater or equal to \p elem with respect to \p cmp_func. | |
| 363 * When no such element exists, \p size is returned. | |
| 364 * | |
| 365 * If \p elem is contained in the array, this is identical to | |
| 366 * #cx_array_binary_search(). | |
| 367 * | |
| 368 * If the array is not sorted with respect to the \p cmp_func, the behavior | |
| 369 * is undefined. | |
| 370 * | |
| 371 * @param arr the array to search | |
| 372 * @param size the size of the array | |
| 373 * @param elem_size the size of one element | |
| 374 * @param elem the element to find | |
| 375 * @param cmp_func the compare function | |
| 376 * @return the index of the largest upper bound, or \p size | |
| 377 */ | |
| 378 __attribute__((__nonnull__)) | |
| 379 static inline size_t cx_array_binary_search_sup( | |
| 380 void const *arr, | |
| 381 size_t size, | |
| 382 size_t elem_size, | |
| 383 void const *elem, | |
| 384 cx_compare_func cmp_func | |
| 385 ) { | |
| 386 size_t inf = cx_array_binary_search_inf(arr, size, elem_size, elem, cmp_func); | |
| 387 if (inf == size) { | |
| 388 // no infimum means, first element is supremum | |
| 389 return 0; | |
| 390 } else if (cmp_func(((char const *) arr) + inf * elem_size, elem) == 0) { | |
| 391 return inf; | |
| 392 } else { | |
| 393 return inf + 1; | |
| 356 } | 394 } |
| 357 } | 395 } |
| 358 | 396 |
| 359 /** | 397 /** |
| 360 * Swaps two array elements. | 398 * Swaps two array elements. |
