leveldb 源码分析(1)varint
一、背景
level db底层对字符的存储是按varint进行编码的。varint是一个紧凑的编码方式。数字越大占用的字节数越大。存储的文本有并不总是大的数字,所以一定程度上,能够减少存储的空间。
二、编码方式
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.读英语。
关于进阶段的学习目标