redisソースノート-adlist
40876 ワード
adlistはredis自身が実現した汎用的な双方向チェーンテーブルである.
------------------------------------------------adlist.h---------------------------------------------------
------------------------------------------------adlist.c---------------------------------------------------
------------------------------------------------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 }