]>
Commit | Line | Data |
---|---|---|
7c673cae | 1 | // Copyright (c) 2011-present, Facebook, Inc. All rights reserved. |
11fdf7f2 TL |
2 | // This source code is licensed under both the GPLv2 (found in the |
3 | // COPYING file in the root directory) and Apache 2.0 License | |
4 | // (found in the LICENSE.Apache file in the root directory). | |
5 | #include <array> | |
7c673cae FG |
6 | #include <map> |
7 | #include <string> | |
8 | ||
9 | #include "memtable/stl_wrappers.h" | |
10 | #include "rocksdb/db.h" | |
11 | #include "rocksdb/env.h" | |
f67539c2 TL |
12 | #include "test_util/testharness.h" |
13 | #include "test_util/testutil.h" | |
7c673cae FG |
14 | #include "util/hash.h" |
15 | #include "util/kv_map.h" | |
20effc67 | 16 | #include "util/random.h" |
7c673cae | 17 | #include "util/string_util.h" |
7c673cae FG |
18 | #include "utilities/merge_operators.h" |
19 | ||
f67539c2 | 20 | namespace ROCKSDB_NAMESPACE { |
7c673cae FG |
21 | namespace { |
22 | ||
f67539c2 | 23 | static const Comparator* kTestComparator = nullptr; |
7c673cae FG |
24 | |
25 | class KVIter : public Iterator { | |
26 | public: | |
27 | explicit KVIter(const stl_wrappers::KVMap* map) | |
28 | : map_(map), iter_(map_->end()) {} | |
494da23a TL |
29 | bool Valid() const override { return iter_ != map_->end(); } |
30 | void SeekToFirst() override { iter_ = map_->begin(); } | |
31 | void SeekToLast() override { | |
7c673cae FG |
32 | if (map_->empty()) { |
33 | iter_ = map_->end(); | |
34 | } else { | |
35 | iter_ = map_->find(map_->rbegin()->first); | |
36 | } | |
37 | } | |
494da23a | 38 | void Seek(const Slice& k) override { |
7c673cae FG |
39 | iter_ = map_->lower_bound(k.ToString()); |
40 | } | |
494da23a | 41 | void SeekForPrev(const Slice& k) override { |
7c673cae FG |
42 | iter_ = map_->upper_bound(k.ToString()); |
43 | Prev(); | |
44 | } | |
494da23a TL |
45 | void Next() override { ++iter_; } |
46 | void Prev() override { | |
7c673cae FG |
47 | if (iter_ == map_->begin()) { |
48 | iter_ = map_->end(); | |
49 | return; | |
50 | } | |
51 | --iter_; | |
52 | } | |
53 | ||
494da23a TL |
54 | Slice key() const override { return iter_->first; } |
55 | Slice value() const override { return iter_->second; } | |
56 | Status status() const override { return Status::OK(); } | |
7c673cae FG |
57 | |
58 | private: | |
59 | const stl_wrappers::KVMap* const map_; | |
60 | stl_wrappers::KVMap::const_iterator iter_; | |
61 | }; | |
62 | ||
63 | void AssertItersEqual(Iterator* iter1, Iterator* iter2) { | |
64 | ASSERT_EQ(iter1->Valid(), iter2->Valid()); | |
65 | if (iter1->Valid()) { | |
66 | ASSERT_EQ(iter1->key().ToString(), iter2->key().ToString()); | |
67 | ASSERT_EQ(iter1->value().ToString(), iter2->value().ToString()); | |
68 | } | |
69 | } | |
70 | ||
71 | // Measuring operations on DB (expect to be empty). | |
72 | // source_strings are candidate keys | |
73 | void DoRandomIteraratorTest(DB* db, std::vector<std::string> source_strings, | |
74 | Random* rnd, int num_writes, int num_iter_ops, | |
75 | int num_trigger_flush) { | |
f67539c2 | 76 | stl_wrappers::KVMap map((stl_wrappers::LessOfComparator(kTestComparator))); |
7c673cae FG |
77 | |
78 | for (int i = 0; i < num_writes; i++) { | |
79 | if (num_trigger_flush > 0 && i != 0 && i % num_trigger_flush == 0) { | |
80 | db->Flush(FlushOptions()); | |
81 | } | |
82 | ||
83 | int type = rnd->Uniform(2); | |
84 | int index = rnd->Uniform(static_cast<int>(source_strings.size())); | |
85 | auto& key = source_strings[index]; | |
86 | switch (type) { | |
87 | case 0: | |
88 | // put | |
89 | map[key] = key; | |
90 | ASSERT_OK(db->Put(WriteOptions(), key, key)); | |
91 | break; | |
92 | case 1: | |
93 | // delete | |
94 | if (map.find(key) != map.end()) { | |
95 | map.erase(key); | |
96 | } | |
97 | ASSERT_OK(db->Delete(WriteOptions(), key)); | |
98 | break; | |
99 | default: | |
100 | assert(false); | |
101 | } | |
102 | } | |
103 | ||
104 | std::unique_ptr<Iterator> iter(db->NewIterator(ReadOptions())); | |
105 | std::unique_ptr<Iterator> result_iter(new KVIter(&map)); | |
106 | ||
107 | bool is_valid = false; | |
108 | for (int i = 0; i < num_iter_ops; i++) { | |
109 | // Random walk and make sure iter and result_iter returns the | |
110 | // same key and value | |
111 | int type = rnd->Uniform(6); | |
112 | ASSERT_OK(iter->status()); | |
113 | switch (type) { | |
114 | case 0: | |
115 | // Seek to First | |
116 | iter->SeekToFirst(); | |
117 | result_iter->SeekToFirst(); | |
118 | break; | |
119 | case 1: | |
120 | // Seek to last | |
121 | iter->SeekToLast(); | |
122 | result_iter->SeekToLast(); | |
123 | break; | |
124 | case 2: { | |
125 | // Seek to random key | |
126 | auto key_idx = rnd->Uniform(static_cast<int>(source_strings.size())); | |
127 | auto key = source_strings[key_idx]; | |
128 | iter->Seek(key); | |
129 | result_iter->Seek(key); | |
130 | break; | |
131 | } | |
132 | case 3: | |
133 | // Next | |
134 | if (is_valid) { | |
135 | iter->Next(); | |
136 | result_iter->Next(); | |
137 | } else { | |
138 | continue; | |
139 | } | |
140 | break; | |
141 | case 4: | |
142 | // Prev | |
143 | if (is_valid) { | |
144 | iter->Prev(); | |
145 | result_iter->Prev(); | |
146 | } else { | |
147 | continue; | |
148 | } | |
149 | break; | |
150 | default: { | |
151 | assert(type == 5); | |
152 | auto key_idx = rnd->Uniform(static_cast<int>(source_strings.size())); | |
153 | auto key = source_strings[key_idx]; | |
154 | std::string result; | |
155 | auto status = db->Get(ReadOptions(), key, &result); | |
156 | if (map.find(key) == map.end()) { | |
157 | ASSERT_TRUE(status.IsNotFound()); | |
158 | } else { | |
159 | ASSERT_EQ(map[key], result); | |
160 | } | |
161 | break; | |
162 | } | |
163 | } | |
164 | AssertItersEqual(iter.get(), result_iter.get()); | |
165 | is_valid = iter->Valid(); | |
166 | } | |
167 | } | |
168 | ||
169 | class DoubleComparator : public Comparator { | |
170 | public: | |
171 | DoubleComparator() {} | |
172 | ||
494da23a | 173 | const char* Name() const override { return "DoubleComparator"; } |
7c673cae | 174 | |
494da23a | 175 | int Compare(const Slice& a, const Slice& b) const override { |
7c673cae FG |
176 | #ifndef CYGWIN |
177 | double da = std::stod(a.ToString()); | |
178 | double db = std::stod(b.ToString()); | |
179 | #else | |
180 | double da = std::strtod(a.ToString().c_str(), 0 /* endptr */); | |
181 | double db = std::strtod(a.ToString().c_str(), 0 /* endptr */); | |
182 | #endif | |
183 | if (da == db) { | |
184 | return a.compare(b); | |
185 | } else if (da > db) { | |
186 | return 1; | |
187 | } else { | |
188 | return -1; | |
189 | } | |
190 | } | |
494da23a TL |
191 | void FindShortestSeparator(std::string* /*start*/, |
192 | const Slice& /*limit*/) const override {} | |
7c673cae | 193 | |
494da23a | 194 | void FindShortSuccessor(std::string* /*key*/) const override {} |
7c673cae FG |
195 | }; |
196 | ||
197 | class HashComparator : public Comparator { | |
198 | public: | |
199 | HashComparator() {} | |
200 | ||
494da23a | 201 | const char* Name() const override { return "HashComparator"; } |
7c673cae | 202 | |
494da23a | 203 | int Compare(const Slice& a, const Slice& b) const override { |
7c673cae FG |
204 | uint32_t ha = Hash(a.data(), a.size(), 66); |
205 | uint32_t hb = Hash(b.data(), b.size(), 66); | |
206 | if (ha == hb) { | |
207 | return a.compare(b); | |
208 | } else if (ha > hb) { | |
209 | return 1; | |
210 | } else { | |
211 | return -1; | |
212 | } | |
213 | } | |
494da23a TL |
214 | void FindShortestSeparator(std::string* /*start*/, |
215 | const Slice& /*limit*/) const override {} | |
7c673cae | 216 | |
494da23a | 217 | void FindShortSuccessor(std::string* /*key*/) const override {} |
7c673cae FG |
218 | }; |
219 | ||
220 | class TwoStrComparator : public Comparator { | |
221 | public: | |
222 | TwoStrComparator() {} | |
223 | ||
494da23a | 224 | const char* Name() const override { return "TwoStrComparator"; } |
7c673cae | 225 | |
494da23a | 226 | int Compare(const Slice& a, const Slice& b) const override { |
7c673cae FG |
227 | assert(a.size() >= 2); |
228 | assert(b.size() >= 2); | |
229 | size_t size_a1 = static_cast<size_t>(a[0]); | |
230 | size_t size_b1 = static_cast<size_t>(b[0]); | |
231 | size_t size_a2 = static_cast<size_t>(a[1]); | |
232 | size_t size_b2 = static_cast<size_t>(b[1]); | |
233 | assert(size_a1 + size_a2 + 2 == a.size()); | |
234 | assert(size_b1 + size_b2 + 2 == b.size()); | |
235 | ||
236 | Slice a1 = Slice(a.data() + 2, size_a1); | |
237 | Slice b1 = Slice(b.data() + 2, size_b1); | |
238 | Slice a2 = Slice(a.data() + 2 + size_a1, size_a2); | |
239 | Slice b2 = Slice(b.data() + 2 + size_b1, size_b2); | |
240 | ||
241 | if (a1 != b1) { | |
242 | return a1.compare(b1); | |
243 | } | |
244 | return a2.compare(b2); | |
245 | } | |
494da23a TL |
246 | void FindShortestSeparator(std::string* /*start*/, |
247 | const Slice& /*limit*/) const override {} | |
7c673cae | 248 | |
494da23a | 249 | void FindShortSuccessor(std::string* /*key*/) const override {} |
7c673cae | 250 | }; |
1e59de90 | 251 | } // anonymous namespace |
7c673cae | 252 | |
11fdf7f2 TL |
253 | class ComparatorDBTest |
254 | : public testing::Test, | |
255 | virtual public ::testing::WithParamInterface<uint32_t> { | |
7c673cae FG |
256 | private: |
257 | std::string dbname_; | |
258 | Env* env_; | |
259 | DB* db_; | |
260 | Options last_options_; | |
261 | std::unique_ptr<const Comparator> comparator_guard; | |
262 | ||
263 | public: | |
264 | ComparatorDBTest() : env_(Env::Default()), db_(nullptr) { | |
f67539c2 | 265 | kTestComparator = BytewiseComparator(); |
11fdf7f2 TL |
266 | dbname_ = test::PerThreadDBPath("comparator_db_test"); |
267 | BlockBasedTableOptions toptions; | |
268 | toptions.format_version = GetParam(); | |
269 | last_options_.table_factory.reset( | |
f67539c2 | 270 | ROCKSDB_NAMESPACE::NewBlockBasedTableFactory(toptions)); |
7c673cae FG |
271 | EXPECT_OK(DestroyDB(dbname_, last_options_)); |
272 | } | |
273 | ||
494da23a | 274 | ~ComparatorDBTest() override { |
7c673cae FG |
275 | delete db_; |
276 | EXPECT_OK(DestroyDB(dbname_, last_options_)); | |
f67539c2 | 277 | kTestComparator = BytewiseComparator(); |
7c673cae FG |
278 | } |
279 | ||
280 | DB* GetDB() { return db_; } | |
281 | ||
11fdf7f2 TL |
282 | void SetOwnedComparator(const Comparator* cmp, bool owner = true) { |
283 | if (owner) { | |
284 | comparator_guard.reset(cmp); | |
285 | } else { | |
286 | comparator_guard.reset(); | |
287 | } | |
f67539c2 | 288 | kTestComparator = cmp; |
7c673cae FG |
289 | last_options_.comparator = cmp; |
290 | } | |
291 | ||
292 | // Return the current option configuration. | |
293 | Options* GetOptions() { return &last_options_; } | |
294 | ||
295 | void DestroyAndReopen() { | |
296 | // Destroy using last options | |
297 | Destroy(); | |
298 | ASSERT_OK(TryReopen()); | |
299 | } | |
300 | ||
301 | void Destroy() { | |
302 | delete db_; | |
303 | db_ = nullptr; | |
304 | ASSERT_OK(DestroyDB(dbname_, last_options_)); | |
305 | } | |
306 | ||
307 | Status TryReopen() { | |
308 | delete db_; | |
309 | db_ = nullptr; | |
310 | last_options_.create_if_missing = true; | |
311 | ||
312 | return DB::Open(last_options_, dbname_, &db_); | |
313 | } | |
314 | }; | |
315 | ||
11fdf7f2 TL |
316 | INSTANTIATE_TEST_CASE_P(FormatDef, ComparatorDBTest, |
317 | testing::Values(test::kDefaultFormatVersion)); | |
318 | INSTANTIATE_TEST_CASE_P(FormatLatest, ComparatorDBTest, | |
1e59de90 | 319 | testing::Values(kLatestFormatVersion)); |
11fdf7f2 TL |
320 | |
321 | TEST_P(ComparatorDBTest, Bytewise) { | |
7c673cae FG |
322 | for (int rand_seed = 301; rand_seed < 306; rand_seed++) { |
323 | DestroyAndReopen(); | |
324 | Random rnd(rand_seed); | |
325 | DoRandomIteraratorTest(GetDB(), | |
326 | {"a", "b", "c", "d", "e", "f", "g", "h", "i"}, &rnd, | |
327 | 8, 100, 3); | |
328 | } | |
329 | } | |
330 | ||
11fdf7f2 | 331 | TEST_P(ComparatorDBTest, SimpleSuffixReverseComparator) { |
7c673cae FG |
332 | SetOwnedComparator(new test::SimpleSuffixReverseComparator()); |
333 | ||
334 | for (int rnd_seed = 301; rnd_seed < 316; rnd_seed++) { | |
335 | Options* opt = GetOptions(); | |
f67539c2 | 336 | opt->comparator = kTestComparator; |
7c673cae FG |
337 | DestroyAndReopen(); |
338 | Random rnd(rnd_seed); | |
339 | ||
340 | std::vector<std::string> source_strings; | |
341 | std::vector<std::string> source_prefixes; | |
342 | // Randomly generate 5 prefixes | |
343 | for (int i = 0; i < 5; i++) { | |
20effc67 | 344 | source_prefixes.push_back(rnd.HumanReadableString(8)); |
7c673cae FG |
345 | } |
346 | for (int j = 0; j < 20; j++) { | |
347 | int prefix_index = rnd.Uniform(static_cast<int>(source_prefixes.size())); | |
348 | std::string key = source_prefixes[prefix_index] + | |
20effc67 | 349 | rnd.HumanReadableString(rnd.Uniform(8)); |
7c673cae FG |
350 | source_strings.push_back(key); |
351 | } | |
352 | ||
353 | DoRandomIteraratorTest(GetDB(), source_strings, &rnd, 30, 600, 66); | |
354 | } | |
355 | } | |
356 | ||
11fdf7f2 TL |
357 | TEST_P(ComparatorDBTest, Uint64Comparator) { |
358 | SetOwnedComparator(test::Uint64Comparator(), false /* owner */); | |
7c673cae FG |
359 | |
360 | for (int rnd_seed = 301; rnd_seed < 316; rnd_seed++) { | |
361 | Options* opt = GetOptions(); | |
f67539c2 | 362 | opt->comparator = kTestComparator; |
7c673cae FG |
363 | DestroyAndReopen(); |
364 | Random rnd(rnd_seed); | |
365 | Random64 rnd64(rnd_seed); | |
366 | ||
367 | std::vector<std::string> source_strings; | |
368 | // Randomly generate source keys | |
369 | for (int i = 0; i < 100; i++) { | |
370 | uint64_t r = rnd64.Next(); | |
371 | std::string str; | |
372 | str.resize(8); | |
373 | memcpy(&str[0], static_cast<void*>(&r), 8); | |
374 | source_strings.push_back(str); | |
375 | } | |
376 | ||
377 | DoRandomIteraratorTest(GetDB(), source_strings, &rnd, 200, 1000, 66); | |
378 | } | |
379 | } | |
380 | ||
11fdf7f2 | 381 | TEST_P(ComparatorDBTest, DoubleComparator) { |
7c673cae FG |
382 | SetOwnedComparator(new DoubleComparator()); |
383 | ||
384 | for (int rnd_seed = 301; rnd_seed < 316; rnd_seed++) { | |
385 | Options* opt = GetOptions(); | |
f67539c2 | 386 | opt->comparator = kTestComparator; |
7c673cae FG |
387 | DestroyAndReopen(); |
388 | Random rnd(rnd_seed); | |
389 | ||
390 | std::vector<std::string> source_strings; | |
391 | // Randomly generate source keys | |
392 | for (int i = 0; i < 100; i++) { | |
393 | uint32_t r = rnd.Next(); | |
394 | uint32_t divide_order = rnd.Uniform(8); | |
395 | double to_divide = 1.0; | |
396 | for (uint32_t j = 0; j < divide_order; j++) { | |
397 | to_divide *= 10.0; | |
398 | } | |
1e59de90 | 399 | source_strings.push_back(std::to_string(r / to_divide)); |
7c673cae FG |
400 | } |
401 | ||
402 | DoRandomIteraratorTest(GetDB(), source_strings, &rnd, 200, 1000, 66); | |
403 | } | |
404 | } | |
405 | ||
11fdf7f2 | 406 | TEST_P(ComparatorDBTest, HashComparator) { |
7c673cae FG |
407 | SetOwnedComparator(new HashComparator()); |
408 | ||
409 | for (int rnd_seed = 301; rnd_seed < 316; rnd_seed++) { | |
410 | Options* opt = GetOptions(); | |
f67539c2 | 411 | opt->comparator = kTestComparator; |
7c673cae FG |
412 | DestroyAndReopen(); |
413 | Random rnd(rnd_seed); | |
414 | ||
415 | std::vector<std::string> source_strings; | |
416 | // Randomly generate source keys | |
417 | for (int i = 0; i < 100; i++) { | |
418 | source_strings.push_back(test::RandomKey(&rnd, 8)); | |
419 | } | |
420 | ||
421 | DoRandomIteraratorTest(GetDB(), source_strings, &rnd, 200, 1000, 66); | |
422 | } | |
423 | } | |
424 | ||
11fdf7f2 | 425 | TEST_P(ComparatorDBTest, TwoStrComparator) { |
7c673cae FG |
426 | SetOwnedComparator(new TwoStrComparator()); |
427 | ||
428 | for (int rnd_seed = 301; rnd_seed < 316; rnd_seed++) { | |
429 | Options* opt = GetOptions(); | |
f67539c2 | 430 | opt->comparator = kTestComparator; |
7c673cae FG |
431 | DestroyAndReopen(); |
432 | Random rnd(rnd_seed); | |
433 | ||
434 | std::vector<std::string> source_strings; | |
435 | // Randomly generate source keys | |
436 | for (int i = 0; i < 100; i++) { | |
437 | std::string str; | |
438 | uint32_t size1 = rnd.Uniform(8); | |
439 | uint32_t size2 = rnd.Uniform(8); | |
440 | str.append(1, static_cast<char>(size1)); | |
441 | str.append(1, static_cast<char>(size2)); | |
442 | str.append(test::RandomKey(&rnd, size1)); | |
443 | str.append(test::RandomKey(&rnd, size2)); | |
444 | source_strings.push_back(str); | |
445 | } | |
446 | ||
447 | DoRandomIteraratorTest(GetDB(), source_strings, &rnd, 200, 1000, 66); | |
448 | } | |
449 | } | |
450 | ||
1e59de90 TL |
451 | namespace { |
452 | void VerifyNotSuccessor(const Slice& s, const Slice& t) { | |
453 | auto bc = BytewiseComparator(); | |
454 | auto rbc = ReverseBytewiseComparator(); | |
455 | ASSERT_FALSE(bc->IsSameLengthImmediateSuccessor(s, t)); | |
456 | ASSERT_FALSE(rbc->IsSameLengthImmediateSuccessor(s, t)); | |
457 | ASSERT_FALSE(bc->IsSameLengthImmediateSuccessor(t, s)); | |
458 | ASSERT_FALSE(rbc->IsSameLengthImmediateSuccessor(t, s)); | |
459 | } | |
460 | ||
461 | void VerifySuccessor(const Slice& s, const Slice& t) { | |
462 | auto bc = BytewiseComparator(); | |
463 | auto rbc = ReverseBytewiseComparator(); | |
464 | ASSERT_TRUE(bc->IsSameLengthImmediateSuccessor(s, t)); | |
465 | ASSERT_FALSE(rbc->IsSameLengthImmediateSuccessor(s, t)); | |
466 | ASSERT_FALSE(bc->IsSameLengthImmediateSuccessor(t, s)); | |
467 | // Should be true but that increases exposure to a design bug in | |
468 | // auto_prefix_mode, so currently set to FALSE | |
469 | ASSERT_FALSE(rbc->IsSameLengthImmediateSuccessor(t, s)); | |
470 | } | |
471 | ||
472 | } // anonymous namespace | |
473 | ||
11fdf7f2 TL |
474 | TEST_P(ComparatorDBTest, IsSameLengthImmediateSuccessor) { |
475 | { | |
476 | // different length | |
477 | Slice s("abcxy"); | |
478 | Slice t("abcxyz"); | |
1e59de90 | 479 | VerifyNotSuccessor(s, t); |
11fdf7f2 TL |
480 | } |
481 | { | |
482 | Slice s("abcxyz"); | |
483 | Slice t("abcxy"); | |
1e59de90 | 484 | VerifyNotSuccessor(s, t); |
11fdf7f2 TL |
485 | } |
486 | { | |
487 | // not last byte different | |
488 | Slice s("abc1xyz"); | |
489 | Slice t("abc2xyz"); | |
1e59de90 | 490 | VerifyNotSuccessor(s, t); |
11fdf7f2 TL |
491 | } |
492 | { | |
493 | // same string | |
494 | Slice s("abcxyz"); | |
495 | Slice t("abcxyz"); | |
1e59de90 | 496 | VerifyNotSuccessor(s, t); |
11fdf7f2 TL |
497 | } |
498 | { | |
499 | Slice s("abcxy"); | |
500 | Slice t("abcxz"); | |
1e59de90 | 501 | VerifySuccessor(s, t); |
11fdf7f2 TL |
502 | } |
503 | { | |
504 | const char s_array[] = "\x50\x8a\xac"; | |
505 | const char t_array[] = "\x50\x8a\xad"; | |
506 | Slice s(s_array); | |
507 | Slice t(t_array); | |
1e59de90 | 508 | VerifySuccessor(s, t); |
11fdf7f2 TL |
509 | } |
510 | { | |
511 | const char s_array[] = "\x50\x8a\xff"; | |
512 | const char t_array[] = "\x50\x8b\x00"; | |
513 | Slice s(s_array, 3); | |
514 | Slice t(t_array, 3); | |
1e59de90 | 515 | VerifySuccessor(s, t); |
11fdf7f2 TL |
516 | } |
517 | { | |
518 | const char s_array[] = "\x50\x8a\xff\xff"; | |
519 | const char t_array[] = "\x50\x8b\x00\x00"; | |
520 | Slice s(s_array, 4); | |
521 | Slice t(t_array, 4); | |
1e59de90 | 522 | VerifySuccessor(s, t); |
11fdf7f2 TL |
523 | } |
524 | { | |
525 | const char s_array[] = "\x50\x8a\xff\xff"; | |
526 | const char t_array[] = "\x50\x8b\x00\x01"; | |
527 | Slice s(s_array, 4); | |
528 | Slice t(t_array, 4); | |
1e59de90 | 529 | VerifyNotSuccessor(s, t); |
11fdf7f2 TL |
530 | } |
531 | } | |
532 | ||
533 | TEST_P(ComparatorDBTest, FindShortestSeparator) { | |
534 | std::string s1 = "abc1xyz"; | |
535 | std::string s2 = "abc3xy"; | |
536 | ||
537 | BytewiseComparator()->FindShortestSeparator(&s1, s2); | |
538 | ASSERT_EQ("abc2", s1); | |
539 | ||
540 | s1 = "abc5xyztt"; | |
541 | ||
542 | ReverseBytewiseComparator()->FindShortestSeparator(&s1, s2); | |
543 | ASSERT_EQ("abc5", s1); | |
544 | ||
545 | s1 = "abc3"; | |
546 | s2 = "abc2xy"; | |
547 | ReverseBytewiseComparator()->FindShortestSeparator(&s1, s2); | |
548 | ASSERT_EQ("abc3", s1); | |
549 | ||
550 | s1 = "abc3xyz"; | |
551 | s2 = "abc2xy"; | |
552 | ReverseBytewiseComparator()->FindShortestSeparator(&s1, s2); | |
553 | ASSERT_EQ("abc3", s1); | |
554 | ||
555 | s1 = "abc3xyz"; | |
556 | s2 = "abc2"; | |
557 | ReverseBytewiseComparator()->FindShortestSeparator(&s1, s2); | |
558 | ASSERT_EQ("abc3", s1); | |
559 | ||
560 | std::string old_s1 = s1 = "abc2xy"; | |
561 | s2 = "abc2"; | |
562 | ReverseBytewiseComparator()->FindShortestSeparator(&s1, s2); | |
563 | ASSERT_TRUE(old_s1 >= s1); | |
564 | ASSERT_TRUE(s1 > s2); | |
565 | } | |
566 | ||
567 | TEST_P(ComparatorDBTest, SeparatorSuccessorRandomizeTest) { | |
568 | // Char list for boundary cases. | |
569 | std::array<unsigned char, 6> char_list{{0, 1, 2, 253, 254, 255}}; | |
570 | Random rnd(301); | |
571 | ||
572 | for (int attempts = 0; attempts < 1000; attempts++) { | |
573 | uint32_t size1 = rnd.Skewed(4); | |
574 | uint32_t size2; | |
575 | ||
576 | if (rnd.OneIn(2)) { | |
577 | // size2 to be random size | |
578 | size2 = rnd.Skewed(4); | |
579 | } else { | |
580 | // size1 is within [-2, +2] of size1 | |
581 | int diff = static_cast<int>(rnd.Uniform(5)) - 2; | |
582 | int tmp_size2 = static_cast<int>(size1) + diff; | |
583 | if (tmp_size2 < 0) { | |
584 | tmp_size2 = 0; | |
585 | } | |
586 | size2 = static_cast<uint32_t>(tmp_size2); | |
587 | } | |
588 | ||
589 | std::string s1; | |
590 | std::string s2; | |
591 | for (uint32_t i = 0; i < size1; i++) { | |
592 | if (rnd.OneIn(2)) { | |
593 | // Use random byte | |
594 | s1 += static_cast<char>(rnd.Uniform(256)); | |
595 | } else { | |
596 | // Use one byte in char_list | |
597 | char c = static_cast<char>(char_list[rnd.Uniform(sizeof(char_list))]); | |
598 | s1 += c; | |
599 | } | |
600 | } | |
601 | ||
602 | // First set s2 to be the same as s1, and then modify s2. | |
603 | s2 = s1; | |
604 | s2.resize(size2); | |
605 | // We start from the back of the string | |
606 | if (size2 > 0) { | |
607 | uint32_t pos = size2 - 1; | |
608 | do { | |
609 | if (pos >= size1 || rnd.OneIn(4)) { | |
610 | // For 1/4 chance, use random byte | |
611 | s2[pos] = static_cast<char>(rnd.Uniform(256)); | |
612 | } else if (rnd.OneIn(4)) { | |
613 | // In 1/4 chance, stop here. | |
614 | break; | |
615 | } else { | |
616 | // Create a char within [-2, +2] of the matching char of s1. | |
617 | int diff = static_cast<int>(rnd.Uniform(5)) - 2; | |
618 | // char may be signed or unsigned based on platform. | |
619 | int s1_char = static_cast<int>(static_cast<unsigned char>(s1[pos])); | |
620 | int s2_char = s1_char + diff; | |
621 | if (s2_char < 0) { | |
622 | s2_char = 0; | |
623 | } | |
624 | if (s2_char > 255) { | |
625 | s2_char = 255; | |
626 | } | |
627 | s2[pos] = static_cast<char>(s2_char); | |
628 | } | |
629 | } while (pos-- != 0); | |
630 | } | |
631 | ||
632 | // Test separators | |
633 | for (int rev = 0; rev < 2; rev++) { | |
634 | if (rev == 1) { | |
635 | // switch s1 and s2 | |
636 | std::string t = s1; | |
637 | s1 = s2; | |
638 | s2 = t; | |
639 | } | |
640 | std::string separator = s1; | |
641 | BytewiseComparator()->FindShortestSeparator(&separator, s2); | |
642 | std::string rev_separator = s1; | |
643 | ReverseBytewiseComparator()->FindShortestSeparator(&rev_separator, s2); | |
644 | ||
645 | if (s1 == s2) { | |
646 | ASSERT_EQ(s1, separator); | |
647 | ASSERT_EQ(s2, rev_separator); | |
648 | } else if (s1 < s2) { | |
649 | ASSERT_TRUE(s1 <= separator); | |
650 | ASSERT_TRUE(s2 > separator); | |
651 | ASSERT_LE(separator.size(), std::max(s1.size(), s2.size())); | |
652 | ASSERT_EQ(s1, rev_separator); | |
653 | } else { | |
654 | ASSERT_TRUE(s1 >= rev_separator); | |
655 | ASSERT_TRUE(s2 < rev_separator); | |
656 | ASSERT_LE(rev_separator.size(), std::max(s1.size(), s2.size())); | |
657 | ASSERT_EQ(s1, separator); | |
658 | } | |
659 | } | |
660 | ||
661 | // Test successors | |
662 | std::string succ = s1; | |
663 | BytewiseComparator()->FindShortSuccessor(&succ); | |
664 | ASSERT_TRUE(succ >= s1); | |
665 | ||
666 | succ = s1; | |
667 | ReverseBytewiseComparator()->FindShortSuccessor(&succ); | |
668 | ASSERT_TRUE(succ <= s1); | |
669 | } | |
670 | } | |
671 | ||
f67539c2 | 672 | } // namespace ROCKSDB_NAMESPACE |
7c673cae FG |
673 | |
674 | int main(int argc, char** argv) { | |
1e59de90 | 675 | ROCKSDB_NAMESPACE::port::InstallStackTraceHandler(); |
7c673cae FG |
676 | ::testing::InitGoogleTest(&argc, argv); |
677 | return RUN_ALL_TESTS(); | |
678 | } |