comparison: src/cx/array_list.h
src/cx/array_list.h
- changeset 884
- d375d8056262
- parent 883
- 3012e9b4214e
- child 885
- 878a450e79bd
equal
deleted
inserted
replaced
| 883:3012e9b4214e | 884:d375d8056262 |
|---|---|
| 292 */ | 292 */ |
| 293 #define cx_array_simple_insert_sorted(array, src, n, cmp_func) \ | 293 #define cx_array_simple_insert_sorted(array, src, n, cmp_func) \ |
| 294 cx_array_insert_sorted((void**)(&array), &(array##_size), &(array##_capacity), \ | 294 cx_array_insert_sorted((void**)(&array), &(array##_size), &(array##_capacity), \ |
| 295 cmp_func, src, sizeof((array)[0]), n, cx_array_default_reallocator) | 295 cmp_func, src, sizeof((array)[0]), n, cx_array_default_reallocator) |
| 296 | 296 |
| 297 | |
| 298 /** | |
| 299 * Searches the largest lower bound in a sorted array. | |
| 300 * | |
| 301 * In other words, this function returns the index of the largest element | |
| 302 * in \p arr that is less or equal to \p elem with respect to \p cmp_func. | |
| 303 * | |
| 304 * If \p elem is contained in the array, this is identical to | |
| 305 * #cx_array_binary_search(). | |
| 306 * | |
| 307 * If the array is not sorted with respect to the \p cmp_func, the behavior | |
| 308 * is undefined. | |
| 309 * | |
| 310 * @param arr the array to search | |
| 311 * @param size the size of the array | |
| 312 * @param elem_size the size of one element | |
| 313 * @param elem the element to find | |
| 314 * @param cmp_func the compare function | |
| 315 * @return the index of the closest element in the array | |
| 316 */ | |
| 317 size_t cx_array_binary_search_inf( | |
| 318 void const *arr, | |
| 319 size_t size, | |
| 320 size_t elem_size, | |
| 321 void const *elem, | |
| 322 cx_compare_func cmp_func | |
| 323 ) __attribute__((__nonnull__)); | |
| 324 | |
| 325 /** | |
| 326 * Searches an item in a sorted array. | |
| 327 * | |
| 328 * If the array is not sorted with respect to the \p cmp_func, the behavior | |
| 329 * is undefined. | |
| 330 * | |
| 331 * @param arr the array to search | |
| 332 * @param size the size of the array | |
| 333 * @param elem_size the size of one element | |
| 334 * @param elem the element to find | |
| 335 * @param cmp_func the compare function | |
| 336 * @return the index of the element in the array, or \p size if the element | |
| 337 * cannot be found | |
| 338 */ | |
| 339 __attribute__((__nonnull__)) | |
| 340 static inline size_t cx_array_binary_search( | |
| 341 void const *arr, | |
| 342 size_t size, | |
| 343 size_t elem_size, | |
| 344 void const *elem, | |
| 345 cx_compare_func cmp_func | |
| 346 ) { | |
| 347 size_t index = cx_array_binary_search_inf( | |
| 348 arr, size, elem_size, elem, cmp_func | |
| 349 ); | |
| 350 char const *found = ((char const *) arr) + index * elem_size; | |
| 351 if (cmp_func(found, elem) == 0) { | |
| 352 return index; | |
| 353 } else { | |
| 354 return size; | |
| 355 } | |
| 356 } | |
| 357 | |
| 297 /** | 358 /** |
| 298 * Swaps two array elements. | 359 * Swaps two array elements. |
| 299 * | 360 * |
| 300 * @param arr the array | 361 * @param arr the array |
| 301 * @param elem_size the element size | 362 * @param elem_size the element size |
