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).
5 //
6 // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
7 // Use of this source code is governed by a BSD-style license that can be
8 // found in the LICENSE file. See the AUTHORS file for names of contributors.
9 
10 #include "db/dbformat.h"
11 #include "logging/logging.h"
12 #include "test_util/testharness.h"
13 
14 namespace ROCKSDB_NAMESPACE {
15 
IKey(const std::string & user_key,uint64_t seq,ValueType vt)16 static std::string IKey(const std::string& user_key,
17                         uint64_t seq,
18                         ValueType vt) {
19   std::string encoded;
20   AppendInternalKey(&encoded, ParsedInternalKey(user_key, seq, vt));
21   return encoded;
22 }
23 
Shorten(const std::string & s,const std::string & l)24 static std::string Shorten(const std::string& s, const std::string& l) {
25   std::string result = s;
26   InternalKeyComparator(BytewiseComparator()).FindShortestSeparator(&result, l);
27   return result;
28 }
29 
ShortSuccessor(const std::string & s)30 static std::string ShortSuccessor(const std::string& s) {
31   std::string result = s;
32   InternalKeyComparator(BytewiseComparator()).FindShortSuccessor(&result);
33   return result;
34 }
35 
TestKey(const std::string & key,uint64_t seq,ValueType vt)36 static void TestKey(const std::string& key,
37                     uint64_t seq,
38                     ValueType vt) {
39   std::string encoded = IKey(key, seq, vt);
40 
41   Slice in(encoded);
42   ParsedInternalKey decoded("", 0, kTypeValue);
43 
44   ASSERT_TRUE(ParseInternalKey(in, &decoded));
45   ASSERT_EQ(key, decoded.user_key.ToString());
46   ASSERT_EQ(seq, decoded.sequence);
47   ASSERT_EQ(vt, decoded.type);
48 
49   ASSERT_TRUE(!ParseInternalKey(Slice("bar"), &decoded));
50 }
51 
52 class FormatTest : public testing::Test {};
53 
TEST_F(FormatTest,InternalKey_EncodeDecode)54 TEST_F(FormatTest, InternalKey_EncodeDecode) {
55   const char* keys[] = { "", "k", "hello", "longggggggggggggggggggggg" };
56   const uint64_t seq[] = {
57     1, 2, 3,
58     (1ull << 8) - 1, 1ull << 8, (1ull << 8) + 1,
59     (1ull << 16) - 1, 1ull << 16, (1ull << 16) + 1,
60     (1ull << 32) - 1, 1ull << 32, (1ull << 32) + 1
61   };
62   for (unsigned int k = 0; k < sizeof(keys) / sizeof(keys[0]); k++) {
63     for (unsigned int s = 0; s < sizeof(seq) / sizeof(seq[0]); s++) {
64       TestKey(keys[k], seq[s], kTypeValue);
65       TestKey("hello", 1, kTypeDeletion);
66     }
67   }
68 }
69 
TEST_F(FormatTest,InternalKeyShortSeparator)70 TEST_F(FormatTest, InternalKeyShortSeparator) {
71   // When user keys are same
72   ASSERT_EQ(IKey("foo", 100, kTypeValue),
73             Shorten(IKey("foo", 100, kTypeValue),
74                     IKey("foo", 99, kTypeValue)));
75   ASSERT_EQ(IKey("foo", 100, kTypeValue),
76             Shorten(IKey("foo", 100, kTypeValue),
77                     IKey("foo", 101, kTypeValue)));
78   ASSERT_EQ(IKey("foo", 100, kTypeValue),
79             Shorten(IKey("foo", 100, kTypeValue),
80                     IKey("foo", 100, kTypeValue)));
81   ASSERT_EQ(IKey("foo", 100, kTypeValue),
82             Shorten(IKey("foo", 100, kTypeValue),
83                     IKey("foo", 100, kTypeDeletion)));
84 
85   // When user keys are misordered
86   ASSERT_EQ(IKey("foo", 100, kTypeValue),
87             Shorten(IKey("foo", 100, kTypeValue),
88                     IKey("bar", 99, kTypeValue)));
89 
90   // When user keys are different, but correctly ordered
91   ASSERT_EQ(IKey("g", kMaxSequenceNumber, kValueTypeForSeek),
92             Shorten(IKey("foo", 100, kTypeValue),
93                     IKey("hello", 200, kTypeValue)));
94 
95   ASSERT_EQ(IKey("ABC2", kMaxSequenceNumber, kValueTypeForSeek),
96             Shorten(IKey("ABC1AAAAA", 100, kTypeValue),
97                     IKey("ABC2ABB", 200, kTypeValue)));
98 
99   ASSERT_EQ(IKey("AAA2", kMaxSequenceNumber, kValueTypeForSeek),
100             Shorten(IKey("AAA1AAA", 100, kTypeValue),
101                     IKey("AAA2AA", 200, kTypeValue)));
102 
103   ASSERT_EQ(
104       IKey("AAA2", kMaxSequenceNumber, kValueTypeForSeek),
105       Shorten(IKey("AAA1AAA", 100, kTypeValue), IKey("AAA4", 200, kTypeValue)));
106 
107   ASSERT_EQ(
108       IKey("AAA1B", kMaxSequenceNumber, kValueTypeForSeek),
109       Shorten(IKey("AAA1AAA", 100, kTypeValue), IKey("AAA2", 200, kTypeValue)));
110 
111   ASSERT_EQ(IKey("AAA2", kMaxSequenceNumber, kValueTypeForSeek),
112             Shorten(IKey("AAA1AAA", 100, kTypeValue),
113                     IKey("AAA2A", 200, kTypeValue)));
114 
115   ASSERT_EQ(
116       IKey("AAA1", 100, kTypeValue),
117       Shorten(IKey("AAA1", 100, kTypeValue), IKey("AAA2", 200, kTypeValue)));
118 
119   // When start user key is prefix of limit user key
120   ASSERT_EQ(IKey("foo", 100, kTypeValue),
121             Shorten(IKey("foo", 100, kTypeValue),
122                     IKey("foobar", 200, kTypeValue)));
123 
124   // When limit user key is prefix of start user key
125   ASSERT_EQ(IKey("foobar", 100, kTypeValue),
126             Shorten(IKey("foobar", 100, kTypeValue),
127                     IKey("foo", 200, kTypeValue)));
128 }
129 
TEST_F(FormatTest,InternalKeyShortestSuccessor)130 TEST_F(FormatTest, InternalKeyShortestSuccessor) {
131   ASSERT_EQ(IKey("g", kMaxSequenceNumber, kValueTypeForSeek),
132             ShortSuccessor(IKey("foo", 100, kTypeValue)));
133   ASSERT_EQ(IKey("\xff\xff", 100, kTypeValue),
134             ShortSuccessor(IKey("\xff\xff", 100, kTypeValue)));
135 }
136 
TEST_F(FormatTest,IterKeyOperation)137 TEST_F(FormatTest, IterKeyOperation) {
138   IterKey k;
139   const char p[] = "abcdefghijklmnopqrstuvwxyz";
140   const char q[] = "0123456789";
141 
142   ASSERT_EQ(std::string(k.GetUserKey().data(), k.GetUserKey().size()),
143             std::string(""));
144 
145   k.TrimAppend(0, p, 3);
146   ASSERT_EQ(std::string(k.GetUserKey().data(), k.GetUserKey().size()),
147             std::string("abc"));
148 
149   k.TrimAppend(1, p, 3);
150   ASSERT_EQ(std::string(k.GetUserKey().data(), k.GetUserKey().size()),
151             std::string("aabc"));
152 
153   k.TrimAppend(0, p, 26);
154   ASSERT_EQ(std::string(k.GetUserKey().data(), k.GetUserKey().size()),
155             std::string("abcdefghijklmnopqrstuvwxyz"));
156 
157   k.TrimAppend(26, q, 10);
158   ASSERT_EQ(std::string(k.GetUserKey().data(), k.GetUserKey().size()),
159             std::string("abcdefghijklmnopqrstuvwxyz0123456789"));
160 
161   k.TrimAppend(36, q, 1);
162   ASSERT_EQ(std::string(k.GetUserKey().data(), k.GetUserKey().size()),
163             std::string("abcdefghijklmnopqrstuvwxyz01234567890"));
164 
165   k.TrimAppend(26, q, 1);
166   ASSERT_EQ(std::string(k.GetUserKey().data(), k.GetUserKey().size()),
167             std::string("abcdefghijklmnopqrstuvwxyz0"));
168 
169   // Size going up, memory allocation is triggered
170   k.TrimAppend(27, p, 26);
171   ASSERT_EQ(std::string(k.GetUserKey().data(), k.GetUserKey().size()),
172             std::string("abcdefghijklmnopqrstuvwxyz0"
173                         "abcdefghijklmnopqrstuvwxyz"));
174 }
175 
TEST_F(FormatTest,UpdateInternalKey)176 TEST_F(FormatTest, UpdateInternalKey) {
177   std::string user_key("abcdefghijklmnopqrstuvwxyz");
178   uint64_t new_seq = 0x123456;
179   ValueType new_val_type = kTypeDeletion;
180 
181   std::string ikey;
182   AppendInternalKey(&ikey, ParsedInternalKey(user_key, 100U, kTypeValue));
183   size_t ikey_size = ikey.size();
184   UpdateInternalKey(&ikey, new_seq, new_val_type);
185   ASSERT_EQ(ikey_size, ikey.size());
186 
187   Slice in(ikey);
188   ParsedInternalKey decoded;
189   ASSERT_TRUE(ParseInternalKey(in, &decoded));
190   ASSERT_EQ(user_key, decoded.user_key.ToString());
191   ASSERT_EQ(new_seq, decoded.sequence);
192   ASSERT_EQ(new_val_type, decoded.type);
193 }
194 
TEST_F(FormatTest,RangeTombstoneSerializeEndKey)195 TEST_F(FormatTest, RangeTombstoneSerializeEndKey) {
196   RangeTombstone t("a", "b", 2);
197   InternalKey k("b", 3, kTypeValue);
198   const InternalKeyComparator cmp(BytewiseComparator());
199   ASSERT_LT(cmp.Compare(t.SerializeEndKey(), k), 0);
200 }
201 
202 }  // namespace ROCKSDB_NAMESPACE
203 
main(int argc,char ** argv)204 int main(int argc, char** argv) {
205   ::testing::InitGoogleTest(&argc, argv);
206   return RUN_ALL_TESTS();
207 }
208