levelDB 代码阅读笔记 02 comparator

 1
 2// A Comparator object provides a total order across slices that are
 3// used as keys in an sstable or a database.  A Comparator implementation
 4// must be thread-safe since leveldb may invoke its methods concurrently
 5// from multiple threads.
 6class LEVELDB_EXPORT Comparator {
 7 public:
 8  virtual ~Comparator();
 9
10  // Three-way comparison.  Returns value:
11  //   < 0 iff "a" < "b",
12  //   == 0 iff "a" == "b",
13  //   > 0 iff "a" > "b"
14  virtual int Compare(const Slice& a, const Slice& b) const = 0;
15
16  // The name of the comparator.  Used to check for comparator
17  // mismatches (i.e., a DB created with one comparator is
18  // accessed using a different comparator.
19  //
20  // The client of this package should switch to a new name whenever
21  // the comparator implementation changes in a way that will cause
22  // the relative ordering of any two keys to change.
23  //
24  // Names starting with "leveldb." are reserved and should not be used
25  // by any clients of this package.
26  virtual const char* Name() const = 0;
27
28  // Advanced functions: these are used to reduce the space requirements
29  // for internal data structures like index blocks.
30
31  // If *start < limit, changes *start to a short string in [start,limit).
32  // Simple comparator implementations may return with *start unchanged,
33  // i.e., an implementation of this method that does nothing is correct.
34  virtual void FindShortestSeparator(std::string* start,
35                                     const Slice& limit) const = 0;
36
37  // Changes *key to a short string >= *key.
38  // Simple comparator implementations may return with *key unchanged,
39  // i.e., an implementation of this method that does nothing is correct.
40  virtual void FindShortSuccessor(std::string* key) const = 0;
41};
42

 1
 2class BytewiseComparatorImpl : public Comparator {
 3 public:
 4  BytewiseComparatorImpl() = default;
 5
 6  const char* Name() const override { return "leveldb.BytewiseComparator"; }
 7
 8  int Compare(const Slice& a, const Slice& b) const override {
 9    return a.compare(b);
10  }
11
12  void FindShortestSeparator(std::string* start,
13                             const Slice& limit) const override {
14    // Find length of common prefix
15    size_t min_length = std::min(start->size(), limit.size());
16    size_t diff_index = 0;
17    // diff_index是一个不同的index
18    while ((diff_index < min_length) &&
19           ((*start)[diff_index] == limit[diff_index])) {
20      diff_index++;
21    }
22
23    if (diff_index >= min_length) {
24      // 没有不同的字符，说明一个串是另一个串的前缀，不需要做任何操作
25      // Do not shorten if one string is a prefix of the other
26    } else {
27      uint8_t diff_byte = static_cast<uint8_t>((*start)[diff_index]);
28      if (diff_byte < static_cast<uint8_t>(0xff) &&
29          diff_byte + 1 < static_cast<uint8_t>(limit[diff_index])) {
30        (*start)[diff_index]++;
31        start->resize(diff_index + 1);
32        assert(Compare(*start, limit) < 0);
33      }
34    }
35  }
36
37  void FindShortSuccessor(std::string* key) const override {
38    // Find first character that can be incremented
39    size_t n = key->size();
40    for (size_t i = 0; i < n; i++) {
41      const uint8_t byte = (*key)[i];
42      if (byte != static_cast<uint8_t>(0xff)) {
43        (*key)[i] = byte + 1;
44        key->resize(i + 1);
45        return;
46      }
47    }
48    // *key is a run of 0xffs.  Leave it alone.
49  }
50};
51
52

1
2const Comparator* BytewiseComparator() {
3  static NoDestructor<BytewiseComparatorImpl> singleton;
4  return singleton.get();
5}

 1
 2struct singleton_t
 3{
 4
 5  static
 6  singleton_t &
 7  instance()
 8  {
 9    static singleton_t s;
10    return s;
11  } // instance
12
13  singleton_t(const singleton_t &) = delete;
14  singleton_t & operator = (const singleton_t &) = delete;
15
16private:
17
18  singleton_t() {}
19  ~singleton_t() {}
20
21
22

 1
 2// Wraps an instance whose destructor is never called.
 3//
 4// This is intended for use with function-level static variables.
 5template <typename InstanceType>
 6class NoDestructor {
 7 public:
 8  template <typename... ConstructorArgTypes>
 9  explicit NoDestructor(ConstructorArgTypes&&... constructor_args) {
10    static_assert(sizeof(instance_storage_) >= sizeof(InstanceType),
11                  "instance_storage_ is not large enough to hold the instance");
12    static_assert(
13        alignof(decltype(instance_storage_)) >= alignof(InstanceType),
14        "instance_storage_ does not meet the instance's alignment requirement");
15    new (&instance_storage_)
16        InstanceType(std::forward<ConstructorArgTypes>(constructor_args)...);
17  }
18
19  ~NoDestructor() = default;
20
21  NoDestructor(const NoDestructor&) = delete;
22  NoDestructor& operator=(const NoDestructor&) = delete;
23
24  InstanceType* get() {
25    return reinterpret_cast<InstanceType*>(&instance_storage_);
26  }
27
28 private:
29
30  typename std::aligned_storage<sizeof(InstanceType),
31                                alignof(InstanceType)>::type instance_storage_;
32};
33
34
35

1
2template<class T, class... Args>
3std::enable_if_t<!std::is_array<T>::value, std::unique_ptr<T>>
4make_unique(Args&&... args)
5{
6    return std::unique_ptr<T>(new T(std::forward<Args>(args)...));
7}

1
2    new (&instance_storage_)
3        InstanceType(std::forward<ConstructorArgTypes>(constructor_args)...);
4

 1
 2// within any block scope...
 3{
 4    alignas(T) unsigned char buf[sizeof(T)];
 5    // Statically allocate the storage with automatic storage duration
 6    // which is large enough for any object of type `T`.
 7    T* tptr = new(buf) T; // Construct a `T` object, placing it directly into your 
 8                          // pre-allocated storage at memory address `buf`.
 9    tptr->~T();           // You must **manually** call the object's destructor
10                          // if its side effects is depended by the program.
11}                         // Leaving this block scope automatically deallocates `buf`.
12
13

 1
 2// Copyright (c) 2018 The LevelDB Authors. All rights reserved.
 3// Use of this source code is governed by a BSD-style license that can be
 4// found in the LICENSE file. See the AUTHORS file for names of contributors.
 5
 6#include "util/no_destructor.h"
 7
 8#include <cstdint>
 9#include <cstdlib>
10#include <utility>
11#include <iostream>
12
13#include "gtest/gtest.h"
14
15namespace leveldb {
16
17namespace {
18
19struct DoNotDestruct {
20 public:
21  DoNotDestruct(uint32_t a, uint64_t b) : a(a), b(b) {}
22  ~DoNotDestruct() { 
23    std::cout<<" dtor"<<std::endl;
24    std::abort(); }
25
26  // Used to check constructor argument forwarding.
27  uint32_t a;
28  uint64_t b;
29};
30
31constexpr const uint32_t kGoldenA = 0xdeadbeef;
32constexpr const uint64_t kGoldenB = 0xaabbccddeeffaabb;
33
34}  // namespace
35
36TEST(NoDestructorTest, StackInstance) {
37  NoDestructor<DoNotDestruct> instance(kGoldenA, kGoldenB);
38  ASSERT_EQ(kGoldenA, instance.get()->a);
39  ASSERT_EQ(kGoldenB, instance.get()->b);
40}
41
42TEST(NoDestructorTest, StaticInstance) {
43  static NoDestructor<DoNotDestruct> instance(kGoldenA, kGoldenB);
44  ASSERT_EQ(kGoldenA, instance.get()->a);
45  ASSERT_EQ(kGoldenB, instance.get()->b);
46}
47
48TEST(NoDestructorTest, StaticIns) {
49  static DoNotDestruct instance(kGoldenA, kGoldenB);
50  ASSERT_EQ(kGoldenA, instance.a);
51  ASSERT_EQ(kGoldenB, instance.b);
52}
53
54}  // namespace leveldb
55
56

 1
 2root@KUANZEREN-PC4:~/workspace/leveldb/build# ./leveldb_tests    --gtest_filter=*NoDestructor* 
 3Running main() from /root/workspace/leveldb/third_party/googletest/googletest/src/gtest_main.cc
 4Note: Google Test filter = *NoDestructor*
 5[==========] Running 3 tests from 1 test suite.
 6[----------] Global test environment set-up.
 7[----------] 3 tests from NoDestructorTest
 8[ RUN      ] NoDestructorTest.StackInstance
 9[       OK ] NoDestructorTest.StackInstance (0 ms)
10[ RUN      ] NoDestructorTest.StaticInstance
11[       OK ] NoDestructorTest.StaticInstance (0 ms)
12[ RUN      ] NoDestructorTest.StaticIns
13[       OK ] NoDestructorTest.StaticIns (0 ms)
14[----------] 3 tests from NoDestructorTest (0 ms total)
15
16[----------] Global test environment tear-down
17[==========] 3 tests from 1 test suite ran. (0 ms total)
18[  PASSED  ] 3 tests.
19 dtor
20Aborted
21

 1
 2int InternalKeyComparator::Compare(const Slice& akey, const Slice& bkey) const {
 3  // Order by:
 4  //    increasing user key (according to user-supplied comparator)
 5  //    decreasing sequence number
 6  //    decreasing type (though sequence# should be enough to disambiguate)
 7  int r = user_comparator_->Compare(ExtractUserKey(akey), ExtractUserKey(bkey));
 8  if (r == 0) {
 9
10    const uint64_t anum = DecodeFixed64(akey.data() + akey.size() - 8);
11    const uint64_t bnum = DecodeFixed64(bkey.data() + bkey.size() - 8);
12    if (anum > bnum) {
13      r = -1;
14    } else if (anum < bnum) {
15      r = +1;
16    }
17  }
18  return r;
19}

 1
 2// Modules in this directory should keep internal keys wrapped inside
 3// the following class instead of plain strings so that we do not
 4// incorrectly use string comparisons instead of an InternalKeyComparator.
 5class InternalKey {
 6 private:
 7  std::string rep_;
 8
 9 public:
10  InternalKey() {}  // Leave rep_ as empty to indicate it is invalid
11  InternalKey(const Slice& user_key, SequenceNumber s, ValueType t) {
12    AppendInternalKey(&rep_, ParsedInternalKey(user_key, s, t));
13  }
14
15  bool DecodeFrom(const Slice& s) {
16    rep_.assign(s.data(), s.size());
17    return !rep_.empty();
18  }
19
20  Slice Encode() const {
21    assert(!rep_.empty());
22    return rep_;
23  }
24
25  Slice user_key() const { return ExtractUserKey(rep_); }
26
27  void SetFrom(const ParsedInternalKey& p) {
28    rep_.clear();
29    AppendInternalKey(&rep_, p);
30  }
31
32  void Clear() { rep_.clear(); }
33
34  std::string DebugString() const;
35};
36
37
38
39

 1
 2static uint64_t PackSequenceAndType(uint64_t seq, ValueType t) {
 3  assert(seq <= kMaxSequenceNumber);
 4  assert(t <= kValueTypeForSeek);
 5  // 高位是sequence number,低位是type
 6  return (seq << 8) | t;
 7}
 8
 9void AppendInternalKey(std::string* result, const ParsedInternalKey& key) {
10  // 把user key这个slice 往result后拼接
11  result->append(key.user_key.data(), key.user_key.size());
12  PutFixed64(result, PackSequenceAndType(key.sequence, key.type));
13  // Result 中分了三部分
14  // user_key , sequence, type.  后两部分合成了一个uint64_t
15}
16

 1
 2// Value types encoded as the last component of internal keys.
 3// DO NOT CHANGE THESE ENUM VALUES: they are embedded in the on-disk
 4// data structures.
 5enum ValueType { kTypeDeletion = 0x0, kTypeValue = 0x1 };
 6// kValueTypeForSeek defines the ValueType that should be passed when
 7// constructing a ParsedInternalKey object for seeking to a particular
 8// sequence number (since we sort sequence numbers in decreasing order
 9// and the value type is embedded as the low 8 bits in the sequence
10// number in internal keys, we need to use the highest-numbered
11// ValueType, not the lowest).
12static const ValueType kValueTypeForSeek = kTypeValue;
13
14typedef uint64_t SequenceNumber;
15
16// We leave eight bits empty at the bottom so a type and sequence#
17// can be packed together into 64-bits.
18// 在真正pack的时候会做一个移位
19static const SequenceNumber kMaxSequenceNumber = ((0x1ull << 56) - 1);
20
21struct ParsedInternalKey {
22  Slice user_key;
23  SequenceNumber sequence;
24  ValueType type;
25
26  ParsedInternalKey() {}  // Intentionally left uninitialized (for speed)
27  ParsedInternalKey(const Slice& u, const SequenceNumber& seq, ValueType t)
28      : user_key(u), sequence(seq), type(t) {}
29  std::string DebugString() const;
30};
31

1
2  const uint64_t anum = DecodeFixed64(akey.data() + akey.size() - 8);
3    const uint64_t bnum = DecodeFixed64(bkey.data() + bkey.size() - 8);
4    if (anum > bnum) {
5      r = -1;
6    } else if (anum < bnum) {
7      r = +1;
8    }
9