【深入浅出leveldb】 比较器
【深入浅出leveldb】 比较器
【深入浅出leveldb】 比较器
源码版本【1.23】
代码位置【include/leveldb/comparator.h】【util/comparator.cc】
比较器里面包含了抽象类接口，同时提供了BytewiseComparatorImpl与InternalKeyComparator。
今天我们主要分析抽象类与BytewiseComparatorImpl以及相关无析构类。
1.抽象类
我们把注释删除掉之后，就只剩下下面的核心内容。
该类当中提供了4个接口，让子类去实现它，该类不可被实例化，因为该类是抽象类，同时提供的虚析构函数保证了继承之后，派生类可以调用对应析构释放内存。
在当前文件(comparator.h)中，还提供了BytewiseComparator函数。该函数的实现引申出线程安全的单例模式与无析构类如何编写。接下来看看如何实现。
class LEVELDB_EXPORT Comparator {
public:
virtual ~Comparator();
virtual int Compare(const Slice& a, const Slice& b) const = 0;
virtual const char* Name() const = 0;
virtual void FindShortestSeparator(std::string* start,
const Slice& limit) const = 0;
virtual void FindShortSuccessor(std::string* key) const = 0;
};
LEVELDB_EXPORT const Comparator* BytewiseComparator();
2.线程安全的单例模式
BytewiseComparator在comparator.cc中实现如下：
const Comparator* BytewiseComparator() {
static NoDestructor<BytewiseComparatorImpl> singleton;
return singleton.get();
}
C++11保证了静态局部变量的初始化过程是线程安全的。
具体可以看：
https://www.zhihu.com/question/267013757
NoDestructor无析构类首先来看一下构造函数，位置在util/no_destructor.h。
explicit NoDestructor(ConstructorArgTypes&&... constructor_args) {
static_assert(sizeof(instance_storage_) >= sizeof(InstanceType),
"instance_storage_ is not large enough to hold the instance");
static_assert(
alignof(decltype(instance_storage_)) >= alignof(InstanceType),
"instance_storage_ does not meet the instance's alignment requirement");
new (&instance_storage_)
InstanceType(std::forward<ConstructorArgTypes>(constructor_args)...);
这里使用了placement new，在已经分配好的内存上构造对象，同时采用了完美转发传递参数。
禁止拷贝动作：
NoDestructor(const NoDestructor&) = delete;
NoDestructor& operator=(const NoDestructor&) = delete;
这里定义了默认的析构：
~NoDestructor() = default;
返回对象：
InstanceType* get() {
return reinterpret_cast<InstanceType*>(&instance_storage_);
}
私有成员：
typename std::aligned_storage<sizeof(InstanceType),
alignof(InstanceType)>::type instance_storage_;
这里有个alignof(InstanceType)主要是取出InstanceType的字节对齐，例如：
64位操作系统gcc上，int字节对齐时4，而Test只有一个int成员，所以这里输出4。
class Test {
private:
int i;
};
void func() {
cout << alignof(Test) << endl; // 这一行输出为4
}
继续看aligned_storage：
template<std::size_t _Len, std::size_t _Align =
__alignof__(typename __aligned_storage_msa<_Len>::__type)>
struct aligned_storage
{
union type
{
unsigned char __data[_Len];
struct __attribute__((__aligned__((_Align)))) { } __align;
};
};
可以看到取出的type是个union，里面是有固定的数组，不考虑内部的__align，上述instance_storage_可以变为：
unsigned char[sizeof(InstanceType)] instance_storage_;
综上，NoDestructor构造函数会在NoDestructor的内存instance_storage_中采用placement new 构造对象，最后使用get返回单例对象。
3.BytewiseComparatorImpl
BytewiseComparatorImpl直接继承Comparator，下面是Name与Compare的实现。
class BytewiseComparatorImpl : public Comparator {
public:
BytewiseComparatorImpl() = default;
const char* Name() const override { return "leveldb.BytewiseComparator"; }
int Compare(const Slice& a, const Slice& b) const override {
return a.compare(b);
}
};
FindShortestSeparator(start, limit)作用是start < limit，就把start修改为*start和limit的共同前缀的ascii加1。
例如：
*start: hellow
limit: helloz
返回：*start变为hellox
看一下具体实现：首先拿出两者最小长度，从index=0开始到*start与limit的某个index值不相等结束。
如果此时index到头了 不做处理，说明两者完全一致，否则对*start的ascii加1。
void FindShortestSeparator(std::string* start,
const Slice& limit) const override {
// Find length of common prefix
size_t min_length = std::min(start->size(), limit.size());
size_t diff_index = 0;
while ((diff_index < min_length) &&
((*start)[diff_index] == limit[diff_index])) {
diff_index++;
}
if (diff_index >= min_length) {
// Do not shorten if one string is a prefix of the other
} else {
uint8_t diff_byte = static_cast<uint8_t>((*start)[diff_index]);
if (diff_byte < static_cast<uint8_t>(0xff) &&
diff_byte + 1 < static_cast<uint8_t>(limit[diff_index])) {
(*start)[diff_index]++;
start->resize(diff_index + 1);
assert(Compare(*start, limit) < 0);
}
}
}
另一个函数是FindShortSuccessor。直接对key中第一个以uint8方式+1的字节+1，清除该位后面的数据。
void FindShortSuccessor(std::string* key) const override {
// Find first character that can be incremented
size_t n = key->size();
for (size_t i = 0; i < n; i++) {
const uint8_t byte = (*key)[i];
if (byte != static_cast<uint8_t>(0xff)) {
(*key)[i] = byte + 1;
key->resize(i + 1);
return;
}
}
// *key is a run of 0xffs. Leave it alone.
}
测试：
string s1("hellow"), s2("hellow");
bt->FindShortestSeparator(&s1, l);
cout << s1 << endl; // hellox
bt->FindShortSuccessor(&s2);
cout << s2 << endl; // i
本节完~