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