X-Git-Url: https://git.saurik.com/redis.git/blobdiff_plain/177a0a0b0d66ca5d25cf3d06907292e8c02f1825..6ddc908ab611b1d6f1c94c71497e181734ac53df:/ziplist.c diff --git a/ziplist.c b/ziplist.c index 48ec2a34..433032e6 100644 --- a/ziplist.c +++ b/ziplist.c @@ -45,7 +45,7 @@ /* Utility macros */ #define ZIPLIST_BYTES(zl) (*((unsigned int*)(zl))) -#define ZIPLIST_TAIL_OFFSET(zl) (*((zl)+sizeof(unsigned int))) +#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) @@ -63,7 +63,7 @@ typedef struct zlentry { } zlentry; /* Return bytes needed to store integer encoded by 'encoding' */ -static unsigned int zipEncodingSize(char encoding) { +static unsigned int zipEncodingSize(unsigned char encoding) { if (encoding == ZIP_ENC_SHORT) { return sizeof(short int); } else if (encoding == ZIP_ENC_INT) { @@ -173,12 +173,12 @@ 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; @@ -194,7 +194,7 @@ 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) { +static void zipSaveInteger(unsigned char *p, long long value, unsigned char encoding) { short int s; int i; long long l; @@ -213,7 +213,7 @@ static void zipSaveInteger(unsigned char *p, long long value, char encoding) { } /* Read integer encoded as 'encoding' from 'p' */ -static long long zipLoadInteger(unsigned char *p, char encoding) { +static long long zipLoadInteger(unsigned char *p, unsigned char encoding) { short int s; int i; long long l, ret; @@ -269,7 +269,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 +306,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 +372,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,15 +428,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 *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; @@ -445,7 +473,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) { @@ -455,10 +483,9 @@ unsigned int ziplistGet(unsigned char *p, char **sstr, unsigned int *slen, long 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 = ziplistIndex(zl,index); - return p == NULL ? zl : __ziplistDelete(zl,p,num); +/* 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. @@ -469,16 +496,24 @@ unsigned char *ziplistDelete(unsigned char *zl, unsigned char **p) { zl = __ziplistDelete(zl,*p,1); /* Store pointer to current element in p, because ziplistDelete will - * do a realloc which might result in a different "zl"-pointer. */ + * 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, 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); @@ -493,8 +528,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; } } } @@ -692,7 +727,7 @@ int main(int argc, char **argv) { } else { printf("%lld", value); } - p = ziplistNext(p); + p = ziplistNext(zl,p); printf("\n"); } printf("\n"); @@ -709,7 +744,7 @@ int main(int argc, char **argv) { } else { printf("%lld", value); } - p = ziplistNext(p); + p = ziplistNext(zl,p); printf("\n"); } printf("\n"); @@ -726,7 +761,7 @@ int main(int argc, char **argv) { } else { printf("%lld", value); } - p = ziplistNext(p); + p = ziplistNext(zl,p); printf("\n"); } printf("\n"); @@ -744,6 +779,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(); @@ -786,7 +856,7 @@ int main(int argc, char **argv) { while (ziplistGet(p, &entry, &elen, &value)) { if (entry && strncmp("foo", entry, elen) == 0) { printf("Delete foo\n"); - zl = ziplistDelete(zl, &p); + zl = ziplistDelete(zl, &p, ZIPLIST_TAIL); } else { printf("Entry: "); if (entry) { @@ -802,6 +872,27 @@ 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,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();