Redis源码阅读--1.基础数据结构与对象

struct sdshdr {
    // 记录 buf 数组中已使用字节的数量，等于 SDS 所保存字符串的长度
    int len;

    // 记录 buf 数组中未使用字节的数量
    int free;

    // 字节数组，用于保存字符串
    char buf[];
};

// Note: sdshdr5 is never used, we just access the flags byte directly.
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 前 3 位表示类型, 后 5 为表示长度 */
    char buf[];
};

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len;                // 已使用长度 1字节
    uint8_t alloc;              // 总长度 1字节
    unsigned char flags;        // 前 3 位表示存储类型，后 5 位 预留
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len;               // 已使用长度 2字节
    uint16_t alloc;             // 总长度 2字节
    unsigned char flags;        // 前 3 位表示存储类型，后 5 位 预留
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len;               // 已使用长度 4字节
    uint32_t alloc;             // 总长度 4字节
    unsigned char flags;        // 前 3 位表示存储类型，后 5 位 预留
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len;               // 已使用长度 8字节
    uint64_t alloc;             // 总长度 8字节
    unsigned char flags;        // 前 3 位表示存储类型，后 5 位 预留
    char buf[];
};

/* Create a new sds string starting from a null terminated C string. */
sds sdsnew(const char *init) {
    size_t initlen = (init == NULL) ? 0 : strlen(init);  // 拿到要创建的字符串的长度
    return sdsnewlen(init, initlen);  // 传入字符串、字符串长度，调用 sdsnewlen 动态分配内存
}
sds sdsnewlen(const void *init, size_t initlen) {
    void *sh;
    sds s;
    char type = sdsReqType(initlen);  // 根据字符串长度得到合适的类型
    // 一般情况下，创建一个空字符串的目的都是为了后面的append操作，因此，空字符串的情况下，直接创建SDS_TYPE_8，减少后面的扩容操作
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
    // 计算类型对应的结构体头部长度(len alloc flags的长度)
    int hdrlen = sdsHdrSize(type);
    // 指向flag的指针
    unsigned char *fp;

    // 申请内存，内存大小为 结构体头部长度+字符串长度(buf)+1，这里+1是因为要考虑 '\0' 字符
    sh = s_malloc(hdrlen+initlen+1);
    if (sh == NULL) return NULL;
    if (init==SDS_NOINIT)
        init = NULL;
    else if (!init)
        memset(sh, 0, hdrlen+initlen+1);
    // 将s指向buf
    s = (char*)sh+hdrlen;
    // 将 s-1 指向flag
    fp = ((unsigned char*)s)-1;
    // 对sds结构体变量进行赋值
    switch(type) {
        case SDS_TYPE_5: {
            *fp = type | (initlen << SDS_TYPE_BITS);
            break;
        }
        case SDS_TYPE_8: {
            SDS_HDR_VAR(8,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        ...
    }
    if (initlen && init)
        memcpy(s, init, initlen);
    // 在s的最后添加'\0'
    s[initlen] = '\0';
    // 返回指向 buf 数组的指针s
    return s;
}

/* Free an sds string. No operation is performed if 's' is NULL. */
void sdsfree(sds s) {
    if (s == NULL) return;
    s_free((char*)s-sdsHdrSize(s[-1]));
}

/* Modify an sds string in-place to make it empty (zero length).
 * However all the existing buffer is not discarded but set as free space
 * so that next append operations will not require allocations up to the
 * number of bytes previously available. */
void sdsclear(sds s) {
    sdssetlen(s, 0);
    s[0] = '\0';
}

// 将 t 拼接到 s 后面。调用此方法之后，sds底层的buf可能经过了扩容迁移了原来的位置，注意更新原来变量中对应的指针
sds sdscatsds(sds s, const sds t) {
    return sdscatlen(s, t, sdslen(t));
}

sds sdscatlen(sds s, const void *t, size_t len) {
    size_t curlen = sdslen(s);  // 计算当前s的长度

    s = sdsMakeRoomFor(s,len);  // 空间不够的话扩容，确保s的剩余空间足够放得下t
    if (s == NULL) return NULL; // 扩容失败
    memcpy(s+curlen, t, len);   // 拼接
    sdssetlen(s, curlen+len);   // 更新s的属性len
    s[curlen+len] = '\0';       // 给s最后加上 '\0'
    return s;
}

// 将sds s的 buf 的可用空间扩大，使得调用此函数之后的s能够再多存储 addlen 长度的字符串。
// 注意：此方法并未改变 sds 的len属性，仅仅改变的是 sds 的 buf 数组的空间。
sds sdsMakeRoomFor(sds s, size_t addlen) {
    void *sh, *newsh;
    size_t avail = sdsavail(s);  // 当前的可用空间长度：s.alloc - s.len
    size_t len, newlen;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen;

    // 情况1：剩余长度大于所需要长度，没必要扩容，直接返回
    if (avail >= addlen) return s;

    len = sdslen(s);     	// 当前字符串长度
    sh = (char*)s-sdsHdrSize(oldtype);
    newlen = (len+addlen);    // 新字符串长度

    // 情况2：扩容
    // 情况2.1： 如果 新长度 < 1MB，则按 新长度的2倍 扩容
    //    		否则，就按 新长度+1MB 扩容
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;

    // 计算新长度的类型
    type = sdsReqType(newlen);

    // 还是为了后续使用减少扩容次数的原因，将 sdshdr5 变为 sdshdr8
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;

    hdrlen = sdsHdrSize(type);
    if (oldtype==type) {
        // 如果新长度对应的类型没变，则直接调用 s_realloc 扩大动态数组即可
        newsh = s_realloc(sh, hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+hdrlen;
    } else {
        /* Since the header size changes, need to move the string forward,
         * and can't use realloc */
        // 类型发生了改变，意味着sds结构体头部的三个属性的类型也要跟着变化，此时直接重新申请一块内存
        newsh = s_malloc(hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        // 原s的数据拷贝到新的内存上
        memcpy((char*)newsh+hdrlen, s, len+1);
        // 释放掉原来的s的空间，并将其更新为刚才新申请的
        s_free(sh);
        s = (char*)newsh+hdrlen;
        // 更新 flag
        s[-1] = type;
        // 更新 len
        sdssetlen(s, len);
    }
    // 更新 alloc
    sdssetalloc(s, newlen);
    return s;
}

typedef struct listNode {
    struct listNode *prev;  // 头指针
    struct listNode *next;  // 尾指针
    void *value;    		// 具体的值，因为值的类型不确定，此处使用万能指针
} listNode;

// 创建的只是一个 list 对象，这个对象可以被 AlFreeList() 释放掉，但是仅仅释放的是这个 list 对象，其上面的 listNode 对象还需要另外手动释放
list *listCreate(void)
{
    struct list *list;

    // 申请分配内存，失败返回 NULL
    if ((list = zmalloc(sizeof(*list))) == NULL)
        return NULL;
    // 给其他属性赋值
    list->head = list->tail = NULL;
    list->len = 0;
    list->dup = NULL;
    list->free = NULL;
    list->match = NULL;
    // 最终返回 list 对象
    return list;
}

list *listAddNodeHead(list *list, void *value)
{
    listNode *node;
	// 申请分配内存，失败返回 NULL
    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    node->value = value;

    // 将 listNode 插入到 list 的元素中
    if (list->len == 0) {
        // 如果之前 list 没有元素，那么 list 的 head 和 tail 均指向当前的 listNode
        list->head = list->tail = node;
        node->prev = node->next = NULL;
    } else {
        // 链表的头插入
        node->prev = NULL;
        node->next = list->head;
        list->head->prev = node;
        list->head = node;
    }
    // 更新 len
    list->len++;

    // 返回的是传进来的 list ，失败返回的是 NULL
    return list;
}

// 尾插入，过程和头插入类似
list *listAddNodeTail(list *list, void *value)
{
    listNode *node;

    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    node->value = value;
    if (list->len == 0) {
        list->head = list->tail = node;
        node->prev = node->next = NULL;
    } else {
        node->prev = list->tail;
        node->next = NULL;
        list->tail->next = node;
        list->tail = node;
    }
    list->len++;
    return list;
}

// 在 list 的 old_node 的前或后(after<0,在前面增加；after>0，在后面增加)新增值为 value 的新listNode
list *listInsertNode(list *list, listNode *old_node, void *value, int after) {
    listNode *node;

    // 为新增的 listNode 申请内存，失败返回 NULL
    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    node->value = value;

    if (after) {
        // after>0，在后面插入
        node->prev = old_node;
        node->next = old_node->next;
        if (list->tail == old_node) {
            list->tail = node;
        }
    } else {
        // after<0，在前面插入
        node->next = old_node;
        node->prev = old_node->prev;
        if (list->head == old_node) {
            list->head = node;
        }
    }
    if (node->prev != NULL) {
        node->prev->next = node;
    }
    if (node->next != NULL) {
        node->next->prev = node;
    }
    // 更新 len
    list->len++;
    // 成功 返回传进来的 list
    return list;
}

/* Remove all the elements from the list without destroying the list itself. */
void listEmpty(list *list)
{
    unsigned long len;
    listNode *current, *next;

    current = list->head;
    len = list->len;
    // 遍历整个链表，逐个释放空间，直到为空
    while(len--) {
        next = current->next;
        if (list->free) list->free(current->value);
        zfree(current);
        current = next;
    }
    list->head = list->tail = NULL;
    list->len = 0;
}

/* Free the whole list.
 *
 * This function can't fail. */
void listRelease(list *list)
{
    listEmpty(list);    // 先清空所有的 listNode
    zfree(list);		// 再释放 list
}

void listDelNode(list *list, listNode *node)
{
    // 是否是 list 中的第一个元素
    if (node->prev)
        node->prev->next = node->next;
    else
        list->head = node->next;
    // 是否是 list 中的最后一个元素
    if (node->next)
        node->next->prev = node->prev;
    else
        list->tail = node->prev;
    // 释放当前节点的值
    if (list->free) list->free(node->value);
    // 释放内存
    zfree(node);
    // 更新 len
    list->len--;
}

redis> set name Jemmy

typedef struct dictEntry {
    // key
    void *key;

    // value，可以是指针 uint64_t int64_t double中的某一个
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;

    // 指向另一个哈希表结点的指针，连接哈希值相同的键值对，用来解决哈希冲突
    struct dictEntry *next;
} dictEntry;

typedef struct dictht {
    dictEntry **table;          // dictEntry数组，dictEntry代表一个键值对
    unsigned long size;         // 哈希表大小(容量)
    unsigned long sizemask;     // 值总是等于 size - 1 ， 这个属性和哈希值一起决定一个键应该被放到 table 数组的哪个索引上面。
    unsigned long used;         // 哈希表已有结点的数量
} dictht;

typedef struct dict {
    dictType *type;  // 类型对应的特定函数
    void *privdata;  // 私有数据
    dictht ht[2];    // 两个哈希表，一个正常使用，另一个用于扩容
    long rehashidx;  // rehash 索引值，扩容时使用，正常时为-1
    unsigned long iterators; // 正在运行的迭代器的数量
} dict;

typedef struct dictType {
    // 计算哈希值的函数
    uint64_t (*hashFunction)(const void *key);
    // 复制键的函数
    void *(*keyDup)(void *privdata, const void *key);
    // 复制值的函数
    void *(*valDup)(void *privdata, const void *obj);
    // 对比键是否相同的函数
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    // 销毁键的函数
    void (*keyDestructor)(void *privdata, void *key);
    // 销毁值的函数
    void (*valDestructor)(void *privdata, void *obj);
} dictType;

/* Add an element to the target hash table */
int dictAdd(dict *d, void *key, void *val)
{
    dictEntry *entry = dictAddRaw(d,key,NULL);  // 将键值对封装成dictEntry

    if (!entry) return DICT_ERR;                // 如果创建dictEntry，返回失败
    dictSetVal(d, entry, val);                  // 键不存在，则设置dictEntry结点的值
    return DICT_OK;
}

// 将 key 插入哈希表中
dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
{
    long index;
    dictEntry *entry;
    dictht *ht;

    // 如果哈希表正在rehash，则向前 rehash一步(渐进式rehash的体现)
    // 是否正在进行 rehash，是通过 dict.rehashidx == -1 来判断的
    if (dictIsRehashing(d)) _dictRehashStep(d);

    // 调用_dictKeyIndex() 检查键是否存在，如果存在则返回NULL
    if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)
        return NULL;

    // 获取当前正在使用的ht，如果正在 rehash，使用 ht[1]，否则使用 ht[0]
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
    // 为新增的节点分配内存
    entry = zmalloc(sizeof(*entry));
    // 将结点插入链表头部
    entry->next = ht->table[index];
    ht->table[index] = entry;
    // 更新结点数量
    ht->used++;

    // 设置新节点的键，使用的是 type 属性中的 keyDup 函数
    dictSetKey(d, entry, key);
    return entry;
}

// 传进来的 existing 是 NULL, hash是通过 type 中的哈希函数计算的
static long _dictKeyIndex(dict *d, const void *key, uint64_t hash, dictEntry **existing)
{
    unsigned long idx, table;
    dictEntry *he;
    if (existing)
        *existing = NULL;

    // 检查是否需要扩展哈希表，如果需要则进行扩展
    if (_dictExpandIfNeeded(d) == DICT_ERR)
        return -1;

    for (table = 0; table <= 1; table++)
    {
        idx = hash & d->ht[table].sizemask;
        /* Search if this slot does not already contain the given key */
        he = d->ht[table].table[idx];
        while (he)
        {
            if (key == he->key || dictCompareKeys(d, key, he->key))
            {
                if (existing)
                    *existing = he;
                return -1;
            }
            he = he->next;
        }
        if (!dictIsRehashing(d))
            break;
    }
    return idx;
}

static int _dictExpandIfNeeded(dict *d)
{
    // 如果正在 rehash，直接返回
    if (dictIsRehashing(d))
        return DICT_OK;

    /* If the hash table is empty expand it to the initial size. */
    // 如果哈希表中是空的，则将其收缩为初始化大小 DICT_HT_INITIAL_SIZE=4
    if (d->ht[0].size == 0)
        return dictExpand(d, DICT_HT_INITIAL_SIZE);

    // 在 (ht[0].used/ht[0].size)>=1前提下，如果 系统允许扩容 或者 ht[0].used/t[0].size>5 时，容量扩展为原来的2倍
    if (d->ht[0].used >= d->ht[0].size &&
        (dict_can_resize ||
         d->ht[0].used / d->ht[0].size > dict_force_resize_ratio))
    {
        return dictExpand(d, d->ht[0].used * 2);  // 扩容至原来容量的2倍
    }
    return DICT_OK;
}

// 扩容 或者 新建一个 dictht
int dictExpand(dict *d, unsigned long size)
{
    /* the size is invalid if it is smaller than the number of
     * elements already inside the hash table */
    // 如果正在 reahsh 或者 传进来的size不合适(size比当前已有的容量小，正常情况下这是不可能的)，直接返回错误
    if (dictIsRehashing(d) || d->ht[0].used > size)
        return DICT_ERR;

    dictht n; // 新哈希表
    // 计算 扩展或缩放新哈希表容量 的大小，必须是2的倍数
    unsigned long realsize = _dictNextPower(size);

    // 如果计算扩容后的新哈希表的容量，和原来的相同，就没必要扩容，直接返回错误
    if (realsize == d->ht[0].size)
        return DICT_ERR;

    // 为新哈希表申请内存，并将所有的指针初始化为NULL
    n.size = realsize;
    n.sizemask = realsize - 1;
    n.table = zcalloc(realsize * sizeof(dictEntry *));
    n.used = 0;

    /* Is this the first initialization? If so it's not really a rehashing
     * we just set the first hash table so that it can accept keys. */
    // 如果原来的哈希表是空的，意味着这是在新建一个哈希表，将新申请的 dictht 赋值给 ht[0]，直接返回创建成功
    if (d->ht[0].table == NULL)
    {
        d->ht[0] = n;
        return DICT_OK;
    }

    // 如果不是新建哈希表，那就是需要实打实的扩容，此时将刚才新申请的 哈希表 赋值给 ht[1]，并将当前字典状态设置为"正在rehash"(rehashidx > -1)
    d->ht[1] = n;
    d->rehashidx = 0;
    return DICT_OK;
}

// 哈希表的容量必须是 2的倍数
static unsigned long _dictNextPower(unsigned long size)
{
    unsigned long i = DICT_HT_INITIAL_SIZE;

    if (size >= LONG_MAX)
        return LONG_MAX + 1LU;
    while (1)
    {
        if (i >= size)
            return i;
        i *= 2;
    }
}

// _dictRehashStep 让 rehash 的动作向前走一步(搬迁一个桶)，前提是当前字典没有被遍历，即iterators==0，iterators表示当前正在遍历此字典的迭代器数目
static void _dictRehashStep(dict *d)
{
    if (d->iterators == 0)
        dictRehash(d, 1);
}

// dictRehash 向前 rehash n步。如果还没有搬迁完，返回 1，搬迁完成返回0
int dictRehash(dict *d, int n)
{
    // 当dictRehash时，rehashidx指向当前正在被搬迁的bucket，如果这个bucket中一个可搬迁的dictEntry都没有，说明就没有可搬迁的数据。
    // 这个时候会继续向后遍历 ht[0].table 数组，直到找到下一个存有数据的bucket位置，如果一直找不到，则最多向前走 empty_visits 步，本次搬迁任务结束。
    int empty_visits = n * 10;
    // 整个dict的 rehash 完成了，返回0
    if (!dictIsRehashing(d))
        return 0;

    // 外层大循环，确保本次最多向前走n步 以及 ht[0].table中还有值
    while (n-- && d->ht[0].used != 0)
    {
        dictEntry *de, *nextde;

        // 确保 rehashidx 不会超过 ht[0].table 的长度，因为 rehashidx 指向当前正在被搬迁的bucket，其实就是 ht[0].table 数组的下标，这里保证数组下标访问不会越界
        assert(d->ht[0].size > (unsigned long)d->rehashidx);

        // 当前的bucket搬迁完了，继续寻找下一个bucket，知道全部为空 或者 向前走的步数超过了限定值
        while (d->ht[0].table[d->rehashidx] == NULL)
        {
            d->rehashidx++;
            if (--empty_visits == 0)
                return 1;
        }
        // 终于找到了可搬迁的某个bucket中的 dictEntry
        de = d->ht[0].table[d->rehashidx];

        // 将这个 bucket 中的所有 dictEntry 包括链表上的，前部搬迁到新的 ht[1] 中
        while (de)
        {
            uint64_t h;

            nextde = de->next;
            // 获取当前键值对在新的哈希表中的桶的序号，这里进行取模的是 ht[1]的sizemask，所以 h 很大概率会与在 ht[0] 中的不一样
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;
            // 更新 新桶与旧桶 中的属性
            de->next = d->ht[1].table[h];
            d->ht[1].table[h] = de;
            d->ht[0].used--;
            d->ht[1].used++;
            de = nextde;
        }
        // 搬迁完成，将原来的ht[0]中的bucket置空
        d->ht[0].table[d->rehashidx] = NULL;
        // rehashidx 自增，表示又搬完了一个桶
        d->rehashidx++;
    }

    // 检查是否搬完了整张表
    if (d->ht[0].used == 0)
    {
        // 全部完成搬迁，则释放掉ht[0]的内存，将ht[1]的内容放到ht[0]中，重置ht[1]，并标志rehash完成(rehashidx=-1)
        zfree(d->ht[0].table);
        d->ht[0] = d->ht[1];
        _dictReset(&d->ht[1]);
        d->rehashidx = -1;
        return 0;
    }

    // 否则后面的动作还要继续搬迁
    return 1;
}

// 找到key对应的键值对，并移除它。此处dictDelete 调用时传入 nofree=0
static dictEntry *dictGenericDelete(dict *d, const void *key, int nofree)
{
    uint64_t h, idx;
    dictEntry *he, *prevHe;
    int table;

    // 如果字典中键值对数量为0，返回 未找到
    if (d->ht[0].used == 0 && d->ht[1].used == 0)
        return NULL;

    // 如果当前处于 rehash 阶段，则往前进行一步 rehash
    if (dictIsRehashing(d))
        _dictRehashStep(d);

    h = dictHashKey(d, key);

    for (table = 0; table <= 1; table++)
    {
        // 获取桶的索引
        idx = h & d->ht[table].sizemask;
        // 获取桶中的第一个 dictEntry
        he = d->ht[table].table[idx];
        prevHe = NULL;
        // 遍历链表，找到之后将其从链表中删除
        while (he)
        {
            if (key == he->key || dictCompareKeys(d, key, he->key))
            {
                if (prevHe)
                    prevHe->next = he->next;
                else
                    d->ht[table].table[idx] = he->next;
                if (!nofree)
                {
                    dictFreeKey(d, he);
                    dictFreeVal(d, he);
                    zfree(he);
                }
                d->ht[table].used--;
                return he;
            }
            prevHe = he;
            he = he->next;
        }
        // 如果没有再 rehash，就没必要再去 ht[1] 中寻找了
        if (!dictIsRehashing(d))
            break;
    }
    return NULL; // 没找到，返回 NULL
}

typedef struct intset {
    // 编码方式
    uint32_t encoding;

    // 集合中包含的元素数量
    uint32_t length;

    // 保存元素的数组
    int8_t contents[];
} intset;

/* Note that these encodings are ordered, so:
 * INTSET_ENC_INT16 < INTSET_ENC_INT32 < INTSET_ENC_INT64. */
#define INTSET_ENC_INT16 (sizeof(int16_t))  // int16 16位
#define INTSET_ENC_INT32 (sizeof(int32_t))  // int32 32位
#define INTSET_ENC_INT64 (sizeof(int64_t))  // int64 64位

// 返回 v 对应的 encoding 值
static uint8_t _intsetValueEncoding(int64_t v) {
    if (v < INT32_MIN || v > INT32_MAX)
        return INTSET_ENC_INT64;
    else if (v < INT16_MIN || v > INT16_MAX)
        return INTSET_ENC_INT32;
    else
        return INTSET_ENC_INT16;
}

// 创建一个空的 intset
intset *intsetNew(void) {
    // 为 intset 对象申请空间
    intset *is = zmalloc(sizeof(intset));
    // 默认使用 INTSET_ENC_INT16 作为存储大小
    is->encoding = intrev32ifbe(INTSET_ENC_INT16);
    // 数组长度为0，因为没有初始化的操作
    is->length = 0;
    return is;
}

// 在 intset 中添加一个整数
intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
    uint8_t valenc = _intsetValueEncoding(value);  // 根据要插入的 value 的类型 获取对应的 encoding
    uint32_t pos;
    if (success) *success = 1;  // success = NULL

    if (valenc > intrev32ifbe(is->encoding)) {
        // 插入元素的 encoding 值大于 intset 当前的，升级
        return intsetUpgradeAndAdd(is,value);
    } else {
        // 插入元素的 encoding 值小于等于当前 intset 的，则找到这个 value 应该插入的位置，赋值给 pos，已经存在的话直接返回
        if (intsetSearch(is,value,&pos)) {
            if (success) *success = 0;
            return is;
        }

        // 动态扩容
        is = intsetResize(is,intrev32ifbe(is->length)+1);
        // 将 pos 位置后面的元素整体向后挪一位，给 pos 腾位置
        if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);
    }

    // 将 pos 位置设置为 value
    _intsetSet(is,pos,value);
    // 更新 length
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

// 动态扩容，即将原来数组的容量 (is.length*encoding) 调整为 ((is.length+1)*encoding)
static intset *intsetResize(intset *is, uint32_t len) {
    uint32_t size = len*intrev32ifbe(is->encoding);
    is = zrealloc(is,sizeof(intset)+size);
    return is;
}

// 暴力迁移pos位置之后的数据，为pos位置挪出位置
static void intsetMoveTail(intset *is, uint32_t from, uint32_t to) {
    // from = pos, to = pos+1

    // src 表示 pos 相对于数组头部的迁移量
    // dst 表示 pos下一个元素相对于数组头部的偏移量
    void *src, *dst;
    // pos位置 距离数组末尾的元素个数，bytes*类型大小 即是pos后面的所有元素的总长度
    uint32_t bytes = intrev32ifbe(is->length)-from;
    // encoding
    uint32_t encoding = intrev32ifbe(is->encoding);

    if (encoding == INTSET_ENC_INT64) {
        src = (int64_t*)is->contents+from;
        dst = (int64_t*)is->contents+to;
        bytes *= sizeof(int64_t);
    } else if (encoding == INTSET_ENC_INT32) {
        src = (int32_t*)is->contents+from;
        dst = (int32_t*)is->contents+to;
        bytes *= sizeof(int32_t);
    } else {
        src = (int16_t*)is->contents+from;
        dst = (int16_t*)is->contents+to;
        bytes *= sizeof(int16_t);
    }
    // 从 src 复制 bytes 个字符到 dst
    memmove(dst,src,bytes);
}

static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
    uint8_t curenc = intrev32ifbe(is->encoding);  // 当前 encoding
    uint8_t newenc = _intsetValueEncoding(value); // 插入元素的 encoding
    int length = intrev32ifbe(is->length);
    // 插入到 数组最左边 还是 数组最右边。为什么会是最值？因为要升级，所以插入值肯定超出了现有 encoding 对应类型的最值，要么是负数越界，要么是正数越界
    int prepend = value < 0 ? 1 : 0;

    // 首先，设置 intset 的 encoding 为插入元素的 encoding(更大的那个)
    is->encoding = intrev32ifbe(newenc);
    // 根据新元素类型 扩展数组大小
    is = intsetResize(is,intrev32ifbe(is->length)+1);

    // 从数组最后一个元素开始遍历，将其放入合适的位置。prepend 的作用就是确保我们能给待插入值留下最左边的位置 或 最右边的位置
    while(length--)
        _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));

    // 在数组头部或者数组尾部插入 value
    if (prepend)
        _intsetSet(is,0,value);
    else
        _intsetSet(is,intrev32ifbe(is->length),value);
    // 最后更新 length
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) {
    int min = 0, max = intrev32ifbe(is->length)-1, mid = -1;
    int64_t cur = -1;

    // 当 intset 中没有元素时，直接返回
    if (intrev32ifbe(is->length) == 0) {
        if (pos) *pos = 0;
        return 0;
    } else {
        // 大于当前数组中最大值 或 小于最小值，也是直接返回
        if (value > _intsetGet(is,max)) {
            if (pos) *pos = intrev32ifbe(is->length);
            return 0;
        } else if (value < _intsetGet(is,0)) {
            if (pos) *pos = 0;
            return 0;
        }
    }

    // 因为数组有序，所以采用二分法查找位置是一个非常正确的选择
    while(max >= min) {
        mid = ((unsigned int)min + (unsigned int)max) >> 1;
        cur = _intsetGet(is,mid);
        if (value > cur) {
            min = mid+1;
        } else if (value < cur) {
            max = mid-1;
        } else {
            break;
        }
    }

    if (value == cur) {
        // value 已经存在
        if (pos) *pos = mid;
        return 1;
    } else {
        // value 不存在
        if (pos) *pos = min;
        return 0;
    }
}

unsigned char *ziplistNew(void) {
    unsigned int bytes = ZIPLIST_HEADER_SIZE+ZIPLIST_END_SIZE;  // 头部的 4+4+2 和 尾部的1 总共 11 字节
    unsigned char *zl = zmalloc(bytes);  // 这里的ziplist类型是一个 char 数组，而不是某个具体的结构体
    ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);  // 设置 zlbytes 为 初始分配的值，即 bytes
    ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);  // 设置 zltail 为 header 结束的地方
    ZIPLIST_LENGTH(zl) = 0;  // 设置 zllen 为 0
    zl[bytes-1] = ZIP_END;  // 最后一个字节存储常量 255 ，表示 ziplist 结束
    return zl;
}

unsigned char *ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
    return __ziplistInsert(zl,p,s,slen);
}

// 在 p 处 插入 s，s 的长度为 slen；插入后s占据p的位置，p及其后面的数据整体后移。其中 p 指向 ziplist 中某一个 entry 的起始位置，或者 zlend(当向尾部插入时)
unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
	// reqlen 表示 将 s 变成一个 entry 所需要的总字节数，即 prevlen,encoding,entry-data 的总长度
    size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), reqlen;
    unsigned int prevlensize, prevlen = 0;
    size_t offset;
    int nextdiff = 0;
    unsigned char encoding = 0;
    long long value = 123456789; // 随便使用一个一眼就能看出来的值表示当前变量未被逻辑初始化，避免 warning
    zlentry tail;

    if (p[0] != ZIP_END) {
        // 如果不是插入尾部，则根据p获取 p所在的 entry 的前一个 entry 的 prevlen，需要保存 prevlen的字节数保存在 prevlensize(1字节或者5字节，前面有介绍)
        ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
    } else {
        // p 指向的是 尾部标志
        unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl);
        if (ptail[0] != ZIP_END) {
            // 获取 ziplist 最后一个 entry 的长度，保存在 prevlen 中
            prevlen = zipRawEntryLength(ptail);
        }
    }

    // 尝试能否转化成整数
    if (zipTryEncoding(s,slen,&value,&encoding)) {
        // 可以转化成 int，则 reqlen 即为存储此 int 所需的字节数，即 entry-data 的长度
        reqlen = zipIntSize(encoding);
    } else {
        // 无法转换成 int，那就是字节数组，reqlen 就是要存入的字符串的长度，即 entry-data 的长度
        reqlen = slen;
    }

    // reqlen
    reqlen += zipStorePrevEntryLength(NULL,prevlen);  // 再加上 prevlen 的长度
    reqlen += zipStoreEntryEncoding(NULL,encoding,slen);  // 再加上 encoding 的长度

    // 当不是向尾部插入时，我们必须确保下一个 entry 的 prevlen 等于当前 entry 的长度
    int forcelarge = 0;
    // 【1】nextdiff 存储的是p的prevlen的变化值(新元素长度reqlen - p之前entry的prelen)，具体解释看代码后面【1】处的解释
    nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;
    if (nextdiff == -4 && reqlen < 4) {
        nextdiff = 0;
        forcelarge = 1;  // 这种情况下意味着，本来可以用 1 字节的，却使用了 5 个字节
    }

    /* Store offset because a realloc may change the address of zl. */
    // 存储 p 相对于 ziplist 的偏移量，因为 resize 可能改变 ziplist 的起始地址
    offset = p-zl;
    // 到这一步已经能确定 ziplist 需要的总的容量了，调用 resize 调整 ziplist 的大小
    zl = ziplistResize(zl,curlen+reqlen+nextdiff);
    // 重新定位 p
    p = zl+offset;

    // 将 p 以及其后面的数据移动为 s 挪地方，别忘了更新 zltail 的值
    if (p[0] != ZIP_END) {

        // 在p前面腾出reqlen字节给新entry使用（将p move到p+reqlen，考虑了prelen缩减或增加）
        memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff);

        // 更新 s 的后一个 entry（p+reqlen即p的新地址）的prevlen；
        if (forcelarge)
            // 【2】强制使用 5 字节存储，避免连锁更新时的大量重新分配空间操作，不进行缩容
            zipStorePrevEntryLengthLarge(p+reqlen,reqlen);
        else
            // 计算 reqlen 进而判断使用 1 字节 还是 5 字节
            zipStorePrevEntryLength(p+reqlen,reqlen);

        // 更新 zltail
        ZIPLIST_TAIL_OFFSET(zl) =
            intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen);

          // 更新zltail
        zipEntry(p+reqlen, &tail);
        if (p[reqlen+tail.headersize+tail.len] != ZIP_END) {
            ZIPLIST_TAIL_OFFSET(zl) =
                intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
        }
    } else {
        // 如果是在尾部插入，则直接修改 zltail 为 s
        ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(p-zl);
    }

    // 如果 nexydiff 不等于0，整个 s 后面的 ziplist 的 prevlen 都可能发生变化，这里尝试进行维护
    if (nextdiff != 0) {
        offset = p-zl;
        zl = __ziplistCascadeUpdate(zl,p+reqlen);
        p = zl+offset;  // 改变的只是 p 后面的，前面的没变，因此 s 插入的位置没变
    }

    // 存入 s 这个 entry
    p += zipStorePrevEntryLength(p,prevlen);
    p += zipStoreEntryEncoding(p,encoding,slen);
    if (ZIP_IS_STR(encoding)) {
        memcpy(p,s,slen);
    } else {
        zipSaveInteger(p,value,encoding);
    }
    // ziplist 的长度加 1
    ZIPLIST_INCR_LENGTH(zl,1);
    return zl;
}

// 将 ziplist 的长度变成 len
unsigned char *ziplistResize(unsigned char *zl, unsigned int len) {
    zl = zrealloc(zl,len);
    ZIPLIST_BYTES(zl) = intrev32ifbe(len);
    zl[len-1] = ZIP_END;
    return zl;
}

// p 指向第一个不需要更新的 entry
unsigned char *__ziplistCascadeUpdate(unsigned char *zl, unsigned char *p) {
    size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), rawlen, rawlensize;
    size_t offset, noffset, extra;
    unsigned char *np;
    zlentry cur, next;

    // 当 p 是 ziplist 的”尾巴“时停止更新
    while (p[0] != ZIP_END) {
        zipEntry(p, &cur);  // 【1】将 entry 解码称为一个易于操作的 entry 结构体，细节见代码后解释
        rawlen = cur.headersize + cur.len; // 当前节点的长度
        rawlensize = zipStorePrevEntryLength(NULL,rawlen);  // 存储当前节点所需要的 prevlen 大小

        // 没有下一个节点，直接返回
        if (p[rawlen] == ZIP_END) break;

        // 获取 p 的下一个节点
        zipEntry(p+rawlen, &next);

        // 如果下一个节点的 prevlen 等于当前节点的 长度，则没必要更新，直接退出循环
        if (next.prevrawlen == rawlen) break;

        // 下一个节点的 prevlen 小于当前节点的长度(当前节点长度为 5 字节，next 的 prevlen 为1 字节)
        if (next.prevrawlensize < rawlensize) {

            // ziplist的地址可能发生改变，先记录 p 相对于zl起始位置的偏移量
            offset = p-zl;
            // 额外需要申请的空间 5 - 1 = 4
            extra = rawlensize-next.prevrawlensize;
            // 改变 ziplist 的容量
            zl = ziplistResize(zl,curlen+extra);
            // 重新计算 p 的位置
            p = zl+offset;

            /* Current pointer and offset for next element. */
            np = p+rawlen;  // next 的新地址
            noffset = np-zl;  // next新地址相对于 ziplist 头部的偏移量

            // 更新 zltail
            if ((zl+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))) != np) {
                ZIPLIST_TAIL_OFFSET(zl) =
                    intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+extra);
            }

            // 扩展 next 的 prevlen，并将数据拷贝
            memmove(np+rawlensize,
                np+next.prevrawlensize,
                curlen-noffset-next.prevrawlensize-1);
            // 在扩展后的 next 的 prevlen 中重新记录 p 的长度
            zipStorePrevEntryLength(np,rawlen);

            /* Advance the cursor */
            // 更新 p 为下一个 entry
            p += rawlen;
            // 更新 p 的长度(需要加上扩展的 prevlen 的 extra 个字节)
            curlen += extra;
        } else {
            // 这种情况下，next 的 prevlen 足够表示 当前 p 的长度
            if (next.prevrawlensize > rawlensize) {
                // next 的 prevlen > p 的长度(next.prevlen = 5 结点，p的长度小于 5 个结点)，此时应该 缩容，但出于性能以及操作的方便性(减少后续连锁更新的可能性)，我们通常不进行缩容，这个时候，直接将 next 的 prevlen 设置为 5 个结点
                zipStorePrevEntryLengthLarge(p+rawlen,rawlen);
            } else {
                // 相等
                zipStorePrevEntryLength(p+rawlen,rawlen);
            }

            // next 的长度并没有发生变化(没有缩容)，终止循环
            break;
        }
    }
    return zl;
}

typedef struct zlentry {
    unsigned int prevrawlensize; // 存储 prevrawlen 所需要的字节数，同样也有 1字节 和 5字节之分
    unsigned int prevrawlen;     // 对应 prevlen
    unsigned int lensize;        // 存储 len 所需要的字节数
    unsigned int len;            // 当前 entry 的长度
    unsigned int headersize;     // ziplist头部大小: prevrawlensize + lensize
    unsigned char encoding;      // 编码方式
    unsigned char *p;            // 指向某个实际 entry 的地址
} zlentry;

typedef struct redisObject
{
    unsigned type : 4;       // 类型
    unsigned encoding : 4;	 // 编码
    unsigned lru : LRU_BITS; // 对象最后被访问的时间，我们暂时不关注 LRU
    int refcount;			 // 引用次数
    void *ptr;				 // 指向实现对象的数据结构
} robj;

/* Object types */
#define OBJ_STRING 0 /* String object. */
#define OBJ_LIST 1   /* List object. */
#define OBJ_SET 2    /* Set object. */
#define OBJ_ZSET 3   /* Sorted set object. */
#define OBJ_HASH 4   /* Hash object. */

/* Objects encoding. Some kind of objects like Strings and Hashes can be
 * internally represented in multiple ways. The 'encoding' field of the object
 * is set to one of this fields for this object. */
#define OBJ_ENCODING_RAW 0        // 简单动态字符串 sds
#define OBJ_ENCODING_INT 1        // long 类型
#define OBJ_ENCODING_HT 2         // 字典 dict
#define OBJ_ENCODING_ZIPMAP 3     // zipmap(弃用)
#define OBJ_ENCODING_LINKEDLIST 4 // 双端链表 adlist
#define OBJ_ENCODING_ZIPLIST 5    // 压缩列表 ziplist
#define OBJ_ENCODING_INTSET 6     // 整数集合 intset
#define OBJ_ENCODING_SKIPLIST 7   // 跳表 skiplist
#define OBJ_ENCODING_EMBSTR 8     // 采用embstr编码的sds
#define OBJ_ENCODING_QUICKLIST 9  // qunicklist，用于列表
#define OBJ_ENCODING_STREAM 10    // 紧凑列表 listpack
#define LRU_BITS 24