I have a question about __ziplistDelete function as follows:
/* When the tail contains more than one entry, we need to take
* "nextdiff" in account as well. Otherwise, a change in the
* size of prevlen doesn't have an effect on the *tail* offset. */
zipEntry(p, &tail);
if (p[tail.headersize+tail.len] != ZIP_END) {
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
}
As we know, ZIPLIST_TAIL_OFFSET macro returns the offset of the last item(entry) inside the ziplist. When the tail contians just one entry instead of more than one entry , should we take "nextdiff" in account as well? Is there a problem about these lines:
if (p[tail.headersize+tail.len] != ZIP_END) {
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
}
Thanks.
/* Delete "num" entries, starting at "p". Returns pointer to the ziplist. */
unsigned char *__ziplistDelete(unsigned char *zl, unsigned char *p, unsigned int num) {
unsigned int i, totlen, deleted = 0;
size_t offset;
int nextdiff = 0;
zlentry first, tail;
zipEntry(p, &first);
for (i = 0; p[0] != ZIP_END && i < num; i++) {
p += zipRawEntryLength(p);
deleted++;
}
totlen = p-first.p; /* Bytes taken by the element(s) to delete. */
if (totlen > 0) {
if (p[0] != ZIP_END) {
/* Storing `prevrawlen` in this entry may increase or decrease the
* number of bytes required compare to the current `prevrawlen`.
* There always is room to store this, because it was previously
* stored by an entry that is now being deleted. */
nextdiff = zipPrevLenByteDiff(p,first.prevrawlen);
/* Note that there is always space when p jumps backward: if
* the new previous entry is large, one of the deleted elements
* had a 5 bytes prevlen header, so there is for sure at least
* 5 bytes free and we need just 4. */
p -= nextdiff;
zipStorePrevEntryLength(p,first.prevrawlen);
/* Update offset for tail */
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))-totlen);
/* When the tail contains more than one entry, we need to take
* "nextdiff" in account as well. Otherwise, a change in the
* size of prevlen doesn't have an effect on the *tail* offset. */
zipEntry(p, &tail);
if (p[tail.headersize+tail.len] != ZIP_END) {
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
}
/* Move tail to the front of the ziplist */
memmove(first.p,p,
intrev32ifbe(ZIPLIST_BYTES(zl))-(p-zl)-1);
} else {
/* The entire tail was deleted. No need to move memory. */
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe((first.p-zl)-first.prevrawlen);
}
/* Resize and update length */
offset = first.p-zl;
zl = ziplistResize(zl, intrev32ifbe(ZIPLIST_BYTES(zl))-totlen+nextdiff);
ZIPLIST_INCR_LENGTH(zl,-deleted);
p = zl+offset;
/* When nextdiff != 0, the raw length of the next entry has changed, so
* we need to cascade the update throughout the ziplist */
if (nextdiff != 0)
zl = __ziplistCascadeUpdate(zl,p);
}
return zl;
}
Comment From: Qinch
@soloestoy 麻烦帮忙看下我是否理解错误
Comment From: soloestoy
OK, I will check that. News come soon.
Comment From: soloestoy
Hi, @Qinch
It is not a bug, just remember that the ZIPLIST_TAIL_OFFSET points to the last zlentry, not the ZIP_END.
If the tail contains only one entry, the ZIPLIST_TAIL_OFFSET already points to the tail, so we need to take nextdiff in account only when the tail contains more than one entry, and __ziplistCascadeUpdate will work to update all entries in tail.
Comment From: Qinch
Thanks for you reply @soloestoy ,I know that ZIPLIST_TAIL_OFFSET return the head address of the last entry(最后一个zlentry的首地址) in zl.
I'm sorry for my broken English.
我想到的是这样一种场景（单击图片放大）：
图中zl为ziplist的首地址，p为__ziplistDelete的参数，num=2，即表示从p开始删除两个entry。 在删除函数执行之前，其中entry2的prevlensize（即entry1的长度）采用5个bytes表示，而entry4的prevlensize（entry3的长度）为1个字节，所以nextdiff=4bytes 当删除函数执行时，zltail设置的值为 new zltail=old zltail-totlen, 如果tail指向的为last zlentry, new zltail指向的last zlentry的首地址的值应该为p'-nextdiff？
Comment From: soloestoy
OK, let me show the trace of this scenario:
zipEntry(p, &first);
for (i = 0; p[0] != ZIP_END && i < num; i++) {
p += zipRawEntryLength(p);
deleted++;
}
totlen = p-first.p; /* Bytes taken by the element(s) to delete. */
After this loop, p points to entry4, and totlen is the length of entry2 and entry3.
if (totlen > 0) {
if (p[0] != ZIP_END) {
/* Storing `prevrawlen` in this entry may increase or decrease the
* number of bytes required compare to the current `prevrawlen`.
* There always is room to store this, because it was previously
* stored by an entry that is now being deleted. */
nextdiff = zipPrevLenByteDiff(p,first.prevrawlen);
/* Note that there is always space when p jumps backward: if
* the new previous entry is large, one of the deleted elements
* had a 5 bytes prevlen header, so there is for sure at least
* 5 bytes free and we need just 4. */
p -= nextdiff;
zipStorePrevEntryLength(p,first.prevrawlen);
/* Update offset for tail */
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))-totlen);
We will take this branch because the two conditions are satisfied, and no matter what the nextdiff is, after ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))-totlen); the ZIPLIST_TAIL_OFFSET points to the address of entry2, the real tail.
zipEntry(p, &tail);
if (p[tail.headersize+tail.len] != ZIP_END) {
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
}
So, these code should not be executed, make sense?
Comment From: Qinch
谢谢，打扰了 @soloestoy
Comment From: soloestoy
u r welcome : )
Comment From: allan-ma
- zipEntry(p, &tail); This mean p point to the tail entry of ziplist? if it is, why? If I just delete entry2, I think p should point to entry3, not the tail of ziplist
@soloestoy