X-Git-Url: https://git.saurik.com/redis.git/blobdiff_plain/b0d605c1d6bbf5746cc957946138108b928c88a1..67b0b41c879d01a35b1fcdab88b7e70f95a3232c:/src/ziplist.c diff --git a/src/ziplist.c b/src/ziplist.c index 4f44bd58..a1a63478 100644 --- a/src/ziplist.c +++ b/src/ziplist.c @@ -409,6 +409,7 @@ static unsigned char *__ziplistCascadeUpdate(unsigned char *zl, unsigned char *p /* Advance the cursor */ p += rawlen; + curlen += extra; } else { if (next.prevrawlensize > rawlensize) { /* This would result in shrinking, which we want to avoid. @@ -594,7 +595,12 @@ unsigned char *ziplistIndex(unsigned char *zl, int index) { return (p[0] == ZIP_END || index > 0) ? NULL : p; } -/* Return pointer to next entry in ziplist. */ +/* Return pointer to next entry in ziplist. + * + * zl is the pointer to the ziplist + * p is the pointer to the current element + * + * The element after 'p' is returned, otherwise NULL if we are at the end. */ unsigned char *ziplistNext(unsigned char *zl, unsigned char *p) { ((void) zl); @@ -753,9 +759,9 @@ void ziplistRepr(unsigned char *zl) { "pls: %2u, " "payload %5u" "} ", - (long unsigned int)p, + (long unsigned)p, index, - p-zl, + (unsigned long) (p-zl), entry.headersize+entry.len, entry.headersize, entry.prevrawlen, @@ -764,10 +770,11 @@ void ziplistRepr(unsigned char *zl) { p += entry.headersize; if (ZIP_IS_STR(entry.encoding)) { if (entry.len > 40) { - fwrite(p,40,1,stdout); + if (fwrite(p,40,1,stdout) == 0) perror("fwrite"); printf("..."); } else { - fwrite(p,entry.len,1,stdout); + if (entry.len && + fwrite(p,entry.len,1,stdout) == 0) perror("fwrite"); } } else { printf("%lld", (long long) zipLoadInteger(p,entry.encoding)); @@ -781,6 +788,10 @@ void ziplistRepr(unsigned char *zl) { #ifdef ZIPLIST_TEST_MAIN #include +#include "adlist.h" +#include "sds.h" + +#define debug(f, ...) { if (DEBUG) printf(f, __VA_ARGS__); } unsigned char *createList() { unsigned char *zl = ziplistNew(); @@ -852,7 +863,7 @@ void pop(unsigned char *zl, int where) { printf("Pop tail: "); if (vstr) - fwrite(vstr,vlen,1,stdout); + if (vlen && fwrite(vstr,vlen,1,stdout) == 0) perror("fwrite"); else printf("%lld", vlong); @@ -864,6 +875,32 @@ void pop(unsigned char *zl, int where) { } } +void randstring(char *target, unsigned int min, unsigned int max) { + int p, len = min+rand()%(max-min+1); + int minval, maxval; + switch(rand() % 3) { + case 0: + minval = 0; + maxval = 255; + break; + case 1: + minval = 48; + maxval = 122; + break; + case 2: + minval = 48; + maxval = 52; + break; + default: + assert(NULL); + } + + while(p < len) + target[p++] = minval+rand()%(maxval-minval+1); + return; +} + + int main(int argc, char **argv) { unsigned char *zl, *p; unsigned char *entry; @@ -901,7 +938,7 @@ int main(int argc, char **argv) { return 1; } if (entry) { - fwrite(entry,elen,1,stdout); + if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite"); printf("\n"); } else { printf("%lld\n", value); @@ -931,7 +968,7 @@ int main(int argc, char **argv) { return 1; } if (entry) { - fwrite(entry,elen,1,stdout); + if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite"); printf("\n"); } else { printf("%lld\n", value); @@ -948,7 +985,7 @@ int main(int argc, char **argv) { return 1; } if (entry) { - fwrite(entry,elen,1,stdout); + if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite"); printf("\n"); } else { printf("%lld\n", value); @@ -976,7 +1013,7 @@ int main(int argc, char **argv) { while (ziplistGet(p, &entry, &elen, &value)) { printf("Entry: "); if (entry) { - fwrite(entry,elen,1,stdout); + if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite"); } else { printf("%lld", value); } @@ -993,7 +1030,7 @@ int main(int argc, char **argv) { while (ziplistGet(p, &entry, &elen, &value)) { printf("Entry: "); if (entry) { - fwrite(entry,elen,1,stdout); + if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite"); } else { printf("%lld", value); } @@ -1010,7 +1047,7 @@ int main(int argc, char **argv) { while (ziplistGet(p, &entry, &elen, &value)) { printf("Entry: "); if (entry) { - fwrite(entry,elen,1,stdout); + if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite"); } else { printf("%lld", value); } @@ -1039,7 +1076,7 @@ int main(int argc, char **argv) { while (ziplistGet(p, &entry, &elen, &value)) { printf("Entry: "); if (entry) { - fwrite(entry,elen,1,stdout); + if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite"); } else { printf("%lld", value); } @@ -1056,7 +1093,7 @@ int main(int argc, char **argv) { while (ziplistGet(p, &entry, &elen, &value)) { printf("Entry: "); if (entry) { - fwrite(entry,elen,1,stdout); + if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite"); } else { printf("%lld", value); } @@ -1113,7 +1150,8 @@ int main(int argc, char **argv) { } else { printf("Entry: "); if (entry) { - fwrite(entry,elen,1,stdout); + if (elen && fwrite(entry,elen,1,stdout) == 0) + perror("fwrite"); } else { printf("%lld",value); } @@ -1137,10 +1175,10 @@ int main(int argc, char **argv) { /* Pop values again and compare their value. */ p = ziplistIndex(zl,0); assert(ziplistGet(p,&entry,&elen,&value)); - assert(strncmp(v1,entry,elen) == 0); + assert(strncmp(v1,(char*)entry,elen) == 0); p = ziplistIndex(zl,1); assert(ziplistGet(p,&entry,&elen,&value)); - assert(strncmp(v2,entry,elen) == 0); + assert(strncmp(v2,(char*)entry,elen) == 0); printf("SUCCESS\n\n"); } @@ -1192,50 +1230,78 @@ int main(int argc, char **argv) { printf("Stress with random payloads of different encoding:\n"); { - int i, idx, where, len; - long long v; + int i,j,len,where; unsigned char *p; - char buf[0x4041]; /* max length of generated string */ - zl = ziplistNew(); - for (i = 0; i < 100000; i++) { - where = (rand() & 1) ? ZIPLIST_HEAD : ZIPLIST_TAIL; - if (rand() & 1) { - /* equally likely create a 16, 32 or 64 bit int */ - v = (rand() & INT16_MAX) + ((1ll << 32) >> ((rand() % 3)*16)); - v *= 2*(rand() & 1)-1; /* randomly flip sign */ - sprintf(buf, "%lld", v); + char buf[1024]; + list *ref; + listNode *refnode; + + /* Hold temp vars from ziplist */ + unsigned char *sstr; + unsigned int slen; + long long sval; + + /* In the regression for the cascade bug, it was triggered + * with a random seed of 2. */ + srand(2); + + for (i = 0; i < 20000; i++) { + zl = ziplistNew(); + ref = listCreate(); + listSetFreeMethod(ref,sdsfree); + len = rand() % 256; + + /* Create lists */ + for (j = 0; j < len; j++) { + where = (rand() & 1) ? ZIPLIST_HEAD : ZIPLIST_TAIL; + switch(rand() % 4) { + case 0: + sprintf(buf,"%lld",(0LL + rand()) >> 20); + break; + case 1: + sprintf(buf,"%lld",(0LL + rand())); + break; + case 2: + sprintf(buf,"%lld",(0LL + rand()) << 20); + break; + case 3: + randstring(buf,0,256); + break; + default: + assert(NULL); + } + + /* Add to ziplist */ zl = ziplistPush(zl, (unsigned char*)buf, strlen(buf), where); - } else { - /* equally likely generate 6, 14 or >14 bit length */ - v = rand() & 0x3f; - v += 0x4000 >> ((rand() % 3)*8); - memset(buf, 'x', v); - zl = ziplistPush(zl, (unsigned char*)buf, v, where); - } - /* delete a random element */ - if ((len = ziplistLen(zl)) >= 10) { - idx = rand() % len; - // printf("Delete index %d\n", idx); - // ziplistRepr(zl); - ziplistDeleteRange(zl, idx, 1); - // ziplistRepr(zl); - len--; + /* Add to reference list */ + if (where == ZIPLIST_HEAD) { + listAddNodeHead(ref,sdsnew(buf)); + } else if (where == ZIPLIST_TAIL) { + listAddNodeTail(ref,sdsnew(buf)); + } else { + assert(NULL); + } } - /* iterate from front to back */ - idx = 0; - p = ziplistIndex(zl, 0); - while((p = ziplistNext(zl,p))) - idx++; - assert(len == idx+1); - - /* iterate from back to front */ - idx = 0; - p = ziplistIndex(zl, -1); - while((p = ziplistPrev(zl,p))) - idx++; - assert(len == idx+1); + assert(listLength(ref) == ziplistLen(zl)); + for (j = 0; j < len; j++) { + /* Naive way to get elements, but similar to the stresser + * executed from the Tcl test suite. */ + p = ziplistIndex(zl,j); + refnode = listIndex(ref,j); + + assert(ziplistGet(p,&sstr,&slen,&sval)); + if (sstr == NULL) { + sprintf(buf,"%lld",sval); + } else { + memcpy(buf,sstr,slen); + buf[slen] = '\0'; + } + assert(strcmp(buf,listNodeValue(refnode)) == 0); + } + zfree(zl); + listRelease(ref); } printf("SUCCESS\n\n"); }