1#include "catch.hpp"
2#include "duckdb/execution/index/art/art_key.hpp"
3#include "duckdb/common/types/string_type.hpp"
4#include <iostream>
5#include <cstring>
6
7using namespace duckdb;
8using namespace std;
9
10static void TestKeyEqual(Key &left, Key &right) {
11 REQUIRE(left == right);
12 REQUIRE(left >= right);
13 REQUIRE(!(left > right));
14
15 REQUIRE(right == left);
16 REQUIRE(right >= left);
17 REQUIRE(!(right > left));
18}
19
20static void TestKeyBigger(Key &big, Key &small) {
21 REQUIRE(!(big == small));
22 if (!(big >= small)) {
23 REQUIRE(0);
24 }
25 REQUIRE(big > small);
26
27 REQUIRE(!(small == big));
28 REQUIRE(!(small >= big));
29 REQUIRE(!(small > big));
30}
31
32static void TestKeys(vector<unique_ptr<Key>> &keys) {
33 for (idx_t outer = 0; outer < keys.size(); outer++) {
34 for (idx_t inner = 0; inner < keys.size(); inner++) {
35 if (inner == outer) {
36 TestKeyEqual(*keys[inner], *keys[outer]);
37 } else if (inner > outer) {
38 TestKeyBigger(*keys[inner], *keys[outer]);
39 } else {
40 TestKeyBigger(*keys[outer], *keys[inner]);
41 }
42 }
43 }
44}
45
46static unique_ptr<Key> CreateCompoundKey(string str_val, int32_t int_val, bool is_little_endian) {
47 auto key_left = Key::CreateKey<string_t>(string_t(str_val.c_str(), str_val.size()), is_little_endian);
48 auto key_right = Key::CreateKey<int32_t>(int_val, is_little_endian);
49 unique_ptr<data_t[]> data = unique_ptr<data_t[]>(new data_t[key_left->len + key_right->len]);
50 memcpy(data.get(), key_left->data.get(), key_left->len);
51 memcpy(data.get() + key_left->len, key_right->data.get(), key_right->len);
52 return make_unique<Key>(move(data), key_left->len + key_right->len);
53}
54
55TEST_CASE("Test correct functioning of art keys", "[art]") {
56 bool is_little_endian;
57 int n = 1;
58 if (*(char *)&n == 1) {
59 is_little_endian = true;
60 } else {
61 is_little_endian = false;
62 }
63 // Test tiny int
64 vector<unique_ptr<Key>> keys;
65 keys.push_back(Key::CreateKey<int8_t>(-127, is_little_endian));
66 keys.push_back(Key::CreateKey<int8_t>(-55, is_little_endian));
67 keys.push_back(Key::CreateKey<int8_t>(-1, is_little_endian));
68 keys.push_back(Key::CreateKey<int8_t>(0, is_little_endian));
69 keys.push_back(Key::CreateKey<int8_t>(1, is_little_endian));
70 keys.push_back(Key::CreateKey<int8_t>(55, is_little_endian));
71 keys.push_back(Key::CreateKey<int8_t>(127, is_little_endian));
72 TestKeys(keys);
73
74 keys.clear();
75
76 // Test small int
77 keys.push_back(Key::CreateKey<int16_t>(-32767, is_little_endian));
78 keys.push_back(Key::CreateKey<int16_t>(-127, is_little_endian));
79 keys.push_back(Key::CreateKey<int16_t>(-55, is_little_endian));
80 keys.push_back(Key::CreateKey<int16_t>(-1, is_little_endian));
81 keys.push_back(Key::CreateKey<int16_t>(0, is_little_endian));
82 keys.push_back(Key::CreateKey<int16_t>(1, is_little_endian));
83 keys.push_back(Key::CreateKey<int16_t>(55, is_little_endian));
84 keys.push_back(Key::CreateKey<int16_t>(127, is_little_endian));
85 keys.push_back(Key::CreateKey<int16_t>(32767, is_little_endian));
86 TestKeys(keys);
87
88 keys.clear();
89
90 // Test int
91 keys.push_back(Key::CreateKey<int32_t>(-2147483647, is_little_endian));
92 keys.push_back(Key::CreateKey<int32_t>(-8388608, is_little_endian));
93 keys.push_back(Key::CreateKey<int32_t>(-32767, is_little_endian));
94 keys.push_back(Key::CreateKey<int32_t>(-1, is_little_endian));
95 keys.push_back(Key::CreateKey<int32_t>(0, is_little_endian));
96 keys.push_back(Key::CreateKey<int32_t>(1, is_little_endian));
97 keys.push_back(Key::CreateKey<int32_t>(32767, is_little_endian));
98 keys.push_back(Key::CreateKey<int32_t>(8388608, is_little_endian));
99 keys.push_back(Key::CreateKey<int32_t>(2147483647, is_little_endian));
100 TestKeys(keys);
101
102 keys.clear();
103
104 // Test big int
105 keys.push_back(Key::CreateKey<int64_t>(-9223372036854775807, is_little_endian));
106 keys.push_back(Key::CreateKey<int64_t>(-72057594037927936, is_little_endian));
107 keys.push_back(Key::CreateKey<int64_t>(-281474976710656, is_little_endian));
108 keys.push_back(Key::CreateKey<int64_t>(-1099511627776, is_little_endian));
109 keys.push_back(Key::CreateKey<int64_t>(-2147483647, is_little_endian));
110 keys.push_back(Key::CreateKey<int64_t>(-8388608, is_little_endian));
111 keys.push_back(Key::CreateKey<int64_t>(-32767, is_little_endian));
112 keys.push_back(Key::CreateKey<int64_t>(-1, is_little_endian));
113 keys.push_back(Key::CreateKey<int64_t>(0, is_little_endian));
114 keys.push_back(Key::CreateKey<int64_t>(1, is_little_endian));
115 keys.push_back(Key::CreateKey<int64_t>(32767, is_little_endian));
116 keys.push_back(Key::CreateKey<int64_t>(8388608, is_little_endian));
117 keys.push_back(Key::CreateKey<int64_t>(2147483647, is_little_endian));
118 keys.push_back(Key::CreateKey<int64_t>(1099511627776, is_little_endian));
119 keys.push_back(Key::CreateKey<int64_t>(281474976710656, is_little_endian));
120 keys.push_back(Key::CreateKey<int64_t>(72057594037927936, is_little_endian));
121 keys.push_back(Key::CreateKey<int64_t>(9223372036854775807, is_little_endian));
122 TestKeys(keys);
123
124 keys.clear();
125
126 // Test strings
127 keys.push_back(Key::CreateKey<const char *>("abc", is_little_endian));
128 keys.push_back(Key::CreateKey<const char *>("babababa", is_little_endian));
129 keys.push_back(Key::CreateKey<const char *>("hello", is_little_endian));
130 keys.push_back(Key::CreateKey<const char *>("hellow", is_little_endian));
131 keys.push_back(Key::CreateKey<const char *>("torororororo", is_little_endian));
132 keys.push_back(Key::CreateKey<const char *>("torororororp", is_little_endian));
133 keys.push_back(Key::CreateKey<const char *>("z", is_little_endian));
134
135 TestKeys(keys);
136
137 keys.clear();
138
139 // test compound keys
140 keys.push_back(CreateCompoundKey("abc", -100, is_little_endian));
141 keys.push_back(CreateCompoundKey("abc", 1000, is_little_endian));
142 keys.push_back(CreateCompoundKey("abcd", -100000, is_little_endian));
143 keys.push_back(CreateCompoundKey("hello", -100000, is_little_endian));
144 keys.push_back(CreateCompoundKey("hello", -1, is_little_endian));
145 keys.push_back(CreateCompoundKey("hello", 0, is_little_endian));
146 keys.push_back(CreateCompoundKey("hello", 1, is_little_endian));
147 keys.push_back(CreateCompoundKey("hellow", -10000, is_little_endian));
148 keys.push_back(CreateCompoundKey("z", 30, is_little_endian));
149
150 TestKeys(keys);
151
152 keys.clear();
153
154 keys.push_back(Key::CreateKey<double>(0, is_little_endian));
155 keys.push_back(Key::CreateKey<double>(0.1, is_little_endian));
156 keys.push_back(Key::CreateKey<double>(488566, is_little_endian));
157 keys.push_back(Key::CreateKey<double>(1163404482, is_little_endian));
158
159 TestKeys(keys);
160
161 keys.clear();
162}
163
164TEST_CASE("Test correct functioning of art EncodeFloat/EncodeDouble", "[art-enc]") {
165 {
166 // EncodeFloat
167 // positive values
168 vector<float> values;
169 float current_value = 0.00001f;
170 while (isfinite(current_value)) {
171 values.push_back(current_value);
172 current_value *= 2;
173 }
174 // negative values
175 current_value = -0.00001f;
176 while (isfinite(current_value)) {
177 values.push_back(current_value);
178 current_value *= 2;
179 }
180 std::sort(values.begin(), values.end());
181 uint32_t current_encoded = Key::EncodeFloat(values[0]);
182 for (idx_t i = 1; i < values.size(); i++) {
183 uint32_t next_encoded = Key::EncodeFloat(values[i]);
184 if (!(next_encoded > current_encoded)) {
185 printf("Failure in Key::EncodeFloat!\n");
186 printf(
187 "Generated value for key %f (=> %u) is bigger or equal to the generated value for key %f (=> %u)\n",
188 values[i - 1], current_encoded, values[i], next_encoded);
189 }
190 REQUIRE(next_encoded > current_encoded);
191 current_encoded = next_encoded;
192 }
193 }
194 {
195 // EncodeDouble
196 // positive values
197 vector<double> values;
198 double current_value = 0.0000001;
199 while (isfinite(current_value)) {
200 values.push_back(current_value);
201 current_value *= 2;
202 }
203 // negative values
204 current_value = -0.0000001;
205 while (isfinite(current_value)) {
206 values.push_back(current_value);
207 current_value *= 2;
208 }
209 std::sort(values.begin(), values.end());
210 uint64_t current_encoded = Key::EncodeDouble(values[0]);
211 for (idx_t i = 1; i < values.size(); i++) {
212 uint64_t next_encoded = Key::EncodeDouble(values[i]);
213 if (!(next_encoded > current_encoded)) {
214 cout << "Failure in Key::EncodeDouble!" << std::endl;
215 cout << "Generated value for key " << values[i - 1] << " (=> %" << current_encoded
216 << ") is bigger or equal to the generated value for key " << values[i] << "(=> %" << next_encoded
217 << ")" << std::endl;
218 }
219 REQUIRE(next_encoded > current_encoded);
220 current_encoded = next_encoded;
221 }
222 }
223}
224