adlist.c

   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 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 /* 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 void listDelNode(list *list, listNode *node)
 131 {
 132     if (node->prev)
 133         node->prev->next = node->next;
 134     else
 135         list->head = node->next;
 136     if (node->next)
 137         node->next->prev = node->prev;
 138     else
 139         list->tail = node->prev;
 140     if (list->free) list->free(node->value);
 141     zfree(node);
 142     list->len--;
 143 }
 144
 145 /* Returns a list iterator 'iter'. After the initialization every
 146  * call to listNext() will return the next element of the list.
 147  *
 148  * This function can't fail. */
 149 listIter *listGetIterator(list *list, int direction)
 150 {
 151     listIter *iter;
 152
 153     if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;
 154     if (direction == AL_START_HEAD)
 155         iter->next = list->head;
 156     else
 157         iter->next = list->tail;
 158     iter->direction = direction;
 159     return iter;
 160 }
 161
 162 /* Release the iterator memory */
 163 void listReleaseIterator(listIter *iter) {
 164     zfree(iter);
 165 }
 166
 167 /* Create an iterator in the list private iterator structure */
 168 void listRewind(list *list, listIter *li) {
 169     li->next = list->head;
 170     li->direction = AL_START_HEAD;
 171 }
 172
 173 void listRewindTail(list *list, listIter *li) {
 174     li->next = list->tail;
 175     li->direction = AL_START_TAIL;
 176 }
 177
 178 /* Return the next element of an iterator.
 179  * It's valid to remove the currently returned element using
 180  * listDelNode(), but not to remove other elements.
 181  *
 182  * The function returns a pointer to the next element of the list,
 183  * or NULL if there are no more elements, so the classical usage patter
 184  * is:
 185  *
 186  * iter = listGetItarotr(list,<direction>);
 187  * while ((node = listNextIterator(iter)) != NULL) {
 188  *     DoSomethingWith(listNodeValue(node));
 189  * }
 190  *
 191  * */
 192 listNode *listNext(listIter *iter)
 193 {
 194     listNode *current = iter->next;
 195
 196     if (current != NULL) {
 197         if (iter->direction == AL_START_HEAD)
 198             iter->next = current->next;
 199         else
 200             iter->next = current->prev;
 201     }
 202     return current;
 203 }
 204
 205 /* Duplicate the whole list. On out of memory NULL is returned.
 206  * On success a copy of the original list is returned.
 207  *
 208  * The 'Dup' method set with listSetDupMethod() function is used
 209  * to copy the node value. Otherwise the same pointer value of
 210  * the original node is used as value of the copied node.
 211  *
 212  * The original list both on success or error is never modified. */
 213 list *listDup(list *orig)
 214 {
 215     list *copy;
 216     listIter *iter;
 217     listNode *node;
 218
 219     if ((copy = listCreate()) == NULL)
 220         return NULL;
 221     copy->dup = orig->dup;
 222     copy->free = orig->free;
 223     copy->match = orig->match;
 224     iter = listGetIterator(orig, AL_START_HEAD);
 225     while((node = listNext(iter)) != NULL) {
 226         void *value;
 227
 228         if (copy->dup) {
 229             value = copy->dup(node->value);
 230             if (value == NULL) {
 231                 listRelease(copy);
 232                 listReleaseIterator(iter);
 233                 return NULL;
 234             }
 235         } else
 236             value = node->value;
 237         if (listAddNodeTail(copy, value) == NULL) {
 238             listRelease(copy);
 239             listReleaseIterator(iter);
 240             return NULL;
 241         }
 242     }
 243     listReleaseIterator(iter);
 244     return copy;
 245 }
 246
 247 /* Search the list for a node matching a given key.
 248  * The match is performed using the 'match' method
 249  * set with listSetMatchMethod(). If no 'match' method
 250  * is set, the 'value' pointer of every node is directly
 251  * compared with the 'key' pointer.
 252  *
 253  * On success the first matching node pointer is returned
 254  * (search starts from head). If no matching node exists
 255  * NULL is returned. */
 256 listNode *listSearchKey(list *list, void *key)
 257 {
 258     listIter *iter;
 259     listNode *node;
 260
 261     iter = listGetIterator(list, AL_START_HEAD);
 262     while((node = listNext(iter)) != NULL) {
 263         if (list->match) {
 264             if (list->match(node->value, key)) {
 265                 listReleaseIterator(iter);
 266                 return node;
 267             }
 268         } else {
 269             if (key == node->value) {
 270                 listReleaseIterator(iter);
 271                 return node;
 272             }
 273         }
 274     }
 275     listReleaseIterator(iter);
 276     return NULL;
 277 }
 278
 279 /* Return the element at the specified zero-based index
 280  * where 0 is the head, 1 is the element next to head
 281  * and so on. Negative integers are used in order to count
 282  * from the tail, -1 is the last element, -2 the penultimante
 283  * and so on. If the index is out of range NULL is returned. */
 284 listNode *listIndex(list *list, int index) {
 285     listNode *n;
 286
 287     if (index < 0) {
 288         index = (-index)-1;
 289         n = list->tail;
 290         while(index-- && n) n = n->prev;
 291     } else {
 292         n = list->head;
 293         while(index-- && n) n = n->next;
 294     }
 295     return n;
 296 }