diff options
Diffstat (limited to 'src/listpack.c')
-rw-r--r-- | src/listpack.c | 1182 |
1 files changed, 1090 insertions, 92 deletions
diff --git a/src/listpack.c b/src/listpack.c index 8672f63c8..9bb1c8c95 100644 --- a/src/listpack.c +++ b/src/listpack.c @@ -55,6 +55,7 @@ #define LP_ENCODING_7BIT_UINT 0 #define LP_ENCODING_7BIT_UINT_MASK 0x80 #define LP_ENCODING_IS_7BIT_UINT(byte) (((byte)&LP_ENCODING_7BIT_UINT_MASK)==LP_ENCODING_7BIT_UINT) +#define LP_ENCODING_7BIT_UINT_ENTRY_SIZE 2 #define LP_ENCODING_6BIT_STR 0x80 #define LP_ENCODING_6BIT_STR_MASK 0xC0 @@ -63,6 +64,7 @@ #define LP_ENCODING_13BIT_INT 0xC0 #define LP_ENCODING_13BIT_INT_MASK 0xE0 #define LP_ENCODING_IS_13BIT_INT(byte) (((byte)&LP_ENCODING_13BIT_INT_MASK)==LP_ENCODING_13BIT_INT) +#define LP_ENCODING_13BIT_INT_ENTRY_SIZE 3 #define LP_ENCODING_12BIT_STR 0xE0 #define LP_ENCODING_12BIT_STR_MASK 0xF0 @@ -71,18 +73,22 @@ #define LP_ENCODING_16BIT_INT 0xF1 #define LP_ENCODING_16BIT_INT_MASK 0xFF #define LP_ENCODING_IS_16BIT_INT(byte) (((byte)&LP_ENCODING_16BIT_INT_MASK)==LP_ENCODING_16BIT_INT) +#define LP_ENCODING_16BIT_INT_ENTRY_SIZE 4 #define LP_ENCODING_24BIT_INT 0xF2 #define LP_ENCODING_24BIT_INT_MASK 0xFF #define LP_ENCODING_IS_24BIT_INT(byte) (((byte)&LP_ENCODING_24BIT_INT_MASK)==LP_ENCODING_24BIT_INT) +#define LP_ENCODING_24BIT_INT_ENTRY_SIZE 5 #define LP_ENCODING_32BIT_INT 0xF3 #define LP_ENCODING_32BIT_INT_MASK 0xFF #define LP_ENCODING_IS_32BIT_INT(byte) (((byte)&LP_ENCODING_32BIT_INT_MASK)==LP_ENCODING_32BIT_INT) +#define LP_ENCODING_32BIT_INT_ENTRY_SIZE 6 #define LP_ENCODING_64BIT_INT 0xF4 #define LP_ENCODING_64BIT_INT_MASK 0xFF #define LP_ENCODING_IS_64BIT_INT(byte) (((byte)&LP_ENCODING_64BIT_INT_MASK)==LP_ENCODING_64BIT_INT) +#define LP_ENCODING_64BIT_INT_ENTRY_SIZE 10 #define LP_ENCODING_32BIT_STR 0xF0 #define LP_ENCODING_32BIT_STR_MASK 0xFF @@ -246,6 +252,58 @@ unsigned char* lpShrinkToFit(unsigned char *lp) { } } +/* Stores the integer encoded representation of 'v' in the 'intenc' buffer. */ +static inline void lpEncodeIntegerGetType(int64_t v, unsigned char *intenc, uint64_t *enclen) { + if (v >= 0 && v <= 127) { + /* Single byte 0-127 integer. */ + intenc[0] = v; + *enclen = 1; + } else if (v >= -4096 && v <= 4095) { + /* 13 bit integer. */ + if (v < 0) v = ((int64_t)1<<13)+v; + intenc[0] = (v>>8)|LP_ENCODING_13BIT_INT; + intenc[1] = v&0xff; + *enclen = 2; + } else if (v >= -32768 && v <= 32767) { + /* 16 bit integer. */ + if (v < 0) v = ((int64_t)1<<16)+v; + intenc[0] = LP_ENCODING_16BIT_INT; + intenc[1] = v&0xff; + intenc[2] = v>>8; + *enclen = 3; + } else if (v >= -8388608 && v <= 8388607) { + /* 24 bit integer. */ + if (v < 0) v = ((int64_t)1<<24)+v; + intenc[0] = LP_ENCODING_24BIT_INT; + intenc[1] = v&0xff; + intenc[2] = (v>>8)&0xff; + intenc[3] = v>>16; + *enclen = 4; + } else if (v >= -2147483648 && v <= 2147483647) { + /* 32 bit integer. */ + if (v < 0) v = ((int64_t)1<<32)+v; + intenc[0] = LP_ENCODING_32BIT_INT; + intenc[1] = v&0xff; + intenc[2] = (v>>8)&0xff; + intenc[3] = (v>>16)&0xff; + intenc[4] = v>>24; + *enclen = 5; + } else { + /* 64 bit integer. */ + uint64_t uv = v; + intenc[0] = LP_ENCODING_64BIT_INT; + intenc[1] = uv&0xff; + intenc[2] = (uv>>8)&0xff; + intenc[3] = (uv>>16)&0xff; + intenc[4] = (uv>>24)&0xff; + intenc[5] = (uv>>32)&0xff; + intenc[6] = (uv>>40)&0xff; + intenc[7] = (uv>>48)&0xff; + intenc[8] = uv>>56; + *enclen = 9; + } +} + /* Given an element 'ele' of size 'size', determine if the element can be * represented inside the listpack encoded as integer, and returns * LP_ENCODING_INT if so. Otherwise returns LP_ENCODING_STR if no integer @@ -257,57 +315,10 @@ unsigned char* lpShrinkToFit(unsigned char *lp) { * Regardless of the returned encoding, 'enclen' is populated by reference to * the number of bytes that the string or integer encoded element will require * in order to be represented. */ -int lpEncodeGetType(unsigned char *ele, uint32_t size, unsigned char *intenc, uint64_t *enclen) { +static inline int lpEncodeGetType(unsigned char *ele, uint32_t size, unsigned char *intenc, uint64_t *enclen) { int64_t v; if (lpStringToInt64((const char*)ele, size, &v)) { - if (v >= 0 && v <= 127) { - /* Single byte 0-127 integer. */ - intenc[0] = v; - *enclen = 1; - } else if (v >= -4096 && v <= 4095) { - /* 13 bit integer. */ - if (v < 0) v = ((int64_t)1<<13)+v; - intenc[0] = (v>>8)|LP_ENCODING_13BIT_INT; - intenc[1] = v&0xff; - *enclen = 2; - } else if (v >= -32768 && v <= 32767) { - /* 16 bit integer. */ - if (v < 0) v = ((int64_t)1<<16)+v; - intenc[0] = LP_ENCODING_16BIT_INT; - intenc[1] = v&0xff; - intenc[2] = v>>8; - *enclen = 3; - } else if (v >= -8388608 && v <= 8388607) { - /* 24 bit integer. */ - if (v < 0) v = ((int64_t)1<<24)+v; - intenc[0] = LP_ENCODING_24BIT_INT; - intenc[1] = v&0xff; - intenc[2] = (v>>8)&0xff; - intenc[3] = v>>16; - *enclen = 4; - } else if (v >= -2147483648 && v <= 2147483647) { - /* 32 bit integer. */ - if (v < 0) v = ((int64_t)1<<32)+v; - intenc[0] = LP_ENCODING_32BIT_INT; - intenc[1] = v&0xff; - intenc[2] = (v>>8)&0xff; - intenc[3] = (v>>16)&0xff; - intenc[4] = v>>24; - *enclen = 5; - } else { - /* 64 bit integer. */ - uint64_t uv = v; - intenc[0] = LP_ENCODING_64BIT_INT; - intenc[1] = uv&0xff; - intenc[2] = (uv>>8)&0xff; - intenc[3] = (uv>>16)&0xff; - intenc[4] = (uv>>24)&0xff; - intenc[5] = (uv>>32)&0xff; - intenc[6] = (uv>>40)&0xff; - intenc[7] = (uv>>48)&0xff; - intenc[8] = uv>>56; - *enclen = 9; - } + lpEncodeIntegerGetType(v, intenc, enclen); return LP_ENCODING_INT; } else { if (size < 64) *enclen = 1+size; @@ -322,7 +333,7 @@ int lpEncodeGetType(unsigned char *ele, uint32_t size, unsigned char *intenc, ui * The function returns the number of bytes used to encode it, from * 1 to 5. If 'buf' is NULL the function just returns the number of bytes * needed in order to encode the backlen. */ -unsigned long lpEncodeBacklen(unsigned char *buf, uint64_t l) { +static inline unsigned long lpEncodeBacklen(unsigned char *buf, uint64_t l) { if (l <= 127) { if (buf) buf[0] = l; return 1; @@ -361,7 +372,7 @@ unsigned long lpEncodeBacklen(unsigned char *buf, uint64_t l) { /* Decode the backlen and returns it. If the encoding looks invalid (more than * 5 bytes are used), UINT64_MAX is returned to report the problem. */ -uint64_t lpDecodeBacklen(unsigned char *p) { +static inline uint64_t lpDecodeBacklen(unsigned char *p) { uint64_t val = 0; uint64_t shift = 0; do { @@ -378,7 +389,7 @@ uint64_t lpDecodeBacklen(unsigned char *p) { * buffer 's'. The function should be called with 'buf' having always enough * space for encoding the string. This is done by calling lpEncodeGetType() * before calling this function. */ -void lpEncodeString(unsigned char *buf, unsigned char *s, uint32_t len) { +static inline void lpEncodeString(unsigned char *buf, unsigned char *s, uint32_t len) { if (len < 64) { buf[0] = len | LP_ENCODING_6BIT_STR; memcpy(buf+1,s,len); @@ -403,7 +414,7 @@ void lpEncodeString(unsigned char *buf, unsigned char *s, uint32_t len) { * str), so should only be called when we know 'p' was already validated by * lpCurrentEncodedSizeBytes or ASSERT_INTEGRITY_LEN (possibly since 'p' is * a return value of another function that validated its return. */ -uint32_t lpCurrentEncodedSizeUnsafe(unsigned char *p) { +static inline uint32_t lpCurrentEncodedSizeUnsafe(unsigned char *p) { if (LP_ENCODING_IS_7BIT_UINT(p[0])) return 1; if (LP_ENCODING_IS_6BIT_STR(p[0])) return 1+LP_ENCODING_6BIT_STR_LEN(p); if (LP_ENCODING_IS_13BIT_INT(p[0])) return 2; @@ -421,7 +432,7 @@ uint32_t lpCurrentEncodedSizeUnsafe(unsigned char *p) { * This includes just the encoding byte, and the bytes needed to encode the length * of the element (excluding the element data itself) * If the element encoding is wrong then 0 is returned. */ -uint32_t lpCurrentEncodedSizeBytes(unsigned char *p) { +static inline uint32_t lpCurrentEncodedSizeBytes(unsigned char *p) { if (LP_ENCODING_IS_7BIT_UINT(p[0])) return 1; if (LP_ENCODING_IS_6BIT_STR(p[0])) return 1; if (LP_ENCODING_IS_13BIT_INT(p[0])) return 1; @@ -492,7 +503,7 @@ unsigned char *lpLast(unsigned char *lp) { * needed. As a side effect of calling this function, the listpack header * could be modified, because if the count is found to be already within * the 'numele' header field range, the new value is set. */ -uint32_t lpLength(unsigned char *lp) { +unsigned long lpLength(unsigned char *lp) { uint32_t numele = lpGetNumElements(lp); if (numele != LP_HDR_NUMELE_UNKNOWN) return numele; @@ -534,6 +545,10 @@ uint32_t lpLength(unsigned char *lp) { * by the function, than to pass a buffer (and convert it back to a number) * is of course useless. * + * If 'entry_size' is not NULL, *entry_size is set to the entry length of the + * listpack element pointed by 'p'. This includes the encoding bytes, length + * bytes, the element data itself, and the backlen bytes. + * * If the function is called against a badly encoded ziplist, so that there * is no valid way to parse it, the function returns like if there was an * integer encoded with value 12345678900000000 + <unrecognized byte>, this may @@ -545,7 +560,7 @@ uint32_t lpLength(unsigned char *lp) { * assumed to be valid, so that would be a very high API cost. However a function * in order to check the integrity of the listpack at load time is provided, * check lpIsValid(). */ -unsigned char *lpGet(unsigned char *p, int64_t *count, unsigned char *intbuf) { +static inline unsigned char *lpGetWithSize(unsigned char *p, int64_t *count, unsigned char *intbuf, uint64_t *entry_size) { int64_t val; uint64_t uval, negstart, negmax; @@ -554,24 +569,29 @@ unsigned char *lpGet(unsigned char *p, int64_t *count, unsigned char *intbuf) { negstart = UINT64_MAX; /* 7 bit ints are always positive. */ negmax = 0; uval = p[0] & 0x7f; + if (entry_size) *entry_size = LP_ENCODING_7BIT_UINT_ENTRY_SIZE; } else if (LP_ENCODING_IS_6BIT_STR(p[0])) { *count = LP_ENCODING_6BIT_STR_LEN(p); + if (entry_size) *entry_size = 1 + *count + lpEncodeBacklen(NULL, *count + 1); return p+1; } else if (LP_ENCODING_IS_13BIT_INT(p[0])) { uval = ((p[0]&0x1f)<<8) | p[1]; negstart = (uint64_t)1<<12; negmax = 8191; + if (entry_size) *entry_size = LP_ENCODING_13BIT_INT_ENTRY_SIZE; } else if (LP_ENCODING_IS_16BIT_INT(p[0])) { uval = (uint64_t)p[1] | (uint64_t)p[2]<<8; negstart = (uint64_t)1<<15; negmax = UINT16_MAX; + if (entry_size) *entry_size = LP_ENCODING_16BIT_INT_ENTRY_SIZE; } else if (LP_ENCODING_IS_24BIT_INT(p[0])) { uval = (uint64_t)p[1] | (uint64_t)p[2]<<8 | (uint64_t)p[3]<<16; negstart = (uint64_t)1<<23; negmax = UINT32_MAX>>8; + if (entry_size) *entry_size = LP_ENCODING_24BIT_INT_ENTRY_SIZE; } else if (LP_ENCODING_IS_32BIT_INT(p[0])) { uval = (uint64_t)p[1] | (uint64_t)p[2]<<8 | @@ -579,6 +599,7 @@ unsigned char *lpGet(unsigned char *p, int64_t *count, unsigned char *intbuf) { (uint64_t)p[4]<<24; negstart = (uint64_t)1<<31; negmax = UINT32_MAX; + if (entry_size) *entry_size = LP_ENCODING_32BIT_INT_ENTRY_SIZE; } else if (LP_ENCODING_IS_64BIT_INT(p[0])) { uval = (uint64_t)p[1] | (uint64_t)p[2]<<8 | @@ -590,11 +611,14 @@ unsigned char *lpGet(unsigned char *p, int64_t *count, unsigned char *intbuf) { (uint64_t)p[8]<<56; negstart = (uint64_t)1<<63; negmax = UINT64_MAX; + if (entry_size) *entry_size = LP_ENCODING_64BIT_INT_ENTRY_SIZE; } else if (LP_ENCODING_IS_12BIT_STR(p[0])) { *count = LP_ENCODING_12BIT_STR_LEN(p); + if (entry_size) *entry_size = 2 + *count + lpEncodeBacklen(NULL, *count + 2); return p+2; } else if (LP_ENCODING_IS_32BIT_STR(p[0])) { *count = LP_ENCODING_32BIT_STR_LEN(p); + if (entry_size) *entry_size = 5 + *count + lpEncodeBacklen(NULL, *count + 5); return p+5; } else { uval = 12345678900000000ULL + p[0]; @@ -626,17 +650,105 @@ unsigned char *lpGet(unsigned char *p, int64_t *count, unsigned char *intbuf) { } } -/* Insert, delete or replace the specified element 'ele' of length 'len' at - * the specified position 'p', with 'p' being a listpack element pointer - * obtained with lpFirst(), lpLast(), lpNext(), lpPrev() or lpSeek(). +unsigned char *lpGet(unsigned char *p, int64_t *count, unsigned char *intbuf) { + return lpGetWithSize(p, count, intbuf, NULL); +} + +/* This is just a wrapper to lpGet() that is able to get entry value directly. + * When the function returns NULL, it populates the integer value by reference in 'lval'. + * Otherwise if the element is encoded as a string a pointer to the string (pointing + * inside the listpack itself) is returned, and 'slen' is set to the length of the + * string. */ +unsigned char *lpGetValue(unsigned char *p, unsigned int *slen, long long *lval) { + unsigned char *vstr; + int64_t ele_len; + + vstr = lpGet(p, &ele_len, NULL); + if (vstr) { + *slen = ele_len; + } else { + *lval = ele_len; + } + return vstr; +} + +/* Find pointer to the entry equal to the specified entry. Skip 'skip' entries + * between every comparison. Returns NULL when the field could not be found. */ +unsigned char *lpFind(unsigned char *lp, unsigned char *p, unsigned char *s, + uint32_t slen, unsigned int skip) { + int skipcnt = 0; + unsigned char vencoding = 0; + unsigned char *value; + int64_t ll, vll; + uint64_t entry_size = 123456789; /* initialized to avoid warning. */ + uint32_t lp_bytes = lpBytes(lp); + + assert(p); + while (p) { + if (skipcnt == 0) { + value = lpGetWithSize(p, &ll, NULL, &entry_size); + if (value) { + if (slen == ll && memcmp(value, s, slen) == 0) { + return p; + } + } else { + /* 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) { + /* If the entry can be encoded as integer we set it to + * 1, else set it to UCHAR_MAX, so that we don't retry + * again the next time. */ + if (slen >= 32 || slen == 0 || !lpStringToInt64((const char*)s, slen, &vll)) { + vencoding = UCHAR_MAX; + } else { + vencoding = 1; + } + } + + /* 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 && ll == vll) { + return p; + } + } + + /* Reset skip count */ + skipcnt = skip; + p += entry_size; + } else { + /* Skip entry */ + skipcnt--; + + /* Move to next entry, avoid use `lpNext` due to `ASSERT_INTEGRITY` in + * `lpNext` will call `lpBytes`, will cause performance degradation */ + p = lpSkip(p); + } + + assert(p >= lp + LP_HDR_SIZE && p < lp + lp_bytes); + if (p[0] == LP_EOF) break; + } + + return NULL; +} + +/* Insert, delete or replace the specified string element 'elestr' of length + * 'size' or integer element 'eleint' at the specified position 'p', with 'p' + * being a listpack element pointer obtained with lpFirst(), lpLast(), lpNext(), + * lpPrev() or lpSeek(). * * The element is inserted before, after, or replaces the element pointed * by 'p' depending on the 'where' argument, that can be LP_BEFORE, LP_AFTER * or LP_REPLACE. - * - * If 'ele' is set to NULL, the function removes the element pointed by 'p' - * instead of inserting one. - * + * + * If both 'elestr' and `eleint` are NULL, the function removes the element + * pointed by 'p' instead of inserting one. + * If `eleint` is non-NULL, 'size' is the length of 'eleint', the function insert + * or replace with a 64 bit integer, which is stored in the 'eleint' buffer. + * If 'elestr` is non-NULL, 'size' is the length of 'elestr', the function insert + * or replace with a string, which is stored in the 'elestr' buffer. + * * Returns NULL on out of memory or when the listpack total length would exceed * the max allowed size of 2^32-1, otherwise the new pointer to the listpack * holding the new element is returned (and the old pointer passed is no longer @@ -646,19 +758,22 @@ unsigned char *lpGet(unsigned char *p, int64_t *count, unsigned char *intbuf) { * to the address of the element just added, so that it will be possible to * continue an interaction with lpNext() and lpPrev(). * - * For deletion operations ('ele' set to NULL) 'newp' is set to the next - * element, on the right of the deleted one, or to NULL if the deleted element - * was the last one. */ -unsigned char *lpInsert(unsigned char *lp, unsigned char *ele, uint32_t size, unsigned char *p, int where, unsigned char **newp) { + * For deletion operations (both 'elestr' and 'eleint' set to NULL) 'newp' is + * set to the next element, on the right of the deleted one, or to NULL if the + * deleted element was the last one. */ +unsigned char *lpInsert(unsigned char *lp, unsigned char *elestr, unsigned char *eleint, + uint32_t size, unsigned char *p, int where, unsigned char **newp) +{ unsigned char intenc[LP_MAX_INT_ENCODING_LEN]; unsigned char backlen[LP_MAX_BACKLEN_SIZE]; uint64_t enclen; /* The length of the encoded element. */ + int delete = (elestr == NULL && eleint == NULL); - /* An element pointer set to NULL means deletion, which is conceptually - * replacing the element with a zero-length element. So whatever we - * get passed as 'where', set it to LP_REPLACE. */ - if (ele == NULL) where = LP_REPLACE; + /* when deletion, it is conceptually replacing the element with a + * zero-length element. So whatever we get passed as 'where', set + * it to LP_REPLACE. */ + if (delete) where = LP_REPLACE; /* If we need to insert after the current element, we just jump to the * next element (that could be the EOF one) and handle the case of @@ -674,17 +789,21 @@ unsigned char *lpInsert(unsigned char *lp, unsigned char *ele, uint32_t size, un * address again after a reallocation. */ unsigned long poff = p-lp; - /* Calling lpEncodeGetType() results into the encoded version of the - * element to be stored into 'intenc' in case it is representable as - * an integer: in that case, the function returns LP_ENCODING_INT. - * Otherwise if LP_ENCODING_STR is returned, we'll have to call - * lpEncodeString() to actually write the encoded string on place later. - * - * Whatever the returned encoding is, 'enclen' is populated with the - * length of the encoded element. */ int enctype; - if (ele) { - enctype = lpEncodeGetType(ele,size,intenc,&enclen); + if (elestr) { + /* Calling lpEncodeGetType() results into the encoded version of the + * element to be stored into 'intenc' in case it is representable as + * an integer: in that case, the function returns LP_ENCODING_INT. + * Otherwise if LP_ENCODING_STR is returned, we'll have to call + * lpEncodeString() to actually write the encoded string on place later. + * + * Whatever the returned encoding is, 'enclen' is populated with the + * length of the encoded element. */ + enctype = lpEncodeGetType(elestr,size,intenc,&enclen); + if (enctype == LP_ENCODING_INT) eleint = intenc; + } else if (eleint) { + enctype = LP_ENCODING_INT; + enclen = size; /* 'size' is the length of the encoded integer element. */ } else { enctype = -1; enclen = 0; @@ -693,7 +812,7 @@ unsigned char *lpInsert(unsigned char *lp, unsigned char *ele, uint32_t size, un /* We need to also encode the backward-parsable length of the element * and append it to the end: this allows to traverse the listpack from * the end to the start. */ - unsigned long backlen_size = ele ? lpEncodeBacklen(backlen,enclen) : 0; + unsigned long backlen_size = (!delete) ? lpEncodeBacklen(backlen,enclen) : 0; uint64_t old_listpack_bytes = lpGetTotalBytes(lp); uint32_t replaced_len = 0; if (where == LP_REPLACE) { @@ -743,13 +862,13 @@ unsigned char *lpInsert(unsigned char *lp, unsigned char *ele, uint32_t size, un *newp = dst; /* In case of deletion, set 'newp' to NULL if the next element is * the EOF element. */ - if (!ele && dst[0] == LP_EOF) *newp = NULL; + if (delete && dst[0] == LP_EOF) *newp = NULL; } - if (ele) { + if (!delete) { if (enctype == LP_ENCODING_INT) { - memcpy(dst,intenc,enclen); + memcpy(dst,eleint,enclen); } else { - lpEncodeString(dst,ele,size); + lpEncodeString(dst,elestr,size); } dst += enclen; memcpy(dst,backlen,backlen_size); @@ -757,10 +876,10 @@ unsigned char *lpInsert(unsigned char *lp, unsigned char *ele, uint32_t size, un } /* Update header. */ - if (where != LP_REPLACE || ele == NULL) { + if (where != LP_REPLACE || delete) { uint32_t num_elements = lpGetNumElements(lp); if (num_elements != LP_HDR_NUMELE_UNKNOWN) { - if (ele) + if (!delete) lpSetNumElements(lp,num_elements+1); else lpSetNumElements(lp,num_elements-1); @@ -790,13 +909,59 @@ unsigned char *lpInsert(unsigned char *lp, unsigned char *ele, uint32_t size, un return lp; } +/* This is just a wrapper for lpInsert() to directly use a 64 bit integer + * instead of a string. */ +unsigned char *lpInsertInteger(unsigned char *lp, long long lval, unsigned char *p, int where, unsigned char **newp) { + uint64_t enclen; /* The length of the encoded element. */ + unsigned char intenc[LP_MAX_INT_ENCODING_LEN]; + + lpEncodeIntegerGetType(lval, intenc, &enclen); + return lpInsert(lp, NULL, intenc, enclen, p, where, newp); +} + +/* Append the specified element 's' of length 'slen' at the head of the listpack. */ +unsigned char *lpPrepend(unsigned char *lp, unsigned char *s, uint32_t slen) { + unsigned char *p = lpFirst(lp); + if (!p) return lpAppend(lp, s, slen); + return lpInsert(lp, s, NULL, slen, p, LP_BEFORE, NULL); +} + +/* Append the specified integer element 'lval' at the head of the listpack. */ +unsigned char *lpPrependInteger(unsigned char *lp, long long lval) { + unsigned char *p = lpFirst(lp); + if (!p) return lpAppendInteger(lp, lval); + return lpInsertInteger(lp, lval, p, LP_BEFORE, NULL); +} + /* Append the specified element 'ele' of length 'len' at the end of the * listpack. It is implemented in terms of lpInsert(), so the return value is * the same as lpInsert(). */ unsigned char *lpAppend(unsigned char *lp, unsigned char *ele, uint32_t size) { uint64_t listpack_bytes = lpGetTotalBytes(lp); unsigned char *eofptr = lp + listpack_bytes - 1; - return lpInsert(lp,ele,size,eofptr,LP_BEFORE,NULL); + return lpInsert(lp,ele,NULL,size,eofptr,LP_BEFORE,NULL); +} + +/* Append the specified integer element 'lval' at the end of the listpack. */ +unsigned char *lpAppendInteger(unsigned char *lp, long long lval) { + uint64_t listpack_bytes = lpGetTotalBytes(lp); + unsigned char *eofptr = lp + listpack_bytes - 1; + return lpInsertInteger(lp, lval, eofptr, LP_BEFORE, NULL); +} + +/* This is just a wrapper for lpInsert() to directly use a string to replace + * the current element. The function returns the new listpack as return + * value, and also updates the current cursor by updating '*p'. */ +unsigned char *lpReplace(unsigned char *lp, unsigned char **p, unsigned char *s, uint32_t slen) { + return lpInsert(lp, s, NULL, slen, *p, LP_REPLACE, p); +} + +/* This is just a wrapper for lpInsertInteger() to directly use a 64 bit integer + * instead of a string to replace the current element. The function returns + * the new listpack as return value, and also updates the current cursor + * by updating '*p'. */ +unsigned char *lpReplaceInteger(unsigned char *lp, unsigned char **p, long long lval) { + return lpInsertInteger(lp, lval, *p, LP_REPLACE, p); } /* Remove the element pointed by 'p', and return the resulting listpack. @@ -804,11 +969,11 @@ unsigned char *lpAppend(unsigned char *lp, unsigned char *ele, uint32_t size) { * deleted one) is returned by reference. If the deleted element was the * last one, '*newp' is set to NULL. */ unsigned char *lpDelete(unsigned char *lp, unsigned char *p, unsigned char **newp) { - return lpInsert(lp,NULL,0,p,LP_REPLACE,newp); + return lpInsert(lp,NULL,NULL,0,p,LP_REPLACE,newp); } /* Return the total number of bytes the listpack is composed of. */ -uint32_t lpBytes(unsigned char *lp) { +size_t lpBytes(unsigned char *lp) { return lpGetTotalBytes(lp); } @@ -927,7 +1092,8 @@ static inline void lpAssertValidEntry(unsigned char* lp, size_t lpbytes, unsigne /* Validate the integrity of the data structure. * when `deep` is 0, only the integrity of the header is validated. * when `deep` is 1, we scan all the entries one by one. */ -int lpValidateIntegrity(unsigned char *lp, size_t size, int deep){ +int lpValidateIntegrity(unsigned char *lp, size_t size, int deep, + listpackValidateEntryCB entry_cb, void *cb_userdata) { /* Check that we can actually read the header. (and EOF) */ if (size < LP_HDR_SIZE + 1) return 0; @@ -948,8 +1114,17 @@ int lpValidateIntegrity(unsigned char *lp, size_t size, int deep){ uint32_t count = 0; unsigned char *p = lp + LP_HDR_SIZE; while(p && p[0] != LP_EOF) { + unsigned char *prev = p; + + /* Validate this entry and move to the next entry in advance + * to avoid callback crash due to corrupt listpack. */ if (!lpValidateNext(lp, &p, bytes)) return 0; + + /* Optionally let the caller validate the entry too. */ + if (entry_cb && !entry_cb(prev, cb_userdata)) + return 0; + count++; } @@ -960,3 +1135,826 @@ int lpValidateIntegrity(unsigned char *lp, size_t size, int deep){ return 1; } + +unsigned int lpCompare(unsigned char *p, unsigned char *s, uint32_t slen) { + unsigned char buf[LP_INTBUF_SIZE]; + unsigned char *value; + int64_t sz; + + if (p[0] == LP_EOF) return 0; + value = lpGet(p, &sz, buf); + return (slen == sz) && memcmp(value,s,slen) == 0; +} + +/* uint compare for qsort */ +static int uintCompare(const void *a, const void *b) { + return (*(unsigned int *) a - *(unsigned int *) b); +} + +/* Helper method to store a string into from val or lval into dest */ +static inline void lpSaveValue(unsigned char *val, unsigned int len, int64_t lval, listpackEntry *dest) { + dest->sval = val; + dest->slen = len; + dest->lval = lval; +} + +/* Randomly select a pair of key and value. + * total_count is a pre-computed length/2 of the listpack (to avoid calls to lpLength) + * 'key' and 'val' are used to store the result key value pair. + * 'val' can be NULL if the value is not needed. */ +void lpRandomPair(unsigned char *lp, unsigned long total_count, listpackEntry *key, listpackEntry *val) { + unsigned char *p; + + /* Avoid div by zero on corrupt listpack */ + assert(total_count); + + /* Generate even numbers, because listpack saved K-V pair */ + int r = (rand() % total_count) * 2; + assert((p = lpSeek(lp, r))); + key->sval = lpGetValue(p, &(key->slen), &(key->lval)); + + if (!val) + return; + assert((p = lpNext(lp, p))); + val->sval = lpGetValue(p, &(val->slen), &(val->lval)); +} + +/* Randomly select count of key value pairs and store into 'keys' and + * 'vals' args. The order of the picked entries is random, and the selections + * are non-unique (repetitions are possible). + * The 'vals' arg can be NULL in which case we skip these. */ +void lpRandomPairs(unsigned char *lp, unsigned int count, listpackEntry *keys, listpackEntry *vals) { + unsigned char *p, *key, *value; + unsigned int klen = 0, vlen = 0; + long long klval = 0, vlval = 0; + + /* Notice: the index member must be first due to the use in uintCompare */ + typedef struct { + unsigned int index; + unsigned int order; + } rand_pick; + rand_pick *picks = zmalloc(sizeof(rand_pick)*count); + unsigned int total_size = lpLength(lp)/2; + + /* Avoid div by zero on corrupt listpack */ + assert(total_size); + + /* create a pool of random indexes (some may be duplicate). */ + for (unsigned int i = 0; i < count; i++) { + picks[i].index = (rand() % total_size) * 2; /* Generate even indexes */ + /* keep track of the order we picked them */ + picks[i].order = i; + } + + /* sort by indexes. */ + qsort(picks, count, sizeof(rand_pick), uintCompare); + + /* fetch the elements form the listpack into a output array respecting the original order. */ + unsigned int lpindex = picks[0].index, pickindex = 0; + p = lpSeek(lp, lpindex); + while (p && pickindex < count) { + key = lpGetValue(p, &klen, &klval); + assert((p = lpNext(lp, p))); + value = lpGetValue(p, &vlen, &vlval); + while (pickindex < count && lpindex == picks[pickindex].index) { + int storeorder = picks[pickindex].order; + lpSaveValue(key, klen, klval, &keys[storeorder]); + if (vals) + lpSaveValue(value, vlen, vlval, &vals[storeorder]); + pickindex++; + } + lpindex += 2; + p = lpNext(lp, p); + } + + zfree(picks); +} + +/* Randomly select count of key value pairs and store into 'keys' and + * 'vals' args. The selections are unique (no repetitions), and the order of + * the picked entries is NOT-random. + * The 'vals' arg can be NULL in which case we skip these. + * The return value is the number of items picked which can be lower than the + * requested count if the listpack doesn't hold enough pairs. */ +unsigned int lpRandomPairsUnique(unsigned char *lp, unsigned int count, listpackEntry *keys, listpackEntry *vals) { + unsigned char *p, *key; + unsigned int klen = 0; + long long klval = 0; + unsigned int total_size = lpLength(lp)/2; + unsigned int index = 0; + if (count > total_size) + count = total_size; + + /* To only iterate once, every time we try to pick a member, the probability + * we pick it is the quotient of the count left we want to pick and the + * count still we haven't visited in the dict, this way, we could make every + * member be equally picked.*/ + p = lpFirst(lp); + unsigned int picked = 0, remaining = count; + while (picked < count && p) { + double randomDouble = ((double)rand()) / RAND_MAX; + double threshold = ((double)remaining) / (total_size - index); + if (randomDouble <= threshold) { + key = lpGetValue(p, &klen, &klval); + lpSaveValue(key, klen, klval, &keys[picked]); + assert((p = lpNext(lp, p))); + if (vals) { + key = lpGetValue(p, &klen, &klval); + lpSaveValue(key, klen, klval, &vals[picked]); + } + remaining--; + picked++; + } else { + assert((p = lpNext(lp, p))); + } + p = lpNext(lp, p); + index++; + } + return picked; +} + +#ifdef REDIS_TEST + +#include <sys/time.h> +#include "adlist.h" +#include "sds.h" + +#define UNUSED(x) (void)(x) +#define TEST(name) printf("test — %s\n", name); + +char *mixlist[] = {"hello", "foo", "quux", "1024"}; +char *intlist[] = {"4294967296", "-100", "100", "128000", + "non integer", "much much longer non integer"}; + +static unsigned char *createList() { + unsigned char *lp = lpNew(0); + lp = lpAppend(lp, (unsigned char*)mixlist[1], strlen(mixlist[1])); + lp = lpAppend(lp, (unsigned char*)mixlist[2], strlen(mixlist[2])); + lp = lpPrepend(lp, (unsigned char*)mixlist[0], strlen(mixlist[0])); + lp = lpAppend(lp, (unsigned char*)mixlist[3], strlen(mixlist[3])); + return lp; +} + +static unsigned char *createIntList() { + unsigned char *lp = lpNew(0); + lp = lpAppend(lp, (unsigned char*)intlist[2], strlen(intlist[2])); + lp = lpAppend(lp, (unsigned char*)intlist[3], strlen(intlist[3])); + lp = lpPrepend(lp, (unsigned char*)intlist[1], strlen(intlist[1])); + lp = lpPrepend(lp, (unsigned char*)intlist[0], strlen(intlist[0])); + lp = lpAppend(lp, (unsigned char*)intlist[4], strlen(intlist[4])); + lp = lpAppend(lp, (unsigned char*)intlist[5], strlen(intlist[5])); + return lp; +} + +static long long usec(void) { + struct timeval tv; + gettimeofday(&tv, NULL); + return (((long long)tv.tv_sec)*1000000)+tv.tv_usec; +} + +static void stress(int pos, int num, int maxsize, int dnum) { + int i, j, k; + unsigned char *lp; + char posstr[2][5] = { "HEAD", "TAIL" }; + long long start; + for (i = 0; i < maxsize; i+=dnum) { + lp = lpNew(0); + for (j = 0; j < i; j++) { + lp = lpAppend(lp, (unsigned char*)"quux", 4); + } + + /* Do num times a push+pop from pos */ + start = usec(); + for (k = 0; k < num; k++) { + if (pos == 0) { + lp = lpPrepend(lp, (unsigned char*)"quux", 4); + } else { + lp = lpAppend(lp, (unsigned char*)"quux", 4); + + } + lp = lpDelete(lp, lpFirst(lp), NULL); + } + printf("List size: %8d, bytes: %8zu, %dx push+pop (%s): %6lld usec\n", + i, lpBytes(lp), num, posstr[pos], usec()-start); + lpFree(lp); + } +} + +static unsigned char *pop(unsigned char *lp, int where) { + unsigned char *p, *vstr; + int64_t vlen; + + p = lpSeek(lp, where == 0 ? 0 : -1); + vstr = lpGet(p, &vlen, NULL); + if (where == 0) + printf("Pop head: "); + else + printf("Pop tail: "); + + if (vstr) { + if (vlen && fwrite(vstr, vlen, 1, stdout) == 0) perror("fwrite"); + } else { + printf("%lld", (long long)vlen); + } + + printf("\n"); + return lpDelete(lp, p, &p); +} + +static int randstring(char *target, unsigned int min, unsigned int max) { + int p = 0; + int 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; +} + +static void verifyEntry(unsigned char *p, unsigned char *s, size_t slen) { + assert(lpCompare(p, s, slen)); +} + +static int lpValidation(unsigned char *p, void *userdata) { + UNUSED(p); + + int ret; + long *count = userdata; + ret = lpCompare(p, (unsigned char *)mixlist[*count], strlen(mixlist[*count])); + (*count)++; + return ret; +} + +int listpackTest(int argc, char *argv[], int accurate) { + UNUSED(argc); + UNUSED(argv); + UNUSED(accurate); + + int i; + unsigned char *lp, *p, *vstr; + int64_t vlen; + unsigned char intbuf[LP_INTBUF_SIZE]; + + TEST("Create int list") { + lp = createIntList(); + assert(lpLength(lp) == 6); + lpFree(lp); + } + + TEST("Create list") { + lp = createList(); + assert(lpLength(lp) == 4); + lpFree(lp); + } + + TEST("Test lpPrepend") { + lp = lpNew(0); + lp = lpPrepend(lp, (unsigned char*)"abc", 3); + lp = lpPrepend(lp, (unsigned char*)"1024", 4); + verifyEntry(lpSeek(lp, 0), (unsigned char*)"1024", 4); + verifyEntry(lpSeek(lp, 1), (unsigned char*)"abc", 3); + lpFree(lp); + } + + TEST("Test lpPrependInteger") { + lp = lpNew(0); + lp = lpPrependInteger(lp, 127); + lp = lpPrependInteger(lp, 4095); + lp = lpPrependInteger(lp, 32767); + lp = lpPrependInteger(lp, 8388607); + lp = lpPrependInteger(lp, 2147483647); + lp = lpPrependInteger(lp, 9223372036854775807); + verifyEntry(lpSeek(lp, 0), (unsigned char*)"9223372036854775807", 19); + verifyEntry(lpSeek(lp, -1), (unsigned char*)"127", 3); + lpFree(lp); + } + + TEST("Get element at index") { + lp = createList(); + verifyEntry(lpSeek(lp, 0), (unsigned char*)"hello", 5); + verifyEntry(lpSeek(lp, 3), (unsigned char*)"1024", 4); + verifyEntry(lpSeek(lp, -1), (unsigned char*)"1024", 4); + verifyEntry(lpSeek(lp, -4), (unsigned char*)"hello", 5); + assert(lpSeek(lp, 4) == NULL); + assert(lpSeek(lp, -5) == NULL); + lpFree(lp); + } + + TEST("Pop list") { + lp = createList(); + lp = pop(lp, 1); + lp = pop(lp, 0); + lp = pop(lp, 1); + lp = pop(lp, 1); + lpFree(lp); + } + + TEST("Get element at index") { + lp = createList(); + verifyEntry(lpSeek(lp, 0), (unsigned char*)"hello", 5); + verifyEntry(lpSeek(lp, 3), (unsigned char*)"1024", 4); + verifyEntry(lpSeek(lp, -1), (unsigned char*)"1024", 4); + verifyEntry(lpSeek(lp, -4), (unsigned char*)"hello", 5); + assert(lpSeek(lp, 4) == NULL); + assert(lpSeek(lp, -5) == NULL); + lpFree(lp); + } + + TEST("Iterate list from 0 to end") { + lp = createList(); + p = lpFirst(lp); + i = 0; + while (p) { + verifyEntry(p, (unsigned char*)mixlist[i], strlen(mixlist[i])); + p = lpNext(lp, p); + i++; + } + lpFree(lp); + } + + TEST("Iterate list from 1 to end") { + lp = createList(); + i = 1; + p = lpSeek(lp, i); + while (p) { + verifyEntry(p, (unsigned char*)mixlist[i], strlen(mixlist[i])); + p = lpNext(lp, p); + i++; + } + lpFree(lp); + } + + TEST("Iterate list from 2 to end") { + lp = createList(); + i = 2; + p = lpSeek(lp, i); + while (p) { + verifyEntry(p, (unsigned char*)mixlist[i], strlen(mixlist[i])); + p = lpNext(lp, p); + i++; + } + lpFree(lp); + } + + TEST("Iterate from back to front") { + lp = createList(); + p = lpLast(lp); + i = 3; + while (p) { + verifyEntry(p, (unsigned char*)mixlist[i], strlen(mixlist[i])); + p = lpPrev(lp, p); + i--; + } + lpFree(lp); + } + + TEST("Iterate from back to front, deleting all items") { + lp = createList(); + p = lpLast(lp); + i = 3; + while ((p = lpLast(lp))) { + verifyEntry(p, (unsigned char*)mixlist[i], strlen(mixlist[i])); + lp = lpDelete(lp, p, &p); + assert(p == NULL); + i--; + } + lpFree(lp); + } + + TEST("Delete foo while iterating") { + lp = createList(); + p = lpFirst(lp); + while (p) { + if (lpCompare(p, (unsigned char*)"foo", 3)) { + lp = lpDelete(lp, p, &p); + } else { + p = lpNext(lp, p); + } + } + lpFree(lp); + } + + TEST("Replace with same size") { + lp = createList(); /* "hello", "foo", "quux", "1024" */ + unsigned char *orig_lp = lp; + p = lpSeek(lp, 0); + lp = lpReplace(lp, &p, (unsigned char*)"zoink", 5); + p = lpSeek(lp, 3); + lp = lpReplace(lp, &p, (unsigned char*)"y", 1); + p = lpSeek(lp, 1); + lp = lpReplace(lp, &p, (unsigned char*)"65536", 5); + p = lpSeek(lp, 0); + assert(!memcmp((char*)p, + "\x85zoink\x06" + "\xf2\x00\x00\x01\x04" /* 65536 as int24 */ + "\x84quux\05" "\x81y\x02" "\xff", + 22)); + assert(lp == orig_lp); /* no reallocations have happened */ + lpFree(lp); + } + + TEST("Replace with different size") { + lp = createList(); /* "hello", "foo", "quux", "1024" */ + p = lpSeek(lp, 1); + lp = lpReplace(lp, &p, (unsigned char*)"squirrel", 8); + p = lpSeek(lp, 0); + assert(!strncmp((char*)p, + "\x85hello\x06" "\x88squirrel\x09" "\x84quux\x05" + "\xc4\x00\x02" "\xff", + 27)); + lpFree(lp); + } + + TEST("Regression test for >255 byte strings") { + char v1[257] = {0}, v2[257] = {0}; + memset(v1,'x',256); + memset(v2,'y',256); + lp = lpNew(0); + lp = lpAppend(lp, (unsigned char*)v1 ,strlen(v1)); + lp = lpAppend(lp, (unsigned char*)v2 ,strlen(v2)); + + /* Pop values again and compare their value. */ + p = lpFirst(lp); + vstr = lpGet(p, &vlen, NULL); + assert(strncmp(v1, (char*)vstr, vlen) == 0); + p = lpSeek(lp, 1); + vstr = lpGet(p, &vlen, NULL); + assert(strncmp(v2, (char*)vstr, vlen) == 0); + lpFree(lp); + } + + TEST("Create long list and check indices") { + lp = lpNew(0); + char buf[32]; + int i,len; + for (i = 0; i < 1000; i++) { + len = sprintf(buf, "%d", i); + lp = lpAppend(lp, (unsigned char*)buf, len); + } + for (i = 0; i < 1000; i++) { + p = lpSeek(lp, i); + vstr = lpGet(p, &vlen, NULL); + assert(i == vlen); + + p = lpSeek(lp, -i-1); + vstr = lpGet(p, &vlen, NULL); + assert(999-i == vlen); + } + lpFree(lp); + } + + TEST("Compare strings with listpack entries") { + lp = createList(); + p = lpSeek(lp,0); + assert(lpCompare(p,(unsigned char*)"hello",5)); + assert(!lpCompare(p,(unsigned char*)"hella",5)); + + p = lpSeek(lp,3); + assert(lpCompare(p,(unsigned char*)"1024",4)); + assert(!lpCompare(p,(unsigned char*)"1025",4)); + lpFree(lp); + } + + TEST("Random pair with one element") { + listpackEntry key, val; + unsigned char *lp = lpNew(0); + lp = lpAppend(lp, (unsigned char*)"abc", 3); + lp = lpAppend(lp, (unsigned char*)"123", 3); + lpRandomPair(lp, 1, &key, &val); + assert(memcmp(key.sval, "abc", key.slen) == 0); + assert(val.lval == 123); + lpFree(lp); + } + + TEST("Random pair with many elements") { + listpackEntry key, val; + unsigned char *lp = lpNew(0); + lp = lpAppend(lp, (unsigned char*)"abc", 3); + lp = lpAppend(lp, (unsigned char*)"123", 3); + lp = lpAppend(lp, (unsigned char*)"456", 3); + lp = lpAppend(lp, (unsigned char*)"def", 3); + lpRandomPair(lp, 2, &key, &val); + if (key.sval) { + assert(!memcmp(key.sval, "abc", key.slen)); + assert(key.slen == 3); + assert(val.lval == 123); + } + if (!key.sval) { + assert(key.lval == 456); + assert(!memcmp(val.sval, "def", val.slen)); + } + lpFree(lp); + } + + TEST("Random pairs with one element") { + int count = 5; + unsigned char *lp = lpNew(0); + listpackEntry *keys = zmalloc(sizeof(listpackEntry) * count); + listpackEntry *vals = zmalloc(sizeof(listpackEntry) * count); + + lp = lpAppend(lp, (unsigned char*)"abc", 3); + lp = lpAppend(lp, (unsigned char*)"123", 3); + lpRandomPairs(lp, count, keys, vals); + assert(memcmp(keys[4].sval, "abc", keys[4].slen) == 0); + assert(vals[4].lval == 123); + zfree(keys); + zfree(vals); + lpFree(lp); + } + + TEST("Random pairs with many elements") { + int count = 5; + lp = lpNew(0); + listpackEntry *keys = zmalloc(sizeof(listpackEntry) * count); + listpackEntry *vals = zmalloc(sizeof(listpackEntry) * count); + + lp = lpAppend(lp, (unsigned char*)"abc", 3); + lp = lpAppend(lp, (unsigned char*)"123", 3); + lp = lpAppend(lp, (unsigned char*)"456", 3); + lp = lpAppend(lp, (unsigned char*)"def", 3); + lpRandomPairs(lp, count, keys, vals); + for (int i = 0; i < count; i++) { + if (keys[i].sval) { + assert(!memcmp(keys[i].sval, "abc", keys[i].slen)); + assert(keys[i].slen == 3); + assert(vals[i].lval == 123); + } + if (!keys[i].sval) { + assert(keys[i].lval == 456); + assert(!memcmp(vals[i].sval, "def", vals[i].slen)); + } + } + zfree(keys); + zfree(vals); + lpFree(lp); + } + + TEST("Random pairs unique with one element") { + unsigned picked; + int count = 5; + lp = lpNew(0); + listpackEntry *keys = zmalloc(sizeof(listpackEntry) * count); + listpackEntry *vals = zmalloc(sizeof(listpackEntry) * count); + + lp = lpAppend(lp, (unsigned char*)"abc", 3); + lp = lpAppend(lp, (unsigned char*)"123", 3); + picked = lpRandomPairsUnique(lp, count, keys, vals); + assert(picked == 1); + assert(memcmp(keys[0].sval, "abc", keys[0].slen) == 0); + assert(vals[0].lval == 123); + zfree(keys); + zfree(vals); + lpFree(lp); + } + + TEST("Random pairs unique with many elements") { + unsigned picked; + int count = 5; + lp = lpNew(0); + listpackEntry *keys = zmalloc(sizeof(listpackEntry) * count); + listpackEntry *vals = zmalloc(sizeof(listpackEntry) * count); + + lp = lpAppend(lp, (unsigned char*)"abc", 3); + lp = lpAppend(lp, (unsigned char*)"123", 3); + lp = lpAppend(lp, (unsigned char*)"456", 3); + lp = lpAppend(lp, (unsigned char*)"def", 3); + picked = lpRandomPairsUnique(lp, count, keys, vals); + assert(picked == 2); + for (int i = 0; i < 2; i++) { + if (keys[i].sval) { + assert(!memcmp(keys[i].sval, "abc", keys[i].slen)); + assert(keys[i].slen == 3); + assert(vals[i].lval == 123); + } + if (!keys[i].sval) { + assert(keys[i].lval == 456); + assert(!memcmp(vals[i].sval, "def", vals[i].slen)); + } + } + zfree(keys); + zfree(vals); + lpFree(lp); + } + + TEST("push various encodings") { + lp = lpNew(0); + + /* Push integer encode element using lpAppend */ + lp = lpAppend(lp, (unsigned char*)"127", 3); + assert(LP_ENCODING_IS_7BIT_UINT(lpLast(lp)[0])); + lp = lpAppend(lp, (unsigned char*)"4095", 4); + assert(LP_ENCODING_IS_13BIT_INT(lpLast(lp)[0])); + lp = lpAppend(lp, (unsigned char*)"32767", 5); + assert(LP_ENCODING_IS_16BIT_INT(lpLast(lp)[0])); + lp = lpAppend(lp, (unsigned char*)"8388607", 7); + assert(LP_ENCODING_IS_24BIT_INT(lpLast(lp)[0])); + lp = lpAppend(lp, (unsigned char*)"2147483647", 10); + assert(LP_ENCODING_IS_32BIT_INT(lpLast(lp)[0])); + lp = lpAppend(lp, (unsigned char*)"9223372036854775807", 19); + assert(LP_ENCODING_IS_64BIT_INT(lpLast(lp)[0])); + + /* Push integer encode element using lpAppendInteger */ + lp = lpAppendInteger(lp, 127); + assert(LP_ENCODING_IS_7BIT_UINT(lpLast(lp)[0])); + verifyEntry(lpLast(lp), (unsigned char*)"127", 3); + lp = lpAppendInteger(lp, 4095); + verifyEntry(lpLast(lp), (unsigned char*)"4095", 4); + assert(LP_ENCODING_IS_13BIT_INT(lpLast(lp)[0])); + lp = lpAppendInteger(lp, 32767); + verifyEntry(lpLast(lp), (unsigned char*)"32767", 5); + assert(LP_ENCODING_IS_16BIT_INT(lpLast(lp)[0])); + lp = lpAppendInteger(lp, 8388607); + verifyEntry(lpLast(lp), (unsigned char*)"8388607", 7); + assert(LP_ENCODING_IS_24BIT_INT(lpLast(lp)[0])); + lp = lpAppendInteger(lp, 2147483647); + verifyEntry(lpLast(lp), (unsigned char*)"2147483647", 10); + assert(LP_ENCODING_IS_32BIT_INT(lpLast(lp)[0])); + lp = lpAppendInteger(lp, 9223372036854775807); + verifyEntry(lpLast(lp), (unsigned char*)"9223372036854775807", 19); + assert(LP_ENCODING_IS_64BIT_INT(lpLast(lp)[0])); + + /* string encode */ + unsigned char *str = zmalloc(65535); + memset(str, 0, 65535); + lp = lpAppend(lp, (unsigned char*)str, 63); + assert(LP_ENCODING_IS_6BIT_STR(lpLast(lp)[0])); + lp = lpAppend(lp, (unsigned char*)str, 4095); + assert(LP_ENCODING_IS_12BIT_STR(lpLast(lp)[0])); + lp = lpAppend(lp, (unsigned char*)str, 65535); + assert(LP_ENCODING_IS_32BIT_STR(lpLast(lp)[0])); + zfree(str); + lpFree(lp); + } + + TEST("Test lpFind") { + lp = createList(); + assert(lpFind(lp, lpFirst(lp), (unsigned char*)"abc", 3, 0) == NULL); + verifyEntry(lpFind(lp, lpFirst(lp), (unsigned char*)"hello", 5, 0), (unsigned char*)"hello", 5); + verifyEntry(lpFind(lp, lpFirst(lp), (unsigned char*)"1024", 4, 0), (unsigned char*)"1024", 4); + lpFree(lp); + } + + TEST("Test lpValidateIntegrity") { + lp = createList(); + long count = 0; + assert(lpValidateIntegrity(lp, lpBytes(lp), 1, lpValidation, &count) == 1); + lpFree(lp); + } + + TEST("Stress with random payloads of different encoding") { + unsigned long long start = usec(); + int i,j,len,where; + unsigned char *p; + char buf[1024]; + int buflen; + list *ref; + listNode *refnode; + + int iteration = accurate ? 20000 : 20; + for (i = 0; i < iteration; i++) { + lp = lpNew(0); + ref = listCreate(); + listSetFreeMethod(ref,(void (*)(void*))sdsfree); + len = rand() % 256; + + /* Create lists */ + for (j = 0; j < len; j++) { + where = (rand() & 1) ? 0 : 1; + 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 listpack */ + if (where == 0) { + lp = lpPrepend(lp, (unsigned char*)buf, buflen); + } else { + lp = lpAppend(lp, (unsigned char*)buf, buflen); + } + + /* Add to reference list */ + if (where == 0) { + listAddNodeHead(ref,sdsnewlen(buf, buflen)); + } else if (where == 1) { + listAddNodeTail(ref,sdsnewlen(buf, buflen)); + } else { + assert(NULL); + } + } + + assert(listLength(ref) == lpLength(lp)); + for (j = 0; j < len; j++) { + /* Naive way to get elements, but similar to the stresser + * executed from the Tcl test suite. */ + p = lpSeek(lp,j); + refnode = listIndex(ref,j); + + vstr = lpGet(p, &vlen, intbuf); + assert(memcmp(vstr,listNodeValue(refnode),vlen) == 0); + } + lpFree(lp); + listRelease(ref); + } + printf("Done. usec=%lld\n\n", usec()-start); + } + + TEST("Stress with variable listpack size") { + unsigned long long start = usec(); + int maxsize = accurate ? 16384 : 16; + stress(0,100000,maxsize,256); + stress(1,100000,maxsize,256); + printf("Done. usec=%lld\n\n", usec()-start); + } + + /* Benchmarks */ + { + int iteration = accurate ? 100000 : 100; + lp = lpNew(0); + TEST("Benchmark lpAppend") { + unsigned long long start = usec(); + for (int i=0; i<iteration; i++) { + char buf[4096] = "asdf"; + lp = lpAppend(lp, (unsigned char*)buf, 4); + lp = lpAppend(lp, (unsigned char*)buf, 40); + lp = lpAppend(lp, (unsigned char*)buf, 400); + lp = lpAppend(lp, (unsigned char*)buf, 4000); + lp = lpAppend(lp, (unsigned char*)"1", 1); + lp = lpAppend(lp, (unsigned char*)"10", 2); + lp = lpAppend(lp, (unsigned char*)"100", 3); + lp = lpAppend(lp, (unsigned char*)"1000", 4); + lp = lpAppend(lp, (unsigned char*)"10000", 5); + lp = lpAppend(lp, (unsigned char*)"100000", 6); + } + printf("Done. usec=%lld\n", usec()-start); + } + + TEST("Benchmark lpFind string") { + unsigned long long start = usec(); + for (int i = 0; i < 2000; i++) { + unsigned char *fptr = lpFirst(lp); + fptr = lpFind(lp, fptr, (unsigned char*)"nothing", 7, 1); + } + printf("Done. usec=%lld\n", usec()-start); + } + + TEST("Benchmark lpFind number") { + unsigned long long start = usec(); + for (int i = 0; i < 2000; i++) { + unsigned char *fptr = lpFirst(lp); + fptr = lpFind(lp, fptr, (unsigned char*)"99999", 5, 1); + } + printf("Done. usec=%lld\n", usec()-start); + } + + TEST("Benchmark lpSeek") { + unsigned long long start = usec(); + for (int i = 0; i < 2000; i++) { + lpSeek(lp, 99999); + } + printf("Done. usec=%lld\n", usec()-start); + } + + TEST("Benchmark lpValidateIntegrity") { + unsigned long long start = usec(); + for (int i = 0; i < 2000; i++) { + lpValidateIntegrity(lp, lpBytes(lp), 1, NULL, NULL); + } + printf("Done. usec=%lld\n", usec()-start); + } + + lpFree(lp); + } + + return 0; +} + +#endif |