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