Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1837879
  • 博文数量: 184
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 2388
  • 用 户 组: 普通用户
  • 注册时间: 2016-12-21 22:26
个人简介

90后空巢老码农

文章分类

全部博文(184)

文章存档

2021年(26)

2020年(56)

2019年(54)

2018年(47)

2017年(1)

我的朋友

分类: NOSQL

2019-01-26 23:37:01

前文提到了一个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个数,当元素个数超过216-2时,这个值就被赋值为216-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 322-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. /* 4 bit integer immediate encoding |1111xxxx| with xxxx between
  15.  * 0001 and 1101. */
  16. #define ZIP_INT_IMM_MASK 0x0f /* Mask to extract the 4 bits value. To add
  17.                                    one is needed to reconstruct the value. */
  18. #define ZIP_INT_IMM_MIN 0xf1 /* 11110001 */
  19. #define ZIP_INT_IMM_MAX 0xfd /* 11111101 */

  20. #define INT24_MAX 0x7fffff
  21. #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;
之后的话就是一些聊表的常规操作了,这里不再赘述了~~~
阅读(9433) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~