Detail the double list structure in Redis
- 2020-05-13 03:48:22
- OfStack
Basic structure of double-linked list implementation in Redis:
1. Node structure
typedef struct listNode {
struct listNode *prev; // Prior to the node
struct listNode *next; // After to the node
void *value; // The value of the node
} listNode;
2. Two-way linked list structure
typedef struct list {
listNode *head; // Head node
listNode *tail; // End node
void *(*dup)(void *ptr); // Copy the function
void (*free)(void *ptr); // Release function
int (*match)(void *ptr, void *key); // Match the function to find the node to use
unsigned long len; // The length of the bidirectional list is the number of nodes
} list;
3. Two-way linked list traverser
typedef struct listIter {
listNode *next; // Under the 1 A node
int direction;
} listIter;
Define the direction
#define AL_START_HEAD 0 // Look ahead
#define AL_START_TAIL 1 // Look behind
Macros define functions
#define listLength(l) ((l)->len)
#define listFirst(l) ((l)->head)
#define listLast(l) ((l)->tail)
#define listPrevNode(n) ((n)->prev)
#define listNextNode(n) ((n)->next)
#define listNodeValue(n) ((n)->value)
#define listSetDupMethod(l,m) ((l)->dup = (m))
#define listSetFreeMethod(l,m) ((l)->free = (m))
#define listSetMatchMethod(l,m) ((l)->match = (m))
#define listGetDupMethod(l) ((l)->dup)
#define listGetFree(l) ((l)->free)
#define listGetMatchMethod(l) ((l)->match)
5. Define functions
list *listCreate(void); // create 1 Two new linked lists. This list can be used AlFree () method release.
// But the use of AlFree The value of the user-released private node needs to be released before the () method.
// If it was not created successfully, return null ; Successful creation returns a pointer to the new list.
void listRelease(list *list); // Release the entire list and this function will not fail. call zfree(list *list) methods , Defined in the Zmalloc.c In the.
list *listAddNodeHead(list *list, void *value); // Add to the top of the list 1 A node
list *listAddNodeTail(list *list, void *value); // Add to the end of the list 1 A node
list *listInsertNode(list *list, listNode *old_node, void *value, int after);// Insert a node into a node location after For the direction
void listDelNode(list *list, listNode *node);// When a specific node is removed from the list, the caller releases the value of the specific private node.
// This function does not fail to execute
listIter *listGetIterator(list *list, int direction);// Returns an iterator for a linked list.
// iterator listNext The () method returns the next node in the list. direction Is the direction
// This function does not fail to execute.
listNode *listNext(listIter *iter);
void listReleaseIterator(listIter *iter); // Free the memory of the iterator.
list *listDup(list *orig); // Copy the entire list. Returns when memory runs out null , which returns the original list on success 1 A backup
// Regardless of whether the method is executed successfully, the original list will not change.
listNode *listSearchKey(list *list, void *key); // Look up from a particular list key . Success returns first 1 A pointer to a matching node
// If there is no match, it returns null .
listNode *listIndex(list *list, long index); // The serial number from 0 To start, the index of the header of the list is 0.1 Is the next node of the header node. 1 So on.
// Negative integers are used to indicate counting from the tail. -1 Said the last 1 A node, -2 From the first 2 A node
// Returns if the index of the list is exceeded null
void listRewind(list *list, listIter *li) {
li->next = list->head;
li->direction = AL_START_HEAD;
}
void listRewindTail(list *list, listIter *li) {
li->next = list->tail;
li->direction = AL_START_TAIL;
}
void listRotate(list *list); // Rotate the list to remove the tail and insert the head.
list structure and API listNode structure
Both list and listNode have their own family of 1, API. Here you can learn the source code of redis.
list *listCreate(void)
/**
* create 1 A new list
*
* T = O(1)
*/
list *listCreate(void)
{
struct list *list;
// Allocate memory for the list structure
list = (struct list *)malloc(sizeof(struct list));
if (list == NULL)
return NULL;
// Initialization property
list->head = list->tail = NULL;
list->len = 0;
list->dup = NULL;
list->free = NULL;
list->match = NULL;
return list;
}
void listRelease(list *list)
/**
* Release the entire list
*
* T = O(N), N Is the list length
*/
void listRelease(list *list)
{
unsigned long len;
listNode *current, *next;
current = list->head;
len = list->len;
while (len --) {
next = current->next;
// If the list comes with its own free Method, so call it first on the node value
if (list->free) list->free(current->value);
// And then release the node
free(current);
current = next;
}
free(list);
} list *listAddNodeHead(list *list, void *value)
/**
* new 1 Individual inclusion given value , and add it to the header of the list
*
* T = O(1)
*/
list *listAddNodeHead(list *list, void *value)
{
listNode *node;
node = (listNode *)malloc(sizeof(listNode));
if (node == NULL)
return NULL;
node->value = value;
if (list->len == 0) {
// The first 1 A node
list->head = list->tail = node;
node->prev = node->next = NULL;
} else {
// Not the first 1 A node
node->prev = NULL;
node->next = list->head;
list->head->prev = node;
list->head = node;
}
list->len ++;
return list;
}
list *listAddNodeTail(list *list, void *value)
/**
* new 1 Individual inclusion given value And add it to the end of the list
*
* T = O(1)
*/
list *listAddNodeTail(list *list, void *value)
{
listNode *node;
node = (listNode *)malloc(sizeof(listNode));
if (node == NULL)
return NULL;
if (list->len == 0) {
// The first 1 A node
list->head = list->tail = node;
node->prev = node->next = NULL;
} else {
// Not the first 1 node
node->prev = list->tail;
node->next = NULL;
list->tail->next = node;
list->tail = node;
}
list->len ++;
return list;
}
list *listInsertNode(list *list, listNode *old_node, void *value, int after)
/**
* create 1 Contains values value The nodes of the
* And according to the after Parameter to insert the new node into old_node Before or after
*
* T = O(1)
*/
list *listInsertNode(list *list, listNode *old_node, void *value, int after)
{
listNode *node;
node = (listNode *)malloc(sizeof(listNode));
if (node == NULL)
return NULL;
if (after) {
// Inserted into the old_node after
node->prev = old_node;
node->next = old_node->next;
// Handle the table tail node
if (list->tail == old_node) {
list->tail = node;
}
} else {
// Inserted into the old_node before
node->next = old_node;
node->prev = old_node->prev;
// Handle header nodes
if (list->head == old_node) {
list->head = node;
}
}
// Updates Pointers to the leading and following nodes ( This is a classic place to save code )
if (node->prev != NULL) {
node->prev->next = node;
}
if (node->next != NULL) {
node->next->prev = node;
}
// Update list node
list->len ++;
return list;
}
void listDelNode(list *list, listNode *node)
typedef struct list {
listNode *head; // Head node
listNode *tail; // End node
void *(*dup)(void *ptr); // Copy the function
void (*free)(void *ptr); // Release function
int (*match)(void *ptr, void *key); // Match the function to find the node to use
unsigned long len; // The length of the bidirectional list is the number of nodes
} list;
The iterator
In fact, I am very unfamiliar with the concept of iterator, because I am a pure c programmer, can not c++, here directly follow to learn!
Redis implements an iterator for the list structure to traverse the linked list
The structure of the iterator is defined as follows:
typedef struct list {
listNode *head; // Head node
listNode *tail; // End node
void *(*dup)(void *ptr); // Copy the function
void (*free)(void *ptr); // Release function
int (*match)(void *ptr, void *key); // Match the function to find the node to use
unsigned long len; // The length of the bidirectional list is the number of nodes
} list;
direction determines whether the iterator iterates backward along the next pointer or forward along the prev pointer. This value can be the AL_START_HEAD constant in adlist.h or AL_START_TAIL constant:
typedef struct list {
listNode *head; // Head node
listNode *tail; // End node
void *(*dup)(void *ptr); // Copy the function
void (*free)(void *ptr); // Release function
int (*match)(void *ptr, void *key); // Match the function to find the node to use
unsigned long len; // The length of the bidirectional list is the number of nodes
} list;
Learn 1 about the implementation of the api iterator:
listIter *listGetIterator(list *list, int direction)
/**
* Create a list of list the 1 The iteration direction is determined by the parameters direction decision
*
* Each time to the iterator listNext(), The iterator returns the bottom of the list 1 A node
*
* T = O(1)
*/
listIter *listGetIterator(list *list, int direction)
{
listIter *iter;
iter = (listIter *)malloc(sizeof(listIter));
if (iter == NULL)
return NULL;
// Depending on the direction of the iterator, point the pointer to the header or footer of the table
if (direction == AL_START_HEAD) {
iter->next = list->head;
} else {
iter->next = list->tail;
}
// Record the direction
iter->direction = direction;
return iter;
}
void listRewind(list *list, listIter *li)
typedef struct list {
listNode *head; // Head node
listNode *tail; // End node
void *(*dup)(void *ptr); // Copy the function
void (*free)(void *ptr); // Release function
int (*match)(void *ptr, void *key); // Match the function to find the node to use
unsigned long len; // The length of the bidirectional list is the number of nodes
} list;
void listRewindTail(list *list, listIter *li)
typedef struct list {
listNode *head; // Head node
listNode *tail; // End node
void *(*dup)(void *ptr); // Copy the function
void (*free)(void *ptr); // Release function
int (*match)(void *ptr, void *key); // Match the function to find the node to use
unsigned long len; // The length of the bidirectional list is the number of nodes
} list;
listNode *listNext(listIter *iter)
typedef struct list {
listNode *head; // Head node
listNode *tail; // End node
void *(*dup)(void *ptr); // Copy the function
void (*free)(void *ptr); // Release function
int (*match)(void *ptr, void *key); // Match the function to find the node to use
unsigned long len; // The length of the bidirectional list is the number of nodes
} list;