redis源码阅读之ziplist

前文提到了一个adlist，它的注释是这样写的“A generic doubly linked list implementation”，这次要说的ziplist，它的注释是这样写的

点击(此处)折叠或打开

1. /* The ziplist is a specially encoded dually linked list that is designed
   
2.  * to be very memory efficient. It stores both strings and integer values,
   
3.  * where integers are encoded as actual integers instead of a series of
   
4.  * characters. It allows push and pop operations on either side of the list
   
5.  * in O(1) time. However, because every operation requires a reallocation of
   
6.  * the memory used by the ziplist, the actual complexity is related to the
   
7.  * amount of memory used by the ziplist.*/

ziplist本身并不会像adlist那样能够存储多种数据，而是存储string和integer values，就像上面的注释一样"encoded dually linked list"。但是其能够更加有效的利用内存空间，如何利用的呢，就让我们一探究竟。注意：如果没有特殊声明，所有字段均按照little endian存储。
首先，和adlist一样会用宏定义头和尾

点击(此处)折叠或打开

1. #define ZIPLIST_HEAD 0
   
2. #define ZIPLIST_TAIL 1

其在内存当中的整体结构如下所示

点击(此处)折叠或打开

1. <zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>

其中各个字段的描述如下

名称	描述
zlbytes(uint32_t)	整个链表所占的字节数
zltail(uint32_t)	到链表当中最后一个元素的偏移量，便于pop操作
zllen(uint16_t)	entry个数，当元素个数超过2-2时，这个值就被赋值为2-1，这个时候，如果想知道实际有多少个entry的话，就需要自己遍历整个链表了
zlend(uint8_t)	表示链表尾部，被设置为255

链表中的entry在内存当中的表示如下：

点击(此处)折叠或打开

1. <prevlen> <encoding> <entry-data>

其中各个字段的描述如下：

名称	描述
prevlen	前一个entry的长度（便于从后向前遍历）。如果长度小于254，则只占1个字节，如果大于254，则占用5个字节，其中第一个字节为254，后面4个字节表示实际长度。
encoding	表明entry type。integer或者string。如果是小整数，有时会省略掉entry-data部分，由encoding直接表示数据，当entry-data为string时，encoding的第一个字节的前2bits用来保存整个字符串长度的encoding type，后面紧接着就是实际的长度：当entry-data时一个integer，第一个字节的前2bits均被置为1，借着它的2位用来表示integer的种类

encoding字段具体表示如下：

encoding字节表示	说明
00pppppp(1 byte)	string value with length less than or equal to 63 bytes
01pppppp|qqqqqqqq(2 bytes)	string value with length less than or equal to 16383 bytes. The 14 bit number is stored in big endian
10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt(5 bytes)	string balue with length greater or equal to 16384 bytes. Only the 4 bytes following the first byte represents the length up to 32-1. The 32 bit number is stored in big endian.
11000000| - 3 bytes total	integer encoded as int16_t(2 bytes)
11010000| - 5 bytes total	integer encoded as int32_t(4 bytes)
11100000| - 9 bytes total	integer encoded as int64_t(8 bytes)
11110000| - 4 bytes total	integer encoded as 24 bit signed(3 bytes)
11111110| - 2 bytes total	integer encoded as 8 bit signed(1 byte)
1111xxxx| - with xxxx between 0000 and 1101	immediate 4 bit integer. unsigned integer from 0 to 12. The encoded value is actually from 1 to 13 because 0000 and 1111 can not be used, so 1 should be subtracted from the encoded 4 bit value to obtain the right value.
11111111	End of ziplist special entry

它是通过定义一些mask来实现上述的各种判断，如下

点击(此处)折叠或打开

1. #define ZIP_END 255 /* Special "end of ziplist" entry. */
   
2. #define ZIP_BIG_PREVLEN 254 /* Max number of bytes of the previous entry*/
   
3. /* Different encoding/length possibilities */
   
4. #define ZIP_STR_MASK 0xc0
   
5. #define ZIP_INT_MASK 0x30
   
6. #define ZIP_STR_06B (0 << 6)
   
7. #define ZIP_STR_14B (1 << 6)
   
8. #define ZIP_STR_32B (2 << 6)
   
9. #define ZIP_INT_16B (0xc0 | 0<<4)
   
10. #define ZIP_INT_32B (0xc0 | 1<<4)
    
11. #define ZIP_INT_64B (0xc0 | 2<<4)
    
12. #define ZIP_INT_24B (0xc0 | 3<<4)
    
13. #define ZIP_INT_8B 0xfe
    
14. 
    
15. /* 4 bit integer immediate encoding |1111xxxx| with xxxx between
    
16.  * 0001 and 1101. */
    
17. #define ZIP_INT_IMM_MASK 0x0f /* Mask to extract the 4 bits value. To add
    
18.                                    one is needed to reconstruct the value. */
    
19. #define ZIP_INT_IMM_MIN 0xf1 /* 11110001 */
    
20. #define ZIP_INT_IMM_MAX 0xfd /* 11111101 */
    
21. 
    
22. #define INT24_MAX 0x7fffff
    
23. #define INT24_MIN (-INT24_MAX - 1)

entry的话是通过下面的结构体来进行读取的，实际上在内存当中并不是按照结构体存储的，这点要记住，可以偷偷的记录在小本本上面~

点击(此处)折叠或打开

1. typedef struct zlentry {
   
2.     unsigned int prevrawlensize; /* Bytes used to encode the previos entry len*/
   
3.     unsigned int prevrawlen; /* Previous entry len. */
   
4.     unsigned int lensize; /* Bytes used to encode this entry type/len.
   
5.                                     For example strings have a 1, 2 or 5 bytes
   
6.                                     header. Integers always use a single byte.*/
   
7.     unsigned int len; /* Bytes used to represent the actual entry.
   
8.                                     For strings this is just the string length
   
9.                                     while for integers it is 1, 2, 3, 4, 8 or
   
10.                                     0 (for 4 bit immediate) depending on the
    
11.                                     number range. */
    
12.     unsigned int headersize; /* prevrawlensize + lensize. */
    
13.     unsigned char encoding; /* Set to ZIP_STR_* or ZIP_INT_* depending on
    
14.                                     the entry encoding. However for 4 bits
    
15.                                     immediate integers this can assume a range
    
16.                                     of values and must be range-checked. */
    
17.     unsigned char *p; /* Pointer to the very start of the entry, that
    
18.                                     is, this points to prev-entry-len field. */
    
19. } zlentry;

之后的话就是一些聊表的常规操作了，这里不再赘述了~~~