redis源码解析（十二）压缩链表ziplist内部功能函数分析

矫情吗；* 2021-11-19 11:48 266阅读 0赞

### 1. 前言 ###

压缩链表内部定义了很多功能函数用于实现数据控制和逻辑的分离，同时简化API代码的流程使其更为一目了然，因此本文主要研究内部功能函数以便于更好的分析API函数。

### 2. 源码分析 ###

/* 初始化压缩链表节点zlentry */
    #define ZIPLIST_ENTRY_ZERO(zle) { \ (zle)->prevrawlensize = (zle)->prevrawlen = 0; \ (zle)->lensize = (zle)->len = (zle)->headersize = 0; \ (zle)->encoding = 0; \ (zle)->p = NULL; \ }
    
    /* 从指针ptr获取encoding并存储至zlentry * Extract the encoding from the byte pointed by 'ptr' and set it into * 'encoding' field of the zlentry structure. */
    #define ZIP_ENTRY_ENCODING(ptr, encoding) do { \ (encoding) = (ptr[0]); \ if ((encoding) < ZIP_STR_MASK) (encoding) &= ZIP_STR_MASK; \ } while(0)
    
    /* 根据encoding返回压缩链表的整型大小 * Return bytes needed to store integer encoded by 'encoding'. */
    unsigned int zipIntSize(unsigned char encoding) { 
        switch(encoding) { 
        case ZIP_INT_8B:  return 1;
        case ZIP_INT_16B: return 2;
        case ZIP_INT_24B: return 3;
        case ZIP_INT_32B: return 4;
        case ZIP_INT_64B: return 8;
        }
        if (encoding >= ZIP_INT_IMM_MIN && encoding <= ZIP_INT_IMM_MAX)
            return 0; /* 4 bit immediate */
        panic("Invalid integer encoding 0x%02X", encoding);
        return 0;
    }
    
    /* 将编码头部存入指针P位置 * Write the encoidng header of the entry in 'p'. If p is NULL it just returns * the amount of bytes required to encode such a length. Arguments: * * 'encoding' is the encoding we are using for the entry. It could be * ZIP_INT_* or ZIP_STR_* or between ZIP_INT_IMM_MIN and ZIP_INT_IMM_MAX * for single-byte small immediate integers. * * 'rawlen' is only used for ZIP_STR_* encodings and is the length of the * srting that this entry represents. * * The function returns the number of bytes used by the encoding/length * header stored in 'p'. */
    unsigned int zipStoreEntryEncoding(unsigned char *p, unsigned char encoding, unsigned int rawlen) 
    { 
        unsigned char len = 1, buf[5];
    
        if (ZIP_IS_STR(encoding)) { 
            /* 根据rawlen判断类型 * Although encoding is given it may not be set for strings, * so we determine it here using the raw length. */
            if (rawlen <= 0x3f) { 
                if (!p) return len;
                buf[0] = ZIP_STR_06B | rawlen;
            } else if (rawlen <= 0x3fff) { 
                len += 1;
                if (!p) return len;
                buf[0] = ZIP_STR_14B | ((rawlen >> 8) & 0x3f);
                buf[1] = rawlen & 0xff;
            } else { 
                len += 4;
                if (!p) return len;
                buf[0] = ZIP_STR_32B;
                buf[1] = (rawlen >> 24) & 0xff;
                buf[2] = (rawlen >> 16) & 0xff;
                buf[3] = (rawlen >> 8) & 0xff;
                buf[4] = rawlen & 0xff;
            }
        } else { 
            /* Implies integer encoding, so length is always 1. */
            if (!p) return len;
            buf[0] = encoding;
        }
    
        /* Store this length at p. */
        memcpy(p, buf, len);
        return len;
    }
    
    /* 对encooding进行解码，返回ptr编码的长度/字节数 * Decode the entry encoding type and data length (string length for strings, * number of bytes used for the integer for integer entries) encoded in 'ptr'. * The 'encoding' variable will hold the entry encoding, the 'lensize' * variable will hold the number of bytes required to encode the entry * length, and the 'len' variable will hold the entry length. */
    #define ZIP_DECODE_LENGTH(ptr, encoding, lensize, len) do 
    {                     														   \
        ZIP_ENTRY_ENCODING((ptr), (encoding));                                     \
        if ((encoding) < ZIP_STR_MASK) {                                            \
            if ((encoding) == ZIP_STR_06B) {                                        \
                (lensize) = 1;                                                     \
                (len) = (ptr)[0] & 0x3f;                                           \
            } else if ((encoding) == ZIP_STR_14B) {                                 \
                (lensize) = 2;                                                     \
                (len) = (((ptr)[0] & 0x3f) << 8) | (ptr)[1];                       \
            } else if ((encoding) == ZIP_STR_32B) {                                 \
                (lensize) = 5;                                                     \
                (len) = ((ptr)[1] << 24) |                                         \
                        ((ptr)[2] << 16) |                                         \
                        ((ptr)[3] <<  8) |                                         \
                        ((ptr)[4]);                                                \
            } else {                                                                \
                panic("Invalid string encoding 0x%02X", (encoding));               \
            }                                                                      \
        } else {                                                                    \
            (lensize) = 1;                                                         \
            (len) = zipIntSize(encoding);                                          \
        }                                                                          \
    } while(0);
    
    /* 对上一个entry的长度进行编码，写入p指针（仅对大型编码使用） * Encode the length of the previous entry and write it to "p". This only * uses the larger encoding (required in __ziplistCascadeUpdate). */
    int zipStorePrevEntryLengthLarge(unsigned char *p, unsigned int len) 
    { 
        if (p != NULL) { 
            p[0] = ZIP_BIG_PREVLEN;
            memcpy(p + 1, &len, sizeof(len));
            memrev32ifbe(p + 1);
        }
        return 1 + sizeof(len);
    }
    
    /* 对上一个entry的长度进行编码，写入p指针 * Encode the length of the previous entry and write it to "p". Return the * number of bytes needed to encode this length if "p" is NULL. */
    unsigned int zipStorePrevEntryLength(unsigned char *p, unsigned int len) 
    { 
        if (p == NULL) { 
            return (len < ZIP_BIG_PREVLEN) ? 1 : sizeof(len) + 1;
        } else { 
            if (len < ZIP_BIG_PREVLEN) { 
                p[0] = len;
                return 1;
            } else { 
                return zipStorePrevEntryLengthLarge(p, len);
            }
        }
    }
    
    /* 返回上一节点编码的字节数 * Return the number of bytes used to encode the length of the previous * entry. The length is returned by setting the var 'prevlensize'. */
    #define ZIP_DECODE_PREVLENSIZE(ptr, prevlensize) do { \ if ((ptr)[0] < ZIP_BIG_PREVLEN) { \ (prevlensize) = 1; \ } else { \ (prevlensize) = 5; \ } \ } while(0);
    
    /* 返回上一个元素的长度prevlen和编码的字节数prevlensize * Return the length of the previous element, and the number of bytes that * are used in order to encode the previous element length. * 'ptr' must point to the prevlen prefix of an entry (that encodes the * length of the previos entry in order to navigate the elements backward). * The length of the previous entry is stored in 'prevlen', the number of * bytes needed to encode the previous entry length are stored in * 'prevlensize'. */
    #define ZIP_DECODE_PREVLEN(ptr, prevlensize, prevlen) do { \ ZIP_DECODE_PREVLENSIZE(ptr, prevlensize); \ if ((prevlensize) == 1) { \ (prevlen) = (ptr)[0]; \ } else if ((prevlensize) == 5) { \ assert(sizeof((prevlen)) == 4); \ memcpy(&(prevlen), ((char*)(ptr)) + 1, 4); \ memrev32ifbe(&prevlen); \ } \ } while(0);
    
    /* 根据指向prevlen的指针p获取prevlensize和len的差值 * Given a pointer 'p' to the prevlen info that prefixes an entry, this * function returns the difference in number of bytes needed to encode * the prevlen if the previous entry changes of size. * * So if A is the number of bytes used right now to encode the 'prevlen' * field. * * And B is the number of bytes that are needed in order to encode the * 'prevlen' if the previous element will be updated to one of size 'len'. * * Then the function returns B - A * * So the function returns a positive number if more space is needed, * a negative number if less space is needed, or zero if the same space * is needed. */
    int zipPrevLenByteDiff(unsigned char *p, unsigned int len) { 
        unsigned int prevlensize;
        ZIP_DECODE_PREVLENSIZE(p, prevlensize);
        return zipStorePrevEntryLength(NULL, len) - prevlensize;
    }
    
    /* 返回节点总字节数 * Return the total number of bytes used by the entry pointed to by 'p'. */
    unsigned int zipRawEntryLength(unsigned char *p) { 
        unsigned int prevlensize, encoding, lensize, len;
        ZIP_DECODE_PREVLENSIZE(p, prevlensize);
        ZIP_DECODE_LENGTH(p + prevlensize, encoding, lensize, len);
        return prevlensize + lensize + len;
    }
    
    /* 检查是否可以编码为整数 * Check if string pointed to by 'entry' can be encoded as an integer. * Stores the integer value in 'v' and its encoding in 'encoding'. */
    int zipTryEncoding(unsigned char *entry, unsigned int entrylen, long long *v, unsigned char *encoding) { 
        long long value;
    
        if (entrylen >= 32 || entrylen == 0) return 0;
        if (string2ll((char*)entry, entrylen, &value)) { 
            /* Great, the string can be encoded. Check what's the smallest * of our encoding types that can hold this value. */
            if (value >= 0 && value <= 12) { 
                *encoding = ZIP_INT_IMM_MIN+value;
            } else if (value >= INT8_MIN && value <= INT8_MAX) { 
                *encoding = ZIP_INT_8B;
            } else if (value >= INT16_MIN && value <= INT16_MAX) { 
                *encoding = ZIP_INT_16B;
            } else if (value >= INT24_MIN && value <= INT24_MAX) { 
                *encoding = ZIP_INT_24B;
            } else if (value >= INT32_MIN && value <= INT32_MAX) { 
                *encoding = ZIP_INT_32B;
            } else { 
                *encoding = ZIP_INT_64B;
            }
            *v = value;
            return 1;
        }
        return 0;
    }
    
    /* 将整数保存在p中并编码 * Store integer 'value' at 'p', encoded as 'encoding' */
    void zipSaveInteger(unsigned char *p, int64_t value, unsigned char encoding) { 
        int16_t i16;
        int32_t i32;
        int64_t i64;
        if (encoding == ZIP_INT_8B) { 
            ((int8_t*)p)[0] = (int8_t)value;
        } else if (encoding == ZIP_INT_16B) { 
            i16 = value;
            memcpy(p, &i16, sizeof(i16));
            memrev16ifbe(p);
        } else if (encoding == ZIP_INT_24B) { 
            i32 = value<<8;
            memrev32ifbe(&i32);
            memcpy(p, ((uint8_t*)&i32)+1, sizeof(i32)-sizeof(uint8_t));
        } else if (encoding == ZIP_INT_32B) { 
            i32 = value;
            memcpy(p, &i32, sizeof(i32));
            memrev32ifbe(p);
        } else if (encoding == ZIP_INT_64B) { 
            i64 = value;
            memcpy(p, &i64, sizeof(i64));
            memrev64ifbe(p);
        } else if (encoding >= ZIP_INT_IMM_MIN && encoding <= ZIP_INT_IMM_MAX) { 
            /* Nothing to do, the value is stored in the encoding itself. */
        } else { 
            assert(NULL);
        }
    }
    
    /* 从p中读取整形，编码类型为encoding * Read integer encoded as 'encoding' from 'p' */
    int64_t zipLoadInteger(unsigned char *p, unsigned char encoding) { 
        int16_t i16;
        int32_t i32;
        int64_t i64, ret = 0;
        if (encoding == ZIP_INT_8B) { 
            ret = ((int8_t*)p)[0];
        } else if (encoding == ZIP_INT_16B) { 
            memcpy(&i16, p, sizeof(i16));
            memrev16ifbe(&i16);
            ret = i16;
        } else if (encoding == ZIP_INT_32B) { 
            memcpy(&i32, p, sizeof(i32));
            memrev32ifbe(&i32);
            ret = i32;
        } else if (encoding == ZIP_INT_24B) { 
            i32 = 0;
            memcpy(((uint8_t*)&i32) + 1, p, sizeof(i32) - sizeof(uint8_t));
            memrev32ifbe(&i32);
            ret = i32>>8;
        } else if (encoding == ZIP_INT_64B) { 
            memcpy(&i64, p, sizeof(i64));
            memrev64ifbe(&i64);
            ret = i64;
        } else if (encoding >= ZIP_INT_IMM_MIN && encoding <= ZIP_INT_IMM_MAX) { 
            ret = (encoding & ZIP_INT_IMM_MASK)-1;
        } else { 
            assert(NULL);
        }
        return ret;
    }
    
    /* 返回entry相关的所有结构体 * Return a struct with all information about an entry. */
    void zipEntry(unsigned char *p, zlentry *e) { 
    
        ZIP_DECODE_PREVLEN(p, e->prevrawlensize, e->prevrawlen);
        ZIP_DECODE_LENGTH(p + e->prevrawlensize, e->encoding, e->lensize, e->len);
        e->headersize = e->prevrawlensize + e->lensize;
        e->p = p;
    }