Redis 5.0 data structure double end linked list source code analysis

summary

Linked list can provide efficient node rearrangement and sequential node access , And you can flexibly adjust the length of the linked list by adding and deleting nodes .Redis be based on C Language development ,C The language has no built-in linked list , therefore Redis I have realized a series of linked lists , Two end linked list linkedlist、 Compress the list ziplist、 Quick list quicklist etc. , This article will show the double ended linked list from the perspective of source code linkedlist.

Redis Medium list Realization

as everyone knows Redis There are five types of data , Linked list is one of them , stay Redis stay 3.2 edition , Revised list The underlying implementation of , stay Redis 3.2 Before, the linked list was composed of two end linked list linkedlist And compressed linked list ziplist Jointly realized ,Redis3.2 After the version, it is mainly optimized for fast linked list quicklist.

Redis3.2 Before , When the following two conditions are satisfied simultaneously ,list The realization of is ziplist, In other cases, use linkedlist

• The string length of all key values stored in hash object is less than 64 byte ;
• The number of key value pairs saved by the hash object is less than 512 individual ;

The source code versions used in this article are Redis 5.0, It mainly introduces the double ended linked list linkedlist The source code comes from adlist.h and adlist.c Two documents .

linkedlist data structure

linkedlist Structure source code

For... In a double ended linked list node , Use adlist.h/listNode Structure , Source code is as follows ：

typedef struct listNode {
    
	//  Front node 
    struct listNode *prev;
    //  Post node 
    struct listNode *next;
    //  value 
    void *value;
} listNode;

It is obvious that each node can directly access the nodes before or after it , so Redis in list The implementation of is a double ended linked list .

By a number of listNode The two terminal chain composed of nodes is intended as follows ：

————————————————————————————————————————

about Double ended linked list , Use adlist.h/list Structure to express , Source code is as follows ：

typedef struct list {
    
	//  Head node 
    listNode *head;
    //  Tail 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 contained in the linked list 
    unsigned long len;
} list;

list Structure provides a header pointer for the linked list head And tail pointer tail And the length of the linked list len. For the three built-in functions , respectively ：

• dup The function is used to copy the... Stored in the linked list node value value .
• free The function is used to release the... Saved by the linked list node value value .
• match The function is used to compare the saved in the linked list node value Whether the value is equal to another input value .

One contains three listNode List of nodes list The structural diagram is as follows ：

————————————————————————————————————————
The structure of the double ended linked list iterator is as follows ：

typedef struct listIter {
    
    listNode *next;
    int direction;
} listIter;

There are two strategies for the iteration of linked lists: from beginning to end and from end to end , adopt direction Attribute representation , When its value is 0 Tense means from beginning to end , When its value is 1 Tense means from end to end .

Main function

First, in the adlist.h Provides a series of macro definition functions for developers , So that the structure can be operated , Source code is as follows ：

/* Functions implemented as macros */
#define listLength(l) ((l)->len) //  Get the current linked list length 
#define listFirst(l) ((l)->head) //  Get the header node 
#define listLast(l) ((l)->tail) //  Get tail node 
#define listPrevNode(n) ((n)->prev) //  Get the previous node of the current node 
#define listNextNode(n) ((n)->next) //  Get the next node of the current node 
#define listNodeValue(n) ((n)->value) //  Get current node value value 

#define listSetDupMethod(l,m) ((l)->dup = (m)) //  Set up dup function 
#define listSetFreeMethod(l,m) ((l)->free = (m)) //  Set up free function 
#define listSetMatchMethod(l,m) ((l)->match = (m)) //  Set up match function 

#define listGetDupMethod(l) ((l)->dup) //  obtain dup function 
#define listGetFree(l) ((l)->free) //  obtain free function 
#define listGetMatchMethod(l) ((l)->match) // obtain match function 

Linked list creation

The source code implementation is very simple , Open up space , Assign initial values to each attribute .

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;
}

Chain list recycling

For the recycling of linked lists / Delete ,Redis Two functions are provided , Namely listEmpty and listRelease, The former releases all nodes in the linked list , But not recycled list Its own space , The latter is fully released

void listEmpty(list *list)
{
    
    unsigned long len;
    listNode *current, *next;

    current = list->head;
    len = list->len;
    //  Self decrement through the counter 0  Release the node space in turn 
    while(len--) {
    
        next = current->next;
        //  If there is a specially defined linked list release function   The first call 
        if (list->free) list->free(current->value);
        //  The release of the node 
        zfree(current);
        current = next;
    }
    list->head = list->tail = NULL;
    list->len = 0;
}

void listRelease(list *list)
{
    	
	//  reusing listEmpty Function to release the linked list itself 
    listEmpty(list);
    zfree(list);
}

Iterator operation

Iterator related implementations are simple , See the comments , The source code of related functions is as follows ：

//  Acquisition iterator 
listIter *listGetIterator(list *list, int direction)
{
    
    listIter *iter;

    if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;
    //  According to the iteration strategy   Determines whether the iterator initialization is assigned to the head node or the tail node 
    if (direction == AL_START_HEAD)
        iter->next = list->head;
    else
        iter->next = list->tail;
    iter->direction = direction;
    return iter;
}
//  The iterator releases 
void listReleaseIterator(listIter *iter) {
    
    zfree(iter);
}

//  Forward reset iterator 
void listRewind(list *list, listIter *li) {
    
    li->next = list->head;
    li->direction = AL_START_HEAD;
}
//  Reverse reset iterator 
void listRewindTail(list *list, listIter *li) {
    
    li->next = list->tail;
    li->direction = AL_START_TAIL;
}
//  Get the next 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;
}

Add operation

stay Redis In the process of actually using the linked list , Developers will definitely use lpush and rpush Instructions , Its functions are realized by the following two functions , Because it is a double ended queue , You can simply get the head node and the tail node , Nodes can also access their front and back nodes , therefore lpush and rpush The same set of logic used , The source code of related functions is as follows ：

//  Add a new node that is the head node of the linked list 
list *listAddNodeHead(list *list, void *value)
{
    	
	//  Create nodes   Initial value 
    listNode *node;

    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    node->value = value;
    //  Special processing when the linked list is empty 
    if (list->len == 0) {
    
        list->head = list->tail = node;
        node->prev = node->next = NULL;
    } else {
    
    	//  Change the original header node   New node  head Pointer pointing 
        node->prev = NULL;
        node->next = list->head;
        list->head->prev = node;
        list->head = node;
    }
    //  Counter auto increment 
    list->len++;
    return list;
}
//  Add a node that is the tail node of the linked list 
//  Logic and listAddNodeHead identical   It's just an operation tail Pointer and tail node 
list *listAddNodeTail(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 = list->tail;
        node->next = NULL;
        list->tail->next = node;
        list->tail = node;
    }
    list->len++;
    return list;
}

————————————————————————————————————————
except push operation , You can also use linsert Insert new node , The actual syntax is ：
linsert key before|after value1 value2
The semantic value in the linked list is value1 Before the node | Then insert a value of value2 The node of , If no value in the linked list is value1 The node of , Do not operate . The function shown below is responsible for the insertion operation ：

//  Pass in the old node   The value of the node to be inserted   And the insertion position 
//  among  after by 0 When, it means to insert forward  after by 1 When, it means to insert backward 
list *listInsertNode(list *list, listNode *old_node, void *value, int after) {
    
    //  The new node   Initial value 
    listNode *node;

    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    node->value = value;
    //  Insert... Before the target node 
    if (after) {
    
        node->prev = old_node;
        node->next = old_node->next;
        if (list->tail == old_node) {
    
            list->tail = node;
        }
    //  Insert... After the target 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;
    }
    //  Counter auto increment 
    list->len++;
    return list;
}

Delete operation

The delete operation is performed by listDelNode Function implementation , This is achieved by passing in the target node instead of the target value .

void listDelNode(list *list, listNode *node)
{
    	
	//  Change the direction of the front and back nodes of the target 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);
    //  Free the memory space of the target node 
    zfree(node);
    //  Counter auto decrement 
    list->len--;
}

Search operation

Redis Built in two node lookup functions , Namely listSearchKey Functions and listIndex function , The former finds by value , The latter is searched by serial number , That is to find a node in the linked list .

//  Find by value 
listNode *listSearchKey(list *list, void *key)
{
    
	//  Use iterators to traverse   After the iterator is initially obtained, it defaults to positive order iteration 
    listIter iter;
    listNode *node;

    listRewind(list, &iter);
    while((node = listNext(&iter)) != NULL) {
    
    	//  If there is a specially defined node matching function   Call 
        if (list->match) {
    
            if (list->match(node->value, key)) {
    
                return node;
            }
        //  Otherwise, carry out ordinary value Value comparison 
        } else {
    
            if (key == node->value) {
    
                return node;
            }
        }
    }
    //  The target node cannot be found. Return NULL
    return NULL;
}
//  Find by serial number 
//  here index There are two kinds of expressions   When index When the value is positive, it means that the search is in positive order from beginning to end   On the contrary, search in reverse order 
listNode *listIndex(list *list, long index) {
    
    listNode *n;
	//  Search in reverse order 
    if (index < 0) {
    
    	// index Value will not be 0  If index yes -1  Means the tail node 
        index = (-index)-1;
        n = list->tail;
        while(index-- && n) n = n->prev;
    //  Positive search 
    } else {
    
        n = list->head;
        while(index-- && n) n = n->next;
    }
    return n;
}

Copy list

Redis Provides a linked list copy function listDup, The source of the function is as follows ：

//  Copy the entire linked list 
list *listDup(list *orig)
{
    
    list *copy;
    listIter iter;
    listNode *node;

    if ((copy = listCreate()) == NULL)
        return NULL;
    //  Copy related operation functions 
    copy->dup = orig->dup;
    copy->free = orig->free;
    copy->match = orig->match;
    listRewind(orig, &iter);
    while((node = listNext(&iter)) != NULL) {
    
        void *value;
		//  If specifically defined dup Copy function   execute 
        if (copy->dup) {
    
            value = copy->dup(node->value);
            if (value == NULL) {
    
                listRelease(copy);
                return NULL;
            }
        //  Otherwise, the direct value is copied 
        } else
            value = node->value;
        //  Add a node to the tail 
        if (listAddNodeTail(copy, value) == NULL) {
    
            listRelease(copy);
            return NULL;
        }
    }
    return copy;
}

---

Some contents and picture references / Excerpt from ：《Redis Design and implementation 》—— Huang Jianhong