Matrixlin Blog

Happy coding, blog for everything

leveldb 源码分析(1)varint

一、背景

level db底层对字符的存储是按varint进行编码的。varint是一个紧凑的编码方式。数字越大占用的字节数越大。存储的文本有并不总是大的数字,所以一定程度上,能够减少存储的空间。

 

二、编码方式

wps_clip_image-21799

    1. 首先编码后的数字,被放到一个字符数组里面。

    2. 每个字符八位,最高有效位代表剩下7位的内容是在原来数字的某个位置。

    3. 如果这位是1,则代表下一个字节的内容也是编码这个数字的。而且位置比当前还高。

    4. 如果这位是0,则代表下面的字节不是编码这个数字的。也就可以解析结束了。

    5. 通过上面的分析,我们可以得知。32位的int,最多要5个字节来编码存储。64位的int,最多要10个自己编码存储。解码的话只要一位位的去分析,知道遇到最高位是0 的字节就终止。

 

三、代码介绍

 编码32位int:

char* EncodeVarint32(char* dst, uint32_t v) {
  // Operate on characters as unsigneds
  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);
}

简直就是暴力。每次检查,从最低有效位开始存。最后把移动过的指针返回。

 

编码64位int:

 

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);
  return reinterpret_cast<char*>(ptr);
}

简单明了。

 

解码32位int

 

bool GetVarint32(Slice* input, uint32_t* value) {
  const char* p = input->data();
  const char* limit = p + input->size();
  const char* q = GetVarint32Ptr(p, limit, value);
  if (q == NULL) {
    return false;
  } else {
    *input = Slice(q, limit - q);
    return true;
  }
}

对input字符串里面最近的一个varint进行解码,然后放到value指向的内存位置。

奇怪的是这里面还调用了GetVarint32Ptr。然后把input的指针移动向下一个未解析的位置。

下面是这个的代码:

 

inline 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);
}

如果是小数的话,直接返回放弃指针的下一个位置,如果是比较大的则调用GetVarint32PtrFallback进行解析:

 

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;
      return reinterpret_cast<const char*>(p);
    }
  }
  return NULL;
}

也是每一位检查有没有最高有效位1,有的话,解析出来放到目标value下。如果没有,就进行返回。通俗易懂。

编码64位就更简单了:

 

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);
  return reinterpret_cast<char*>(ptr);
}

四、彩蛋

最近看头号玩家,居然用上了这个。好吧,本篇文章还没结束。

leveldb 其实是个单机存储引擎。对一个字符串的存储,其实不会像上面进行编码。会把字符串的上面进行varint编码放content里面,然后把实际内存追加到后面:

 

void PutLengthPrefixedSlice(std::string* dst, const Slice& value) {
  PutVarint32(dst, value.size());
  dst->append(value.data(), value.size());
}

这里的PutVarint32源码:

 

void PutVarint32(std::string* dst, uint32_t v) {
  char buf[5];
  char* ptr = EncodeVarint32(buf, v);
  dst->append(buf, ptr - buf);
}

看完是不是感觉很巧妙?

Emacs入门指南及配置Python开发IDE

最近在家里倒腾emacs这玩意,都说牛逼的程序员都用这个东西。我不知天高地厚的表示也想玩玩。

一开始在ubuntu 安装emacs,然后看着它的tutorial,学了几个命令以为万事大吉,然后在学Python,想着要不在emacs里面搞个python的IDE,顺便高亮,最好像eclipse那边智能提示,然后像之前使用的vs那样快捷键运行,最好调试也搞定。

第一天上网查的时候看的是http://cnlox.is-programmer.com/posts/35867.html

完全不懂作者在讲啥。各种百度谷歌。包括翻墙上emacs中文网。上面下了两个电子版,看了一点emacs lisp发现这东西有点意思。

渐渐明白,原来emacs的配置基本都是用lisp写的。

然后知道~/.emacs文件一开始没有,要自己新建,至于配置网上随便找一个都能做到了酷炫。然后知道~/.emacs.d/init.d这个文件夹下的文件是emacs启动时会一起运行的。

百度时看到一个很好的关于emacs的文章:http://blog.csdn.net/redguardtoo/article/details/7222501/

里面提到作者自己的配置,我就去他github上面按他所说的安装:https://github.com/redguardtoo/emacs.d

Please remove the file “~/.emacs.d/init.el” (“~” means the parent directory of your “.emacs.d”).

Uninstall any package which not located in “~/.emacs.d”. For example, run “apt-get autoremove emacs-w3m” on Debian/Ubuntu. All packages will be placed at “~/.emacs.d” from now on.

Download latest setup and extract its content into “~/.emacs.d”.

Or you can use stable setup which has been regression tested by volunteers every 3 months.

If you’ve installed Git, run command `cd ~; git clone https://github.com/redguardtoo/emacs.d.git.emacs.d` in terminal.

Ensure that the init.el contained in this repo ends up at ~/.emacs.d/init.el.

其实按这个我是没安装成功的。不过注意https改成git,然后就可以,当然你要先安装git还要有自己的账户密码这是必须的,这个容易自己百度。

然后开始按http://blog.csdn.net/mikelearnscode/article/details/23022277 进行配置,不过里面的elpy安装不成功,然后我找到elpy的官网:http://elpy.readthedocs.org/en/latest/introduction.html

按它这样的install还是不行。结果用了国外一小哥的配置就可以了:

(require 'package)
(setq package-archives '(("gnu" . "http://elpa.gnu.org/packages/")
                 ("marmalade" . "http://marmalade-repo.org/packages/")))
; Auto-complete:
(add-to-list 'package-archives '("melpa" . "http://melpa.milkbox.net/packages/") t)
; Org mode
(add-to-list 'package-archives '("org" . "http://orgmode.org/elpa/") t)
(add-to-list 'package-archives '("elpy" . "http://jorgenschaefer.github.io/packages/") t)

这些放.emacs上面。

最后按下包管理工具el-get:http://emacser.com/el-get.htm

如果安装不成功可以试着改下上面的url,改成如下:https://raw.githubusercontent.com/dimitri/el-get/master/el-get-install.el

然后试了一下emacs上写python,可以高亮和智能提示。

如果不懂emacs lisp,完全按着别人怎么配怎么配就完全没意义了。所以我接下来要弄懂lisp.

这个花了我一个白天加一个半天完成。

赋闲在家的TO DO LIST

1.实验楼或慕课网完成如下课程:Linux,PHP,Pyhon,JS,HTML,CSS..

2.看完Python核心编程。。

3.看书。

4.读英语。

关于进阶段的学习目标

 距离毕业答辩还有5天或6天,听说会提前,但是没关系,反正该来的还是要来得,快乐或忧伤。自古离别多伤感。
 昨天wilti联系了我,让准备下面几个技术:
 1、linux看一下《鸟哥的linux私房菜》,搞个环境,实操一下
 2、python看一下python核心编程,后续主要应该是用python
 3、前端看http://www.w3school.com.cn/index.html
 4、写一个监控系统,采集设备的基础信息(cpu使用率、负载、内存使用、磁盘、网络)
 5、js,打算刷speaking js
 6、itil
 鸟哥那部分我看过前面几章,讲得挺好的,主要是一些linux命令,配置和一些简单的原理。后面没看完主要是因为当时没用得上。不过现在得重新拿起来回顾下。
python看过高级编程,这本确实没看过,不过语法都一样,做几个project会更熟悉。前端这个= =,大一暑假就看过了,后来就没碰了,主要是后面写网页总是遇到那么几个主要的标签,有什么不会的我都是直接查的。“我可是身经百战的了”。监控系统可以作为一个project试下,无非就是监控一个linux信息,以网页动态实时展现出来。
 其实,技术这种东西,我比较喜欢以问题为向导。比如某个技术,html,先熟悉下大概的原理,然后学习几个主要的标签,然后实践写几个网页加深理解。我不会记住所有的细节,但几个重要的标签用多了自然会记住。原理性的东西当然要理解,最好能理解其设计的哲学理念。具体的api或标签可以等你要用了再查,而且一般你查个一两次就记住了。如果只是记住一个非常偏僻的标签,平时又不怎么用到,那是没用的。就好像孔乙己的茴香豆的茴有四种写法。什么技术都一样,包括python,linux,js。这些东西我都实践过。python用Django写过网站后端,linux上我部署过j2ee的环境,写过shell,js的话从大三就基本在用了。虽然我现在记不起所有细节,但是大概简单的原理的我都知道。如果让我现在马上写一个project,我是很容易上手的。所以学习的,不是特定的技术,而是方法。难怪有人说:码农做的事小学毕业就能做了。真正厉害的是思想。
 博客对我来说,其实是读书笔记,我没有宣传,没有观众。我只是想写写证明我做过,督促自己去做而已。
 最近开始回顾下各种技术,有时间的话会深入读一些各个方面的高级材料。
 最后的最后,以一副五角星结尾。