Redis is written in C language, but because C language does not have the structure of built-in linked list, Redis uses the structure of bidirectional linked list as its own implementation. As we all know, the linked list structure has the advantage of no continuous memory space, and the time complexity of insert and delete is O(1) level, which is relatively high, but its disadvantage is that compared to array, the query efficiency is not so high.
Bidirectional linked list contents
What a bidirectional linked list node looks like in Redis:
Specific code
/* * Two-way linked list node */
typedef struct listNode {
// A pointer to the front node
struct listNode *prev;
// A pointer to a trailing node
struct listNode *next;
// Node value
void *value;
} listNode;
Copy the codeA node consists of prev, next, and value (c in the image).
A concrete bidirectional linked list structure in Redis looks like:
Specific code
/* * Two-way list structure */
typedef struct list {
// Table header node
listNode *head;
// Table end node
listNode *tail;
// Node value copy function
void *(*dup)(void *ptr);
// Node value release function
void (*free) (void *ptr);
// Node value comparison function
int (*match)(void *ptr, void *key);
// The number of nodes in the linked list
unsigned long len;
} list;
Copy the codeIn the list structure, head refers to the first node of the bidirectional list, tail refers to the last node of the bidirectional list, len represents the number of bidirectional list nodes, DUP is used to copy the value of the bidirectional list node, free is used to release the value of the bidirectional list node. The match function is used to compare whether the value stored by a bidirectional list node is equal to the input value of another.
Advantages of using bidirectional linked lists
- In the bidirectional linked list structure of Redis, the time complexity of the front and back nodes of a node is O(1) through the pointer before and after.
- Through the head pointer and tail pointer in the structure, the time complexity of the program to obtain the head node and the tail node of the bidirectional list is O(1).
- Both the leading pointer to the head node and the trailing pointer to the tail node point to NULL, and access to the bidirectional list ends with NULL
- The program directly obtains the number of nodes through the len attribute of the structure, the time complexity is O(1), and the efficiency is high
- The value of the linked list node uses the void* pointer to store the specific node value, and the dUP, free and match attributes in the structure can be set to different types of node value, because their input parameters have void*, such a design makes the bidirectional linked list node can basically store various types of data
Bidirectional linked list implementation
Create a list
If zmolloc fails to allocate memory, NULL will be returned. If zmolloc fails to allocate memory, NULL will be returned. If zmolloc fails, NULL will be returned. The dUP, free, and match attributes are set to NULL and len is set to 0. After successful initialization, return list.
list *listCreate(void){
struct list *list;
// Allocate memory
if ((list = zmalloc(sizeof(*list))) = =NULL)
return NULL;
// Initialize the property
list->head = list->tail = NULL;
list->len = 0;
list->dup = NULL;
list->free = NULL;
list->match = NULL;
return list;
}
Copy the codeInsert the node
If the allocation fails, NULL will be returned. After the new node is successfully created, the value of the new node will be saved to the new node node. Then according to the after value, the new node will be inserted before the old node. If it is 1, insert the new node after the old node, adjust the position of the pointer before and after the old node according to the position of the old node, then add 1 to the len value of the structure, and finally return the new bidirectional linked list structure.
list *listInsertNode(list *list, listNode *old_node, void
*value, int after) {
listNode *node;
// Create a node
if ((node = zmalloc(sizeof(*node))) == NULL)
return NULL;
/ / save the value
node->value = value;
// Add the new node after the given node
if (after) {
node->prev = old_node;
node->next = old_node->next;
// The given node is the last node of the original table
if (list->tail == old_node) {
list->tail = node;
}
// Add the new node before the given node
} else {
node->next = old_node;
node->prev = old_node->prev;
// The given node is the original table head node
if (list->head == old_node) {
list->head = node; }}// Update the leading pointer to the new node
if(node->prev ! =NULL) {
node->prev->next = node;
}
// Update the post-pointer of the new node
if(node->next ! =NULL) {
node->next->prev = node;
}
// Update the number of linked list nodes
list->len++;
return list;
}
Copy the codeRemove nodes
Firstly, it is determined whether the leading pointer of the node to be deleted exists. If so, the post-pointer of the previous node of the node points to the next node of the node; if not, the head pointer of the structure points to the next node of the node. Similarly, we then determine whether the rear pointer of the deleted node exists. If so, the leading pointer of the next node of the node points to the last node of the node. If not, the tail pointer of the structure points to the last node of the node. If the free node value release function exists, the value of the node will be released, and finally the node will be released by zfree function and the len length of the linked list will be reduced by one.
void listDelNode(list *list, listNode *node){
// Adjust the pointer to the front node
if (node->prev)
node->prev->next = node->next;
else
list->head = node->next;
// Adjust the pointer to the rear node
if (node->next)
node->next->prev = node->prev;
else
list->tail = node->prev;
/ / release value
if (list->free) list->free(node->value);
// Release the node
zfree(node);
// The number of linked lists is reduced by one
list->len--;
}
Copy the codeRelease of the list
Start by defining a current node and pointing to the head pointer, and get len, the number of nodes in the original list, through which len traverses each node. If the node-value release function exists, the node-value release function is called to release the value saved by the current node, and then the node-structure is released. The node-value of current is null. Then change the node corresponding to next to current and start a new wave of operations until len is 0. Finally, the zfree function is called to release the entire list structure.
void listRelease(list *list){
unsigned long len;
listNode *current, *next;
// point to a header pointer
current = list->head;
// Iterate through the list
len = list->len;
while(len--) {
next = current->next;
// If there is a set value release function, then call it
if (list->free) list->free(current->value);
// Release the node structure
zfree(current);
current = next;
}
// Release the list structure
zfree(list);
}
Copy the codeThrough the source of part of the reading, to understand the Redis two-way linked list structure of the operation, the specific can read the Redis source adlist.c part.
Application scenarios of bidirectional linked lists
Redis uses the bidirectional linked List structure for publish and subscribe, slow query, monitor, and data structure List. It also uses linked lists to store the status information of multiple clients, and uses linked lists to build client output buffers.
Reference: Redis Design and Implementation
For more Java backend development related technologies, you can follow the public account “Red Orange ah”.