“This is the 30th day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

Introduction of the list

Redis lists are nothing special, just plain bidirectional lists adlist.c/listNode.

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

Copy the code

Multiple ListNodes can form a double-ended list using prev and NEXT, as shown below:

Prev and next of the head and tail nodes point to null respectively.

Lists can be formed using the listNode structure, but it is more convenient to hold lists using adlist.c/list:

typedef struct list {
    / / head node
    listNode *head;
    / / end nodes
    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 bytes the linked list contains
    unsigned long len;
} list;
Copy the code

A linked list with a list structure and three listNode structures

List features

  • 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 of the table point to NULL, and the access to the linked list is 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 property of the list structure to count which list nodes the list holds. The program gets a load of O(1) for the number of nodes in the list.
  • Polymorphic: Linked list nodes use void* Pointers to hold node values, and you can use the dUP, free, and match properties of the list structure to set type-specific functions for node values. So linked lists can be used to hold a variety of different types of values.

The iterator

The iterator mode is used in levelDB for many scenarios. You can search for iterator mode.

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

listIter *listGetIterator(list *list.int direction)
{
    listIter *iter;

    if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;
    if (direction == AL_START_HEAD)
        iter->next = list->head;
    else
        iter->next = list->tail;
    iter->direction = direction;
    return iter;
}

Copy the code

Using the scenario

  • Linked lists are widely used to realize various functions of Redis, such as list keys, publish and subscribe, full query, monitor, etc.
  • Redis lists can be used to hold various types of values by setting different type-specific functions for the lists.

The resources

  • redis.io
  • Redis Design and Implementation, Huang Jianhong