深入浅出LevelDB —— 02 Slice
本文为原创文章，转载请严格遵守CC BY-NC-SA协议。
0. 引言
为了避免操作字节数组或字符串时不必要的拷贝，LevelDB使用了其自己实现的Slice类。同时，提供了字节数组和定长或变长整型的编码方式。
本文将介绍LevelDB中的Slice及相关编码方式，以便介绍并分析LevelDB的实现。
1.Slice
相关文件：include/leveldb/slice.h。
Slice是LevelDB中广泛使用的切片类。Slice的结构非常简单，其只有两个字段，分别保存切片指针与切片大小：
class LEVELDB_EXPORT Slice {
// ... ...
private:
const char* data_;
size_t size_;
};
Slice只关心切片的位置与大小，而不关心切片内容。因此。我们可以将Slice看做字节数组切片。
Slice有4种构造方法，其显式使用了默认的拷贝构造方法与拷贝构造运算符：
class LEVELDB_EXPORT Slice {
public:
// Create an empty slice.
Slice() : data_(""), size_(0) {}
// Create a slice that refers to d[0,n-1].
Slice(const char* d, size_t n) : data_(d), size_(n) {}
// Create a slice that refers to the contents of "s"
Slice(const std::string& s) : data_(s.data()), size_(s.size()) {}
// Create a slice that refers to s[0,strlen(s)-1]
Slice(const char* s) : data_(s), size_(strlen(s)) {}
// Intentionally copyable.
Slice(const Slice&) = default;
Slice& operator=(const Slice&) = default;
// ... ...
}
从Slice的构造方法可以看出，在Slice实例构造时，LevelDB不会为其分配新的内存空间，而是直接将其指向需要表示的切片头位置。因此，Slice的使用者需要确保在Slice实例还在使用时，其指向的内存不会销毁。
Slice的默认比较方式比较主要通过memcmp实现：
inline int Slice::compare(const Slice& b) const {
const size_t min_len = (size_ < b.size_) ? size_ : b.size_;
int r = memcmp(data_, b.data_, min_len);
if (r == 0) {
if (size_ < b.size_)
r = -1;
else if (size_ > b.size_)
r = +1;
}
return r;
}
2. 整型与Slice编码方式
相关文件：coding.h、coding.cc。
LevelDB中另一种常用的数据类型是整型。在LevelDB的源码中，其直接使用了<cstdint>的uint32_t与uint64_t作为整型类型，因此我们只需要关注其编码为字节数组的方式。
LevelDB中为整型提供了两类编码方式，一类是定长编码，一类是变长编码。
另外，LevelDB为了便于从字节数组中划分Slice，其还提供了一种LengthPrefixedSlice的编码方式，在编码中将长度确定的Slice的长度作为Slice的前缀。
2.1 整型定长编码
LevelDB中整型的定长编码（32bits或64bits）方式非常简单，只需要将整型按照小端的顺序编码即可：
inline void EncodeFixed32(char* dst, uint32_t value) {
uint8_t* const buffer = reinterpret_cast<uint8_t*>(dst);
// Recent clang and gcc optimize this to a single mov / str instruction.
buffer[0] = static_cast<uint8_t>(value);
buffer[1] = static_cast<uint8_t>(value >> 8);
buffer[2] = static_cast<uint8_t>(value >> 16);
buffer[3] = static_cast<uint8_t>(value >> 24);
}
inline void EncodeFixed64(char* dst, uint64_t value) {
uint8_t* const buffer = reinterpret_cast<uint8_t*>(dst);
// Recent clang and gcc optimize this to a single mov / str instruction.
buffer[0] = static_cast<uint8_t>(value);
buffer[1] = static_cast<uint8_t>(value >> 8);
buffer[2] = static_cast<uint8_t>(value >> 16);
buffer[3] = static_cast<uint8_t>(value >> 24);
buffer[4] = static_cast<uint8_t>(value >> 32);
buffer[5] = static_cast<uint8_t>(value >> 40);
buffer[6] = static_cast<uint8_t>(value >> 48);
buffer[7] = static_cast<uint8_t>(value >> 56);
}
定长整型的解码方式同理，这里不再赘述。
2.2 整型变长编码
当整型值较小时，LevelDB支持将其编码为变长整型，以减少其空间占用（对于值与类型最大值接近时，变长整型占用空间反而增加）。
对于变长整型编码，LevelDB需要知道该整型编码的终点在哪儿。因此，LevelDB将每个字节的最高位作为标识符，当字节最高位为1时表示编码未结束，当字节最高位为0时表示编码结束。因此，LevelDB的整型变长编码每8位用来表示整型值的7位。因此，当整型值接近其类型最大值时，变长编码需要额外一字节来容纳原整型值。
同样，变长整型编码也采用了小端顺序：
// 笔者注：Encode
char* EncodeVarint32(char* dst, uint32_t v) {
// Operate on characters as unsigneds
uint8_t* ptr = reinterpret_cast<uint8_t*>(dst);
static const int B = 128;
if (v < (1 << 7)) {
*(ptr++) = v;
} else if (v < (1 << 14)) {
*(ptr++) = v | B;
*(ptr++) = v >> 7;
} else if (v < (1 << 21)) {
*(ptr++) = v | B;
*(ptr++) = (v >> 7) | B;
*(ptr++) = v >> 14;
} else if (v < (1 << 28)) {
*(ptr++) = v | B;
*(ptr++) = (v >> 7) | B;
*(ptr++) = (v >> 14) | B;
*(ptr++) = v >> 21;
} else {
*(ptr++) = v | B;
*(ptr++) = (v >> 7) | B;
*(ptr++) = (v >> 14) | B;
*(ptr++) = (v >> 21) | B;
*(ptr++) = v >> 28;
}
return reinterpret_cast<char*>(ptr);
}
char* EncodeVarint64(char* dst, uint64_t v) {
static const int B = 128;
uint8_t* ptr = reinterpret_cast<uint8_t*>(dst);
while (v >= B) {
*(ptr++) = v | B;
v >>= 7;
}
*(ptr++) = static_cast<uint8_t>(v);
return reinterpret_cast<char*>(ptr);
}
在解码时，LevelDB只需要根据字节的最高位判断变长编码是否结束即可，这里不再赘述。另外，LevelDB提供了解码同时返回一些信息的方法，以方便在不通场景下的使用。
2.3 带长度的Slice编码
带长度的Slice的编码方式非常简单，只需要在原Slice之前加上用变长整型表示的Slice长度即可：
void PutLengthPrefixedSlice(std::string* dst, const Slice& value) {
PutVarint32(dst, value.size());
dst->append(value.data(), value.size());
}