Redis源码学习基本数据结构之zipmap

zipmap

  Zipmap是为了实现保存Pair(String,String)数据的结构，是存储效率非常高的一种结构

zipmap结构

对于map :
  "foo" => "bar", "hello" => "world":
<zmlen><len>"foo"<len><free>"bar"<len>"hello"<len><free>"world"<end>
zmlen 1字节 键值对的个数
len 1字节表示key or value长度(0-253) 如果超过253 则使用5字节 第一个字节设为254 后面四个字节表示长度.
free 1字节 value长度中未使用的长度，主要考虑到value改变的情况.
end 0xFF 结束标志

此map的在内存中的结构为
0x02,0x03,foo,0x03,0x00,bar,0x05,hello,0x05,0x00,world,0xFF
2个键值对:len=3:foo:len=3:len=3:free=0:bar:len=5:hello:len=5:free=0:world:结束标志

主要api

unsigned char *zipmapNew(void);//创建一个空的map 只需要两个字节

unsigned char *zipmapSet(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned char *val, unsigned int vlen, int *update);//插入或者跟新一个键值对
unsigned char *zipmapDel(unsigned char *zm, unsigned char *key, unsigned int klen, int *deleted);//删除一个键值对

unsigned char *zipmapRewind(unsigned char *zm);// 返回第一个元素的地址
unsigned char *zipmapNext(unsigned char *p, unsigned char **key, unsigned int *klen, unsigned char **value, unsigned int *vlen);//得到p所指向的键值对的数据，并且返回下一个键值对的起始位置

int zipmapGet(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned char **value, unsigned int *vlen);//寻找key相等的键值对起始位置
int zipmapExists(unsigned char *zm, unsigned char *key, unsigned int klen);//key是否存在 调用了zipmapGet函数

unsigned int zipmapLen(unsigned char *zm);//如果长度小于254直接返回，否则需要遍历map得到其大小
size_t zipmapBlobLen(unsigned char *zm);//得到这个zipmap所占内存

zipmap插入or更新键值对

//不存在则插入否则更新
unsigned char *zipmapSet(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned char *val, unsigned int vlen, int *update) {
    unsigned int zmlen, offset;
    unsigned int freelen, reqlen = zipmapRequiredLength(klen,vlen);
    unsigned int empty, vempty;
    unsigned char *p;

    freelen = reqlen;
    if (update) *update = 0;
    p = zipmapLookupRaw(zm,key,klen,&zmlen);//得到总长度 并且找到有没有这个key
    if (p == NULL) {//没有找到  插入新的pair
        zm = zipmapResize(zm, zmlen+reqlen);//重新申请内存
        p = zm+zmlen-1;//要被填充键值对数据的起始位置
        zmlen = zmlen+reqlen;//更新zipmap所占字节数
        if (zm[0] < ZIPMAP_BIGLEN) zm[0]++;//更新pair个数
    } else {
        //找到了key  更新 value
        if (update) *update = 1;
        freelen = zipmapRawEntryLength(p);//返回p所代表的键值对所占有的空间
        if (freelen < reqlen) {//如果更新的这个键值对所需空间大于 此键值对目前所占有的空间 更新
            offset = p-zm;//记录下p的偏移量
            zm = zipmapResize(zm, zmlen-freelen+reqlen);//realloc
            p = zm+offset;//重新得到p的地址
            memmove(p+reqlen, p+freelen, zmlen-(offset+freelen+1));//后移数据，腾出空间放置更新的value
            zmlen = zmlen-freelen+reqlen;//更新zipmap所占内存大小
            freelen = reqlen;//freelen == reqlen
        }
    }

    empty = freelen-reqlen;//如果此键值对目前所占有的空间  大于 更新的这个键值对所需空间
    if (empty >= ZIPMAP_VALUE_MAX_FREE) {//empty>4的话就要重新分配内存
        /* First, move the tail <empty> bytes to the front, then resize
         * the zipmap to be <empty> bytes smaller. */
        offset = p-zm;
        memmove(p+reqlen, p+freelen, zmlen-(offset+freelen+1));//数据前移
        zmlen -= empty;//减去需要需要减少的字节个数
        zm = zipmapResize(zm, zmlen);//重新分配内存
        p = zm+offset;
        vempty = 0;//free 的值
    } else {//设置free的值
        vempty = empty;//free 的值
    }

    //把数据填充一下即可
    p += zipmapEncodeLength(p,klen);
    memcpy(p,key,klen);
    p += klen;
    p += zipmapEncodeLength(p,vlen);
    *p++ = vempty;
    memcpy(p,val,vlen);
    return zm;
}

zipmap删除键

unsigned char *zipmapDel(unsigned char *zm, unsigned char *key, unsigned int klen, int *deleted) {
    unsigned int zmlen, freelen;
    unsigned char *p = zipmapLookupRaw(zm,key,klen,&zmlen);//有这个key吗
    if (p) {//存在
        freelen = zipmapRawEntryLength(p);//这个键值对所占内存字节数
        memmove(p, p+freelen, zmlen-((p-zm)+freelen+1));//前移数据
        zm = zipmapResize(zm, zmlen-freelen);//realloc内存

        if (zm[0] < ZIPMAP_BIGLEN) zm[0]--;//如果可以 更新 键值对个数

        if (deleted) *deleted = 1;//删除了
    } else {
        if (deleted) *deleted = 0;//没有这个键
    }
    return zm;
}

参考

• https://redis.io/
• https://blog.csdn.net/u012658346/article/details/51329360