1 /*
2 Copyright (c) DataStax, Inc.
3
4 Licensed under the Apache License, Version 2.0 (the "License");
5 you may not use this file except in compliance with the License.
6 You may obtain a copy of the License at
7
8 http://www.apache.org/licenses/LICENSE-2.0
9
10 Unless required by applicable law or agreed to in writing, software
11 distributed under the License is distributed on an "AS IS" BASIS,
12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 See the License for the specific language governing permissions and
14 limitations under the License.
15 */
16
17 #include <gtest/gtest.h>
18
19 #include "token_map_impl.hpp"
20
21 #include "uint128.hpp"
22
23 #include <ctype.h>
24 #include <stdio.h>
25
26 using namespace datastax;
27 using namespace datastax::internal;
28 using namespace datastax::internal::core;
29
30 namespace {
31
to_string(RandomPartitioner::Token token)32 String to_string(RandomPartitioner::Token token) {
33 return numeric::uint128_t(token.lo, token.hi).to_string();
34 }
35
36 } // namespace
37
TEST(TokenUnitTest,RandomAbs)38 TEST(TokenUnitTest, RandomAbs) {
39 // Two's complement: -170141183460469231731687303715884105728
40 {
41 uint8_t digest[16] = {};
42 digest[0] = 0x80;
43
44 RandomPartitioner::Token token;
45 token.hi = RandomPartitioner::encode(digest);
46 token.lo = RandomPartitioner::encode(digest + 8);
47 token = RandomPartitioner::abs(token);
48
49 EXPECT_EQ(to_string(token), "170141183460469231731687303715884105728");
50 }
51
52 // Two's complement: -170141183460469231731687303715884105727
53 {
54 uint8_t digest[16] = {};
55 digest[0] = 0x80;
56 digest[15] = 0x01;
57
58 RandomPartitioner::Token token;
59 token.hi = RandomPartitioner::encode(digest);
60 token.lo = RandomPartitioner::encode(digest + 8);
61 token = RandomPartitioner::abs(token);
62
63 EXPECT_EQ(to_string(token), "170141183460469231731687303715884105727");
64 }
65
66 // Two's complement: -18446744073709551616
67 {
68 uint8_t digest[16] = {};
69 digest[0] = 0xFF;
70 digest[1] = 0xFF;
71 digest[2] = 0xFF;
72 digest[3] = 0xFF;
73 digest[4] = 0xFF;
74 digest[5] = 0xFF;
75 digest[6] = 0xFF;
76 digest[7] = 0xFF;
77
78 RandomPartitioner::Token token;
79 token.hi = RandomPartitioner::encode(digest);
80 token.lo = RandomPartitioner::encode(digest + 8);
81 token = RandomPartitioner::abs(token);
82
83 EXPECT_EQ(to_string(token), "18446744073709551616");
84 }
85
86 // Two's complement: 0
87 {
88 uint8_t digest[16] = {};
89
90 RandomPartitioner::Token token;
91 token.hi = RandomPartitioner::encode(digest);
92 token.lo = RandomPartitioner::encode(digest + 8);
93 token = RandomPartitioner::abs(token);
94
95 EXPECT_EQ(numeric::uint128_t(token.lo, token.hi).to_string(), "0");
96 }
97
98 // Two's complement: 170141183460469231731687303715884105727
99 {
100 uint8_t digest[16] = {};
101 digest[0] = 0x7F;
102 digest[1] = 0xFF;
103 digest[2] = 0xFF;
104 digest[3] = 0xFF;
105 digest[4] = 0xFF;
106 digest[5] = 0xFF;
107 digest[6] = 0xFF;
108 digest[7] = 0xFF;
109 digest[8] = 0xFF;
110 digest[9] = 0xFF;
111 digest[10] = 0xFF;
112 digest[11] = 0xFF;
113 digest[12] = 0xFF;
114 digest[13] = 0xFF;
115 digest[14] = 0xFF;
116 digest[15] = 0xFF;
117
118 RandomPartitioner::Token token;
119 token.hi = RandomPartitioner::encode(digest);
120 token.lo = RandomPartitioner::encode(digest + 8);
121 token = RandomPartitioner::abs(token);
122
123 EXPECT_EQ(to_string(token), "170141183460469231731687303715884105727");
124 }
125 }
126
TEST(TokenUnitTest,RandomLessThan)127 TEST(TokenUnitTest, RandomLessThan) {
128 // 'hi' is the same and 'lo' is less than
129 {
130 RandomPartitioner::Token t1, t2;
131
132 // Two's complement: 0
133 {
134 uint8_t digest[16] = {};
135 t1.hi = RandomPartitioner::encode(digest);
136 t1.lo = RandomPartitioner::encode(digest + 8);
137 t1 = RandomPartitioner::abs(t1);
138 }
139
140 // Two's complement: 1
141 {
142 uint8_t digest[16] = {};
143 digest[15] = 0x01;
144 t2.hi = RandomPartitioner::encode(digest);
145 t2.lo = RandomPartitioner::encode(digest + 8);
146 t2 = RandomPartitioner::abs(t2);
147 }
148
149 EXPECT_TRUE(t1 < t2);
150 }
151
152 // 'lo' is the same and 'hi' is less than
153 {
154 RandomPartitioner::Token t1, t2;
155
156 // Two's complement: 18446744073709551616
157 {
158 uint8_t digest[16] = {};
159 digest[7] = 0x01;
160
161 t1.hi = RandomPartitioner::encode(digest);
162 t1.lo = RandomPartitioner::encode(digest + 8);
163 t1 = RandomPartitioner::abs(t1);
164 }
165
166 // Two's complement: 36893488147419103232
167 {
168 uint8_t digest[16] = {};
169 digest[7] = 0x02;
170 t2.hi = RandomPartitioner::encode(digest);
171 t2.lo = RandomPartitioner::encode(digest + 8);
172 t2 = RandomPartitioner::abs(t2);
173 }
174
175 EXPECT_TRUE(t1 < t2);
176 }
177
178 // Absolute value of negative values
179 {
180 RandomPartitioner::Token t1, t2;
181
182 // Two's complement: -170141183460469231731687303715884105727
183 {
184 uint8_t digest[16] = {};
185 digest[0] = 0x80;
186 digest[15] = 0x01;
187 t1.hi = RandomPartitioner::encode(digest);
188 t1.lo = RandomPartitioner::encode(digest + 8);
189 t1 = RandomPartitioner::abs(t1);
190 }
191
192 // Two's complement: -170141183460469231731687303715884105728
193 {
194 uint8_t digest[16] = {};
195 digest[0] = 0x80;
196 t2.hi = RandomPartitioner::encode(digest);
197 t2.lo = RandomPartitioner::encode(digest + 8);
198 t2 = RandomPartitioner::abs(t2);
199 }
200
201 EXPECT_TRUE(t1 < t2);
202 }
203
204 // Same value
205 {
206 RandomPartitioner::Token t1, t2;
207
208 // Two's complement: 18446744073709551616
209 {
210 uint8_t digest[16] = {};
211 digest[7] = 0x01;
212 t1.hi = RandomPartitioner::encode(digest);
213 t1.lo = RandomPartitioner::encode(digest + 8);
214 t1 = RandomPartitioner::abs(t1);
215 }
216
217 // Two's complement: 18446744073709551616
218 {
219 uint8_t digest[16] = {};
220 digest[7] = 0x01;
221 t2.hi = RandomPartitioner::encode(digest);
222 t2.lo = RandomPartitioner::encode(digest + 8);
223 t2 = RandomPartitioner::abs(t2);
224 }
225
226 EXPECT_FALSE(t1 < t2);
227 }
228
229 // Zero
230 {
231 RandomPartitioner::Token t1, t2;
232
233 {
234 uint8_t digest[16] = {};
235 t1.hi = RandomPartitioner::encode(digest);
236 t1.lo = RandomPartitioner::encode(digest + 8);
237 t1 = RandomPartitioner::abs(t1);
238 }
239
240 {
241 uint8_t digest[16] = {};
242 t2.hi = RandomPartitioner::encode(digest);
243 t2.lo = RandomPartitioner::encode(digest + 8);
244 t2 = RandomPartitioner::abs(t2);
245 }
246
247 EXPECT_FALSE(t1 < t2);
248 }
249 }
250
TEST(TokenUnitTest,RandomEqual)251 TEST(TokenUnitTest, RandomEqual) {
252 // Same value
253 {
254 RandomPartitioner::Token t1, t2;
255
256 // Two's complement: 18446744073709551616
257 {
258 uint8_t digest[16] = {};
259 digest[7] = 0x01;
260 t1.hi = RandomPartitioner::encode(digest);
261 t1.lo = RandomPartitioner::encode(digest + 8);
262 t1 = RandomPartitioner::abs(t1);
263 }
264
265 // Two's complement: 18446744073709551616
266 {
267 uint8_t digest[16] = {};
268 digest[7] = 0x01;
269 t2.hi = RandomPartitioner::encode(digest);
270 t2.lo = RandomPartitioner::encode(digest + 8);
271 t2 = RandomPartitioner::abs(t2);
272 }
273
274 EXPECT_TRUE(t1 == t2);
275 }
276
277 // Zero
278 {
279 RandomPartitioner::Token t1, t2;
280
281 {
282 uint8_t digest[16] = {};
283 t1.hi = RandomPartitioner::encode(digest);
284 t1.lo = RandomPartitioner::encode(digest + 8);
285 t1 = RandomPartitioner::abs(t1);
286 }
287
288 {
289 uint8_t digest[16] = {};
290 t2.hi = RandomPartitioner::encode(digest);
291 t2.lo = RandomPartitioner::encode(digest + 8);
292 t2 = RandomPartitioner::abs(t2);
293 }
294
295 EXPECT_TRUE(t1 == t2);
296 }
297
298 // 'hi' is the same and 'lo' is less than
299 {
300 RandomPartitioner::Token t1, t2;
301
302 // Two's complement: 0
303 {
304 uint8_t digest[16] = {};
305 t1.hi = RandomPartitioner::encode(digest);
306 t1.lo = RandomPartitioner::encode(digest + 8);
307 t1 = RandomPartitioner::abs(t1);
308 }
309
310 // Two's complement: 1
311 {
312 uint8_t digest[16] = {};
313 digest[15] = 0x01;
314 t2.hi = RandomPartitioner::encode(digest);
315 t2.lo = RandomPartitioner::encode(digest + 8);
316 t2 = RandomPartitioner::abs(t2);
317 }
318
319 EXPECT_FALSE(t1 == t2);
320 }
321
322 // 'lo' is the same and 'hi' is less than
323 {
324 RandomPartitioner::Token t1, t2;
325
326 // Two's complement: 18446744073709551616
327 {
328 uint8_t digest[16] = {};
329 digest[7] = 0x01;
330
331 t1.hi = RandomPartitioner::encode(digest);
332 t1.lo = RandomPartitioner::encode(digest + 8);
333 t1 = RandomPartitioner::abs(t1);
334 }
335
336 // Two's complement: 36893488147419103232
337 {
338 uint8_t digest[16] = {};
339 digest[7] = 0x02;
340 t2.hi = RandomPartitioner::encode(digest);
341 t2.lo = RandomPartitioner::encode(digest + 8);
342 t2 = RandomPartitioner::abs(t2);
343 }
344
345 EXPECT_FALSE(t1 == t2);
346 }
347 }
348
TEST(TokenUnitTest,RandomHash)349 TEST(TokenUnitTest, RandomHash) {
350 // Sampled using: SELECT token(key) FROM sometable;
351 EXPECT_EQ(to_string(RandomPartitioner::hash("a")), "16955237001963240173058271559858726497");
352 EXPECT_EQ(to_string(RandomPartitioner::hash("b")), "144992942750327304334463589818972416113");
353 EXPECT_EQ(to_string(RandomPartitioner::hash("c")), "99079589977253916124855502156832923443");
354 EXPECT_EQ(to_string(RandomPartitioner::hash("d")), "166860289390734216023086131251507064403");
355 EXPECT_EQ(to_string(RandomPartitioner::hash("abc")), "148866708576779697295343134153845407886");
356 EXPECT_EQ(to_string(RandomPartitioner::hash("xyz")), "61893731502141497228477852773302439842");
357 }
358
TEST(TokenUnitTest,RandomFromString)359 TEST(TokenUnitTest, RandomFromString) {
360 EXPECT_EQ(to_string(RandomPartitioner::from_string("0")), "0");
361 EXPECT_EQ(to_string(RandomPartitioner::from_string("1")), "1");
362 EXPECT_EQ(to_string(RandomPartitioner::from_string("170141183460469231731687303715884105727")),
363 "170141183460469231731687303715884105727");
364 EXPECT_EQ(to_string(RandomPartitioner::from_string("170141183460469231731687303715884105728")),
365 "170141183460469231731687303715884105728");
366 }
367