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 listNextElement() 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 /* 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 listNode *listNextElement(listIter *iter)
 182 {
 183     listNode *current = iter->next;
 184
 185     if (current != NULL) {
 186         if (iter->direction == AL_START_HEAD)
 187             iter->next = current->next;
 188         else
 189             iter->next = current->prev;
 190     }
 191     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 list *listDup(list *orig)
 203 {
 204     list *copy;
 205     listIter *iter;
 206     listNode *node;
 207
 208     if ((copy = listCreate()) == NULL)
 209         return NULL;
 210     copy->dup = orig->dup;
 211     copy->free = orig->free;
 212     copy->match = orig->match;
 213     iter = listGetIterator(orig, AL_START_HEAD);
 214     while((node = listNextElement(iter)) != NULL) {
 215         void *value;
 216
 217         if (copy->dup) {
 218             value = copy->dup(node->value);
 219             if (value == NULL) {
 220                 listRelease(copy);
 221                 listReleaseIterator(iter);
 222                 return NULL;
 223             }
 224         } else
 225             value = node->value;
 226         if (listAddNodeTail(copy, value) == NULL) {
 227             listRelease(copy);
 228             listReleaseIterator(iter);
 229             return NULL;
 230         }
 231     }
 232     listReleaseIterator(iter);
 233     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 listNode *listSearchKey(list *list, void *key)
 246 {
 247     listIter *iter;
 248     listNode *node;
 249
 250     iter = listGetIterator(list, AL_START_HEAD);
 251     while((node = listNextElement(iter)) != NULL) {
 252         if (list->match) {
 253             if (list->match(node->value, key)) {
 254                 listReleaseIterator(iter);
 255                 return node;
 256             }
 257         } else {
 258             if (key == node->value) {
 259                 listReleaseIterator(iter);
 260                 return node;
 261             }
 262         }
 263     }
 264     listReleaseIterator(iter);
 265     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 listNode *listIndex(list *list, int index) {
 274     listNode *n;
 275
 276     if (index < 0) {
 277         index = (-index)-1;
 278         n = list->tail;
 279         while(index-- && n) n = n->prev;
 280     } else {
 281         n = list->head;
 282         while(index-- && n) n = n->next;
 283     }
 284     return n;
 285 }