Line data    Source code

       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       37170 : static uint64_t PackSequenceAndType(uint64_t seq, ValueType t) {
      13       37170 :   assert(seq <= kMaxSequenceNumber);
      14       37170 :   assert(t <= kValueTypeForSeek);
      15       37170 :   return (seq << 8) | t;
      16             : }
      17             : 
      18          93 : void AppendInternalKey(std::string* result, const ParsedInternalKey& key) {
      19          93 :   result->append(key.user_key.data(), key.user_key.size());
      20          93 :   PutFixed64(result, PackSequenceAndType(key.sequence, key.type));
      21          93 : }
      22             : 
      23           0 : std::string ParsedInternalKey::DebugString() const {
      24             :   char buf[50];
      25             :   snprintf(buf, sizeof(buf), "' @ %llu : %d",
      26             :            (unsigned long long) sequence,
      27           0 :            int(type));
      28           0 :   std::string result = "'";
      29           0 :   result += EscapeString(user_key.ToString());
      30             :   result += buf;
      31           0 :   return result;
      32             : }
      33             : 
      34           0 : std::string InternalKey::DebugString() const {
      35             :   std::string result;
      36             :   ParsedInternalKey parsed;
      37           0 :   if (ParseInternalKey(rep_, &parsed)) {
      38           0 :     result = parsed.DebugString();
      39             :   } else {
      40             :     result = "(bad)";
      41           0 :     result.append(EscapeString(rep_));
      42             :   }
      43           0 :   return result;
      44             : }
      45             : 
      46           0 : const char* InternalKeyComparator::Name() const {
      47           0 :   return "leveldb.InternalKeyComparator";
      48             : }
      49             : 
      50      588540 : 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      588540 :   int r = user_comparator_->Compare(ExtractUserKey(akey), ExtractUserKey(bkey));
      56      588539 :   if (r == 0) {
      57       26926 :     const uint64_t anum = DecodeFixed64(akey.data() + akey.size() - 8);
      58       26926 :     const uint64_t bnum = DecodeFixed64(bkey.data() + bkey.size() - 8);
      59       13463 :     if (anum > bnum) {
      60             :       r = -1;
      61       13205 :     } else if (anum < bnum) {
      62       13047 :       r = +1;
      63             :     }
      64             :   }
      65      588539 :   return r;
      66             : }
      67             : 
      68         395 : void InternalKeyComparator::FindShortestSeparator(
      69             :       std::string* start,
      70             :       const Slice& limit) const {
      71             :   // Attempt to shorten the user portion of the key
      72         395 :   Slice user_start = ExtractUserKey(*start);
      73         395 :   Slice user_limit = ExtractUserKey(limit);
      74         790 :   std::string tmp(user_start.data(), user_start.size());
      75         395 :   user_comparator_->FindShortestSeparator(&tmp, user_limit);
      76        1580 :   if (tmp.size() < user_start.size() &&
      77        1484 :       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         363 :     PutFixed64(&tmp, PackSequenceAndType(kMaxSequenceNumber,kValueTypeForSeek));
      81         726 :     assert(this->Compare(*start, tmp) < 0);
      82         726 :     assert(this->Compare(tmp, limit) < 0);
      83         363 :     start->swap(tmp);
      84             :   }
      85         395 : }
      86             : 
      87         122 : void InternalKeyComparator::FindShortSuccessor(std::string* key) const {
      88         122 :   Slice user_key = ExtractUserKey(*key);
      89         244 :   std::string tmp(user_key.data(), user_key.size());
      90         122 :   user_comparator_->FindShortSuccessor(&tmp);
      91         488 :   if (tmp.size() < user_key.size() &&
      92         290 :       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          56 :     PutFixed64(&tmp, PackSequenceAndType(kMaxSequenceNumber,kValueTypeForSeek));
      96         112 :     assert(this->Compare(*key, tmp) < 0);
      97          56 :     key->swap(tmp);
      98             :   }
      99         122 : }
     100             : 
     101         282 : const char* InternalFilterPolicy::Name() const {
     102         282 :   return user_policy_->Name();
     103             : }
     104             : 
     105         517 : 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         517 :   Slice* mkey = const_cast<Slice*>(keys);
     110       18754 :   for (int i = 0; i < n; i++) {
     111       18237 :     mkey[i] = ExtractUserKey(keys[i]);
     112             :     // TODO(sanjay): Suppress dups?
     113             :   }
     114         517 :   user_policy_->CreateFilter(keys, n, dst);
     115         517 : }
     116             : 
     117       16890 : bool InternalFilterPolicy::KeyMayMatch(const Slice& key, const Slice& f) const {
     118       16890 :   return user_policy_->KeyMayMatch(ExtractUserKey(key), f);
     119             : }
     120             : 
     121       36658 : LookupKey::LookupKey(const Slice& user_key, SequenceNumber s) {
     122       36658 :   size_t usize = user_key.size();
     123       36658 :   size_t needed = usize + 13;  // A conservative estimate
     124             :   char* dst;
     125       36658 :   if (needed <= sizeof(space_)) {
     126       36658 :     dst = space_;
     127             :   } else {
     128           0 :     dst = new char[needed];
     129             :   }
     130       36658 :   start_ = dst;
     131       36658 :   dst = EncodeVarint32(dst, usize + 8);
     132       36658 :   kstart_ = dst;
     133       36658 :   memcpy(dst, user_key.data(), usize);
     134       36658 :   dst += usize;
     135       36658 :   EncodeFixed64(dst, PackSequenceAndType(s, kValueTypeForSeek));
     136       36658 :   dst += 8;
     137       36658 :   end_ = dst;
     138       36658 : }
     139             : 
     140             : }  // namespace leveldb