详解Redis中的双链表结构

Redis  /  管理员 发布于 7年前   123

Redis中双链表实现的基本结构：
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倒数第二个节点     //如果超过链表的索引，则返回nullvoid 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);         //旋转链表，移除尾节点并插入头部。

list结构和listNode结构的API
list和listNode都有它们自己的一族API，这里贴出来学习一下redis的源码(ps:下面的代码都是我仿照redis改写能直接编译运行的代码)

list *listCreate(void)

  /**    * 创建一个新列表    *    * T = O(1)      */   list *listCreate(void)   {     struct list *list;        // 为列表结构分配内存     list = (struct list *)malloc(sizeof(struct list));     if (list == NULL)       return NULL;        // 初始化属性     list->head = list->tail = NULL;     list->len = 0;     list->dup = NULL;     list->free = NULL;     list->match = NULL;        return list;   } 

void listRelease(list *list)

 

  /**    * 释放整个列表    *    * T = O(N), N为列表长度    */   void listRelease(list *list)   {     unsigned long len;     listNode *current, *next;        current = list->head;     len = list->len;        while (len --) {       next = current->next;       // 如果列表有自带的free方法，那么先对节点值调用它       if (list->free) list->free(current->value);       // 之后释放节点       free(current);       current = next;     }     free(list);   }  

list *listAddNodeHead(list *list, void *value)

  /**    * 新建一个包含给定value的节点，并将它加入到列表的表头    *    * T = O(1)      */   list *listAddNodeHead(list *list, void *value)   {     listNode *node;        node = (listNode *)malloc(sizeof(listNode));     if (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;   } 

list *listAddNodeTail(list *list, void *value)

  /**    * 新建一个包含给定value的节点，并把它加入到列表的表尾    *    * T = O(1)    */   list *listAddNodeTail(list *list, void *value)   {     listNode *node;          node = (listNode *)malloc(sizeof(listNode));     if (node == NULL)       return NULL;        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 *listInsertNode(list *list, listNode *old_node, void *value, int after)

 

  /**    * 创建一个包含值value的节点    * 并根据after参数的指示，将新节点插入到old_node的之前或者之后    *    * T = O(1)    */   list *listInsertNode(list *list, listNode *old_node, void *value, int after)   {     listNode *node;        node = (listNode *)malloc(sizeof(listNode));     if (node == NULL)       return NULL;        if (after) {       // 插入到old_node之后       node->prev = old_node;       node->next = old_node->next;       // 处理表尾节点       if (list->tail == old_node) {         list->tail = node;       }     } else {       // 插入到old_node之前       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;     }        // 更新列表节点     list->len ++;        return list;   } 

void listDelNode(list *list, listNode *node)

  

 /**    * 释放列表中给定的节点    *    * T = O(1)    */   void listDelNode(list *list, listNode *node)   {     // 处理前驱节点指针     if (node->prev) {       node->prev->next = node->next;     } else {       list->head = node->next;     }        // 处理后继节点     if (node->next) {       node->next->prev = node->prev;     } else {       list->tail = node->prev;     }        // 释放节点值     if (list->free) list->free(node->value);        // 释放节点     free(node);        // 更新列表节点数目     list->len --;   } 

迭代器
其实我对迭代器的概念非常陌生，因为我是纯c程序员，不会c++，这里直接跟着学了！

Redis针对list结构实现了一个迭代器，用于对链表进行遍历

迭代器的结构定义如下：

  /**    * 链表迭代器    */   typedef struct listIter {     // 下一节点     listNode *next;        // 迭代方向     int direction;   } listIter; 

direction决定了迭代器是沿着next指针向后迭代，还是沿着prev指针向前迭代，这个值可以是adlist.h中的AL_START_HEAD常量或AL_START_TAIL常量：

  #define AL_START_HEAD 0   #define AL_START_TAIL 1 

学习一下迭代器的api实现：

listIter *listGetIterator(list *list, int direction)

  /**    * 创建列表list的一个迭代器，迭代方向由参数direction决定    *    * 每次对迭代器listNext(),迭代器返回列表的下一个节点    *    * T = O(1)    */   listIter *listGetIterator(list *list, int direction)   {     listIter *iter;        iter = (listIter *)malloc(sizeof(listIter));     if (iter == NULL)       return NULL;        // 根据迭代器的方向，将迭代器的指针指向表头或者表尾     if (direction == AL_START_HEAD) {       iter->next = list->head;     } else {       iter->next = list->tail;     }        // 记录方向     iter->direction = direction;        return iter;   } 

void listRewind(list *list, listIter *li)

  /**    * 将迭代器iter的迭代指针倒回list的表头    *    * T = O(1)    */   void listRewind(list *list, listIter *li)   {     li->next = list->head;     li->direction = AL_START_HEAD;   } 

void listRewindTail(list *list, listIter *li)

  /**    * 将迭代器iter的迭代指针倒回list的表尾    *    * T = O(1)    */   void listRewindTail(list *list, listIter *li)   {     li->next = list->tail;     li->direction = AL_START_TAIL;   } 

listNode *listNext(listIter *iter)

  /**    * 函数要么返回当前节点，要么返回NULL，因此，常见的用法是：    * iter = listGetIterator(list, <direction>);    * while ((node = listNext(iter)) != NULL) {    *   doSomethingWith(listNodeValue(node));    * }    *    * T = O(1)    */   listNode *listNext(listIter *iter)   {     listNode *current = iter->next;        if (current != NULL) {       // 根据迭代方向，选择节点       if (iter->direction == AL_START_HEAD)         iter->next = current->next;       else         iter->next = current->prev;     }        return current;   }