02-Redis数据结构之链表

链表的具体介绍参考：链表的几种形式以及约瑟夫环和LRU缓存淘汰算法的设计（java、C、Go语言实现），在Java语言中，我们有LinkedList是基于链表实现的，但是在C语言中没有这样的内置数据结构，所以redis构建了一个双向链表，主要用在List这种数据结构的底层实现，在发布与订阅、慢查询、监视器等功能也有用到。

下面是redis中对双向链表的定义

// adlist.h

#ifndef __ADLIST_H__
#define __ADLIST_H__


typedef struct listNode {
	// 前驱节点
	struct listNode* prev;
	// 后继节点
	struct listNode* next;
	// 节点的值
	void* value;
} listNode;


typedef struct listIter {
	// 当前迭代节点
	listNode* next;
	// 迭代方向
	int direction;
} listIter;

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

 // 从表头向表尾进行迭代
#define AL_START_HEAD 0
// 从表尾到表头进行迭代
#define AL_START_TAIL 1

#endif

// adlist.c


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;
}

// adlist.c


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;
}


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;
}


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;
        }
    }

    // 将old_node的prev指向node
    if (node->prev != NULL) {
        node->prev->next = node;
    }

    // 将old_node的next指向node
    if (node->next !=NULL) {
        node->next->prev = node;
    }

    list->len++;
    return list;    
}

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--;
}

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;
}


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 listReleaseIter(listIter *li) {
    free(li);
}


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;
}