简而言之，quicklist是一个双端链表,双端链表的节点表示的元素是一个压缩链表(ziplist),压缩链表中的每一个entry是实际数据的表示。ziplist(https://www.jianshu.com/p/adfde59df5ff)
一、结构
//占32字节 表示快速链表的节点 节点数据是一个压缩链表 压缩链表中的entry 包含的才是实际数据
typedef struct quicklistNode {
struct quicklistNode *prev;//8字节
struct quicklistNode *next;//8字节
unsigned char *zl;//8字节 压缩链表首地址
unsigned int sz; //4字节 压缩链表的所占字节数
//以下总共四字节
unsigned int count : 16; //压缩链表的entry个数
unsigned int encoding : 2;//1表示不压缩 2 表示压缩
unsigned int container : 2;/* NONE==1 or ZIPLIST==2 */
unsigned int recompress : 1; // /* was this node previous compressed? */
unsigned int attempted_compress : 1;//quicklist是否已经压缩过
unsigned int extra : 10;//额外bit位
} quicklistNode;//快速链表的节点
压缩链表编码后的结构
typedef struct quicklistLZF {
unsigned int sz;
char compressed[];
} quicklistLZF;
//占40字节(由于字节对齐)
typedef struct quicklist {//5*8=40bytes
quicklistNode *head; //8
quicklistNode *tail; //8
unsigned long count; //8 所有压缩链表中所有entry的个数之和
unsigned long len; //8 快速链表节点个数
int fill : 16; //2 ziplist大小限定，由list-max-ziplist-size给定
unsigned int compress : 16; //2 一个quicklist两端不被压缩的节点个数。
} quicklist;
typedef struct quicklistIter {//快速链表迭代器
const quicklist *quicklist; //所在快速链表
quicklistNode *current; //所在的快速链表节点
unsigned char *zi; //ziplist中的entry首地址
long offset; //数据entry在当前ziplist中的第offset位
int direction; //方向 向后或者向前
} quicklistIter;
//实际数据的获得表示
typedef struct quicklistEntry {
const quicklist *quicklist;//属于的快速链表
quicklistNode *node; //指向的快速链表的节点
unsigned char *zi; //指向当前ziplist的entry的指针
unsigned char *value; //指向当前ziplist结构的字符串vlaue成员
long long longval; //指向当前ziplist结构的数字成员
unsigned int sz; //保存当前ziplist结构的字节数大小
int offset; //保存当前数据相对ziplist的偏移量
} quicklistEntry;//就是表示 实际的数据的存储方位
二、api
quicklist *quicklistCreate(void);//创建一个新的快速双端链表
quicklist *quicklistNew(int fill, int compress);//创建一个新的快速双端链表
void quicklistSetCompressDepth(quicklist *quicklist, int depth);//设置压缩深度
void quicklistSetFill(quicklist *quicklist, int fill);//设置填充因子
void quicklistSetOptions(quicklist *quicklist, int fill, int depth);//同时设置压缩深度和填充因子
void quicklistRelease(quicklist *quicklist);//释放快速链表内存
int quicklistPushHead(quicklist *quicklist, void *value, const size_t sz);//往头部对应的ziplist插入数据
int quicklistPushTail(quicklist *quicklist, void *value, const size_t sz);//往尾部对应的ziplist插入数据
void quicklistPush(quicklist *quicklist, void *value, const size_t sz,
int where);//往头部或者尾部对应的ziplist插入数据
void quicklistAppendZiplist(quicklist *quicklist, unsigned char *zl);//快速链表中尾部插入压缩链表
quicklist *quicklistAppendValuesFromZiplist(quicklist *quicklist,
unsigned char *zl);//将压缩链表中的每隔entry数据插入到快速链表tail里面
quicklist *quicklistCreateFromZiplist(int fill, int compress,
unsigned char *zl);//创建快速链表，然后将压缩链表中的数据插入到快速链表
void quicklistInsertAfter(quicklist *quicklist, quicklistEntry *node,
void *value, const size_t sz);//在node所指向的数据后面插入数据
void quicklistInsertBefore(quicklist *quicklist, quicklistEntry *node,
void *value, const size_t sz);//在node前面插入数据
void quicklistDelEntry(quicklistIter *iter, quicklistEntry *entry);//删除entry指向的数据
int quicklistReplaceAtIndex(quicklist *quicklist, long index, void *data,
int sz);//替换index位置的数据
int quicklistDelRange(quicklist *quicklist, const long start, const long stop);//删除start 到 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);//得到node的下一个元素迭代器
void quicklistReleaseIterator(quicklistIter *iter);//释放当前指向的迭代器
quicklist *quicklistDup(quicklist *orig);//copy
int quicklistIndex(const quicklist *quicklist, const long long index,
quicklistEntry *entry);//找到第index个元素，index可以为-1表示最后一个元素，然后对entry赋值
void quicklistRewind(quicklist *quicklist, quicklistIter *li);
void quicklistRewindTail(quicklist *quicklist, quicklistIter *li);
void quicklistRotate(quicklist *quicklist);//把尾部元素移到头部
int quicklistPopCustom(quicklist *quicklist, int where, unsigned char **data,
unsigned int *sz, long long *sval,
void *(*saver)(unsigned char *data, unsigned int sz));//pop 只能从头或者尾部 pop
int quicklistPop(quicklist *quicklist, int where, unsigned char **data,
unsigned int *sz, long long *slong);//pop 只能从头或者尾部
unsigned long quicklistCount(const quicklist *ql);//返回所有压缩链表中所有entry的个数之和
int quicklistCompare(unsigned char *p1, unsigned char *p2, int p2_len);//比较p1所指向的entry对应的数据与p2
size_t quicklistGetLzf(const quicklistNode *node, void **data);
三、重要api介绍
1. quicklistInsertAfter
void quicklistInsertAfter(quicklist *quicklist, quicklistEntry *entry,
void *value, const size_t sz) {
_quicklistInsert(quicklist, entry, value, sz, 1);
}
//after==1向后插入 ==0前插
REDIS_STATIC void _quicklistInsert(quicklist *quicklist, quicklistEntry *entry,
void *value, const size_t sz, int after) {
int full = 0, at_tail = 0, at_head = 0, full_next = 0, full_prev = 0;
int fill = quicklist->fill;
quicklistNode *node = entry->node;
quicklistNode *new_node = NULL;
if (!node) {//如果node为空 只需要创建一个新的ziplist，并将数据插入即可
/* we have no reference node, so let's create only node in the list */
D("No node given!");
new_node = quicklistCreateNode();
new_node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_HEAD);
__quicklistInsertNode(quicklist, NULL, new_node, after);
new_node->count++;
quicklist->count++;
return;
}
if (!_quicklistNodeAllowInsert(node, fill, sz)) {//对于sz长度的数据可以插入吗
full = 1;//不允许插入的话 表示此节点满了 full设为1
}
if (after && (entry->offset == node->count)) {//如果这个entry是最后一个数据 应该插入这里
D("At Tail of current ziplist");
at_tail = 1;
if (!_quicklistNodeAllowInsert(node->next, fill, sz)) {
D("Next node is full too.");
full_next = 1;//下一个节点也满了
}
}
if (!after && (entry->offset == 0)) {//如果是前插
D("At Head");
at_head = 1;
if (!_quicklistNodeAllowInsert(node->prev, fill, sz)) {
D("Prev node is full too.");
full_prev = 1;
}
}
if (!full && after) {//当前node未满 向后的方向此时直接插入即可
D("Not full, inserting after current position.");
quicklistDecompressNodeForUse(node);
unsigned char *next = ziplistNext(node->zl, entry->zi);
if (next == NULL) {
node->zl = ziplistPush(node->zl, value, sz, ZIPLIST_TAIL);
} else {
node->zl = ziplistInsert(node->zl, next, value, sz);
}
node->count++;
quicklistNodeUpdateSz(node);
quicklistRecompressOnly(quicklist, node);
} else if (!full && !after) {//当前node未满 向前插入此时直接插入即可
D("Not full, inserting before current position.");
quicklistDecompressNodeForUse(node);
node->zl = ziplistInsert(node->zl, entry->zi, value, sz);
node->count++;
quicklistNodeUpdateSz(node);
quicklistRecompressOnly(quicklist, node);
} else if (full && at_tail && node->next && !full_next && after) {//插入到下一个node 的条件
D("Full and tail, but next isn't full; inserting next node head");
new_node = node->next;
quicklistDecompressNodeForUse(new_node);
new_node->zl = ziplistPush(new_node->zl, value, sz, ZIPLIST_HEAD);
new_node->count++;
quicklistNodeUpdateSz(new_node);
quicklistRecompressOnly(quicklist, new_node);
} else if (full && at_head && node->prev && !full_prev && !after) {//插入到前一个node 的条件
D("Full and head, but prev isn't full, inserting prev node tail");
new_node = node->prev;
quicklistDecompressNodeForUse(new_node);
new_node->zl = ziplistPush(new_node->zl, value, sz, ZIPLIST_TAIL);
new_node->count++;
quicklistNodeUpdateSz(new_node);
quicklistRecompressOnly(quicklist, new_node);
} else if (full && ((at_tail && node->next && full_next && after) ||
(at_head && node->prev && full_prev && !after))) {//如果前一个node 或者后一个node也满来了 创建一个新的node
D("\tprovisioning new node...");
new_node = quicklistCreateNode();
new_node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_HEAD);
new_node->count++;
quicklistNodeUpdateSz(new_node);
__quicklistInsertNode(quicklist, node, new_node, after);
} else if (full) {//将node对应的压缩链表分割
D("\tsplitting node...");
quicklistDecompressNodeForUse(node);
new_node = _quicklistSplitNode(node, entry->offset, after);//把ziplist分割为两部分
new_node->zl = ziplistPush(new_node->zl, value, sz,
after ? ZIPLIST_HEAD : ZIPLIST_TAIL);
new_node->count++;
quicklistNodeUpdateSz(new_node);
__quicklistInsertNode(quicklist, node, new_node, after);
_quicklistMergeNodes(quicklist, node);
}
quicklist->count++;
}
2. quicklistDelRange
//返回1 表示都删除了 0表示啥也没删除
int quicklistDelRange(quicklist *quicklist, const long start,
const long count) {
if (count <= 0)
return 0;
unsigned long extent = (unsigned long) count; /*删除的长度*/
if (start >= 0 && extent > (quicklist->count - start)) {//如果start大于零且从start开始count个查过了总个数 更新正确删除的个数
extent = quicklist->count - start;
} else if (start < 0 && extent > (unsigned long)(-start)) {
extent = -start;
}
quicklistEntry entry;
if (!quicklistIndex(quicklist, start, &entry))
return 0;
D("Quicklist delete request for start %ld, count %ld, extent: %ld", start,
count, extent);
quicklistNode *node = entry.node;
/* iterate over next nodes until everything is deleted. */
while (extent) {//最终应该删除这么多个数据
quicklistNode *next = node->next;
unsigned long del;
int delete_entire_node = 0;
if (entry.offset == 0 && extent >= node->count) {
//直接删除此node del为此ziplist数据个数
delete_entire_node = 1;
del = node->count;
} else if (entry.offset >= 0 && extent >= node->count) {
//从offset删除 del长度的数据
del = node->count - entry.offset;
} else if (entry.offset < 0) {
del = -entry.offset;
if (del > extent)
del = extent;
} else {
del = extent;
}
D("[%ld]: asking to del: %ld because offset: %d; (ENTIRE NODE: %d), "
"node count: %u",
extent, del, entry.offset, delete_entire_node, node->count);
if (delete_entire_node) {//直接ziplist全部删除
__quicklistDelNode(quicklist, node);
} else {//范围删除
quicklistDecompressNodeForUse(node);
node->zl = ziplistDeleteRange(node->zl, entry.offset, del);
quicklistNodeUpdateSz(node);
node->count -= del;
quicklist->count -= del;
quicklistDeleteIfEmpty(quicklist, node);
if (node)
quicklistRecompressOnly(quicklist, node);
}
extent -= del;//更新还要被删除的entry的个数
node = next;
entry.offset = 0;
}
return 1;
}
网友评论