X-Git-Url: https://git.saurik.com/redis.git/blobdiff_plain/dbaa41c618346be2ab58dfbab0a35e3ff1948ed1..e1f93d4b2cc94fec29ede9b3cedea891ee9bd050:/ziplist.c diff --git a/ziplist.c b/ziplist.c index 1354b4ea..d1d7a151 100644 --- a/ziplist.c +++ b/ziplist.c @@ -17,6 +17,7 @@ #include #include #include +#include #include #include #include "zmalloc.h" @@ -33,9 +34,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,15 +45,18 @@ #define ZIP_LEN_UINT32 2 /* Utility macros */ -#define ZIPLIST_BYTES(zl) (*((unsigned int*)(zl))) -#define ZIPLIST_TAIL_OFFSET(zl) (*((unsigned int*)((zl)+sizeof(unsigned int)))) -#define ZIPLIST_LENGTH(zl) (*((zl)+2*sizeof(unsigned int))) -#define ZIPLIST_HEADER_SIZE (2*sizeof(unsigned int)+1) -#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) +#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; @@ -63,13 +67,13 @@ typedef struct zlentry { } 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); } @@ -173,19 +177,19 @@ static int zipPrevLenByteDiff(unsigned char *p, unsigned int len) { /* 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(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(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; - } 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; @@ -194,38 +198,38 @@ static int zipTryEncoding(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); } @@ -269,7 +273,7 @@ static unsigned char *ziplistResize(unsigned char *zl, unsigned int len) { } /* Delete "num" entries, starting at "p". Returns pointer to the ziplist. */ -static unsigned char *__ziplistDelete(unsigned char *zl, unsigned char *p, int num) { +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); @@ -306,11 +310,11 @@ static unsigned char *__ziplistDelete(unsigned char *zl, unsigned char *p, int n } /* Insert item at "p". */ -static unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, char *s, unsigned int slen) { +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; + unsigned char encoding = ZIP_ENC_RAW; long long value; zlentry entry; @@ -372,7 +376,7 @@ static unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, char return zl; } -unsigned char *ziplistPush(unsigned char *zl, char *s, unsigned int slen, int where) { +unsigned char *ziplistPush(unsigned char *zl, unsigned char *s, unsigned int slen, int where) { unsigned char *p; p = (where == ZIPLIST_HEAD) ? ZIPLIST_ENTRY_HEAD(zl) : ZIPLIST_ENTRY_END(zl); return __ziplistInsert(zl,p,s,slen); @@ -428,21 +432,43 @@ unsigned char *ziplistIndex(unsigned char *zl, int index) { } /* Return pointer to next entry in ziplist. */ -unsigned char *ziplistNext(unsigned char *p) { - return (p[0] == ZIP_END) ? NULL : p+zipRawEntryLength(p); +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 pointer to previous entry in ziplist. */ -unsigned char *ziplistPrev(unsigned char *p) { - zlentry entry = zipEntry(p); - return (entry.prevrawlen == 0) ? NULL : p-entry.prevrawlen; +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, char **sstr, unsigned int *slen, long long *sval) { +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; @@ -451,7 +477,7 @@ unsigned int ziplistGet(unsigned char *p, char **sstr, unsigned int *slen, long if (entry.encoding == ZIP_ENC_RAW) { if (sstr) { *slen = entry.len; - *sstr = (char*)p+entry.headersize; + *sstr = p+entry.headersize; } } else { if (sval) { @@ -462,14 +488,14 @@ unsigned int ziplistGet(unsigned char *p, char **sstr, unsigned int *slen, long } /* Insert an entry at "p". */ -unsigned char *ziplistInsert(unsigned char *zl, unsigned char *p, char *s, unsigned int slen) { +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, int direction) { +unsigned char *ziplistDelete(unsigned char *zl, unsigned char **p) { unsigned int offset = *p-zl; zl = __ziplistDelete(zl,*p,1); @@ -477,11 +503,7 @@ unsigned char *ziplistDelete(unsigned char *zl, unsigned char **p, int direction * 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. */ - if (*(zl+offset) == ZIP_END && direction == ZIPLIST_HEAD) { - *p = ZIPLIST_ENTRY_TAIL(zl); - } else { - *p = zl+offset; - } + *p = zl+offset; return zl; } @@ -492,10 +514,10 @@ unsigned char *ziplistDeleteRange(unsigned char *zl, unsigned int index, unsigne } /* Compare entry pointer to by 'p' with 'entry'. Return 1 if equal. */ -unsigned int ziplistCompare(unsigned char *p, char *sstr, unsigned int slen) { +unsigned int ziplistCompare(unsigned char *p, unsigned char *sstr, unsigned int slen) { zlentry entry; - char sencoding; - long long val, sval; + unsigned char sencoding; + long long zval, sval; if (p[0] == ZIP_END) return 0; entry = zipEntry(p); @@ -510,8 +532,8 @@ unsigned int ziplistCompare(unsigned char *p, char *sstr, unsigned int slen) { /* Try to compare encoded values */ if (zipTryEncoding(sstr,&sval,&sencoding)) { if (entry.encoding == sencoding) { - val = zipLoadInteger(p+entry.headersize,entry.encoding); - return val == sval; + zval = zipLoadInteger(p+entry.headersize,entry.encoding); + return zval == sval; } } } @@ -521,7 +543,7 @@ unsigned int ziplistCompare(unsigned char *p, char *sstr, unsigned int slen) { /* 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; @@ -531,7 +553,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; } @@ -563,13 +585,14 @@ void ziplistRepr(unsigned char *zl) { } #ifdef ZIPLIST_TEST_MAIN +#include unsigned char *createList() { unsigned char *zl = ziplistNew(); - zl = ziplistPush(zl, "foo", 3, ZIPLIST_TAIL); - zl = ziplistPush(zl, "quux", 4, ZIPLIST_TAIL); - zl = ziplistPush(zl, "hello", 5, ZIPLIST_HEAD); - zl = ziplistPush(zl, "1024", 4, ZIPLIST_TAIL); + zl = ziplistPush(zl, (unsigned char*)"foo", 3, ZIPLIST_TAIL); + zl = ziplistPush(zl, (unsigned char*)"quux", 4, ZIPLIST_TAIL); + zl = ziplistPush(zl, (unsigned char*)"hello", 5, ZIPLIST_HEAD); + zl = ziplistPush(zl, (unsigned char*)"1024", 4, ZIPLIST_TAIL); return zl; } @@ -578,23 +601,52 @@ 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); + } +} + int main(int argc, char **argv) { unsigned char *zl, *p; - char *entry; + unsigned char *entry; unsigned int elen; long long value; sds s; @@ -709,7 +761,7 @@ int main(int argc, char **argv) { } else { printf("%lld", value); } - p = ziplistNext(p); + p = ziplistNext(zl,p); printf("\n"); } printf("\n"); @@ -726,7 +778,7 @@ int main(int argc, char **argv) { } else { printf("%lld", value); } - p = ziplistNext(p); + p = ziplistNext(zl,p); printf("\n"); } printf("\n"); @@ -743,7 +795,7 @@ int main(int argc, char **argv) { } else { printf("%lld", value); } - p = ziplistNext(p); + p = ziplistNext(zl,p); printf("\n"); } printf("\n"); @@ -772,7 +824,7 @@ int main(int argc, char **argv) { } else { printf("%lld", value); } - p = ziplistPrev(p); + p = ziplistPrev(zl,p); printf("\n"); } printf("\n"); @@ -789,7 +841,8 @@ int main(int argc, char **argv) { } else { printf("%lld", value); } - zl = ziplistDelete(zl, &p, ZIPLIST_HEAD); + zl = ziplistDelete(zl,&p); + p = ziplistPrev(zl,p); printf("\n"); } printf("\n"); @@ -833,19 +886,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, ZIPLIST_TAIL); + 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"); } } @@ -860,7 +913,7 @@ int main(int argc, char **argv) { int i,len; for (i = 0; i < 1000; i++) { len = sprintf(buf,"%d",i); - zl = ziplistPush(zl,buf,len,ZIPLIST_TAIL); + zl = ziplistPush(zl,(unsigned char*)buf,len,ZIPLIST_TAIL); } for (i = 0; i < 1000; i++) { p = ziplistIndex(zl,i); @@ -877,28 +930,35 @@ int main(int argc, char **argv) { 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 1; } - if (ziplistCompare(p,"hella",5)) { + if (ziplistCompare(p,(unsigned char*)"hella",5)) { printf("ERROR: \"hella\"\n"); 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 1; } - if (ziplistCompare(p,"1025",4)) { + if (ziplistCompare(p,(unsigned char*)"1025",4)) { printf("ERROR: \"1025\"\n"); 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