| 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 DO_CHECK_BSEARCH_ARRAY(a, field, cmp) \ | ||
| 19 | static_assert_flat_struct_array(a, field); \ | ||
| 20 | check_bsearch_array(a, #a, "." #field, ARRAYLEN(a), sizeof(a[0]), sizeof(a[0].field), cmp) | ||
| 21 | |||
| 22 | #define CHECK_BSEARCH_STR_ARRAY(a) \ | ||
| 23 | static_assert_flat_string_array(a); \ | ||
| 24 | check_bsearch_array(a, #a, "", ARRAYLEN(a), sizeof(a[0]), sizeof(a[0]), strcmp) | ||
| 25 | |||
| 26 | #define CHECK_BSEARCH_ARRAY(a, field) DO_CHECK_BSEARCH_ARRAY(a, field, strcmp) | ||
| 27 | #define CHECK_BSEARCH_ARRAY_ICASE(a, field) DO_CHECK_BSEARCH_ARRAY(a, field, ascii_strcmp_icase) | ||
| 28 | |||
| 29 | // NOLINTNEXTLINE(readability-function-size): 7 param debug function is fine | ||
| 30 | 352 | static inline void check_bsearch_array ( | |
| 31 | const void *base, | ||
| 32 | const char *array_name, | ||
| 33 | const char *name_field_name, | ||
| 34 | size_t array_len, | ||
| 35 | size_t elem_size, | ||
| 36 | size_t name_size, | ||
| 37 | StringCompareFunction cmp | ||
| 38 | ) { | ||
| 39 | 352 | if (!DEBUG_ASSERTIONS_ENABLED) { | |
| 40 | return; | ||
| 41 | } | ||
| 42 | |||
| 43 | 352 | BUG_ON(!cmp); | |
| 44 | 352 | check_array(base, array_name, name_field_name, array_len, elem_size, name_size); | |
| 45 | |||
| 46 | 352 | const char *first_name = base; | |
| 47 |
2/2✓ Branch 0 (10→6) taken 19624 times.
✓ Branch 1 (10→11) taken 352 times.
|
19976 | for (size_t i = 1; i < array_len; i++) { |
| 48 | 19624 | const char *curr_name = first_name + (i * elem_size); | |
| 49 | 19624 | const char *prev_name = curr_name - elem_size; | |
| 50 |
1/2✗ Branch 0 (7→8) not taken.
✓ Branch 1 (7→9) taken 19624 times.
|
19624 | if (cmp(curr_name, prev_name) <= 0) { |
| 51 | − | BUG ( | |
| 52 | "String at %s[%zu]%s not in sorted order: \"%s\" (prev: \"%s\")", | ||
| 53 | array_name, i, name_field_name, | ||
| 54 | curr_name, prev_name | ||
| 55 | ); | ||
| 56 | } | ||
| 57 | } | ||
| 58 | } | ||
| 59 | |||
| 60 | // Like bsearch(3), but returning the index of the element instead of | ||
| 61 | // a pointer to it (or -1 if not found) | ||
| 62 | 9489 | static inline ssize_t bisearch_idx ( | |
| 63 | const void *key, | ||
| 64 | const void *base, | ||
| 65 | size_t nmemb, | ||
| 66 | size_t size, | ||
| 67 | CompareFunction compare | ||
| 68 | ) { | ||
| 69 | 9489 | const char *found = bsearch(key, base, nmemb, size, compare); | |
| 70 |
2/2✓ Branch 0 (3→4) taken 261 times.
✓ Branch 1 (3→5) taken 9228 times.
|
9489 | if (!found) { |
| 71 | return -1; | ||
| 72 | } | ||
| 73 | 261 | const char *char_base = base; | |
| 74 | 261 | return (size_t)(found - char_base) / size; | |
| 75 | } | ||
| 76 | |||
| 77 | // This is a wrapper around strcmp(3) with void* parameters, suitable | ||
| 78 | // for use in bsearch(3) without the need for casting | ||
| 79 | 39388 | static inline int vstrcmp(const void *a, const void *b) | |
| 80 | { | ||
| 81 | 39388 | return strcmp(a, b); | |
| 82 | } | ||
| 83 | |||
| 84 | #endif | ||
| 85 |