Shulou(Shulou.com)06/01 Report--

Today, the editor shares with you the data structure and operation of the double-ended linked list in Redis, which is not well understood by many people. Today, in order to let you know more about the double-ended linked list in Redis, I summed up the following contents and looked down together. I'm sure you'll get something.

As a double-ended linked list in Redis, adlist has been widely used in many places in Redis, such as the storage of slowlog, the error reporting client in master-slave replication, the implementation of list data structure and so on.

1). The data structure of double-ended linked list in Redis

Double-ended linked list (the following code is defined in src/adlist.h):

Typedef struct list {listNode * head; / / points to the first node of the linked list, listNode * tail; / / points to the last node of the linked list / / copies the callback function of the linked list node. Because the linked list node can have any type of data, different types of operations are different, so the callback function is used to specially handle void * (* dup) (void * ptr); void (* free) (void * ptr) / / the callback function when releasing the memory of the linked list node, for the same reason as the above int (* match) (void * ptr, void * key); / / comparing the callback function of the linked list node value for custom comparison, for the same reason as the above unsigned long len; / / number of nodes in the current list} list

The node of the double-ended linked list (the following code is defined in src/adlist.h):

Typedef struct listNode {struct listNode * prev; / / the previous node of the current node struct listNode * next; / / the next node of the current node void * value; / / the value stored by the current node, which can be of any type} listNode

List points to both ends of the linked list through head and tail, respectively, so that the traversal of the linked list can be traversed in both positive and negative order, while the void * value of listNode can save arbitrary data, and you can define how to handle the value of listNode through dup,free,match.

2. Simple operation of double-ended linked list

Create a linked list (the following code is defined in src/adlist.c):

List * listCreate (void) {struct list * list; / / initialize the linked list / / allocate memory if for the linked list ((list = zmalloc (sizeof (* list) = = NULL) return NULL; / / set the initial value for the empty linked list list- > head = list- > tail = NULL; list- > len = 0; list- > dup = NULL; list- > free = NULL; list- > match = NULL; return list;}

Append to the end of the linked list (the following code is defined in src/adlist.c):

List * listAddNodeTail (list * list, void * value) {listNode * node; / / initialize the node node / / allocate memory if for the new node node ((node = zmalloc (sizeof (* node)) = = NULL) return NULL; / / set the value node- > value = value for the node node If (list- > len = = 0) {/ / if the list is empty, point the head and tail to the new node and set the successor precursor node to NULL list- > head = list- > tail = node; node- > prev = node- > next = NULL;} else {/ / otherwise, the precursor node of the node will be set to the original tail node node- > prev = list- > tail / / because the successor node is appended to the tail, the successor node of the tail node before it is NULL node- > next = NULL; / / the successor node of the tail node is set to the new node list- > tail- > next = node; / / the pointer of the tail node of the list is pointed to the new node list- > tail = node;} / / increase the list length list- > len++; return list;}

Traverse the linked list:

There are two common ways to traverse the linked list, one is to traverse manually through the while loop according to the length of the linked list, and the other is to traverse with the iterator provided by the Redis double-ended linked list.

Traverse manually (the following code defines the memory release function in src/adlist.c):

Void listRelease (list * list) {unsigned long len; / / current represents the cursor pointer for the current traversal, next indicates the cursor pointer for the next traversal (next is used as a temporary variable to hold the next node) listNode * current, and * next; / / points the current to the header node current = list- > head; / / calculate the length (actually listLength (list)) len = list- > len / / traversing by decreasing length, so that when the length is 0, traversing ends while (len--) {/ / saves the node pointer of the next loop next = current- > next; / / releases the current node. If you set the callback function to release the node, execute the user-defined function if (list- > free) list- > free (current- > value). Zfree (current); / / point the cursor to the next node current = next;} zfree (list);}

Iterator mode traversal is shown below.

3) iterator of double-ended linked list

Redis encapsulates the linked list with an iterator to facilitate the iteration of the linked list. The structure of the iterator is as follows (the following code is defined in src/adlist.h):

The typedef struct listIter {listNode * next; / / iterator points to the next node / / iterative direction. Since the double-ended linked list holds the values of head and tail, you can iterate in both directions / / AL_START_HEAD means to traverse from beginning to back, and AL_START_TAIL means to traverse int direction;} listIter forward from the tail

Examples of iterator usage:

/ l represents list structure, n represents listNode structure, the value of listNode holds the sds string / / create iterator object iter = listGetIterator (l, AL_START_HEAD); / / cycle to get the next node while ((n = listNext (iter) {/ / output the value printf ("NodeValue:% s\ n", listNodeValue (n)) of the returned node n;}

The above is a brief introduction to the data structure and operation of the double-ended linked list in Redis. Of course, the differences in the detailed use of the above have to be understood by everyone. If you want to know more, welcome to follow the industry information channel!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.