欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

详解Redis中的双链表结构

程序员文章站 2022-03-14 18:08:50
redis中双链表实现的基本结构: 1.节点结构 typedef struct listnode { struct listnode *prev; /...

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