1 // Copyright (c) 2011-present, Facebook, Inc. All rights reserved.
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).
9 #include "memtable/stl_wrappers.h"
10 #include "rocksdb/db.h"
11 #include "rocksdb/env.h"
12 #include "test_util/testharness.h"
13 #include "test_util/testutil.h"
14 #include "util/hash.h"
15 #include "util/kv_map.h"
16 #include "util/random.h"
17 #include "util/string_util.h"
18 #include "utilities/merge_operators.h"
20 namespace ROCKSDB_NAMESPACE
{
23 static const Comparator
* kTestComparator
= nullptr;
25 class KVIter
: public Iterator
{
27 explicit KVIter(const stl_wrappers::KVMap
* map
)
28 : map_(map
), iter_(map_
->end()) {}
29 bool Valid() const override
{ return iter_
!= map_
->end(); }
30 void SeekToFirst() override
{ iter_
= map_
->begin(); }
31 void SeekToLast() override
{
35 iter_
= map_
->find(map_
->rbegin()->first
);
38 void Seek(const Slice
& k
) override
{
39 iter_
= map_
->lower_bound(k
.ToString());
41 void SeekForPrev(const Slice
& k
) override
{
42 iter_
= map_
->upper_bound(k
.ToString());
45 void Next() override
{ ++iter_
; }
46 void Prev() override
{
47 if (iter_
== map_
->begin()) {
54 Slice
key() const override
{ return iter_
->first
; }
55 Slice
value() const override
{ return iter_
->second
; }
56 Status
status() const override
{ return Status::OK(); }
59 const stl_wrappers::KVMap
* const map_
;
60 stl_wrappers::KVMap::const_iterator iter_
;
63 void AssertItersEqual(Iterator
* iter1
, Iterator
* iter2
) {
64 ASSERT_EQ(iter1
->Valid(), iter2
->Valid());
66 ASSERT_EQ(iter1
->key().ToString(), iter2
->key().ToString());
67 ASSERT_EQ(iter1
->value().ToString(), iter2
->value().ToString());
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
) {
76 stl_wrappers::KVMap
map((stl_wrappers::LessOfComparator(kTestComparator
)));
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());
83 int type
= rnd
->Uniform(2);
84 int index
= rnd
->Uniform(static_cast<int>(source_strings
.size()));
85 auto& key
= source_strings
[index
];
90 ASSERT_OK(db
->Put(WriteOptions(), key
, key
));
94 if (map
.find(key
) != map
.end()) {
97 ASSERT_OK(db
->Delete(WriteOptions(), key
));
104 std::unique_ptr
<Iterator
> iter(db
->NewIterator(ReadOptions()));
105 std::unique_ptr
<Iterator
> result_iter(new KVIter(&map
));
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());
117 result_iter
->SeekToFirst();
122 result_iter
->SeekToLast();
125 // Seek to random key
126 auto key_idx
= rnd
->Uniform(static_cast<int>(source_strings
.size()));
127 auto key
= source_strings
[key_idx
];
129 result_iter
->Seek(key
);
152 auto key_idx
= rnd
->Uniform(static_cast<int>(source_strings
.size()));
153 auto key
= source_strings
[key_idx
];
155 auto status
= db
->Get(ReadOptions(), key
, &result
);
156 if (map
.find(key
) == map
.end()) {
157 ASSERT_TRUE(status
.IsNotFound());
159 ASSERT_EQ(map
[key
], result
);
164 AssertItersEqual(iter
.get(), result_iter
.get());
165 is_valid
= iter
->Valid();
169 class DoubleComparator
: public Comparator
{
171 DoubleComparator() {}
173 const char* Name() const override
{ return "DoubleComparator"; }
175 int Compare(const Slice
& a
, const Slice
& b
) const override
{
177 double da
= std::stod(a
.ToString());
178 double db
= std::stod(b
.ToString());
180 double da
= std::strtod(a
.ToString().c_str(), 0 /* endptr */);
181 double db
= std::strtod(a
.ToString().c_str(), 0 /* endptr */);
185 } else if (da
> db
) {
191 void FindShortestSeparator(std::string
* /*start*/,
192 const Slice
& /*limit*/) const override
{}
194 void FindShortSuccessor(std::string
* /*key*/) const override
{}
197 class HashComparator
: public Comparator
{
201 const char* Name() const override
{ return "HashComparator"; }
203 int Compare(const Slice
& a
, const Slice
& b
) const override
{
204 uint32_t ha
= Hash(a
.data(), a
.size(), 66);
205 uint32_t hb
= Hash(b
.data(), b
.size(), 66);
208 } else if (ha
> hb
) {
214 void FindShortestSeparator(std::string
* /*start*/,
215 const Slice
& /*limit*/) const override
{}
217 void FindShortSuccessor(std::string
* /*key*/) const override
{}
220 class TwoStrComparator
: public Comparator
{
222 TwoStrComparator() {}
224 const char* Name() const override
{ return "TwoStrComparator"; }
226 int Compare(const Slice
& a
, const Slice
& b
) const override
{
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());
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
);
242 return a1
.compare(b1
);
244 return a2
.compare(b2
);
246 void FindShortestSeparator(std::string
* /*start*/,
247 const Slice
& /*limit*/) const override
{}
249 void FindShortSuccessor(std::string
* /*key*/) const override
{}
251 } // anonymous namespace
253 class ComparatorDBTest
254 : public testing::Test
,
255 virtual public ::testing::WithParamInterface
<uint32_t> {
260 Options last_options_
;
261 std::unique_ptr
<const Comparator
> comparator_guard
;
264 ComparatorDBTest() : env_(Env::Default()), db_(nullptr) {
265 kTestComparator
= BytewiseComparator();
266 dbname_
= test::PerThreadDBPath("comparator_db_test");
267 BlockBasedTableOptions toptions
;
268 toptions
.format_version
= GetParam();
269 last_options_
.table_factory
.reset(
270 ROCKSDB_NAMESPACE::NewBlockBasedTableFactory(toptions
));
271 EXPECT_OK(DestroyDB(dbname_
, last_options_
));
274 ~ComparatorDBTest() override
{
276 EXPECT_OK(DestroyDB(dbname_
, last_options_
));
277 kTestComparator
= BytewiseComparator();
280 DB
* GetDB() { return db_
; }
282 void SetOwnedComparator(const Comparator
* cmp
, bool owner
= true) {
284 comparator_guard
.reset(cmp
);
286 comparator_guard
.reset();
288 kTestComparator
= cmp
;
289 last_options_
.comparator
= cmp
;
292 // Return the current option configuration.
293 Options
* GetOptions() { return &last_options_
; }
295 void DestroyAndReopen() {
296 // Destroy using last options
298 ASSERT_OK(TryReopen());
304 ASSERT_OK(DestroyDB(dbname_
, last_options_
));
310 last_options_
.create_if_missing
= true;
312 return DB::Open(last_options_
, dbname_
, &db_
);
316 INSTANTIATE_TEST_CASE_P(FormatDef
, ComparatorDBTest
,
317 testing::Values(test::kDefaultFormatVersion
));
318 INSTANTIATE_TEST_CASE_P(FormatLatest
, ComparatorDBTest
,
319 testing::Values(kLatestFormatVersion
));
321 TEST_P(ComparatorDBTest
, Bytewise
) {
322 for (int rand_seed
= 301; rand_seed
< 306; rand_seed
++) {
324 Random
rnd(rand_seed
);
325 DoRandomIteraratorTest(GetDB(),
326 {"a", "b", "c", "d", "e", "f", "g", "h", "i"}, &rnd
,
331 TEST_P(ComparatorDBTest
, SimpleSuffixReverseComparator
) {
332 SetOwnedComparator(new test::SimpleSuffixReverseComparator());
334 for (int rnd_seed
= 301; rnd_seed
< 316; rnd_seed
++) {
335 Options
* opt
= GetOptions();
336 opt
->comparator
= kTestComparator
;
338 Random
rnd(rnd_seed
);
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
++) {
344 source_prefixes
.push_back(rnd
.HumanReadableString(8));
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
] +
349 rnd
.HumanReadableString(rnd
.Uniform(8));
350 source_strings
.push_back(key
);
353 DoRandomIteraratorTest(GetDB(), source_strings
, &rnd
, 30, 600, 66);
357 TEST_P(ComparatorDBTest
, Uint64Comparator
) {
358 SetOwnedComparator(test::Uint64Comparator(), false /* owner */);
360 for (int rnd_seed
= 301; rnd_seed
< 316; rnd_seed
++) {
361 Options
* opt
= GetOptions();
362 opt
->comparator
= kTestComparator
;
364 Random
rnd(rnd_seed
);
365 Random64
rnd64(rnd_seed
);
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();
373 memcpy(&str
[0], static_cast<void*>(&r
), 8);
374 source_strings
.push_back(str
);
377 DoRandomIteraratorTest(GetDB(), source_strings
, &rnd
, 200, 1000, 66);
381 TEST_P(ComparatorDBTest
, DoubleComparator
) {
382 SetOwnedComparator(new DoubleComparator());
384 for (int rnd_seed
= 301; rnd_seed
< 316; rnd_seed
++) {
385 Options
* opt
= GetOptions();
386 opt
->comparator
= kTestComparator
;
388 Random
rnd(rnd_seed
);
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
++) {
399 source_strings
.push_back(std::to_string(r
/ to_divide
));
402 DoRandomIteraratorTest(GetDB(), source_strings
, &rnd
, 200, 1000, 66);
406 TEST_P(ComparatorDBTest
, HashComparator
) {
407 SetOwnedComparator(new HashComparator());
409 for (int rnd_seed
= 301; rnd_seed
< 316; rnd_seed
++) {
410 Options
* opt
= GetOptions();
411 opt
->comparator
= kTestComparator
;
413 Random
rnd(rnd_seed
);
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));
421 DoRandomIteraratorTest(GetDB(), source_strings
, &rnd
, 200, 1000, 66);
425 TEST_P(ComparatorDBTest
, TwoStrComparator
) {
426 SetOwnedComparator(new TwoStrComparator());
428 for (int rnd_seed
= 301; rnd_seed
< 316; rnd_seed
++) {
429 Options
* opt
= GetOptions();
430 opt
->comparator
= kTestComparator
;
432 Random
rnd(rnd_seed
);
434 std::vector
<std::string
> source_strings
;
435 // Randomly generate source keys
436 for (int i
= 0; i
< 100; i
++) {
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
);
447 DoRandomIteraratorTest(GetDB(), source_strings
, &rnd
, 200, 1000, 66);
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
));
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
));
472 } // anonymous namespace
474 TEST_P(ComparatorDBTest
, IsSameLengthImmediateSuccessor
) {
479 VerifyNotSuccessor(s
, t
);
484 VerifyNotSuccessor(s
, t
);
487 // not last byte different
490 VerifyNotSuccessor(s
, t
);
496 VerifyNotSuccessor(s
, t
);
501 VerifySuccessor(s
, t
);
504 const char s_array
[] = "\x50\x8a\xac";
505 const char t_array
[] = "\x50\x8a\xad";
508 VerifySuccessor(s
, t
);
511 const char s_array
[] = "\x50\x8a\xff";
512 const char t_array
[] = "\x50\x8b\x00";
515 VerifySuccessor(s
, t
);
518 const char s_array
[] = "\x50\x8a\xff\xff";
519 const char t_array
[] = "\x50\x8b\x00\x00";
522 VerifySuccessor(s
, t
);
525 const char s_array
[] = "\x50\x8a\xff\xff";
526 const char t_array
[] = "\x50\x8b\x00\x01";
529 VerifyNotSuccessor(s
, t
);
533 TEST_P(ComparatorDBTest
, FindShortestSeparator
) {
534 std::string s1
= "abc1xyz";
535 std::string s2
= "abc3xy";
537 BytewiseComparator()->FindShortestSeparator(&s1
, s2
);
538 ASSERT_EQ("abc2", s1
);
542 ReverseBytewiseComparator()->FindShortestSeparator(&s1
, s2
);
543 ASSERT_EQ("abc5", s1
);
547 ReverseBytewiseComparator()->FindShortestSeparator(&s1
, s2
);
548 ASSERT_EQ("abc3", s1
);
552 ReverseBytewiseComparator()->FindShortestSeparator(&s1
, s2
);
553 ASSERT_EQ("abc3", s1
);
557 ReverseBytewiseComparator()->FindShortestSeparator(&s1
, s2
);
558 ASSERT_EQ("abc3", s1
);
560 std::string old_s1
= s1
= "abc2xy";
562 ReverseBytewiseComparator()->FindShortestSeparator(&s1
, s2
);
563 ASSERT_TRUE(old_s1
>= s1
);
564 ASSERT_TRUE(s1
> s2
);
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}};
572 for (int attempts
= 0; attempts
< 1000; attempts
++) {
573 uint32_t size1
= rnd
.Skewed(4);
577 // size2 to be random size
578 size2
= rnd
.Skewed(4);
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
;
586 size2
= static_cast<uint32_t>(tmp_size2
);
591 for (uint32_t i
= 0; i
< size1
; i
++) {
594 s1
+= static_cast<char>(rnd
.Uniform(256));
596 // Use one byte in char_list
597 char c
= static_cast<char>(char_list
[rnd
.Uniform(sizeof(char_list
))]);
602 // First set s2 to be the same as s1, and then modify s2.
605 // We start from the back of the string
607 uint32_t pos
= size2
- 1;
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.
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
;
627 s2
[pos
] = static_cast<char>(s2_char
);
629 } while (pos
-- != 0);
633 for (int rev
= 0; rev
< 2; rev
++) {
640 std::string separator
= s1
;
641 BytewiseComparator()->FindShortestSeparator(&separator
, s2
);
642 std::string rev_separator
= s1
;
643 ReverseBytewiseComparator()->FindShortestSeparator(&rev_separator
, 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
);
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
);
662 std::string succ
= s1
;
663 BytewiseComparator()->FindShortSuccessor(&succ
);
664 ASSERT_TRUE(succ
>= s1
);
667 ReverseBytewiseComparator()->FindShortSuccessor(&succ
);
668 ASSERT_TRUE(succ
<= s1
);
672 } // namespace ROCKSDB_NAMESPACE
674 int main(int argc
, char** argv
) {
675 ROCKSDB_NAMESPACE::port::InstallStackTraceHandler();
676 ::testing::InitGoogleTest(&argc
, argv
);
677 return RUN_ALL_TESTS();