| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #ifndef UTIL_BSEARCH_H | ||
| 2 | #define UTIL_BSEARCH_H | ||
| 3 | |||
| 4 | #include <stddef.h> | ||
| 5 | #include <stdlib.h> | ||
| 6 | #include <string.h> | ||
| 7 | #include <sys/types.h> | ||
| 8 | #include "array.h" | ||
| 9 | #include "debug.h" | ||
| 10 | #include "macros.h" | ||
| 11 | |||
| 12 | typedef int (*CompareFunction)(const void *key, const void *elem); | ||
| 13 | typedef int (*StringCompareFunction)(const char *key, const char *elem); | ||
| 14 | |||
| 15 | #define BSEARCH(key, a, cmp) bsearch(key, a, ARRAYLEN(a), sizeof(a[0]), cmp) | ||
| 16 | #define BSEARCH_IDX(key, a, cmp) bisearch_idx(key, a, ARRAYLEN(a), sizeof(a[0]), cmp) | ||
| 17 | |||
| 18 | #define CHECK_BSEARCH_ARRAY(a, field, cmp) do { \ | ||
| 19 | static_assert_flat_struct_array(a, field); \ | ||
| 20 | check_bsearch_array ( \ | ||
| 21 | a, #a, "." #field, ARRAYLEN(a), sizeof(a[0]), sizeof(a[0].field), cmp \ | ||
| 22 | ); \ | ||
| 23 | } while (0) | ||
| 24 | |||
| 25 | #define CHECK_BSEARCH_STR_ARRAY(a, cmp) do { \ | ||
| 26 | static_assert_flat_string_array(a); \ | ||
| 27 | check_bsearch_array(a, #a, "", ARRAYLEN(a), sizeof(a[0]), sizeof(a[0]), cmp); \ | ||
| 28 | } while (0) | ||
| 29 | |||
| 30 | // NOLINTNEXTLINE(readability-function-size): 7 param debug function is fine | ||
| 31 | 288 | static inline void check_bsearch_array ( | |
| 32 | const void *base, | ||
| 33 | const char *array_name, | ||
| 34 | const char *name_field_name, | ||
| 35 | size_t array_len, | ||
| 36 | size_t elem_size, | ||
| 37 | size_t name_size, | ||
| 38 | StringCompareFunction cmp | ||
| 39 | ) { | ||
| 40 | 288 | if (DEBUG < 1) { | |
| 41 | return; | ||
| 42 | } | ||
| 43 | |||
| 44 | 288 | BUG_ON(!cmp); | |
| 45 | 288 | check_array(base, array_name, name_field_name, array_len, elem_size, name_size); | |
| 46 | |||
| 47 | 288 | const char *first_name = base; | |
| 48 |
2/2✓ Branch 0 taken 15570 times.
✓ Branch 1 taken 288 times.
|
15858 | for (size_t i = 1; i < array_len; i++) { |
| 49 | 15570 | const char *curr_name = first_name + (i * elem_size); | |
| 50 | 15570 | const char *prev_name = curr_name - elem_size; | |
| 51 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 15570 times.
|
15570 | if (cmp(curr_name, prev_name) <= 0) { |
| 52 | − | BUG ( | |
| 53 | "String at %s[%zu]%s not in sorted order: \"%s\" (prev: \"%s\")", | ||
| 54 | array_name, i, name_field_name, | ||
| 55 | curr_name, prev_name | ||
| 56 | ); | ||
| 57 | } | ||
| 58 | } | ||
| 59 | } | ||
| 60 | |||
| 61 | // Like bsearch(3), but returning the index of the element instead of | ||
| 62 | // a pointer to it (or -1 if not found) | ||
| 63 | 9262 | static inline ssize_t bisearch_idx ( | |
| 64 | const void *key, | ||
| 65 | const void *base, | ||
| 66 | size_t nmemb, | ||
| 67 | size_t size, | ||
| 68 | CompareFunction compare | ||
| 69 | ) { | ||
| 70 | 9262 | const char *found = bsearch(key, base, nmemb, size, compare); | |
| 71 |
2/2✓ Branch 0 taken 223 times.
✓ Branch 1 taken 9039 times.
|
9262 | if (!found) { |
| 72 | return -1; | ||
| 73 | } | ||
| 74 | 223 | const char *char_base = base; | |
| 75 | 223 | return (size_t)(found - char_base) / size; | |
| 76 | } | ||
| 77 | |||
| 78 | // This is a wrapper around strcmp(3) with void* parameters, suitable | ||
| 79 | // for use with bsearch(3) without the need for casting | ||
| 80 | 38076 | static inline int vstrcmp(const void *a, const void *b) | |
| 81 | { | ||
| 82 | 38076 | return strcmp(a, b); | |
| 83 | } | ||
| 84 | |||
| 85 | #endif | ||
| 86 |