Debian Codegraph @

src/basic/sort-util.c

raw
1 /* SPDX-License-Identifier: LGPL-2.1-or-later */
2
3 #include <stdlib.h>
4
5 #include "alloc-util.h"
6 #include "sort-util.h"
7
8 /* hey glibc, APIs with callbacks without a user pointer are so useless */
9 void *xbsearch_r(const void *key, const void *base, size_t nmemb, size_t size,
10 comparison_userdata_fn_t compar, void *arg) {
11 size_t l, u, idx;
12 const void *p;
13 int comparison;
14
15 assert(!size_multiply_overflow(nmemb, size));
16
17 l = 0;
18 u = nmemb;
19 while (l < u) {
20 idx = (l + u) / 2;
21 p = (const uint8_t*) base + idx * size;
22 comparison = compar(key, p, arg);
23 if (comparison < 0)
24 u = idx;
25 else if (comparison > 0)
26 l = idx + 1;
27 else
28 return (void *)p;
29 }
30 return NULL;
31 }
32
33 void* bsearch_safe_internal(const void *key, const void *base, size_t nmemb, size_t size, comparison_fn_t compar) {
34 /**
35 * Normal bsearch requires base to be nonnull. Here were require
36 * that only if nmemb > 0.
37 */
38
39 if (nmemb <= 0)
40 return NULL;
41
42 assert(base);
43 return (void*) bsearch(key, base, nmemb, size, compar);
44 }
45
46 void qsort_safe(void *base, size_t nmemb, size_t size, comparison_fn_t compar) {
47 /**
48 * Normal qsort requires base to be nonnull. Here were require
49 * that only if nmemb > 0.
50 */
51
52 if (nmemb <= 1)
53 return;
54
55 assert(base);
56 qsort(base, nmemb, size, compar);
57 }
58
59 void qsort_r_safe(void *base, size_t nmemb, size_t size, comparison_userdata_fn_t compar, void *userdata) {
60 if (nmemb <= 1)
61 return;
62
63 assert(base);
64 qsort_r(base, nmemb, size, compar, userdata);
65 }
66
67 int cmp_int(const int *a, const int *b) {
68 /* This is called from qsort()s inner loops. Correctly implemented qsort will never pass NULL so we
69 just suppress the check via POINTER_MAY_BE_NULL instead of assert() to avoid the runtime cost. */
70 POINTER_MAY_BE_NULL(a);
71 POINTER_MAY_BE_NULL(b);
72
73 return CMP(*a, *b);
74 }
75
76 int cmp_uint16(const uint16_t *a, const uint16_t *b) {
77 /* This is called from qsort()s inner loops. Correctly implemented qsort will never pass NULL so we
78 just suppress the check via POINTER_MAY_BE_NULL instead of assert() to avoid the runtime cost. */
79 POINTER_MAY_BE_NULL(a);
80 POINTER_MAY_BE_NULL(b);
81
82 return CMP(*a, *b);
83 }
84
85 int cmp_unsigned(const unsigned *a, const unsigned *b) {
86 /* This is called from qsort()s inner loops. Correctly implemented qsort will never pass NULL so we
87 just suppress the check via POINTER_MAY_BE_NULL instead of assert() to avoid the runtime cost. */
88 POINTER_MAY_BE_NULL(a);
89 POINTER_MAY_BE_NULL(b);
90
91 return CMP(*a, *b);
92 }