comparison: src/array_list.c
src/array_list.c
- changeset 884
- d375d8056262
- parent 883
- 3012e9b4214e
- child 885
- 878a450e79bd
equal
deleted
inserted
replaced
| 883:3012e9b4214e | 884:d375d8056262 |
|---|---|
| 234 // don't worry, we already moved them to the correct place | 234 // don't worry, we already moved them to the correct place |
| 235 | 235 |
| 236 return CX_ARRAY_SUCCESS; | 236 return CX_ARRAY_SUCCESS; |
| 237 } | 237 } |
| 238 | 238 |
| 239 size_t cx_array_binary_search_inf( | |
| 240 void const *arr, | |
| 241 size_t size, | |
| 242 size_t elem_size, | |
| 243 void const *elem, | |
| 244 cx_compare_func cmp_func | |
| 245 ) { | |
| 246 // declare a variable that will contain the compare results | |
| 247 int result; | |
| 248 | |
| 249 // cast the array pointer to something we can use offsets with | |
| 250 char const *array = arr; | |
| 251 | |
| 252 // check the first array element | |
| 253 result = cmp_func(elem, array); | |
| 254 if (result <= 0) { | |
| 255 return 0; | |
| 256 } | |
| 257 | |
| 258 // check the last array element | |
| 259 result = cmp_func(elem, array + elem_size * (size - 1)); | |
| 260 if (result >= 0) { | |
| 261 return size - 1; | |
| 262 } | |
| 263 | |
| 264 // the element is now guaranteed to be somewhere in the list | |
| 265 // so start the binary search | |
| 266 size_t left_index = 1; | |
| 267 size_t right_index = size - 1; | |
| 268 size_t pivot_index; | |
| 269 | |
| 270 while (left_index <= right_index) { | |
| 271 pivot_index = left_index + (right_index - left_index) / 2; | |
| 272 char const *arr_elem = array + pivot_index * elem_size; | |
| 273 result = cmp_func(elem, arr_elem); | |
| 274 if (result == 0) { | |
| 275 // found it! | |
| 276 return pivot_index; | |
| 277 } else if (result < 0) { | |
| 278 // element is smaller than pivot, continue search left | |
| 279 right_index = pivot_index - 1; | |
| 280 } else { | |
| 281 // element is larger than pivot, continue search right | |
| 282 left_index = pivot_index + 1; | |
| 283 } | |
| 284 } | |
| 285 | |
| 286 // report the largest upper bound | |
| 287 return result < 0 ? (pivot_index - 1) : pivot_index; | |
| 288 } | |
| 289 | |
| 239 #ifndef CX_ARRAY_SWAP_SBO_SIZE | 290 #ifndef CX_ARRAY_SWAP_SBO_SIZE |
| 240 #define CX_ARRAY_SWAP_SBO_SIZE 128 | 291 #define CX_ARRAY_SWAP_SBO_SIZE 128 |
| 241 #endif | 292 #endif |
| 242 unsigned cx_array_swap_sbo_size = CX_ARRAY_SWAP_SBO_SIZE; | 293 unsigned cx_array_swap_sbo_size = CX_ARRAY_SWAP_SBO_SIZE; |
| 243 | 294 |
