1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
|
/* See LICENSE file for copyright and license details. */
#include "common.h"
#ifdef USE_INTERPOLATION_SEARCH
# ifndef INTERPOLATION_SEARCH_FLOAT
# define INTERPOLATION_SEARCH_FLOAT long double
# endif
/* convertion to unsigned is a modulo (unsigned maximum + 1) operation */
# define DIFF(TYPE, A, B) ((unsigned TYPE)(A) - (unsigned TYPE)(B))
# define INTERPOL_SEARCH(KEY, BASE, N, READ)\
do {\
INTERPOLATION_SEARCH_FLOAT guess_d;\
unsigned long long int guess;\
size_t h = (N);\
\
if (!h--)\
return NULL;\
\
if ((KEY) <= READ((BASE), 0))\
return (KEY) == READ((BASE), 0) ? &(BASE)[0] : NULL;\
if ((KEY) >= READ((BASE), h))\
return (KEY) == READ((BASE), h) ? &(BASE)[h] : NULL;\
if (READ((BASE), 0) == READ((BASE), h))\
return NULL;\
\
goto use_double;\
guess = DIFF(long long int, (KEY), READ((BASE), 0));\
if (h > ULLONG_MAX / guess)\
goto use_double;\
\
for (;;) {\
guess = DIFF(long long int, (KEY), READ((BASE), 0));\
guess *= (unsigned long long int)h;\
guess /= DIFF(long long int, READ((BASE), h), READ((BASE), 0));\
\
if (READ((BASE), guess) < (KEY)) {\
h -= guess += 1;\
(BASE) = &(BASE)[guess];\
} else if (READ((BASE), guess) > (KEY)) {\
h = guess -= 1;\
} else {\
return &(BASE)[guess];\
}\
\
if ((KEY) <= READ((BASE), 0))\
return (KEY) == READ((BASE), 0) ? &(BASE)[0] : NULL;\
if ((KEY) >= READ((BASE), h))\
return (KEY) == READ((BASE), h) ? &(BASE)[h] : NULL;\
if (READ((BASE), 0) == READ((BASE), h))\
return NULL;\
}\
\
use_double:\
for (;;) {\
guess = DIFF(long long int, (KEY), READ((BASE), 0));\
guess_d = (INTERPOLATION_SEARCH_FLOAT)guess * (INTERPOLATION_SEARCH_FLOAT)h;\
guess = DIFF(long long int, READ((BASE), h), READ((BASE), 0));\
guess_d /= (INTERPOLATION_SEARCH_FLOAT)guess;\
guess = (unsigned long long int)guess_d;\
\
if (READ((BASE), guess) < (KEY)) {\
h -= guess += 1;\
(BASE) = &(BASE)[guess];\
} else if (READ((BASE), guess) > (KEY)) {\
h = guess -= 1;\
} else {\
return &(BASE)[guess];\
}\
\
if ((KEY) <= READ((BASE), 0))\
return (KEY) == READ((BASE), 0) ? &(BASE)[0] : NULL;\
if ((KEY) >= READ((BASE), h))\
return (KEY) == READ((BASE), h) ? &(BASE)[h] : NULL;\
if (READ((BASE), 0) == READ((BASE), h))\
return NULL;\
}\
} while (0)
#else
PURE_FUNCTION
static int
signed_named_number_cmp(const void *a_, const void *b_)
{
const struct libsyscalls_named_number *a = a_, *b = b_;
return a->number.s < b->number.s ? -1 : a->number.s > b->number.s;
}
PURE_FUNCTION
static int
unsigned_named_number_cmp(const void *a_, const void *b_)
{
const struct libsyscalls_named_number *a = a_, *b = b_;
return a->number.u < b->number.u ? -1 : a->number.u > b->number.u;
}
#endif
const struct libsyscalls_named_number *
libsyscalls_find_signed_named_number(signed long long int key,
const struct libsyscalls_named_number *base, size_t n)
{
#ifdef USE_INTERPOLATION_SEARCH
# define X(ARR, I) ((ARR)[I].number.s)
INTERPOL_SEARCH(key, base, n, X);
# undef X
#else
struct libsyscalls_named_number struct_key = {.number.s = key};
return bsearch(&struct_key, base, n, sizeof(*base), &signed_named_number_cmp);
#endif
}
const struct libsyscalls_named_number *
libsyscalls_find_unsigned_named_number(unsigned long long int key,
const struct libsyscalls_named_number *base, size_t n)
{
#ifdef USE_INTERPOLATION_SEARCH
# define X(ARR, I) ((ARR)[I].number.u)
INTERPOL_SEARCH(key, base, n, X);
# undef X
#else
struct libsyscalls_named_number struct_key = {.number.u = key};
return bsearch(&struct_key, base, n, sizeof(*base), &unsigned_named_number_cmp);
#endif
}
extern inline const struct libsyscalls_named_number *
libsyscalls_find_named_number(unsigned long long int key, int is_signed,
const struct libsyscalls_named_number *base, size_t n);
|
