X-Git-Url: https://git.saurik.com/redis.git/blobdiff_plain/5a86ab47995586f0a0ef18472eafd6e9131644c1..e323635c2d9d9039442cd1014932e4dd314d2d06:/src/ziplist.c diff --git a/src/ziplist.c b/src/ziplist.c index a2c0edb3..23bad45c 100644 --- a/src/ziplist.c +++ b/src/ziplist.c @@ -52,12 +52,23 @@ * String value with length less than or equal to 16383 bytes (14 bits). * |10______|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| - 5 bytes * String value with length greater than or equal to 16384 bytes. - * |1100____| - 1 byte + * |11000000| - 1 byte * Integer encoded as int16_t (2 bytes). - * |1101____| - 1 byte + * |11010000| - 1 byte * Integer encoded as int32_t (4 bytes). - * |1110____| - 1 byte + * |11100000| - 1 byte * Integer encoded as int64_t (8 bytes). + * |11110000| - 1 byte + * Integer encoded as 24 bit signed (3 bytes). + * |11111110| - 1 byte + * Integer encoded as 8 bit signed (1 byte). + * |1111xxxx| - (with xxxx between 0000 and 1101) immediate 4 bit integer. + * Unsigned integer from 0 to 12. The encoded value is actually from + * 1 to 13 because 0000 and 1111 can not be used, so 1 should be + * subtracted from the encoded 4 bit value to obtain the right value. + * |11111111| - End of ziplist. + * + * All the integers are represented in little endian byte order. */ #include @@ -75,8 +86,8 @@ #define ZIP_BIGLEN 254 /* Different encoding/length possibilities */ -#define ZIP_STR_MASK (0xc0) -#define ZIP_INT_MASK (0x30) +#define ZIP_STR_MASK 0xc0 +#define ZIP_INT_MASK 0x30 #define ZIP_STR_06B (0 << 6) #define ZIP_STR_14B (1 << 6) #define ZIP_STR_32B (2 << 6) @@ -84,6 +95,12 @@ #define ZIP_INT_32B (0xc0 | 1<<4) #define ZIP_INT_64B (0xc0 | 2<<4) #define ZIP_INT_24B (0xc0 | 3<<4) +#define ZIP_INT_8B 0xfe +/* 4 bit integer immediate encoding */ +#define ZIP_INT_IMM_MASK 0x0f +#define ZIP_INT_IMM_MIN 0xf1 /* 11110001 */ +#define ZIP_INT_IMM_MAX 0xfd /* 11111101 */ +#define ZIP_INT_IMM_VAL(v) (v & ZIP_INT_IMM_MASK) #define INT24_MAX 0x7fffff #define INT24_MIN (-INT24_MAX - 1) @@ -115,21 +132,22 @@ typedef struct zlentry { unsigned char *p; } zlentry; -#define ZIP_ENTRY_ENCODING(ptr, encoding) do { \ - (encoding) = (ptr[0]) & (ZIP_STR_MASK | ZIP_INT_MASK); \ - if (((encoding) & ZIP_STR_MASK) < ZIP_STR_MASK) { \ - /* String encoding: 2 MSBs */ \ - (encoding) &= ZIP_STR_MASK; \ - } \ +/* Extract the encoding from the byte pointed by 'ptr' and set it into + * 'encoding'. */ +#define ZIP_ENTRY_ENCODING(ptr, encoding) do { \ + (encoding) = (ptr[0]); \ + if ((encoding) < ZIP_STR_MASK) (encoding) &= ZIP_STR_MASK; \ } while(0) /* Return bytes needed to store integer encoded by 'encoding' */ static unsigned int zipIntSize(unsigned char encoding) { switch(encoding) { - case ZIP_INT_16B: return sizeof(int16_t); - case ZIP_INT_24B: return sizeof(int32_t)-sizeof(int8_t); - case ZIP_INT_32B: return sizeof(int32_t); - case ZIP_INT_64B: return sizeof(int64_t); + case ZIP_INT_8B: return 1; + case ZIP_INT_16B: return 2; + case ZIP_INT_24B: return 3; + case ZIP_INT_32B: return 4; + case ZIP_INT_64B: return 8; + default: return 0; /* 4 bit immediate */ } assert(NULL); return 0; @@ -274,7 +292,11 @@ static int zipTryEncoding(unsigned char *entry, unsigned int entrylen, long long 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) { + if (value >= 0 && value <= 12) { + *encoding = ZIP_INT_IMM_MIN+value; + } else if (value >= INT8_MIN && value <= INT8_MAX) { + *encoding = ZIP_INT_8B; + } else if (value >= INT16_MIN && value <= INT16_MAX) { *encoding = ZIP_INT_16B; } else if (value >= INT24_MIN && value <= INT24_MAX) { *encoding = ZIP_INT_24B; @@ -294,14 +316,16 @@ static void zipSaveInteger(unsigned char *p, int64_t value, unsigned char encodi int16_t i16; int32_t i32; int64_t i64; - if (encoding == ZIP_INT_16B) { + if (encoding == ZIP_INT_8B) { + ((int8_t*)p)[0] = (int8_t)value; + } else if (encoding == ZIP_INT_16B) { i16 = value; memcpy(p,&i16,sizeof(i16)); memrev16ifbe(p); } else if (encoding == ZIP_INT_24B) { i32 = value<<8; memrev32ifbe(&i32); - memcpy(p,((unsigned char*)&i32)+1,sizeof(i32)-sizeof(int8_t)); + memcpy(p,((uint8_t*)&i32)+1,sizeof(i32)-sizeof(uint8_t)); } else if (encoding == ZIP_INT_32B) { i32 = value; memcpy(p,&i32,sizeof(i32)); @@ -310,6 +334,8 @@ static void zipSaveInteger(unsigned char *p, int64_t value, unsigned char encodi i64 = value; memcpy(p,&i64,sizeof(i64)); memrev64ifbe(p); + } else if (encoding >= ZIP_INT_IMM_MIN && encoding <= ZIP_INT_IMM_MAX) { + /* Nothing to do, the value is stored in the encoding itself. */ } else { assert(NULL); } @@ -320,7 +346,9 @@ static int64_t zipLoadInteger(unsigned char *p, unsigned char encoding) { int16_t i16; int32_t i32; int64_t i64, ret = 0; - if (encoding == ZIP_INT_16B) { + if (encoding == ZIP_INT_8B) { + ret = ((int8_t*)p)[0]; + } else if (encoding == ZIP_INT_16B) { memcpy(&i16,p,sizeof(i16)); memrev16ifbe(&i16); ret = i16; @@ -330,13 +358,15 @@ static int64_t zipLoadInteger(unsigned char *p, unsigned char encoding) { ret = i32; } else if (encoding == ZIP_INT_24B) { i32 = 0; - memcpy(((unsigned char*)&i32)+1,p,sizeof(i32)-sizeof(int8_t)); + memcpy(((uint8_t*)&i32)+1,p,sizeof(i32)-sizeof(uint8_t)); memrev32ifbe(&i32); ret = i32>>8; } else if (encoding == ZIP_INT_64B) { memcpy(&i64,p,sizeof(i64)); memrev64ifbe(&i64); ret = i64; + } else if (encoding >= ZIP_INT_IMM_MIN && encoding <= ZIP_INT_IMM_MAX) { + ret = (encoding & ZIP_INT_IMM_MASK)-1; } else { assert(NULL); } @@ -470,12 +500,13 @@ static unsigned char *__ziplistDelete(unsigned char *zl, unsigned char *p, unsig 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. */ + /* Storing `prevrawlen` in this entry may increase or decrease the + * number of bytes required compare to the current `prevrawlen`. + * There always is room to store this, because it was previously + * stored by an entry that is now being deleted. */ nextdiff = zipPrevLenByteDiff(p,first.prevrawlen); - zipPrevEncodeLength(p-nextdiff,first.prevrawlen); + p -= nextdiff; + zipPrevEncodeLength(p,first.prevrawlen); /* Update offset for tail */ ZIPLIST_TAIL_OFFSET(zl) = @@ -491,8 +522,8 @@ static unsigned char *__ziplistDelete(unsigned char *zl, unsigned char *p, unsig } /* Move tail to the front of the ziplist */ - memmove(first.p,p-nextdiff, - intrev32ifbe(ZIPLIST_BYTES(zl))-(p-zl)-1+nextdiff); + memmove(first.p,p, + intrev32ifbe(ZIPLIST_BYTES(zl))-(p-zl)-1); } else { /* The entire tail was deleted. No need to move memory. */ ZIPLIST_TAIL_OFFSET(zl) = @@ -743,12 +774,11 @@ unsigned int ziplistCompare(unsigned char *p, unsigned char *sstr, unsigned int return 0; } } else { - /* Try to compare encoded values */ + /* Try to compare encoded values. Don't compare encoding because + * different implementations may encoded integers differently. */ if (zipTryEncoding(sstr,slen,&sval,&sencoding)) { - if (entry.encoding == sencoding) { - zval = zipLoadInteger(p+entry.headersize,entry.encoding); - return zval == sval; - } + zval = zipLoadInteger(p+entry.headersize,entry.encoding); + return zval == sval; } } return 0; @@ -776,19 +806,24 @@ unsigned char *ziplistFind(unsigned char *p, unsigned char *vstr, unsigned int v return p; } } else { - /* Find out if the specified entry can be encoded */ + /* Find out if the searched field can be encoded. Note that + * we do it only the first time, once done vencoding is set + * to non-zero and vll is set to the integer value. */ if (vencoding == 0) { - /* UINT_MAX when the entry CANNOT be encoded */ if (!zipTryEncoding(vstr, vlen, &vll, &vencoding)) { + /* If the entry can't be encoded we set it to + * UCHAR_MAX so that we don't retry again the next + * time. */ vencoding = UCHAR_MAX; } - /* Must be non-zero by now */ assert(vencoding); } - /* Compare current entry with specified entry */ - if (encoding == vencoding) { + /* Compare current entry with specified entry, do it only + * if vencoding != UCHAR_MAX because if there is no encoding + * possible for the field it can't be a valid integer. */ + if (vencoding != UCHAR_MAX) { long long ll = zipLoadInteger(q, encoding); if (ll == vll) { return p; @@ -1000,6 +1035,22 @@ int randstring(char *target, unsigned int min, unsigned int max) { return len; } +void verify(unsigned char *zl, zlentry *e) { + int i; + int len = ziplistLen(zl); + zlentry _e; + + for (i = 0; i < len; i++) { + memset(&e[i], 0, sizeof(zlentry)); + e[i] = zipEntry(ziplistIndex(zl, i)); + + memset(&_e, 0, sizeof(zlentry)); + _e = zipEntry(ziplistIndex(zl, -len+i)); + + assert(memcmp(&e[i], &_e, sizeof(zlentry)) == 0); + } +} + int main(int argc, char **argv) { unsigned char *zl, *p; unsigned char *entry; @@ -1281,6 +1332,43 @@ int main(int argc, char **argv) { printf("SUCCESS\n\n"); } + printf("Regression test deleting next to last entries:\n"); + { + char v[3][257]; + zlentry e[3]; + int i; + + for (i = 0; i < (sizeof(v)/sizeof(v[0])); i++) { + memset(v[i], 'a' + i, sizeof(v[0])); + } + + v[0][256] = '\0'; + v[1][ 1] = '\0'; + v[2][256] = '\0'; + + zl = ziplistNew(); + for (i = 0; i < (sizeof(v)/sizeof(v[0])); i++) { + zl = ziplistPush(zl, (unsigned char *) v[i], strlen(v[i]), ZIPLIST_TAIL); + } + + verify(zl, e); + + assert(e[0].prevrawlensize == 1); + assert(e[1].prevrawlensize == 5); + assert(e[2].prevrawlensize == 1); + + /* Deleting entry 1 will increase `prevrawlensize` for entry 2 */ + unsigned char *p = e[1].p; + zl = ziplistDelete(zl, &p); + + verify(zl, e); + + assert(e[0].prevrawlensize == 1); + assert(e[1].prevrawlensize == 5); + + printf("SUCCESS\n\n"); + } + printf("Create long list and check indices:\n"); { zl = ziplistNew();