Redis代码阅读2--Redis数据结构之链表

secce

　　 Redis

是一个开源的高性能key-value数据库，其很大程度上弥补了memeched这类key-value存储的不足（除了支持String外，还支持Hash，Set，sorted set， List），在部分场合对关系型数据库也起到了很好的补充作用。因为Redis的代码量并不多，因为我逐步阅读了其源代码，以期能对其有深入的理解。首先介绍Redis支持的各种数据结构。
　　Redis中的链表是双向链表，这一点可以由 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;
void *(*dup)(void *ptr);
void (*free)(void *ptr);
int (*match)(void *ptr, void *key);
unsigned int len;
} list;

　　struct list通过head 和tail这两个指针维护了链表的头、尾节点。ListNode通过prev和next使得链表成为一个双向链表。Struct List里面的dup、free和match这三个函数指针用于配置复制、释放和匹配三个功能。比如listSetMatchMethod就是用来设置match方法的。
　　Redis里的List这一数据结构和我们常说的数据结构里面的链表很相似，同样有在头、尾节点增加Node，删除Node，查找Node及Index等功能。
　　Redis里面操作list的命令有RPUSH，LPUSH，LSET，LLEN等。Redis中负责实现这些命令的API就在t_list.c。下面就以RPUSH为例，来说明当客户端执行RPUSH命令时，Redis是如何通过list 的API去执行list的listAddNodeTail方法的。
　　在Redis.c里面，有一个Struct里面叫readonlyCommandTable。这个struct将Redis的各种命令和Redis里面各种命令对应的函数关联起来。比如：{"rpush",rpushCommand,-3,REDIS_CMD_DENYOOM,NULL,1,1,1}。
　　Redis Server接收各个Client传过来的各种命令是通过networking.c里面的代码来完成的。具体如何解析和执行各种Command以后会单独拎出来讲。这里主要简单介绍下其流程。
　　processInputBuffer-->processCommand-->lookupCommand.这里的lookupCommand就是根据Command的名字从readonlyCommandTable找出该Command对应的方法。比如，Client执行RPUSH命令，则这里的lookupCommand找到的是rpushCommand。

void rpushCommand(redisClient *c) {
pushGenericCommand(c,REDIS_TAIL);
}
void pushGenericCommand(redisClient *c, int where) {
int j, addlen = 0, pushed = 0;
robj *lobj = lookupKeyWrite(c->db,c->argv[1]);
int may_have_waiting_clients = (lobj == NULL);
if (lobj && lobj->type != REDIS_LIST) {
addReply(c,shared.wrongtypeerr);
return;
}
for (j = 2; j < c->argc; j++) {
c->argv[j] = tryObjectEncoding(c->argv[j]);
if (may_have_waiting_clients) {
if (handleClientsWaitingListPush(c,c->argv[1],c->argv[j])) {
addlen++;
continue;
} else {
may_have_waiting_clients = 0;
}
}
if (!lobj) {
lobj = createZiplistObject();
dbAdd(c->db,c->argv[1],lobj);
}
listTypePush(lobj,c->argv[j],where);
pushed++;
}
addReplyLongLong(c,addlen + (lobj ? listTypeLength(lobj) : 0));
if (pushed) signalModifiedKey(c->db,c->argv[1]);
server.dirty += pushed;
}
void listTypePush(robj *subject, robj *value, int where) {
/* Check if we need to convert the ziplist */
listTypeTryConversion(subject,value);
if (subject->encoding == REDIS_ENCODING_ZIPLIST &&
ziplistLen(subject->ptr) >= server.list_max_ziplist_entries)
listTypeConvert(subject,REDIS_ENCODING_LINKEDLIST);
if (subject->encoding == REDIS_ENCODING_ZIPLIST) {
int pos = (where == REDIS_HEAD) ? ZIPLIST_HEAD : ZIPLIST_TAIL;
value = getDecodedObject(value);
subject->ptr = ziplistPush(subject->ptr,value->ptr,sdslen(value->ptr),pos);
decrRefCount(value);
} else if (subject->encoding == REDIS_ENCODING_LINKEDLIST) {
if (where == REDIS_HEAD) {
listAddNodeHead(subject->ptr,value);
} else {
listAddNodeTail(subject->ptr,value);
}
incrRefCount(value);
} else {
redisPanic("Unknown list encoding");
}
}
　　在t_list.c里面，rpushCommand-->pushGenericCommand-->listTypePush。listTypePush里面通过方向变量where来判断是在head还是在tail插入新的Node。