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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
|
/* This software was written by Dirk Engling <erdgeist@erdgeist.org>
It is considered beerware. Prost. Skol. Cheers or whatever.
$id$ */
/* System */
#include <stdlib.h>
#include <string.h>
/* Opentracker */
#include "trackerlogic.h"
#include "test.h"
/* binary_search returns the matching member when there is one, and otherwise
the position at which the key would have to be inserted to keep the vector
sorted. exactmatch distinguishes the two. */
static const unsigned char sorted[5][4] = {{0, 0, 0, 1}, {0, 0, 0, 3}, {0, 0, 0, 5}, {0, 0, 0, 7}, {0, 0, 0, 9}};
static void case_search_finds_member(void) {
const unsigned char key[4] = {0, 0, 0, 5};
int exactmatch;
void *found;
test_case("an existing key is found");
found = binary_search(key, sorted, 5, 4, 4, &exactmatch);
CHECK(exactmatch != 0);
CHECK_PTR(found, sorted[2]);
}
static void case_search_finds_first_and_last(void) {
const unsigned char first[4] = {0, 0, 0, 1};
const unsigned char last[4] = {0, 0, 0, 9};
int exactmatch;
test_case("the first and last members are found");
CHECK_PTR(binary_search(first, sorted, 5, 4, 4, &exactmatch), sorted[0]);
CHECK(exactmatch != 0);
CHECK_PTR(binary_search(last, sorted, 5, 4, 4, &exactmatch), sorted[4]);
CHECK(exactmatch != 0);
}
static void case_search_insert_position(void) {
const unsigned char middle[4] = {0, 0, 0, 4};
const unsigned char before[4] = {0, 0, 0, 0};
int exactmatch;
void *slot;
test_case("a missing key yields its insert position");
slot = binary_search(middle, sorted, 5, 4, 4, &exactmatch);
CHECK_INT(exactmatch, 0);
CHECK_PTR(slot, sorted[2]);
slot = binary_search(before, sorted, 5, 4, 4, &exactmatch);
CHECK_INT(exactmatch, 0);
CHECK_PTR(slot, sorted[0]);
}
static void case_search_past_the_end(void) {
const unsigned char beyond[4] = {0, 0, 0, 0xff};
int exactmatch;
void *slot;
test_case("a key above every member yields the position past the end");
slot = binary_search(beyond, sorted, 5, 4, 4, &exactmatch);
CHECK_INT(exactmatch, 0);
CHECK_PTR(slot, sorted[5]);
}
static void case_search_empty(void) {
int exactmatch;
void *base = (void *)sorted;
test_case("searching an empty vector reports no match at the base");
CHECK_PTR(binary_search(sorted[0], base, 0, 4, 4, &exactmatch), base);
CHECK_INT(exactmatch, 0);
}
static void case_insert_keeps_order(void) {
ot_vector vector = {NULL, 0, 0};
const unsigned char five[4] = {0, 0, 0, 5};
const unsigned char one[4] = {0, 0, 0, 1};
const unsigned char nine[4] = {0, 0, 0, 9};
int exactmatch;
void *slot;
test_case("inserts land in sorted order and grow the vector");
slot = vector_find_or_insert(&vector, (void *)five, 4, 4, &exactmatch);
CHECK(slot != NULL);
CHECK_INT(exactmatch, 0);
memcpy(slot, five, 4);
CHECK_INT(vector.size, 1);
CHECK_INT(vector.space, OT_VECTOR_MIN_MEMBERS);
slot = vector_find_or_insert(&vector, (void *)one, 4, 4, &exactmatch);
CHECK(slot != NULL);
CHECK_INT(exactmatch, 0);
memcpy(slot, one, 4);
CHECK_INT(vector.size, 2);
slot = vector_find_or_insert(&vector, (void *)nine, 4, 4, &exactmatch);
CHECK(slot != NULL);
CHECK_INT(exactmatch, 0);
memcpy(slot, nine, 4);
CHECK_INT(vector.size, 3);
CHECK_INT(vector.space, OT_VECTOR_MIN_MEMBERS * OT_VECTOR_GROW_RATIO);
CHECK_MEM(vector.data, "\0\0\0\1\0\0\0\5\0\0\0\11", 12);
free(vector.data);
}
static void case_insert_finds_existing(void) {
ot_vector vector = {NULL, 0, 0};
const unsigned char five[4] = {0, 0, 0, 5};
int exactmatch;
void *slot, *again;
test_case("a second insert of the same key returns the existing member");
slot = vector_find_or_insert(&vector, (void *)five, 4, 4, &exactmatch);
CHECK(slot != NULL);
memcpy(slot, five, 4);
again = vector_find_or_insert(&vector, (void *)five, 4, 4, &exactmatch);
CHECK(exactmatch != 0);
CHECK_PTR(again, vector.data);
CHECK_INT(vector.size, 1);
free(vector.data);
}
static void case_insert_compare_prefix(void) {
ot_vector vector = {NULL, 0, 0};
unsigned char first[6] = {1, 2, 3, 0xaa, 0xaa, 0xaa};
unsigned char second[6] = {1, 2, 3, 0xbb, 0xbb, 0xbb};
int exactmatch;
void *slot;
test_case("only the compare prefix decides identity");
slot = vector_find_or_insert(&vector, first, 6, 3, &exactmatch);
CHECK(slot != NULL);
memcpy(slot, first, 6);
slot = vector_find_or_insert(&vector, second, 6, 3, &exactmatch);
CHECK(exactmatch != 0);
CHECK_INT(vector.size, 1);
CHECK_MEM(slot, first, 6);
free(vector.data);
}
void test_vector(void) {
case_search_finds_member();
case_search_finds_first_and_last();
case_search_insert_position();
case_search_past_the_end();
case_search_empty();
case_insert_keeps_order();
case_insert_finds_existing();
case_insert_compare_prefix();
}
|
