Line data Source code
1 : /* adlist.c - A generic doubly linked list implementation
2 : *
3 : * Copyright (c) 2006-2009, 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 3 : list *listCreate(void)
42 : {
43 : struct list *list;
44 :
45 3 : if ((list = zmalloc(sizeof(*list))) == NULL)
46 1 : return NULL;
47 2 : list->head = list->tail = NULL;
48 2 : list->len = 0;
49 2 : list->dup = NULL;
50 2 : list->free = NULL;
51 2 : list->match = NULL;
52 2 : return list;
53 : }
54 :
55 : /* Free the whole list.
56 : *
57 : * This function can't fail. */
58 2 : void listRelease(list *list)
59 : {
60 : unsigned int len;
61 : listNode *current, *next;
62 :
63 2 : current = list->head;
64 2 : len = list->len;
65 6 : while(len--) {
66 4 : next = current->next;
67 4 : if (list->free) list->free(current->value);
68 4 : zfree(current);
69 4 : current = next;
70 : }
71 2 : zfree(list);
72 2 : }
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 4 : list *listAddNodeHead(list *list, void *value)
81 : {
82 : listNode *node;
83 :
84 4 : if ((node = zmalloc(sizeof(*node))) == NULL)
85 0 : return NULL;
86 4 : node->value = value;
87 4 : if (list->len == 0) {
88 1 : list->head = list->tail = node;
89 1 : node->prev = node->next = NULL;
90 : } else {
91 3 : node->prev = NULL;
92 3 : node->next = list->head;
93 3 : list->head->prev = node;
94 3 : list->head = node;
95 : }
96 4 : list->len++;
97 4 : 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 0 : list *listAddNodeTail(list *list, void *value)
107 : {
108 : listNode *node;
109 :
110 0 : if ((node = zmalloc(sizeof(*node))) == NULL)
111 0 : return NULL;
112 0 : node->value = value;
113 0 : if (list->len == 0) {
114 0 : list->head = list->tail = node;
115 0 : node->prev = node->next = NULL;
116 : } else {
117 0 : node->prev = list->tail;
118 0 : node->next = NULL;
119 0 : list->tail->next = node;
120 0 : list->tail = node;
121 : }
122 0 : list->len++;
123 0 : 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 0 : void listDelNode(list *list, listNode *node)
131 : {
132 0 : if (node->prev)
133 0 : node->prev->next = node->next;
134 : else
135 0 : list->head = node->next;
136 0 : if (node->next)
137 0 : node->next->prev = node->prev;
138 : else
139 0 : list->tail = node->prev;
140 0 : if (list->free) list->free(node->value);
141 0 : zfree(node);
142 0 : list->len--;
143 0 : }
144 :
145 : /* Returns a list iterator 'iter'. After the initialization every
146 : * call to listNextElement() will return the next element of the list.
147 : *
148 : * This function can't fail. */
149 2 : listIter *listGetIterator(list *list, int direction)
150 : {
151 : listIter *iter;
152 :
153 2 : if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;
154 2 : if (direction == AL_START_HEAD)
155 1 : iter->next = list->head;
156 : else
157 1 : iter->next = list->tail;
158 2 : iter->direction = direction;
159 2 : return iter;
160 : }
161 :
162 : /* Release the iterator memory */
163 2 : void listReleaseIterator(listIter *iter) {
164 2 : zfree(iter);
165 2 : }
166 :
167 : /* Return the next element of an iterator.
168 : * It's valid to remove the currently returned element using
169 : * listDelNode(), but not to remove other elements.
170 : *
171 : * The function returns a pointer to the next element of the list,
172 : * or NULL if there are no more elements, so the classical usage patter
173 : * is:
174 : *
175 : * iter = listGetItarotr(list,<direction>);
176 : * while ((node = listNextIterator(iter)) != NULL) {
177 : * DoSomethingWith(listNodeValue(node));
178 : * }
179 : *
180 : * */
181 4 : listNode *listNextElement(listIter *iter)
182 : {
183 4 : listNode *current = iter->next;
184 :
185 4 : if (current != NULL) {
186 4 : if (iter->direction == AL_START_HEAD)
187 2 : iter->next = current->next;
188 : else
189 2 : iter->next = current->prev;
190 : }
191 4 : return current;
192 : }
193 :
194 : /* Duplicate the whole list. On out of memory NULL is returned.
195 : * On success a copy of the original list is returned.
196 : *
197 : * The 'Dup' method set with listSetDupMethod() function is used
198 : * to copy the node value. Otherwise the same pointer value of
199 : * the original node is used as value of the copied node.
200 : *
201 : * The original list both on success or error is never modified. */
202 0 : list *listDup(list *orig)
203 : {
204 : list *copy;
205 : listIter *iter;
206 : listNode *node;
207 :
208 0 : if ((copy = listCreate()) == NULL)
209 0 : return NULL;
210 0 : copy->dup = orig->dup;
211 0 : copy->free = orig->free;
212 0 : copy->match = orig->match;
213 0 : iter = listGetIterator(orig, AL_START_HEAD);
214 0 : while((node = listNextElement(iter)) != NULL) {
215 : void *value;
216 :
217 0 : if (copy->dup) {
218 0 : value = copy->dup(node->value);
219 0 : if (value == NULL) {
220 0 : listRelease(copy);
221 0 : listReleaseIterator(iter);
222 0 : return NULL;
223 : }
224 : } else
225 0 : value = node->value;
226 0 : if (listAddNodeTail(copy, value) == NULL) {
227 0 : listRelease(copy);
228 0 : listReleaseIterator(iter);
229 0 : return NULL;
230 : }
231 : }
232 0 : listReleaseIterator(iter);
233 0 : return copy;
234 : }
235 :
236 : /* Search the list for a node matching a given key.
237 : * The match is performed using the 'match' method
238 : * set with listSetMatchMethod(). If no 'match' method
239 : * is set, the 'value' pointer of every node is directly
240 : * compared with the 'key' pointer.
241 : *
242 : * On success the first matching node pointer is returned
243 : * (search starts from head). If no matching node exists
244 : * NULL is returned. */
245 0 : listNode *listSearchKey(list *list, void *key)
246 : {
247 : listIter *iter;
248 : listNode *node;
249 :
250 0 : iter = listGetIterator(list, AL_START_HEAD);
251 0 : while((node = listNextElement(iter)) != NULL) {
252 0 : if (list->match) {
253 0 : if (list->match(node->value, key)) {
254 0 : listReleaseIterator(iter);
255 0 : return node;
256 : }
257 : } else {
258 0 : if (key == node->value) {
259 0 : listReleaseIterator(iter);
260 0 : return node;
261 : }
262 : }
263 : }
264 0 : listReleaseIterator(iter);
265 0 : return NULL;
266 : }
267 :
268 : /* Return the element at the specified zero-based index
269 : * where 0 is the head, 1 is the element next to head
270 : * and so on. Negative integers are used in order to count
271 : * from the tail, -1 is the last element, -2 the penultimante
272 : * and so on. If the index is out of range NULL is returned. */
273 0 : listNode *listIndex(list *list, int index) {
274 : listNode *n;
275 :
276 0 : if (index < 0) {
277 0 : index = (-index)-1;
278 0 : n = list->tail;
279 0 : while(index-- && n) n = n->prev;
280 : } else {
281 0 : n = list->head;
282 0 : while(index-- && n) n = n->next;
283 : }
284 0 : return n;
285 : }
|
