redis源码3--链表list

源码文件在 adlist.h 和 adlist.c 中

结点的定义

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;

  // 节点值 value 复制函数
  void *(*dup)(void *ptr);

  // 节点值 value 释放函数
  void (*free)(void *ptr);

  // 节点值 value 对比函数
  int (*match)(void *ptr, void *key);

  // 链表所包含的节点数量
  unsigned long len;

} list;

宏定义

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

宏函数

// 返回给定链表所包含的节点数量
#define listLength(l) ((l)->len)
// 返回给定链表的表头节点
#define listFirst(l) ((l)->head)
// 返回给定链表的表尾节点
#define listLast(l) ((l)->tail)
// 返回给定节点的前置节点
#define listPrevNode(n) ((n)->prev)
// 返回给定节点的后置节点
#define listNextNode(n) ((n)->next)
// 返回给定节点的值
#define listNodeValue(n) ((n)->value)

// 将链表 l 的值复制函数设置为 m
#define listSetDupMethod(l,m) ((l)->dup = (m))
// 将链表 l 的值释放函数设置为 m
#define listSetFreeMethod(l,m) ((l)->free = (m))
// 将链表的对比函数设置为 m
#define listSetMatchMethod(l,m) ((l)->match = (m))

// 返回给定链表的值复制函数
#define listGetDupMethod(l) ((l)->dup)
// 返回给定链表的值释放函数
#define listGetFree(l) ((l)->free)
// 返回给定链表的值对比函数
#define listGetMatchMethod(l) ((l)->match)

主要函数

//创建一个新的链表
list *listCreate(void)
//释放整个链表，以及链表中所有节点
void listRelease(list *list)
//将一个包含有给定值指针 value 的新节点添加到链表的表头
list *listAddNodeHead(list *list, void *value)
//将一个包含有给定值指针 value 的新节点添加到链表的表尾
list *listAddNodeTail(list *list, void *value)
//创建一个包含值 value 的新节点，并将它插入到 old_node 的之前或之后，
//如果 after 为 0 ，将新节点插入到 old_node 之前。
//如果 after 为 1 ，将新节点插入到 old_node 之后。
list *listInsertNode(list *list, listNode *old_node, void *value, int after)
//从链表 list 中删除给定节点 node
void listDelNode(list *list, listNode *node)
//为给定链表创建一个迭代器
listIter *listGetIterator(list *list, int direction)
//释放迭代器
void listReleaseIterator(listIter *iter) 
//将迭代器的方向设置为 AL_START_HEAD ，并将迭代指针重新指向表头节点。
void listRewind(list *list, listIter *li)
//将迭代器的方向设置为 AL_START_TAIL ，并将迭代指针重新指向表尾节点。
void listRewindTail(list *list, listIter *li)
//返回迭代器当前所指向的节点。
listNode *listNext(listIter *iter)
//复制整个链表。
list *listDup(list *orig)
//查找链表 list 中值和 key 匹配的节点。
listNode *listSearchKey(list *list, void *key)
//返回链表在给定索引上的值。
listNode *listIndex(list *list, long index) 
//取出链表的表尾节点，并将它移动到表头，成为新的表头节点。
void listRotate(list *list)

listCreate

创建一个新的链表

list *listCreate(void)
{
  struct list *list;

  // 分配内存，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;
}

listRelease

释放整个链表，以及链表中所有节点

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

listAddNodeHead

将一个包含有给定值指针 value 的新节点添加到链表的表头，如果为新节点分配内存出错，那么不执行任何动作，仅返回 NULL，如果执行成功，返回传入的链表指针

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

listAddNodeTail

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

listInsertNode

创建一个包含值 value 的新节点，并将它插入到 old_node 的之前或之后，如果 after 为 0 ，将新节点插入到 old_node 之前。如果 after 为 1 ，将新节点插入到 old_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) {
    node->prev = old_node;
    node->next = old_node->next;
    // 给定节点是原表尾节点
    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;
}

listDelNode

从链表 list 中删除给定节点 node

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

listGetIterator

为给定链表创建一个迭代器，之后每次对这个迭代器调用 listNext 都返回被迭代到的链表节点
direction 参数决定了迭代器的迭代方向：

  • AL_START_HEAD ：从表头向表尾迭代
  • AL_START_TAIL ：从表尾想表头迭代
 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;
}

listReleaseIterator

释放迭代器

void listReleaseIterator(listIter *iter) {
  zfree(iter);
}

listRewind

将迭代器的方向设置为 AL_START_HEAD ，并将迭代指针重新指向表头节点。

void listRewind(list *list, listIter *li) {
  li->next = list->head;
  li->direction = AL_START_HEAD;
}

listRewindTail

将迭代器的方向设置为 AL_START_TAIL ，并将迭代指针重新指向表尾节点。

void listRewindTail(list *list, listIter *li) {
  li->next = list->tail;
  li->direction = AL_START_TAIL;
}

listNext

返回迭代器当前所指向的节点

listNode *listNext(listIter *iter)
{
  //iter->next 为迭代器当前指向的结点
  listNode *current = iter->next;

  if (current != NULL) {
    // 根据方向选择下一个节点
    if (iter->direction == AL_START_HEAD)
        // 保存下一个节点，防止当前节点被删除而造成指针丢失
        iter->next = current->next;
    else
        // 保存下一个节点，防止当前节点被删除而造成指针丢失
        iter->next = current->prev;
}

  return current;
}

listDup

复制整个链表。
复制成功返回输入链表的副本，如果因为内存不足而造成复制失败，返回 NULL 。
如果链表有设置值复制函数 dup ，那么对值的复制将使用复制函数进行，否则，新节点将和旧节点共享同一个指针（因为value是 void* 类型）。
无论复制是成功还是失败，输入节点都不会修改

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是 void* 类型）
        value = node->value;

    // 将节点添加到链表
    if (listAddNodeTail(copy, value) == NULL) {
        listRelease(copy);
        listReleaseIterator(iter);
        return NULL;
    }
  }

  // 释放迭代器
  listReleaseIterator(iter);

  // 返回副本
  return copy;
}

listSearchKey

查找链表 list 中值和 key 匹配的节点。
对比操作由链表的 match 函数负责进行，如果没有设置 match 函数，那么直接通过对比值的指针来决定是否匹配。
如果匹配成功，那么第一个匹配的节点会被返回。如果没有匹配任何节点，那么返回 NULL 。

listNode *listSearchKey(list *list, void *key)
{
  listIter *iter;
  listNode *node;

  // 迭代整个链表
  iter = listGetIterator(list, AL_START_HEAD);
  while((node = listNext(iter)) != NULL) {
    
    // 对比
    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;
}

listIndex

返回链表在给定索引上的结点。索引以 0 为起始，也可以是负数， -1 表示链表最后一个节点，诸如此类。如果索引超出范围（out of range），返回 NULL 。

listNode *listIndex(list *list, long index) {
  listNode *n;

  // 如果索引为负数，从表尾开始查找
  if (index < 0) {
    index = (-index)-1;
    n = list->tail;
    while(index-- && n) n = n->prev;
  // 如果索引为正数，从表头开始查找
  } else {
    n = list->head;
    while(index-- && n) n = n->next;
  }

  return n;
}

listRotate

取出链表的表尾节点，并将它移动到表头，成为新的表头节点。

void listRotate(list *list) {
  listNode *tail = list->tail;
  
  //如果只有一个结点或没有结点，直接返回
  if (listLength(list) <= 1) return;

  /* Detach current tail */
  // 取出表尾节点
  list->tail = tail->prev;
  list->tail->next = NULL;

  /* Move it as head */
  // 插入到表头
  list->head->prev = tail;
  tail->prev = NULL;
  tail->next = list->head;
  list->head = tail;
}
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 216,324评论 6赞 498
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 92,356评论 3赞 392
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 162,328评论 0赞 353
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 58,147评论 1赞 292
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 67,160评论 6赞 388
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 51,115评论 1赞 296
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 40,025评论 3赞 417
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,867评论 0赞 274
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 45,307评论 1赞 310
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,528评论 2赞 332
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,688评论 1赞 348
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,409评论 5赞 343
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 41,001评论 3赞 325
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,657评论 0赞 22
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,811评论 1赞 268
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,685评论 2赞 368
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,573评论 2赞 353