45fan.com - 路饭网

搜索: 您的位置主页 > 网络频道 > 阅读资讯:Redis双链表结构的教程

Redis双链表结构的教程

2015-09-16 10:12:01 来源:www.45fan.com 【

Redis双链表结构的教程

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倒数第二个节点

               //如果超过链表的索引,则返回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);     //旋转链表,移除尾节点并插入头部。

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; 
 } 


本文地址:http://www.45fan.com/a/question/21256.html
Tags: Redis 中的 详解
编辑:路饭网
关于我们 | 联系我们 | 友情链接 | 网站地图 | Sitemap | App | 返回顶部