redis 學習筆記（一）

1.adlist.h

準備花點時間將redis的源代碼從頭到尾學習一邊，一邊鍛煉自己讀代碼的能力，一邊學習大牛們是如何寫出來漂亮的代碼，而且能從底層代碼實現中將自己一直以來欠缺的那一部分知識體系補全，所以準備從redis入手，再學習apache thrift，我想等都學習完一遍之后，能夠將自己工作一年半以來零碎的一些知識技能變得更加系統化一點

redis源碼中分為結構體，數據操作，工具，事件，基本信息，兼容，主程序，網絡，封裝類等，我準備從最基礎的結構體入手，大致的看了一下，redis的結構體基本上基于list和hash，一個一個順著學吧，今天就是adlist了

結構體：

typedef struct listNode{

struct listNode *PRev;//指向前一個節點

struct listNode *next;//指向后一個節點

void *value;//node值的指針

} listNode；

第一個結構體應該定義的是鏈表的節點，從結構體的內容可以猜測adlist是一個雙向列表，prev是指向前一個節點的指針，next是指向后一個節點的指針，而value暫時不知道是干什么的

typedef struct listIter{

listNode *next;//指向當前迭代位置的下一個節點，隨迭代器方向而變化

int direction;//迭代器的方向

}listIter;

從名字來看，第二個結構體應該是一個迭代器，那么next便是指向下一個節點，direction從字面意思應該是迭代器的方向，由于list是一個雙向鏈表，那么可以猜測listIter可以實現正向迭代器和反向迭代器，相比于C++的iterator基類，這應該是用C實現的一個簡易的迭代器了

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;

結構體list應該就是一個雙向列表，head是頭節點，tail是尾節點，然后dup，free和match應該就是C風格的list的成員函數,len是鏈表的長度

從adlist.h文件里面定義了如下函數,從字面分析其實現：

list *listCreate(void);//創建list

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);//獲取迭代器，返回一個listIter結構體指針

listNode *listNext(listIter *iter); //獲取下個節點

void listReleaseIterator(listIter *iter);//釋放迭代器指針

list *listDup(list *orig); //列表復制

listNode *listSearchKey(list *list, void *key);//在list中查找key，并返回節點

listNode *listIndex(list *list, long index);//根據索引查找節點

void listRewind(list *list, listIter *li);//重置迭代器

void listRewindTail(list *list, listIter *li);//從尾部重置迭代器

void listRotate(list *list);//將鏈表的尾節點置于隊首

此外，在adlist.h中定義了一系列的宏定義，不再一一列述，不過學習了程序員大牛們的編碼習慣，適當的定義宏使得代碼變得更易讀

再看adlist.c中對于函數的具體實現（感覺看完之后，把大學學鏈表的時候的C實現撿回來了…）:

//返回一個list結構體指針

list *listCreate(void){

//聲明一個list結構體

struct list *list;

//為list結構體分配內存，zmalloc是redis文件下面zmalloc.h里面定義的方法，跳過去看了一下，看不懂，里面很多宏定義，想想以前看別人代碼就是懶得看些，所以賴著性子看看

/*

void *zmalloc(size_t size){

//上文中宏PREFIX_SIZE為0，為ptr分配了一個size大小的內存空間，size_t的實現代碼為typedef unsigned int size_t;

void *ptr = malloc(size + PREFIX_SIZE);

if(!ptr) zmalloc_oom_handler(size);//如果ptr為NULL，返回錯誤，abort

#ifdef HAVE_MALLOC_SIZE//上文定義

//返回所申請的內存空間

update_zmalloc_stat_alloc(zmalloc_size(ptr));

return ptr;

}

*/

if((list = zmalloc(sizeof(*list))) == NULL) return NULL;

//將頭節點和尾節點都置為NULL

list->head = list->tail = NULL;

//將鏈表長度置為0

list->len = 0;

//將struct的成員函數指針置為NULL

list->dup = NULL;

list->free = NULL;

list->match  = NULL;

//返回一個空的list指針

return list;

}

void listRelease(list *list){

unsigned long len;

listNode *current, *next;//兩個節點指針，一個指向當前節點，一個指向下一個節點

current = list->head;//將起點置在隊首

len = list->len;

//遍歷鏈表

while(len—){

//next為current所指向的下一個節點

next = current->next;

//判斷鏈表是否有free方法，調用free方法,釋放listNode的value函數指針，這里并不是很清楚value是干什么的，我理解可能在其他文件里面有實現

if(list->free) list->free(current->value);

//調用zmalloc.h中的zfree方法釋放掉current指針

zfree(current);

//指針后移

current = next;

}

//釋放鏈表指針

zfree(list);

}//個人認為這里可以每次釋放一個node，便使list->len—，且重置head指針,這樣如果循環釋放到一半程序崩潰的話，還能保證鏈表的完整性

 繼續往下看

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

listNode *node;

//分配內存檢查

if((node = zmalloc(sizeof(*node))) == NULL)return NULL;

//這里理解了value的含義，在node中設置為void*是為了適配不同指針類型，然后value就是node的值的指針類型

node->value = value;

//如果鏈表為空，那么插入的節點就是鏈表的唯一一個節點，由于是雙向鏈表，所以需要注意前后指針的重置

if(list->len == 0){

list->head = list->tail = node;

node->prev = node->next = NULL;

} else{//如果不是空，那么就在鏈表最前面插入，然后置新節點為head

node->prev = NULL;

node->next = list->head;

list->head->prev = node;

list->head = node;

}

//鏈表長度加1

list->len ++;

return list;

}

//功能與上面類似，只不過實現的是在鏈表尾部添加

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

listNode *node;

if((node = zmalloc(sizeof(*node))) == NULL) return NULL;

node->value = value;

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;

}

// old_node應該指的是目標節點，after應該是指是否在后面插入

void *listInsertNode(list *list, listNode *old_node, void *value, int after){

listNode *node;

//如果新節點分配內存失敗，返回null

if((node = zmalloc(sizeof(*node))) == NULL)return NULL;

//為新節點的value賦值

node->value = value;

//如果是在目標節點身后插入，那么要注意移動目標節點的next指針

if(after){

node->prev = old_node;

node->next = old_node->next;

//我覺得如果是我在寫代碼會遺漏這一個條件判斷，如果是尾節點，那么需要重置list的尾指針位置

if(list->tail = old_node){

list->tail = node;

}

}else{//如果在前插入，與上面相反

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;

}

lits->len++;

return list;

}

void listDelNode(list *list, listNode *node){

//判斷如果目標節點有前置指針，那么使前節點指向目標節點的身后

if(node->prev){

node->prev->next = node->next;

}else{//如果目標節點是頭指針，那么直接標識next為頭部（我寫代碼絕對寫不得這樣簡潔易懂）

list->head = node->next;

}

//處理尾部，與上文類似

if(node->next){

node->next->prev = node->prev;

}else{

list->tail = node->prev;

}

//處理前后節點是相互獨立的，這樣寫就不用單獨將首尾列出來處理一遍

if(list->free) list->free(node->value);

//釋放節點

zfree(node);

list->len—;

}

//獲取一個list迭代器指針

listiter *listGetIteraor(list *list, int dirction){

//申明一個迭代器指針

listIter *iter;

//判斷內存分配，人家每一個臨界條件都注意得特別好

if((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;

//判斷方向，如果dire為0，那么從頭開始遍歷

if(direction == AL_START_HEAD) iter->next = list->head;

//如果是1，從尾部開始

else iter->next = list->tail;

iter->direction  = direction;

return tier;

} //迭代器區別與listNode，所以這里的iter->next可以理解為存在于list維度之外的一層

void listReleaseIterator(listIter *iter){

zfree(iter);//zfree封裝了redis自己的free方法,free方法只釋放用malloc或者alloc操作分配的內存

}

//對一個迭代器指針的重置操作，但是迭代器必須先初始化，這個函數置首部

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;

}

//獲取迭代器指向的節點

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;

} //我理解這里其實是實現了C++ Iterator中iterator++/—的操作

//鏈表的復制操作

list *listDup(list *orig){

list *copy;//復制后的指針

listIter iter;//迭代器指針

listNode *node;

//判斷copy是否創建成功

if((copy = listCreate()) == NULL)return NULL;

//復制相關函數指針

copy->dup = orig->dup;

copy->free = orig->free;

copy->match = orig->match;

//迭代器置首部

listRewind(orig, &iter);

//在C++里面相當于iter++!=list.end();

while((node = listNext(&iter)) != NULL){

void *value;

if(copy->dup){

value = copy->dup(node->value);

if(value == NULL){

listRelease(copy);

return NULL;

}

}else

value = node->value;

//從新鏈表的尾部開始插入節點

if(listAddNodeTail(copy, value) == NULL){

listRelease(copy);

return NULL;

}

}

//返回新的鏈表

return copy;

}

//一個雙向鏈表的查詢操作，自己也寫過無數遍，感覺就是沒有別人寫得清楚

listNode *listSearchKey(list *list, void *key){

listIter iter;

listNode *node;

//首部迭代器

listRewind(list, &iter);

//同樣的一個迭代器向后迭代的操作

while((node = listNex(&iter)) != NULL){

//調用了match方法，這里用了這么多函數指針我理解為redis可能有很多的數據類型是基于list實現的，所以根據不同的類型實現了不同的方法

if(list->match){

if(list->match(node->value, key)){

return node;

}

}else{//簡單的比較

if(key == node->value){

return node;

}

}

}

return NULL;

}

//這個函數看了幾遍才看懂,而且是看了英文注釋，感覺英文水平飆升…根據index查找節點，正數從前往后，負數從后往前

listNode *listIndex(list *list, long index){

listNode *n;

//負數，從尾部開始遍歷

if(index < 0){

index = (-index)-1;

n = list->tail;

while(index— && n) n = n->prev;

}else{

n = list>head;

while(index— && n) n = n->next;

}

return n;

} // 想當于給一個非順序存儲的鏈表給了一個根據下標查找的操作

將鏈表尾部放在首部前面

void listRotate(list *list){

//定義尾部

listNode *tail = list->tail;

// 如果長度是1，那么尾部就是首部，無意義

if(listLength(list) <= 1)return;

//將尾部重置為之前尾部的prev

list->tail = tail->prev;

list->tail->next = NULL;

//將之前的尾部放在list->head之前作為list的首部

list->head->prev = tail;

tail->prev = NULL;

tail->next = list->head;

list->head = tail;

}

總結： 1.回顧了list鏈表的一些底層操作代碼，順帶的一下子將例如棧，隊列，以及二叉樹的操作回憶了一遍；

2.無腦的用C++的庫用多了之后，都完全覺得所有的組件方法等天生就有，然而現在重新改變了這一個觀點，任何邏輯操作都是代碼寫出來的，底層的也好，業務層也好；

3.多學習別人的代碼果然很有好處，雖然在這一章感覺閱讀難度不大，但是對于編碼習慣也好，還是思維也好，給自己有一定的沖擊，先易后難，希望自己堅持