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
7#include <stdio.h>
8
9#include <sstream>
10
11#include "port/port.h"
12#include "util/coding.h"
13
14namespace leveldb {
15
16static uint64_t PackSequenceAndType(uint64_t seq, ValueType t) {
17  assert(seq <= kMaxSequenceNumber);
18  assert(t <= kValueTypeForSeek);
19  return (seq << 8) | t;
20}
21
22void AppendInternalKey(std::string* result, const ParsedInternalKey& key) {
23  result->append(key.user_key.data(), key.user_key.size());
24  PutFixed64(result, PackSequenceAndType(key.sequence, key.type));
25}
26
27std::string ParsedInternalKey::DebugString() const {
28  std::ostringstream ss;
29  ss << '\'' << EscapeString(user_key.ToString()) << "' @ " << sequence << " : "
30     << static_cast<int>(type);
31  return ss.str();
32}
33
34std::string InternalKey::DebugString() const {
35  ParsedInternalKey parsed;
36  if (ParseInternalKey(rep_, &parsed)) {
37    return parsed.DebugString();
38  }
39  std::ostringstream ss;
40  ss << "(bad)" << EscapeString(rep_);
41  return ss.str();
42}
43
44const char* InternalKeyComparator::Name() const {
45  return "leveldb.InternalKeyComparator";
46}
47
48int InternalKeyComparator::Compare(const Slice& akey, const Slice& bkey) const {
49  // Order by:
50  //    increasing user key (according to user-supplied comparator)
51  //    decreasing sequence number
52  //    decreasing type (though sequence# should be enough to disambiguate)
53  int r = user_comparator_->Compare(ExtractUserKey(akey), ExtractUserKey(bkey));
54  if (r == 0) {
55    const uint64_t anum = DecodeFixed64(akey.data() + akey.size() - 8);
56    const uint64_t bnum = DecodeFixed64(bkey.data() + bkey.size() - 8);
57    if (anum > bnum) {
58      r = -1;
59    } else if (anum < bnum) {
60      r = +1;
61    }
62  }
63  return r;
64}
65
66void InternalKeyComparator::FindShortestSeparator(std::string* start,
67                                                  const Slice& limit) const {
68  // Attempt to shorten the user portion of the key
69  Slice user_start = ExtractUserKey(*start);
70  Slice user_limit = ExtractUserKey(limit);
71  std::string tmp(user_start.data(), user_start.size());
72  user_comparator_->FindShortestSeparator(&tmp, user_limit);
73  if (tmp.size() < user_start.size() &&
74      user_comparator_->Compare(user_start, tmp) < 0) {
75    // User key has become shorter physically, but larger logically.
76    // Tack on the earliest possible number to the shortened user key.
77    PutFixed64(&tmp,
78               PackSequenceAndType(kMaxSequenceNumber, kValueTypeForSeek));
79    assert(this->Compare(*start, tmp) < 0);
80    assert(this->Compare(tmp, limit) < 0);
81    start->swap(tmp);
82  }
83}
84
85void InternalKeyComparator::FindShortSuccessor(std::string* key) const {
86  Slice user_key = ExtractUserKey(*key);
87  std::string tmp(user_key.data(), user_key.size());
88  user_comparator_->FindShortSuccessor(&tmp);
89  if (tmp.size() < user_key.size() &&
90      user_comparator_->Compare(user_key, tmp) < 0) {
91    // User key has become shorter physically, but larger logically.
92    // Tack on the earliest possible number to the shortened user key.
93    PutFixed64(&tmp,
94               PackSequenceAndType(kMaxSequenceNumber, kValueTypeForSeek));
95    assert(this->Compare(*key, tmp) < 0);
96    key->swap(tmp);
97  }
98}
99
100const char* InternalFilterPolicy::Name() const { return user_policy_->Name(); }
101
102void InternalFilterPolicy::CreateFilter(const Slice* keys, int n,
103                                        std::string* dst) const {
104  // We rely on the fact that the code in table.cc does not mind us
105  // adjusting keys[].
106  Slice* mkey = const_cast<Slice*>(keys);
107  for (int i = 0; i < n; i++) {
108    mkey[i] = ExtractUserKey(keys[i]);
109    // TODO(sanjay): Suppress dups?
110  }
111  user_policy_->CreateFilter(keys, n, dst);
112}
113
114bool InternalFilterPolicy::KeyMayMatch(const Slice& key, const Slice& f) const {
115  return user_policy_->KeyMayMatch(ExtractUserKey(key), f);
116}
117
118LookupKey::LookupKey(const Slice& user_key, SequenceNumber s) {
119  size_t usize = user_key.size();
120  size_t needed = usize + 13;  // A conservative estimate
121  char* dst;
122  if (needed <= sizeof(space_)) {
123    dst = space_;
124  } else {
125    dst = new char[needed];
126  }
127  start_ = dst;
128  dst = EncodeVarint32(dst, usize + 8);
129  kstart_ = dst;
130  memcpy(dst, user_key.data(), usize);
131  dst += usize;
132  EncodeFixed64(dst, PackSequenceAndType(s, kValueTypeForSeek));
133  dst += 8;
134  end_ = dst;
135}
136
137}  // namespace leveldb
138