dbformat.cc raw

   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  
  14  namespace leveldb {
  15  
  16  static uint64_t PackSequenceAndType(uint64_t seq, ValueType t) {
  17    assert(seq <= kMaxSequenceNumber);
  18    assert(t <= kValueTypeForSeek);
  19    return (seq << 8) | t;
  20  }
  21  
  22  void 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  
  27  std::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  
  34  std::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  
  44  const char* InternalKeyComparator::Name() const {
  45    return "leveldb.InternalKeyComparator";
  46  }
  47  
  48  int 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  
  66  void 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  
  85  void 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  
 100  const char* InternalFilterPolicy::Name() const { return user_policy_->Name(); }
 101  
 102  void 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  
 114  bool InternalFilterPolicy::KeyMayMatch(const Slice& key, const Slice& f) const {
 115    return user_policy_->KeyMayMatch(ExtractUserKey(key), f);
 116  }
 117  
 118  LookupKey::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