? ? ? ? ?繼上次的redis源碼分析(一)之后，本人開始訂制著一份非常偉大的計劃-啃完redis源代碼，也對他進行了切塊劃分，鑒于本人目前對他的整個運行流暢還不特別清楚的情況下，所以決定第一個要解決的就是與邏輯無關的代碼，也就是一些基本模塊，因為是相互獨立的，所以不會影響整體的閱讀，所以第一個開刀的就是結構體模塊了。結構體模塊我劃分了差不多10個文件的樣子，今天看的主要是adlist.c的文件，收獲有如下 **1.真心的幫我把數據結構的鏈表操作復習了一遍** **2.還有給人感覺最深的就是函數編程的思想無處不在，并沒有明確的數據類型，結構體里的各種函數指針的調用，函數作為參數存在的頻率非常高** **3.讓我見識到了C語言中迭代器還能這么寫，像用過高級語言的java，C#語言的同學肯定感覺迭代器Iterator嘛，不很簡單嘛，一句話的事唄，但是C語言中沒有現成的方法，怎么實現，adlist.c給我們提供了一種很簡潔的寫法.** **下面給出我分析的2個文件，一個是.h頭文件，一個是.c的具體文件(我上面提到的3點可以著重看看出現的地方):** ~~~ /* adlist.h - A generic doubly linked list implementation * * Copyright (c) 2006-2012, Salvatore Sanfilippo <antirez at gmail dot com> * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: * * * Redistributions of source code must retain the above copyright notice, * this list of conditions and the following disclaimer. * * Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * Neither the name of Redis nor the names of its contributors may be used * to endorse or promote products derived from this software without * specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE * POSSIBILITY OF SUCH DAMAGE. */ #ifndef __ADLIST_H__ #define __ADLIST_H__ /* Node, List, and Iterator are the only data structures used currently. */ /* listNode結點 */ typedef struct listNode { //結點的前一結點 struct listNode *prev; //結點的下一結點 struct listNode *next; //Node的函數指針 void *value; } listNode; /* list迭代器，只能為單向 */ typedef struct listIter { //當前迭代位置的下一結點 listNode *next; //迭代器的方向 int direction; } listIter; /* listNode 列表 */ typedef struct list { //列表頭結點 listNode *head; //列表尾結點 listNode *tail; /* 下面3個方法為所有結點公用的方法，分別在相應情況下回調用 */ //復制函數指針 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) //獲取list長度 #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) //給點的結點的值，這個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); //創建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); //獲取列表給定方向上的迭代器 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 */ /* 定義2個迭代方向，從頭部開始往尾部，第二個從尾部開始向頭部 */ #define AL_START_HEAD 0 #define AL_START_TAIL 1 #endif /* __ADLIST_H__ */ ~~~ adlist.c: ~~~ /* adlist.c - A generic doubly linked list implementation * * Copyright (c) 2006-2010, Salvatore Sanfilippo <antirez at gmail dot com> * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: * * * Redistributions of source code must retain the above copyright notice, * this list of conditions and the following disclaimer. * * Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * Neither the name of Redis nor the names of its contributors may be used * to endorse or promote products derived from this software without * specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE * POSSIBILITY OF SUCH DAMAGE. */ #include <stdlib.h> #include "adlist.h" #include "zmalloc.h" /* Create a new list. The created list can be freed with * AlFreeList(), but private value of every node need to be freed * by the user before to call AlFreeList(). * * On error, NULL is returned. Otherwise the pointer to the new list. */ /* 創建結點列表 */ list *listCreate(void) { struct list *list; //申請空間，如果失敗了就直接返回NULL if ((list = zmalloc(sizeof(*list))) == NULL) return NULL; //初始化操作，頭尾結點，，3個公共的函數指針全部賦值為NULL list->head = list->tail = NULL; list->len = 0; list->dup = NULL; list->free = NULL; list->match = NULL; return list; } /* Free the whole list. * * This function can't fail. */ /* 釋放整個列表 */ void listRelease(list *list) { unsigned long len; listNode *current, *next; //找到當前結點，也就是頭結點 current = list->head; len = list->len; while(len--) { //while循環依次釋放結點 next = current->next; //如果列表有free釋放方法定義，每個結點都必須調用自己內部的value方法 if (list->free) list->free(current->value); //采用redis新定義的在zfree方式釋放結點，與zmalloc對應，不是free！！ zfree(current); current = next; } //最后再次釋放list同樣是zfree zfree(list); } /* Add a new node to the list, to head, contaning the specified 'value' * pointer as value. * * On error, NULL is returned and no operation is performed (i.e. the * list remains unaltered). * On success the 'list' pointer you pass to the function is returned. */ /* 列表添加頭結點 */ list *listAddNodeHead(list *list, void *value) { listNode *node; //定義新的listNode，并賦值函數指針 if ((node = zmalloc(sizeof(*node))) == NULL) return NULL; node->value = value; if (list->len == 0) { //當此時沒有任何結點時，頭尾結點是同一個結點，前后指針為NULL list->head = list->tail = node; node->prev = node->next = NULL; } else { //設置此結點next與前頭結點的位置關系 node->prev = NULL; node->next = list->head; list->head->prev = node; list->head = node; } //結點計數遞增并返回 list->len++; return list; } /* Add a new node to the list, to tail, containing the specified 'value' * pointer as value. * * On error, NULL is returned and no operation is performed (i.e. the * list remains unaltered). * On success the 'list' pointer you pass to the function is returned. */ /* 列表添加尾結點，操作大體上與增加頭結點一樣，不加以描述了 */ list *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結點的前面或后面插入新結點 */ list *listInsertNode(list *list, listNode *old_node, void *value, int after) { listNode *node; //新申請結點，并賦值好函數指針 if ((node = zmalloc(sizeof(*node))) == NULL) return NULL; node->value = value; if (after) { //如果是在目標結點的后面插入的情況，將新結點的next指針指向老結點的next node->prev = old_node; node->next = old_node->next; if (list->tail == old_node) { //如果老結點已經是最后一個結點了，則新的結點直接成為尾部結點 list->tail = node; } } else { //如果是在目標結點的前面插入的情況，將新結點的preview指針指向老結點的preview node->next = old_node; node->prev = old_node->prev; if (list->head == old_node) { //如果老結點已經是頭結點了，則新的結點直接成為頭部結點 list->head = node; } } //檢查Node的前后結點還有沒有未連接的操作 if (node->prev != NULL) { node->prev->next = node; } if (node->next != NULL) { node->next->prev = node; } list->len++; return list; } /* Remove the specified node from the specified list. * It's up to the caller to free the private value of the node. * * This function can't fail. */ /* 列表刪除某結點 */ void listDelNode(list *list, listNode *node) { if (node->prev) //如果結點prev結點存在，prev的結點的下一及誒單指向Node的next結點 node->prev->next = node->next; else //如果不存在說明是被刪除的是頭結點，則重新賦值Node的next為新頭結點 list->head = node->next; //后半操作類似 if (node->next) node->next->prev = node->prev; else list->tail = node->prev; //同樣要調用list的free函數 if (list->free) list->free(node->value); zfree(node); list->len--; } /* Returns a list iterator 'iter'. After the initialization every * call to listNext() will return the next element of the list. * * This function can't fail. */ /* 獲取列表呢迭代器 */ listIter *listGetIterator(list *list, int direction) { listIter *iter; //申請空間，失敗了就直接返回NULL if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL; if (direction == AL_START_HEAD) //如果方向定義的是從頭開始，則迭代器的next指針指向列表頭結點 iter->next = list->head; else //如果方向定義的是從尾開始，則迭代器的next指針指向列表尾結點 iter->next = list->tail; //賦值好迭代器方向并返回 iter->direction = direction; return iter; } /* Release the iterator memory */ /* 釋放迭代器內存 */ void listReleaseIterator(listIter *iter) { zfree(iter); } /* Create an iterator in the list private iterator structure */ /* 相當于重置迭代器為方向從頭開始 */ 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; } /* Return the next element of an iterator. * It's valid to remove the currently returned element using * listDelNode(), but not to remove other elements. * * The function returns a pointer to the next element of the list, * or NULL if there are no more elements, so the classical usage patter * is: * * iter = listGetIterator(list,<direction>); * while ((node = listNext(iter)) != NULL) { * doSomethingWith(listNodeValue(node)); * } * * */ /* 根據迭代器獲取下一結點 */ 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; } /* Duplicate the whole list. On out of memory NULL is returned. * On success a copy of the original list is returned. * * The 'Dup' method set with listSetDupMethod() function is used * to copy the node value. Otherwise the same pointer value of * the original node is used as value of the copied node. * * The original list both on success or error is never modified. */ /* 列表賦值方法，傳入的參數為原始列表 */ list *listDup(list *orig) { list *copy; listIter *iter; listNode *node; //如果創建列表失敗則直接返回 if ((copy = listCreate()) == NULL) return NULL; //為新列表賦值好3個函數指針 copy->dup = orig->dup; copy->free = orig->free; copy->match = orig->match; //獲得從頭方向開始的迭代器 iter = listGetIterator(orig, AL_START_HEAD); while((node = listNext(iter)) != NULL) { //從前往后遍歷結點 void *value; if (copy->dup) { //如果定義了列表復制方法，則調用dup方法 value = copy->dup(node->value); if (value == NULL) { //如果發生OOM內存溢出問題，直接釋放所有空間 listRelease(copy); listReleaseIterator(iter); return NULL; } } else //沒定義直接復制函數指針 value = node->value; if (listAddNodeTail(copy, value) == NULL) { //后面的結點都是從尾部逐一添加結點，如果內存溢出，同上操作 listRelease(copy); listReleaseIterator(iter); return NULL; } } //最后釋放迭代器 listReleaseIterator(iter); return copy; } /* Search the list for a node matching a given key. * The match is performed using the 'match' method * set with listSetMatchMethod(). If no 'match' method * is set, the 'value' pointer of every node is directly * compared with the 'key' pointer. * * On success the first matching node pointer is returned * (search starts from head). If no matching node exists * NULL is returned. */ /* 關鍵字搜索Node結點此時用到了list的match方法了 */ listNode *listSearchKey(list *list, void *key) { listIter *iter; listNode *node; //獲取迭代器 iter = listGetIterator(list, AL_START_HEAD); while((node = listNext(iter)) != NULL) { //遍歷循環 if (list->match) { //如果定義了list的match方法，則調用match方法 if (list->match(node->value, key)) { //如果方法返回true，則代表找到結點，釋放迭代器 listReleaseIterator(iter); return node; } } else { //如果沒有定義list 的match方法，則直接比較函數指針 if (key == node->value) { //如果相等，則代表找到結點，釋放迭代器 listReleaseIterator(iter); return node; } } } listReleaseIterator(iter); return NULL; } /* Return the element at the specified zero-based index * where 0 is the head, 1 is the element next to head * and so on. Negative integers are used in order to count * from the tail, -1 is the last element, -2 the penultimate * and so on. If the index is out of range NULL is returned. */ /* 根據下標值返回相應的結點*/ /*下標有2種表示形式，從頭往后一次0， 1， 2，...從后往前是 ...-3， -2， -1.-1為最后一個結點*/ listNode *listIndex(list *list, long index) { listNode *n; if (index < 0) { //如果index為負數，則從后往前數 index = (-index)-1; n = list->tail; while(index-- && n) n = n->prev; } else { //如果index為正數，則從前往后數 n = list->head; while(index-- && n) n = n->next; } return n; } /* Rotate the list removing the tail node and inserting it to the head. */ /* rotate操作其實就是把尾部結點挪到頭部，原本倒數第二個結點變為尾部結點 */ void listRotate(list *list) { listNode *tail = list->tail; //如果長度為不足，直接返回，之前宏定義的方法 if (listLength(list) <= 1) return; /* Detach current tail */ //替換新的尾部結點，原結點后挪一個位置 list->tail = tail->prev; list->tail->next = NULL; /* Move it as head */ //設置新結點 list->head->prev = tail; tail->prev = NULL; tail->next = list->head; list->head = tail; } ~~~ 其實目前網上的各種的解析都有吧，每個人閱讀帶給自己的感受是不一樣的，只有自己親手體驗過才叫真的體會過，閱讀代碼的確會給人很多啟發，非常嚴謹吧，每行代碼，抱著一種學習，欣賞的心態看待代碼。不錯，良好的開始，繼續堅持。