redis源码阅读-zipmap(压缩字典)

¶redis源码阅读-zipmap(压缩字典)

¶zipmap介绍

zipmap,是redis定义的压缩字典，是用来保存键值对的数据结构。它保证hash表刚创建以及元素较少时，用更少的内存来存储，同时对查询效率没太大影响。

¶zipmap.h

/* String -> String Map data structure optimized for size.
 *
 * See zipmap.c for more info.
 *
 * --------------------------------------------------------------------------
 *
 * Copyright (c) 2009-2010, Salvatore Sanfilippo <antirez at gmail dot com>
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 *   * Redistributions of source code must retain the above copyright notice,
 *     this list of conditions and the following disclaimer.
 *   * Redistributions in binary form must reproduce the above copyright
 *     notice, this list of conditions and the following disclaimer in the
 *     documentation and/or other materials provided with the distribution.
 *   * Neither the name of Redis nor the names of its contributors may be used
 *     to endorse or promote products derived from this software without
 *     specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

#ifndef _ZIPMAP_H
#define _ZIPMAP_H

// 创建一个压缩字典结构
unsigned char *zipmapNew(void);
// 将键值对设置进压缩字典
unsigned char *zipmapSet(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned char *val, unsigned int vlen, int *update);
// 通过key删除压缩字典中的节点，并通过deleted标记是否被删除
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 *zm, unsigned char **key, unsigned int *klen, unsigned char **value, unsigned int *vlen);
// 通过key来获取value和vlen,返回0或1判断是否成功
int zipmapGet(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned char **value, unsigned int *vlen);
// 返回0或1判断是否存在key
int zipmapExists(unsigned char *zm, unsigned char *key, unsigned int klen);
// 获取压缩字典中节点数
unsigned int zipmapLen(unsigned char *zm);
// 获取压缩字典总长度
size_t zipmapBlobLen(unsigned char *zm);

// 以下两个函数都是用来测试的
void zipmapRepr(unsigned char *p);

#ifdef REDIS_TEST
int zipmapTest(int argc, char *argv[]);
#endif

#endif

¶zipmap.c

/* String -> String Map data structure optimized for size.
 * This file implements a data structure mapping strings to other strings
 * implementing an O(n) lookup data structure designed to be very memory
 * efficient.
 *
 * The Redis Hash type uses this data structure for hashes composed of a small
 * number of elements, to switch to a hash table once a given number of
 * elements is reached.
 *
 * Given that many times Redis Hashes are used to represent objects composed
 * of few fields, this is a very big win in terms of used memory.
 *
 * --------------------------------------------------------------------------
 *
 * Copyright (c) 2009-2010, Salvatore Sanfilippo <antirez at gmail dot com>
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 *   * Redistributions of source code must retain the above copyright notice,
 *     this list of conditions and the following disclaimer.
 *   * Redistributions in binary form must reproduce the above copyright
 *     notice, this list of conditions and the following disclaimer in the
 *     documentation and/or other materials provided with the distribution.
 *   * Neither the name of Redis nor the names of its contributors may be used
 *     to endorse or promote products derived from this software without
 *     specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

/* Memory layout of a zipmap, for the map "foo" => "bar", "hello" => "world":
 *
 * <zmlen><len>"foo"<len><free>"bar"<len>"hello"<len><free>"world"
 *
 * <zmlen> is 1 byte length that holds the current size of the zipmap.
 * When the zipmap length is greater than or equal to 254, this value
 * is not used and the zipmap needs to be traversed to find out the length.
 *
 * <len> is the length of the following string (key or value).
 * <len> lengths are encoded in a single value or in a 5 bytes value.
 * If the first byte value (as an unsigned 8 bit value) is between 0 and
 * 253, it's a single-byte length. If it is 254 then a four bytes unsigned
 * integer follows (in the host byte ordering). A value of 255 is used to
 * signal the end of the hash.
 *
 * <free> is the number of free unused bytes after the string, resulting
 * from modification of values associated to a key. For instance if "foo"
 * is set to "bar", and later "foo" will be set to "hi", it will have a
 * free byte to use if the value will enlarge again later, or even in
 * order to add a key/value pair if it fits.
 *
 * <free> is always an unsigned 8 bit number, because if after an
 * update operation there are more than a few free bytes, the zipmap will be
 * reallocated to make sure it is as small as possible.
 *
 * The most compact representation of the above two elements hash is actually:
 *
 * "\x02\x03foo\x03\x00bar\x05hello\x05\x00world\xff"
 *
 * Note that because keys and values are prefixed length "objects",
 * the lookup will take O(N) where N is the number of elements
 * in the zipmap and *not* the number of bytes needed to represent the zipmap.
 * This lowers the constant times considerably.
 */

/**
	压缩字典结构:<zmlen><len>"foo"<len><free>"bar"<len>"hello"<len><free>"world"
	zmlen表示压缩字典的节点数，zmlen占1个字节，最大值254,当zmlen的节点数小于254，就用zmlen表示压缩字典节点数，如果zmlen大于254，zmlen作用失效，要知道节点数，需要遍历整个压缩字典
	len表示key或者value的长度，所占字节数；当key或者value的长度小于254，len就只需要1个字节用来存储key或者value的长度；如果key或者value的长度大于等于254，就需要扩展为5个字节来表示长度
	free在value数据的前面，一般用在通过key对value进行缩减，会出现剩余的空闲空间(比如"foo" -> "bar" 缩减为 "foo" -> "b",这时就会剩余2个字节),free的大小不能超过4个字节。free一般只需要8位，因为更新操作很多时候都只更新很少一部分

	上面的字典结构可以用以下表示：
	\x02表示压缩字典节点数为2
	\x03表示元素长度为3字节
	\xff表示结束标志
	"\x02\x03foo\x03\x00bar\x05hello\x05\x00world\xff"
 */

#include <stdio.h>
#include <string.h>
#include "zmalloc.h"
#include "endianconv.h"

#define ZIPMAP_BIGLEN 254 // 压缩字典最大长度在254之内，压缩列表head位能记录压缩字典长度,如果大于254，则不能再记录压缩字典长度(如果想计算需要遍历整个压缩字典)
#define ZIPMAP_END 255 // 压缩列表的结尾，占一个8位，是压缩的结束标志

/* The following defines the max value for the <free> field described in the
 * comments above, that is, the max number of trailing bytes in a value. */
#define ZIPMAP_VALUE_MAX_FREE 4 // <free>字段最大字节数

/* The following macro returns the number of bytes needed to encode the length
 * for the integer value _l, that is, 1 byte for lengths < ZIPMAP_BIGLEN and
 * 5 bytes for all the other lengths. */
// 当输入的压缩字典长度时，如果压缩字典长度在ZIPMAP_BIGLEN之内，就只需要占用1字节，否则占用5字节
#define ZIPMAP_LEN_BYTES(_l) (((_l) < ZIPMAP_BIGLEN) ? 1 : sizeof(unsigned int)+1)

/* Create a new empty zipmap. */
// 创建一个空的压缩字典
unsigned char *zipmapNew(void) {
    unsigned char *zm = zmalloc(2);// 先为压缩字典分配2个字节的内存，因为空的压缩字典只有头部的记录长度(记录长度默认是1字节，最大5字节)和尾部的结束标志(1字节的\xff)

    zm[0] = 0; /* Length */ // 就是头部记录长度的1字节位
    zm[1] = ZIPMAP_END; // 尾部1字节的结束标志
    return zm; // 压缩字典起始就是一个字符串
}

/* Decode the encoded length pointed by 'p' */
// 从节点p中解码出编码长度
static unsigned int zipmapDecodeLength(unsigned char *p) {
    unsigned int len = *p; // p表示压缩字典中的每个节点的第一个区域，也就是1字节或者5字节的记录长度区，*p就是这个区的内容，也就是长度

    if (len < ZIPMAP_BIGLEN) return len; // 如果长度小于254，就让其作为节点的长度
	// 下面就是len大于254，也就是其所占5个字节
    memcpy(&len,p+1,sizeof(unsigned int)); // 为len再分配4个字节的内存,让其拥有5个字节的内存，有1个字节的内存刚开始就分配了
    memrev32ifbe(&len); // 将其地址进行小端字节序转换
    return len; // 获得地址里的内容
}

/* Encode the length 'l' writing it in 'p'. If p is NULL it just returns
 * the amount of bytes required to encode such a length. */
 // 将长度len编码进入p中(p为每个节点的第一个内存区，也就是1字节或者5字节的记录长度区);如果p为空，就返回编码len需要的字节数
static unsigned int zipmapEncodeLength(unsigned char *p, unsigned int len) {
    if (p == NULL) {
        return ZIPMAP_LEN_BYTES(len); // 直接返回len需要编码的字节数
    } else { // 不为空
        if (len < ZIPMAP_BIGLEN) { // 判断len小于254
            p[0] = len; // 只需要给len分配1个字节，也就是指针p指向的第0位
            return 1; // 返回1字节
        } else { // 如果len大于254
            p[0] = ZIPMAP_BIGLEN; // 先将254给第1个字节的内存
            memcpy(p+1,&len,sizeof(len)); // 然后再给它分配4个字节的内存
            memrev32ifbe(p+1); // 转换为小端字节序
            return 1+sizeof(len); // 返回5个字节
        }
    }
}

/* Search for a matching key, returning a pointer to the entry inside the
 * zipmap. Returns NULL if the key is not found.
 *
 * If NULL is returned, and totlen is not NULL, it is set to the entire
 * size of the zimap, so that the calling function will be able to
 * reallocate the original zipmap to make room for more entries. */
 // 通过key来搜索，返回在压缩字典中的节点，如果没有找到Key,返回NULL
 /*
	zm 表示压缩字典
	key 表示压缩字典中一个节点中的key
	klen key的长度
	totlen 压缩字典的总长度，当key没有查找到，就直接返回压缩字典的总长度
  */
static unsigned char *zipmapLookupRaw(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned int *totlen) {
    unsigned char *p = zm+1, *k = NULL; // p从压缩字典的第二位开始，也就是表示节点的位开始
    unsigned int l,llen;

    while(*p != ZIPMAP_END) { // 如果指针p指向的位置不在压缩字典的结尾标志，就表示还没有循环完
        unsigned char free;

        /* Match or skip the key */
        l = zipmapDecodeLength(p); // 从p(节点的len字段)中解码出长度
        llen = zipmapEncodeLength(NULL,l); // 然后获取长度所占字节数
		// 如果需要搜索的key不为null,并且匹配的k还没有，遍历到的节点的长度等于需要匹配节点的长度，并且指针P当前游标+llen位置的地址(len所在地址)与key地址匹配
		// 这旧表示匹配到相同的节点
        if (key != NULL && k == NULL && l == klen && !memcmp(p+llen,key,l)) {
            /* Only return when the user doesn't care
             * for the total length of the zipmap. */
            if (totlen != NULL) { // 如果总长不为空
                k = p; // 让k指向指针p当前游标位置处
            } else {
                return p;
            }
        }
        p += llen+l; // 指针跳过len和key所占区域，直接到value区
        /* Skip the value as well */
        l = zipmapDecodeLength(p); // 解码出value长度
        p += zipmapEncodeLength(NULL,l); // 让指针p跳过value的长度所占区，直接到value的数据区
        free = p[0]; // free区，一般1个字节
        p += l+1+free; /* +1 to skip the free byte */ // 然后跳过free区
    }
	// 这里是已经遍历完整个压缩字典，
    if (totlen != NULL) *totlen = (unsigned int)(p-zm)+1; // p-zm回到起始点 (p-zm)+1表示压缩字典的长度区，获取压缩字典长度
    return k; // 返回搜素到的节点
}
// 一个节点被需要的长度
// klen表示key长度，vlen表示value长度
static unsigned long zipmapRequiredLength(unsigned int klen, unsigned int vlen) {
    unsigned int l;

    l = klen+vlen+3; // klen和vlen是key和value数据占的长度，3表示free以及两个数据区记录长度位
    if (klen >= ZIPMAP_BIGLEN) l += 4; // 当klen大于等于254，就为长度扩容4字节
    if (vlen >= ZIPMAP_BIGLEN) l += 4; // 与上面一样
    return l; // 返回衣蛾节点需要的占用的长度
}

/* Return the total amount used by a key (encoded length + payload) */
// 返回一个key所占用的总长度(len+key)
static unsigned int zipmapRawKeyLength(unsigned char *p) {
    unsigned int l = zipmapDecodeLength(p); // key长度
    return zipmapEncodeLength(NULL,l) + l; //key长度+记录key长度的位的长度
}

/* Return the total amount used by a value
 * (encoded length + single byte free count + payload) */
 // 返回一个value所占用的总长度(len++free+key)
static unsigned int zipmapRawValueLength(unsigned char *p) {
    unsigned int l = zipmapDecodeLength(p); // value数据的长度
    unsigned int used;

    used = zipmapEncodeLength(NULL,l); // 编码len所占字节数
    used += p[used] + 1 + l; // len的长度+free的长度+value的长度
    return used; // 得到value需要的总长度
}

/* If 'p' points to a key, this function returns the total amount of
 * bytes used to store this entry (entry = key + associated value + trailing
 * free space if any). */
 // 返回节点所需总长度
static unsigned int zipmapRawEntryLength(unsigned char *p) {
    unsigned int l = zipmapRawKeyLength(p); // 先获得key的长度
    return l + zipmapRawValueLength(p+l); // key的长度+value的长度
}

// inline 内联函数 调整压缩列表长度
static inline unsigned char *zipmapResize(unsigned char *zm, unsigned int len) {
    zm = zrealloc(zm, len); //为zm扩展分配len长度的内存
    zm[len-1] = ZIPMAP_END; // 重新设置结尾标志
    return zm;
}

/* Set key to value, creating the key if it does not already exist.
 * If 'update' is not NULL, *update is set to 1 if the key was
 * already preset, otherwise to 0. */
// 如果key不存在，就将key和value设置到压缩字典中。如果update不为NULL,如果需要输入的key已经被预设(也就是已经被找到)，则设为1
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); // 获取需要的key和value占用的长度
    unsigned int empty, vempty;
    unsigned char *p;

    freelen = reqlen; // 让空闲长度等于请求长度
    if (update) *update = 0; // 如果update不为NULL或者0，则让update为0
    p = zipmapLookupRaw(zm,key,klen,&zmlen); // 判断压缩字典中有没有需要设置的key和value
    if (p == NULL) { // 如果key没有被找到
        /* Key not found: enlarge */
        zm = zipmapResize(zm, zmlen+reqlen); // 为压缩字典扩容，使其能够容纳新增的键值对
        p = zm+zmlen-1; // 让指针p指向新增键值对的起始地址(略过存储长度的地址,直接到键的起始地址)
        zmlen = zmlen+reqlen; // 总长度加上新增长度

        /* Increase zipmap length (this is an insert) */
        if (zm[0] < ZIPMAP_BIGLEN) zm[0]++; // 如果压缩字典长度在ZIPMAP_BIGLEN之内，长度就加
    } else {
        /* Key found. Is there enough space for the new value? */
        /* Compute the total length: */
		// 如果key在压缩字典中内找到，就将update置1,并且更新key的value值
        if (update) *update = 1;
        freelen = zipmapRawEntryLength(p); // 获取压缩字典中查找到的节点总长度
        if (freelen < reqlen) { // 如果节点总长度小于需要新增的长度
            /* Store the offset of this key within the current zipmap, so
             * it can be resized. Then, move the tail backwards so this
             * pair fits at the current position. */
            offset = p-zm; // 获取压缩字典起始地址到查找到的键值对的起始地址之间的偏移量
            zm = zipmapResize(zm, zmlen-freelen+reqlen); // 为压缩字典分配需要新增的多余的长度，zm回到压缩字典的起始地址
            p = zm+offset; // 扩容之后，再将指针p指向键值对的起始地址

            /* The +1 in the number of bytes to be moved is caused by the
             * end-of-zipmap byte. Note: the *original* zmlen is used. */
			// +1是压缩字典的结尾字符,zmlen-(offset+freelen+1)就是用来获取原压缩字典的当前节点的后面所有节点的长度,将后面所有节点所占的内存区域重新移动到更新后的节点的内存区域后面
            memmove(p+reqlen, p+freelen, zmlen-(offset+freelen+1));
            zmlen = zmlen-freelen+reqlen; // 总长度就是减去原来的节点长度，然后加上新增的节点长度
            freelen = reqlen;
        }
    }

    /* We now have a suitable block where the key/value entry can
     * be written. If there is too much free space, move the tail
     * of the zipmap a few bytes to the front and shrink the zipmap,
     * as we want zipmaps to be very space efficient. */
	// 上面讨论了压缩字典中没有key的情况和压缩字典中有key的情况；但是在压缩字典中有key的情况下，没有讨论如果节点总长度大于需要请求的长度，这时更新的value小于当前的value长度
    empty = freelen-reqlen; // 而free字段只预留了4个字节的空闲空间
    if (empty >= ZIPMAP_VALUE_MAX_FREE) { // 如果更新value后产生的空闲空间大于4字节
        /* First, move the tail <empty> bytes to the front, then resize
         * the zipmap to be <empty> bytes smaller. */
		 // 那么后面的节点就要向前移动，将多余的free字节消除
        offset = p-zm; // 这里获取当前位置与起始位置之间的偏移量
        memmove(p+reqlen, p+freelen, zmlen-(offset+freelen+1)); // 将后面所有内存区域(除去结尾符)移动到reqlen后面(这里reqlen比freelen小，遮阳将reqlen长度后面的字节覆盖了)
        zmlen -= empty; // 整个压缩字典减去空闲出来的长度
        zm = zipmapResize(zm, zmlen); // 改变压缩字典的长度
        p = zm+offset; // p指针重新指向当前位置
        vempty = 0; // value值前面的free长度变为0
    } else {
        vempty = empty; // 否则的话，空闲长度在4字节之内，这就不需要将空闲长度缩小了，empty的长度就是free字段的长度
    }

    /* Just write the key + value and we are done. */
    /* Key: */
    p += zipmapEncodeLength(p,klen); // 将klen编码写入len字段中,p指针向后偏移，略过len
    memcpy(p,key,klen); // 将输入的key放入len后面的key的位置
    p += klen; // p指针向后偏移
    /* Value: */
	// 值的操作与key的操作一样
    p += zipmapEncodeLength(p,vlen);
    *p++ = vempty;
    memcpy(p,val,vlen);
    return zm; // 然后返回插入节点后的压缩字典
}

/* Remove the specified key. If 'deleted' is not NULL the pointed integer is
 * set to 0 if the key was not found, to 1 if it was found and deleted. */
// 通过key删除节点;如果key没有被找到，就被设置为0，找到就被设置为1
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从压缩字典中找到key，并返回
    if (p) { // 如果key存在,就可以执行删除
        freelen = zipmapRawEntryLength(p); // 获取key所在节点的总长度
        memmove(p, p+freelen, zmlen-((p-zm)+freelen+1)); // 将节点后的所有内存(除了结尾符)向前移动删除节点的长度的位置，覆盖需要删除的节点
        zm = zipmapResize(zm, zmlen-freelen); // 将需要删除的节点的长度释放

        /* Decrease zipmap length */
        if (zm[0] < ZIPMAP_BIGLEN) zm[0]--; // 判断压缩字典总长度是否在限制之内，如果在限制之内就可以把其看做是长度，可以进行加减

        if (deleted) *deleted = 1; // 将标志位置1，表示找到需要删除的节点
    } else { // 如果key不存在
        if (deleted) *deleted = 0; // 将标志位置0，表示没有找到需要删除的节点
    }
    return zm; // 返回删除节点后的压缩字典
}

/* Call before iterating through elements via zipmapNext() */
// 在迭代压缩字典之前，将指针游标重置到第一个节点的起始地址
unsigned char *zipmapRewind(unsigned char *zm) {
    return zm+1;
}

/* This function is used to iterate through all the zipmap elements.
 * In the first call the first argument is the pointer to the zipmap + 1.
 * In the next calls what zipmapNext returns is used as first argument.
 * Example:
 *
 * unsigned char *i = zipmapRewind(my_zipmap);
 * while((i = zipmapNext(i,&key,&klen,&value,&vlen)) != NULL) {
 *     printf("%d bytes key at $p\n", klen, key);
 *     printf("%d bytes value at $p\n", vlen, value);
 * }
 */
/*
	用来迭代压缩字典中的节点(这个函数一次只能迭代一次)，所以起始地址需要忽略存储压缩字典总长度的第一个字节(所以需要先调用zipmapRewind将指针重置)
	*zm表示需要迭代的压缩字典
	**key用来存储迭代的key
	**value用来存储迭代的value
 */
unsigned char *zipmapNext(unsigned char *zm, unsigned char **key, unsigned int *klen, unsigned char **value, unsigned int *vlen) {
    if (zm[0] == ZIPMAP_END) return NULL; // 如果压缩字典为空
    if (key) {
        *key = zm; // 将指针移到到第一个节点的key的起始位置
        *klen = zipmapDecodeLength(zm); // 解码key的长度
        *key += ZIPMAP_LEN_BYTES(*klen); //获取key长度所占字符数,现在key指针就指向key数据的起始位置
    }
    zm += zipmapRawKeyLength(zm); // 将zm指针移动到key数据区结束位置
    if (value) {
        *value = zm+1; // 现在value指针指向value的起始位置
        *vlen = zipmapDecodeLength(zm); // 解码出value的长度
        *value += ZIPMAP_LEN_BYTES(*vlen); // 获取value长度所占字符数,现在value指针就指向value数据的起始位置
    }
    zm += zipmapRawValueLength(zm); // 将zm指针移动到value数据区结束位置

	// 现在key和value两个变量都存储了遍历的节点的键值对
    return zm; // 返回压缩字典，其游标在下一个节点的起始位置
}

/* Search a key and retrieve the pointer and len of the associated value.
 * If the key is found the function returns 1, otherwise 0. */
// 通过已知的key获取key对应的value数据区的起始地址，并存储到value变量中，value的值就存储到vlen中
int zipmapGet(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned char **value, unsigned int *vlen) {
    unsigned char *p;

	// 通过key查找压缩字典中的节点，并返回给p
    if ((p = zipmapLookupRaw(zm,key,klen,NULL)) == NULL) return 0;
    p += zipmapRawKeyLength(p); // 如果存在则将节点的key的总长度，并将游标移向总长度之后
    *vlen = zipmapDecodeLength(p); // 现在游标在value的len字段出，解码出len的长度，存储到vlen中
    *value = p + ZIPMAP_LEN_BYTES(*vlen) + 1; // 将value的数据区的起始地址给value
    return 1; // 找到就返回1
}

/* Return 1 if the key exists, otherwise 0 is returned. */
// 判断key是否存在,调用的是zipmapLookupRaw函数
int zipmapExists(unsigned char *zm, unsigned char *key, unsigned int klen) {
    return zipmapLookupRaw(zm,key,klen,NULL) != NULL;
}

/* Return the number of entries inside a zipmap */
// 遍历压缩字典，获得压缩字典中节点数
unsigned int zipmapLen(unsigned char *zm) {
    unsigned int len = 0;
    if (zm[0] < ZIPMAP_BIGLEN) { // 表示压缩字典的节点数小于254，压缩字典的第一个字节能表示节点数
        len = zm[0];
    } else { // 否则需要遍历
        unsigned char *p = zipmapRewind(zm); // 将指针重置到第一个节点的起始地址
        while((p = zipmapNext(p,NULL,NULL,NULL,NULL)) != NULL) len++; // 循环调用zipmapNext,遍历压缩字典，获得节点数

        /* Re-store length if small enough */
		// 如果遍历节点后，发现节点数还是小于254，也可以让压缩字典的第一个字典表示节点数，只是重新遍历了一次压缩字典
        if (len < ZIPMAP_BIGLEN) zm[0] = len;
    }
    return len;
}

/* Return the raw size in bytes of a zipmap, so that we can serialize
 * the zipmap on disk (or everywhere is needed) just writing the returned
 * amount of bytes of the C array starting at the zipmap pointer. */
// 获取压缩字典的总长度,用于序列化
size_t zipmapBlobLen(unsigned char *zm) {
    unsigned int totlen;
    zipmapLookupRaw(zm,NULL,0,&totlen);
    return totlen;
}

#ifdef REDIS_TEST
static void zipmapRepr(unsigned char *p) {
    unsigned int l;

    printf("{status %u}",*p++);
    while(1) {
        if (p[0] == ZIPMAP_END) {
            printf("{end}");
            break;
        } else {
            unsigned char e;

            l = zipmapDecodeLength(p);
            printf("{key %u}",l);
            p += zipmapEncodeLength(NULL,l);
            if (l != 0 && fwrite(p,l,1,stdout) == 0) perror("fwrite");
            p += l;

            l = zipmapDecodeLength(p);
            printf("{value %u}",l);
            p += zipmapEncodeLength(NULL,l);
            e = *p++;
            if (l != 0 && fwrite(p,l,1,stdout) == 0) perror("fwrite");
            p += l+e;
            if (e) {
                printf("[");
                while(e--) printf(".");
                printf("]");
            }
        }
    }
    printf("\n");
}

#define UNUSED(x) (void)(x)
int zipmapTest(int argc, char *argv[]) {
    unsigned char *zm;

    UNUSED(argc);
    UNUSED(argv);

    zm = zipmapNew();

    zm = zipmapSet(zm,(unsigned char*) "name",4, (unsigned char*) "foo",3,NULL);
    zm = zipmapSet(zm,(unsigned char*) "surname",7, (unsigned char*) "foo",3,NULL);
    zm = zipmapSet(zm,(unsigned char*) "age",3, (unsigned char*) "foo",3,NULL);
    zipmapRepr(zm);

    zm = zipmapSet(zm,(unsigned char*) "hello",5, (unsigned char*) "world!",6,NULL);
    zm = zipmapSet(zm,(unsigned char*) "foo",3, (unsigned char*) "bar",3,NULL);
    zm = zipmapSet(zm,(unsigned char*) "foo",3, (unsigned char*) "!",1,NULL);
    zipmapRepr(zm);
    zm = zipmapSet(zm,(unsigned char*) "foo",3, (unsigned char*) "12345",5,NULL);
    zipmapRepr(zm);
    zm = zipmapSet(zm,(unsigned char*) "new",3, (unsigned char*) "xx",2,NULL);
    zm = zipmapSet(zm,(unsigned char*) "noval",5, (unsigned char*) "",0,NULL);
    zipmapRepr(zm);
    zm = zipmapDel(zm,(unsigned char*) "new",3,NULL);
    zipmapRepr(zm);

    printf("\nLook up large key:\n");
    {
        unsigned char buf[512];
        unsigned char *value;
        unsigned int vlen, i;
        for (i = 0; i < 512; i++) buf[i] = 'a';

        zm = zipmapSet(zm,buf,512,(unsigned char*) "long",4,NULL);
        if (zipmapGet(zm,buf,512,&value,&vlen)) {
            printf("  <long key> is associated to the %d bytes value: %.*s\n",
                vlen, vlen, value);
        }
    }

    printf("\nPerform a direct lookup:\n");
    {
        unsigned char *value;
        unsigned int vlen;

        if (zipmapGet(zm,(unsigned char*) "foo",3,&value,&vlen)) {
            printf("  foo is associated to the %d bytes value: %.*s\n",
                vlen, vlen, value);
        }
    }
    printf("\nIterate through elements:\n");
    {
        unsigned char *i = zipmapRewind(zm);
        unsigned char *key, *value;
        unsigned int klen, vlen;

        while((i = zipmapNext(i,&key,&klen,&value,&vlen)) != NULL) {
            printf("  %d:%.*s => %d:%.*s\n", klen, klen, key, vlen, vlen, value);
        }
    }
    return 0;
}
#endif