src/adlist.c

   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 long 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, long 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 }
 326
 327 /* Rotate the list removing the tail node and inserting it to the head. */
 328 void listRotate(list *list) {
 329     listNode *tail = list->tail;
 330
 331     if (listLength(list) <= 1) return;
 332
 333     /* Detatch current tail */
 334     list->tail = tail->prev;
 335     list->tail->next = NULL;
 336     /* Move it as head */
 337     list->head->prev = tail;
 338     tail->prev = NULL;
 339     tail->next = list->head;
 340     list->head = tail;
 341 }