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) {
 169     list->iter.next = list->head;
 170     list->iter.direction = AL_START_HEAD;
 171 }
 172
 173 void listRewindTail(list *list) {
 174     list->iter.next = list->tail;
 175     list->iter.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 /* List Yield just call listNext() against the list private iterator */
 206 listNode *listYield(list *list) {
 207     return listNext(&list->iter);
 208 }
 209
 210 /* Duplicate the whole list. On out of memory NULL is returned.
 211  * On success a copy of the original list is returned.
 212  *
 213  * The 'Dup' method set with listSetDupMethod() function is used
 214  * to copy the node value. Otherwise the same pointer value of
 215  * the original node is used as value of the copied node.
 216  *
 217  * The original list both on success or error is never modified. */
 218 list *listDup(list *orig)
 219 {
 220     list *copy;
 221     listIter *iter;
 222     listNode *node;
 223
 224     if ((copy = listCreate()) == NULL)
 225         return NULL;
 226     copy->dup = orig->dup;
 227     copy->free = orig->free;
 228     copy->match = orig->match;
 229     iter = listGetIterator(orig, AL_START_HEAD);
 230     while((node = listNext(iter)) != NULL) {
 231         void *value;
 232
 233         if (copy->dup) {
 234             value = copy->dup(node->value);
 235             if (value == NULL) {
 236                 listRelease(copy);
 237                 listReleaseIterator(iter);
 238                 return NULL;
 239             }
 240         } else
 241             value = node->value;
 242         if (listAddNodeTail(copy, value) == NULL) {
 243             listRelease(copy);
 244             listReleaseIterator(iter);
 245             return NULL;
 246         }
 247     }
 248     listReleaseIterator(iter);
 249     return copy;
 250 }
 251
 252 /* Search the list for a node matching a given key.
 253  * The match is performed using the 'match' method
 254  * set with listSetMatchMethod(). If no 'match' method
 255  * is set, the 'value' pointer of every node is directly
 256  * compared with the 'key' pointer.
 257  *
 258  * On success the first matching node pointer is returned
 259  * (search starts from head). If no matching node exists
 260  * NULL is returned. */
 261 listNode *listSearchKey(list *list, void *key)
 262 {
 263     listIter *iter;
 264     listNode *node;
 265
 266     iter = listGetIterator(list, AL_START_HEAD);
 267     while((node = listNext(iter)) != NULL) {
 268         if (list->match) {
 269             if (list->match(node->value, key)) {
 270                 listReleaseIterator(iter);
 271                 return node;
 272             }
 273         } else {
 274             if (key == node->value) {
 275                 listReleaseIterator(iter);
 276                 return node;
 277             }
 278         }
 279     }
 280     listReleaseIterator(iter);
 281     return NULL;
 282 }
 283
 284 /* Return the element at the specified zero-based index
 285  * where 0 is the head, 1 is the element next to head
 286  * and so on. Negative integers are used in order to count
 287  * from the tail, -1 is the last element, -2 the penultimante
 288  * and so on. If the index is out of range NULL is returned. */
 289 listNode *listIndex(list *list, int index) {
 290     listNode *n;
 291
 292     if (index < 0) {
 293         index = (-index)-1;
 294         n = list->tail;
 295         while(index-- && n) n = n->prev;
 296     } else {
 297         n = list->head;
 298         while(index-- && n) n = n->next;
 299     }
 300     return n;
 301 }