summaryrefslogtreecommitdiffstats
path: root/src/adlist.c
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-14 13:40:54 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-14 13:40:54 +0000
commit317c0644ccf108aa23ef3fd8358bd66c2840bfc0 (patch)
treec417b3d25c86b775989cb5ac042f37611b626c8a /src/adlist.c
parentInitial commit. (diff)
downloadredis-317c0644ccf108aa23ef3fd8358bd66c2840bfc0.tar.xz
redis-317c0644ccf108aa23ef3fd8358bd66c2840bfc0.zip
Adding upstream version 5:7.2.4.upstream/5%7.2.4
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'src/adlist.c')
-rw-r--r--src/adlist.c417
1 files changed, 417 insertions, 0 deletions
diff --git a/src/adlist.c b/src/adlist.c
new file mode 100644
index 0000000..f031c46
--- /dev/null
+++ b/src/adlist.c
@@ -0,0 +1,417 @@
+/* adlist.c - A generic doubly linked list implementation
+ *
+ * Copyright (c) 2006-2010, Salvatore Sanfilippo <antirez at gmail dot com>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ *
+ * * Redistributions of source code must retain the above copyright notice,
+ * this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ * * Neither the name of Redis nor the names of its contributors may be used
+ * to endorse or promote products derived from this software without
+ * specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+
+#include <stdlib.h>
+#include "adlist.h"
+#include "zmalloc.h"
+
+/* Create a new list. The created list can be freed with
+ * listRelease(), but private value of every node need to be freed
+ * by the user before to call listRelease(), or by setting a free method using
+ * listSetFreeMethod.
+ *
+ * On error, NULL is returned. Otherwise the pointer to the new list. */
+list *listCreate(void)
+{
+ struct list *list;
+
+ if ((list = zmalloc(sizeof(*list))) == NULL)
+ return NULL;
+ list->head = list->tail = NULL;
+ list->len = 0;
+ list->dup = NULL;
+ list->free = NULL;
+ list->match = NULL;
+ return list;
+}
+
+/* Remove all the elements from the list without destroying the list itself. */
+void listEmpty(list *list)
+{
+ unsigned long len;
+ listNode *current, *next;
+
+ current = list->head;
+ len = list->len;
+ while(len--) {
+ next = current->next;
+ if (list->free) list->free(current->value);
+ zfree(current);
+ current = next;
+ }
+ list->head = list->tail = NULL;
+ list->len = 0;
+}
+
+/* Free the whole list.
+ *
+ * This function can't fail. */
+void listRelease(list *list)
+{
+ listEmpty(list);
+ zfree(list);
+}
+
+/* Add a new node to the list, to head, containing the specified 'value'
+ * pointer as value.
+ *
+ * On error, NULL is returned and no operation is performed (i.e. the
+ * list remains unaltered).
+ * On success the 'list' pointer you pass to the function is returned. */
+list *listAddNodeHead(list *list, void *value)
+{
+ listNode *node;
+
+ if ((node = zmalloc(sizeof(*node))) == NULL)
+ return NULL;
+ node->value = value;
+ listLinkNodeHead(list, node);
+ return list;
+}
+
+/*
+ * Add a node that has already been allocated to the head of list
+ */
+void listLinkNodeHead(list* list, listNode *node) {
+ if (list->len == 0) {
+ list->head = list->tail = node;
+ node->prev = node->next = NULL;
+ } else {
+ node->prev = NULL;
+ node->next = list->head;
+ list->head->prev = node;
+ list->head = node;
+ }
+ list->len++;
+}
+
+/* Add a new node to the list, to tail, containing the specified 'value'
+ * pointer as value.
+ *
+ * On error, NULL is returned and no operation is performed (i.e. the
+ * list remains unaltered).
+ * On success the 'list' pointer you pass to the function is returned. */
+list *listAddNodeTail(list *list, void *value)
+{
+ listNode *node;
+
+ if ((node = zmalloc(sizeof(*node))) == NULL)
+ return NULL;
+ node->value = value;
+ listLinkNodeTail(list, node);
+ return list;
+}
+
+/*
+ * Add a node that has already been allocated to the tail of list
+ */
+void listLinkNodeTail(list *list, listNode *node) {
+ if (list->len == 0) {
+ list->head = list->tail = node;
+ node->prev = node->next = NULL;
+ } else {
+ node->prev = list->tail;
+ node->next = NULL;
+ list->tail->next = node;
+ list->tail = node;
+ }
+ list->len++;
+}
+
+list *listInsertNode(list *list, listNode *old_node, void *value, int after) {
+ listNode *node;
+
+ if ((node = zmalloc(sizeof(*node))) == NULL)
+ return NULL;
+ node->value = value;
+ if (after) {
+ node->prev = old_node;
+ node->next = old_node->next;
+ if (list->tail == old_node) {
+ list->tail = node;
+ }
+ } else {
+ node->next = old_node;
+ node->prev = old_node->prev;
+ if (list->head == old_node) {
+ list->head = node;
+ }
+ }
+ if (node->prev != NULL) {
+ node->prev->next = node;
+ }
+ if (node->next != NULL) {
+ node->next->prev = node;
+ }
+ list->len++;
+ return list;
+}
+
+/* Remove the specified node from the specified list.
+ * The node is freed. If free callback is provided the value is freed as well.
+ *
+ * This function can't fail. */
+void listDelNode(list *list, listNode *node)
+{
+ listUnlinkNode(list, node);
+ if (list->free) list->free(node->value);
+ zfree(node);
+}
+
+/*
+ * Remove the specified node from the list without freeing it.
+ */
+void listUnlinkNode(list *list, listNode *node) {
+ if (node->prev)
+ node->prev->next = node->next;
+ else
+ list->head = node->next;
+ if (node->next)
+ node->next->prev = node->prev;
+ else
+ list->tail = node->prev;
+
+ node->next = NULL;
+ node->prev = NULL;
+
+ list->len--;
+}
+
+/* Returns a list iterator 'iter'. After the initialization every
+ * call to listNext() will return the next element of the list.
+ *
+ * This function can't fail. */
+listIter *listGetIterator(list *list, int direction)
+{
+ listIter *iter;
+
+ if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;
+ if (direction == AL_START_HEAD)
+ iter->next = list->head;
+ else
+ iter->next = list->tail;
+ iter->direction = direction;
+ return iter;
+}
+
+/* Release the iterator memory */
+void listReleaseIterator(listIter *iter) {
+ zfree(iter);
+}
+
+/* Create an iterator in the list private iterator structure */
+void listRewind(list *list, listIter *li) {
+ li->next = list->head;
+ li->direction = AL_START_HEAD;
+}
+
+void listRewindTail(list *list, listIter *li) {
+ li->next = list->tail;
+ li->direction = AL_START_TAIL;
+}
+
+/* Return the next element of an iterator.
+ * It's valid to remove the currently returned element using
+ * listDelNode(), but not to remove other elements.
+ *
+ * The function returns a pointer to the next element of the list,
+ * or NULL if there are no more elements, so the classical usage
+ * pattern is:
+ *
+ * iter = listGetIterator(list,<direction>);
+ * while ((node = listNext(iter)) != NULL) {
+ * doSomethingWith(listNodeValue(node));
+ * }
+ *
+ * */
+listNode *listNext(listIter *iter)
+{
+ listNode *current = iter->next;
+
+ if (current != NULL) {
+ if (iter->direction == AL_START_HEAD)
+ iter->next = current->next;
+ else
+ iter->next = current->prev;
+ }
+ return current;
+}
+
+/* Duplicate the whole list. On out of memory NULL is returned.
+ * On success a copy of the original list is returned.
+ *
+ * The 'Dup' method set with listSetDupMethod() function is used
+ * to copy the node value. Otherwise the same pointer value of
+ * the original node is used as value of the copied node.
+ *
+ * The original list both on success or error is never modified. */
+list *listDup(list *orig)
+{
+ list *copy;
+ listIter iter;
+ listNode *node;
+
+ if ((copy = listCreate()) == NULL)
+ return NULL;
+ copy->dup = orig->dup;
+ copy->free = orig->free;
+ copy->match = orig->match;
+ listRewind(orig, &iter);
+ while((node = listNext(&iter)) != NULL) {
+ void *value;
+
+ if (copy->dup) {
+ value = copy->dup(node->value);
+ if (value == NULL) {
+ listRelease(copy);
+ return NULL;
+ }
+ } else {
+ value = node->value;
+ }
+
+ if (listAddNodeTail(copy, value) == NULL) {
+ /* Free value if dup succeed but listAddNodeTail failed. */
+ if (copy->free) copy->free(value);
+
+ listRelease(copy);
+ return NULL;
+ }
+ }
+ return copy;
+}
+
+/* Search the list for a node matching a given key.
+ * The match is performed using the 'match' method
+ * set with listSetMatchMethod(). If no 'match' method
+ * is set, the 'value' pointer of every node is directly
+ * compared with the 'key' pointer.
+ *
+ * On success the first matching node pointer is returned
+ * (search starts from head). If no matching node exists
+ * NULL is returned. */
+listNode *listSearchKey(list *list, void *key)
+{
+ listIter iter;
+ listNode *node;
+
+ listRewind(list, &iter);
+ while((node = listNext(&iter)) != NULL) {
+ if (list->match) {
+ if (list->match(node->value, key)) {
+ return node;
+ }
+ } else {
+ if (key == node->value) {
+ return node;
+ }
+ }
+ }
+ return NULL;
+}
+
+/* Return the element at the specified zero-based index
+ * where 0 is the head, 1 is the element next to head
+ * and so on. Negative integers are used in order to count
+ * from the tail, -1 is the last element, -2 the penultimate
+ * and so on. If the index is out of range NULL is returned. */
+listNode *listIndex(list *list, long index) {
+ listNode *n;
+
+ if (index < 0) {
+ index = (-index)-1;
+ n = list->tail;
+ while(index-- && n) n = n->prev;
+ } else {
+ n = list->head;
+ while(index-- && n) n = n->next;
+ }
+ return n;
+}
+
+/* Rotate the list removing the tail node and inserting it to the head. */
+void listRotateTailToHead(list *list) {
+ if (listLength(list) <= 1) return;
+
+ /* Detach current tail */
+ listNode *tail = list->tail;
+ list->tail = tail->prev;
+ list->tail->next = NULL;
+ /* Move it as head */
+ list->head->prev = tail;
+ tail->prev = NULL;
+ tail->next = list->head;
+ list->head = tail;
+}
+
+/* Rotate the list removing the head node and inserting it to the tail. */
+void listRotateHeadToTail(list *list) {
+ if (listLength(list) <= 1) return;
+
+ listNode *head = list->head;
+ /* Detach current head */
+ list->head = head->next;
+ list->head->prev = NULL;
+ /* Move it as tail */
+ list->tail->next = head;
+ head->next = NULL;
+ head->prev = list->tail;
+ list->tail = head;
+}
+
+/* Add all the elements of the list 'o' at the end of the
+ * list 'l'. The list 'other' remains empty but otherwise valid. */
+void listJoin(list *l, list *o) {
+ if (o->len == 0) return;
+
+ o->head->prev = l->tail;
+
+ if (l->tail)
+ l->tail->next = o->head;
+ else
+ l->head = o->head;
+
+ l->tail = o->tail;
+ l->len += o->len;
+
+ /* Setup other as an empty list. */
+ o->head = o->tail = NULL;
+ o->len = 0;
+}
+
+/* Initializes the node's value and sets its pointers
+ * so that it is initially not a member of any list.
+ */
+void listInitNode(listNode *node, void *value) {
+ node->prev = NULL;
+ node->next = NULL;
+ node->value = value;
+}