Back to home page

Redis cross reference

 
 

    


0001 /* adlist.c - A generic doubly linked list implementation
0002  *
0003  * Copyright (c) 2006-2010, Salvatore Sanfilippo <antirez at gmail dot com>
0004  * All rights reserved.
0005  *
0006  * Redistribution and use in source and binary forms, with or without
0007  * modification, are permitted provided that the following conditions are met:
0008  *
0009  *   * Redistributions of source code must retain the above copyright notice,
0010  *     this list of conditions and the following disclaimer.
0011  *   * Redistributions in binary form must reproduce the above copyright
0012  *     notice, this list of conditions and the following disclaimer in the
0013  *     documentation and/or other materials provided with the distribution.
0014  *   * Neither the name of Redis nor the names of its contributors may be used
0015  *     to endorse or promote products derived from this software without
0016  *     specific prior written permission.
0017  *
0018  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
0019  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
0020  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
0021  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
0022  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
0023  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
0024  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
0025  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
0026  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
0027  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
0028  * POSSIBILITY OF SUCH DAMAGE.
0029  */
0030 
0031 
0032 #include <stdlib.h>
0033 #include "adlist.h"
0034 #include "zmalloc.h"
0035 
0036 /* Create a new list. The created list can be freed with
0037  * AlFreeList(), but private value of every node need to be freed
0038  * by the user before to call AlFreeList().
0039  *
0040  * On error, NULL is returned. Otherwise the pointer to the new list. */
0041 list *listCreate(void)
0042 {
0043     struct list *list;
0044 
0045     if ((list = zmalloc(sizeof(*list))) == NULL)
0046         return NULL;
0047     list->head = list->tail = NULL;
0048     list->len = 0;
0049     list->dup = NULL;
0050     list->free = NULL;
0051     list->match = NULL;
0052     return list;
0053 }
0054 
0055 /* Free the whole list.
0056  *
0057  * This function can't fail. */
0058 void listRelease(list *list)
0059 {
0060     unsigned long len;
0061     listNode *current, *next;
0062 
0063     current = list->head;
0064     len = list->len;
0065     while(len--) {
0066         next = current->next;
0067         if (list->free) list->free(current->value);
0068         zfree(current);
0069         current = next;
0070     }
0071     zfree(list);
0072 }
0073 
0074 /* Add a new node to the list, to head, contaning the specified 'value'
0075  * pointer as value.
0076  *
0077  * On error, NULL is returned and no operation is performed (i.e. the
0078  * list remains unaltered).
0079  * On success the 'list' pointer you pass to the function is returned. */
0080 list *listAddNodeHead(list *list, void *value)
0081 {
0082     listNode *node;
0083 
0084     if ((node = zmalloc(sizeof(*node))) == NULL)
0085         return NULL;
0086     node->value = value;
0087     if (list->len == 0) {
0088         list->head = list->tail = node;
0089         node->prev = node->next = NULL;
0090     } else {
0091         node->prev = NULL;
0092         node->next = list->head;
0093         list->head->prev = node;
0094         list->head = node;
0095     }
0096     list->len++;
0097     return list;
0098 }
0099 
0100 /* Add a new node to the list, to tail, containing the specified 'value'
0101  * pointer as value.
0102  *
0103  * On error, NULL is returned and no operation is performed (i.e. the
0104  * list remains unaltered).
0105  * On success the 'list' pointer you pass to the function is returned. */
0106 list *listAddNodeTail(list *list, void *value)
0107 {
0108     listNode *node;
0109 
0110     if ((node = zmalloc(sizeof(*node))) == NULL)
0111         return NULL;
0112     node->value = value;
0113     if (list->len == 0) {
0114         list->head = list->tail = node;
0115         node->prev = node->next = NULL;
0116     } else {
0117         node->prev = list->tail;
0118         node->next = NULL;
0119         list->tail->next = node;
0120         list->tail = node;
0121     }
0122     list->len++;
0123     return list;
0124 }
0125 
0126 list *listInsertNode(list *list, listNode *old_node, void *value, int after) {
0127     listNode *node;
0128 
0129     if ((node = zmalloc(sizeof(*node))) == NULL)
0130         return NULL;
0131     node->value = value;
0132     if (after) {
0133         node->prev = old_node;
0134         node->next = old_node->next;
0135         if (list->tail == old_node) {
0136             list->tail = node;
0137         }
0138     } else {
0139         node->next = old_node;
0140         node->prev = old_node->prev;
0141         if (list->head == old_node) {
0142             list->head = node;
0143         }
0144     }
0145     if (node->prev != NULL) {
0146         node->prev->next = node;
0147     }
0148     if (node->next != NULL) {
0149         node->next->prev = node;
0150     }
0151     list->len++;
0152     return list;
0153 }
0154 
0155 /* Remove the specified node from the specified list.
0156  * It's up to the caller to free the private value of the node.
0157  *
0158  * This function can't fail. */
0159 void listDelNode(list *list, listNode *node)
0160 {
0161     if (node->prev)
0162         node->prev->next = node->next;
0163     else
0164         list->head = node->next;
0165     if (node->next)
0166         node->next->prev = node->prev;
0167     else
0168         list->tail = node->prev;
0169     if (list->free) list->free(node->value);
0170     zfree(node);
0171     list->len--;
0172 }
0173 
0174 /* Returns a list iterator 'iter'. After the initialization every
0175  * call to listNext() will return the next element of the list.
0176  *
0177  * This function can't fail. */
0178 listIter *listGetIterator(list *list, int direction)
0179 {
0180     listIter *iter;
0181     
0182     if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;
0183     if (direction == AL_START_HEAD)
0184         iter->next = list->head;
0185     else
0186         iter->next = list->tail;
0187     iter->direction = direction;
0188     return iter;
0189 }
0190 
0191 /* Release the iterator memory */
0192 void listReleaseIterator(listIter *iter) {
0193     zfree(iter);
0194 }
0195 
0196 /* Create an iterator in the list private iterator structure */
0197 void listRewind(list *list, listIter *li) {
0198     li->next = list->head;
0199     li->direction = AL_START_HEAD;
0200 }
0201 
0202 void listRewindTail(list *list, listIter *li) {
0203     li->next = list->tail;
0204     li->direction = AL_START_TAIL;
0205 }
0206 
0207 /* Return the next element of an iterator.
0208  * It's valid to remove the currently returned element using
0209  * listDelNode(), but not to remove other elements.
0210  *
0211  * The function returns a pointer to the next element of the list,
0212  * or NULL if there are no more elements, so the classical usage patter
0213  * is:
0214  *
0215  * iter = listGetIterator(list,<direction>);
0216  * while ((node = listNext(iter)) != NULL) {
0217  *     doSomethingWith(listNodeValue(node));
0218  * }
0219  *
0220  * */
0221 listNode *listNext(listIter *iter)
0222 {
0223     listNode *current = iter->next;
0224 
0225     if (current != NULL) {
0226         if (iter->direction == AL_START_HEAD)
0227             iter->next = current->next;
0228         else
0229             iter->next = current->prev;
0230     }
0231     return current;
0232 }
0233 
0234 /* Duplicate the whole list. On out of memory NULL is returned.
0235  * On success a copy of the original list is returned.
0236  *
0237  * The 'Dup' method set with listSetDupMethod() function is used
0238  * to copy the node value. Otherwise the same pointer value of
0239  * the original node is used as value of the copied node.
0240  *
0241  * The original list both on success or error is never modified. */
0242 list *listDup(list *orig)
0243 {
0244     list *copy;
0245     listIter *iter;
0246     listNode *node;
0247 
0248     if ((copy = listCreate()) == NULL)
0249         return NULL;
0250     copy->dup = orig->dup;
0251     copy->free = orig->free;
0252     copy->match = orig->match;
0253     iter = listGetIterator(orig, AL_START_HEAD);
0254     while((node = listNext(iter)) != NULL) {
0255         void *value;
0256 
0257         if (copy->dup) {
0258             value = copy->dup(node->value);
0259             if (value == NULL) {
0260                 listRelease(copy);
0261                 listReleaseIterator(iter);
0262                 return NULL;
0263             }
0264         } else
0265             value = node->value;
0266         if (listAddNodeTail(copy, value) == NULL) {
0267             listRelease(copy);
0268             listReleaseIterator(iter);
0269             return NULL;
0270         }
0271     }
0272     listReleaseIterator(iter);
0273     return copy;
0274 }
0275 
0276 /* Search the list for a node matching a given key.
0277  * The match is performed using the 'match' method
0278  * set with listSetMatchMethod(). If no 'match' method
0279  * is set, the 'value' pointer of every node is directly
0280  * compared with the 'key' pointer.
0281  *
0282  * On success the first matching node pointer is returned
0283  * (search starts from head). If no matching node exists
0284  * NULL is returned. */
0285 listNode *listSearchKey(list *list, void *key)
0286 {
0287     listIter *iter;
0288     listNode *node;
0289 
0290     iter = listGetIterator(list, AL_START_HEAD);
0291     while((node = listNext(iter)) != NULL) {
0292         if (list->match) {
0293             if (list->match(node->value, key)) {
0294                 listReleaseIterator(iter);
0295                 return node;
0296             }
0297         } else {
0298             if (key == node->value) {
0299                 listReleaseIterator(iter);
0300                 return node;
0301             }
0302         }
0303     }
0304     listReleaseIterator(iter);
0305     return NULL;
0306 }
0307 
0308 /* Return the element at the specified zero-based index
0309  * where 0 is the head, 1 is the element next to head
0310  * and so on. Negative integers are used in order to count
0311  * from the tail, -1 is the last element, -2 the penultimate
0312  * and so on. If the index is out of range NULL is returned. */
0313 listNode *listIndex(list *list, long index) {
0314     listNode *n;
0315 
0316     if (index < 0) {
0317         index = (-index)-1;
0318         n = list->tail;
0319         while(index-- && n) n = n->prev;
0320     } else {
0321         n = list->head;
0322         while(index-- && n) n = n->next;
0323     }
0324     return n;
0325 }
0326 
0327 /* Rotate the list removing the tail node and inserting it to the head. */
0328 void listRotate(list *list) {
0329     listNode *tail = list->tail;
0330 
0331     if (listLength(list) <= 1) return;
0332 
0333     /* Detach current tail */
0334     list->tail = tail->prev;
0335     list->tail->next = NULL;
0336     /* Move it as head */
0337     list->head->prev = tail;
0338     tail->prev = NULL;
0339     tail->next = list->head;
0340     list->head = tail;
0341 }