Inside Bitcoin

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, uint64_t seq,
12                        ValueType vt) {
13  std::string encoded;
14  AppendInternalKey(&encoded, ParsedInternalKey(user_key, seq, vt));
15  return encoded;
16}
17
18static 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
24static std::string ShortSuccessor(const std::string& s) {
25  std::string result = s;
26  InternalKeyComparator(BytewiseComparator()).FindShortSuccessor(&result);
27  return result;
28}
29
30static 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
44class FormatTest {};
45
46TEST(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
68TEST(FormatTest, InternalKey_DecodeFromEmpty) {
69  InternalKey internal_key;
70
71  ASSERT_TRUE(!internal_key.DecodeFrom(""));
72}
73
74TEST(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
108TEST(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
115TEST(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
121TEST(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
131int main(int argc, char** argv) { return leveldb::test::RunAllTests(); }
132