adlist是redis自己是实现的一个通用的双向链表。
------------------------------------------------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; 双向链表，存的结构是一个指针void
*
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
int
len;
} list; 链表本身的结构，头、尾指针，同时一个函数指针dup用于在复制链表（list or listNode
?
）调用，一个函数指针free在释放链表时调用，一个函数指针match用来作匹配时调用，以及一个记录链表长度的字段；注意三个函数指针是list的成员，也就是被所有list node共用，因此listNode应该具有共性。
/*
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)) set三个函数指针的方法
#define
listGetDupMethod(l) ((l)->dup)
#define
listGetFree(l) ((l)->free)
#define
listGetMatchMethod(l) ((l)->match) get三个函数指针的方法
/*
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,
int
index);
void
listRewind(list *list, listIter *
li);
void
listRewindTail(list *list, listIter *
li);
/*
Directions for iterators
*/
#define
AL_START_HEAD 0
#define
AL_START_TAIL 1 定义迭代器方向
#endif
/* __ADLIST_H__ */
------------------------------------------------adlist.c---------------------------------------------------
1
#include <stdlib.h>
2
#include
"
adlist.h
"
3
#include
"
zmalloc.h
" //redis对内存分配库函数的一个封装，用于stat目的
4
5
/*
Create a new list. The created list can be freed with
6
* AlFreeList(), but private value of every node need to be freed
7
* by the user before to call AlFreeList().
8
*
9
* On error, NULL is returned. Otherwise the pointer to the new list.
*/
10
list *listCreate(
void
)
11
{
12
struct
list *
list;
13
14
if
((list = zmalloc(
sizeof
(*list))) ==
NULL)
15
return
NULL;
16
list->head = list->tail =
NULL;
17
list->len =
0
;
18
list->dup =
NULL;
19
list->free =
NULL;
20
list->match =
NULL;
21
return
list;
22
} //这个函数创建的list是个裸的list，三个函数指针需要自行调用set赋值
23
24
/*
Free the whole list.
25
*
26
* This function can't fail.
*/
27
void
listRelease(list *
list)
28
{
29
unsigned
int
len;
30
listNode *current, *
next;
31
32
current = list->
head;
33
len = list->
len;
34
while
(len--
) {
35
next = current->
next;
36
if
(list->free) list->free(current->
value); //
37
zfree(current);
38
current =
next;
39
}
40
zfree(list);
41
} //先用free释放listNode中保存的元素，然后释放结点，最后释放链表本身。在链表操作中，注意在释放当前结点时，需要保存后续结点的值
42
43
/*
Add a new node to the list, to head, contaning the specified 'value'
44
* pointer as value.
45
*
46
* On error, NULL is returned and no operation is performed (i.e. the
47
* list remains unaltered).
48
* On success the 'list' pointer you pass to the function is returned.
*/
49
list *listAddNodeHead(list *list,
void
*
value)
50
{
51
listNode *
node;
52
53
if
((node = zmalloc(
sizeof
(*node))) ==
NULL)
54
return
NULL;
55
node->value =
value;
56
if
(list->len ==
0
) {
57
list->head = list->tail =
node;
58
node->prev = node->next =
NULL;
59
}
else
{
60
node->prev =
NULL;
61
node->next = list->
head;
62
list->head->prev =
node;
63
list->head =
node;
64
}
65
list->len++
;
66
return
list;
67
}
68
69
/*
Add a new node to the list, to tail, contaning the specified 'value'
70
* pointer as value.
71
*
72
* On error, NULL is returned and no operation is performed (i.e. the
73
* list remains unaltered).
74
* On success the 'list' pointer you pass to the function is returned.
*/
75
list *listAddNodeTail(list *list,
void
*
value)
76
{
77
listNode *
node;
78
79
if
((node = zmalloc(
sizeof
(*node))) ==
NULL)
80
return
NULL;
81
node->value =
value;
82
if
(list->len ==
0
) {
83
list->head = list->tail =
node;
84
node->prev = node->next =
NULL;
85
}
else
{
86
node->prev = list->
tail;
87
node->next =
NULL;
88
list->tail->next =
node;
89
list->tail =
node;
90
}
91
list->len++
;
92
return
list;
93
}
94
95
list *listInsertNode(list *list, listNode *old_node,
void
*value,
int
after) {
96
listNode *
node;
97
98
if
((node = zmalloc(
sizeof
(*node))) ==
NULL)
99
return
NULL;
100
node->value =
value;
101
if
(after) {
102
node->prev =
old_node;
103
node->next = old_node->
next;
104
if
(list->tail ==
old_node) {
105
list->tail =
node;
106
}
107
}
else
{
108
node->next =
old_node;
109
node->prev = old_node->
prev;
110
if
(list->head ==
old_node) {
111
list->head =
node;
112
}
113
}
114
if
(node->prev !=
NULL) {
115
node->prev->next =
node;
116
}
117
if
(node->next !=
NULL) {
118
node->next->prev =
node;
119
}
120
list->len++
;
121
return
list;
122
}
123
124
/*
Remove the specified node from the specified list.
125
* It's up to the caller to free the private value of the node.
126
*
127
* This function can't fail.
*/
128
void
listDelNode(list *list, listNode *
node)
129
{
130
if
(node->
prev)
131
node->prev->next = node->
next;
132
else
133
list->head = node->
next;
134
if
(node->
next)
135
node->next->prev = node->
prev;
136
else
137
list->tail = node->
prev;
138
if
(list->free) list->free(node->
value);
139
zfree(node);
140
list->len--
;
141
}
142
143
/*
Returns a list iterator 'iter'. After the initialization every
144
* call to listNext() will return the next element of the list.
145
*
146
* This function can't fail.
*/
147
listIter *listGetIterator(list *list,
int
direction)
148
{
149
listIter *
iter;
150
151
if
((iter = zmalloc(
sizeof
(*iter))) == NULL)
return
NULL;
152
if
(direction ==
AL_START_HEAD)
153
iter->next = list->
head;
154
else
155
iter->next = list->
tail;
156
iter->direction =
direction;
157
return
iter;
158
}
159
160
/*
Release the iterator memory
*/
161
void
listReleaseIterator(listIter *
iter) {
162
zfree(iter);
163
}
164
165
/*
Create an iterator in the list private iterator structure
*/
166
void
listRewind(list *list, listIter *
li) {
167
li->next = list->
head;
168
li->direction =
AL_START_HEAD;
169
}
170
171
void
listRewindTail(list *list, listIter *
li) {
172
li->next = list->
tail;
173
li->direction =
AL_START_TAIL;
174
}
175
176
/*
Return the next element of an iterator.
177
* It's valid to remove the currently returned element using
178
* listDelNode(), but not to remove other elements.
179
*
180
* The function returns a pointer to the next element of the list,
181
* or NULL if there are no more elements, so the classical usage patter
182
* is:
183
*
184
* iter = listGetIterator(list,<direction>);
185
* while ((node = listNext(iter)) != NULL) {
186
* doSomethingWith(listNodeValue(node));
187
* }
188
*
189
*
*/
190
listNode *listNext(listIter *
iter)
191
{
192
listNode *current = iter->
next;
193
194
if
(current !=
NULL) {
195
if
(iter->direction ==
AL_START_HEAD)
196
iter->next = current->
next;
197
else
198
iter->next = current->
prev;
199
}
200
return
current;
201
} //注意这个函数，如果对返回值作delete操作，iter并未失效
202
203
/*
Duplicate the whole list. On out of memory NULL is returned.
204
* On success a copy of the original list is returned.
205
*
206
* The 'Dup' method set with listSetDupMethod() function is used
207
* to copy the node value. Otherwise the same pointer value of
208
* the original node is used as value of the copied node.
209
*
210
* The original list both on success or error is never modified.
*/
211
list *listDup(list *
orig)
212
{
213
list *
copy;
214
listIter *
iter;
215
listNode *
node;
216
217
if
((copy = listCreate()) ==
NULL)
218
return
NULL;
219
copy->dup = orig->
dup;
220
copy->free = orig->
free;
221
copy->match = orig->
match;
222
iter =
listGetIterator(orig, AL_START_HEAD);
223
while
((node = listNext(iter)) !=
NULL) {
224
void
*
value;
225
226
if
(copy->
dup) {
227
value = copy->dup(node->
value);
228
if
(value ==
NULL) {
229
listRelease(copy);
230
listReleaseIterator(iter);
231
return
NULL;
232
}
233
}
else
234
value = node->
value;
235
if
(listAddNodeTail(copy, value) ==
NULL) {
236
listRelease(copy);
//这里疑似有内存泄露，如果copy->dup被指定，并为value成功分配了内存，但addNodeTail的时候失败了，这块内存就没人管了。
237
listReleaseIterator(iter);
238
return
NULL;
239
}
240
}
241
listReleaseIterator(iter);
242
return
copy;
243
} //如果没有指定dup函数则是个浅拷贝，否则是个深拷贝。
244
245
/*
Search the list for a node matching a given key.
246
* The match is performed using the 'match' method
247
* set with listSetMatchMethod(). If no 'match' method
248
* is set, the 'value' pointer of every node is directly
249
* compared with the 'key' pointer.
250
*
251
* On success the first matching node pointer is returned
252
* (search starts from head). If no matching node exists
253
* NULL is returned.
*/
254
listNode *listSearchKey(list *list,
void
*
key)
255
{
256
listIter *
iter;
257
listNode *
node;
258
259
iter =
listGetIterator(list, AL_START_HEAD);
260
while
((node = listNext(iter)) !=
NULL) {
261
if
(list->
match) {
262
if
(list->match(node->
value, key)) {
263
listReleaseIterator(iter);
264
return
node;
265
}
266
}
else
{
267
if
(key == node->
value) {
268
listReleaseIterator(iter);
269
return
node;
270
}
271
}
272
}
273
listReleaseIterator(iter);
274
return
NULL;
275
} //O(n)的复杂度，n是链表长度
276
277
/*
Return the element at the specified zero-based index
278
* where 0 is the head, 1 is the element next to head
279
* and so on. Negative integers are used in order to count
280
* from the tail, -1 is the last element, -2 the penultimante
281
* and so on. If the index is out of range NULL is returned.
*/
282
listNode *listIndex(list *list,
int
index) {
283
listNode *
n;
284
285
if
(index <
0
) {
286
index = (-index)-
1
; //注意从后边往前数时index的处理
287
n = list->
tail;
288
while
(index-- && n) n = n->
prev;
289
}
else
{
290
n = list->
head;
291
while
(index-- && n) n = n->
next;
292
}
293
return
n;
294
}
