src/leveldb/db/dbformat_test.cc

   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 }