redis 5.0.7 源码阅读——双向链表
redis中动态字符串sds相关的文件为:adlist.h与adlist.c
一、数据结构
redis里定义的双向链表,与普通双向链表大致相同
单个节点:
typedef struct listNode { struct listNode *prev; struct listNode *next; void *value; } listNode;
链表:
typedef struct list { listNode *head; listNode *tail; void *(*dup)(void *ptr); void (*free)(void *ptr); int (*match)(void *ptr, void *key); unsigned long len; } list;
链表以函数指针的方式,实现了复制、销毁与比较的方法的多态。
迭代器:
typedef struct listIter { listNode *next; int direction; } listIter;
迭代器中有个成员变量direction,用于表示当前遍历的方向。
大致结构:
/* +-------------------+ +----------------> +--------------+ <-------+ |listNode *head |--------+ |listNode *prev|-->NULL | +-------------------+ +--------------+ | |listNode *tail |--------+ |listNode *next|----+ | +-------------------+ | +--------------+ | | |void *(*dup)(...) | | |void *value | | | +-------------------+ | +--------------+ | | |void (*free)(...) | | | | +-------------------+ | | | |int (*match)(...) | | | | +-------------------+ +----------------> +--------------+ <--+ | |unsigned long len | |listNode *prev|---------+ +-------------------+ +--------------+ |listNode *next|-->NULL +--------------+ |void *value | +--------------+ */
二、创建
redis中创建一个初始双向链表比较简单,只要分配好内存,并给成员变量赋初值就可以了
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; }
redis中提供了头插法、尾插法以及指定位置插入节点三种方式向链表中添加节点,与普通双向链表无异,此处不做详细叙述。
三、销毁
因链表中每个节点的value可能指向堆空间,故不能直接把list结构体free,这样会造成内存泄露。需要先将每个节点的value释放,才可以free结构体
清空所有节点:
void listEmpty(list *list) { unsigned long len; listNode *current, *next; current = list->head; len = list->len; while(len--) { next = current->next; //若指定了销毁的函数,则使用指定的函数进行销毁value if (list->free) list->free(current->value); zfree(current); current = next; } list->head = list->tail = NULL; list->len = 0; }
销毁链表:
void listRelease(list *list) { listEmpty(list); zfree(list); }
同样,redis的链表提供了与普通链表相同的删除单个节点的操作,此处也不做叙述。
四、迭代器操作
redis中提供了获取迭代器的接口
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; }
以AL_START_HEAD为例,生成好的迭代器结构如下:
/* +-------------------+ +---> +--------------+ <-------+----+ |listNode *head |----+ |listNode *prev|-->NULL | | +-------------------+ +--------------+ | | +--------------+ |listNode *tail |----+ |listNode *next|----+ | +--|listNode *next| +-------------------+ | +--------------+ | | +--------------+ |void *(*dup)(...) | | |void *value | | | |int direction | +-------------------+ | +--------------+ | | +--------------+ |void (*free)(...) | | | | +-------------------+ | | | |int (*match)(...) | | | | +-------------------+ +---> +--------------+ <--+ | |unsigned long len | |listNode *prev|---------+ +-------------------+ +--------------+ |listNode *next|-->NULL +--------------+ |void *value | +--------------+ */
迭代器的next方法:
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; }
调用一次之后的结构:
/* +-------------------+ +---> +--------------+ <-------+ |listNode *head |----+ |listNode *prev|-->NULL | +-------------------+ +--------------+ | +--------------+ |listNode *tail |----+ |listNode *next|----+ | +--|listNode *next| +-------------------+ | +--------------+ | | | +--------------+ |void *(*dup)(...) | | |void *value | | | | |int direction | +-------------------+ | +--------------+ | | | +--------------+ |void (*free)(...) | | | | | +-------------------+ | | | | |int (*match)(...) | | | | | +-------------------+ +---> +--------------+ <--+----|----+ |unsigned long len | |listNode *prev|---------+ +-------------------+ +--------------+ |listNode *next|-->NULL +--------------+ |void *value | +--------------+ */
再次调用:
/* +-------------------+ +---> +--------------+ <-------+ |listNode *head |----+ |listNode *prev|-->NULL | +-------------------+ +--------------+ | +--------------+ |listNode *tail |----+ |listNode *next|----+ | +--|listNode *next| +-------------------+ | +--------------+ | | | +--------------+ |void *(*dup)(...) | | |void *value | | | | |int direction | +-------------------+ | +--------------+ | | | +--------------+ |void (*free)(...) | | | | | +-------------------+ | | | | |int (*match)(...) | | | | | +-------------------+ +---> +--------------+ <--+ | +-->NULL |unsigned long len | |listNode *prev|---------+ +-------------------+ +--------------+ |listNode *next|-->NULL +--------------+ |void *value | +--------------+ */
调用next函数的返回值为调用之前的listNode首地址
五、其它操作
redis的双向链表还提供了其它操作。其中,查找指定的key与复制整个list依赖于迭代器的使用,并使用到自定义的比较/复制方法。
除此之外,还提供了类似随机读取的方式,其内部实现为遍历,且“越界”时返回NULL。同时,它支持index为负数,表示从尾开始。类似旋转的操作,把尾节点移至原头节点之前,成为新的头节点。当然,还有拼接两个链表的操作。
redis 5.0.7 下载链接
http://download.redis.io/releases/redis-5.0.7.tar.gz
源码阅读顺序参考:
https://github.com/huangz1990/blog/blob/master/diary/2014/how-to-read-redis-source-code.rst