Redis源码（1）基本数据结构（上）

// 类型别名，用于指向 sdshdr 的 buf 属性
typedef char *sds;
//保存字符串对象的结构
struct sdshdr {
    // buf 中已占用空间的长度
    int len;
    // buf 中剩余可用空间的长度
    int free;
    // 数据空间
    char buf[];
};

/*
 * 返回 sds 实际保存的字符串的长度
 *
 * T = O(1)
 */
static inline size_t sdslen(const sds s) {
    struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
    return sh->len;
}

   //根据初始化字符串（无符号）及长度建立sds
   //这是很多API所都需要的
 sds sdsnewlen(const void *init, size_t initlen) {
    struct sdshdr *sh;
    // 根据是否有初始化内容，选择适当的内存分配方式
    // T = O(N)
    if (init) {
    // zmalloc 不初始化所分配的内存(这个函数之后介绍)
    sh = zmalloc(sizeof(struct sdshdr)+initlen+1);
    } else {
    // zcalloc 将分配的内存全部初始化为 0
    sh = zcalloc(sizeof(struct sdshdr)+initlen+1);
    }
    // 内存分配失败，返回
    if (sh == NULL) return NULL;
    // 设置初始化长度
    sh->len = initlen;
    // 新 sds 不预留任何空间
    sh->free = 0;
    // 如果有指定初始化内容，将它们复制到 sdshdr 的 buf 中
    // T = O(N)
    if (initlen && init)
    memcpy(sh->buf, init, initlen);
    // 以 \0 结尾
    sh->buf[initlen] = '\0';
    // 返回 buf 部分，而不是整个 sdshdr
    //因为我们要的是char
    return (char*)sh->buf;
}

//以O（1)的时间完成字符串的“清空”
//只需要将终止符放在0即可
void sdsclear(sds s) {
// 取出 sdshdr
    struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr))); 
    // 重新计算属性
    sh->free += sh->len;
    sh->len = 0; 
    // 将结束符放到最前面（相当于惰性地删除 buf 中的内容）
    sh->buf[0] = '\0';
}

sds sdsMakeRoomFor(sds s, size_t addlen) {
    struct sdshdr *sh, *newsh;
    
    // 获取 s 目前的空余空间长度
    size_t free = sdsavail(s);
    size_t len, newlen;
    
    // s 目前的空余空间已经足够，无须再进行扩展，直接返回
    if (free >= addlen) return s;
    
    // 获取 s 目前已占用空间的长度
    len = sdslen(s);
    sh = (void*) (s-(sizeof(struct sdshdr)));
    
    // s 最少需要的长度
    newlen = (len+addlen);
    
    // 根据新长度，为 s 分配新空间所需的大小
    if (newlen < SDS_MAX_PREALLOC)
    // 如果新长度小于 SDS_MAX_PREALLOC 
    // 那么为它分配两倍于所需长度的空间
    newlen *= 2;
    else
    // 否则，分配长度为目前长度加上 SDS_MAX_PREALLOC
    newlen += SDS_MAX_PREALLOC;
    // T = O(N)
    newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1);
    
    // 内存不足，分配失败，返回
    if (newsh == NULL) return NULL;   
    // 更新 sds 的空余长度
    newsh->free = newlen - len; 
    // 返回 sds
    return newsh->buf;
}

/*
 * 双端链表结构定义
 */
typedef struct list {

    // 表头节点
    listNode *head;
    // 表尾节点
    listNode *tail;
    
    // 以下这些是函数指针，负责对应的功能
    // 节点值复制函数
    void *(*dup)(void *ptr);
    // 节点值释放函数
    void (*free)(void *ptr);
    // 节点值对比函数
    int (*match)(void *ptr, void *key);
    // 链表所包含的节点数量
    unsigned long len;
} list;

// 双端链表节点
typedef struct listNode {
    // 前置节点
    struct listNode *prev;
    // 后置节点
    struct listNode *next;
    // 节点的值
    void *value;
} listNode;

//双端链表迭代器
typedef struct listIter {
    // 当前迭代到的节点
    listNode *next;
    // 迭代的方向（前向还是后向）
    int direction;
} listIter;

list *listAddNodeHead(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 = NULL;
        node->next = list->head;
        list->head->prev = node;
        list->head = node;
    }   
    // 更新链表节点数
    list->len++;
    return list;
}

 /* 为给定链表创建一个迭代器，
 * 之后每次对这个迭代器调用 listNext 都返回被迭代到的链表节点
 * direction 参数决定了迭代器的迭代方向：
 *  AL_START_HEAD ：从表头向表尾迭代
 *  AL_START_TAIL ：从表尾想表头迭代
 */
listIter *listGetIterator(list *list, int direction)
{
    // 为迭代器分配内存
    listIter *iter;
    if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;
    // 根据迭代方向，设置迭代器的起始节点
    if (direction == AL_START_HEAD)
    iter->next = list->head;
    else
    iter->next = list->tail;   
    // 记录迭代方向
    iter->direction = direction; 
    return iter;
}

listNode *listSearchKey(list *list, void *key)
{
    listIter *iter;
    listNode *node;
    
    // 迭代整个链表
    iter = listGetIterator(list, AL_START_HEAD);
    while((node = listNext(iter)) != NULL) {
        // 对比
        if (list->match) {
            if (list->match(node->value, key)) {
                listReleaseIterator(iter);
                // 找到
                return node;
            }
        } else {
            if (key == node->value) {
            listReleaseIterator(iter);
            // 找到
            return node;
            }
            }
        }
        listReleaseIterator(iter);
    // 未找到
    return NULL;
}