Redis源码剖析之快速列表(quicklist)( 三 ) @TOC何为quicklist

代码比较长，总结如下：

如果当前被插入节点不满，直接插入。
如果当前被插入节点是满的，要插入的位置是当前节点的尾部，且后一个节点有空间，那就插到后一个节点的头部。
如果当前被插入节点是满的，要插入的位置是当前节点的头部，且前一个节点有空间，那就插到前一个节点的尾部。
如果当前被插入节点是满的，前后节点也都是满的，要插入的位置是当前节点的头部或者尾部，那就创建一个新的节点插进去。
否则，当前节点是满的，且要插入的位置在当前节点的中间位置，我们需要把当前节点分裂成两个新节点，然后再插入。

数据删除数据删除相对于插入而言应该是反着来的，看完下面的代码后你就会发现不完全是：

void quicklistDelEntry(quicklistIter *iter, quicklistEntry *entry) {quicklistNode *prev = entry->node->prev;quicklistNode *next = entry->node->next;int deleted_node = quicklistDelIndex((quicklist *)entry->quicklist,entry->node,/* after delete, the zi is now invalid for any future usage. */iter->zi = NULL;/* If current node is deleted, we must update iterator node and offset. */if (deleted_node) {if (iter->direction == AL_START_HEAD) {iter->current = next;iter->offset = 0;} else if (iter->direction == AL_START_TAIL) {iter->current = prev;iter->offset = -1;}}}REDIS_STATIC int quicklistDelIndex(quicklist *quicklist, quicklistNode *node,unsigned char **p) {int gone = 0;node->zl = ziplistDelete(node->zl, p);node->count--;if (node->count == 0) {gone = 1;__quicklistDelNode(quicklist, node);} else {quicklistNodeUpdateSz(node);}quicklist->count--;/* If we deleted the node, the original node is no longer valid */return gone ? 1 : 0;}

删除相对于插入而言简单多了，我先看的插入逻辑，插入中有节点的分裂，但删除里却没有节点的合并， quicklist有节点最大容量，但没有最小容量限制。
其他API理解了quicklist数据结构的设计，也基本就能猜测到每个api的具体实现了，这里我就不再罗列代码了，有兴趣可以自行查阅。

quicklist *quicklistCreate(void);// 创建quicklist quicklist *quicklistNew(int fill, int compress);// 用一些指定参数创建一个新的quicklistvoid quicklistSetCompressDepth(quicklist *quicklist, int depth);// 设置压缩深度 void quicklistSetFill(quicklist *quicklist, int fill); // 设置容量上限 void quicklistSetOptions(quicklist *quicklist, int fill, int depth); void quicklistRelease(quicklist *quicklist); // 释放quicklistint quicklistPushHead(quicklist *quicklist, void *value, const size_t sz);// 头部插入int quicklistPushTail(quicklist *quicklist, void *value, const size_t sz);// 尾部插入void quicklistPush(quicklist *quicklist, void *value, const size_t sz,int where); // 指定头部或者尾部插入void quicklistAppendZiplist(quicklist *quicklist, unsigned char *zl); // 把一个ziplist放到quicklist中quicklist *quicklistAppendValuesFromZiplist(quicklist *quicklist,unsigned char *zl); // 把ziplist中的所有数据放到quicklist中quicklist *quicklistCreateFromZiplist(int fill, int compress,unsigned char *zl);// 从ziplist生成一个quicklistvoid quicklistInsertAfter(quicklist *quicklist, quicklistEntry *node,void *value, const size_t sz);void quicklistInsertBefore(quicklist *quicklist, quicklistEntry *node,void *value, const size_t sz);void quicklistDelEntry(quicklistIter *iter, quicklistEntry *entry); // 数据删除 int quicklistReplaceAtIndex(quicklist *quicklist, long index, void *data,int sz);// 数据替换 int quicklistDelRange(quicklist *quicklist, const long start, const long stop);// 范围删除quicklistIter *quicklistGetIterator(const quicklist *quicklist, int direction);// 迭代器 quicklistIter *quicklistGetIteratorAtIdx(const quicklist *quicklist,int direction, const long long idx);// 从指定位置开始的迭代器int quicklistNext(quicklistIter *iter, quicklistEntry *node);// 迭代器下一个位置void quicklistReleaseIterator(quicklistIter *iter);// 释放迭代器quicklist *quicklistDup(quicklist *orig);// 去重int quicklistIndex(const quicklist *quicklist, const long long index,quicklistEntry *entry);// 找到entry的下标索引 void quicklistRewind(quicklist *quicklist, quicklistIter *li);void quicklistRewindTail(quicklist *quicklist, quicklistIter *li);void quicklistRotate(quicklist *quicklist);// 选择quicklistint quicklistPopCustom(quicklist *quicklist, int where, unsigned char **data,unsigned int *sz, long long *sval,void *(*saver)(unsigned char *data, unsigned int sz)); int quicklistPop(quicklist *quicklist, int where, unsigned char **data,unsigned int *sz, long long *slong); // 数据pop unsigned long quicklistCount(const quicklist *ql);int quicklistCompare(unsigned char *p1, unsigned char *p2, int p2_len); // 比较大小size_t quicklistGetLzf(const quicklistNode *node, void **data);// LZF节点
上一页
1
2
3
4
下一页
		  	


















次世代大作标配 光线追踪DLSS深度剖析 

java 从零实现属于你的 redis 分布式锁 

Redis集群做法的难点，百万并发客户端「实战」 

C语言火车订单管理源码 

HFL Redis_10_set类型底层存储数据结构 

为什么 Redis 单线程能支撑高并发？ 

清华教授整理535本编程电子书+视频教程+项目源码限时领取 

Redis流行的原因 

掌握会用了，为什么还要源码学习？ 

阿里爆款SpringBoot项目实战PDF+源码+视频分享