[redis underlying parsing] linked list type

Linked list

Linked list provides efficient node rearrangement capability , And sequential node access , And you can flexibly adjust the length of the linked list by adding and deleting nodes .

The list is in redis Is also widely used , For example, publish and subscribe , The slow query , Linked lists are also used in functions such as monitors . It also uses a linked list to store the status information of multiple clients , And using linked list to build client output buffer (output buffer).

1. The realization of linked list and linked list node

Each linked list node uses one adlist.h/listNode Structure to express ：

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

Multiple listNode Can pass prev and next The hands make up Double ended linked list

As shown in the figure below

Although only multiple listNode Structure can form a linked list , But with adlist.h/list To hold the list , It will be more convenient to operate .

typedef struct list{
    
	listNode *head; //  header node 
	listNode *tail; //  Tail node 
	unsigned long len; //  Number of nodes in the list 
	void *(*dup)(void *ptr); //  Node value copy function 
	void *(*free)(void *ptr); //  Node value release function 
	int (*match)(void *ptr,void *key); //  Node value comparison function 
}list;

list The structure provides a pointer to the head of the linked list head, Tail pointer tail, And chain length counter len.
dup,free and match Members are type specific functions used to implement polymorphic linked lists .

• dup Used to copy the value saved by the linked list node
• free Function is used to release the value saved by the linked list node
• match Function is used to compare whether the value maintained by the linked list node is equal to another input value

2. The characteristics of linked list

• Two ends ： Link list nodes with prev and next The pointer , The complexity of obtaining the pre node and post node of a node is O(1)
• acyclic ： Of the header node prev Pointer and tail node next The hands all point to NULL, Access to the linked list NULL End point .
• With head pointer and tail pointer ： adopt list The structure and head The pointer and tail The pointer , The complexity of getting the header node and the tail node of the linked list is O(1)
• With linked list length counter ： Program usage list Structural len attribute Come on list Count the number of linked list nodes held , The complexity of the program to obtain the number of nodes in the linked list is also O(1)
• polymorphic ： Link list node use void* Pointer to save the node value , And through list Structural dup,free,match Three properties set type specific functions for node values , So linked lists can be used to hold different types of values .