【redis源码】（四）Adlist

sm702

　　双向链表~~ 代码比较容易懂，小弟只是做了简单的注释，没啥特别的，不多说了，上代码~~
　　Adlist.h



1 #ifndef __ADLIST_H__
2 #define __ADLIST_H__
3
4 /* Node, List, and Iterator are the only data structures used currently. */
5
6 typedef struct listNode {
7     struct listNode *prev;
8     struct listNode *next;
9     void *value;
10 } listNode;
11
12 typedef struct listIter {
13     listNode *next;
14     int direction;
15 } listIter;
16
17 typedef struct list {
18     listNode *head;
19     listNode *tail;
20     void *(*dup)(void *ptr);
21     void (*free)(void *ptr);
22     int (*match)(void *ptr, void *key);
23     unsigned int len;
24 } list;
25
26 /* Functions implemented as macros */
27 #define listLength(l) ((l)->len)
28 #define listFirst(l) ((l)->head)
29 #define listLast(l) ((l)->tail)
30 #define listPrevNode(n) ((n)->prev)
31 #define listNextNode(n) ((n)->next)
32 #define listNodeValue(n) ((n)->value)
33
34 #define listSetDupMethod(l,m) ((l)->dup = (m))
35 #define listSetFreeMethod(l,m) ((l)->free = (m))
36 #define listSetMatchMethod(l,m) ((l)->match = (m))
37
38 #define listGetDupMethod(l) ((l)->dup)
39 #define listGetFree(l) ((l)->free)
40 #define listGetMatchMethod(l) ((l)->match)
41
42 /* Prototypes */
43 list *listCreate(void);
44 void listRelease(list *list);
45 list *listAddNodeHead(list *list, void *value);
46 list *listAddNodeTail(list *list, void *value);
47 list *listInsertNode(list *list, listNode *old_node, void *value, int after);
48 void listDelNode(list *list, listNode *node);
49 listIter *listGetIterator(list *list, int direction);
50 listNode *listNext(listIter *iter);
51 void listReleaseIterator(listIter *iter);
52 list *listDup(list *orig);
53 listNode *listSearchKey(list *list, void *key);
54 listNode *listIndex(list *list, int index);
55 void listRewind(list *list, listIter *li);
56 void listRewindTail(list *list, listIter *li);
57
58 /* Directions for iterators */
59 #define AL_START_HEAD 0
60 #define AL_START_TAIL 1
61
62 #endif /* __ADLIST_H__ */
　　
　　Adlist.c



  1 #include
  2 #include "adlist.h"
  3 #include "zmalloc.h"
  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
11 //创建一个新的list，返回list指针
12 //如果创建失败，返回NULL指针
13 list *listCreate(void)
14 {
15     struct list *list;
16
17     if ((list = zmalloc(sizeof(*list))) == NULL)
18         return NULL;
19     list->head = list->tail = NULL;
20     list->len = 0;
21     list->dup = NULL;
22     list->free = NULL;
23     list->match = NULL;
24     return list;
25 }
26
27 /* Free the whole list.
28  *
29  * This function can't fail. */
30 //释放列表
31 void listRelease(list *list)
32 {
33     unsigned int len;
34     listNode *current, *next;
35
36     current = list->head;
37     len = list->len;
38     while(len--) {
39         next = current->next;
40         if (list->free) list->free(current->value);
41         zfree(current);
42         current = next;
43     }
44     zfree(list);
45 }
46
47 //在list头部添加一个新节点，并返回新的list指针
48 //如果失败，返回NULL【申请内存失败】
49 /* Add a new node to the list, to head, contaning the specified 'value'
50  * pointer as value.
51  *
52  * On error, NULL is returned and no operation is performed (i.e. the
53  * list remains unaltered).
54  * On success the 'list' pointer you pass to the function is returned. */
55 list *listAddNodeHead(list *list, void *value)
56 {
57     listNode *node;
58
59     if ((node = zmalloc(sizeof(*node))) == NULL)
60         return NULL;
61     node->value = value;
62     if (list->len == 0) {
63         list->head = list->tail = node;
64         node->prev = node->next = NULL;
65     } else {
66         node->prev = NULL;
67         node->next = list->head;
68         list->head->prev = node;
69         list->head = node;
70     }
71     list->len++;
72     return list;
73 }
74
75
76 //在list尾部增加添加node，返回list指针
77 /* Add a new node to the list, to tail, contaning the specified 'value'
78  * pointer as value.
79  *
80  * On error, NULL is returned and no operation is performed (i.e. the
81  * list remains unaltered).
82  * On success the 'list' pointer you pass to the function is returned. */
83 list *listAddNodeTail(list *list, void *value)
84 {
85     listNode *node;
86
87     if ((node = zmalloc(sizeof(*node))) == NULL)
88         return NULL;
89     node->value = value;
90     if (list->len == 0) {
91         list->head = list->tail = node;
92         node->prev = node->next = NULL;
93     } else {
94         node->prev = list->tail;
95         node->next = NULL;
96         list->tail->next = node;
97         list->tail = node;
98     }
99     list->len++;
100     return list;
101 }
102
103 //在list中插入一个新节点，如果after为非零，插在old_node后，否则，插在old_node之前
104 list *listInsertNode(list *list, listNode *old_node, void *value, int after) {
105     listNode *node;
106
107     if ((node = zmalloc(sizeof(*node))) == NULL)
108         return NULL;
109     node->value = value;
110     if (after) {
111         node->prev = old_node;
112         node->next = old_node->next;
113         if (list->tail == old_node) {
114             list->tail = node;
115         }
116     } else {
117         node->next = old_node;
118         node->prev = old_node->prev;
119         if (list->head == old_node) {
120             list->head = node;
121         }
122     }
123     if (node->prev != NULL) {
124         node->prev->next = node;
125     }
126     if (node->next != NULL) {
127         node->next->prev = node;
128     }
129     list->len++;
130     return list;
131 }
132
133 //删除某节点
134 /* Remove the specified node from the specified list.
135  * It's up to the caller to free the private value of the node.
136  *
137  * This function can't fail. */
138 void listDelNode(list *list, listNode *node)
139 {
140     if (node->prev)
141         node->prev->next = node->next;
142     else
143         list->head = node->next;
144     if (node->next)
145         node->next->prev = node->prev;
146     else
147         list->tail = node->prev;
148     if (list->free) list->free(node->value);
149     zfree(node);
150     list->len--;
151 }
152
153 //得到一个listIter，用来遍历列表list用
154 /* Returns a list iterator 'iter'. After the initialization every
155  * call to listNext() will return the next element of the list.
156  *
157  * This function can't fail. */
158 listIter *listGetIterator(list *list, int direction)
159 {
160     listIter *iter;
161     
162     if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;
163     if (direction == AL_START_HEAD)
164         iter->next = list->head;
165     else
166         iter->next = list->tail;
167     iter->direction = direction;
168     return iter;
169 }
170
171 //释放listIter
172 /* Release the iterator memory */
173 void listReleaseIterator(listIter *iter) {
174     zfree(iter);
175 }
176
177 //把一个listIter强制搞成指向头指针的iter
178 /* Create an iterator in the list private iterator structure */
179 void listRewind(list *list, listIter *li) {
180     li->next = list->head;
181     li->direction = AL_START_HEAD;
182 }
183
184 //把一个listIter强制搞成指向尾指针的iter
185 void listRewindTail(list *list, listIter *li) {
186     li->next = list->tail;
187     li->direction = AL_START_TAIL;
188 }
189
190 /* Return the next element of an iterator.
191  * It's valid to remove the currently returned element using
192  * listDelNode(), but not to remove other elements.
193  *
194  * The function returns a pointer to the next element of the list,
195  * or NULL if there are no more elements, so the classical usage patter
196  * is:
197  *
198  * iter = listGetIterator(list,);
199  * while ((node = listNext(iter)) != NULL) {
200  *     doSomethingWith(listNodeValue(node));
201  * }
202  *
203  * */
204 //得到iter的下一个iter
205 listNode *listNext(listIter *iter)
206 {
207     listNode *current = iter->next;
208
209     if (current != NULL) {
210         if (iter->direction == AL_START_HEAD)
211             iter->next = current->next;
212         else
213             iter->next = current->prev;
214     }
215     return current;
216 }
217 /* Duplicate the whole list. On out of memory NULL is returned.
218  * On success a copy of the original list is returned.
219  *
220  * The 'Dup' method set with listSetDupMethod() function is used
221  * to copy the node value. Otherwise the same pointer value of
222  * the original node is used as value of the copied node.
223  *
224  * The original list both on success or error is never modified. */
225 //复制整个list，并返回新list的指针，如果dup失败，返回NULL
226 //
227 list *listDup(list *orig)
228 {
229     list *copy;
230     listIter *iter;
231     listNode *node;
232
233     if ((copy = listCreate()) == NULL)
234         return NULL;
235     copy->dup = orig->dup;
236     copy->free = orig->free;
237     copy->match = orig->match;
238     iter = listGetIterator(orig, AL_START_HEAD);
239     while((node = listNext(iter)) != NULL) {
240         void *value;
241           //如果预定义了copy函数【clone?】则使用其来复制value
242         if (copy->dup) {
243             value = copy->dup(node->value);
244             //如果复制失败【一般是内存alloc失败】
245             if (value == NULL) {
246                 listRelease(copy);
247                 listReleaseIterator(iter);
248                 return NULL;
249             }
250         } else
251             value = node->value;
252         if (listAddNodeTail(copy, value) == NULL) {
253             listRelease(copy);
254             listReleaseIterator(iter);
255             return NULL;
256         }
257     }
258     listReleaseIterator(iter);
259     return copy;
260 }
261
262 /* Search the list for a node matching a given key.
263  * The match is performed using the 'match' method
264  * set with listSetMatchMethod(). If no 'match' method
265  * is set, the 'value' pointer of every node is directly
266  * compared with the 'key' pointer.
267  *
268  * On success the first matching node pointer is returned
269  * (search starts from head). If no matching node exists
270  * NULL is returned. */
271  //在list中查找*key指针指向的value
272 listNode *listSearchKey(list *list, void *key)
273 {
274     listIter *iter;
275     listNode *node;
276
277     iter = listGetIterator(list, AL_START_HEAD);
278     while((node = listNext(iter)) != NULL) {
279         //如果自定义了match方法，则使用自定义match方法
280         if (list->match) {
281             if (list->match(node->value, key)) {
282                 listReleaseIterator(iter);
283                 return node;
284             }
285         } else {
286             if (key == node->value) {
287                 listReleaseIterator(iter);
288                 return node;
289             }
290         }
291     }
292     listReleaseIterator(iter);
293     return NULL;
294 }
295
296 /* Return the element at the specified zero-based index
297  * where 0 is the head, 1 is the element next to head
298  * and so on. Negative integers are used in order to count
299  * from the tail, -1 is the last element, -2 the penultimante
300  * and so on. If the index is out of range NULL is returned. */
301 //找到第index个元素，如果没找到，返回NULL【如果index为什么没有和list->len 做一次比较呢?】
302 listNode *listIndex(list *list, int index) {
303     listNode *n;
304
305     if (index < 0) {
306         index = (-index)-1;
307         n = list->tail;
308         while(index-- && n) n = n->prev;
309     } else {
310         n = list->head;
311         while(index-- && n) n = n->next;
312     }
313     return n;
314 }