當前位置:網站首頁>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 學習總結
- listNode 是鏈錶節點的結構體定義,它有三個屬性,分別是上一個節點的指針、下一個節點的指針、值的指針。
- list 是鏈錶的結構體定義,它有六個熟悉,分別頭尾節點的指針,還有三個函數的指針,最後是列錶節點的數量。
- listIter是鏈錶迭代器的結構體定義,它有兩個熟悉,一個是下一個節點的指針,另一個是遍曆方向。
- sds.h 裏有一些宏方法,例如listLength、listFirst、listLast、listPrevNode、listNextNode、listNodeValue。
版權聲明
本文為[無痕之意]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2022/134/202205141050489885.html
邊欄推薦
- 【服務器數據恢複】硬盤壞道和不穩定扇區導致服務器崩潰的數據恢複案例
- 性能測試報告編寫技巧
- ASP.NET對Cookie的操作方法有哪些
- SAP UI5 應用開發教程之八十七 - 如何讓 SAP UI5 Mock 服務器支持自定義 url 參數試讀版
- Redis基礎之溫故
- 神經網絡中的反向傳播&&參數更新
- 深度學習基礎知識點(一)CNN卷積神經網絡——1.卷積方面的原理
- 從PlatEMO中提取真實PF前沿
- G020-OP-INS-RHEL-02 RedHat OpenStack 發放雲主機(命令行)
- 解决報錯: AttributeError: module ‘distutils‘ has no attribute ‘version‘,親測有效
猜你喜歡
隨機推薦
- c# 獲取枚舉描述的擴展方法
- 應如何認定解除合同通知的效力?
- 遊戲行業實戰案例5:玩家在線分布
- 【LeetCode】Day59-醜數 & 不同的二叉搜索樹
- CTFSHOW MISC入門
- 【國產免費】分布式作業批量處理平臺TASKCTL驗證的不同方式
- 數學建模學習(66):支持向量機 (SVM)案例實戰
- Thanos Sidecar組件
- Meta AI 宣布對人腦和語言處理進行長期研究
- 檢討書範文生成微信小程序工具源碼-支持流量主
- 元組類型(C# 參考)
- PTC:元宇宙引發醫療設備研發重大變革
- 面試題 01.05. 一次編輯 / 劍指 Offer II 041. 滑動窗口的平均值
- 華為機試第十一題:HJ11 數字顛倒
- Pascal VOC2012數據集
- unzip命令
- flink(scala版)學習一之常用的source
- [電路]7-實際電源模型和等效變換
- Go語言type自定義類型哦
- Pytorch和GPU有關操作(CUDA)
- 不均衡樣本集的重采樣
- uni-app技術分享| uni-app轉小程序-實時消息
- SQL中某個字段大於等於且不等於某值該如何寫
- 【Leetcode】442. 數組中重複的數據
- 2022年為什麼降薪也要跳槽?機會比漲薪很重要?
- 工作流結合動態錶單的工作流程
- 為什麼要使用.NET5?.NET5是未來!
- (pycharm)安裝nltk包
- 安裝Apache
- 利用循環輸入輸出數組(簡便易學)利用循環設置函數
- 雲原生時代的搜索服務算力管理
- 證券投資基金的監管
- ArrayList循環删除元素的常見問題及解决方法
- Stack Overflow 上最熱門的 10 個 Kotlin 問題
- 555 定時器的時間計算
- 二叉樹的最近公共祖先
- 模擬卷Leetcode【普通】931. 下降路徑最小和
- C語言 數組(一維數組 · 二維數組)
- NFC之華為AIPASS認證:測試用例簡介
- 622. 設計循環隊列