ed9b544e |
1 | /* adlist.c - A generic doubly linked list implementation |
2 | * |
12d090d2 |
3 | * Copyright (c) 2006-2010, Salvatore Sanfilippo <antirez at gmail dot com> |
ed9b544e |
4 | * All rights reserved. |
5 | * |
6 | * Redistribution and use in source and binary forms, with or without |
7 | * modification, are permitted provided that the following conditions are met: |
8 | * |
9 | * * Redistributions of source code must retain the above copyright notice, |
10 | * this list of conditions and the following disclaimer. |
11 | * * Redistributions in binary form must reproduce the above copyright |
12 | * notice, this list of conditions and the following disclaimer in the |
13 | * documentation and/or other materials provided with the distribution. |
14 | * * Neither the name of Redis nor the names of its contributors may be used |
15 | * to endorse or promote products derived from this software without |
16 | * specific prior written permission. |
17 | * |
18 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
19 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
20 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
21 | * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE |
22 | * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
23 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
24 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
25 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
26 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
27 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
28 | * POSSIBILITY OF SUCH DAMAGE. |
29 | */ |
30 | |
31 | |
32 | #include <stdlib.h> |
33 | #include "adlist.h" |
34 | #include "zmalloc.h" |
35 | |
36 | /* Create a new list. The created list can be freed with |
37 | * AlFreeList(), but private value of every node need to be freed |
38 | * by the user before to call AlFreeList(). |
39 | * |
40 | * On error, NULL is returned. Otherwise the pointer to the new list. */ |
41 | list *listCreate(void) |
42 | { |
43 | struct list *list; |
44 | |
45 | if ((list = zmalloc(sizeof(*list))) == NULL) |
46 | return NULL; |
47 | list->head = list->tail = NULL; |
48 | list->len = 0; |
49 | list->dup = NULL; |
50 | list->free = NULL; |
51 | list->match = NULL; |
52 | return list; |
53 | } |
54 | |
55 | /* Free the whole list. |
56 | * |
57 | * This function can't fail. */ |
58 | void listRelease(list *list) |
59 | { |
60 | unsigned int len; |
61 | listNode *current, *next; |
62 | |
63 | current = list->head; |
64 | len = list->len; |
65 | while(len--) { |
66 | next = current->next; |
67 | if (list->free) list->free(current->value); |
68 | zfree(current); |
69 | current = next; |
70 | } |
71 | zfree(list); |
72 | } |
73 | |
74 | /* Add a new node to the list, to head, contaning the specified 'value' |
75 | * pointer as value. |
76 | * |
77 | * On error, NULL is returned and no operation is performed (i.e. the |
78 | * list remains unaltered). |
79 | * On success the 'list' pointer you pass to the function is returned. */ |
80 | list *listAddNodeHead(list *list, void *value) |
81 | { |
82 | listNode *node; |
83 | |
84 | if ((node = zmalloc(sizeof(*node))) == NULL) |
85 | return NULL; |
86 | node->value = value; |
87 | if (list->len == 0) { |
88 | list->head = list->tail = node; |
89 | node->prev = node->next = NULL; |
90 | } else { |
91 | node->prev = NULL; |
92 | node->next = list->head; |
93 | list->head->prev = node; |
94 | list->head = node; |
95 | } |
96 | list->len++; |
97 | return list; |
98 | } |
99 | |
100 | /* Add a new node to the list, to tail, contaning the specified 'value' |
101 | * pointer as value. |
102 | * |
103 | * On error, NULL is returned and no operation is performed (i.e. the |
104 | * list remains unaltered). |
105 | * On success the 'list' pointer you pass to the function is returned. */ |
106 | list *listAddNodeTail(list *list, void *value) |
107 | { |
108 | listNode *node; |
109 | |
110 | if ((node = zmalloc(sizeof(*node))) == NULL) |
111 | return NULL; |
112 | node->value = value; |
113 | if (list->len == 0) { |
114 | list->head = list->tail = node; |
115 | node->prev = node->next = NULL; |
116 | } else { |
117 | node->prev = list->tail; |
118 | node->next = NULL; |
119 | list->tail->next = node; |
120 | list->tail = node; |
121 | } |
122 | list->len++; |
123 | return list; |
124 | } |
125 | |
126 | /* Remove the specified node from the specified list. |
127 | * It's up to the caller to free the private value of the node. |
128 | * |
129 | * This function can't fail. */ |
130 | void listDelNode(list *list, listNode *node) |
131 | { |
132 | if (node->prev) |
133 | node->prev->next = node->next; |
134 | else |
135 | list->head = node->next; |
136 | if (node->next) |
137 | node->next->prev = node->prev; |
138 | else |
139 | list->tail = node->prev; |
140 | if (list->free) list->free(node->value); |
141 | zfree(node); |
142 | list->len--; |
143 | } |
144 | |
145 | /* Returns a list iterator 'iter'. After the initialization every |
6208b3a7 |
146 | * call to listNext() will return the next element of the list. |
ed9b544e |
147 | * |
148 | * This function can't fail. */ |
149 | listIter *listGetIterator(list *list, int direction) |
150 | { |
151 | listIter *iter; |
152 | |
153 | if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL; |
154 | if (direction == AL_START_HEAD) |
155 | iter->next = list->head; |
156 | else |
157 | iter->next = list->tail; |
158 | iter->direction = direction; |
159 | return iter; |
160 | } |
161 | |
162 | /* Release the iterator memory */ |
163 | void listReleaseIterator(listIter *iter) { |
164 | zfree(iter); |
165 | } |
166 | |
6208b3a7 |
167 | /* Create an iterator in the list private iterator structure */ |
c7df85a4 |
168 | void listRewind(list *list, listIter *li) { |
169 | li->next = list->head; |
170 | li->direction = AL_START_HEAD; |
6208b3a7 |
171 | } |
172 | |
c7df85a4 |
173 | void listRewindTail(list *list, listIter *li) { |
174 | li->next = list->tail; |
175 | li->direction = AL_START_TAIL; |
6208b3a7 |
176 | } |
177 | |
ed9b544e |
178 | /* Return the next element of an iterator. |
179 | * It's valid to remove the currently returned element using |
180 | * listDelNode(), but not to remove other elements. |
181 | * |
182 | * The function returns a pointer to the next element of the list, |
183 | * or NULL if there are no more elements, so the classical usage patter |
184 | * is: |
185 | * |
186 | * iter = listGetItarotr(list,<direction>); |
187 | * while ((node = listNextIterator(iter)) != NULL) { |
188 | * DoSomethingWith(listNodeValue(node)); |
189 | * } |
190 | * |
191 | * */ |
6208b3a7 |
192 | listNode *listNext(listIter *iter) |
ed9b544e |
193 | { |
194 | listNode *current = iter->next; |
195 | |
196 | if (current != NULL) { |
197 | if (iter->direction == AL_START_HEAD) |
198 | iter->next = current->next; |
199 | else |
200 | iter->next = current->prev; |
201 | } |
202 | return current; |
203 | } |
204 | |
205 | /* Duplicate the whole list. On out of memory NULL is returned. |
206 | * On success a copy of the original list is returned. |
207 | * |
208 | * The 'Dup' method set with listSetDupMethod() function is used |
209 | * to copy the node value. Otherwise the same pointer value of |
210 | * the original node is used as value of the copied node. |
211 | * |
212 | * The original list both on success or error is never modified. */ |
213 | list *listDup(list *orig) |
214 | { |
215 | list *copy; |
216 | listIter *iter; |
217 | listNode *node; |
218 | |
219 | if ((copy = listCreate()) == NULL) |
220 | return NULL; |
221 | copy->dup = orig->dup; |
222 | copy->free = orig->free; |
223 | copy->match = orig->match; |
224 | iter = listGetIterator(orig, AL_START_HEAD); |
6208b3a7 |
225 | while((node = listNext(iter)) != NULL) { |
ed9b544e |
226 | void *value; |
227 | |
228 | if (copy->dup) { |
229 | value = copy->dup(node->value); |
230 | if (value == NULL) { |
231 | listRelease(copy); |
232 | listReleaseIterator(iter); |
233 | return NULL; |
234 | } |
235 | } else |
236 | value = node->value; |
237 | if (listAddNodeTail(copy, value) == NULL) { |
238 | listRelease(copy); |
239 | listReleaseIterator(iter); |
240 | return NULL; |
241 | } |
242 | } |
243 | listReleaseIterator(iter); |
244 | return copy; |
245 | } |
246 | |
247 | /* Search the list for a node matching a given key. |
248 | * The match is performed using the 'match' method |
249 | * set with listSetMatchMethod(). If no 'match' method |
250 | * is set, the 'value' pointer of every node is directly |
251 | * compared with the 'key' pointer. |
252 | * |
253 | * On success the first matching node pointer is returned |
254 | * (search starts from head). If no matching node exists |
255 | * NULL is returned. */ |
256 | listNode *listSearchKey(list *list, void *key) |
257 | { |
258 | listIter *iter; |
259 | listNode *node; |
260 | |
261 | iter = listGetIterator(list, AL_START_HEAD); |
6208b3a7 |
262 | while((node = listNext(iter)) != NULL) { |
ed9b544e |
263 | if (list->match) { |
264 | if (list->match(node->value, key)) { |
265 | listReleaseIterator(iter); |
266 | return node; |
267 | } |
268 | } else { |
269 | if (key == node->value) { |
270 | listReleaseIterator(iter); |
271 | return node; |
272 | } |
273 | } |
274 | } |
275 | listReleaseIterator(iter); |
276 | return NULL; |
277 | } |
278 | |
279 | /* Return the element at the specified zero-based index |
280 | * where 0 is the head, 1 is the element next to head |
281 | * and so on. Negative integers are used in order to count |
282 | * from the tail, -1 is the last element, -2 the penultimante |
283 | * and so on. If the index is out of range NULL is returned. */ |
284 | listNode *listIndex(list *list, int index) { |
285 | listNode *n; |
286 | |
287 | if (index < 0) { |
288 | index = (-index)-1; |
289 | n = list->tail; |
290 | while(index-- && n) n = n->prev; |
291 | } else { |
292 | n = list->head; |
293 | while(index-- && n) n = n->next; |
294 | } |
295 | return n; |
296 | } |