跳转至

leveldb 源码分析 2

本系列《leveldb 源码分析》共有 22 篇文章,这是第二篇。

3.Int Coding

轻松一刻,前面约定中讲过 Leveldb 使用了很多 VarInt 型编码,典型的如后面将涉及到的各种 key。其中的 编码、解码函数分为 VarInt 和 FixedInt 两种。int32 和 int64 操作都是类似的。

3.1 Eecode

首先是 FixedInt 编码,直接上代码,很简单明了。

void EncodeFixed32(char* buf, uint32_t value)
{
  if (port::kLittleEndian) {
    memcpy(buf, &value,sizeof(value));
  } else {
    buf[0] = value & 0xff;
    buf[1] = (value >> 8)& 0xff;
    buf[2] = (value >> 16)& 0xff;
    buf[3] = (value >> 24)& 0xff;
  }
}

下面是 VarInt 编码,int32 和 int64 格式,代码如下,有效位是 7bit 的,因此把 uint32 按 7bit 分割,对 unsigned char 赋值时,超出 0xFF 会自动截断,因此直接 *(ptr++) = v|B 即可,不需要再把 (v|B) 与 0xFF 作&操作。

char* EncodeVarint32(char* dst, uint32_t v)
{
  unsigned char* ptr =reinterpret_cast<unsigned char*>(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);
}

// 对于uint64,直接循环
char* EncodeVarint64(char* dst, uint64_t v) {
  static const int B = 128;
  unsigned char* ptr =reinterpret_cast<unsigned char*>(dst);
  while (v >= B) {
    *(ptr++) = (v & (B-1)) |B;
    v >>= 7;
  }
  *(ptr++) =static_cast<unsigned char>(v);
  returnreinterpret_cast<char*>(ptr);
}

3.2 Decode

Fixed Int 的 Decode,操作,代码:

inline uint32_t DecodeFixed32(const char* ptr)
{
  if (port::kLittleEndian) {
    uint32_t result;
    // gcc optimizes this to a plain load
    memcpy(&result, ptr,sizeof(result));
    return result;
  } else {
    return((static_cast<uint32_t>(static_cast<unsigned char>(ptr[0])))
        |(static_cast<uint32_t>(static_cast<unsigned char>(ptr[1])) <<8)
        | (static_cast<uint32_t>(static_cast<unsignedchar>(ptr[2])) << 16)
        |(static_cast<uint32_t>(static_cast<unsigned char>(ptr[3])) <<24));
  }
}

再来看看 VarInt 的解码,很简单,依次读取 1byte,直到最高位为 0 的 byte 结束,取低 7bit,作 (<<7) 移位操作组合成 Int。看代码:

const char* GetVarint32Ptr(const char* p,
                           const char* limit, 
                           uint32_t* value)
{
  if (p < limit) {
    uint32_t result =*(reinterpret_cast<const unsigned char*>(p));
    if ((result & 128) == 0) {
      *value = result;
      return p + 1;
    }
  }
  return GetVarint32PtrFallback(p,limit, value);
}

const char* GetVarint32PtrFallback(const char* p,
                                   const char* limit,
                                   uint32_t* value)
{
  uint32_t result = 0;
  for (uint32_t shift = 0; shift<= 28 && p < limit; shift += 7) {
    uint32_t byte =*(reinterpret_cast<const unsigned char*>(p));
    p++;
    if (byte & 128) { // More bytes are present
      result |= ((byte & 127)<< shift);
    } else {
      result |= (byte <<shift);
      *value = result;
      returnreinterpret_cast<const char*>(p);
    }
  }
  return NULL;
}