Redis代码阅读2--Redis数据结构之链表
???? 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。
?
?
?
?
?