src/leveldb/db/dbformat.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 <stdio.h>
   6 #include "db/dbformat.h"
   7 #include "port/port.h"
   8 #include "util/coding.h"
   9
  10 namespace leveldb {
  11
  12 static uint64_t PackSequenceAndType(uint64_t seq, ValueType t) {
  13   assert(seq <= kMaxSequenceNumber);
  14   assert(t <= kValueTypeForSeek);
  15   return (seq << 8) | t;
  16 }
  17
  18 void 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
  23 std::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
  34 std::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
  46 const char* InternalKeyComparator::Name() const {
  47   return "leveldb.InternalKeyComparator";
  48 }
  49
  50 int 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
  68 void 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
  87 void 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
 101 const char* InternalFilterPolicy::Name() const {
 102   return user_policy_->Name();
 103 }
 104
 105 void 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
 117 bool InternalFilterPolicy::KeyMayMatch(const Slice& key, const Slice& f) const {
 118   return user_policy_->KeyMayMatch(ExtractUserKey(key), f);
 119 }
 120
 121 LookupKey::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