1 | /* adlist.c - A generic doubly linked list implementation |
2 | * |
3 | * Copyright (c) 2006-2010, Salvatore Sanfilippo <antirez at gmail dot com> |
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 | * listRelease(), but private value of every node need to be freed |
38 | * by the user before to call listRelease(), or by setting a free method using |
39 | * listSetFreeMethod. |
40 | * |
41 | * On error, NULL is returned. Otherwise the pointer to the new list. */ |
42 | list *listCreate(void) |
43 | { |
44 | struct list *list; |
45 | |
46 | if ((list = zmalloc(sizeof(*list))) == NULL) |
47 | return NULL; |
48 | list->head = list->tail = NULL; |
49 | list->len = 0; |
50 | list->dup = NULL; |
51 | list->free = NULL; |
52 | list->match = NULL; |
53 | return list; |
54 | } |
55 | |
56 | /* Remove all the elements from the list without destroying the list itself. */ |
57 | void listEmpty(list *list) |
58 | { |
59 | unsigned long len; |
60 | listNode *current, *next; |
61 | |
62 | current = list->head; |
63 | len = list->len; |
64 | while(len--) { |
65 | next = current->next; |
66 | if (list->free) list->free(current->value); |
67 | zfree(current); |
68 | current = next; |
69 | } |
70 | list->head = list->tail = NULL; |
71 | list->len = 0; |
72 | } |
73 | |
74 | /* Free the whole list. |
75 | * |
76 | * This function can't fail. */ |
77 | void listRelease(list *list) |
78 | { |
79 | listEmpty(list); |
80 | zfree(list); |
81 | } |
82 | |
83 | /* Add a new node to the list, to head, containing the specified 'value' |
84 | * pointer as value. |
85 | * |
86 | * On error, NULL is returned and no operation is performed (i.e. the |
87 | * list remains unaltered). |
88 | * On success the 'list' pointer you pass to the function is returned. */ |
89 | list *listAddNodeHead(list *list, void *value) |
90 | { |
91 | listNode *node; |
92 | |
93 | if ((node = zmalloc(sizeof(*node))) == NULL) |
94 | return NULL; |
95 | node->value = value; |
96 | if (list->len == 0) { |
97 | list->head = list->tail = node; |
98 | node->prev = node->next = NULL; |
99 | } else { |
100 | node->prev = NULL; |
101 | node->next = list->head; |
102 | list->head->prev = node; |
103 | list->head = node; |
104 | } |
105 | list->len++; |
106 | return list; |
107 | } |
108 | |
109 | /* Add a new node to the list, to tail, containing the specified 'value' |
110 | * pointer as value. |
111 | * |
112 | * On error, NULL is returned and no operation is performed (i.e. the |
113 | * list remains unaltered). |
114 | * On success the 'list' pointer you pass to the function is returned. */ |
115 | list *listAddNodeTail(list *list, void *value) |
116 | { |
117 | listNode *node; |
118 | |
119 | if ((node = zmalloc(sizeof(*node))) == NULL) |
120 | return NULL; |
121 | node->value = value; |
122 | if (list->len == 0) { |
123 | list->head = list->tail = node; |
124 | node->prev = node->next = NULL; |
125 | } else { |
126 | node->prev = list->tail; |
127 | node->next = NULL; |
128 | list->tail->next = node; |
129 | list->tail = node; |
130 | } |
131 | list->len++; |
132 | return list; |
133 | } |
134 | |
135 | list *listInsertNode(list *list, listNode *old_node, void *value, int after) { |
136 | listNode *node; |
137 | |
138 | if ((node = zmalloc(sizeof(*node))) == NULL) |
139 | return NULL; |
140 | node->value = value; |
141 | if (after) { |
142 | node->prev = old_node; |
143 | node->next = old_node->next; |
144 | if (list->tail == old_node) { |
145 | list->tail = node; |
146 | } |
147 | } else { |
148 | node->next = old_node; |
149 | node->prev = old_node->prev; |
150 | if (list->head == old_node) { |
151 | list->head = node; |
152 | } |
153 | } |
154 | if (node->prev != NULL) { |
155 | node->prev->next = node; |
156 | } |
157 | if (node->next != NULL) { |
158 | node->next->prev = node; |
159 | } |
160 | list->len++; |
161 | return list; |
162 | } |
163 | |
164 | /* Remove the specified node from the specified list. |
165 | * It's up to the caller to free the private value of the node. |
166 | * |
167 | * This function can't fail. */ |
168 | void listDelNode(list *list, listNode *node) |
169 | { |
170 | if (node->prev) |
171 | node->prev->next = node->next; |
172 | else |
173 | list->head = node->next; |
174 | if (node->next) |
175 | node->next->prev = node->prev; |
176 | else |
177 | list->tail = node->prev; |
178 | if (list->free) list->free(node->value); |
179 | zfree(node); |
180 | list->len--; |
181 | } |
182 | |
183 | /* Returns a list iterator 'iter'. After the initialization every |
184 | * call to listNext() will return the next element of the list. |
185 | * |
186 | * This function can't fail. */ |
187 | listIter *listGetIterator(list *list, int direction) |
188 | { |
189 | listIter *iter; |
190 | |
191 | if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL; |
192 | if (direction == AL_START_HEAD) |
193 | iter->next = list->head; |
194 | else |
195 | iter->next = list->tail; |
196 | iter->direction = direction; |
197 | return iter; |
198 | } |
199 | |
200 | /* Release the iterator memory */ |
201 | void listReleaseIterator(listIter *iter) { |
202 | zfree(iter); |
203 | } |
204 | |
205 | /* Create an iterator in the list private iterator structure */ |
206 | void listRewind(list *list, listIter *li) { |
207 | li->next = list->head; |
208 | li->direction = AL_START_HEAD; |
209 | } |
210 | |
211 | void listRewindTail(list *list, listIter *li) { |
212 | li->next = list->tail; |
213 | li->direction = AL_START_TAIL; |
214 | } |
215 | |
216 | /* Return the next element of an iterator. |
217 | * It's valid to remove the currently returned element using |
218 | * listDelNode(), but not to remove other elements. |
219 | * |
220 | * The function returns a pointer to the next element of the list, |
221 | * or NULL if there are no more elements, so the classical usage |
222 | * pattern is: |
223 | * |
224 | * iter = listGetIterator(list,<direction>); |
225 | * while ((node = listNext(iter)) != NULL) { |
226 | * doSomethingWith(listNodeValue(node)); |
227 | * } |
228 | * |
229 | * */ |
230 | listNode *listNext(listIter *iter) |
231 | { |
232 | listNode *current = iter->next; |
233 | |
234 | if (current != NULL) { |
235 | if (iter->direction == AL_START_HEAD) |
236 | iter->next = current->next; |
237 | else |
238 | iter->next = current->prev; |
239 | } |
240 | return current; |
241 | } |
242 | |
243 | /* Duplicate the whole list. On out of memory NULL is returned. |
244 | * On success a copy of the original list is returned. |
245 | * |
246 | * The 'Dup' method set with listSetDupMethod() function is used |
247 | * to copy the node value. Otherwise the same pointer value of |
248 | * the original node is used as value of the copied node. |
249 | * |
250 | * The original list both on success or error is never modified. */ |
251 | list *listDup(list *orig) |
252 | { |
253 | list *copy; |
254 | listIter iter; |
255 | listNode *node; |
256 | |
257 | if ((copy = listCreate()) == NULL) |
258 | return NULL; |
259 | copy->dup = orig->dup; |
260 | copy->free = orig->free; |
261 | copy->match = orig->match; |
262 | listRewind(orig, &iter); |
263 | while((node = listNext(&iter)) != NULL) { |
264 | void *value; |
265 | |
266 | if (copy->dup) { |
267 | value = copy->dup(node->value); |
268 | if (value == NULL) { |
269 | listRelease(copy); |
270 | return NULL; |
271 | } |
272 | } else { |
273 | value = node->value; |
274 | } |
275 | |
276 | if (listAddNodeTail(copy, value) == NULL) { |
277 | /* Free value if dup succeed but listAddNodeTail failed. */ |
278 | if (copy->free) copy->free(value); |
279 | |
280 | listRelease(copy); |
281 | return NULL; |
282 | } |
283 | } |
284 | return copy; |
285 | } |
286 | |
287 | /* Search the list for a node matching a given key. |
288 | * The match is performed using the 'match' method |
289 | * set with listSetMatchMethod(). If no 'match' method |
290 | * is set, the 'value' pointer of every node is directly |
291 | * compared with the 'key' pointer. |
292 | * |
293 | * On success the first matching node pointer is returned |
294 | * (search starts from head). If no matching node exists |
295 | * NULL is returned. */ |
296 | listNode *listSearchKey(list *list, void *key) |
297 | { |
298 | listIter iter; |
299 | listNode *node; |
300 | |
301 | listRewind(list, &iter); |
302 | while((node = listNext(&iter)) != NULL) { |
303 | if (list->match) { |
304 | if (list->match(node->value, key)) { |
305 | return node; |
306 | } |
307 | } else { |
308 | if (key == node->value) { |
309 | return node; |
310 | } |
311 | } |
312 | } |
313 | return NULL; |
314 | } |
315 | |
316 | /* Return the element at the specified zero-based index |
317 | * where 0 is the head, 1 is the element next to head |
318 | * and so on. Negative integers are used in order to count |
319 | * from the tail, -1 is the last element, -2 the penultimate |
320 | * and so on. If the index is out of range NULL is returned. */ |
321 | listNode *listIndex(list *list, long index) { |
322 | listNode *n; |
323 | |
324 | if (index < 0) { |
325 | index = (-index)-1; |
326 | n = list->tail; |
327 | while(index-- && n) n = n->prev; |
328 | } else { |
329 | n = list->head; |
330 | while(index-- && n) n = n->next; |
331 | } |
332 | return n; |
333 | } |
334 | |
335 | /* Rotate the list removing the tail node and inserting it to the head. */ |
336 | void listRotateTailToHead(list *list) { |
337 | if (listLength(list) <= 1) return; |
338 | |
339 | /* Detach current tail */ |
340 | listNode *tail = list->tail; |
341 | list->tail = tail->prev; |
342 | list->tail->next = NULL; |
343 | /* Move it as head */ |
344 | list->head->prev = tail; |
345 | tail->prev = NULL; |
346 | tail->next = list->head; |
347 | list->head = tail; |
348 | } |
349 | |
350 | /* Rotate the list removing the head node and inserting it to the tail. */ |
351 | void listRotateHeadToTail(list *list) { |
352 | if (listLength(list) <= 1) return; |
353 | |
354 | listNode *head = list->head; |
355 | /* Detach current head */ |
356 | list->head = head->next; |
357 | list->head->prev = NULL; |
358 | /* Move it as tail */ |
359 | list->tail->next = head; |
360 | head->next = NULL; |
361 | head->prev = list->tail; |
362 | list->tail = head; |
363 | } |
364 | |
365 | /* Add all the elements of the list 'o' at the end of the |
366 | * list 'l'. The list 'other' remains empty but otherwise valid. */ |
367 | void listJoin(list *l, list *o) { |
368 | if (o->len == 0) return; |
369 | |
370 | o->head->prev = l->tail; |
371 | |
372 | if (l->tail) |
373 | l->tail->next = o->head; |
374 | else |
375 | l->head = o->head; |
376 | |
377 | l->tail = o->tail; |
378 | l->len += o->len; |
379 | |
380 | /* Setup other as an empty list. */ |
381 | o->head = o->tail = NULL; |
382 | o->len = 0; |
383 | } |
384 | |