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. */
42list *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. */
57void 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. */
77void 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. */
89list *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. */
115list *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
135list *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. */
168void 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. */
187listIter *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 */
201void listReleaseIterator(listIter *iter) {
202 zfree(iter);
203}
204
205/* Create an iterator in the list private iterator structure */
206void listRewind(list *list, listIter *li) {
207 li->next = list->head;
208 li->direction = AL_START_HEAD;
209}
210
211void 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 * */
230listNode *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. */
251list *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. */
296listNode *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. */
321listNode *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. */
336void 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. */
351void 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. */
367void 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