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
|
#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "binary-multisearch.h"
static struct binary_multisearch_stack_entry stack[16];
static ssize_t result[1 << 16];
static short int sought[1 << 16];
static short int list[1 << 16];
static size_t sought_count;
static size_t list_count;
static int
cmp(const void *a, const void *b, void *data)
{
const short int *x = a, *y = b;
(void) data;
return *x < *y ? -1 : *x > *y;
}
static short int
random16(short int mask)
{
return (short int)((((rand() & 255) << 8) | (rand() & 255)) & mask);
}
static void
fill_random16(short int arr[], size_t n, short int mask)
{
while (n--)
arr[n] = random16(mask);
}
static size_t
uniq(short int arr[], size_t n)
{
size_t r, w = (n > 0);
for (r = 1; r < n; r++)
if (arr[r] != arr[r - 1])
arr[w++] = arr[r];
return w;
}
static void
test(size_t sn, size_t ln, short int mask)
{
size_t i, p;
sought_count = sn;
list_count = ln;
fill_random16(sought, sought_count, mask);
fill_random16(list, list_count, mask);
qsort_r(sought, sought_count, sizeof(*sought), cmp, NULL);
qsort_r(list, list_count, sizeof(*list), cmp, NULL);
sought_count = uniq(sought, sought_count);
for (i = 0; i < sought_count; i++)
result[i] = SIZE_MAX / 2;
binary_multisearch(sought, sought_count, sizeof(*sought), list, list_count,
sizeof(*list), cmp, NULL, binary_search, stack, result);
for (i = 0; i < sought_count; i++) {
if (list_count == 0) {
if (result[i] != -1)
exit(1);
continue;
}
if (result[i] >= (ssize_t)list_count) {
exit(2);
}
if (result[i] >= 0) {
if (list[result[i]] != sought[i])
exit(3);
continue;
}
p = (size_t)(-result[i] - 1);
if (p > list_count) {
exit(4);
}
if (p == list_count) {
if (list[p - 1] >= sought[i])
exit(5);
continue;
}
if (list[p] <= sought[i])
exit(6);
if (p && list[p - 1] >= sought[i])
exit(7);
}
}
int
main(void)
{
size_t i, j;
short int mask;
srand((unsigned)time(NULL));
for (i = 1; i <= 16; i++) {
mask = (short int)(((size_t)1 << i) - 1);
test(0, 0, mask);
test(0, 10, mask);
test(10, 0, mask);
for (j = 0; j < 100; j++) {
test((size_t)(unsigned short int)random16(mask) + 1,
(size_t)(unsigned short int)random16(mask) + 1, mask);
}
}
return 0;
}
|
