Home | History | Annotate | Download | only in db 
      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
    141