jcs.org
Serenity Operating System
1/*
2 * Copyright (c) 2021, Jan de Visser <jan@de-visser.net>
3 *
4 * SPDX-License-Identifier: BSD-2-Clause
5 */
6
7#include <LibSQL/HashIndex.h>
8#include <LibSQL/Heap.h>
9#include <LibSQL/Meta.h>
10#include <LibSQL/Tuple.h>
11#include <LibSQL/Value.h>
12#include <LibTest/TestCase.h>
13#include <unistd.h>
14
15constexpr static int keys[] = {
16 39,
17 87,
18 77,
19 42,
20 98,
21 40,
22 53,
23 8,
24 37,
25 12,
26 90,
27 72,
28 73,
29 11,
30 88,
31 22,
32 10,
33 82,
34 25,
35 61,
36 97,
37 18,
38 60,
39 68,
40 21,
41 3,
42 58,
43 29,
44 13,
45 17,
46 89,
47 81,
48 16,
49 64,
50 5,
51 41,
52 36,
53 91,
54 38,
55 24,
56 32,
57 50,
58 34,
59 94,
60 49,
61 47,
62 1,
63 6,
64 44,
65 76,
66};
67constexpr static u32 pointers[] = {
68 92,
69 4,
70 50,
71 47,
72 68,
73 73,
74 24,
75 28,
76 50,
77 93,
78 60,
79 36,
80 92,
81 72,
82 53,
83 26,
84 91,
85 84,
86 25,
87 43,
88 88,
89 12,
90 62,
91 35,
92 96,
93 27,
94 96,
95 27,
96 99,
97 30,
98 21,
99 89,
100 54,
101 60,
102 37,
103 68,
104 35,
105 55,
106 80,
107 2,
108 33,
109 26,
110 93,
111 70,
112 45,
113 44,
114 3,
115 66,
116 75,
117 4,
118};
119
120NonnullRefPtr<SQL::HashIndex> setup_hash_index(SQL::Serializer&);
121void insert_and_get_to_and_from_hash_index(int);
122void insert_into_and_scan_hash_index(int);
123
124NonnullRefPtr<SQL::HashIndex> setup_hash_index(SQL::Serializer& serializer)
125{
126 NonnullRefPtr<SQL::TupleDescriptor> tuple_descriptor = adopt_ref(*new SQL::TupleDescriptor);
127 tuple_descriptor->append({ "schema", "table", "key_value", SQL::SQLType::Integer, SQL::Order::Ascending });
128 tuple_descriptor->append({ "schema", "table", "text_value", SQL::SQLType::Text, SQL::Order::Ascending });
129
130 auto directory_pointer = serializer.heap().user_value(0);
131 if (!directory_pointer) {
132 directory_pointer = serializer.heap().new_record_pointer();
133 serializer.heap().set_user_value(0, directory_pointer);
134 }
135 auto hash_index = SQL::HashIndex::construct(serializer, tuple_descriptor, directory_pointer);
136 return hash_index;
137}
138
139void insert_and_get_to_and_from_hash_index(int num_keys)
140{
141 ScopeGuard guard([]() { unlink("/tmp/test.db"); });
142 {
143 auto heap = SQL::Heap::construct("/tmp/test.db");
144 EXPECT(!heap->open().is_error());
145 SQL::Serializer serializer(heap);
146 auto hash_index = setup_hash_index(serializer);
147
148 for (auto ix = 0; ix < num_keys; ix++) {
149 SQL::Key k(hash_index->descriptor());
150 k[0] = keys[ix];
151 k[1] = DeprecatedString::formatted("The key value is {} and the pointer is {}", keys[ix], pointers[ix]);
152 k.set_pointer(pointers[ix]);
153 hash_index->insert(k);
154 }
155#ifdef LIST_HASH_INDEX
156 hash_index->list_hash();
157#endif
158 }
159
160 {
161 auto heap = SQL::Heap::construct("/tmp/test.db");
162 EXPECT(!heap->open().is_error());
163 SQL::Serializer serializer(heap);
164 auto hash_index = setup_hash_index(serializer);
165
166 for (auto ix = 0; ix < num_keys; ix++) {
167 SQL::Key k(hash_index->descriptor());
168 k[0] = keys[ix];
169 k[1] = DeprecatedString::formatted("The key value is {} and the pointer is {}", keys[ix], pointers[ix]);
170 auto pointer_opt = hash_index->get(k);
171 VERIFY(pointer_opt.has_value());
172 EXPECT_EQ(pointer_opt.value(), pointers[ix]);
173 }
174 }
175}
176
177TEST_CASE(hash_index_one_key)
178{
179 insert_and_get_to_and_from_hash_index(1);
180}
181
182TEST_CASE(hash_index_four_keys)
183{
184 insert_and_get_to_and_from_hash_index(4);
185}
186
187TEST_CASE(hash_index_five_keys)
188{
189 insert_and_get_to_and_from_hash_index(5);
190}
191
192TEST_CASE(hash_index_10_keys)
193{
194 insert_and_get_to_and_from_hash_index(10);
195}
196
197TEST_CASE(hash_index_13_keys)
198{
199 insert_and_get_to_and_from_hash_index(13);
200}
201
202TEST_CASE(hash_index_20_keys)
203{
204 insert_and_get_to_and_from_hash_index(20);
205}
206
207TEST_CASE(hash_index_25_keys)
208{
209 insert_and_get_to_and_from_hash_index(25);
210}
211
212TEST_CASE(hash_index_30_keys)
213{
214 insert_and_get_to_and_from_hash_index(30);
215}
216
217TEST_CASE(hash_index_35_keys)
218{
219 insert_and_get_to_and_from_hash_index(35);
220}
221
222TEST_CASE(hash_index_40_keys)
223{
224 insert_and_get_to_and_from_hash_index(40);
225}
226
227TEST_CASE(hash_index_45_keys)
228{
229 insert_and_get_to_and_from_hash_index(45);
230}
231
232TEST_CASE(hash_index_50_keys)
233{
234 insert_and_get_to_and_from_hash_index(50);
235}
236
237void insert_into_and_scan_hash_index(int num_keys)
238{
239 ScopeGuard guard([]() { unlink("/tmp/test.db"); });
240 {
241 auto heap = SQL::Heap::construct("/tmp/test.db");
242 EXPECT(!heap->open().is_error());
243 SQL::Serializer serializer(heap);
244 auto hash_index = setup_hash_index(serializer);
245
246 for (auto ix = 0; ix < num_keys; ix++) {
247 SQL::Key k(hash_index->descriptor());
248 k[0] = keys[ix];
249 k[1] = DeprecatedString::formatted("The key value is {} and the pointer is {}", keys[ix], pointers[ix]);
250 k.set_pointer(pointers[ix]);
251 hash_index->insert(k);
252 }
253#ifdef LIST_HASH_INDEX
254 hash_index->list_hash();
255#endif
256 }
257
258 {
259 auto heap = SQL::Heap::construct("/tmp/test.db");
260 EXPECT(!heap->open().is_error());
261 SQL::Serializer serializer(heap);
262 auto hash_index = setup_hash_index(serializer);
263 Vector<bool> found;
264 for (auto ix = 0; ix < num_keys; ix++) {
265 found.append(false);
266 }
267
268 int count = 0;
269 for (auto iter = hash_index->begin(); !iter.is_end(); iter++, count++) {
270 auto key = (*iter);
271 auto key_value = key[0].to_int<i32>();
272 VERIFY(key_value.has_value());
273
274 for (auto ix = 0; ix < num_keys; ix++) {
275 if (keys[ix] == key_value) {
276 EXPECT_EQ(key.pointer(), pointers[ix]);
277 if (found[ix])
278 FAIL(DeprecatedString::formatted("Key {}, index {} already found previously", *key_value, ix));
279 found[ix] = true;
280 break;
281 }
282 }
283 }
284
285#ifdef LIST_HASH_INDEX
286 hash_index->list_hash();
287#endif
288 EXPECT_EQ(count, num_keys);
289 for (auto ix = 0; ix < num_keys; ix++) {
290 if (!found[ix])
291 FAIL(DeprecatedString::formatted("Key {}, index {} not found", keys[ix], ix));
292 }
293 }
294}
295
296TEST_CASE(hash_index_scan_one_key)
297{
298 insert_into_and_scan_hash_index(1);
299}
300
301TEST_CASE(hash_index_scan_four_keys)
302{
303 insert_into_and_scan_hash_index(4);
304}
305
306TEST_CASE(hash_index_scan_five_keys)
307{
308 insert_into_and_scan_hash_index(5);
309}
310
311TEST_CASE(hash_index_scan_10_keys)
312{
313 insert_into_and_scan_hash_index(10);
314}
315
316TEST_CASE(hash_index_scan_15_keys)
317{
318 insert_into_and_scan_hash_index(15);
319}
320
321TEST_CASE(hash_index_scan_20_keys)
322{
323 insert_into_and_scan_hash_index(20);
324}
325
326TEST_CASE(hash_index_scan_30_keys)
327{
328 insert_into_and_scan_hash_index(30);
329}
330
331TEST_CASE(hash_index_scan_40_keys)
332{
333 insert_into_and_scan_hash_index(40);
334}
335
336TEST_CASE(hash_index_scan_50_keys)
337{
338 insert_into_and_scan_hash_index(50);
339}