linked list

Redis is a self-implemented list. Linked lists are widely used in various functions of Redis, such as list keys, publishing to subscriptions, slow queries, monitors, etc.

One of the underlying implementations of list keys is linked lists. Reids uses linked lists as the underlying implementation of list keys when a list building contains a large number of elements, or when the elements in the list are long strings. (Redis Design and Implementation)

Characteristic

Redis Design and Implementation

• Each list node is represented by a listNode structure, and each node is represented by a pointer to the pre-node and post-node. All Redis's list implementation is a double-ended list.
• Each linked list is represented by a list structure with information such as the header node pointer, the epitope node pointer and the length of the linked list.
• Because the pre-node of the head node and the post-node of the end node of the list point to NULL, Redis's list implementation is an acyclic list.
• By setting different types of specific functions for the linked list, Redis's linked list can be used to store different types of values.

Code structure

// adlist.h

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

// Linked list structure
typedef struct list {
    listNode *head; // header node
    listNode *tail; // Tail node
    void *(*dup)(void *ptr); // Node Value Copy Function Pointer
    void (*free)(void *ptr); // Node Value Release Function Pointer
    int (*match)(void *ptr, void *key); // Node Value Contrast Function Pointer
    unsigned long len; // Number of nodes contained in linked list
} list;

// Iterator of linked list
typedef struct listIter {
    listNode *next; // Next node
    int direction; // Iterative direction
} listIter;

• The dup function is used to copy the values saved by the linked list nodes.
• free function is used to release the values saved by linked list nodes.
• The match function is used to compare whether the value saved by the linked list node is equal to another input value.

Partial code parsing

• List * list AddNodeHead (list * list, void * value) adds a list header to the 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;
  
  	    // Allocate memory for linked list nodes
  	    if ((node = zmalloc(sizeof(*node))) == NULL)
  	        return NULL;
  	    // value assignment for linked list nodes
  	    node->value = value;
  
  	    if (list->len == 0) {
  	        // If the list does not have nodes, both the header node and the tail node are set to nodes.
  	        list->head = list->tail = node;
  	        // And the pre-and post-nodes of node are NULL
  	        node->prev = node->next = NULL;
  	    } else {
  	        // If the list already has nodes
  	        // Set the node's preceding node to NULL
  	        node->prev = NULL;
  	        // Then point the node's post-node to the original table header node of the list
  	        node->next = list->head;
  	        // Point the pre-node of the original list header node to the node
  	        list->head->prev = node;
  	        // Set node as a new table header node for list
  	        list->head = node;
  	    }
  	    // list length plus 1
  	    list->len++;
  	    return list;
  	}
  

• list *listInsertNode(list *list, listNode *old_node, void *value, int after) inserts node value into the list at the old_node position, which means before or after old_node:

  	list *listInsertNode(list *list, listNode *old_node, void *value, int after) {
  	    listNode *node;
  
  	    // Allocate memory to the node to be inserted
  	    if ((node = zmalloc(sizeof(*node))) == NULL)
  	        return NULL;
  	    // value assignment of node
  	    node->value = value;
  
  	    if (after) {
  	        // After inserting into old_node
  	        node->prev = old_node;
  	        node->next = old_node->next;
  	        if (list->tail == old_node) {
  	            // If old_node is originally a table-tail node, then the table-tail node is redirected to the node.
  	            list->tail = node;
  	        }
  	    } else {
  	        // Insert before old_node
  	        node->next = old_node;
  	        node->prev = old_node->prev;
  	        if (list->head == old_node) {
  	            // If old_node is originally a header node, then the tail node is redirected to the node
  	            list->head = node;
  	        }
  	    }
  	    if (node->prev != NULL) {
  	        //If the node's preceding node is not NULL, the node's preceding node's posterior node is pointed to the node.
  	        node->prev->next = node;
  	    }
  	    if (node->next != NULL) {
  	        //If the node's post-node is not NULL, the node's pre-node of the post-node is pointed to the node.
  	        node->next->prev = node;
  	    }
  	    // list length plus 1
  	    list->len++;
  	    return list;
  	}
  

• Void list DelNode (list * list, listNode * node) deletes the node node node in the list:

  	/* Remove the specified node from the specified list.
  	 * It's up to the caller to free the private value of the node.
  	 *
  	 * This function can't fail. */
  	void listDelNode(list *list, listNode *node)
  	{
  	    if (node->prev)
  	        // If node has a leading node
  	        // Point the post-node of the node's front node to the post-node of the node
  	        node->prev->next = node->next;
  	    else
  	        // If node does not have a pre-node, then node is a header node
  	        // Point the list header node to the post-node of the node
  	        list->head = node->next;
  	    if (node->next)
  	        // If node has a post-node
  	        // Point the front node of the node's post-node to the front node of the node
  	        node->next->prev = node->prev;
  	    else
  	        // If node does not have a post-node, then node is the end of the table node
  	        // Point the list tail node to the node's leading node
  	        list->tail = node->prev;
  
  	    // If the list has a free function, the free function is called to release the value in the node
  	    if (list->free) list->free(node->value);
  	    // Release node memory
  	    zfree(node);
  	    // list length minus 1
  	    list->len--;
  	}
  

Linked list API

Reference to Redis Design and Implementation