1 // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file. See the AUTHORS file for names of contributors.
4
5 #include "db/dbformat.h"
6
7 #include "gtest/gtest.h"
8 #include "util/logging.h"
9
10 namespace leveldb {
11
IKey(const std::string & user_key,uint64_t seq,ValueType vt)12 static std::string IKey(const std::string& user_key, uint64_t seq,
13 ValueType vt) {
14 std::string encoded;
15 AppendInternalKey(&encoded, ParsedInternalKey(user_key, seq, vt));
16 return encoded;
17 }
18
Shorten(const std::string & s,const std::string & l)19 static std::string Shorten(const std::string& s, const std::string& l) {
20 std::string result = s;
21 InternalKeyComparator(BytewiseComparator()).FindShortestSeparator(&result, l);
22 return result;
23 }
24
ShortSuccessor(const std::string & s)25 static std::string ShortSuccessor(const std::string& s) {
26 std::string result = s;
27 InternalKeyComparator(BytewiseComparator()).FindShortSuccessor(&result);
28 return result;
29 }
30
TestKey(const std::string & key,uint64_t seq,ValueType vt)31 static void TestKey(const std::string& key, uint64_t seq, ValueType vt) {
32 std::string encoded = IKey(key, seq, vt);
33
34 Slice in(encoded);
35 ParsedInternalKey decoded("", 0, kTypeValue);
36
37 ASSERT_TRUE(ParseInternalKey(in, &decoded));
38 ASSERT_EQ(key, decoded.user_key.ToString());
39 ASSERT_EQ(seq, decoded.sequence);
40 ASSERT_EQ(vt, decoded.type);
41
42 ASSERT_TRUE(!ParseInternalKey(Slice("bar"), &decoded));
43 }
44
TEST(FormatTest,InternalKey_EncodeDecode)45 TEST(FormatTest, InternalKey_EncodeDecode) {
46 const char* keys[] = {"", "k", "hello", "longggggggggggggggggggggg"};
47 const uint64_t seq[] = {1,
48 2,
49 3,
50 (1ull << 8) - 1,
51 1ull << 8,
52 (1ull << 8) + 1,
53 (1ull << 16) - 1,
54 1ull << 16,
55 (1ull << 16) + 1,
56 (1ull << 32) - 1,
57 1ull << 32,
58 (1ull << 32) + 1};
59 for (int k = 0; k < sizeof(keys) / sizeof(keys[0]); k++) {
60 for (int s = 0; s < sizeof(seq) / sizeof(seq[0]); s++) {
61 TestKey(keys[k], seq[s], kTypeValue);
62 TestKey("hello", 1, kTypeDeletion);
63 }
64 }
65 }
66
TEST(FormatTest,InternalKey_DecodeFromEmpty)67 TEST(FormatTest, InternalKey_DecodeFromEmpty) {
68 InternalKey internal_key;
69
70 ASSERT_TRUE(!internal_key.DecodeFrom(""));
71 }
72
TEST(FormatTest,InternalKeyShortSeparator)73 TEST(FormatTest, InternalKeyShortSeparator) {
74 // When user keys are same
75 ASSERT_EQ(IKey("foo", 100, kTypeValue),
76 Shorten(IKey("foo", 100, kTypeValue), IKey("foo", 99, kTypeValue)));
77 ASSERT_EQ(
78 IKey("foo", 100, kTypeValue),
79 Shorten(IKey("foo", 100, kTypeValue), IKey("foo", 101, kTypeValue)));
80 ASSERT_EQ(
81 IKey("foo", 100, kTypeValue),
82 Shorten(IKey("foo", 100, kTypeValue), IKey("foo", 100, kTypeValue)));
83 ASSERT_EQ(
84 IKey("foo", 100, kTypeValue),
85 Shorten(IKey("foo", 100, kTypeValue), IKey("foo", 100, kTypeDeletion)));
86
87 // When user keys are misordered
88 ASSERT_EQ(IKey("foo", 100, kTypeValue),
89 Shorten(IKey("foo", 100, kTypeValue), IKey("bar", 99, kTypeValue)));
90
91 // When user keys are different, but correctly ordered
92 ASSERT_EQ(
93 IKey("g", kMaxSequenceNumber, kValueTypeForSeek),
94 Shorten(IKey("foo", 100, kTypeValue), IKey("hello", 200, kTypeValue)));
95
96 // When start user key is prefix of limit user key
97 ASSERT_EQ(
98 IKey("foo", 100, kTypeValue),
99 Shorten(IKey("foo", 100, kTypeValue), IKey("foobar", 200, kTypeValue)));
100
101 // When limit user key is prefix of start user key
102 ASSERT_EQ(
103 IKey("foobar", 100, kTypeValue),
104 Shorten(IKey("foobar", 100, kTypeValue), IKey("foo", 200, kTypeValue)));
105 }
106
TEST(FormatTest,InternalKeyShortestSuccessor)107 TEST(FormatTest, InternalKeyShortestSuccessor) {
108 ASSERT_EQ(IKey("g", kMaxSequenceNumber, kValueTypeForSeek),
109 ShortSuccessor(IKey("foo", 100, kTypeValue)));
110 ASSERT_EQ(IKey("\xff\xff", 100, kTypeValue),
111 ShortSuccessor(IKey("\xff\xff", 100, kTypeValue)));
112 }
113
TEST(FormatTest,ParsedInternalKeyDebugString)114 TEST(FormatTest, ParsedInternalKeyDebugString) {
115 ParsedInternalKey key("The \"key\" in 'single quotes'", 42, kTypeValue);
116
117 ASSERT_EQ("'The \"key\" in 'single quotes'' @ 42 : 1", key.DebugString());
118 }
119
TEST(FormatTest,InternalKeyDebugString)120 TEST(FormatTest, InternalKeyDebugString) {
121 InternalKey key("The \"key\" in 'single quotes'", 42, kTypeValue);
122 ASSERT_EQ("'The \"key\" in 'single quotes'' @ 42 : 1", key.DebugString());
123
124 InternalKey invalid_key;
125 ASSERT_EQ("(bad)", invalid_key.DebugString());
126 }
127
128 } // namespace leveldb
129
130