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 #include "util/logging.h" 7 #include "util/testharness.h" 8 9 namespace leveldb { 10 11 static std::string IKey(const std::string& user_key, 12 uint64_t seq, 13 ValueType vt) { 14 std::string encoded; 15 AppendInternalKey(&encoded, ParsedInternalKey(user_key, seq, vt)); 16 return encoded; 17 } 18 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 25 static std::string ShortSuccessor(const std::string& s) { 26 std::string result = s; 27 InternalKeyComparator(BytewiseComparator()).FindShortSuccessor(&result); 28 return result; 29 } 30 31 static void TestKey(const std::string& key, 32 uint64_t seq, 33 ValueType vt) { 34 std::string encoded = IKey(key, seq, vt); 35 36 Slice in(encoded); 37 ParsedInternalKey decoded("", 0, kTypeValue); 38 39 ASSERT_TRUE(ParseInternalKey(in, &decoded)); 40 ASSERT_EQ(key, decoded.user_key.ToString()); 41 ASSERT_EQ(seq, decoded.sequence); 42 ASSERT_EQ(vt, decoded.type); 43 44 ASSERT_TRUE(!ParseInternalKey(Slice("bar"), &decoded)); 45 } 46 47 class FormatTest { }; 48 49 TEST(FormatTest, InternalKey_EncodeDecode) { 50 const char* keys[] = { "", "k", "hello", "longggggggggggggggggggggg" }; 51 const uint64_t seq[] = { 52 1, 2, 3, 53 (1ull << 8) - 1, 1ull << 8, (1ull << 8) + 1, 54 (1ull << 16) - 1, 1ull << 16, (1ull << 16) + 1, 55 (1ull << 32) - 1, 1ull << 32, (1ull << 32) + 1 56 }; 57 for (int k = 0; k < sizeof(keys) / sizeof(keys[0]); k++) { 58 for (int s = 0; s < sizeof(seq) / sizeof(seq[0]); s++) { 59 TestKey(keys[k], seq[s], kTypeValue); 60 TestKey("hello", 1, kTypeDeletion); 61 } 62 } 63 } 64 65 TEST(FormatTest, InternalKeyShortSeparator) { 66 // When user keys are same 67 ASSERT_EQ(IKey("foo", 100, kTypeValue), 68 Shorten(IKey("foo", 100, kTypeValue), 69 IKey("foo", 99, kTypeValue))); 70 ASSERT_EQ(IKey("foo", 100, kTypeValue), 71 Shorten(IKey("foo", 100, kTypeValue), 72 IKey("foo", 101, kTypeValue))); 73 ASSERT_EQ(IKey("foo", 100, kTypeValue), 74 Shorten(IKey("foo", 100, kTypeValue), 75 IKey("foo", 100, kTypeValue))); 76 ASSERT_EQ(IKey("foo", 100, kTypeValue), 77 Shorten(IKey("foo", 100, kTypeValue), 78 IKey("foo", 100, kTypeDeletion))); 79 80 // When user keys are misordered 81 ASSERT_EQ(IKey("foo", 100, kTypeValue), 82 Shorten(IKey("foo", 100, kTypeValue), 83 IKey("bar", 99, kTypeValue))); 84 85 // When user keys are different, but correctly ordered 86 ASSERT_EQ(IKey("g", kMaxSequenceNumber, kValueTypeForSeek), 87 Shorten(IKey("foo", 100, kTypeValue), 88 IKey("hello", 200, kTypeValue))); 89 90 // When start user key is prefix of limit user key 91 ASSERT_EQ(IKey("foo", 100, kTypeValue), 92 Shorten(IKey("foo", 100, kTypeValue), 93 IKey("foobar", 200, kTypeValue))); 94 95 // When limit user key is prefix of start user key 96 ASSERT_EQ(IKey("foobar", 100, kTypeValue), 97 Shorten(IKey("foobar", 100, kTypeValue), 98 IKey("foo", 200, kTypeValue))); 99 } 100 101 TEST(FormatTest, InternalKeyShortestSuccessor) { 102 ASSERT_EQ(IKey("g", kMaxSequenceNumber, kValueTypeForSeek), 103 ShortSuccessor(IKey("foo", 100, kTypeValue))); 104 ASSERT_EQ(IKey("\xff\xff", 100, kTypeValue), 105 ShortSuccessor(IKey("\xff\xff", 100, kTypeValue))); 106 } 107 108 } // namespace leveldb 109 110 int main(int argc, char** argv) { 111 return leveldb::test::RunAllTests(); 112 } 113
