X-Git-Url: https://git.saurik.com/redis.git/blobdiff_plain/dcb9cf4e8213744e431f38722d04b841f78b316c..b8b8501d70770465adc67d4effb4dbae2899f3a8:/ziplist.c diff --git a/ziplist.c b/ziplist.c index adb7d054..4b9d0fad 100644 --- a/ziplist.c +++ b/ziplist.c @@ -17,10 +17,10 @@ #include #include #include +#include #include #include #include "zmalloc.h" -#include "sds.h" #include "ziplist.h" /* Important note: the ZIP_END value is used to depict the end of the @@ -33,9 +33,9 @@ /* Entry encoding */ #define ZIP_ENC_RAW 0 -#define ZIP_ENC_SHORT 1 -#define ZIP_ENC_INT 2 -#define ZIP_ENC_LLONG 3 +#define ZIP_ENC_INT16 1 +#define ZIP_ENC_INT32 2 +#define ZIP_ENC_INT64 3 #define ZIP_ENCODING(p) ((p)[0] >> 6) /* Length encoding for raw entries */ @@ -44,21 +44,35 @@ #define ZIP_LEN_UINT32 2 /* Utility macros */ -#define ZIPLIST_BYTES(zl) (*((unsigned int*)(zl))) -#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_BYTES(zl) (*((uint32_t*)(zl))) +#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t)))) +#define ZIPLIST_LENGTH(zl) (*((uint16_t*)((zl)+sizeof(uint32_t)*2))) +#define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t)) +#define ZIPLIST_ENTRY_HEAD(zl) ((zl)+ZIPLIST_HEADER_SIZE) +#define ZIPLIST_ENTRY_TAIL(zl) ((zl)+ZIPLIST_TAIL_OFFSET(zl)) +#define ZIPLIST_ENTRY_END(zl) ((zl)+ZIPLIST_BYTES(zl)-1) + +/* We know a positive increment can only be 1 because entries can only be + * pushed one at a time. */ #define ZIPLIST_INCR_LENGTH(zl,incr) { \ - if (ZIPLIST_LENGTH(zl) < ZIP_BIGLEN) ZIPLIST_LENGTH(zl)+=incr; } + if (ZIPLIST_LENGTH(zl) < UINT16_MAX) 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) { - return sizeof(short int); - } else if (encoding == ZIP_ENC_INT) { - return sizeof(int); - } else if (encoding == ZIP_ENC_LLONG) { - return sizeof(long long); +static unsigned int zipEncodingSize(unsigned char encoding) { + if (encoding == ZIP_ENC_INT16) { + return sizeof(int16_t); + } else if (encoding == ZIP_ENC_INT32) { + return sizeof(int32_t); + } else if (encoding == ZIP_ENC_INT64) { + return sizeof(int64_t); } assert(NULL); } @@ -122,30 +136,59 @@ static unsigned int zipEncodeLength(unsigned char *p, char encoding, unsigned in return len; } +/* Decode the length of the previous element stored at "p". */ +static unsigned int zipPrevDecodeLength(unsigned char *p, unsigned int *lensize) { + unsigned int len = *p; + if (len < ZIP_BIGLEN) { + if (lensize) *lensize = 1; + } else { + if (lensize) *lensize = 1+sizeof(len); + memcpy(&len,p+1,sizeof(len)); + } + return len; +} + +/* Encode the length of the previous entry and write it to "p". Return the + * number of bytes needed to encode this length if "p" is NULL. */ +static unsigned int zipPrevEncodeLength(unsigned char *p, unsigned int len) { + if (p == NULL) { + return (len < ZIP_BIGLEN) ? 1 : sizeof(len)+1; + } else { + if (len < ZIP_BIGLEN) { + p[0] = len; + return 1; + } else { + p[0] = ZIP_BIGLEN; + memcpy(p+1,&len,sizeof(len)); + return 1+sizeof(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; + zipPrevDecodeLength(p,&prevlensize); + return zipPrevEncodeLength(NULL,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! */ -static int zipTryEncoding(unsigned char *entry, long long *v, char *encoding) { +static int zipTryEncoding(unsigned char *entry, long long *v, unsigned char *encoding) { long long value; char *eptr; if (entry[0] == '-' || (entry[0] >= '0' && entry[0] <= '9')) { value = strtoll((char*)entry,&eptr,10); if (eptr[0] != '\0') return 0; - if (value >= SHRT_MIN && value <= SHRT_MAX) { - *encoding = ZIP_ENC_SHORT; - } else if (value >= INT_MIN && value <= INT_MAX) { - *encoding = ZIP_ENC_INT; + if (value >= INT16_MIN && value <= INT16_MAX) { + *encoding = ZIP_ENC_INT16; + } else if (value >= INT32_MIN && value <= INT32_MAX) { + *encoding = ZIP_ENC_INT32; } else { - *encoding = ZIP_ENC_LLONG; + *encoding = ZIP_ENC_INT64; } *v = value; return 1; @@ -154,52 +197,59 @@ static int zipTryEncoding(unsigned char *entry, long long *v, char *encoding) { } /* Store integer 'value' at 'p', encoded as 'encoding' */ -static void zipSaveInteger(unsigned char *p, long long value, char encoding) { - short int s; - int i; - long long l; - if (encoding == ZIP_ENC_SHORT) { - s = value; - memcpy(p,&s,sizeof(s)); - } else if (encoding == ZIP_ENC_INT) { - i = value; - memcpy(p,&i,sizeof(i)); - } else if (encoding == ZIP_ENC_LLONG) { - l = value; - memcpy(p,&l,sizeof(l)); +static void zipSaveInteger(unsigned char *p, int64_t value, unsigned char encoding) { + int16_t i16; + int32_t i32; + int64_t i64; + if (encoding == ZIP_ENC_INT16) { + i16 = value; + memcpy(p,&i16,sizeof(i16)); + } else if (encoding == ZIP_ENC_INT32) { + i32 = value; + memcpy(p,&i32,sizeof(i32)); + } else if (encoding == ZIP_ENC_INT64) { + i64 = value; + memcpy(p,&i64,sizeof(i64)); } else { assert(NULL); } } /* Read integer encoded as 'encoding' from 'p' */ -static long long zipLoadInteger(unsigned char *p, char encoding) { - short int s; - int i; - long long l, ret; - if (encoding == ZIP_ENC_SHORT) { - memcpy(&s,p,sizeof(s)); - ret = s; - } else if (encoding == ZIP_ENC_INT) { - memcpy(&i,p,sizeof(i)); - ret = i; - } else if (encoding == ZIP_ENC_LLONG) { - memcpy(&l,p,sizeof(l)); - ret = l; +static int64_t zipLoadInteger(unsigned char *p, unsigned char encoding) { + int16_t i16; + int32_t i32; + int64_t i64, ret; + if (encoding == ZIP_ENC_INT16) { + memcpy(&i16,p,sizeof(i16)); + ret = i16; + } else if (encoding == ZIP_ENC_INT32) { + memcpy(&i32,p,sizeof(i32)); + ret = i32; + } else if (encoding == ZIP_ENC_INT64) { + memcpy(&i64,p,sizeof(i64)); + ret = i64; } else { assert(NULL); } 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 = zipPrevDecodeLength(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 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. */ @@ -221,243 +271,245 @@ static unsigned char *ziplistResize(unsigned char *zl, unsigned int len) { return zl; } -static unsigned char *ziplistHead(unsigned char *zl) { - return zl+ZIPLIST_HEADER_SIZE; -} - -static unsigned char *ziplistTail(unsigned char *zl) { - unsigned char *p, *q; - p = q = ziplistHead(zl); - while (*p != ZIP_END) { - q = p; +/* Delete "num" entries, starting at "p". Returns pointer to the ziplist. */ +static unsigned char *__ziplistDelete(unsigned char *zl, unsigned char *p, unsigned 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++; } - return q; + + 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); + zipPrevEncodeLength(p-nextdiff,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; - char encoding = ZIP_ENC_RAW; +/* 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; + unsigned 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 = ZIPLIST_ENTRY_TAIL(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 += zipPrevEncodeLength(NULL,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. */ + zipPrevEncodeLength(p+reqlen,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 += zipPrevEncodeLength(p,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 *ziplistPop(unsigned char *zl, sds *target, int where) { - unsigned int curlen = ZIPLIST_BYTES(zl), rawlen; - unsigned int prevrawlensize, prevrawlen, lensize, len, headerlen; - int nextdiff = 0; - unsigned char encoding; +unsigned char *ziplistPush(unsigned char *zl, unsigned char *s, unsigned int slen, int where) { unsigned char *p; - long long value; - if (target) *target = NULL; - - /* Get pointer to element to remove */ - p = (where == ZIPLIST_HEAD) ? ziplistHead(zl) : ziplistTail(zl); - if (*p == ZIP_END) return zl; - - prevrawlen = zipDecodeLength(p,&prevrawlensize); - len = zipDecodeLength(p+prevrawlensize,&lensize); - headerlen = prevrawlensize+lensize; - rawlen = headerlen+len; - if (target) { - encoding = ZIP_ENCODING(p+prevrawlensize); - if (encoding == ZIP_ENC_RAW) { - *target = sdsnewlen(p+headerlen,len); - } else { - value = zipLoadInteger(p+headerlen,encoding); - *target = sdscatprintf(sdsempty(), "%lld", value); - } - } + p = (where == ZIPLIST_HEAD) ? ZIPLIST_ENTRY_HEAD(zl) : ZIPLIST_ENTRY_END(zl); + return __ziplistInsert(zl,p,s,slen); +} - 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); +/* Returns an offset to use for iterating with ziplistNext. When the given + * index is negative, the list is traversed back to front. When the list + * doesn't contain an element at the provided index, NULL is returned. */ +unsigned char *ziplistIndex(unsigned char *zl, int index) { + unsigned char *p; + zlentry entry; + if (index < 0) { + index = (-index)-1; + p = ZIPLIST_ENTRY_TAIL(zl); + if (p[0] != ZIP_END) { + entry = zipEntry(p); + while (entry.prevrawlen > 0 && index--) { + p -= entry.prevrawlen; + entry = zipEntry(p); + } } - /* 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) -= prevrawlen; + p = ZIPLIST_ENTRY_HEAD(zl); + while (p[0] != ZIP_END && index--) { + p += zipRawEntryLength(p); + } } - - /* Resize and update length */ - zl = ziplistResize(zl,curlen-rawlen+nextdiff); - ZIPLIST_INCR_LENGTH(zl,-1); - return zl; + return (p[0] == ZIP_END || index > 0) ? NULL : p; } -/* Returns an offset to use for iterating with ziplistNext. */ -unsigned char *ziplistIndex(unsigned char *zl, unsigned int index) { - unsigned char *p = zl+ZIPLIST_HEADER_SIZE; - unsigned int i = 0; - for (; i < index; i++) { - if (*p == ZIP_END) break; - p += zipRawEntryLength(p); +/* Return pointer to next entry in ziplist. */ +unsigned char *ziplistNext(unsigned char *zl, unsigned char *p) { + ((void) zl); + + /* "p" could be equal to ZIP_END, caused by ziplistDelete, + * and we should return NULL. Otherwise, we should return NULL + * when the *next* element is ZIP_END (there is no next entry). */ + if (p[0] == ZIP_END) { + return NULL; + } else { + p = p+zipRawEntryLength(p); + return (p[0] == ZIP_END) ? NULL : p; } - return p; } -/* Return pointer to next entry in ziplist. */ -unsigned char *ziplistNext(unsigned char *p) { - return *p == ZIP_END ? p : p+zipRawEntryLength(p); +/* Return pointer to previous entry in ziplist. */ +unsigned char *ziplistPrev(unsigned char *zl, unsigned char *p) { + zlentry entry; + + /* Iterating backwards from ZIP_END should return the tail. When "p" is + * equal to the first element of the list, we're already at the head, + * and should return NULL. */ + if (p[0] == ZIP_END) { + p = ZIPLIST_ENTRY_TAIL(zl); + return (p[0] == ZIP_END) ? NULL : p; + } else if (p == ZIPLIST_ENTRY_HEAD(zl)) { + return NULL; + } else { + entry = zipEntry(p); + return p-entry.prevrawlen; + } } /* Get entry pointer to by 'p' and store in either 'e' or 'v' depending * 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 prevrawlensize, lensize, len, headerlen; - if (*p == ZIP_END) return 0; - if (e) *e = NULL; - - zipDecodeLength(p,&prevrawlensize); - len = zipDecodeLength(p+prevrawlensize,&lensize); - headerlen = prevrawlensize+lensize; - if (ZIP_ENCODING(p+prevrawlensize) == ZIP_ENC_RAW) { - if (e) { - *elen = len; - *e = p+headerlen; +unsigned int ziplistGet(unsigned char *p, unsigned char **sstr, unsigned int *slen, long long *sval) { + zlentry entry; + if (p == NULL || p[0] == ZIP_END) return 0; + 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+headerlen,ZIP_ENCODING(p+prevrawlensize)); + if (sval) { + *sval = zipLoadInteger(p+entry.headersize,entry.encoding); } } return 1; } -/* 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; +/* Insert an entry at "p". */ +unsigned char *ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) { + return __ziplistInsert(zl,p,s,slen); } /* 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. + * When the delete direction is back to front, we might delete the last + * entry and end up with "p" pointing to ZIP_END, so check this. */ *p = zl+offset; return zl; } +/* Delete a range of entries from the ziplist. */ +unsigned char *ziplistDeleteRange(unsigned char *zl, unsigned int index, unsigned int num) { + unsigned char *p = ziplistIndex(zl,index); + return (p == NULL) ? zl : __ziplistDelete(zl,p,num); +} + /* 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 prevrawlensize, lensize, len, headerlen; - char encoding; - long long val, eval; - if (*p == ZIP_END) return 0; - - zipDecodeLength(p,&prevrawlensize); - len = zipDecodeLength(p+prevrawlensize,&lensize); - headerlen = prevrawlensize+lensize; - if (ZIP_ENCODING(p+prevrawlensize) == ZIP_ENC_RAW) { +unsigned int ziplistCompare(unsigned char *p, unsigned char *sstr, unsigned int slen) { + zlentry entry; + unsigned char sencoding; + long long zval, sval; + if (p[0] == ZIP_END) return 0; + + entry = zipEntry(p); + if (entry.encoding == ZIP_ENC_RAW) { /* Raw compare */ - if (len == elen) { - return memcmp(p+headerlen,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 */ - val = zipLoadInteger(p+headerlen,ZIP_ENCODING(p+prevrawlensize)); - return val == 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) { + zval = zipLoadInteger(p+entry.headersize,entry.encoding); + return zval == sval; + } } } return 0; @@ -466,7 +518,7 @@ unsigned int ziplistCompare(unsigned char *p, unsigned char *entry, unsigned int /* Return length of ziplist. */ unsigned int ziplistLen(unsigned char *zl) { unsigned int len = 0; - if (ZIPLIST_LENGTH(zl) < ZIP_BIGLEN) { + if (ZIPLIST_LENGTH(zl) < UINT16_MAX) { len = ZIPLIST_LENGTH(zl); } else { unsigned char *p = zl+ZIPLIST_HEADER_SIZE; @@ -476,7 +528,7 @@ unsigned int ziplistLen(unsigned char *zl) { } /* Re-store length if small enough */ - if (len < ZIP_BIGLEN) ZIPLIST_LENGTH(zl) = len; + if (len < UINT16_MAX) ZIPLIST_LENGTH(zl) = len; } return len; } @@ -487,29 +539,28 @@ unsigned int ziplistSize(unsigned char *zl) { } void ziplistRepr(unsigned char *zl) { - unsigned char *p, encoding; - unsigned int prevrawlensize, prevrawlen, lensize, len; + unsigned char *p; + zlentry entry; printf("{total bytes %d} {length %u}\n",ZIPLIST_BYTES(zl), ZIPLIST_LENGTH(zl)); - p = ziplistHead(zl); + p = ZIPLIST_ENTRY_HEAD(zl); while(*p != ZIP_END) { - prevrawlen = zipDecodeLength(p,&prevrawlensize); - len = zipDecodeLength(p+prevrawlensize,&lensize); - printf("{offset %ld, header %u, payload %u} ",p-zl,prevrawlensize+lensize,len); - encoding = ZIP_ENCODING(p+prevrawlensize); - p += prevrawlensize+lensize; - if (encoding == ZIP_ENC_RAW) { - fwrite(p,len,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 += len; + p += entry.len; } printf("{end}\n\n"); } #ifdef ZIPLIST_TEST_MAIN +#include unsigned char *createList() { unsigned char *zl = ziplistNew(); @@ -525,25 +576,79 @@ unsigned char *createIntList() { char buf[32]; sprintf(buf, "100"); - zl = ziplistPush(zl, buf, strlen(buf), ZIPLIST_TAIL); + zl = ziplistPush(zl, (unsigned char*)buf, strlen(buf), ZIPLIST_TAIL); sprintf(buf, "128000"); - zl = ziplistPush(zl, buf, strlen(buf), ZIPLIST_TAIL); + zl = ziplistPush(zl, (unsigned char*)buf, strlen(buf), ZIPLIST_TAIL); sprintf(buf, "-100"); - zl = ziplistPush(zl, buf, strlen(buf), ZIPLIST_HEAD); + zl = ziplistPush(zl, (unsigned char*)buf, strlen(buf), ZIPLIST_HEAD); sprintf(buf, "4294967296"); - zl = ziplistPush(zl, buf, strlen(buf), ZIPLIST_HEAD); + zl = ziplistPush(zl, (unsigned char*)buf, strlen(buf), ZIPLIST_HEAD); sprintf(buf, "non integer"); - zl = ziplistPush(zl, buf, strlen(buf), ZIPLIST_TAIL); + zl = ziplistPush(zl, (unsigned char*)buf, strlen(buf), ZIPLIST_TAIL); sprintf(buf, "much much longer non integer"); - zl = ziplistPush(zl, buf, strlen(buf), ZIPLIST_TAIL); + zl = ziplistPush(zl, (unsigned char*)buf, strlen(buf), ZIPLIST_TAIL); return zl; } +long long usec(void) { + struct timeval tv; + gettimeofday(&tv,NULL); + return (((long long)tv.tv_sec)*1000000)+tv.tv_usec; +} + +void stress(int pos, int num, int maxsize, int dnum) { + int i,j,k; + unsigned char *zl; + char posstr[2][5] = { "HEAD", "TAIL" }; + long long start; + for (i = 0; i < maxsize; i+=dnum) { + zl = ziplistNew(); + for (j = 0; j < i; j++) { + zl = ziplistPush(zl,(unsigned char*)"quux",4,ZIPLIST_TAIL); + } + + /* Do num times a push+pop from pos */ + start = usec(); + for (k = 0; k < num; k++) { + zl = ziplistPush(zl,(unsigned char*)"quux",4,pos); + zl = ziplistDeleteRange(zl,0,1); + } + printf("List size: %8d, bytes: %8d, %dx push+pop (%s): %6lld usec\n", + i,ZIPLIST_BYTES(zl),num,posstr[pos],usec()-start); + zfree(zl); + } +} + +void pop(unsigned char *zl, int where) { + unsigned char *p, *vstr; + unsigned int vlen; + long long vlong; + + p = ziplistIndex(zl,where == ZIPLIST_HEAD ? 0 : -1); + if (ziplistGet(p,&vstr,&vlen,&vlong)) { + if (where == ZIPLIST_HEAD) + printf("Pop head: "); + else + printf("Pop tail: "); + + if (vstr) + fwrite(vstr,vlen,1,stdout); + else + printf("%lld", vlong); + + printf("\n"); + ziplistDeleteRange(zl,-1,1); + } else { + printf("ERROR: Could not pop\n"); + exit(1); + } +} + int main(int argc, char **argv) { - unsigned char *zl, *p, *q, *entry; + unsigned char *zl, *p; + unsigned char *entry; unsigned int elen; long long value; - sds s; zl = createIntList(); ziplistRepr(zl); @@ -551,22 +656,95 @@ int main(int argc, char **argv) { zl = createList(); ziplistRepr(zl); - zl = ziplistPop(zl, &s, ZIPLIST_TAIL); - printf("Pop tail: %s (length %ld)\n", s, sdslen(s)); + pop(zl,ZIPLIST_TAIL); ziplistRepr(zl); - zl = ziplistPop(zl, &s, ZIPLIST_HEAD); - printf("Pop head: %s (length %ld)\n", s, sdslen(s)); + pop(zl,ZIPLIST_HEAD); ziplistRepr(zl); - zl = ziplistPop(zl, &s, ZIPLIST_TAIL); - printf("Pop tail: %s (length %ld)\n", s, sdslen(s)); + pop(zl,ZIPLIST_TAIL); ziplistRepr(zl); - zl = ziplistPop(zl, &s, ZIPLIST_TAIL); - printf("Pop tail: %s (length %ld)\n", s, sdslen(s)); + pop(zl,ZIPLIST_TAIL); ziplistRepr(zl); + printf("Get element at index 3:\n"); + { + zl = createList(); + p = ziplistIndex(zl, 3); + if (!ziplistGet(p, &entry, &elen, &value)) { + printf("ERROR: Could not access index 3\n"); + return 1; + } + if (entry) { + fwrite(entry,elen,1,stdout); + printf("\n"); + } else { + printf("%lld\n", value); + } + printf("\n"); + } + + printf("Get element at index 4 (out of range):\n"); + { + zl = createList(); + p = ziplistIndex(zl, 4); + if (p == NULL) { + printf("No entry\n"); + } else { + printf("ERROR: Out of range index should return NULL, returned offset: %ld\n", p-zl); + return 1; + } + printf("\n"); + } + + printf("Get element at index -1 (last element):\n"); + { + zl = createList(); + p = ziplistIndex(zl, -1); + if (!ziplistGet(p, &entry, &elen, &value)) { + printf("ERROR: Could not access index -1\n"); + return 1; + } + if (entry) { + fwrite(entry,elen,1,stdout); + printf("\n"); + } else { + printf("%lld\n", value); + } + printf("\n"); + } + + printf("Get element at index -4 (first element):\n"); + { + zl = createList(); + p = ziplistIndex(zl, -4); + if (!ziplistGet(p, &entry, &elen, &value)) { + printf("ERROR: Could not access index -4\n"); + return 1; + } + if (entry) { + fwrite(entry,elen,1,stdout); + printf("\n"); + } else { + printf("%lld\n", value); + } + printf("\n"); + } + + printf("Get element at index -5 (reverse out of range):\n"); + { + zl = createList(); + p = ziplistIndex(zl, -5); + if (p == NULL) { + printf("No entry\n"); + } else { + printf("ERROR: Out of range index should return NULL, returned offset: %ld\n", p-zl); + return 1; + } + printf("\n"); + } + printf("Iterate list from 0 to end:\n"); { zl = createList(); @@ -578,7 +756,7 @@ int main(int argc, char **argv) { } else { printf("%lld", value); } - p = ziplistNext(p); + p = ziplistNext(zl,p); printf("\n"); } printf("\n"); @@ -595,7 +773,7 @@ int main(int argc, char **argv) { } else { printf("%lld", value); } - p = ziplistNext(p); + p = ziplistNext(zl,p); printf("\n"); } printf("\n"); @@ -612,7 +790,7 @@ int main(int argc, char **argv) { } else { printf("%lld", value); } - p = ziplistNext(p); + p = ziplistNext(zl,p); printf("\n"); } printf("\n"); @@ -630,6 +808,41 @@ int main(int argc, char **argv) { printf("\n"); } + printf("Iterate from back to front:\n"); + { + zl = createList(); + p = ziplistIndex(zl, -1); + while (ziplistGet(p, &entry, &elen, &value)) { + printf("Entry: "); + if (entry) { + fwrite(entry,elen,1,stdout); + } else { + printf("%lld", value); + } + p = ziplistPrev(zl,p); + printf("\n"); + } + printf("\n"); + } + + printf("Iterate from back to front, deleting all items:\n"); + { + zl = createList(); + p = ziplistIndex(zl, -1); + while (ziplistGet(p, &entry, &elen, &value)) { + printf("Entry: "); + if (entry) { + fwrite(entry,elen,1,stdout); + } else { + printf("%lld", value); + } + zl = ziplistDelete(zl,&p); + p = ziplistPrev(zl,p); + printf("\n"); + } + printf("\n"); + } + printf("Delete inclusive range 0,0:\n"); { zl = createList(); @@ -668,19 +881,19 @@ int main(int argc, char **argv) { printf("Delete foo while iterating:\n"); { zl = createList(); - p = ziplistIndex(zl, 0); - while (ziplistGet(p, &entry, &elen, &value)) { - if (entry && strncmp("foo", entry, elen) == 0) { + p = ziplistIndex(zl,0); + while (ziplistGet(p,&entry,&elen,&value)) { + if (entry && strncmp("foo",(char*)entry,elen) == 0) { printf("Delete foo\n"); - zl = ziplistDelete(zl, &p); + zl = ziplistDelete(zl,&p); } else { printf("Entry: "); if (entry) { fwrite(entry,elen,1,stdout); } else { - printf("%lld", value); + printf("%lld",value); } - p = ziplistNext(p); + p = ziplistNext(zl,p); printf("\n"); } } @@ -688,31 +901,59 @@ int main(int argc, char **argv) { ziplistRepr(zl); } + printf("Create long list and check indices:\n"); + { + zl = ziplistNew(); + char buf[32]; + int i,len; + for (i = 0; i < 1000; i++) { + len = sprintf(buf,"%d",i); + zl = ziplistPush(zl,(unsigned char*)buf,len,ZIPLIST_TAIL); + } + for (i = 0; i < 1000; i++) { + p = ziplistIndex(zl,i); + assert(ziplistGet(p,NULL,NULL,&value)); + assert(i == value); + + p = ziplistIndex(zl,-i-1); + assert(ziplistGet(p,NULL,NULL,&value)); + assert(999-i == value); + } + printf("SUCCESS\n\n"); + } + printf("Compare strings with ziplist entries:\n"); { zl = createList(); - p = ziplistIndex(zl, 0); - if (!ziplistCompare(p,"hello",5)) { + p = ziplistIndex(zl,0); + if (!ziplistCompare(p,(unsigned char*)"hello",5)) { printf("ERROR: not \"hello\"\n"); - return; + return 1; } - if (ziplistCompare(p,"hella",5)) { + if (ziplistCompare(p,(unsigned char*)"hella",5)) { printf("ERROR: \"hella\"\n"); - return; + return 1; } - p = ziplistIndex(zl, 3); - if (!ziplistCompare(p,"1024",4)) { + p = ziplistIndex(zl,3); + if (!ziplistCompare(p,(unsigned char*)"1024",4)) { printf("ERROR: not \"1024\"\n"); - return; + return 1; } - if (ziplistCompare(p,"1025",4)) { + if (ziplistCompare(p,(unsigned char*)"1025",4)) { printf("ERROR: \"1025\"\n"); - return; + return 1; } printf("SUCCESS\n"); } + printf("Stress with variable ziplist size:\n"); + { + stress(ZIPLIST_HEAD,100000,16384,256); + stress(ZIPLIST_TAIL,100000,16384,256); + } + return 0; } + #endif