redis学习笔记（一）

redis 学习笔记（一）

1.adlist.h

准备花点时间将redis的源代码从头到尾学习一边，一边锻炼自己读代码的能力，一边学习大牛们是如何写出来漂亮的代码，而且能从底层代码实现中将自己一直以来欠缺的那一部分知识体系补全，所以准备从redis入手，再学习apache thrift，我想等都学习完一遍之后，能够将自己工作一年半以来零碎的一些知识技能变得更加系统化一点

redis源码中分为结构体，数据操作，工具，事件，基本信息，兼容，主程序，网络，封装类等，我准备从最基础的结构体入手，大致的看了一下，redis的结构体基本上基于list和hash，一个一个顺着学吧，今天就是adlist了

结构体：

typedef struct listNode{

struct listNode *PRev;//指向前一个节点

struct listNode *next;//指向后一个节点

void *value;//node值的指针

} listNode；

第一个结构体应该定义的是链表的节点，从结构体的内容可以猜测adlist是一个双向列表，prev是指向前一个节点的指针，next是指向后一个节点的指针，而value暂时不知道是干什么的

typedef struct listIter{

listNode *next;//指向当前迭代位置的下一个节点，随迭代器方向而变化

int direction;//迭代器的方向

}listIter;

从名字来看，第二个结构体应该是一个迭代器，那么next便是指向下一个节点，direction从字面意思应该是迭代器的方向，由于list是一个双向链表，那么可以猜测listIter可以实现正向迭代器和反向迭代器，相比于C++的iterator基类，这应该是用C实现的一个简易的迭代器了

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;

结构体list应该就是一个双向列表，head是头节点，tail是尾节点，然后dup，free和match应该就是C风格的list的成员函数,len是链表的长度

从adlist.h文件里面定义了如下函数,从字面分析其实现：

list *listCreate(void);//创建list

void listRelease(list *list);//列表释放

list *listAddNodeHead(list *list, void *value);//从头部增加节点

list *listAddNodeTail(list *list, void *value);//从尾部增加节点

list *listInsertNode(list *list, listNode *old_node, void *value,int after);//随机插入节点

void listDelNode(list *list, listNode *node);//删除节点

listIter *listGetIterator(list *list, int direction);//获取迭代器，返回一个listIter结构体指针

listNode *listNext(listIter *iter); //获取下个节点

void listReleaseIterator(listIter *iter);//释放迭代器指针

list *listDup(list *orig); //列表复制

listNode *listSearchKey(list *list, void *key);//在list中查找key，并返回节点

listNode *listIndex(list *list, long index);//根据索引查找节点

void listRewind(list *list, listIter *li);//重置迭代器

void listRewindTail(list *list, listIter *li);//从尾部重置迭代器

void listRotate(list *list);//将链表的尾节点置于队首

此外，在adlist.h中定义了一系列的宏定义，不再一一列述，不过学习了程序员大牛们的编码习惯，适当的定义宏使得代码变得更易读

再看adlist.c中对于函数的具体实现（感觉看完之后，把大学学链表的时候的C实现捡回来了…）:

//返回一个list结构体指针

list *listCreate(void){

//声明一个list结构体

struct list *list;

//为list结构体分配内存，zmalloc是redis文件下面zmalloc.h里面定义的方法，跳过去看了一下，看不懂，里面很多宏定义，想想以前看别人代码就是懒得看些，所以赖着性子看看

/*

void *zmalloc(size_t size){

//上文中宏PREFIX_SIZE为0，为ptr分配了一个size大小的内存空间，size_t的实现代码为typedef unsigned int size_t;

void *ptr = malloc(size + PREFIX_SIZE);

if(!ptr) zmalloc_oom_handler(size);//如果ptr为NULL，返回错误，abort

#ifdef HAVE_MALLOC_SIZE//上文定义

//返回所申请的内存空间

update_zmalloc_stat_alloc(zmalloc_size(ptr));

return ptr;

}

*/

if((list = zmalloc(sizeof(*list))) == NULL) return NULL;

//将头节点和尾节点都置为NULL

list->head = list->tail = NULL;

//将链表长度置为0

list->len = 0;

//将struct的成员函数指针置为NULL

list->dup = NULL;

list->free = NULL;

list->match  = NULL;

//返回一个空的list指针

return list;

}

void listRelease(list *list){

unsigned long len;

listNode *current, *next;//两个节点指针，一个指向当前节点，一个指向下一个节点

current = list->head;//将起点置在队首

len = list->len;

//遍历链表

while(len—){

//next为current所指向的下一个节点

next = current->next;

//判断链表是否有free方法，调用free方法,释放listNode的value函数指针，这里并不是很清楚value是干什么的，我理解可能在其他文件里面有实现

if(list->free) list->free(current->value);

//调用zmalloc.h中的zfree方法释放掉current指针

zfree(current);

//指针后移

current = next;

}

//释放链表指针

zfree(list);

}//个人认为这里可以每次释放一个node，便使list->len—，且重置head指针,这样如果循环释放到一半程序崩溃的话，还能保证链表的完整性

 继续往下看

void *listAddNodeHead(list *list, void* value){

listNode *node;

//分配内存检查

if((node = zmalloc(sizeof(*node))) == NULL)return NULL;

//这里理解了value的含义，在node中设置为void*是为了适配不同指针类型，然后value就是node的值的指针类型

node->value = value;

//如果链表为空，那么插入的节点就是链表的唯一一个节点，由于是双向链表，所以需要注意前后指针的重置

if(list->len == 0){

list->head = list->tail = node;

node->prev = node->next = NULL;

} else{//如果不是空，那么就在链表最前面插入，然后置新节点为head

node->prev = NULL;

node->next = list->head;

list->head->prev = node;

list->head = node;

}

//链表长度加1

list->len ++;

return list;

}

//功能与上面类似，只不过实现的是在链表尾部添加

void *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;

}

// old_node应该指的是目标节点，after应该是指是否在后面插入

void *listInsertNode(list *list, listNode *old_node, void *value, int after){

listNode *node;

//如果新节点分配内存失败，返回null

if((node = zmalloc(sizeof(*node))) == NULL)return NULL;

//为新节点的value赋值

node->value = value;

//如果是在目标节点身后插入，那么要注意移动目标节点的next指针

if(after){

node->prev = old_node;

node->next = old_node->next;

//我觉得如果是我在写代码会遗漏这一个条件判断，如果是尾节点，那么需要重置list的尾指针位置

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;

}

lits->len++;

return list;

}

void listDelNode(list *list, listNode *node){

//判断如果目标节点有前置指针，那么使前节点指向目标节点的身后

if(node->prev){

node->prev->next = node->next;

}else{//如果目标节点是头指针，那么直接标识next为头部（我写代码绝对写不得这样简洁易懂）

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

}

//获取一个list迭代器指针

listiter *listGetIteraor(list *list, int dirction){

//申明一个迭代器指针

listIter *iter;

//判断内存分配，人家每一个临界条件都注意得特别好

if((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;

//判断方向，如果dire为0，那么从头开始遍历

if(direction == AL_START_HEAD) iter->next = list->head;

//如果是1，从尾部开始

else iter->next = list->tail;

iter->direction  = direction;

return tier;

} //迭代器区别与listNode，所以这里的iter->next可以理解为存在于list维度之外的一层

void listReleaseIterator(listIter *iter){

zfree(iter);//zfree封装了redis自己的free方法,free方法只释放用malloc或者alloc操作分配的内存

}

//对一个迭代器指针的重置操作，但是迭代器必须先初始化，这个函数置首部

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;

}

//获取迭代器指向的节点

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;

} //我理解这里其实是实现了C++ Iterator中iterator++/—的操作

//链表的复制操作

list *listDup(list *orig){

list *copy;//复制后的指针

listIter iter;//迭代器指针

listNode *node;

//判断copy是否创建成功

if((copy = listCreate()) == NULL)return NULL;

//复制相关函数指针

copy->dup = orig->dup;

copy->free = orig->free;

copy->match = orig->match;

//迭代器置首部

listRewind(orig, &iter);

//在C++里面相当于iter++!=list.end();

while((node = listNext(&iter)) != NULL){

void *value;

if(copy->dup){

value = copy->dup(node->value);

if(value == NULL){

listRelease(copy);

return NULL;

}

}else

value = node->value;

//从新链表的尾部开始插入节点

if(listAddNodeTail(copy, value) == NULL){

listRelease(copy);

return NULL;

}

}

//返回新的链表

return copy;

}

//一个双向链表的查询操作，自己也写过无数遍，感觉就是没有别人写得清楚

listNode *listSearchKey(list *list, void *key){

listIter iter;

listNode *node;

//首部迭代器

listRewind(list, &iter);

//同样的一个迭代器向后迭代的操作

while((node = listNex(&iter)) != NULL){

//调用了match方法，这里用了这么多函数指针我理解为redis可能有很多的数据类型是基于list实现的，所以根据不同的类型实现了不同的方法

if(list->match){

if(list->match(node->value, key)){

return node;

}

}else{//简单的比较

if(key == node->value){

return node;

}

}

}

return NULL;

}

//这个函数看了几遍才看懂,而且是看了英文注释，感觉英文水平飙升…根据index查找节点，正数从前往后，负数从后往前

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;

} // 想当于给一个非顺序存储的链表给了一个根据下标查找的操作

将链表尾部放在首部前面

void listRotate(list *list){

//定义尾部

listNode *tail = list->tail;

// 如果长度是1，那么尾部就是首部，无意义

if(listLength(list) <= 1)return;

//将尾部重置为之前尾部的prev

list->tail = tail->prev;

list->tail->next = NULL;

//将之前的尾部放在list->head之前作为list的首部

list->head->prev = tail;

tail->prev = NULL;

tail->next = list->head;

list->head = tail;

}

总结： 1.回顾了list链表的一些底层操作代码，顺带的一下子将例如栈，队列，以及二叉树的操作回忆了一遍；

2.无脑的用C++的库用多了之后，都完全觉得所有的组件方法等天生就有，然而现在重新改变了这一个观点，任何逻辑操作都是代码写出来的，底层的也好，业务层也好；

3.多学习别人的代码果然很有好处，虽然在这一章感觉阅读难度不大，但是对于编码习惯也好，还是思维也好，给自己有一定的冲击，先易后难，希望自己坚持