A list,

  • As a common data structure, Redis doesn’t have it built into THE C language, so Redis built its own linked list implementation.
  • Linked lists are widely used in Redis. For example, one of the underlying implementations of list keys is linked lists. Redis uses linked lists as the underlying implementation of list keys when a list key contains a large number of elements, or when the list contains long strings of elements.

Second, the implementation

  • Single linked list node:
typedef struct listNode { struct listNode *prev; Struct listNode *next; Void *value; } listNode;Copy the code

You can see that the nodes of the linked list have Pointers before and after, so the list implemented by Redis is a bidirectional list.

  • Redis implements a list structure to hold linked list nodes.
typedef struct list { listNode *head; // listNode *tail; Unsigned long len; Void *(*dup)(void * PTR); Void (*free)(void * PTR); Int (*match)(void * PTR, void *key); } list;Copy the code

The overall structure of list and listNode is as follows:

Three, the source code

1. Create linked lists

To create a linked list, zmalloc is used to request a list structure space, and each field is set to NULL.

list *listCreate(void)
{
    struct list *list;
 
    if ((list = zmalloc(sizeof(*list))) == NULL)
        return NULL;
    list->head = list->tail = NULL;
    list->len = 0;
    list->dup = NULL;
    list->free = NULL;
    list->match = NULL;
    return list;
}
Copy the code

2. Release linked lists

To release the list, we first get the length and the header pointer to the list, and then call the free function to traverse each node in turn.

void listRelease(list *list)
{
    unsigned long len;
    listNode *current, *next;
 
    current = list->head;
    len = list->len;
    while(len--) {
        next = current->next;
        if (list->free) list->free(current->value);
        zfree(current);
        current = next;
    }
    zfree(list);
}
Copy the code

3. Add a node

  • New head and tail:

Zmalloc function is used to allocate memory space of listNode node, and then determine whether the linked list is empty before the new node. If it is empty, set the pointer before and after the new node to NULL, and let the pointer at the beginning and end of the list point to the new node.

list *listAddNodeHead(list *list, void *value) { listNode *node; if ((node = zmalloc(sizeof(*node))) == NULL) return NULL; node->value = value; if (list->len == 0) { list->head = list->tail = node; node->prev = node->next = NULL; } else { node->prev = NULL; Node ->next = list->head; List ->head->prev = node; List ->head = node; } list->len++; return list; } list *listAddNodeTail(list *list, void *value) { listNode *node; if ((node = zmalloc(sizeof(*node))) == NULL) return NULL; node->value = value; if (list->len == 0) { list->head = list->tail = node; node->prev = node->next = NULL; } else { node->prev = list->tail; node->next = NULL; list->tail->next = node; list->tail = node; } list->len++; return list; }Copy the code
  • Added in the middle:

You need to determine whether the current node is a head or tail node.

list *listInsertNode(list *list, listNode *old_node, void *value, int after) { listNode *node; if ((node = zmalloc(sizeof(*node))) == NULL) return NULL; node->value = value; If (after) {// Insert node after old_node ->prev = old_node; // set the front pointer to old_node node->next = old_node->next; If (list->tail == old_node) {if (list->tail == old_node) {list->tail = node; } } else { node->next = old_node; node->prev = old_node->prev; if (list->head == old_node) { list->head = node; } } if (node->prev ! = NULL) { node->prev->next = node; } if (node->next ! = NULL) { node->next->prev = node; } list->len++; return list; }Copy the code

4. Delete the node

When deleting a node, consider whether the node is the first or last node of the linked list. If yes, update the linked list; otherwise, update the node pointing relationship before and after the node to be deleted.

void listDelNode(list *list, listNode *node)
{
    if (node->prev)
        node->prev->next = node->next;
    else
        list->head = node->next;
    if (node->next)
        node->next->prev = node->prev;
    else
        list->tail = node->prev;
    if (list->free) list->free(node->value);
    zfree(node);
    list->len--;
}
Copy the code

5. The iterator

  • Iterator data structure:
typedef struct listIter { listNode *next; // The current node to which the iterator points is int direction; // The direction of iteration can take two values: AL_START_HEAD and AL_START_TAIL} listIterCopy the code
  • Create an iterator:
ListIter *listGetIterator(list *list, int direction) iterator {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; // Set the iteration direction return iter; }Copy the code
  • Reset iterator orientation:
Void listRewind(list *list, listIter *li) {li->next = list->head; li->next = list->head; // set the starting position of the iterator pointer li->direction = AL_START_HEAD; } void listRewindTail(list *list, listIter *li) {li->next = list->tail; li->next = list->tail; // set the starting position of the iterator pointer li->direction = AL_START_TAIL; // Set the direction of iteration from end to end}Copy the code
  • Iterator traversal:

Returns the current node pointed to by iterator iter and updates iter

listNode *listNext(listIter *iter) { listNode *current = iter->next; If (current! = NULL) { if (iter->direction == AL_START_HEAD) iter->next = current->next; else iter->next = current->prev; } return current; // return the current node address of backup}Copy the code
  • List replication:

List replication is the process of copying data from the original list to the new list through a start-to-end iterator. If we set the data copy method with listSetDupMethod, we use that method to copy the data, and then put the new copied data into a new linked list. If not set, simply assign the value field of the element in the old list.

list *listDup(list *orig) { list *copy; listIter *iter; listNode *node; If ((copy = listCreate()) == NULL) return NULL; Copy ->dup = orig->dup; copy->free = orig->free; copy->match = orig->match; Iter = listGetIterator(orig, AL_START_HEAD); // Define an iterator for orig and set the direction of the iteration while((node = listNext(iter))! Void *value; If (copy->dup) {value = copy->dup(node->value); // Use this method to copy node values if a dUP pointer is defined in the list structure. if (value == NULL) { listRelease(copy); listReleaseIterator(iter); return NULL; } } else value = node->value; If (listAddNodeTail(copy, value) == NULL) {// Insert the end of the node into the copy header listRelease(copy); listReleaseIterator(iter); return NULL; } } listReleaseIterator(iter); // return copy; // return a copy copy}Copy the code

6. Find elements

Finding elements is also done by iterating through the list, and then depending on whether the user sets the comparison method through listSetMatchMethod, the user can use the user-defined method to compare the elements, or use value directly to compare the elements. If value is used to compare data directly, it is a strong comparison, that is, the data to be compared and the linked list data in the same location in memory.

listNode *listSearchKey(list *list, void *key) { listIter *iter; listNode *node; iter = listGetIterator(list, AL_START_HEAD); While ((node = listNext(iter))! If (list->match) {// If (list->match) { If (list->match(node->value, key)) {listReleaseIterator(iter); // If found, release the iterator to return node address return node; } } else { if (key == node->value) { listReleaseIterator(iter); return node; } } } listReleaseIterator(iter); // Release iterator return NULL; }Copy the code

7. Access linked lists by subscript

The subscript can be negative, representing the element from the last digit.

listNode *listIndex(list *list, long index) { listNode *n; If (index < 0) {// Return index = (-index)-1; N = list->tail; while(index-- && n) n = n->prev; //index = 0, h} else {n = list->head; while(index-- && n) n = n->next; } return n; }Copy the code

4. Summary of 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 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.

5. Reference materials

  • Redis Design and Implementation

Read more

  • Void pointer in C: www.zhihu.com/question/40…