X-Git-Url: https://git.saurik.com/redis.git/blobdiff_plain/d23d73c7469645cafc003574ff1fa6c4beb54566..6caa0c10ef630ec583deb63d0b04cc01f8256d5d:/src/ziplist.c?ds=inline diff --git a/src/ziplist.c b/src/ziplist.c index 31e61633..d4ac4f9b 100644 --- a/src/ziplist.c +++ b/src/ziplist.c @@ -69,6 +69,36 @@ * |11111111| - End of ziplist. * * All the integers are represented in little endian byte order. + * + * ---------------------------------------------------------------------------- + * + * Copyright (c) 2009-2012, Pieter Noordhuis <pcnoordhuis at gmail dot com> + * Copyright (c) 2009-2012, Salvatore Sanfilippo <antirez at gmail dot com> + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * * Neither the name of Redis nor the names of its contributors may be used + * to endorse or promote products derived from this software without + * specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. */ #include <stdio.h> @@ -317,7 +347,7 @@ static void zipSaveInteger(unsigned char *p, int64_t value, unsigned char encodi int32_t i32; int64_t i64; if (encoding == ZIP_INT_8B) { - ((char*)p)[0] = (char)value; + ((int8_t*)p)[0] = (int8_t)value; } else if (encoding == ZIP_INT_16B) { i16 = value; memcpy(p,&i16,sizeof(i16)); @@ -325,7 +355,7 @@ static void zipSaveInteger(unsigned char *p, int64_t value, unsigned char encodi } 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)); @@ -347,7 +377,7 @@ static int64_t zipLoadInteger(unsigned char *p, unsigned char encoding) { int32_t i32; int64_t i64, ret = 0; if (encoding == ZIP_INT_8B) { - ret = ((char*)p)[0]; + ret = ((int8_t*)p)[0]; } else if (encoding == ZIP_INT_16B) { memcpy(&i16,p,sizeof(i16)); memrev16ifbe(&i16); @@ -358,7 +388,7 @@ 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) { @@ -500,12 +530,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) = @@ -521,8 +552,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) = @@ -805,19 +836,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; @@ -1029,6 +1065,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; @@ -1310,6 +1362,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();