leveldb - coding


废话

先是看的hash.hhash.cc在实现里面用到coding里面的DecodeFixed32(),于是就把coding.hcoding.cc看了。

顺带提一下Hash,leveldb用的hash函数是murmurhash的变种。

coding .h .cc

单从这个头文件来看,可以猜到和Slice有关,通过std::stringchar []以及uint32_tuint64_tSlice关联起来。

头文件可以分成如下部分

  • Encode
    • Fixed
      EncodeFixed32
      EncodeFixed64
    • Non-Fixed
      EncodeVarint32
      EncodeVarint64
  • Decode
    • Fixed
      DecodeFixed32
      DecodeFixed64
    • Non-Fixed
      GetVarint32Ptr
      GetVarint32PtrFallback
      GetVarint64Ptr
  • PutXXX
    • Fixed
      PutFixed32
      PutFixed64
    • Non-Fixed
      PutVarint32
      PutVarint64
  • GetXXX
    • GetVarint32 (wrapper)
    • GetVarint64 (wrapper)
  • Other
    • PutLengthPrefixedSlice
    • GetLengthPrefixedSlice
    • VarintLength //确定需要几个char来装一个uintxx_t

理清结构之后再来看实现就简单了。由于我的机器是小端的所以省去了些代码不看,这样EncodeFixedxxxx就只有

memcpy(buf, &value, sizeof(value));

一行代码,它的作用是将value的值拷贝到buf[]中。同样,PutFixedxxx变成了这样

void PutFixedxx(std::string* dst, uintxx_t value) {
  char buf[sizeof(value)];
  EncodeFixedxx(buf, value);
  dst->append(buf, sizeof(buf));
}

它的作用是将uintxx_t的值追加到std::string的尾部。(不知道这和Qt里面QString的QString("%1").arg(uint32_t)有什么区别)

为了节约内存,没必要对于一个较小的数也使用sizeof(value)的大小,所以leveldb提供了EncodeVarintxx。原理就不讲了,我用leveldb的EncodeVarint32写了个例了,看看就能明白了

/*********************************************************
          File Name:xx.cpp
          Author: Abby Cin
          Mail: abbytsing@gmail.com
          Created Time: Sun 20 Mar 2016 02:20:07 PM CST
**********************************************************/

#include <iostream>
#include <cstring>

char *encodevarint32(char *dst, uint32_t v)
{
  unsigned char *ptr = reinterpret_cast<unsigned char *>(dst);
  static const int B = 128;
  if(v < (1<<7)) //只需要一个 uchar
  {
    *(ptr++) = v;
  }
  else if(v < (1<<14)) // 需要两个 uchar
  {
    *(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);
}

uint32_t decodevarint32(char *data, uint32_t limit)
{
  unsigned char *ptr = reinterpret_cast<unsigned char*>(data);
  unsigned char tmp;
  uint32_t res = 0;
  int multi = 0;
  limit -= 1;
  while(limit--)
  {
    memcpy(&tmp, ptr, sizeof(tmp));
    res |= ((tmp ^ 128) * (1<<multi));
    multi += 7;
    ptr++;
  }
  res |= *ptr * (1 << multi);
  return res;
}

int main(int argc, char *argv[])
{
  if(argc != 2)
  {
    std::cerr << argv[0] << "number (0..28)\n";
    return 1;
  }
  char buf[5] = {0};
  char *ptr = encodevarint32(buf, (1<<atoi(argv[1])) + 13);
  uint32_t limit = ptr - buf;
  char *data = new char[limit];
  memcpy(data, buf, limit);
  uint32_t res = decodevarint32(data, limit);
  std::cout << "res = " << res << std::endl;
  delete [] data;
}

最后PutVarintxxx变成了这样

void PutVarintxx(std::string* dst, uintxx_t v) {
  char buf[size]; // 32 => size = 5; 64 => size = 10
  char* ptr = EncodeVarint64(buf, v);
  dst->append(buf, ptr - buf);
}

Decodexxx如果是Fixed的话,直接使用memcpy搞定,如果是Varint的话会在GetVarintxx里面调用GetVarintxxPtr以及GetVarintxxPtrFallback原理和上面例子中的类似。

最后来说说Put(Get)LengthPrefixedSlice,虽然还没有看其它的源码,但是可以感觉出,xxxVarintxxx主要就是为这两个函数服务的,而这两个函数我猜很有可能是用来在Slice中存取key的。

PS
atoi? stod?



转载请注明:Serenity » leveldb - coding