X-Git-Url: https://git.saurik.com/redis.git/blobdiff_plain/b04ce2a35ce084a043ef8749ca4fa0e62b92bd03..18aa2b87b6db7fa79b0596590aa385adcbc64e53:/src/ziplist.c diff --git a/src/ziplist.c b/src/ziplist.c index 4f44bd58..113e71d9 100644 --- a/src/ziplist.c +++ b/src/ziplist.c @@ -67,9 +67,9 @@ #include #include #include "zmalloc.h" +#include "util.h" #include "ziplist.h" - -int ll2string(char *s, size_t len, long long value); +#include "endian.h" #define ZIP_END 255 #define ZIP_BIGLEN 254 @@ -92,13 +92,15 @@ int ll2string(char *s, size_t len, long long value); #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) +#define ZIPLIST_ENTRY_TAIL(zl) ((zl)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))) +#define ZIPLIST_ENTRY_END(zl) ((zl)+intrev32ifbe(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) < UINT16_MAX) ZIPLIST_LENGTH(zl)+=incr; } + if (ZIPLIST_LENGTH(zl) < UINT16_MAX) \ + ZIPLIST_LENGTH(zl) = intrev16ifbe(intrev16ifbe(ZIPLIST_LENGTH(zl))+incr); \ +} typedef struct zlentry { unsigned int prevrawlensize, prevrawlen; @@ -119,6 +121,7 @@ static unsigned int zipEntryEncoding(unsigned char *p) { return p[0] & 0xf0; } assert(NULL); + return 0; } /* Return bytes needed to store integer encoded by 'encoding' */ @@ -129,13 +132,14 @@ static unsigned int zipIntSize(unsigned char encoding) { case ZIP_INT_64B: return sizeof(int64_t); } assert(NULL); + return 0; } /* Decode the encoded length pointed by 'p'. If a pointer to 'lensize' is * provided, it is set to the number of bytes required to encode the length. */ static unsigned int zipDecodeLength(unsigned char *p, unsigned int *lensize) { unsigned char encoding = zipEntryEncoding(p); - unsigned int len; + unsigned int len = 0; if (ZIP_IS_STR(encoding)) { switch(encoding) { @@ -205,6 +209,7 @@ static unsigned int zipPrevDecodeLength(unsigned char *p, unsigned int *lensize) } else { if (lensize) *lensize = 1+sizeof(len); memcpy(&len,p+1,sizeof(len)); + memrev32ifbe(&len); } return len; } @@ -221,6 +226,7 @@ static unsigned int zipPrevEncodeLength(unsigned char *p, unsigned int len) { } else { p[0] = ZIP_BIGLEN; memcpy(p+1,&len,sizeof(len)); + memrev32ifbe(p+1); return 1+sizeof(len); } } @@ -232,6 +238,7 @@ static void zipPrevEncodeLengthForceLarge(unsigned char *p, unsigned int len) { if (p == NULL) return; p[0] = ZIP_BIGLEN; memcpy(p+1,&len,sizeof(len)); + memrev32ifbe(p+1); } /* Return the difference in number of bytes needed to store the new length @@ -246,22 +253,9 @@ static int zipPrevLenByteDiff(unsigned char *p, unsigned int len) { * Stores the integer value in 'v' and its encoding in 'encoding'. */ static int zipTryEncoding(unsigned char *entry, unsigned int entrylen, long long *v, unsigned char *encoding) { long long value; - char *eptr; - char buf[32]; if (entrylen >= 32 || entrylen == 0) return 0; - if (entry[0] == '-' || (entry[0] >= '0' && entry[0] <= '9')) { - int slen; - - /* Perform a back-and-forth conversion to make sure that - * the string turned into an integer is not losing any info. */ - memcpy(buf,entry,entrylen); - buf[entrylen] = '\0'; - value = strtoll(buf,&eptr,10); - if (eptr[0] != '\0') return 0; - slen = ll2string(buf,32,value); - if (entrylen != (unsigned)slen || memcmp(buf,entry,slen)) return 0; - + if (string2ll((char*)entry,entrylen,&value)) { /* Great, the string can be encoded. Check what's the smallest * of our encoding types that can hold this value. */ if (value >= INT16_MIN && value <= INT16_MAX) { @@ -285,12 +279,15 @@ static void zipSaveInteger(unsigned char *p, int64_t value, unsigned char encodi if (encoding == ZIP_INT_16B) { i16 = value; memcpy(p,&i16,sizeof(i16)); + memrev16ifbe(p); } else if (encoding == ZIP_INT_32B) { i32 = value; memcpy(p,&i32,sizeof(i32)); + memrev32ifbe(p); } else if (encoding == ZIP_INT_64B) { i64 = value; memcpy(p,&i64,sizeof(i64)); + memrev64ifbe(p); } else { assert(NULL); } @@ -300,15 +297,18 @@ static void zipSaveInteger(unsigned char *p, int64_t value, unsigned char encodi static int64_t zipLoadInteger(unsigned char *p, unsigned char encoding) { int16_t i16; int32_t i32; - int64_t i64, ret; + int64_t i64, ret = 0; if (encoding == ZIP_INT_16B) { memcpy(&i16,p,sizeof(i16)); + memrev16ifbe(&i16); ret = i16; } else if (encoding == ZIP_INT_32B) { memcpy(&i32,p,sizeof(i32)); + memrev32ifbe(&i32); ret = i32; } else if (encoding == ZIP_INT_64B) { memcpy(&i64,p,sizeof(i64)); + memrev64ifbe(&i64); ret = i64; } else { assert(NULL); @@ -337,8 +337,8 @@ static unsigned int zipRawEntryLength(unsigned char *p) { 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_BYTES(zl) = intrev32ifbe(bytes); + ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE); ZIPLIST_LENGTH(zl) = 0; zl[bytes-1] = ZIP_END; return zl; @@ -347,7 +347,7 @@ unsigned char *ziplistNew(void) { /* Resize the ziplist. */ static unsigned char *ziplistResize(unsigned char *zl, unsigned int len) { zl = zrealloc(zl,len); - ZIPLIST_BYTES(zl) = len; + ZIPLIST_BYTES(zl) = intrev32ifbe(len); zl[len-1] = ZIP_END; return zl; } @@ -373,8 +373,8 @@ static unsigned char *ziplistResize(unsigned char *zl, unsigned int len) { * The pointer "p" points to the first entry that does NOT need to be * updated, i.e. consecutive fields MAY need an update. */ static unsigned char *__ziplistCascadeUpdate(unsigned char *zl, unsigned char *p) { - unsigned int curlen = ZIPLIST_BYTES(zl), rawlen, rawlensize; - unsigned int offset, noffset, extra; + size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), rawlen, rawlensize; + size_t offset, noffset, extra; unsigned char *np; zlentry cur, next; @@ -396,12 +396,19 @@ static unsigned char *__ziplistCascadeUpdate(unsigned char *zl, unsigned char *p offset = p-zl; extra = rawlensize-next.prevrawlensize; zl = ziplistResize(zl,curlen+extra); - ZIPLIST_TAIL_OFFSET(zl) += extra; p = zl+offset; - /* Move the tail to the back. */ + /* Current pointer and offset for next element. */ np = p+rawlen; noffset = np-zl; + + /* Update tail offset when next element is not the tail element. */ + if ((zl+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))) != np) { + ZIPLIST_TAIL_OFFSET(zl) = + intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+extra); + } + + /* Move the tail to the back. */ memmove(np+rawlensize, np+next.prevrawlensize, curlen-noffset-next.prevrawlensize-1); @@ -409,6 +416,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. @@ -428,7 +436,8 @@ static unsigned char *__ziplistCascadeUpdate(unsigned char *zl, unsigned char *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 offset, nextdiff = 0; + size_t offset; + int nextdiff = 0; zlentry first, tail; first = zipEntry(p); @@ -448,25 +457,30 @@ static unsigned char *__ziplistDelete(unsigned char *zl, unsigned char *p, unsig zipPrevEncodeLength(p-nextdiff,first.prevrawlen); /* Update offset for tail */ - ZIPLIST_TAIL_OFFSET(zl) -= totlen; + ZIPLIST_TAIL_OFFSET(zl) = + intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))-totlen); /* When the tail contains more than one entry, we need to take * "nextdiff" in account as well. Otherwise, a change in the * size of prevlen doesn't have an effect on the *tail* offset. */ tail = zipEntry(p); - if (p[tail.headersize+tail.len] != ZIP_END) - ZIPLIST_TAIL_OFFSET(zl) += nextdiff; + if (p[tail.headersize+tail.len] != ZIP_END) { + ZIPLIST_TAIL_OFFSET(zl) = + intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff); + } /* Move tail to the front of the ziplist */ - memmove(first.p,p-nextdiff,ZIPLIST_BYTES(zl)-(p-zl)-1+nextdiff); + memmove(first.p,p-nextdiff, + intrev32ifbe(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; + ZIPLIST_TAIL_OFFSET(zl) = + intrev32ifbe((first.p-zl)-first.prevrawlen); } /* Resize and update length */ offset = first.p-zl; - zl = ziplistResize(zl, ZIPLIST_BYTES(zl)-totlen+nextdiff); + zl = ziplistResize(zl, intrev32ifbe(ZIPLIST_BYTES(zl))-totlen+nextdiff); ZIPLIST_INCR_LENGTH(zl,-deleted); p = zl+offset; @@ -480,10 +494,13 @@ static unsigned char *__ziplistDelete(unsigned char *zl, unsigned char *p, unsig /* 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; + size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), reqlen, prevlen = 0; + size_t offset; + int nextdiff = 0; unsigned char encoding = 0; - long long value; + long long value = 123456789; /* initialized to avoid warning. Using a value + that is easy to see if for some reason + we use it uninitialized. */ zlentry entry, tail; /* Find out prevlen for the entry that is inserted. */ @@ -530,17 +547,20 @@ static unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsig zipPrevEncodeLength(p+reqlen,reqlen); /* Update offset for tail */ - ZIPLIST_TAIL_OFFSET(zl) += reqlen; + ZIPLIST_TAIL_OFFSET(zl) = + intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen); /* When the tail contains more than one entry, we need to take * "nextdiff" in account as well. Otherwise, a change in the * size of prevlen doesn't have an effect on the *tail* offset. */ tail = zipEntry(p+reqlen); - if (p[reqlen+tail.headersize+tail.len] != ZIP_END) - ZIPLIST_TAIL_OFFSET(zl) += nextdiff; + if (p[reqlen+tail.headersize+tail.len] != ZIP_END) { + ZIPLIST_TAIL_OFFSET(zl) = + intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff); + } } else { /* This element will be the new tail. */ - ZIPLIST_TAIL_OFFSET(zl) = p-zl; + ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(p-zl); } /* When nextdiff != 0, the raw length of the next entry has changed, so @@ -594,7 +614,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); @@ -660,7 +685,7 @@ unsigned char *ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char * 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; + size_t offset = *p-zl; zl = __ziplistDelete(zl,*p,1); /* Store pointer to current element in p, because ziplistDelete will @@ -707,8 +732,8 @@ unsigned int ziplistCompare(unsigned char *p, unsigned char *sstr, unsigned int /* Return length of ziplist. */ unsigned int ziplistLen(unsigned char *zl) { unsigned int len = 0; - if (ZIPLIST_LENGTH(zl) < UINT16_MAX) { - len = ZIPLIST_LENGTH(zl); + if (intrev16ifbe(ZIPLIST_LENGTH(zl)) < UINT16_MAX) { + len = intrev16ifbe(ZIPLIST_LENGTH(zl)); } else { unsigned char *p = zl+ZIPLIST_HEADER_SIZE; while (*p != ZIP_END) { @@ -717,14 +742,14 @@ unsigned int ziplistLen(unsigned char *zl) { } /* Re-store length if small enough */ - if (len < UINT16_MAX) ZIPLIST_LENGTH(zl) = len; + if (len < UINT16_MAX) ZIPLIST_LENGTH(zl) = intrev16ifbe(len); } return len; } -/* Return size in bytes of ziplist. */ -unsigned int ziplistSize(unsigned char *zl) { - return ZIPLIST_BYTES(zl); +/* Return ziplist blob size in bytes. */ +size_t ziplistBlobLen(unsigned char *zl) { + return intrev32ifbe(ZIPLIST_BYTES(zl)); } void ziplistRepr(unsigned char *zl) { @@ -736,9 +761,9 @@ void ziplistRepr(unsigned char *zl) { "{total bytes %d} " "{length %u}\n" "{tail offset %u}\n", - ZIPLIST_BYTES(zl), - ZIPLIST_LENGTH(zl), - ZIPLIST_TAIL_OFFSET(zl)); + intrev32ifbe(ZIPLIST_BYTES(zl)), + intrev16ifbe(ZIPLIST_LENGTH(zl)), + intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))); p = ZIPLIST_ENTRY_HEAD(zl); while(*p != ZIP_END) { entry = zipEntry(p); @@ -753,9 +778,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 +789,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 +807,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(); @@ -834,7 +864,7 @@ void stress(int pos, int num, int maxsize, int dnum) { 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); + i,intrev32ifbe(ZIPLIST_BYTES(zl)),num,posstr[pos],usec()-start); zfree(zl); } } @@ -852,7 +882,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 +894,31 @@ void pop(unsigned char *zl, int where) { } } +int 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 len; +} + int main(int argc, char **argv) { unsigned char *zl, *p; unsigned char *entry; @@ -901,7 +956,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 +986,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 +1003,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 +1031,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 +1048,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 +1065,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 +1094,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 +1111,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 +1168,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 +1193,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 +1248,77 @@ 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); - 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); - } + char buf[1024]; + int buflen; + list *ref; + listNode *refnode; + + /* Hold temp vars from ziplist */ + unsigned char *sstr; + unsigned int slen; + long long sval; + + 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; + if (rand() % 2) { + buflen = randstring(buf,1,sizeof(buf)-1); + } else { + switch(rand() % 3) { + case 0: + buflen = sprintf(buf,"%lld",(0LL + rand()) >> 20); + break; + case 1: + buflen = sprintf(buf,"%lld",(0LL + rand())); + break; + case 2: + buflen = sprintf(buf,"%lld",(0LL + rand()) << 20); + break; + default: + assert(NULL); + } + } + + /* Add to ziplist */ + zl = ziplistPush(zl, (unsigned char*)buf, buflen, 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,sdsnewlen(buf, buflen)); + } else if (where == ZIPLIST_TAIL) { + listAddNodeTail(ref,sdsnewlen(buf, buflen)); + } 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) { + buflen = sprintf(buf,"%lld",sval); + } else { + buflen = slen; + memcpy(buf,sstr,buflen); + buf[buflen] = '\0'; + } + assert(memcmp(buf,listNodeValue(refnode),buflen) == 0); + } + zfree(zl); + listRelease(ref); } printf("SUCCESS\n\n"); }