ThinkChat🤖让你学习和工作更高效,注册即送10W Token,即刻开启你的AI之旅 广告
每个压缩列表节点可以保存一个字节数组或者一个整数值, 其中, 字节数组可以是以下三种长度的其中一种: 1. 长度小于等于 `63` (![2^{6}-1](https://box.kancloud.cn/2015-09-13_55f51c2987686.png))字节的字节数组; 2. 长度小于等于 `16383` (![2^{14}-1](https://box.kancloud.cn/2015-09-13_55f51c30b8762.png)) 字节的字节数组; 3. 长度小于等于 `4294967295` (![2^{32}-1](https://box.kancloud.cn/2015-09-13_55f51c3202274.png))字节的字节数组; 而整数值则可以是以下六种长度的其中一种: 1. `4` 位长,介于 `0` 至 `12` 之间的无符号整数; 2. `1` 字节长的有符号整数; 3. `3` 字节长的有符号整数; 4. `int16_t` 类型整数; 5. `int32_t` 类型整数; 6. `int64_t` 类型整数。 每个压缩列表节点都由 `previous_entry_length` 、 `encoding` 、 `content` 三个部分组成, 如图 7-4 所示。 ![](https://box.kancloud.cn/2015-09-13_55f51c330140d.png) 接下来的内容将分别介绍这三个组成部分。 ## previous_entry_length 节点的 `previous_entry_length` 属性以字节为单位, 记录了压缩列表中前一个节点的长度。 `previous_entry_length` 属性的长度可以是 `1` 字节或者 `5` 字节: * 如果前一节点的长度小于 `254` 字节, 那么 `previous_entry_length` 属性的长度为 `1` 字节: 前一节点的长度就保存在这一个字节里面。 * 如果前一节点的长度大于等于 `254` 字节, 那么 `previous_entry_length` 属性的长度为 `5` 字节: 其中属性的第一字节会被设置为 `0xFE`(十进制值 `254`), 而之后的四个字节则用于保存前一节点的长度。 图 7-5 展示了一个包含一字节长 `previous_entry_length` 属性的压缩列表节点, 属性的值为 `0x05` , 表示前一节点的长度为 `5` 字节。 ![](https://box.kancloud.cn/2015-09-13_55f51c341e72d.png) 图 7-6 展示了一个包含五字节长 `previous_entry_length` 属性的压缩节点, 属性的值为 `0xFE00002766` , 其中值的最高位字节 `0xFE` 表示这是一个五字节长的 `previous_entry_length` 属性, 而之后的四字节 `0x00002766` (十进制值 `10086` )才是前一节点的实际长度。 ![](https://box.kancloud.cn/2015-09-13_55f51c358c906.png) 因为节点的 `previous_entry_length` 属性记录了前一个节点的长度, 所以程序可以通过指针运算, 根据当前节点的起始地址来计算出前一个节点的起始地址。 举个例子, 如果我们有一个指向当前节点起始地址的指针 `c` , 那么我们只要用指针 `c` 减去当前节点 `previous_entry_length` 属性的值, 就可以得出一个指向前一个节点起始地址的指针 `p` , 如图 7-7 所示。 ![](https://box.kancloud.cn/2015-09-13_55f51c36a9d1e.png) 压缩列表的从表尾向表头遍历操作就是使用这一原理实现的: 只要我们拥有了一个指向某个节点起始地址的指针, 那么通过这个指针以及这个节点的 `previous_entry_length` 属性, 程序就可以一直向前一个节点回溯, 最终到达压缩列表的表头节点。 图 7-8 展示了一个从表尾节点向表头节点进行遍历的完整过程: * 首先,我们拥有指向压缩列表表尾节点 `entry4` 起始地址的指针 `p1` (指向表尾节点的指针可以通过指向压缩列表起始地址的指针加上`zltail` 属性的值得出); * 通过用 `p1` 减去 `entry4` 节点 `previous_entry_length` 属性的值, 我们得到一个指向 `entry4` 前一节点 `entry3` 起始地址的指针 `p2` ; * 通过用 `p2` 减去 `entry3` 节点 `previous_entry_length` 属性的值, 我们得到一个指向 `entry3` 前一节点 `entry2` 起始地址的指针 `p3` ; * 通过用 `p3` 减去 `entry2` 节点 `previous_entry_length` 属性的值, 我们得到一个指向 `entry2` 前一节点 `entry1` 起始地址的指针 `p4` , `entry1`为压缩列表的表头节点; * 最终, 我们从表尾节点向表头节点遍历了整个列表。 ![](https://box.kancloud.cn/2015-09-13_55f51c38519f1.png) ![](https://box.kancloud.cn/2015-09-13_55f51c3971a7c.png) ![](https://box.kancloud.cn/2015-09-13_55f51c3f8bb1c.png) ![](https://box.kancloud.cn/2015-09-13_55f51c40b5c7f.png) ## encoding 节点的 `encoding` 属性记录了节点的 `content` 属性所保存数据的类型以及长度: * 一字节、两字节或者五字节长, 值的最高位为 `00` 、 `01` 或者 `10` 的是字节数组编码: 这种编码表示节点的 `content` 属性保存着字节数组, 数组的长度由编码除去最高两位之后的其他位记录; * 一字节长, 值的最高位以 `11` 开头的是整数编码: 这种编码表示节点的 `content` 属性保存着整数值, 整数值的类型和长度由编码除去最高两位之后的其他位记录; 表 7-2 记录了所有可用的字节数组编码, 而表 7-3 则记录了所有可用的整数编码。 表格中的下划线 `_` 表示留空, 而 `b` 、 `x` 等变量则代表实际的二进制数据, 为了方便阅读, 多个字节之间用空格隔开。 * * * 表 7-2 字节数组编码 | 编码 | 编码长度 | `content` 属性保存的值 | | --- | --- | --- | | `00bbbbbb` | `1` 字节 | 长度小于等于 `63` 字节的字节数组。 | | `01bbbbbb xxxxxxxx` | `2` 字节 | 长度小于等于 `16383` 字节的字节数组。 | | `10______ aaaaaaaa bbbbbbbb cccccccc dddddddd` | `5` 字节 | 长度小于等于 `4294967295` 的字节数组。 | 表 7-3 整数编码 | 编码 | 编码长度 | `content` 属性保存的值 | | --- | --- | --- | | `11000000` | `1` 字节 | `int16_t` 类型的整数。 | | `11010000` | `1` 字节 | `int32_t` 类型的整数。 | | `11100000` | `1` 字节 | `int64_t` 类型的整数。 | | `11110000` | `1` 字节 | `24` 位有符号整数。 | | `11111110` | `1` 字节 | `8` 位有符号整数。 | | `1111xxxx` | `1` 字节 | 使用这一编码的节点没有相应的 `content` 属性, 因为编码本身的 `xxxx` 四个位已经保存了一个介于 `0` 和`12` 之间的值, 所以它无须 `content` 属性。 | * * * ## content 节点的 `content` 属性负责保存节点的值, 节点值可以是一个字节数组或者整数, 值的类型和长度由节点的 `encoding` 属性决定。 图 7-9 展示了一个保存字节数组的节点示例: * 编码的最高两位 `00` 表示节点保存的是一个字节数组; * 编码的后六位 `001011` 记录了字节数组的长度 `11` ; * `content` 属性保存着节点的值 `"hello world"` 。 ![](https://box.kancloud.cn/2015-09-13_55f51c4228d21.png) 图 7-10 展示了一个保存整数值的节点示例: * 编码 `11000000` 表示节点保存的是一个 `int16_t` 类型的整数值; * `content` 属性保存着节点的值 `10086` 。 ![](https://box.kancloud.cn/2015-09-13_55f51c4312fbc.png)