| 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 | 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 | list *listInsertNode(list *list, listNode *old_node, void *value, int after) { |
| 127 | listNode *node; |
| 128 | |
| 129 | if ((node = zmalloc(sizeof(*node))) == NULL) |
| 130 | return NULL; |
| 131 | node->value = value; |
| 132 | if (after) { |
| 133 | node->prev = old_node; |
| 134 | node->next = old_node->next; |
| 135 | if (list->tail == old_node) { |
| 136 | list->tail = node; |
| 137 | } |
| 138 | } else { |
| 139 | node->next = old_node; |
| 140 | node->prev = old_node->prev; |
| 141 | if (list->head == old_node) { |
| 142 | list->head = node; |
| 143 | } |
| 144 | } |
| 145 | if (node->prev != NULL) { |
| 146 | node->prev->next = node; |
| 147 | } |
| 148 | if (node->next != NULL) { |
| 149 | node->next->prev = node; |
| 150 | } |
| 151 | list->len++; |
| 152 | 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 | void listDelNode(list *list, listNode *node) |
| 160 | { |
| 161 | if (node->prev) |
| 162 | node->prev->next = node->next; |
| 163 | else |
| 164 | list->head = node->next; |
| 165 | if (node->next) |
| 166 | node->next->prev = node->prev; |
| 167 | else |
| 168 | list->tail = node->prev; |
| 169 | if (list->free) list->free(node->value); |
| 170 | zfree(node); |
| 171 | list->len--; |
| 172 | } |
| 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 | listIter *listGetIterator(list *list, int direction) |
| 179 | { |
| 180 | listIter *iter; |
| 181 | |
| 182 | if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL; |
| 183 | if (direction == AL_START_HEAD) |
| 184 | iter->next = list->head; |
| 185 | else |
| 186 | iter->next = list->tail; |
| 187 | iter->direction = direction; |
| 188 | return iter; |
| 189 | } |
| 190 | |
| 191 | /* Release the iterator memory */ |
| 192 | void listReleaseIterator(listIter *iter) { |
| 193 | zfree(iter); |
| 194 | } |
| 195 | |
| 196 | /* Create an iterator in the list private iterator structure */ |
| 197 | void listRewind(list *list, listIter *li) { |
| 198 | li->next = list->head; |
| 199 | li->direction = AL_START_HEAD; |
| 200 | } |
| 201 | |
| 202 | void listRewindTail(list *list, listIter *li) { |
| 203 | li->next = list->tail; |
| 204 | li->direction = AL_START_TAIL; |
| 205 | } |
| 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 | listNode *listNext(listIter *iter) |
| 222 | { |
| 223 | listNode *current = iter->next; |
| 224 | |
| 225 | if (current != NULL) { |
| 226 | if (iter->direction == AL_START_HEAD) |
| 227 | iter->next = current->next; |
| 228 | else |
| 229 | iter->next = current->prev; |
| 230 | } |
| 231 | 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 | list *listDup(list *orig) |
| 243 | { |
| 244 | list *copy; |
| 245 | listIter *iter; |
| 246 | listNode *node; |
| 247 | |
| 248 | if ((copy = listCreate()) == NULL) |
| 249 | return NULL; |
| 250 | copy->dup = orig->dup; |
| 251 | copy->free = orig->free; |
| 252 | copy->match = orig->match; |
| 253 | iter = listGetIterator(orig, AL_START_HEAD); |
| 254 | while((node = listNext(iter)) != NULL) { |
| 255 | void *value; |
| 256 | |
| 257 | if (copy->dup) { |
| 258 | value = copy->dup(node->value); |
| 259 | if (value == NULL) { |
| 260 | listRelease(copy); |
| 261 | listReleaseIterator(iter); |
| 262 | return NULL; |
| 263 | } |
| 264 | } else |
| 265 | value = node->value; |
| 266 | if (listAddNodeTail(copy, value) == NULL) { |
| 267 | listRelease(copy); |
| 268 | listReleaseIterator(iter); |
| 269 | return NULL; |
| 270 | } |
| 271 | } |
| 272 | listReleaseIterator(iter); |
| 273 | 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 | listNode *listSearchKey(list *list, void *key) |
| 286 | { |
| 287 | listIter *iter; |
| 288 | listNode *node; |
| 289 | |
| 290 | iter = listGetIterator(list, AL_START_HEAD); |
| 291 | while((node = listNext(iter)) != NULL) { |
| 292 | if (list->match) { |
| 293 | if (list->match(node->value, key)) { |
| 294 | listReleaseIterator(iter); |
| 295 | return node; |
| 296 | } |
| 297 | } else { |
| 298 | if (key == node->value) { |
| 299 | listReleaseIterator(iter); |
| 300 | return node; |
| 301 | } |
| 302 | } |
| 303 | } |
| 304 | listReleaseIterator(iter); |
| 305 | 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 | listNode *listIndex(list *list, int index) { |
| 314 | listNode *n; |
| 315 | |
| 316 | if (index < 0) { |
| 317 | index = (-index)-1; |
| 318 | n = list->tail; |
| 319 | while(index-- && n) n = n->prev; |
| 320 | } else { |
| 321 | n = list->head; |
| 322 | while(index-- && n) n = n->next; |
| 323 | } |
| 324 | return n; |
| 325 | } |