preface

The List data type of Redis, as a data type, its underlying implementation is a linked List. Since the C language used by Redis does not have this data structure built-in, Redis has built its own linked List implementation.

The structure of the List type is a linked List, where each node holds a value. In addition to linked list keys, publish and subscribe, slow query, monitor and other functions also use linked lists. Redis server itself also uses linked lists to store the status information of multiple clients, and uses linked lists to build client output buffers. This article will introduce the linked lists of Redis.

The list

Each linked list is represented using a listNode structure:

typedef struct listNode{
    // The front node
    struct listNode *prev;
    // back node
    struct listNode *next;
    // Node value
    void *value;
}
Copy the code

Multiple ListNodes can form bidirectional lists with prev and next Pointers:

While it is possible to use only multiple listNode structures to form lists, it is much easier to use adlist.h/list to hold lists:

typedef struct list{
    // Table header node
    listNode *head;
    // Table end node
    listNode *tail;
    // The number of nodes in the list
    unsigned long len;
    // 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);
}list;
Copy the code

The list structure provides the head pointer, tail pointer, and len length counter for the list, while the dUP, free, and match members are the type-specific functions needed to implement polymorphic lists:

  • The dUP function is used to copy the values stored by the linked list node.
  • The free function frees the value held by the linked list node;
  • The match function is used to compare the value held by the linked list node to another input value.

The following figure shows a linked list composed of a list structure and three ListNodes

The features of Redis’s linked list implementation are summarized as follows:

  • Double-ended: Linked list nodes have prev and next Pointers, and the complexity of obtaining the pre-node and post-node of a node is O(1).
  • Acyclic: The prev pointer on the head node and the next pointer on the tail node point to NULL, and access to the linked list ends at NULL.
  • With head and tail Pointers: Through the head and tail Pointers of the list structure, the complexity of the program to obtain the head and tail nodes of the linked list is O(1).
  • List length counter: The program uses the len attribute of the list structure to count the list nodes held by the list. The complexity of obtaining the number of nodes in the list is O(1).
  • Polymorphic: Linked list nodes use void* Pointers to hold node values, and you can set type-specific functions for node values through the DUP,free, and match attributes of the list structure, so linked lists can be used to hold various types of values.

summary

Linked lists are widely used to implement Redis features such as list keys, publish and subscribe, slow queries, monitors, and more.

Such as theRedisIf you are interested, please continue to follow this column.