Redis provides a generic doubly linked list implementation, which is widely used in Redis. If a list key involves two many elements or there are many long strings in the list, Redis will apply linked list for it. Publish-subscribe, slow query, monitor also make use of linked list. Redis keeps the states of clients in linked list, and client’s output buffer use it too.
This post will plough into the implementation of doubly linked list.
The code analyzed in this post is based on 5.0.0
Node and List
Each node in the doubly list is represented by a listNode
in adlist.h
.
typedef struct listNode {
struct listNode *prev;
struct listNode *next;
void *value;
} listNode;
Multiple nodes can constitute a linked list with next
pointing to their next nodes and prev
pointing to the previous nodes.
typedef struct list {
listNode *head;
listNode *tail;
void *(*dup)(void *ptr);
void (*free)(void *ptr);
int (*match)(void *ptr, void *key);
unsigned long len;
} list;
The features of this linked list can be concluded as following:
- Doubly with
prev
andnext
pointer. It’s easy to get the previous or next node of a specified node. - No cycle. The
prev
of head andnext
of tail point toNone
. - Two pointers making it effortless to get the head or tail.
- Node counter.
len
attribute is updated every times when the length changes. - Polymorphism. The value of node is stored in
void*
, anddup
,free
,match
can change its value to a different type.
Functions Implemented as Macros
The time complexity of these functions is O(1).
#define listLength(l) ((l)->len)
#define listFirst(l) ((l)->head)
#define listLast(l) ((l)->tail)
#define listPrevNode(n) ((n)->prev)
#define listNextNode(n) ((n)->next)
#define listNodeValue(n) ((n)->value)
#define listSetDupMethod(l,m) ((l)->dup = (m))
#define listSetFreeMethod(l,m) ((l)->free = (m))
#define listSetMatchMethod(l,m) ((l)->match = (m))
#define listGetDupMethod(l) ((l)->dup)
#define listGetFree(l) ((l)->free)
#define listGetMatchMethod(l) ((l)->match)
Create a List
When creating a new list, only the header of list
is allocated, the other member variables are assigned to NULL
or 0.
// Time complexity: O(1)
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;
}
The created list can be freed with AlFreeList()
, but private value of every node need to be freed by the user before to call AlFreeList()
.
Remove All Elements
listEmpty(list*)
is called to remove all the elements from the list but not destroy the list itself.
It costs O(n) time complexity because it frees each node in a traversal. if free
function is available, it will be used to release the value of every node. After that, the memory of the node will be collected.
// Time complexity: O(n)
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;
}
While listRelease(list*)
free the whole list including the header.
void listRelease(list *list)
{
listEmpty(list);
zfree(list);
}
Add a New Head
listAddNodeHead
add a new node to the list as the new head. If the list is empty (list->len == 0
), the new node will be the only node with head
and tail
pointing to it. Or, the old head will be moved after the new node and pointers should be updated too.
// Time complexity: O(1)
list *listAddNodeHead(list *list, void *value)
{
listNode *node;
if ((node = zmalloc(sizeof(*node))) == NULL)
return NULL;
node->value = value;
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++;
return list;
}
Insert a Node
The situation becomes more complicated if you want to insert a new node. Note that after
is indicator whether the new node is inserted before or after old_node
.
If you insert a node before old_node
, you may update the head
of the list. Whereas the tail
of the list may be modified if you insert after old_node
.
// Time complexity: O(1)
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 a Node
If you remove the specified node from the specified list, you need to call listDelNode
function. Before freeing the value and memory space of the node, you must change the pointers of its previous and next nodes. And the length also should be updated after your deletion.
// Time complexity: O(1)
void listDelNode(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;
if (list->free) list->free(node->value);
zfree(node);
list->len--;
}
Returns a List Iterator
listGetIterator
returns a list iterator iter
. After the initialization every call to listNext()
will return the next element of the list.
typedef struct listIter {
listNode *next;
int direction;
} listIter;
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;
}
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;
}
Rotate the List
Rotating the list means removing the tail node and inserting it to the head.
// Time complexity: O(1)
void listRotate(list *list) {
listNode *tail = list->tail;
if (listLength(list) <= 1) return;
/* Detach current 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;
}
Join Two Lists
listJoin(list *l, list *o)
adds all the elements of the list o
at the end of the list l
. The list o
remains empty but otherwise valid.
// Time complexity: O(1)
void listJoin(list *l, list *o) {
if (o->head)
o->head->prev = l->tail;
if (l->tail)
l->tail->next = o->head;
else
l->head = o->head;
if (o->tail) l->tail = o->tail;
l->len += o->len;
/* Setup other as an empty list. */
o->head = o->tail = NULL;
o->len = 0;
}