詳解Redis中的雙鏈表結(jié)構(gòu)

更新時(shí)間：2015年08月11日 12:21:49 作者：zinss26914

這篇文章主要介紹了Redis中的雙鏈表結(jié)構(gòu),包括listNode結(jié)構(gòu)的API,需要的朋友可以參考下

Redis中雙鏈表實(shí)現(xiàn)的基本結(jié)構(gòu)：
1.節(jié)點(diǎn)結(jié)構(gòu)

typedef struct listNode {
  struct listNode *prev; //前向節(jié)點(diǎn)
  struct listNode *next; //后向節(jié)點(diǎn)
  void *value;       //該節(jié)點(diǎn)的值
} listNode;

2.雙向鏈表結(jié)構(gòu)

typedef struct list {
  listNode *head;       //頭節(jié)點(diǎn)
  listNode *tail;        //尾節(jié)點(diǎn)
  void *(*dup)(void *ptr); //復(fù)制函數(shù)
  void (*free)(void *ptr);  //釋放函數(shù)
  int (*match)(void *ptr, void *key); //匹配函數(shù)，查找節(jié)點(diǎn)使用
  unsigned long len;     //雙向鏈表的長(zhǎng)度即節(jié)點(diǎn)的個(gè)數(shù)
} list;

3.雙向鏈表遍歷器

typedef struct listIter {
  listNode *next;  //下一個(gè)節(jié)點(diǎn)
  int direction;
} listIter;

 方向定義

  #define AL_START_HEAD 0 //向前查找
  #define AL_START_TAIL 1  //向后查找

4.宏定義函數(shù)

#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.定義函數(shù)

list *listCreate(void); //創(chuàng)建一個(gè)新的鏈表。該鏈表可以使用AlFree（）方法釋放。

               //但使用AlFree（）方法前需要釋放用戶釋放私有節(jié)點(diǎn)的值。

               //如果沒(méi)有創(chuàng)建成功，返回null；創(chuàng)建成功則返回指向新鏈表的指針。


void listRelease(list *list); //釋放整個(gè)鏈表，此函數(shù)不會(huì)執(zhí)行失敗。調(diào)用zfree(list *list)方法,定義在Zmalloc.c中。


list *listAddNodeHead(list *list, void *value); //向鏈表頭部中增加一個(gè)節(jié)點(diǎn)


list *listAddNodeTail(list *list, void *value);  //向鏈表尾部增加一個(gè)節(jié)點(diǎn)


list *listInsertNode(list *list, listNode *old_node, void *value, int after);//向某個(gè)節(jié)點(diǎn)位置插入節(jié)點(diǎn) after為方向


void listDelNode(list *list, listNode *node);//從鏈表上刪除特定節(jié)點(diǎn)，調(diào)用者釋放特定私用節(jié)點(diǎn)的值。

                              //該函數(shù)不會(huì)執(zhí)行失敗
listIter *listGetIterator(list *list, int direction);//返回某個(gè)鏈表的迭代器。

                                 //迭代器的listNext（）方法會(huì)返回鏈表的下個(gè)節(jié)點(diǎn)。direction是方向

                                //該函數(shù)不會(huì)執(zhí)行失敗。


listNode *listNext(listIter *iter);        


void listReleaseIterator(listIter *iter);      //釋放迭代器的內(nèi)存。


list *listDup(list *orig);                //復(fù)制整個(gè)鏈表。當(dāng)內(nèi)存溢出時(shí)返回null，成功時(shí)返回原鏈表的一個(gè)備份

                                //不管該方法是否執(zhí)行成功，原鏈表不會(huì)改變。


listNode *listSearchKey(list *list, void *key); //從特定的鏈表查找key。成功則返回第一個(gè)匹配節(jié)點(diǎn)的指針

                                //如果沒(méi)有匹配，則返回null。


listNode *listIndex(list *list, long index);   //序號(hào)從0開(kāi)始，鏈表的頭的索引為0.1為頭節(jié)點(diǎn)的下個(gè)節(jié)點(diǎn)。一次類(lèi)推。

                            //負(fù)整數(shù)用來(lái)表示從尾部開(kāi)始計(jì)數(shù)。-1表示最后一個(gè)節(jié)點(diǎn)，-2倒數(shù)第二個(gè)節(jié)點(diǎn)

                             //如果超過(guò)鏈表的索引，則返回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);         //旋轉(zhuǎn)鏈表，移除尾節(jié)點(diǎn)并插入頭部。

list結(jié)構(gòu)和listNode結(jié)構(gòu)的API
list和listNode都有它們自己的一族API，這里貼出來(lái)學(xué)習(xí)一下redis的源碼(ps:下面的代碼都是我仿照redis改寫(xiě)能直接編譯運(yùn)行的代碼)

list *listCreate(void)

  /** 
   * 創(chuàng)建一個(gè)新列表 
   * 
   * T = O(1)                                                               
   */ 
  list *listCreate(void) 
  { 
    struct list *list; 
   
    // 為列表結(jié)構(gòu)分配內(nèi)存 
    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)

  /** 
   * 釋放整個(gè)列表 
   * 
   * T = O(N), N為列表長(zhǎng)度 
   */ 
  void listRelease(list *list) 
  { 
    unsigned long len; 
    listNode *current, *next; 
   
    current = list->head; 
    len = list->len; 
   
    while (len --) { 
      next = current->next; 
      // 如果列表有自帶的free方法，那么先對(duì)節(jié)點(diǎn)值調(diào)用它 
      if (list->free) list->free(current->value); 
      // 之后釋放節(jié)點(diǎn) 
      free(current); 
      current = next; 
    } 
    free(list); 
  }

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

  /** 
   * 新建一個(gè)包含給定value的節(jié)點(diǎn)，并將它加入到列表的表頭 
   * 
   * 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) { 
      // 第一個(gè)節(jié)點(diǎn) 
      list->head = list->tail = node; 
      node->prev = node->next = NULL; 
    } else { 
      // 不是第一個(gè)節(jié)點(diǎn) 
      node->prev = NULL; 
      node->next = list->head; 
      list->head->prev = node; 
      list->head = node; 
    } 
   
    list->len ++; 
   
    return list; 
  }

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

  /** 
   * 新建一個(gè)包含給定value的節(jié)點(diǎn)，并把它加入到列表的表尾 
   * 
   * 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) { 
      // 第一個(gè)節(jié)點(diǎn) 
      list->head = list->tail = node; 
      node->prev = node->next = NULL; 
    } else { 
      // 不是第一節(jié)點(diǎn) 
      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)

  /** 
   * 創(chuàng)建一個(gè)包含值value的節(jié)點(diǎn) 
   * 并根據(jù)after參數(shù)的指示，將新節(jié)點(diǎn)插入到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; 
      // 處理表尾節(jié)點(diǎn) 
      if (list->tail == old_node) { 
        list->tail = node; 
      } 
    } else { 
      // 插入到old_node之前 
      node->next = old_node; 
      node->prev = old_node->prev; 
      // 處理表頭節(jié)點(diǎn) 
      if (list->head == old_node) { 
        list->head = node; 
      } 
    } 
   
    // 更新前置節(jié)點(diǎn)和后繼節(jié)點(diǎn)的指針(這個(gè)地方很經(jīng)典，節(jié)約代碼) 
    if (node->prev != NULL) { 
      node->prev->next = node; 
    } 
    if (node->next != NULL) { 
      node->next->prev = node; 
    } 
   
    // 更新列表節(jié)點(diǎn) 
    list->len ++; 
   
    return list; 
  }

void listDelNode(list *list, listNode *node)

 /** 
   * 釋放列表中給定的節(jié)點(diǎn) 
   * 
   * T = O(1) 
   */ 
  void listDelNode(list *list, listNode *node) 
  { 
    // 處理前驅(qū)節(jié)點(diǎn)指針 
    if (node->prev) { 
      node->prev->next = node->next; 
    } else { 
      list->head = node->next; 
    } 
   
    // 處理后繼節(jié)點(diǎn) 
    if (node->next) { 
      node->next->prev = node->prev; 
    } else { 
      list->tail = node->prev; 
    } 
   
    // 釋放節(jié)點(diǎn)值 
    if (list->free) list->free(node->value); 
   
    // 釋放節(jié)點(diǎn) 
    free(node); 
   
    // 更新列表節(jié)點(diǎn)數(shù)目 
    list->len --; 
  }

迭代器
其實(shí)我對(duì)迭代器的概念非常陌生，因?yàn)槲沂羌僣程序員，不會(huì)c++，這里直接跟著學(xué)了！

Redis針對(duì)list結(jié)構(gòu)實(shí)現(xiàn)了一個(gè)迭代器，用于對(duì)鏈表進(jìn)行遍歷

迭代器的結(jié)構(gòu)定義如下：

  /** 
   * 鏈表迭代器 
   */ 
  typedef struct listIter { 
    // 下一節(jié)點(diǎn) 
    listNode *next; 
   
    // 迭代方向 
    int direction; 
  } listIter;

direction決定了迭代器是沿著next指針向后迭代，還是沿著prev指針向前迭代，這個(gè)值可以是adlist.h中的AL_START_HEAD常量或AL_START_TAIL常量：

  #define AL_START_HEAD 0 
  #define AL_START_TAIL 1

學(xué)習(xí)一下迭代器的api實(shí)現(xiàn)：

listIter *listGetIterator(list *list, int direction)

  /** 
   * 創(chuàng)建列表list的一個(gè)迭代器，迭代方向由參數(shù)direction決定 
   * 
   * 每次對(duì)迭代器listNext(),迭代器返回列表的下一個(gè)節(jié)點(diǎn) 
   * 
   * T = O(1) 
   */ 
  listIter *listGetIterator(list *list, int direction) 
  { 
    listIter *iter; 
   
    iter = (listIter *)malloc(sizeof(listIter)); 
    if (iter == NULL) 
      return NULL; 
   
    // 根據(jù)迭代器的方向，將迭代器的指針指向表頭或者表尾 
    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)

  /** 
   * 函數(shù)要么返回當(dāng)前節(jié)點(diǎn)，要么返回NULL，因此，常見(jiàn)的用法是： 
   * 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) { 
      // 根據(jù)迭代方向，選擇節(jié)點(diǎn) 
      if (iter->direction == AL_START_HEAD) 
        iter->next = current->next; 
      else 
        iter->next = current->prev; 
    } 
   
    return current; 
  }

您可能感興趣的文章: