當前位置:網站首頁>Redis源碼學習(25),雙端鏈錶學習,adlist.h

Redis源碼學習(25),雙端鏈錶學習,adlist.h

2022-05-14 10:51:42無痕之意

前言

  學習完SDS之後,我們了解了Redis字符串的底層數據結構,對Redis在提昇性能的一些處理上有了一些簡單的了解,這是一個非常不錯的開始,但這還是冰山一角,我們還有很多知識我們需要去學習。

  相信學習完SDS之後,大家和我一樣應該有了不少信心,數據結構也不是那麼難對吧,接下來我們要學習的是雙端鏈錶,它是實現列錶的底層數據結構之一,只要我們弄清楚雙端鏈錶再回過頭去溫習下之前我們學習過的列錶的一些方法,想必就能更加清楚了。

  Redis將雙端鏈錶的代碼放在了adlist.h和adlist.c兩個文件中,這裏有個小疑問為什麼文件名是adlist呢?其實可以從兩個源代碼中的開頭找到答案。

	 adlist.h - A generic doubly linked list implementation

  翻譯過來的意思,一個通用的雙向鏈錶實現

1 雙端鏈錶

  學習過數據結構的小夥伴應該很清楚雙端鏈錶是個啥東西,這裏就簡單的概述一下雙端鏈錶,先有一個簡單的概念再看代碼就能更容易一些。

  首先鏈錶類似我們平常看到的鏈條一樣,是用一個個的節點連接起來的東西。

  清楚了鏈錶是什麼東西之後,再來理解雙端鏈錶就方便了,雙端鏈錶是指每個節點都有指向前一個節點和後一個節點的指針,這樣的話鏈錶就可以在兩個方向上遍曆,那單鏈錶就一個指向後一個節點的指針也就是只能向後遍曆。

2 結構體定義

  說的再多不如直接上代碼,讓我們來看看Redis中是怎麼實現的吧。

/* Node, List, and Iterator are the only data structures used currently. */

//雙端鏈錶節點結構體定義
typedef struct listNode {
    
    struct listNode *prev;//上一個節點的指針
    struct listNode *next;//下一個節點的指針
    void *value;//指向值的指針
} listNode;

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;

  這裏有兩個結構體,分別是listNode 和 list ,一個是鏈接節點,一個是鏈錶。

  鏈錶節點中總共有3個屬性,一個是指向上一個節點的指針,一個是指向下一個節點的指針,最後還有一個指向值的指針,有了這三個屬性就可以組織起一個簡單的鏈錶節點,同時也能將其他節點串聯起來。

  鏈錶中總共有6個屬性,前面兩個好理解,一個是指向頭節點的指針,一個指向尾節點指針,後面3個有點難理解,目前只要先知道指向3個函數就可以,分別是複制、釋放、匹配函數。最後還有一個節點數量的屬性,顯然通過這個屬性可以快速獲取鏈錶節點的數量。

3 adlist.h 學習

3.1 adlist.h 源代碼

#ifndef __ADLIST_H__
#define __ADLIST_H__

/* Node, List, and Iterator are the only data structures used currently. */

typedef struct listNode {
    
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

typedef struct listIter {
    
    listNode *next;
    int direction;
} listIter;

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;

/* Functions implemented as macros */
#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)

/* Prototypes */
list *listCreate(void);
void listRelease(list *list);
list *listAddNodeHead(list *list, void *value);
list *listAddNodeTail(list *list, void *value);
list *listInsertNode(list *list, listNode *old_node, void *value, int after);
void listDelNode(list *list, listNode *node);
listIter *listGetIterator(list *list, int direction);
listNode *listNext(listIter *iter);
void listReleaseIterator(listIter *iter);
list *listDup(list *orig);
listNode *listSearchKey(list *list, void *key);
listNode *listIndex(list *list, long index);
void listRewind(list *list, listIter *li);
void listRewindTail(list *list, listIter *li);
void listRotate(list *list);

/* Directions for iterators */
#define AL_START_HEAD 0
#define AL_START_TAIL 1

#endif /* __ADLIST_H__ */

3.2 listIter

  在源代碼中除了能看到listNode和list還發現一個結構體,listIter這是一個鏈錶迭代器的結構體的定義,用於遍曆鏈錶的時候使用。

typedef struct listIter {
    
    listNode *next;
    int direction;
} listIter;

/* Directions for iterators */
#define AL_START_HEAD 0
#define AL_START_TAIL 1

   listIter中只有兩個屬性,一個指向下一個節點的指針,一個是錶示方向的值,方向的定義分別是AL_START_HEAD 和 AL_START_TAIL ,錶示從頭部開始還是尾部開始。

3.2 宏方法

  在源代碼中直接使用宏定義了一些方法,讓我們來看下這些方法大概做什麼的。

#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)
  • listLength:獲取列錶節點的數量,返回列錶的len屬性。
  • listFirst:獲取列錶頭節點的指針,返回列錶的head屬性。
  • listLast:獲取列錶尾節點的指針,返回列錶的tail屬性。
  • listPrevNode:獲取上一個節點的指針,返回列錶的prev屬性。
  • listNextNode:獲取下一個節點的指針,返回列錶的next屬性。
  • listNodeValue:獲取節點值的指針,返回列錶的value屬性。
  • listSetDupMethod:設置複制函數。
  • listSetFreeMethod:設置釋放函數。
  • listSetMatchMethod:設置匹配函數。
  • listGetDupMethod:獲取複制函數。
  • listGetFree:獲取釋放函數。
  • listGetMatchMethod:獲取匹配函數。

3.3 方法簽名

list *listCreate(void);
void listRelease(list *list);
list *listAddNodeHead(list *list, void *value);
list *listAddNodeTail(list *list, void *value);
list *listInsertNode(list *list, listNode *old_node, void *value, int after);
void listDelNode(list *list, listNode *node);
listIter *listGetIterator(list *list, int direction);
listNode *listNext(listIter *iter);
void listReleaseIterator(listIter *iter);
list *listDup(list *orig);
listNode *listSearchKey(list *list, void *key);
listNode *listIndex(list *list, long index);
void listRewind(list *list, listIter *li);
void listRewindTail(list *list, listIter *li);
void listRotate(list *list);
  • listCreate:創建一個鏈錶。
  • listRelease:釋放一個鏈錶。
  • listAddNodeHead:向列錶頭部添加一個節點。
  • listAddNodeTail:向列錶尾部添加一個節點。
  • listInsertNode:向列錶中某個節點前後添加一個節點。
  • listDelNode:删除一個節點。
  • listGetIterator:獲取列錶迭代器。
  • listNext:獲取下一個列錶。
  • listReleaseIterator:釋放列錶迭代器。
  • listDup:複制一個列錶。
  • listSearchKey:搜索某個節點。
  • listIndex:通過索引返回一個節點。
  • listRewind:迭代器重置到頭部。
  • listRewindTail:迭代器重置到尾部。
  • listRotate:鏈錶翻轉 。

4 學習總結

  1. listNode 是鏈錶節點的結構體定義,它有三個屬性,分別是上一個節點的指針、下一個節點的指針、值的指針。
  2. list 是鏈錶的結構體定義,它有六個熟悉,分別頭尾節點的指針,還有三個函數的指針,最後是列錶節點的數量。
  3. listIter是鏈錶迭代器的結構體定義,它有兩個熟悉,一個是下一個節點的指針,另一個是遍曆方向。
  4. sds.h 裏有一些宏方法,例如listLength、listFirst、listLast、listPrevNode、listNextNode、listNodeValue。

版權聲明
本文為[無痕之意]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2022/134/202205141050489885.html

隨機推薦