Redis中雙鏈表實現(xiàn)的基本結(jié)構(gòu)：
1.節(jié)點結(jié)構(gòu)
|
1
2
3
4
5
|
typedef struct listNode { struct listNode *prev; //前向節(jié)點 struct listNode *next; //后向節(jié)點 void *value; //該節(jié)點的值} listNode; |
2.雙向鏈表結(jié)構(gòu)
|
1
2
3
4
5
6
7
8
|
typedef struct list { listNode *head; //頭節(jié)點 listNode *tail; //尾節(jié)點 void *(*dup)(void *ptr); //復制函數(shù) void (*free)(void *ptr); //釋放函數(shù) int (*match)(void *ptr, void *key); //匹配函數(shù)，查找節(jié)點使用 unsigned long len; //雙向鏈表的長度即節(jié)點的個數(shù)} list; |
3.雙向鏈表遍歷器
|
1
2
3
4
5
6
7
8
9
|
typedef struct listIter { listNode *next; //下一個節(jié)點 int direction;} listIter; 方向定義 #define AL_START_HEAD 0 //向前查找 #define AL_START_TAIL 1 //向后查找 |
4.宏定義函數(shù)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
#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ù)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
list *listCreate(void); //創(chuàng)建一個新的鏈表。該鏈表可以使用AlFree（）方法釋放。 //但使用AlFree（）方法前需要釋放用戶釋放私有節(jié)點的值。 //如果沒有創(chuàng)建成功，返回null；創(chuàng)建成功則返回指向新鏈表的指針。void listRelease(list *list); //釋放整個鏈表，此函數(shù)不會執(zhí)行失敗。調(diào)用zfree(list *list)方法,定義在Zmalloc.c中。list *listAddNodeHead(list *list, void *value); //向鏈表頭部中增加一個節(jié)點list *listAddNodeTail(list *list, void *value); //向鏈表尾部增加一個節(jié)點list *listInsertNode(list *list, listNode *old_node, void *value, int after);//向某個節(jié)點位置插入節(jié)點 after為方向void listDelNode(list *list, listNode *node);//從鏈表上刪除特定節(jié)點，調(diào)用者釋放特定私用節(jié)點的值。 //該函數(shù)不會執(zhí)行失敗listIter *listGetIterator(list *list, int direction);//返回某個鏈表的迭代器。 //迭代器的listNext（）方法會返回鏈表的下個節(jié)點。direction是方向 //該函數(shù)不會執(zhí)行失敗。listNode *listNext(listIter *iter); void listReleaseIterator(listIter *iter); //釋放迭代器的內(nèi)存。list *listDup(list *orig); //復制整個鏈表。當內(nèi)存溢出時返回null，成功時返回原鏈表的一個備份 //不管該方法是否執(zhí)行成功，原鏈表不會改變。listNode *listSearchKey(list *list, void *key); //從特定的鏈表查找key。成功則返回第一個匹配節(jié)點的指針 //如果沒有匹配，則返回null。listNode *listIndex(list *list, long index); //序號從0開始，鏈表的頭的索引為0.1為頭節(jié)點的下個節(jié)點。一次類推。 //負整數(shù)用來表示從尾部開始計數(shù)。-1表示最后一個節(jié)點，-2倒數(shù)第二個節(jié)點 //如果超過鏈表的索引，則返回nullvoid 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é)點并插入頭部。 |
list結(jié)構(gòu)和listNode結(jié)構(gòu)的API
list和listNode都有它們自己的一族API，這里貼出來學習一下redis的源碼(ps:下面的代碼都是我仿照redis改寫能直接編譯運行的代碼)
list *listCreate(void)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
/** * 創(chuàng)建一個新列表 * * 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)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
/** * 釋放整個列表 * * T = O(N), N為列表長度 */void listRelease(list *list) { unsigned long len; listNode *current, *next; current = list->head; len = list->len; while (len --) { next = current->next; // 如果列表有自帶的free方法，那么先對節(jié)點值調(diào)用它 if (list->free) list->free(current->value); // 之后釋放節(jié)點 free(current); current = next; } free(list); } |
list *listAddNodeHead(list *list, void *value)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
/** * 新建一個包含給定value的節(jié)點，并將它加入到列表的表頭 * * 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) { // 第一個節(jié)點 list->head = list->tail = node; node->prev = node->next = NULL; } else { // 不是第一個節(jié)點 node->prev = NULL; node->next = list->head; list->head->prev = node; list->head = node; } list->len ++; return list; } |
list *listAddNodeTail(list *list, void *value)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
/** * 新建一個包含給定value的節(jié)點，并把它加入到列表的表尾 * * 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) { // 第一個節(jié)點 list->head = list->tail = node; node->prev = node->next = NULL; } else { // 不是第一節(jié)點 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)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
/** * 創(chuàng)建一個包含值value的節(jié)點 * 并根據(jù)after參數(shù)的指示，將新節(jié)點插入到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é)點 if (list->tail == old_node) { list->tail = node; } } else { // 插入到old_node之前 node->next = old_node; node->prev = old_node->prev; // 處理表頭節(jié)點 if (list->head == old_node) { list->head = node; } } // 更新前置節(jié)點和后繼節(jié)點的指針(這個地方很經(jīng)典，節(jié)約代碼) if (node->prev != NULL) { node->prev->next = node; } if (node->next != NULL) { node->next->prev = node; } // 更新列表節(jié)點 list->len ++; return list; } |
void listDelNode(list *list, listNode *node)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
/** * 釋放列表中給定的節(jié)點 * * T = O(1) */ void listDelNode(list *list, listNode *node) { // 處理前驅(qū)節(jié)點指針 if (node->prev) { node->prev->next = node->next; } else { list->head = node->next; } // 處理后繼節(jié)點 if (node->next) { node->next->prev = node->prev; } else { list->tail = node->prev; } // 釋放節(jié)點值 if (list->free) list->free(node->value); // 釋放節(jié)點 free(node); // 更新列表節(jié)點數(shù)目 list->len --; } |
迭代器
其實我對迭代器的概念非常陌生，因為我是純c程序員，不會c++，這里直接跟著學了！
Redis針對list結(jié)構(gòu)實現(xiàn)了一個迭代器，用于對鏈表進行遍歷
迭代器的結(jié)構(gòu)定義如下：
|
1
2
3
4
5
6
7
8
9
10
|
/** * 鏈表迭代器 */typedef struct listIter { // 下一節(jié)點 listNode *next; // 迭代方向 int direction; } listIter; |
direction決定了迭代器是沿著next指針向后迭代，還是沿著prev指針向前迭代，這個值可以是adlist.h中的AL_START_HEAD常量或AL_START_TAIL常量：
|
1
2
|
#define AL_START_HEAD 0 #define AL_START_TAIL 1 |
學習一下迭代器的api實現(xiàn)：
listIter *listGetIterator(list *list, int direction)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
/** * 創(chuàng)建列表list的一個迭代器，迭代方向由參數(shù)direction決定 * * 每次對迭代器listNext(),迭代器返回列表的下一個節(jié)點 * * 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)
|
1
2
3
4
5
6
7
8
9
10
|
/** * 將迭代器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)
|
1
2
3
4
5
6
7
8
9
10
|
/** * 將迭代器iter的迭代指針倒回list的表尾 * * T = O(1) */void listRewindTail(list *list, listIter *li) { li->next = list->tail; li->direction = AL_START_TAIL; } |
listNode *listNext(listIter *iter)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
/** * 函數(shù)要么返回當前節(jié)點，要么返回NULL，因此，常見的用法是： * 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é)點 if (iter->direction == AL_START_HEAD) iter->next = current->next; else iter->next = current->prev; } return current; } |
