comparison: src/cx/array_list.h
src/cx/array_list.h
- changeset 890
- 54565fd74e74
- parent 887
- e5181fe13b9c
- child 891
- 49d8cff6f0ee
equal
deleted
inserted
replaced
| 889:f549fd9fbd8f | 890:54565fd74e74 |
|---|---|
| 162 enum cx_array_result cx_array_copy( | 162 enum cx_array_result cx_array_copy( |
| 163 void **target, | 163 void **target, |
| 164 size_t *size, | 164 size_t *size, |
| 165 size_t *capacity, | 165 size_t *capacity, |
| 166 size_t index, | 166 size_t index, |
| 167 void const *src, | 167 const void *src, |
| 168 size_t elem_size, | 168 size_t elem_size, |
| 169 size_t elem_count, | 169 size_t elem_count, |
| 170 struct cx_array_reallocator_s *reallocator | 170 struct cx_array_reallocator_s *reallocator |
| 171 ) __attribute__((__nonnull__(1, 2, 5))); | 171 ) __attribute__((__nonnull__(1, 2, 5))); |
| 172 | 172 |
| 239 enum cx_array_result cx_array_insert_sorted( | 239 enum cx_array_result cx_array_insert_sorted( |
| 240 void **target, | 240 void **target, |
| 241 size_t *size, | 241 size_t *size, |
| 242 size_t *capacity, | 242 size_t *capacity, |
| 243 cx_compare_func cmp_func, | 243 cx_compare_func cmp_func, |
| 244 void const *src, | 244 const void *src, |
| 245 size_t elem_size, | 245 size_t elem_size, |
| 246 size_t elem_count, | 246 size_t elem_count, |
| 247 struct cx_array_reallocator_s *reallocator | 247 struct cx_array_reallocator_s *reallocator |
| 248 ) __attribute__((__nonnull__)); | 248 ) __attribute__((__nonnull__)); |
| 249 | 249 |
| 314 * @param elem the element to find | 314 * @param elem the element to find |
| 315 * @param cmp_func the compare function | 315 * @param cmp_func the compare function |
| 316 * @return the index of the largest lower bound, or \p size | 316 * @return the index of the largest lower bound, or \p size |
| 317 */ | 317 */ |
| 318 size_t cx_array_binary_search_inf( | 318 size_t cx_array_binary_search_inf( |
| 319 void const *arr, | 319 const void *arr, |
| 320 size_t size, | 320 size_t size, |
| 321 size_t elem_size, | 321 size_t elem_size, |
| 322 void const *elem, | 322 const void *elem, |
| 323 cx_compare_func cmp_func | 323 cx_compare_func cmp_func |
| 324 ) __attribute__((__nonnull__)); | 324 ) __attribute__((__nonnull__)); |
| 325 | 325 |
| 326 /** | 326 /** |
| 327 * Searches an item in a sorted array. | 327 * Searches an item in a sorted array. |
| 337 * @return the index of the element in the array, or \p size if the element | 337 * @return the index of the element in the array, or \p size if the element |
| 338 * cannot be found | 338 * cannot be found |
| 339 */ | 339 */ |
| 340 __attribute__((__nonnull__)) | 340 __attribute__((__nonnull__)) |
| 341 static inline size_t cx_array_binary_search( | 341 static inline size_t cx_array_binary_search( |
| 342 void const *arr, | 342 const void *arr, |
| 343 size_t size, | 343 size_t size, |
| 344 size_t elem_size, | 344 size_t elem_size, |
| 345 void const *elem, | 345 const void *elem, |
| 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 if (index < size && cmp_func(((char const *) arr) + index * elem_size, elem) == 0) { | 351 if (index < size && cmp_func(((const char *) arr) + index * elem_size, elem) == 0) { |
| 352 return index; | 352 return index; |
| 353 } else { | 353 } else { |
| 354 return size; | 354 return size; |
| 355 } | 355 } |
| 356 } | 356 } |
| 375 * @param cmp_func the compare function | 375 * @param cmp_func the compare function |
| 376 * @return the index of the smallest upper bound, or \p size | 376 * @return the index of the smallest upper bound, or \p size |
| 377 */ | 377 */ |
| 378 __attribute__((__nonnull__)) | 378 __attribute__((__nonnull__)) |
| 379 static inline size_t cx_array_binary_search_sup( | 379 static inline size_t cx_array_binary_search_sup( |
| 380 void const *arr, | 380 const void *arr, |
| 381 size_t size, | 381 size_t size, |
| 382 size_t elem_size, | 382 size_t elem_size, |
| 383 void const *elem, | 383 const void *elem, |
| 384 cx_compare_func cmp_func | 384 cx_compare_func cmp_func |
| 385 ) { | 385 ) { |
| 386 size_t inf = cx_array_binary_search_inf(arr, size, elem_size, elem, cmp_func); | 386 size_t inf = cx_array_binary_search_inf(arr, size, elem_size, elem, cmp_func); |
| 387 if (inf == size) { | 387 if (inf == size) { |
| 388 // no infimum means, first element is supremum | 388 // no infimum means, first element is supremum |
| 389 return 0; | 389 return 0; |
| 390 } else if (cmp_func(((char const *) arr) + inf * elem_size, elem) == 0) { | 390 } else if (cmp_func(((const char *) arr) + inf * elem_size, elem) == 0) { |
| 391 return inf; | 391 return inf; |
| 392 } else { | 392 } else { |
| 393 return inf + 1; | 393 return inf + 1; |
| 394 } | 394 } |
| 395 } | 395 } |
| 424 * @param elem_size the size of each element in bytes | 424 * @param elem_size the size of each element in bytes |
| 425 * @param initial_capacity the initial number of elements the array can store | 425 * @param initial_capacity the initial number of elements the array can store |
| 426 * @return the created list | 426 * @return the created list |
| 427 */ | 427 */ |
| 428 CxList *cxArrayListCreate( | 428 CxList *cxArrayListCreate( |
| 429 CxAllocator const *allocator, | 429 const CxAllocator *allocator, |
| 430 cx_compare_func comparator, | 430 cx_compare_func comparator, |
| 431 size_t elem_size, | 431 size_t elem_size, |
| 432 size_t initial_capacity | 432 size_t initial_capacity |
| 433 ); | 433 ); |
| 434 | 434 |
