adlist解读

通用双向链表数据结构，支持在头部、尾部插入节点，以及双向遍历等操作

核心数据结构

链表节点 (listNode)

typedef struct listNode {
    struct listNode *prev;  // 前驱节点指针
    struct listNode *next;  // 后继节点指针
    void *value;           // 节点值（void*类型，支持任意数据类型）
} listNode;

链表结构 (list)

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;

head / tail 头尾节点
dup、free 和 match 是函数指针，用于节点值的复制、释放和匹配操作，提供了链表操作的扩展性
len 链表长度(节点数量)

sizeof(*list) ，64位os,5 个指针一个 long 类型 = 6 * 8=48

迭代器 (listIter)

typedef struct listIter {
    listNode *next;        // 下一个要访问的节点
    int direction;         // 遍历方向（AL_START_HEAD=0 或 AL_START_TAIL=1）
} listIter;

结构特性

双向

每个节点均配备 prev/ next 指针，前驱后继节点，操作复杂度保持在 O(1) 水平
无环

头节点 prev 指针和表尾节点 next 指针均指向 NULL，确保了链表的访问始终有明确的终点，避免循环引用导致的潜在问题
便捷的表头尾访问

list 结构中的 head 和 tail 指针，能直接定位到链表的起始和结束节点，获取表头节点和表尾节点的操作复杂度同样为 O(1)，简化链表的操作流程
高效长度计数

内置 len 属性记录链表中的节点数量，操作复杂度保持在 O(1)
多态支持

链表节点采用 void* 指针来存储节点值，同时，list 结构提供了 dup、free 和 match 三个属性，允许用户为节点值设置类型特定的函数。使 Redis 的链表能够灵活地保存和处理各种不同类型的值，实现了多态链表的功能

核心API函数

创建和销毁

listCreate(): 创建新的空链表
listRelease(): 释放整个链表
listEmpty(): 清空链表内容但保留链表结构

节点操作

listAddNodeHead(): 在链表头部添加节点
listAddNodeTail(): 在链表尾部添加节点
listInsertNode(): 在指定位置插入节点
listDelNode(): 删除指定节点
listUnlinkNode(): 从链表中移除节点但不释放内存

遍历和搜索

listGetIterator(): 创建迭代器
listNext(): 获取下一个节点
listRewind(): 重置迭代器到头部
listRewindTail(): 重置迭代器到尾部
listSearchKey(): 搜索指定键值的节点
listIndex(): 根据索引获取节点（支持负数索引）

高级操作

listDup(): 复制整个链表
listRotateTailToHead(): 将尾节点移到头部
listRotateHeadToTail(): 将头节点移到尾部
listJoin(): 合并两个链表

宏定义

#define listLength(l) ((l)->len)           // 获取链表长度
#define listFirst(l) ((l)->head)           // 获取头节点
#define listLast(l) ((l)->tail)            // 获取尾节点
#define listPrevNode(n) ((n)->prev)        // 获取前驱节点
#define listNextNode(n) ((n)->next)        // 获取后继节点
#define listNodeValue(n) ((n)->value)      // 获取节点值

Redis中的应用

核心服务器结构

server.clients - 活跃客户端列表
server.clients_to_close - 待关闭的客户端
server.clients_pending_write - 待写入的客户端
server.clients_pending_read - 待读取的客户端

客户端结构

client.reply - 响应缓冲区列表
client.deferred_reply_errors - 延迟错误响应列表

复制和监控

server.slaves - 从节点列表
server.monitors - 监控客户端列表

事务和阻塞操作

client.watched_keys - 客户端监视的键
server.postponed_clients - 延迟处理的客户端
server.unblocked_clients - 待解除阻塞的客户端

复制缓冲区

replDataBuf.blocks - 复制数据缓冲区块列表

慢查询日志

server.slowlog - 慢查询日志列表

模块系统

RedisModule.types - 模块数据类型列表
RedisModule.usedby - 使用该模块API的模块列表
RedisModule.using - 该模块使用的API列表

使用示例

// 创建链表
list *myList = listCreate();

// 添加节点
listAddNodeTail(myList, "hello");
listAddNodeHead(myList, "world");

// 遍历链表
listIter *iter = listGetIterator(myList, AL_START_HEAD);
listNode *node;
while ((node = listNext(iter)) != NULL) {
    printf("%s\n", (char*)node->value);
}
listReleaseIterator(iter);

// 释放链表
listRelease(myList);

源码

listCreate

list *listCreate(void){
	// 声明 list结构体的指针list
    struct list *list;
	// list 结构体分配内存
    if ((list = zmalloc(sizeof(*list))) == NULL)
        return NULL;
    // 初始化链表头尾指针为 NULL,链表长度len=0
    list->head = list->tail = NULL;
    list->len = 0;
    // 复制、释放和匹配函数为 NULL
    list->dup = NULL;
    list->free = NULL;
    list->match = NULL;
    return list;
}

listRelease

void listRelease(list *list){
    if (!list) // 避免了在空指针上执行操作，这可能会导致未定义行为或程序崩溃。
        return;
    // listEmpty释放链表中的所有节点，逐个释放每个节点所占用的内存
    listEmpty(list);
    // zfree释放list结构体本身所占用的内存
    zfree(list);
}

listEmpty

void listEmpty(list *list)  {  
    // 获取链表的长度  
    unsigned long len;  
    // 定义当前节点和下一个节点的指针  
    listNode *current, *next;  
      
    // 将当前节点指针指向链表的头节点  
    current = list->head;  
      
    // 将链表长度赋值给len变量，方便后续遍历  
    len = list->len;  
      
    // 循环遍历链表，直到所有节点都被处理  
    while(len--) {  
        // 将下一个节点指针指向当前节点的下一个节点  
        next = current->next;  
          
        // 如果链表定义了释放节点值的函数，则调用该函数释放当前节点的值  
        if (list->free) list->free(current->value);  
          
        // 释放当前节点所占用的内存  
        zfree(current);  
          
        // 将当前节点指针指向下一个节点，准备处理下一个节点  
        current = next;  
    }  
      
    // 将链表的头节点和尾节点指针置为NULL，表示链表为空  
    list->head = list->tail = NULL;  
      
    // 将链表长度置为0，表示链表没有节点  
    list->len = 0;  
}

listAddNodeHead

参数：
- list：指向列表的指针
- value：要添加到新节点的值（作为指针）
返回值：
- 成功时返回更新后的列表指针
- 出错时返回 NULL

// 接受一个指向 list 结构的指针和一个 void 类型的指针作为参数
// 返回一个指向 list 结构的指针
list *listAddNodeHead(list *list, void *value)  {  
    // 指向 listNode 结构的指针 node
    listNode *node;
  
    // 为 listNode 分配内存，并将返回的地址赋值给 node
    if ((node = zmalloc(sizeof(*node))) == NULL)  
        // 如果内存分配失败，则返回 NULL  
        return NULL;  
  
    // 将传入的 value 赋值给新节点的 value 字段
    node->value = value;  
  
    // 调用 listLinkNodeHead 函数，将新节点添加到链表的头部  
    listLinkNodeHead(list, node);  
  
    // 返回更新后的链表指针
    return list;  
} 

listAddNodeTail

只有 listLinkNodeTail(list, node); 不同

listLinkNodeHead

// 将一个节点链接到链表的头部  
void listLinkNodeHead(list* list, listNode *node) {  
    // 如果链表为空（即长度为0）  
    if (list->len == 0) {  
        // 将新节点设置为链表的头节点和尾节点  
        list->head = list->tail = node;  
        // 因为链表只有一个节点，所以该节点的prev和next都指向NULL  
        node->prev = node->next = NULL;  
    } else {  
        // 如果链表不为空，新节点的prev指向NULL（因为它是头部节点）  
        node->prev = NULL;  
        // 将新节点的next指向当前的头节点  
        node->next = list->head;  
        // 将当前头节点的prev指向新节点，形成双向链表的链接  
        list->head->prev = node;  
        // 将链表的头节点更新为新节点  
        list->head = node;  
    }  
    // 无论链表是否为空，都将链表的长度加1  
    list->len++;  
}

链表为空：

（list->len == 0），说明之前没有节点，新节点不仅会成为头节点，也会成为尾节点
将list->head和list->tail都指向新节点node
由于链表只有一个节点，该节点的prev和next指针都应该指向NULL

链表不为空：

初始化新节点的prev为NULL，因为它即将成为新的头节点
将新节点的next指向当前的头节点list->head
更新当前头节点的prev指针，使其指向新节点，确保双向链表的连接正确
更新链表的头节点指针list->head，使其指向新节点

链表长度更新：

无论链表之前是否为空，在插入新节点后，链表的长度都会增加 1，因此list->len需要加 1

listDelNode

// 从列表中删除一个节点，并释放相关内存  
void listDelNode(list *list, listNode *node)  {  
    // listUnlinkNode从列表中解除该节点的链接  
    listUnlinkNode(list, node);  
    // 列表的free字段不为空（即存在一个用于释放节点值的回调函数）  
    if (list->free)   
        // 调用该回调函数，释放节点中存储的值所占用的内存  
        list->free(node->value);  
      
    // zfree释放节点本身所占用的内存  
    zfree(node);  
}

listUnlinkNode

// 从双向链表中移除一个节点，但不释放其内存  
void listUnlinkNode(list *list, listNode *node) {  
    // 如果该节点有前一个节点  
    if (node->prev) {  
        // 将前一个节点的next指针指向当前节点的下一个节点  
        node->prev->next = node->next;  
    } else {  
        // 否则，当前节点是头节点，将列表的头指针指向当前节点的下一个节点  
        list->head = node->next;  
    }  
      
    // 如果该节点有下一个节点  
    if (node->next) {  
        // 将下一个节点的prev指针指向当前节点的前一个节点  
        node->next->prev = node->prev;  
    } else {  
        // 否则，当前节点是尾节点，将列表的尾指针指向当前节点的前一个节点  
        list->tail = node->prev;  
    }  
      
    // 将当前节点的next和prev指针都设置为NULL，表示它已经从链表中移除  
    node->next = NULL;  
    node->prev = NULL;  
      
    // 减少列表的长度计数  
    list->len--;  
}

可以重新利用该节点，或者将其添加到其他列表中，而无需再次分配内存

redis adlist

adlist解读

核心数据结构

链表节点 (listNode)

链表结构 (list)

迭代器 (listIter)

结构特性

核心API函数

创建和销毁

节点操作

遍历和搜索

高级操作

宏定义

Redis中的应用

核心服务器结构

客户端结构

复制和监控

事务和阻塞操作

复制缓冲区

慢查询日志

模块系统

使用示例

源码

listCreate

listRelease

listEmpty

listAddNodeHead

listAddNodeTail

listLinkNodeHead

listDelNode

listUnlinkNode