02 linked list of redis data structure

Linked list

Introduction of the list

Specific introduction and reference of linked list ： Several forms of linked lists, Joseph rings and LRU Design of cache elimination algorithm （java、C、Go Language implementation ）, stay Java In language , We have LinkedList It is based on linked list , But in C There is no such built-in data structure in the language , therefore redis Built a Double linked list , Mainly used in List The underlying implementation of this data structure , In publishing and subscribing 、 The slow query 、 Monitor and other functions are also useful .

Here is redis Definition of bidirectional linked list in

// adlist.h

#ifndef __ADLIST_H__
#define __ADLIST_H__

/* *  Double ended list node  */
typedef struct listNode {
    
	//  Precursor node 
	struct listNode* prev;
	//  The subsequent nodes 
	struct listNode* next;
	//  The value of the node 
	void* value;
} listNode;

/* *  Double ended linked list iterator  */
typedef struct listIter {
    
	//  Current iteration node 
	listNode* next;
	//  Iteration direction 
	int direction;
} listIter;

typedef struct list {
    
	listNode* head;
	listNode* tail;
	unsigned long len;
} list;

 //  Iterate from header to tail 
#define AL_START_HEAD 0
//  Iterate from the end of the table to the head 
#define AL_START_TAIL 1

#endif

Core code

Create a linked list

// adlist.c

/* *  Create a new list  * *  Successful creation returns the linked list , Failure to return  NULL . * * T = O(1) */
list* listCreate() {
    
	struct list* list;
	list = malloc(sizeof(struct list));
	if (list == NULL) return NULL;

	list->head = list->tail = NULL;
	list->len = 0;
	list->dup = NULL;
	list->free = NULL;
	list->match = NULL;
	return list;
}

Insert nodes in the list

// adlist.c

/* *  Insert a node into the chain header  * * T = O(1) */
list* listAddNodeHead(list* list, void* value) {
    
    listNode* node;
    node = malloc(sizeof(struct listNode));
    if (node == NULL) return NULL;

    node->value = value;
    if (list->len == 0) {
    
        list->head = node;
        list->tail = node;
        node->prev = NULL;
        node->next = NULL;
    } else {
    
        node->prev = NULL;
        node->next = list->head;
        list->head->prev = node;
        list->head = node;
    }
    list->len++;
    return list;
}

/* *  Insert a node at the end of the linked list  * * T = O(1) */
list* listAddNodeTail(list* list, void* value) {
    
    listNode* node;
    node = malloc(sizeof(struct listNode));
    if (node == NULL) return NULL;

    node->value = value;
    if (list->len == 0) {
    
        list->head = node;
        list->tail = node;
        node->prev = NULL;
        node->next = NULL;
    } else {
    
        node->prev = list->tail;
        node->next = NULL;
        list->tail->next = node;
        list->tail = node;
    }
    list->len++;
    return list;
}

/* *  Insert into  old_node  Before or after  * *  If  after  by  0 , Insert the new node into  old_node  Before . *  If  after  by  1 , Insert the new node into  old_node  after . * * T = O(1) */
list* listInsertNode(list *list, listNode *old_node, void *value, int after) {
    
    listNode* node;
    node = malloc(sizeof(struct listNode));
    if (node == NULL) return NULL;

    node->value = value;
    if (after) {
    
        node->prev = old_node;
        node->next = old_node->next;
        old_node->next = 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;
        }
    }

    //  take old_node Of prev Point to node
    if (node->prev != NULL) {
    
        node->prev->next = node;
    }

    //  take old_node Of next Point to node
    if (node->next !=NULL) {
    
        node->next->prev = node;
    }

    list->len++;
    return list;    
}

Delete node from linked list

/* *  From the list  list  Delete the given node in  node * *  Private value to node (private value of the node) The release of is performed by the caller . * * T = O(1) */
void listDelNode(list *list, listNode *node) {
    

    if (node->prev != NULL) {
    
        node->prev->next = node->next;
    } else {
    
        list->head = node->next;
    }
    
    if (node->next != NULL) {
    
        node->next->prev = node->prev;
    } else {
    
        list->tail = node->prev;
    }

    free(node);
    list->len--;
}

Iteration of linked list

/* *  Create an iterator for a given linked list  * * T = O(1) */
listIter *listGetIterator(list *list, int direction) {
    
    listIter* iter;
    iter = malloc(sizeof(struct listIter));
    if (iter == NULL) return NULL;

    if (direction == AL_START_HEAD) {
    
        iter->next = list->head;
    } else {
    
        iter->next = list->tail;
    }

    iter->direction = direction;
    return iter;
}

/* *  Set the direction of the iterator to  AL_START_HEAD , *  And re point the iteration pointer to the header node . * * T = O(1) */
void listRewind(list *list, listIter *li) {
    
    li->next = list->head;
    li->direction = AL_START_HEAD;
}

/* *  Set the direction of the iterator to  AL_START_TAIL , *  And re point the iteration pointer to the header node . * * T = O(1) */
void listRewindTail(list *list, listIter *li) {
    
    li->next = list->tail;
    li->direction = AL_START_TAIL;
}

/** *  Release iterators  */
void listReleaseIter(listIter *li) {
    
    free(li);
}

/** *  Returns the node to which the iterator is currently pointing . */
listNode* listNext(listIter *iter) {
    
    listNode* current = iter->next;
    if (current != NULL) {
    
        if (AL_START_HEAD == iter->direction) {
    
            iter->next = current->next;
        } else {
    
            iter->next = current->prev;
        }
    }
    return current;
}