X-Git-Url: https://git.saurik.com/redis.git/blobdiff_plain/c4aace9003e29fc9becce292683dd09bdce7785c..6435c76772bfc846c4f336d07f56668aef33a38b:/ziplist.c diff --git a/ziplist.c b/ziplist.c index 3dc534d3..e54f3211 100644 --- a/ziplist.c +++ b/ziplist.c @@ -23,6 +23,11 @@ #include "sds.h" #include "ziplist.h" +/* Important note: the ZIP_END value is used to depict the end of the + * ziplist structure. When a pointer contains an entry, the first couple + * of bytes contain the encoded length of the previous entry. This length + * is encoded as ZIP_ENC_RAW length, so the first two bits will contain 00 + * and the byte will therefore never have a value of 255. */ #define ZIP_END 255 #define ZIP_BIGLEN 254 @@ -40,11 +45,20 @@ /* Utility macros */ #define ZIPLIST_BYTES(zl) (*((unsigned int*)(zl))) -#define ZIPLIST_LENGTH(zl) (*((zl)+sizeof(unsigned int))) -#define ZIPLIST_HEADER_SIZE (sizeof(unsigned int)+1) +#define ZIPLIST_TAIL_OFFSET(zl) (*((zl)+sizeof(unsigned int))) +#define ZIPLIST_LENGTH(zl) (*((zl)+2*sizeof(unsigned int))) +#define ZIPLIST_HEADER_SIZE (2*sizeof(unsigned int)+1) #define ZIPLIST_INCR_LENGTH(zl,incr) { \ if (ZIPLIST_LENGTH(zl) < ZIP_BIGLEN) ZIPLIST_LENGTH(zl)+=incr; } +typedef struct zlentry { + unsigned int prevrawlensize, prevrawlen; + unsigned int lensize, len; + unsigned int headersize; + unsigned char encoding; + unsigned char *p; +} zlentry; + /* Return bytes needed to store integer encoded by 'encoding' */ static unsigned int zipEncodingSize(char encoding) { if (encoding == ZIP_ENC_SHORT) { @@ -116,6 +130,14 @@ static unsigned int zipEncodeLength(unsigned char *p, char encoding, unsigned in return len; } +/* Return the difference in number of bytes needed to store the new length + * "len" on the entry pointed to by "p". */ +static int zipPrevLenByteDiff(unsigned char *p, unsigned int len) { + unsigned int prevlensize; + zipDecodeLength(p,&prevlensize); + return zipEncodeLength(NULL,ZIP_ENC_RAW,len)-prevlensize; +} + /* Check if string pointed to by 'entry' can be encoded as an integer. * Stores the integer value in 'v' and its encoding in 'encoding'. * Warning: this function requires a NULL-terminated string! */ @@ -124,7 +146,7 @@ static int zipTryEncoding(unsigned char *entry, long long *v, char *encoding) { char *eptr; if (entry[0] == '-' || (entry[0] >= '0' && entry[0] <= '9')) { - value = strtoll(entry,&eptr,10); + value = strtoll((char*)entry,&eptr,10); if (eptr[0] != '\0') return 0; if (value >= SHRT_MIN && value <= SHRT_MAX) { *encoding = ZIP_ENC_SHORT; @@ -178,11 +200,21 @@ static long long zipLoadInteger(unsigned char *p, char encoding) { return ret; } -/* Return the total amount used by an entry (encoded length + payload). */ +/* Return a struct with all information about an entry. */ +static zlentry zipEntry(unsigned char *p) { + zlentry e; + e.prevrawlen = zipDecodeLength(p,&e.prevrawlensize); + 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 number of bytes used by the entry at "p". */ static unsigned int zipRawEntryLength(unsigned char *p) { - unsigned int lensize, len; - len = zipDecodeLength(p, &lensize); - return lensize + len; + zlentry e = zipEntry(p); + return e.headersize + e.len; } /* Create a new empty ziplist. */ @@ -190,6 +222,7 @@ unsigned char *ziplistNew(void) { unsigned int bytes = ZIPLIST_HEADER_SIZE+1; unsigned char *zl = zmalloc(bytes); ZIPLIST_BYTES(zl) = bytes; + ZIPLIST_TAIL_OFFSET(zl) = ZIPLIST_HEADER_SIZE; ZIPLIST_LENGTH(zl) = 0; zl[bytes-1] = ZIP_END; return zl; @@ -215,48 +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; - unsigned char *p; +/* 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; + + /* Find out prevlen for the entry that is inserted. */ + if (p[0] != ZIP_END) { + entry = zipEntry(p); + prevlen = entry.prevrawlen; + } else { + 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; } - 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); - } + + /* 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,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; + /* This element will be the new tail. */ + ZIPLIST_TAIL_OFFSET(zl) = p-zl; } /* Write the entry */ - p += zipEncodeLength(p,encoding,elen); + p += zipEncodeLength(p,ZIP_ENC_RAW,prevlen); + 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; - unsigned int len, lensize; + zlentry entry; unsigned char *p; long long value; if (target) *target = NULL; @@ -264,25 +368,18 @@ unsigned char *ziplistPop(unsigned char *zl, sds *target, int where) { /* Get pointer to element to remove */ p = (where == ZIPLIST_HEAD) ? ziplistHead(zl) : ziplistTail(zl); if (*p == ZIP_END) return zl; - len = zipDecodeLength(p,&lensize); + + entry = zipEntry(p); if (target) { - if (ZIP_ENCODING(p) == ZIP_ENC_RAW) { - *target = sdsnewlen(p+lensize,len); + if (entry.encoding == ZIP_ENC_RAW) { + *target = sdsnewlen(p+entry.headersize,entry.len); } else { - value = zipLoadInteger(p+lensize,ZIP_ENCODING(p)); + value = zipLoadInteger(p+entry.headersize,entry.encoding); *target = sdscatprintf(sdsempty(), "%lld", value); } } - /* Move list to front when popping from the head */ - rawlen = lensize+len; - if (where == ZIPLIST_HEAD) { - memmove(p,p+rawlen,curlen-ZIPLIST_HEADER_SIZE-len); - } - - /* Resize and update length */ - zl = ziplistResize(zl,curlen-rawlen); - ZIPLIST_INCR_LENGTH(zl,-1); + zl = __ziplistDelete(zl,p,1); return zl; } @@ -306,19 +403,20 @@ unsigned char *ziplistNext(unsigned char *p) { * on the encoding of the entry. 'e' is always set to NULL to be able * to find out whether the string pointer or the integer value was set. * Return 0 if 'p' points to the end of the zipmap, 1 otherwise. */ -unsigned int ziplistGet(unsigned char *p, unsigned char **e, unsigned int *elen, long long *v) { - unsigned int len, lensize; +unsigned int ziplistGet(unsigned char *p, unsigned char **sstr, unsigned int *slen, long long *sval) { + zlentry entry; if (*p == ZIP_END) return 0; - if (e) *e = NULL; - len = zipDecodeLength(p,&lensize); - if (ZIP_ENCODING(p) == ZIP_ENC_RAW) { - if (e) { - *elen = len; - *e = p+lensize; + if (sstr) *sstr = NULL; + + entry = zipEntry(p); + if (entry.encoding == ZIP_ENC_RAW) { + if (sstr) { + *slen = entry.len; + *sstr = p+entry.headersize; } } else { - if (v) { - *v = zipLoadInteger(p+lensize,ZIP_ENCODING(p)); + if (sval) { + *sval = zipLoadInteger(p+entry.headersize,entry.encoding); } } return 1; @@ -326,68 +424,45 @@ unsigned int ziplistGet(unsigned char *p, unsigned char **e, unsigned int *elen, /* 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, deleted = 0, totlen, newlen; - 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; + unsigned int offset = *p-zl; + zl = __ziplistDelete(zl,*p,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); - - /* 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; } /* Compare entry pointer to by 'p' with 'entry'. Return 1 if equal. */ -unsigned int ziplistCompare(unsigned char *p, unsigned char *entry, unsigned int elen) { - unsigned int zlen, lensize; - char encoding; - long long zval, eval; +unsigned int ziplistCompare(unsigned char *p, unsigned char *sstr, unsigned int slen) { + zlentry entry; + unsigned char sencoding; + long long val, sval; if (*p == ZIP_END) return 0; - zlen = zipDecodeLength(p,&lensize); - if (ZIP_ENCODING(p) == ZIP_ENC_RAW) { + entry = zipEntry(p); + if (entry.encoding == ZIP_ENC_RAW) { /* Raw compare */ - if (zlen == elen) { - return memcmp(p+lensize,entry,elen) == 0; + if (entry.len == slen) { + return memcmp(p+entry.headersize,sstr,slen) == 0; } else { return 0; } } else { - if (zipTryEncoding(entry,&eval,&encoding)) { - /* Do integer compare */ - zval = zipLoadInteger(p+lensize,ZIP_ENCODING(p)); - return zval == eval; - } else { - /* Ziplist entry is integer encoded, but given entry is not. */ + /* Try to compare encoded values */ + if (zipTryEncoding(sstr,&sval,&sencoding)) { + if (entry.encoding == sencoding) { + val = zipLoadInteger(p+entry.headersize,entry.encoding); + return val == sval; + } } } return 0; @@ -411,25 +486,28 @@ unsigned int ziplistLen(unsigned char *zl) { return len; } +/* Return size in bytes of ziplist. */ +unsigned int ziplistSize(unsigned char *zl) { + return ZIPLIST_BYTES(zl); +} + void ziplistRepr(unsigned char *zl) { - unsigned char *p, encoding; - unsigned int l, lsize; - long long value; + unsigned char *p; + zlentry entry; printf("{total bytes %d} {length %u}\n",ZIPLIST_BYTES(zl), ZIPLIST_LENGTH(zl)); p = ziplistHead(zl); while(*p != ZIP_END) { - l = zipDecodeLength(p,&lsize); - printf("{header %u, payload %u} ",lsize,l); - encoding = ZIP_ENCODING(p); - p += lsize; - if (encoding == ZIP_ENC_RAW) { - fwrite(p,l,1,stdout); + entry = zipEntry(p); + printf("{offset %ld, header %u, payload %u} ",p-zl,entry.headersize,entry.len); + p += entry.headersize; + if (entry.encoding == ZIP_ENC_RAW) { + fwrite(p,entry.len,1,stdout); } else { - printf("%lld", zipLoadInteger(p,encoding)); + printf("%lld", zipLoadInteger(p,entry.encoding)); } printf("\n"); - p += l; + p += entry.len; } printf("{end}\n\n"); } @@ -484,6 +562,14 @@ int main(int argc, char **argv) { printf("Pop head: %s (length %ld)\n", s, sdslen(s)); ziplistRepr(zl); + zl = ziplistPop(zl, &s, ZIPLIST_TAIL); + printf("Pop tail: %s (length %ld)\n", s, sdslen(s)); + ziplistRepr(zl); + + zl = ziplistPop(zl, &s, ZIPLIST_TAIL); + printf("Pop tail: %s (length %ld)\n", s, sdslen(s)); + ziplistRepr(zl); + printf("Iterate list from 0 to end:\n"); { zl = createList(); @@ -610,21 +696,21 @@ int main(int argc, char **argv) { zl = createList(); p = ziplistIndex(zl, 0); if (!ziplistCompare(p,"hello",5)) { - printf("ERROR\n"); + printf("ERROR: not \"hello\"\n"); return; } if (ziplistCompare(p,"hella",5)) { - printf("ERROR\n"); + printf("ERROR: \"hella\"\n"); return; } p = ziplistIndex(zl, 3); if (!ziplistCompare(p,"1024",4)) { - printf("ERROR\n"); + printf("ERROR: not \"1024\"\n"); return; } if (ziplistCompare(p,"1025",4)) { - printf("ERROR\n"); + printf("ERROR: \"1025\"\n"); return; } printf("SUCCESS\n");