深入redis内部--实现双向链表

wtuyss

　　数据结构的应用--Adlist.h定义
　　1.节点结构
　　typedef struct listNode {
    struct listNode *prev;  //前向节点
    struct listNode *next; //后向节点
    void *value;              //该节点的值
} listNode;
　　2.双向链表结构
　　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;
　　3.双向链表遍历器
　　typedef struct listIter {
    listNode *next;   //下一个节点
    int direction;
} listIter;
　　方向定义
　　#define AL_START_HEAD 0  //向前查找
   #define AL_START_TAIL 1    //向后查找
　　4.宏定义函数
　　#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)
　　5.定义函数
　　list *listCreate(void); //创建一个新的链表。该链表可以使用AlFree（）方法释放。
　　//但使用AlFree（）方法前需要释放用户释放私有节点的值。
　　//如果没有创建成功，返回null；创建成功则返回指向新链表的指针。
　　
void listRelease(list *list);  //释放整个链表，此函数不会执行失败。调用zfree(list *list)方法,定义在Zmalloc.c中。
　　
list *listAddNodeHead(list *list, void *value); //向链表头部中增加一个节点
　　
list *listAddNodeTail(list *list, void *value);    //向链表尾部增加一个节点
　　
list *listInsertNode(list *list, listNode *old_node, void *value, int after);//向某个节点位置插入节点 after为方向
　　
void listDelNode(list *list, listNode *node);//从链表上删除特定节点，调用者释放特定私用节点的值。
　　//该函数不会执行失败
listIter *listGetIterator(list *list, int direction);//返回某个链表的迭代器。
　　//迭代器的listNext（）方法会返回链表的下个节点。direction是方向
　　//该函数不会执行失败。
　　
listNode *listNext(listIter *iter);               
　　
void listReleaseIterator(listIter *iter);            //释放迭代器的内存。
　　
list *listDup(list *orig);                               //复制整个链表。当内存溢出时返回null，成功时返回原链表的一个备份
　　//不管该方法是否执行成功，原链表不会改变。
　　
listNode *listSearchKey(list *list, void *key);  //从特定的链表查找key。成功则返回第一个匹配节点的指针
　　//如果没有匹配，则返回null。
　　
listNode *listIndex(list *list, long index);     //序号从0开始，链表的头的索引为0.1为头节点的下个节点。一次类推。
　　//负整数用来表示从尾部开始计数。-1表示最后一个节点，-2倒数第二个节点
　　//如果超过链表的索引，则返回null
　　
void listRewind(list *list, listIter *li) {
    li->next = list->head;
    li->direction = AL_START_HEAD;
}
void listRewindTail(list *list, listIter *li) {
    li->next = list->tail;
    li->direction = AL_START_TAIL;
}
　　
void listRotate(list *list);                 //旋转链表，移除尾节点并插入头部。