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 : * 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 5090 : list *listCreate(void)
42 : {
43 : struct list *list;
44 :
45 5090 : if ((list = zmalloc(sizeof(*list))) == NULL)
46 0 : return NULL;
47 5090 : list->head = list->tail = NULL;
48 5090 : list->len = 0;
49 5090 : list->dup = NULL;
50 5090 : list->free = NULL;
51 5090 : list->match = NULL;
52 5090 : return list;
53 : }
54 :
55 : /* Free the whole list.
56 : *
57 : * This function can't fail. */
58 2789 : void listRelease(list *list)
59 : {
60 : unsigned long len;
61 : listNode *current, *next;
62 :
63 2789 : current = list->head;
64 2789 : len = list->len;
65 48676 : while(len--) {
66 43098 : next = current->next;
67 43098 : if (list->free) list->free(current->value);
68 43098 : zfree(current);
69 43098 : current = next;
70 : }
71 2789 : zfree(list);
72 2789 : }
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 18873 : list *listAddNodeHead(list *list, void *value)
81 : {
82 : listNode *node;
83 :
84 18873 : if ((node = zmalloc(sizeof(*node))) == NULL)
85 0 : return NULL;
86 18873 : node->value = value;
87 18873 : if (list->len == 0) {
88 2756 : list->head = list->tail = node;
89 2756 : node->prev = node->next = NULL;
90 : } else {
91 16117 : node->prev = NULL;
92 16117 : node->next = list->head;
93 16117 : list->head->prev = node;
94 16117 : list->head = node;
95 : }
96 18873 : list->len++;
97 18873 : 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 57384 : list *listAddNodeTail(list *list, void *value)
107 : {
108 : listNode *node;
109 :
110 57384 : if ((node = zmalloc(sizeof(*node))) == NULL)
111 0 : return NULL;
112 57384 : node->value = value;
113 57384 : if (list->len == 0) {
114 3501 : list->head = list->tail = node;
115 3501 : node->prev = node->next = NULL;
116 : } else {
117 53883 : node->prev = list->tail;
118 53883 : node->next = NULL;
119 53883 : list->tail->next = node;
120 53883 : list->tail = node;
121 : }
122 57384 : list->len++;
123 57384 : return list;
124 : }
125 :
126 7 : list *listInsertNode(list *list, listNode *old_node, void *value, int after) {
127 : listNode *node;
128 :
129 7 : if ((node = zmalloc(sizeof(*node))) == NULL)
130 0 : return NULL;
131 7 : node->value = value;
132 7 : if (after) {
133 3 : node->prev = old_node;
134 3 : node->next = old_node->next;
135 3 : if (list->tail == old_node) {
136 2 : list->tail = node;
137 : }
138 : } else {
139 4 : node->next = old_node;
140 4 : node->prev = old_node->prev;
141 4 : if (list->head == old_node) {
142 3 : list->head = node;
143 : }
144 : }
145 7 : if (node->prev != NULL) {
146 4 : node->prev->next = node;
147 : }
148 7 : if (node->next != NULL) {
149 5 : node->next->prev = node;
150 : }
151 7 : list->len++;
152 7 : return list;
153 : }
154 :
155 : /* Remove the specified node from the specified list.
156 : * It's up to the caller to free the private value of the node.
157 : *
158 : * This function can't fail. */
159 30134 : void listDelNode(list *list, listNode *node)
160 : {
161 30134 : if (node->prev)
162 7434 : node->prev->next = node->next;
163 : else
164 22700 : list->head = node->next;
165 30134 : if (node->next)
166 17928 : node->next->prev = node->prev;
167 : else
168 12206 : list->tail = node->prev;
169 30134 : if (list->free) list->free(node->value);
170 30134 : zfree(node);
171 30134 : list->len--;
172 30134 : }
173 :
174 : /* Returns a list iterator 'iter'. After the initialization every
175 : * call to listNext() will return the next element of the list.
176 : *
177 : * This function can't fail. */
178 200 : listIter *listGetIterator(list *list, int direction)
179 : {
180 : listIter *iter;
181 :
182 200 : if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;
183 200 : if (direction == AL_START_HEAD)
184 200 : iter->next = list->head;
185 : else
186 0 : iter->next = list->tail;
187 200 : iter->direction = direction;
188 200 : return iter;
189 : }
190 :
191 : /* Release the iterator memory */
192 0 : void listReleaseIterator(listIter *iter) {
193 200 : zfree(iter);
194 0 : }
195 :
196 : /* Create an iterator in the list private iterator structure */
197 351108 : void listRewind(list *list, listIter *li) {
198 351108 : li->next = list->head;
199 351108 : li->direction = AL_START_HEAD;
200 351108 : }
201 :
202 0 : void listRewindTail(list *list, listIter *li) {
203 0 : li->next = list->tail;
204 0 : li->direction = AL_START_TAIL;
205 0 : }
206 :
207 : /* Return the next element of an iterator.
208 : * It's valid to remove the currently returned element using
209 : * listDelNode(), but not to remove other elements.
210 : *
211 : * The function returns a pointer to the next element of the list,
212 : * or NULL if there are no more elements, so the classical usage patter
213 : * is:
214 : *
215 : * iter = listGetIterator(list,<direction>);
216 : * while ((node = listNext(iter)) != NULL) {
217 : * doSomethingWith(listNodeValue(node));
218 : * }
219 : *
220 : * */
221 875656 : listNode *listNext(listIter *iter)
222 : {
223 876143 : listNode *current = iter->next;
224 :
225 876143 : if (current != NULL) {
226 525025 : if (iter->direction == AL_START_HEAD)
227 525025 : iter->next = current->next;
228 : else
229 0 : iter->next = current->prev;
230 : }
231 876143 : return current;
232 : }
233 :
234 : /* Duplicate the whole list. On out of memory NULL is returned.
235 : * On success a copy of the original list is returned.
236 : *
237 : * The 'Dup' method set with listSetDupMethod() function is used
238 : * to copy the node value. Otherwise the same pointer value of
239 : * the original node is used as value of the copied node.
240 : *
241 : * The original list both on success or error is never modified. */
242 2 : list *listDup(list *orig)
243 : {
244 : list *copy;
245 : listIter *iter;
246 : listNode *node;
247 :
248 2 : if ((copy = listCreate()) == NULL)
249 0 : return NULL;
250 2 : copy->dup = orig->dup;
251 2 : copy->free = orig->free;
252 2 : copy->match = orig->match;
253 2 : iter = listGetIterator(orig, AL_START_HEAD);
254 137 : while((node = listNext(iter)) != NULL) {
255 : void *value;
256 :
257 133 : if (copy->dup) {
258 133 : value = copy->dup(node->value);
259 133 : if (value == NULL) {
260 0 : listRelease(copy);
261 : listReleaseIterator(iter);
262 0 : return NULL;
263 : }
264 : } else
265 0 : value = node->value;
266 133 : if (listAddNodeTail(copy, value) == NULL) {
267 0 : listRelease(copy);
268 : listReleaseIterator(iter);
269 0 : return NULL;
270 : }
271 : }
272 : listReleaseIterator(iter);
273 2 : return copy;
274 : }
275 :
276 : /* Search the list for a node matching a given key.
277 : * The match is performed using the 'match' method
278 : * set with listSetMatchMethod(). If no 'match' method
279 : * is set, the 'value' pointer of every node is directly
280 : * compared with the 'key' pointer.
281 : *
282 : * On success the first matching node pointer is returned
283 : * (search starts from head). If no matching node exists
284 : * NULL is returned. */
285 198 : listNode *listSearchKey(list *list, void *key)
286 : {
287 : listIter *iter;
288 : listNode *node;
289 :
290 198 : iter = listGetIterator(list, AL_START_HEAD);
291 550 : while((node = listNext(iter)) != NULL) {
292 341 : if (list->match) {
293 20 : if (list->match(node->value, key)) {
294 : listReleaseIterator(iter);
295 16 : return node;
296 : }
297 : } else {
298 321 : if (key == node->value) {
299 : listReleaseIterator(iter);
300 171 : return node;
301 : }
302 : }
303 : }
304 : listReleaseIterator(iter);
305 11 : return NULL;
306 : }
307 :
308 : /* Return the element at the specified zero-based index
309 : * where 0 is the head, 1 is the element next to head
310 : * and so on. Negative integers are used in order to count
311 : * from the tail, -1 is the last element, -2 the penultimante
312 : * and so on. If the index is out of range NULL is returned. */
313 35200 : listNode *listIndex(list *list, long index) {
314 : listNode *n;
315 :
316 35200 : if (index < 0) {
317 2004 : index = (-index)-1;
318 2004 : n = list->tail;
319 2004 : while(index-- && n) n = n->prev;
320 : } else {
321 33196 : n = list->head;
322 33196 : while(index-- && n) n = n->next;
323 : }
324 35200 : return n;
325 : }
326 :
327 : /* Rotate the list removing the tail node and inserting it to the head. */
328 7038 : void listRotate(list *list) {
329 7038 : listNode *tail = list->tail;
330 :
331 7038 : if (listLength(list) <= 1) return;
332 :
333 : /* Detatch current tail */
334 6086 : list->tail = tail->prev;
335 6086 : list->tail->next = NULL;
336 : /* Move it as head */
337 6086 : list->head->prev = tail;
338 6086 : tail->prev = NULL;
339 6086 : tail->next = list->head;
340 6086 : list->head = tail;
341 : }
|
