redis0.1源码解析之链表---theanarkh

分析代码之前先看看链表的数据结构。

1 新建一个链表// 新建一个链表头结点 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; // 释放节点value域的函数 list->free = NULL; // 匹配节点的函数 list->match = NULL; return list; }2 释放一个链表// 释放一个链表 void listRelease(list *list) { unsigned int len; listNode *current, *next; // 第一个节点 current = list->head; // 链表中的节点数 len = list->len; while(len--) { next = current->next; // 定义了free函数，则执行 if (list->free) list->free(current->value); // 释放节点内存 zfree(current); current = next; } // 释放链表内存 zfree(list); }

3 插入一个节点（支持头插和尾插）

// 给链表新增一个节点，头插法 list *listAddNodeHead(list *list, void *value) { listNode *node; // 分配一个新的listNode节点 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; }4 删除节点// 删除节点node void listDelNode(list *list, listNode *node) { // 有前指针说明不是第一个节点，则前节点的next指针指向node的第一个节点 if (node->prev) node->prev->next = node->next; else // 前指针为空说明是第一个节点，更新头节点头指针的指向，指向node的下一个节点 list->head = node->next; // next非空说明不是最后一个节点，更新node下一个节点的前指针为node的前一个节点 if (node->next) node->next->prev = node->prev; else // 删除的是最后一个节点，则更新头节点尾指针的指向 list->tail = node->prev; // 定义了free函数 if (list->free) list->free(node->value); // 释放节点的内存 zfree(node); // 节点数减一 list->len--; }5 查找

查找有两种，第一是根据索引查找，第二种是根据键查找。

// 返回链表的第index个字节 listNode *listIndex(list *list, int index) { listNode *n; // index小于0，则-1是最后一个节点 if (index < 0) { /* | --------------------- | -2 -1 0 1 2 假设index=-2，-index则为2，-index-1则为1。即向前走1个节点， 因为初始化时n指向了尾节点，所以这时候返回的是倒数第二个节点 */ index = (-index)-1; n = list->tail; while(index-- && n) n = n->prev; } else { // 索引为0对应的节点（第一个节点），如果只有2个节点，index大于节点数，则返回最后一个节点 n = list->head; while(index-- && n) n = n->next; } return n; }

通过键查找

// 遍历链表，查找key对应的节点 listNode *listSearchKey(list *list, void *key) { listIter *iter; listNode *node; iter = listGetIterator(list, AL_START_HEAD); while((node = listNext(iter)) != NULL) { // 定义了match函数 if (list->match) { if (list->match(node->value, key)) { listReleaseIterator(iter); return node; } } else { // 默认比较内存地址 if (key == node->value) { listReleaseIterator(iter); return node; } } } listReleaseIterator(iter); return NULL; }6 复制一个链表// 复制一个链表 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); while((node = listNext(iter)) != NULL) { void *value; // 定义了复制函数，比如深度复制 if (copy->dup) { value = copy->dup(node->value); // 复制出错，释放刚才申请的内存 if (value == NULL) { listRelease(copy); listReleaseIterator(iter); return NULL; } } else // 默认浅复制 value = node->value; // 插入新的链表 if (listAddNodeTail(copy, value) == NULL) { listRelease(copy); listReleaseIterator(iter); return NULL; } } // 用完了，释放迭代器 listReleaseIterator(iter); return copy; }

7 迭代链表 首先申请一个迭代器。

// 申请一个链表迭代器 listIter *listGetIterator(list *list, int direction) { 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; return 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; } ---来自腾讯云社区的---theanarkh