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
9namespace leveldb {
10
11static 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
19static 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
25static std::string ShortSuccessor(const std::string& s) {
26  std::string result = s;
27  InternalKeyComparator(BytewiseComparator()).FindShortSuccessor(&result);
28  return result;
29}
30
31static 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
47class FormatTest { };
48
49TEST(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
65TEST(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
101TEST(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
110int main(int argc, char** argv) {
111  return leveldb::test::RunAllTests();
112}
113