日期:2014-05-16  浏览次数:20440 次

【Redis】对通用双向链表实现的理解

Redis实现的双向链表还是比较容易看得懂的,其实现的原理很经典, 代码很整洁清晰。

以下是对其源码注释的翻译及本人见解的部分说明,如有偏颇欢迎指正: 

/* adlist.h - 通用双向链表的实现*/

#ifndef __ADLIST_H__
#define __ADLIST_H__

/* 目前的数据结构只使用了Node, List, and Iterator. */

/* list节点*/
typedef struct listNode {
    struct listNode *prev;        // 前向指针
    struct listNode *next;        // 后向指针
    void *value;                  // 当前节点值
} listNode;

/* list迭代器*/
typedef struct listIter {
    listNode *next;               // 节点指针
    int direction;                // 迭代方向 
} listIter;

/*链表结构*/
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;

/* 函数宏定义 */
#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)                  // 指定节点的值

/* 函数指针, 设置外部调用模块的自定义的方法 */
#define listSetDupMethod(l,m) ((l)->dup = (m))         // 复制链表
#define listSetFreeMethod(l,m) ((l)->free = (m))       // 释放链表
#define listSetMatchMethod(l,m) ((l)->match = (m))     // 匹配

/* 函数指针, 获取外部调用模块的自定义的方法 */
#define listGetDupMethod(l) ((l)->dup)                      // 获取复制的自定义方法
#define listGetFree(l) ((l)->free)                          // 获取释放的自定义方法
#define listGetMatchMethod(l) ((l)->match)                  // 获取匹配的自定义方法

/* 函数原型 */
list *listCreate(void);                                                               // 创建链表
void listRelease(list *list);                                                         // 释放链表
list *listAddNodeHead(list *list, void *value);                                       // 在表头添加节点
list *listAddNodeTail(list *list, void *value);                                       // 在表尾添加节点
list *listInsertNode(list *list, listNode *old_node, void *value, int after);         // 在指定位置之后添加节点
void listDelNode(list *list, listNode *node);                                         // 删除节点
listIter *listGetIterator(list *list, int direction);                                 // 获取列表迭代器
listNode *listNext(listIter *iter);                                                   // 获取下一个节点
void listReleaseIterator(listIter *iter);                                             // 释放列表迭代器
list *listDup(list *orig);                                                            // 复制链表
listNode *listSearchKey(list *list, void *key);                                       // 给定key查找节点
listNode *listIndex(list *list, long index);                                          // 给定index查找节点
void listRewind(list *list, listIter *li);                                            // 迭代器指针重新指向头节点
void listRewindTail(list *list, listIter *li);                                        // 迭代器指针重新指向末节点
void listRotate(list *list);                                                          // 链表翻转, 末节点移动成为头节点

/* 迭代器的迭代方向 */
#define AL_START_HEAD 0
#define AL_START_TAIL 1

#endif /* __ADLIST_H__ */

/* adlist.c - 通用双向链表的实现 */


#include <stdlib.h>
#include "adlist.h"
#include "zmalloc.h"

/* 创建新链表. 新建的链表可以用函数
* AlFreeList()来释放, 但调用此函数之前需要要应用手动释放对每个节点的私有值空间
*