X-Git-Url: https://git.saurik.com/redis.git/blobdiff_plain/03e52931dd4e7d3c9a87eaa0195fdb8b08ff74b2..6435c76772bfc846c4f336d07f56668aef33a38b:/ziplist.c?ds=sidebyside diff --git a/ziplist.c b/ziplist.c index d3e3cbaa..e54f3211 100644 --- a/ziplist.c +++ b/ziplist.c @@ -56,6 +56,7 @@ typedef struct zlentry { unsigned int lensize, len; unsigned int headersize; unsigned char encoding; + unsigned char *p; } zlentry; /* Return bytes needed to store integer encoded by 'encoding' */ @@ -206,17 +207,14 @@ static zlentry zipEntry(unsigned char *p) { e.len = zipDecodeLength(p+e.prevrawlensize,&e.lensize); e.headersize = e.prevrawlensize+e.lensize; e.encoding = ZIP_ENCODING(p+e.prevrawlensize); + e.p = p; return e; } -/* Return the total amount used by an entry (encoded length + payload). */ +/* Return the total number of bytes used by the entry at "p". */ static unsigned int zipRawEntryLength(unsigned char *p) { - unsigned int prevlensize, lensize, len; - /* Byte-size of encoded length of previous entry */ - zipDecodeLength(p,&prevlensize); - /* Encoded length of this entry's payload */ - len = zipDecodeLength(p+prevlensize, &lensize); - return prevlensize+lensize+len; + zlentry e = zipEntry(p); + return e.headersize + e.len; } /* Create a new empty ziplist. */ @@ -250,72 +248,119 @@ static unsigned char *ziplistTail(unsigned char *zl) { p += zipRawEntryLength(p); } return q; + +/* Delete "num" entries, starting at "p". Returns pointer to the ziplist. */ +static unsigned char *__ziplistDelete(unsigned char *zl, unsigned char *p, int num) { + unsigned int i, totlen, deleted = 0; + int nextdiff = 0; + zlentry first = zipEntry(p); + for (i = 0; p[0] != ZIP_END && i < num; i++) { + p += zipRawEntryLength(p); + deleted++; + } + + totlen = p-first.p; + if (totlen > 0) { + if (p[0] != ZIP_END) { + /* Tricky: storing the prevlen in this entry might reduce or + * increase the number of bytes needed, compared to the current + * prevlen. Note that we can always store this length because + * it was previously stored by an entry that is being deleted. */ + nextdiff = zipPrevLenByteDiff(p,first.prevrawlen); + zipEncodeLength(p-nextdiff,ZIP_ENC_RAW,first.prevrawlen); + + /* Update offset for tail */ + ZIPLIST_TAIL_OFFSET(zl) -= totlen+nextdiff; + + /* Move tail to the front of the ziplist */ + memmove(first.p,p-nextdiff,ZIPLIST_BYTES(zl)-(p-zl)-1+nextdiff); + } else { + /* The entire tail was deleted. No need to move memory. */ + ZIPLIST_TAIL_OFFSET(zl) = (first.p-zl)-first.prevrawlen; + } + + /* Resize and update length */ + zl = ziplistResize(zl, ZIPLIST_BYTES(zl)-totlen+nextdiff); + ZIPLIST_INCR_LENGTH(zl,-deleted); + } + return zl; } -unsigned char *ziplistPush(unsigned char *zl, unsigned char *entry, unsigned int elen, int where) { - unsigned int curlen = ZIPLIST_BYTES(zl), reqlen, prevlen; - unsigned char *p, *curtail; +/* Insert item at "p". */ +static unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) { + unsigned int curlen = ZIPLIST_BYTES(zl), reqlen, prevlen = 0; + unsigned int offset, nextdiff = 0; + unsigned char *tail; char encoding = ZIP_ENC_RAW; long long value; + zlentry entry; - /* We need to store the length of the current tail when the list - * is non-empty and we push at the tail. */ - curtail = zl+ZIPLIST_TAIL_OFFSET(zl); - if (where == ZIPLIST_TAIL && curtail[0] != ZIP_END) { - prevlen = zipRawEntryLength(curtail); + /* Find out prevlen for the entry that is inserted. */ + if (p[0] != ZIP_END) { + entry = zipEntry(p); + prevlen = entry.prevrawlen; } else { - prevlen = 0; + tail = ziplistTail(zl); + if (tail[0] != ZIP_END) { + prevlen = zipRawEntryLength(tail); + } } /* See if the entry can be encoded */ - if (zipTryEncoding(entry,&value,&encoding)) { + if (zipTryEncoding(s,&value,&encoding)) { reqlen = zipEncodingSize(encoding); } else { - reqlen = elen; + reqlen = slen; } /* We need space for both the length of the previous entry and * the length of the payload. */ reqlen += zipEncodeLength(NULL,ZIP_ENC_RAW,prevlen); - reqlen += zipEncodeLength(NULL,encoding,elen); - - /* Resize the ziplist and move if needed */ - zl = ziplistResize(zl,curlen+reqlen); - if (where == ZIPLIST_HEAD) { - p = zl+ZIPLIST_HEADER_SIZE; - if (*p != ZIP_END) { - /* Subtract one because of the ZIP_END bytes */ - memmove(p+reqlen,p,curlen-ZIPLIST_HEADER_SIZE-1); - } + reqlen += zipEncodeLength(NULL,encoding,slen); + + /* When the insert position is not equal to the tail, we need to + * make sure that the next entry can hold this entry's length in + * its prevlen field. */ + nextdiff = p[0] != ZIP_END ? zipPrevLenByteDiff(p,reqlen) : 0; + + /* Store offset because a realloc may change the address of zl. */ + offset = p-zl; + zl = ziplistResize(zl,curlen+reqlen+nextdiff); + p = zl+offset; + + /* Apply memory move when necessary and update tail offset. */ + if (p[0] != ZIP_END) { + /* Subtract one because of the ZIP_END bytes */ + memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff); + /* Encode this entry's raw length in the next entry. */ + zipEncodeLength(p+reqlen,ZIP_ENC_RAW,reqlen); + /* Update offset for tail */ + ZIPLIST_TAIL_OFFSET(zl) += reqlen+nextdiff; } else { - p = zl+curlen-1; - } - - /* Update tail offset if this is not the first element */ - if (curtail[0] != ZIP_END) { - if (where == ZIPLIST_HEAD) { - ZIPLIST_TAIL_OFFSET(zl) += reqlen; - } else { - ZIPLIST_TAIL_OFFSET(zl) += prevlen; - } + /* This element will be the new tail. */ + ZIPLIST_TAIL_OFFSET(zl) = p-zl; } /* Write the entry */ p += zipEncodeLength(p,ZIP_ENC_RAW,prevlen); - p += zipEncodeLength(p,encoding,elen); + p += zipEncodeLength(p,encoding,slen); if (encoding != ZIP_ENC_RAW) { zipSaveInteger(p,value,encoding); } else { - memcpy(p,entry,elen); + memcpy(p,s,slen); } ZIPLIST_INCR_LENGTH(zl,1); return zl; } +unsigned char *ziplistPush(unsigned char *zl, unsigned char *s, unsigned int slen, int where) { + unsigned char *p; + p = (where == ZIPLIST_HEAD) ? ziplistHead(zl) : (zl+ZIPLIST_BYTES(zl)-1); + return __ziplistInsert(zl,p,s,slen); +} + unsigned char *ziplistPop(unsigned char *zl, sds *target, int where) { - unsigned int curlen = ZIPLIST_BYTES(zl), rawlen; zlentry entry; - int nextdiff = 0; unsigned char *p; long long value; if (target) *target = NULL; @@ -325,7 +370,6 @@ unsigned char *ziplistPop(unsigned char *zl, sds *target, int where) { if (*p == ZIP_END) return zl; entry = zipEntry(p); - rawlen = entry.headersize+entry.len; if (target) { if (entry.encoding == ZIP_ENC_RAW) { *target = sdsnewlen(p+entry.headersize,entry.len); @@ -335,32 +379,7 @@ unsigned char *ziplistPop(unsigned char *zl, sds *target, int where) { } } - if (where == ZIPLIST_HEAD) { - /* The next entry will now be the head of the list */ - if (p[rawlen] != ZIP_END) { - /* Tricky: storing the length of the previous entry in the next - * entry (this previous length is always 0 when popping from the - * head), might reduce the number of bytes needed. - * - * In this special case (new length is 0), we know that the - * byte difference to store is always <= 0, which means that - * we always have space to store it. */ - nextdiff = zipPrevLenByteDiff(p+rawlen,0); - zipEncodeLength(p+rawlen-nextdiff,ZIP_ENC_RAW,0); - } - /* Move list to the front */ - memmove(p,p+rawlen-nextdiff,curlen-ZIPLIST_HEADER_SIZE-rawlen+nextdiff); - - /* Subtract the gained space from the tail offset */ - ZIPLIST_TAIL_OFFSET(zl) -= rawlen+nextdiff; - } else { - /* Subtract the length of the previous element from the tail offset. */ - ZIPLIST_TAIL_OFFSET(zl) -= entry.prevrawlen; - } - - /* Resize and update length */ - zl = ziplistResize(zl,curlen-rawlen+nextdiff); - ZIPLIST_INCR_LENGTH(zl,-1); + zl = __ziplistDelete(zl,p,1); return zl; } @@ -405,42 +424,19 @@ unsigned int ziplistGet(unsigned char *p, unsigned char **sstr, unsigned int *sl /* Delete a range of entries from the ziplist. */ unsigned char *ziplistDeleteRange(unsigned char *zl, unsigned int index, unsigned int num) { - unsigned char *p, *first = ziplistIndex(zl, index); - unsigned int i, totlen, deleted = 0; - for (p = first, i = 0; *p != ZIP_END && i < num; i++) { - p += zipRawEntryLength(p); - deleted++; - } - - totlen = p-first; - if (totlen > 0) { - /* Move current tail to the new tail when there *is* a tail */ - if (*p != ZIP_END) memmove(first,p,ZIPLIST_BYTES(zl)-(p-zl)-1); - - /* Resize and update length */ - zl = ziplistResize(zl, ZIPLIST_BYTES(zl)-totlen); - ZIPLIST_INCR_LENGTH(zl,-deleted); - } - return zl; + unsigned char *p = ziplistIndex(zl,index); + return __ziplistDelete(zl,p,num); } /* Delete a single entry from the ziplist, pointed to by *p. * Also update *p in place, to be able to iterate over the * ziplist, while deleting entries. */ unsigned char *ziplistDelete(unsigned char *zl, unsigned char **p) { - unsigned int offset = *p-zl, tail, len; - len = zipRawEntryLength(*p); - tail = ZIPLIST_BYTES(zl)-offset-len-1; - - /* Move current tail to the new tail when there *is* a tail */ - if (tail > 0) memmove(*p,*p+len,tail); - - /* Resize and update length */ - zl = ziplistResize(zl, ZIPLIST_BYTES(zl)-len); - ZIPLIST_INCR_LENGTH(zl,-1); + unsigned int offset = *p-zl; + zl = __ziplistDelete(zl,*p,1); - /* Store new pointer to current element in p. - * This needs to be done because zl can change on realloc. */ + /* Store pointer to current element in p, because ziplistDelete will + * do a realloc which might result in a different "zl"-pointer. */ *p = zl+offset; return zl; }