Redis bidirectional linked list article all know

Redis source code analysis series of articles

String low-level implementation – dynamic String SDS

preface

Hello, again. Don’t ask why, to ask is to be industrious. We’re about to go into shock mode. In Redis linked List List is widely used, but Redis is written in C language, the bottom layer of the bidirectional linked List (here mention a word, if it is a class or university students have learned data structure, you can cross out). What we’re going to focus on today is bidirectional lists.

​

Use the API

Let’s start with the API. If you’ve done this before, you can skip to the next section.

Lpush inserts data to the left

Use lpush to insert a, B, and C into the left side of the list. They’ll tell you why. Dig a hole.

​

Rpush inserts data to the right

Insert d and E into the list using rpush. The order is the same as we expected, with d and E as the last two characters.

​

Delete data

Use the lrem command to delete the a character, so what does the middle 1 mean? This is count, which represents the number of elements in the removed list that are equal to A. If count>0, search from the top of the table to the end of the table and remove count elements equal to a. If count<0, search from the end of the table to the end of the table and remove count elements equal to A. If count=0, we remove all elements that are equal to a, because we’re removing all elements, so we get the same result from the top of the table or the bottom of the table.

​

Modify certain data

Use lset to change the subscript 1 of myList to dd. List is c,b, d, e.

​

Concrete logic diagram

It doesn’t matter if you don’t understand this, the following will be detailed for each module.

​

Definition of a bidirectional linked list

Node ListNode

Including the head pointer prev, the tail pointer next, and the current value value, as shown in the figure below. Each node has two Pointers that can find the end of the table from the header pointer or the head of the table from the header pointer prev. If they are joined together, they form a bidirectional linked list.

​

The specific code is as follows:

Typedef struct listNode {// struct listNode *prev; Struct listNode *next; // A pointer to the value of the current node, because the value type is undefined void *value; } listNode;Copy the code

The overall architecture

Including the head pointer head, tail pointer, the length of the whole list len, some functions (I don’t think it is important, if you know it), as shown in the picture below. The head pointer refers to the first node of the list, and the tail pointer refers to the last node of the list.

​

The specific code is as follows:

Typedef struct list {listNode *head; // head pointer listNode *tail; Void *(*dup)(void * PTR); Void (*free)(void * PTR); Int (*match)(void * PTR, void *key); Unsigned long len; // list length} list;Copy the code

Implementation of bidirectional linked list

Create a header

Select * from zmalloc; select * from zmalloc; select * from zmalloc; Then assign the head and tail nodes of the list to NULL, len to 0, and the assignment function to NULL. The result list is returned.

List *listCreate(void) {struct list *list; // Try to allocate spaceif ((list = zmalloc(sizeof(*list))) == NULL)
        returnNULL; List ->head = list->tail = NULL; list->len = 0; list->dup = NULL; list->free = NULL; list->match = NULL; // The final result returnsreturn list;
} 
Copy the code

Clear the table

Pass the pointer to list, first define the current node to point to the header pointer, and define len to be equal to the length of list. A new node is defined next, always pointing to the next node of the current node. If there is a value, the node will be released. The current node will move forward, and the next node will move forward as well. Until len is 0, all nodes are freed and the loop exits. Finally, assign the head and tail nodes of the list to NULL and len to 0.

Note: As with SDS, the list is not deleted directly, but its data is deleted. The outer list structure still exists. This is essentially lazy deletion.

void listEmpty(list *list) { unsigned long len; ListNode *current, *next; Current = list->head; Len = list->len; // Start the loop by decreasing len by 1 each timewhile(len--) {next = current->next; // Releases the value of the current nodeif(list->free) list->free(current->value); // Release the current node zfree(current); // The current node is equal to the next node, which is the beginning of the next cycle. List ->head = list->tail = NULL; List ->len = 0; }Copy the code

Add an element to the table header

Add an element to the table header, first create a new node, node, check whether there is memory allocation, if so, continue, if not, return NULL, exit the method. This new node is used to store the value in the input parameter, so it needs memory. We then assign the value of the new node node to the input parameter value. Finally, we need to adjust the head pointer, tail pointer, and pointer of the first node. And finally, len of list plus 1, returns list.

For example, if you want to insert node F into the list, first set the head pointer of the node to null (corresponding to step 1), then set the tail pointer of the new node next to the first node (corresponding to step 2), and set the prev of the first node to the new node (corresponding to Step 3), Finally, the list’s head pointer points to the new node (corresponding to Step 4). Note that steps 2 and 3 need to come before Step 4, otherwise the first node will be found.

​

The specific code is as follows:

List *listAddNodeHead(list *list, void *value) {listNode *node;if ((node = zmalloc(sizeof(*node))) == NULL)
        returnNULL; node->value = value; // Assign a value to the current node // If the current list is emptyif(list->len == 0) { list->head = list->tail = node; Prev = node->next = NULL; // The first and last Pointers of the current node are both null}else{// If the current list is not empty node->prev = NULL; // New node head pointer null node->next = list->head; List ->head->prev = node; List ->head = node; } list->len++; / / the list length + 1return list;
}Copy the code

Add an element to the end of the table

Add the element to the end of the table, first create a new node, node, check whether there is memory allocation, if so, continue, if not, return NULL, exit method. This new node is used to store the value in the input parameter, so it needs memory. We then assign the value of the new node node to the input parameter value. Finally, we need to adjust the head pointer, tail pointer, and pointer of the last node of the list. And finally, len of list plus 1, returns list.

, for example, if you want to insert node f in the list, first of all the nodes of the tail pointer assignment is empty (step 1), then the head of the new node pointer to the last node (step 2), will be the last node of the next point to the new node (step 3), the final will be a list of the tail pointer tail pointing to the new node (step 4).

​

The steps are as follows:

List *listAddNodeTail(list *list, void *value) {// Create a new node. // Try to allocate memoryif ((node = zmalloc(sizeof(*node))) == NULL)
        returnNULL; Node ->value = value; // Adjust the pointerif (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++;return list;
} Copy the code

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 > 0 ->prev = old_node; node->next = old_node->next;if(list->tail == old_node) { list->tail = node; }}else{// less than 0 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;
}Copy the code

Void listDelNode(list *list, listNode *node) {// If there is a node in front of the nodeif (node->prev)
        node->prev->next = node->next;
    elselist->head = node->next; // If there is a node before this nodeif (node->next)
        node->next->prev = node->prev;
    elselist->tail = node->prev; // Release the value of the current nodeif(list->free) list->free(node->value); // Free memory zfree(node); //len-1 list->len--; }Copy the code

conclusion

This article mainly talks about the Redis list data type of the bottom realization of bidirectional linked list ADList, first from the list of some API use, derived bidirectional linked list data structure, and then combined with the source code to describe the bidirectional linked list, including nodes listNode and list of head pointer and tail pointer, Finally, for list to insert elements to the head of the table, insert elements to the tail of the table, delete, modify the source code analysis, so that it has a clearer understanding of the bidirectional linked list.

If you feel that writing is also good, trouble to give a praise 👍, your recognition is the power of my writing!

If you think something is wrong, please feel free to comment.

All right, bye.

And a focus on