summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorsundb <sundbcn@gmail.com>2021-09-09 23:18:53 +0800
committerGitHub <noreply@github.com>2021-09-09 18:18:53 +0300
commit3ca6972ecd3e9963f65b9cb1ff050ad60f03563e (patch)
tree9f82d9d622f5d161bc0d72c83f8f31555f5a652d
parent86b0de5c41c96225377b83090fbdbe0209c2d9b9 (diff)
downloadredis-3ca6972ecd3e9963f65b9cb1ff050ad60f03563e.tar.gz
Replace all usage of ziplist with listpack for t_zset (#9366)
Part two of implementing #8702 (zset), after #8887. ## Description of the feature Replaced all uses of ziplist with listpack in t_zset, and optimized some of the code to optimize performance. ## Rdb format changes New `RDB_TYPE_ZSET_LISTPACK` rdb type. ## Rdb loading improvements: 1) Pre-expansion of dict for validation of duplicate data for listpack and ziplist. 2) Simplifying the release of empty key objects when RDB loading. 3) Unify ziplist and listpack data verify methods for zset and hash, and move code to rdb.c. ## Interface changes 1) New `zset-max-listpack-entries` config is an alias for `zset-max-ziplist-entries` (same with `zset-max-listpack-value`). 2) OBJECT ENCODING will return listpack instead of ziplist. ## Listpack improvements: 1) Add `lpDeleteRange` and `lpDeleteRangeWithEntry` functions to delete a range of entries from listpack. 2) Improve the performance of `lpCompare`, converting from string to integer is faster than converting from integer to string. 3) Replace `snprintf` with `ll2string` to improve performance in converting numbers to strings in `lpGet()`. ## Zset improvements: 1) Improve the performance of `zzlFind` method, use `lpFind` instead of `lpCompare` in a loop. 2) Use `lpDeleteRangeWithEntry` instead of `lpDelete` twice to delete a element of zset. ## Tests 1) Add some unittests for `lpDeleteRange` and `lpDeleteRangeWithEntry` function. 2) Add zset RDB loading test. 3) Add benchmark test for `lpCompare` and `ziplsitCompare`. 4) Add empty listpack zset corrupt dump test.
Diffstat
-rw-r--r--redis.conf4
-rw-r--r--src/aof.c8
-rw-r--r--src/config.c4
-rw-r--r--src/db.c16
-rw-r--r--src/debug.c8
-rw-r--r--src/defrag.c2
-rw-r--r--src/geo.c9
-rw-r--r--src/listpack.c251
-rw-r--r--src/listpack.h6
-rw-r--r--src/module.c38
-rw-r--r--src/object.c16
-rw-r--r--src/rdb.c176
-rw-r--r--src/rdb.h3
-rw-r--r--src/redis-check-rdb.c1
-rw-r--r--src/server.h13
-rw-r--r--src/t_hash.c112
-rw-r--r--src/t_zset.c369
-rw-r--r--src/ziplist.c30
-rw-r--r--src/ziplist.h2
-rw-r--r--tests/assets/corrupt_empty_keys.rdbbin261 -> 280 bytes
-rw-r--r--tests/assets/zset-ziplist.rdbbin0 -> 135 bytes
-rw-r--r--tests/integration/convert-ziplist-zset-on-load.tcl28
-rw-r--r--tests/integration/corrupt-dump.tcl22
-rw-r--r--tests/test_helper.tcl1
-rw-r--r--tests/unit/aofrw.tcl4
-rw-r--r--tests/unit/keyspace.tcl4
-rw-r--r--tests/unit/scan.tcl4
-rw-r--r--tests/unit/type/zset.tcl12
28 files changed, 688 insertions, 455 deletions
diff --git a/redis.conf b/redis.conf
index 09107dcea..6d5acd4fb 100644
--- a/redis.conf
+++ b/redis.conf
@@ -1748,8 +1748,8 @@ set-max-intset-entries 512
# Similarly to hashes and lists, sorted sets are also specially encoded in
# order to save a lot of space. This encoding is only used when the length and
# elements of a sorted set are below the following limits:
-zset-max-ziplist-entries 128
-zset-max-ziplist-value 64
+zset-max-listpack-entries 128
+zset-max-listpack-value 64
# HyperLogLog sparse representation bytes limit. The limit includes the
# 16 bytes header. When an HyperLogLog using the sparse representation crosses
diff --git a/src/aof.c b/src/aof.c
index 2663b4f7e..defc4d24b 100644
--- a/src/aof.c
+++ b/src/aof.c
@@ -1023,7 +1023,7 @@ int rewriteSetObject(rio *r, robj *key, robj *o) {
int rewriteSortedSetObject(rio *r, robj *key, robj *o) {
long long count = 0, items = zsetLength(o);
- if (o->encoding == OBJ_ENCODING_ZIPLIST) {
+ if (o->encoding == OBJ_ENCODING_LISTPACK) {
unsigned char *zl = o->ptr;
unsigned char *eptr, *sptr;
unsigned char *vstr;
@@ -1031,13 +1031,13 @@ int rewriteSortedSetObject(rio *r, robj *key, robj *o) {
long long vll;
double score;
- eptr = ziplistIndex(zl,0);
+ eptr = lpSeek(zl,0);
serverAssert(eptr != NULL);
- sptr = ziplistNext(zl,eptr);
+ sptr = lpNext(zl,eptr);
serverAssert(sptr != NULL);
while (eptr != NULL) {
- serverAssert(ziplistGet(eptr,&vstr,&vlen,&vll));
+ vstr = lpGetValue(eptr,&vlen,&vll);
score = zzlGetScore(sptr);
if (count == 0) {
diff --git a/src/config.c b/src/config.c
index 957c20fc2..349021f9e 100644
--- a/src/config.c
+++ b/src/config.c
@@ -2645,11 +2645,11 @@ standardConfig configs[] = {
/* Size_t configs */
createSizeTConfig("hash-max-listpack-entries", "hash-max-ziplist-entries", MODIFIABLE_CONFIG, 0, LONG_MAX, server.hash_max_listpack_entries, 512, INTEGER_CONFIG, NULL, NULL),
createSizeTConfig("set-max-intset-entries", NULL, MODIFIABLE_CONFIG, 0, LONG_MAX, server.set_max_intset_entries, 512, INTEGER_CONFIG, NULL, NULL),
- createSizeTConfig("zset-max-ziplist-entries", NULL, MODIFIABLE_CONFIG, 0, LONG_MAX, server.zset_max_ziplist_entries, 128, INTEGER_CONFIG, NULL, NULL),
+ createSizeTConfig("zset-max-listpack-entries", "zset-max-ziplist-entries", MODIFIABLE_CONFIG, 0, LONG_MAX, server.zset_max_listpack_entries, 128, INTEGER_CONFIG, NULL, NULL),
createSizeTConfig("active-defrag-ignore-bytes", NULL, MODIFIABLE_CONFIG, 1, LLONG_MAX, server.active_defrag_ignore_bytes, 100<<20, MEMORY_CONFIG, NULL, NULL), /* Default: don't defrag if frag overhead is below 100mb */
createSizeTConfig("hash-max-listpack-value", "hash-max-ziplist-value", MODIFIABLE_CONFIG, 0, LONG_MAX, server.hash_max_listpack_value, 64, MEMORY_CONFIG, NULL, NULL),
createSizeTConfig("stream-node-max-bytes", NULL, MODIFIABLE_CONFIG, 0, LONG_MAX, server.stream_node_max_bytes, 4096, MEMORY_CONFIG, NULL, NULL),
- createSizeTConfig("zset-max-ziplist-value", NULL, MODIFIABLE_CONFIG, 0, LONG_MAX, server.zset_max_ziplist_value, 64, MEMORY_CONFIG, NULL, NULL),
+ createSizeTConfig("zset-max-listpack-value", "zset-max-ziplist-value", MODIFIABLE_CONFIG, 0, LONG_MAX, server.zset_max_listpack_value, 64, MEMORY_CONFIG, NULL, NULL),
createSizeTConfig("hll-sparse-max-bytes", NULL, MODIFIABLE_CONFIG, 0, LONG_MAX, server.hll_sparse_max_bytes, 3000, MEMORY_CONFIG, NULL, NULL),
createSizeTConfig("tracking-table-max-keys", NULL, MODIFIABLE_CONFIG, 0, LONG_MAX, server.tracking_table_max_keys, 1000000, INTEGER_CONFIG, NULL, NULL), /* Default: 1 million keys max. */
createSizeTConfig("client-query-buffer-limit", NULL, DEBUG_CONFIG | MODIFIABLE_CONFIG, 1024*1024, LONG_MAX, server.client_max_querybuf_len, 1024*1024*1024, MEMORY_CONFIG, NULL, NULL), /* Default: 1GB max query buffer. */
diff --git a/src/db.c b/src/db.c
index ba2c24348..5be1aeb88 100644
--- a/src/db.c
+++ b/src/db.c
@@ -914,21 +914,7 @@ void scanGenericCommand(client *c, robj *o, unsigned long cursor) {
while(intsetGet(o->ptr,pos++,&ll))
listAddNodeTail(keys,createStringObjectFromLongLong(ll));
cursor = 0;
- } else if (o->type == OBJ_ZSET) {
- unsigned char *p = ziplistIndex(o->ptr,0);
- unsigned char *vstr;
- unsigned int vlen;
- long long vll;
-
- while(p) {
- ziplistGet(p,&vstr,&vlen,&vll);
- listAddNodeTail(keys,
- (vstr != NULL) ? createStringObject((char*)vstr,vlen) :
- createStringObjectFromLongLong(vll));
- p = ziplistNext(o->ptr,p);
- }
- cursor = 0;
- } else if (o->type == OBJ_HASH) {
+ } else if (o->type == OBJ_HASH || o->type == OBJ_ZSET) {
unsigned char *p = lpFirst(o->ptr);
unsigned char *vstr;
int64_t vlen;
diff --git a/src/debug.c b/src/debug.c
index 817ec0894..d29d48673 100644
--- a/src/debug.c
+++ b/src/debug.c
@@ -162,7 +162,7 @@ void xorObjectDigest(redisDb *db, robj *keyobj, unsigned char *digest, robj *o)
} else if (o->type == OBJ_ZSET) {
unsigned char eledigest[20];
- if (o->encoding == OBJ_ENCODING_ZIPLIST) {
+ if (o->encoding == OBJ_ENCODING_LISTPACK) {
unsigned char *zl = o->ptr;
unsigned char *eptr, *sptr;
unsigned char *vstr;
@@ -170,13 +170,13 @@ void xorObjectDigest(redisDb *db, robj *keyobj, unsigned char *digest, robj *o)
long long vll;
double score;
- eptr = ziplistIndex(zl,0);
+ eptr = lpSeek(zl,0);
serverAssert(eptr != NULL);
- sptr = ziplistNext(zl,eptr);
+ sptr = lpNext(zl,eptr);
serverAssert(sptr != NULL);
while (eptr != NULL) {
- serverAssert(ziplistGet(eptr,&vstr,&vlen,&vll));
+ vstr = lpGetValue(eptr,&vlen,&vll);
score = zzlGetScore(sptr);
memset(eledigest,0,20);
diff --git a/src/defrag.c b/src/defrag.c
index d59a4c5b5..fe2a0585e 100644
--- a/src/defrag.c
+++ b/src/defrag.c
@@ -856,7 +856,7 @@ long defragKey(redisDb *db, dictEntry *de) {
serverPanic("Unknown set encoding");
}
} else if (ob->type == OBJ_ZSET) {
- if (ob->encoding == OBJ_ENCODING_ZIPLIST) {
+ if (ob->encoding == OBJ_ENCODING_LISTPACK) {
if ((newzl = activeDefragAlloc(ob->ptr)))
defragged++, ob->ptr = newzl;
} else if (ob->encoding == OBJ_ENCODING_SKIPLIST) {
diff --git a/src/geo.c b/src/geo.c
index 8c541bcfa..507a287c6 100644
--- a/src/geo.c
+++ b/src/geo.c
@@ -259,7 +259,7 @@ int geoGetPointsInRange(robj *zobj, double min, double max, GeoShape *shape, geo
size_t origincount = ga->used;
sds member;
- if (zobj->encoding == OBJ_ENCODING_ZIPLIST) {
+ if (zobj->encoding == OBJ_ENCODING_LISTPACK) {
unsigned char *zl = zobj->ptr;
unsigned char *eptr, *sptr;
unsigned char *vstr = NULL;
@@ -272,7 +272,7 @@ int geoGetPointsInRange(robj *zobj, double min, double max, GeoShape *shape, geo
return 0;
}
- sptr = ziplistNext(zl, eptr);
+ sptr = lpNext(zl, eptr);
while (eptr) {
score = zzlGetScore(sptr);
@@ -280,8 +280,7 @@ int geoGetPointsInRange(robj *zobj, double min, double max, GeoShape *shape, geo
if (!zslValueLteMax(score, &range))
break;
- /* We know the element exists. ziplistGet should always succeed */
- ziplistGet(eptr, &vstr, &vlen, &vlong);
+ vstr = lpGetValue(eptr, &vlen, &vlong);
member = (vstr == NULL) ? sdsfromlonglong(vlong) :
sdsnewlen(vstr,vlen);
if (geoAppendIfWithinShape(ga,shape,score,member)
@@ -819,7 +818,7 @@ void georadiusGeneric(client *c, int srcKeyIndex, int flags) {
}
if (returned_items) {
- zsetConvertToZiplistIfNeeded(zobj,maxelelen);
+ zsetConvertToListpackIfNeeded(zobj,maxelelen);
setKey(c,c->db,storekey,zobj);
decrRefCount(zobj);
notifyKeyspaceEvent(NOTIFY_ZSET,flags & GEOSEARCH ? "geosearchstore" : "georadiusstore",storekey,
diff --git a/src/listpack.c b/src/listpack.c
index 9bb1c8c95..1849a5479 100644
--- a/src/listpack.c
+++ b/src/listpack.c
@@ -43,6 +43,7 @@
#include "listpack.h"
#include "listpack_malloc.h"
#include "redisassert.h"
+#include "util.h"
#define LP_HDR_SIZE 6 /* 32 bit total len + 16 bit number of elements. */
#define LP_HDR_NUMELE_UNKNOWN UINT16_MAX
@@ -642,7 +643,7 @@ static inline unsigned char *lpGetWithSize(unsigned char *p, int64_t *count, uns
/* Return the string representation of the integer or the value itself
* depending on intbuf being NULL or not. */
if (intbuf) {
- *count = snprintf((char*)intbuf,LP_INTBUF_SIZE,"%lld",(long long)val);
+ *count = ll2string((char*)intbuf,LP_INTBUF_SIZE,(long long)val);
return intbuf;
} else {
*count = val;
@@ -909,6 +910,13 @@ unsigned char *lpInsert(unsigned char *lp, unsigned char *elestr, unsigned char
return lp;
}
+/* This is just a wrapper for lpInsert() to directly use a string. */
+unsigned char *lpInsertString(unsigned char *lp, unsigned char *s, uint32_t slen,
+ unsigned char *p, int where, unsigned char **newp)
+{
+ return lpInsert(lp, s, NULL, slen, p, where, newp);
+}
+
/* 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) {
@@ -972,6 +980,73 @@ unsigned char *lpDelete(unsigned char *lp, unsigned char *p, unsigned char **new
return lpInsert(lp,NULL,NULL,0,p,LP_REPLACE,newp);
}
+/* Delete a range of entries from the listpack start with the element pointed by 'p'. */
+unsigned char *lpDeleteRangeWithEntry(unsigned char *lp, unsigned char **p, unsigned long num) {
+ size_t bytes = lpBytes(lp);
+ unsigned long deleted = 0;
+ unsigned char *eofptr = lp + bytes - 1;
+ unsigned char *first, *tail;
+ first = tail = *p;
+
+ if (num == 0) return lp; /* Nothing to delete, return ASAP. */
+
+ /* Find the next entry to the last entry that needs to be deleted.
+ * lpLength may be unreliable due to corrupt data, so we cannot
+ * treat 'num' as the number of elements to be deleted. */
+ while (num--) {
+ deleted++;
+ tail = lpSkip(tail);
+ if (tail[0] == LP_EOF) break;
+ lpAssertValidEntry(lp, bytes, tail);
+ }
+
+ /* Store the offset of the element 'first', so that we can obtain its
+ * address again after a reallocation. */
+ unsigned long poff = first-lp;
+
+ /* Move tail to the front of the ziplist */
+ memmove(first, tail, eofptr - tail + 1);
+ lpSetTotalBytes(lp, bytes - (tail - first));
+ uint32_t numele = lpGetNumElements(lp);
+ if (numele != LP_HDR_NUMELE_UNKNOWN)
+ lpSetNumElements(lp, numele-deleted);
+ lp = lpShrinkToFit(lp);
+
+ /* Store the entry. */
+ *p = lp+poff;
+ if ((*p)[0] == LP_EOF) *p = NULL;
+
+ return lp;
+}
+
+/* Delete a range of entries from the listpack. */
+unsigned char *lpDeleteRange(unsigned char *lp, long index, unsigned long num) {
+ unsigned char *p;
+ uint32_t numele = lpGetNumElements(lp);
+
+ if (num == 0) return lp; /* Nothing to delete, return ASAP. */
+ if ((p = lpSeek(lp, index)) == NULL) return lp;
+
+ /* If we know we're gonna delete beyond the end of the listpack, we can just move
+ * the EOF marker, and there's no need to iterate through the entries,
+ * but if we can't be sure how many entries there are, we rather avoid calling lpLength
+ * since that means an additional iteration on all elements.
+ *
+ * Note that index could overflow, but we use the value after seek, so when we
+ * use it no overflow happens. */
+ if (numele != LP_HDR_NUMELE_UNKNOWN && index < 0) index = (long)numele + index;
+ if (numele != LP_HDR_NUMELE_UNKNOWN && (numele - (unsigned long)index) <= num) {
+ p[0] = LP_EOF;
+ lpSetTotalBytes(lp, p - lp + 1);
+ lpSetNumElements(lp, index);
+ lp = lpShrinkToFit(lp);
+ } else {
+ lp = lpDeleteRangeWithEntry(lp, &p, num);
+ }
+
+ return lp;
+}
+
/* Return the total number of bytes the listpack is composed of. */
size_t lpBytes(unsigned char *lp) {
return lpGetTotalBytes(lp);
@@ -1112,6 +1187,7 @@ int lpValidateIntegrity(unsigned char *lp, size_t size, int deep,
/* Validate the individual entries. */
uint32_t count = 0;
+ uint32_t numele = lpGetNumElements(lp);
unsigned char *p = lp + LP_HDR_SIZE;
while(p && p[0] != LP_EOF) {
unsigned char *prev = p;
@@ -1122,28 +1198,39 @@ int lpValidateIntegrity(unsigned char *lp, size_t size, int deep,
return 0;
/* Optionally let the caller validate the entry too. */
- if (entry_cb && !entry_cb(prev, cb_userdata))
+ if (entry_cb && !entry_cb(prev, numele, cb_userdata))
return 0;
count++;
}
/* Check that the count in the header is correct */
- uint32_t numele = lpGetNumElements(lp);
if (numele != LP_HDR_NUMELE_UNKNOWN && numele != count)
return 0;
return 1;
}
+/* Compare entry pointer to by 'p' with string 's' of length 'slen'.
+ * Return 1 if equal. */
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;
+
+ value = lpGet(p, &sz, NULL);
+ if (value) {
+ return (slen == sz) && memcmp(value,s,slen) == 0;
+ } else {
+ /* We use lpStringToInt64() to get an integer representation of the
+ * string 's' and compare it to 'sval', it's much faster than convert
+ * integer to string and comparing. */
+ int64_t sval;
+ if (lpStringToInt64((const char*)s, slen, &sval))
+ return sz == sval;
+ }
+
+ return 0;
}
/* uint compare for qsort */
@@ -1391,8 +1478,9 @@ 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) {
+static int lpValidation(unsigned char *p, unsigned int head_count, void *userdata) {
UNUSED(p);
+ UNUSED(head_count);
int ret;
long *count = userdata;
@@ -1537,6 +1625,114 @@ int listpackTest(int argc, char *argv[], int accurate) {
lpFree(lp);
}
+ TEST("Delete whole listpack when num == -1");
+ {
+ lp = createList();
+ lp = lpDeleteRange(lp, 0, -1);
+ assert(lpLength(lp) == 0);
+ assert(lp[LP_HDR_SIZE] == LP_EOF);
+ assert(lpBytes(lp) == (LP_HDR_SIZE + 1));
+ zfree(lp);
+
+ lp = createList();
+ unsigned char *ptr = lpFirst(lp);
+ lp = lpDeleteRangeWithEntry(lp, &ptr, -1);
+ assert(lpLength(lp) == 0);
+ assert(lp[LP_HDR_SIZE] == LP_EOF);
+ assert(lpBytes(lp) == (LP_HDR_SIZE + 1));
+ zfree(lp);
+ }
+
+ TEST("Delete whole listpack with negative index");
+ {
+ lp = createList();
+ lp = lpDeleteRange(lp, -4, 4);
+ assert(lpLength(lp) == 0);
+ assert(lp[LP_HDR_SIZE] == LP_EOF);
+ assert(lpBytes(lp) == (LP_HDR_SIZE + 1));
+ zfree(lp);
+
+ lp = createList();
+ unsigned char *ptr = lpSeek(lp, -4);
+ lp = lpDeleteRangeWithEntry(lp, &ptr, 4);
+ assert(lpLength(lp) == 0);
+ assert(lp[LP_HDR_SIZE] == LP_EOF);
+ assert(lpBytes(lp) == (LP_HDR_SIZE + 1));
+ zfree(lp);
+ }
+
+ TEST("Delete inclusive range 0,0");
+ {
+ lp = createList();
+ lp = lpDeleteRange(lp, 0, 1);
+ assert(lpLength(lp) == 3);
+ assert(lpSkip(lpLast(lp))[0] == LP_EOF); /* check set LP_EOF correctly */
+ zfree(lp);
+
+ lp = createList();
+ unsigned char *ptr = lpFirst(lp);
+ lp = lpDeleteRangeWithEntry(lp, &ptr, 1);
+ assert(lpLength(lp) == 3);
+ assert(lpSkip(lpLast(lp))[0] == LP_EOF); /* check set LP_EOF correctly */
+ zfree(lp);
+ }
+
+ TEST("Delete inclusive range 0,1");
+ {
+ lp = createList();
+ lp = lpDeleteRange(lp, 0, 2);
+ assert(lpLength(lp) == 2);
+ verifyEntry(lpFirst(lp), (unsigned char*)mixlist[2], strlen(mixlist[2]));
+ zfree(lp);
+
+ lp = createList();
+ unsigned char *ptr = lpFirst(lp);
+ lp = lpDeleteRangeWithEntry(lp, &ptr, 2);
+ assert(lpLength(lp) == 2);
+ verifyEntry(lpFirst(lp), (unsigned char*)mixlist[2], strlen(mixlist[2]));
+ zfree(lp);
+ }
+
+ TEST("Delete inclusive range 1,2");
+ {
+ lp = createList();
+ lp = lpDeleteRange(lp, 1, 2);
+ assert(lpLength(lp) == 2);
+ verifyEntry(lpFirst(lp), (unsigned char*)mixlist[0], strlen(mixlist[0]));
+ zfree(lp);
+
+ lp = createList();
+ unsigned char *ptr = lpSeek(lp, 1);
+ lp = lpDeleteRangeWithEntry(lp, &ptr, 2);
+ assert(lpLength(lp) == 2);
+ verifyEntry(lpFirst(lp), (unsigned char*)mixlist[0], strlen(mixlist[0]));
+ zfree(lp);
+ }
+
+ TEST("Delete with start index out of range");
+ {
+ lp = createList();
+ lp = lpDeleteRange(lp, 5, 1);
+ assert(lpLength(lp) == 4);
+ zfree(lp);
+ }
+
+ TEST("Delete with num overflow");
+ {
+ lp = createList();
+ lp = lpDeleteRange(lp, 1, 5);
+ assert(lpLength(lp) == 1);
+ verifyEntry(lpFirst(lp), (unsigned char*)mixlist[0], strlen(mixlist[0]));
+ zfree(lp);
+
+ lp = createList();
+ unsigned char *ptr = lpSeek(lp, 1);
+ lp = lpDeleteRangeWithEntry(lp, &ptr, 5);
+ assert(lpLength(lp) == 1);
+ verifyEntry(lpFirst(lp), (unsigned char*)mixlist[0], strlen(mixlist[0]));
+ zfree(lp);
+ }
+
TEST("Delete foo while iterating") {
lp = createList();
p = lpFirst(lp);
@@ -1817,6 +2013,21 @@ int listpackTest(int argc, char *argv[], int accurate) {
lpFree(lp);
}
+ TEST("Test number of elements exceeds LP_HDR_NUMELE_UNKNOWN") {
+ lp = lpNew(0);
+ for (int i = 0; i < LP_HDR_NUMELE_UNKNOWN + 1; i++)
+ lp = lpAppend(lp, (unsigned char*)"1", 1);
+
+ assert(lpGetNumElements(lp) == LP_HDR_NUMELE_UNKNOWN);
+ assert(lpLength(lp) == LP_HDR_NUMELE_UNKNOWN+1);
+
+ lp = lpDeleteRange(lp, -2, 2);
+ assert(lpGetNumElements(lp) == LP_HDR_NUMELE_UNKNOWN);
+ assert(lpLength(lp) == LP_HDR_NUMELE_UNKNOWN-1);
+ assert(lpGetNumElements(lp) == LP_HDR_NUMELE_UNKNOWN-1); /* update length after lpLength */
+ lpFree(lp);
+ }
+
TEST("Stress with random payloads of different encoding") {
unsigned long long start = usec();
int i,j,len,where;
@@ -1951,6 +2162,30 @@ int listpackTest(int argc, char *argv[], int accurate) {
printf("Done. usec=%lld\n", usec()-start);
}
+ TEST("Benchmark lpCompare with string") {
+ unsigned long long start = usec();
+ for (int i = 0; i < 2000; i++) {
+ unsigned char *eptr = lpSeek(lp,0);
+ while (eptr != NULL) {
+ lpCompare(eptr,(unsigned char*)"nothing",7);
+ eptr = lpNext(lp,eptr);
+ }
+ }
+ printf("Done. usec=%lld\n", usec()-start);
+ }
+
+ TEST("Benchmark lpCompare with number") {
+ unsigned long long start = usec();
+ for (int i = 0; i < 2000; i++) {
+ unsigned char *eptr = lpSeek(lp,0);
+ while (eptr != NULL) {
+ lpCompare(lp, (unsigned char*)"99999", 5);
+ eptr = lpNext(lp,eptr);
+ }
+ }
+ printf("Done. usec=%lld\n", usec()-start);
+ }
+
lpFree(lp);
}
diff --git a/src/listpack.h b/src/listpack.h
index 57bd4ecf3..535513ac2 100644
--- a/src/listpack.h
+++ b/src/listpack.h
@@ -57,6 +57,8 @@ typedef struct {
unsigned char *lpNew(size_t capacity);
void lpFree(unsigned char *lp);
unsigned char* lpShrinkToFit(unsigned char *lp);
+unsigned char *lpInsertString(unsigned char *lp, unsigned char *s, uint32_t slen,
+ unsigned char *p, int where, unsigned char **newp);
unsigned char *lpPrepend(unsigned char *lp, unsigned char *s, uint32_t slen);
unsigned char *lpPrependInteger(unsigned char *lp, long long lval);
unsigned char *lpAppend(unsigned char *lp, unsigned char *s, uint32_t slen);
@@ -64,6 +66,8 @@ unsigned char *lpAppendInteger(unsigned char *lp, long long lval);
unsigned char *lpReplace(unsigned char *lp, unsigned char **p, unsigned char *s, uint32_t slen);
unsigned char *lpReplaceInteger(unsigned char *lp, unsigned char **p, long long lval);
unsigned char *lpDelete(unsigned char *lp, unsigned char *p, unsigned char **newp);
+unsigned char *lpDeleteRangeWithEntry(unsigned char *lp, unsigned char **p, unsigned long num);
+unsigned char *lpDeleteRange(unsigned char *lp, long index, unsigned long num);
unsigned long lpLength(unsigned char *lp);
unsigned char *lpGet(unsigned char *p, int64_t *count, unsigned char *intbuf);
unsigned char *lpGetValue(unsigned char *p, unsigned int *slen, long long *lval);
@@ -74,7 +78,7 @@ unsigned char *lpNext(unsigned char *lp, unsigned char *p);
unsigned char *lpPrev(unsigned char *lp, unsigned char *p);
size_t lpBytes(unsigned char *lp);
unsigned char *lpSeek(unsigned char *lp, long index);
-typedef int (*listpackValidateEntryCB)(unsigned char *p, void *userdata);
+typedef int (*listpackValidateEntryCB)(unsigned char *p, unsigned int head_count, void *userdata);
int lpValidateIntegrity(unsigned char *lp, size_t size, int deep,
listpackValidateEntryCB entry_cb, void *cb_userdata);
unsigned char *lpValidateFirst(unsigned char *lp);
diff --git a/src/module.c b/src/module.c
index a617d6053..8bf3cbccf 100644
--- a/src/module.c
+++ b/src/module.c
@@ -522,7 +522,7 @@ int moduleCreateEmptyKey(RedisModuleKey *key, int type) {
server.list_compress_depth);
break;
case REDISMODULE_KEYTYPE_ZSET:
- obj = createZsetZiplistObject();
+ obj = createZsetListpackObject();
break;
case REDISMODULE_KEYTYPE_HASH:
obj = createHashObject();
@@ -2966,7 +2966,7 @@ int zsetInitScoreRange(RedisModuleKey *key, double min, double max, int minex, i
zrs->minex = minex;
zrs->maxex = maxex;
- if (key->value->encoding == OBJ_ENCODING_ZIPLIST) {
+ if (key->value->encoding == OBJ_ENCODING_LISTPACK) {
key->u.zset.current = first ? zzlFirstInRange(key->value->ptr,zrs) :
zzlLastInRange(key->value->ptr,zrs);
} else if (key->value->encoding == OBJ_ENCODING_SKIPLIST) {
@@ -3030,7 +3030,7 @@ int zsetInitLexRange(RedisModuleKey *key, RedisModuleString *min, RedisModuleStr
* otherwise we don't want the zlexrangespec to be freed. */
key->u.zset.type = REDISMODULE_ZSET_RANGE_LEX;
- if (key->value->encoding == OBJ_ENCODING_ZIPLIST) {
+ if (key->value->encoding == OBJ_ENCODING_LISTPACK) {
key->u.zset.current = first ? zzlFirstInLexRange(key->value->ptr,zlrs) :
zzlLastInLexRange(key->value->ptr,zlrs);
} else if (key->value->encoding == OBJ_ENCODING_SKIPLIST) {
@@ -3076,12 +3076,12 @@ RedisModuleString *RM_ZsetRangeCurrentElement(RedisModuleKey *key, double *score
if (!key->value || key->value->type != OBJ_ZSET) return NULL;
if (key->u.zset.current == NULL) return NULL;
- if (key->value->encoding == OBJ_ENCODING_ZIPLIST) {
+ if (key->value->encoding == OBJ_ENCODING_LISTPACK) {
unsigned char *eptr, *sptr;
eptr = key->u.zset.current;
- sds ele = ziplistGetObject(eptr);
+ sds ele = lpGetObject(eptr);
if (score) {
- sptr = ziplistNext(key->value->ptr,eptr);
+ sptr = lpNext(key->value->ptr,eptr);
*score = zzlGetScore(sptr);
}
str = createObject(OBJ_STRING,ele);
@@ -3103,12 +3103,12 @@ int RM_ZsetRangeNext(RedisModuleKey *key) {
if (!key->value || key->value->type != OBJ_ZSET) return 0;
if (!key->u.zset.type || !key->u.zset.current) return 0; /* No active iterator. */
- if (key->value->encoding == OBJ_ENCODING_ZIPLIST) {
+ if (key->value->encoding == OBJ_ENCODING_LISTPACK) {
unsigned char *zl = key->value->ptr;
unsigned char *eptr = key->u.zset.current;
unsigned char *next;
- next = ziplistNext(zl,eptr); /* Skip element. */
- if (next) next = ziplistNext(zl,next); /* Skip score. */
+ next = lpNext(zl,eptr); /* Skip element. */
+ if (next) next = lpNext(zl,next); /* Skip score. */
if (next == NULL) {
key->u.zset.er = 1;
return 0;
@@ -3118,7 +3118,7 @@ int RM_ZsetRangeNext(RedisModuleKey *key) {
/* Fetch the next element score for the
* range check. */
unsigned char *saved_next = next;
- next = ziplistNext(zl,next); /* Skip next element. */
+ next = lpNext(zl,next); /* Skip next element. */
double score = zzlGetScore(next); /* Obtain the next score. */
if (!zslValueLteMax(score,&key->u.zset.rs)) {
key->u.zset.er = 1;
@@ -3167,12 +3167,12 @@ int RM_ZsetRangePrev(RedisModuleKey *key) {
if (!key->value || key->value->type != OBJ_ZSET) return 0;
if (!key->u.zset.type || !key->u.zset.current) return 0; /* No active iterator. */
- if (key->value->encoding == OBJ_ENCODING_ZIPLIST) {
+ if (key->value->encoding == OBJ_ENCODING_LISTPACK) {
unsigned char *zl = key->value->ptr;
unsigned char *eptr = key->u.zset.current;
unsigned char *prev;
- prev = ziplistPrev(zl,eptr); /* Go back to previous score. */
- if (prev) prev = ziplistPrev(zl,prev); /* Back to previous ele. */
+ prev = lpPrev(zl,eptr); /* Go back to previous score. */
+ if (prev) prev = lpPrev(zl,prev); /* Back to previous ele. */
if (prev == NULL) {
key->u.zset.er = 1;
return 0;
@@ -3182,7 +3182,7 @@ int RM_ZsetRangePrev(RedisModuleKey *key) {
/* Fetch the previous element score for the
* range check. */
unsigned char *saved_prev = prev;
- prev = ziplistNext(zl,prev); /* Skip element to get the score.*/
+ prev = lpNext(zl,prev); /* Skip element to get the score.*/
double score = zzlGetScore(prev); /* Obtain the prev score. */
if (!zslValueGteMin(score,&key->u.zset.rs)) {
key->u.zset.er = 1;
@@ -7991,22 +7991,22 @@ int RM_ScanKey(RedisModuleKey *key, RedisModuleScanCursor *cursor, RedisModuleSc
cursor->done = 1;
ret = 0;
} else if (o->type == OBJ_ZSET) {
- unsigned char *p = ziplistIndex(o->ptr,0);
+ unsigned char *p = lpSeek(o->ptr,0);
unsigned char *vstr;
unsigned int vlen;
long long vll;
while(p) {
- ziplistGet(p,&vstr,&vlen,&vll);
+ vstr = lpGetValue(p,&vlen,&vll);
robj *field = (vstr != NULL) ?
createStringObject((char*)vstr,vlen) :
createObject(OBJ_STRING,sdsfromlonglong(vll));
- p = ziplistNext(o->ptr,p);
- ziplistGet(p,&vstr,&vlen,&vll);
+ p = lpNext(o->ptr,p);
+ vstr = lpGetValue(p,&vlen,&vll);
robj *value = (vstr != NULL) ?
createStringObject((char*)vstr,vlen) :
createObject(OBJ_STRING,sdsfromlonglong(vll));
fn(key, field, value, privdata);
- p = ziplistNext(o->ptr,p);
+ p = lpNext(o->ptr,p);
decrRefCount(field);
decrRefCount(value);
}
diff --git a/src/object.c b/src/object.c
index ef1430088..0f869ea7e 100644
--- a/src/object.c
+++ b/src/object.c
@@ -272,10 +272,10 @@ robj *createZsetObject(void) {
return o;
}
-robj *createZsetZiplistObject(void) {
- unsigned char *zl = ziplistNew();
- robj *o = createObject(OBJ_ZSET,zl);
- o->encoding = OBJ_ENCODING_ZIPLIST;
+robj *createZsetListpackObject(void) {
+ unsigned char *lp = lpNew(0);
+ robj *o = createObject(OBJ_ZSET,lp);
+ o->encoding = OBJ_ENCODING_LISTPACK;
return o;
}
@@ -329,7 +329,7 @@ void freeZsetObject(robj *o) {
zslFree(zs->zsl);
zfree(zs);
break;
- case OBJ_ENCODING_ZIPLIST:
+ case OBJ_ENCODING_LISTPACK:
zfree(o->ptr);
break;
default:
@@ -473,8 +473,8 @@ void dismissZsetObject(robj *o, size_t size_hint) {
dict *d = zs->dict;
dismissMemory(d->ht_table[0], DICTHT_SIZE(d->ht_size_exp[0])*sizeof(dictEntry*));
dismissMemory(d->ht_table[1], DICTHT_SIZE(d->ht_size_exp[1])*sizeof(dictEntry*));
- } else if (o->encoding == OBJ_ENCODING_ZIPLIST) {
- dismissMemory(o->ptr, ziplistBlobLen((unsigned char*)o->ptr));
+ } else if (o->encoding == OBJ_ENCODING_LISTPACK) {
+ dismissMemory(o->ptr, lpBytes((unsigned char*)o->ptr));
} else {
serverPanic("Unknown zset encoding type");
}
@@ -1027,7 +1027,7 @@ size_t objectComputeSize(robj *key, robj *o, size_t sample_size, int dbid) {
serverPanic("Unknown set encoding");
}
} else if (o->type == OBJ_ZSET) {
- if (o->encoding == OBJ_ENCODING_ZIPLIST) {
+ if (o->encoding == OBJ_ENCODING_LISTPACK) {
asize = sizeof(*o)+zmalloc_size(o->ptr);
} else if (o->encoding == OBJ_ENCODING_SKIPLIST) {
d = ((zset*)o->ptr)->dict;
diff --git a/src/rdb.c b/src/rdb.c
index e38c93407..1ebabf2ec 100644
--- a/src/rdb.c
+++ b/src/rdb.c
@@ -669,8 +669,8 @@ int rdbSaveObjectType(rio *rdb, robj *o) {
else
serverPanic("Unknown set encoding");
case OBJ_ZSET:
- if (o->encoding == OBJ_ENCODING_ZIPLIST)
- return rdbSaveType(rdb,RDB_TYPE_ZSET_ZIPLIST);
+ if (o->encoding == OBJ_ENCODING_LISTPACK)
+ return rdbSaveType(rdb,RDB_TYPE_ZSET_LISTPACK);
else if (o->encoding == OBJ_ENCODING_SKIPLIST)
return rdbSaveType(rdb,RDB_TYPE_ZSET_2);
else
@@ -861,8 +861,8 @@ ssize_t rdbSaveObject(rio *rdb, robj *o, robj *key, int dbid) {
}
} else if (o->type == OBJ_ZSET) {
/* Save a sorted set value */
- if (o->encoding == OBJ_ENCODING_ZIPLIST) {
- size_t l = ziplistBlobLen((unsigned char*)o->ptr);
+ if (o->encoding == OBJ_ENCODING_LISTPACK) {
+ size_t l = lpBytes((unsigned char*)o->ptr);
if ((n = rdbSaveRawString(rdb,o->ptr,l)) == -1) return -1;
nwritten += n;
@@ -1518,6 +1518,124 @@ robj *rdbLoadCheckModuleValue(rio *rdb, char *modulename) {
return createStringObject("module-dummy-value",18);
}
+/* callback for hashZiplistConvertAndValidateIntegrity.
+ * Check that the ziplist doesn't have duplicate hash field names.
+ * The ziplist element pointed by 'p' will be converted and stored into listpack. */
+static int _ziplistPairsEntryConvertAndValidate(unsigned char *p, unsigned int head_count, void *userdata) {
+ unsigned char *str;
+ unsigned int slen;
+ long long vll;
+
+ struct {
+ long count;
+ dict *fields;
+ unsigned char **lp;
+ } *data = userdata;
+
+ if (data->fields == NULL) {
+ data->fields = dictCreate(&hashDictType);
+ dictExpand(data->fields, head_count/2);
+ }
+
+ if (!ziplistGet(p, &str, &slen, &vll))
+ return 0;
+
+ /* Even records are field names, add to dict and check that's not a dup */
+ if (((data->count) & 1) == 0) {
+ sds field = str? sdsnewlen(str, slen): sdsfromlonglong(vll);
+ if (dictAdd(data->fields, field, NULL) != DICT_OK) {
+ /* Duplicate, return an error */
+ sdsfree(field);
+ return 0;
+ }
+ }
+
+ if (str) {
+ *(data->lp) = lpAppend(*(data->lp), (unsigned char*)str, slen);
+ } else {
+ *(data->lp) = lpAppendInteger(*(data->lp), vll);
+ }
+
+ (data->count)++;
+ return 1;
+}
+
+/* Validate the integrity of the data structure while converting it to
+ * listpack and storing it at 'lp'.
+ * The function is safe to call on non-validated ziplists, it returns 0
+ * when encounter an integrity validation issue. */
+int ziplistPairsConvertAndValidateIntegrity(unsigned char *zl, size_t size, unsigned char **lp) {
+ /* Keep track of the field names to locate duplicate ones */
+ struct {
+ long count;
+ dict *fields; /* Initialisation at the first callback. */
+ unsigned char **lp;
+ } data = {0, NULL, lp};
+
+ int ret = ziplistValidateIntegrity(zl, size, 1, _ziplistPairsEntryConvertAndValidate, &data);
+
+ /* make sure we have an even number of records. */
+ if (data.count & 1)
+ ret = 0;
+
+ if (data.fields) dictRelease(data.fields);
+ return ret;
+}
+
+/* callback for to check the listpack doesn't have duplicate records */
+static int _lpPairsEntryValidation(unsigned char *p, unsigned int head_count, void *userdata) {
+ struct {
+ long count;
+ dict *fields;
+ } *data = userdata;
+
+ if (data->fields == NULL) {
+ data->fields = dictCreate(&hashDictType);
+ dictExpand(data->fields, head_count/2);
+ }
+
+ /* Even records are field names, add to dict and check that's not a dup */
+ if (((data->count) & 1) == 0) {
+ unsigned char *str;
+ int64_t slen;
+ unsigned char buf[LP_INTBUF_SIZE];
+
+ str = lpGet(p, &slen, buf);
+ sds field = sdsnewlen(str, slen);
+ if (dictAdd(data->fields, field, NULL) != DICT_OK) {
+ /* Duplicate, return an error */
+ sdsfree(field);
+ return 0;
+ }
+ }
+
+ (data->count)++;
+ return 1;
+}
+
+/* Validate the integrity of the listpack 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 lpPairsValidateIntegrityAndDups(unsigned char *lp, size_t size, int deep) {
+ if (!deep)
+ return lpValidateIntegrity(lp, size, 0, NULL, NULL);
+
+ /* Keep track of the field names to locate duplicate ones */
+ struct {
+ long count;
+ dict *fields; /* Initialisation at the first callback. */
+ } data = {0, NULL};
+
+ int ret = lpValidateIntegrity(lp, size, 1, _lpPairsEntryValidation, &data);
+
+ /* make sure we have an even number of records. */
+ if (data.count & 1)
+ ret = 0;
+
+ if (data.fields) dictRelease(data.fields);
+ return ret;
+}
+
/* Load a Redis object of the specified type from the specified file.
* On success a newly allocated object is returned, otherwise NULL.
* When the function returns NULL and if 'error' is not NULL, the
@@ -1686,9 +1804,9 @@ robj *rdbLoadObject(int rdbtype, rio *rdb, sds key, int dbid, int *error) {
}
/* Convert *after* loading, since sorted sets are not stored ordered. */
- if (zsetLength(o) <= server.zset_max_ziplist_entries &&
- maxelelen <= server.zset_max_ziplist_value)
- zsetConvert(o,OBJ_ENCODING_ZIPLIST);
+ if (zsetLength(o) <= server.zset_max_listpack_entries &&
+ maxelelen <= server.zset_max_listpack_value)
+ zsetConvert(o,OBJ_ENCODING_LISTPACK);
} else if (rdbtype == RDB_TYPE_HASH) {
uint64_t len;
int ret;
@@ -1842,6 +1960,7 @@ robj *rdbLoadObject(int rdbtype, rio *rdb, sds key, int dbid, int *error) {
rdbtype == RDB_TYPE_LIST_ZIPLIST ||
rdbtype == RDB_TYPE_SET_INTSET ||
rdbtype == RDB_TYPE_ZSET_ZIPLIST ||
+ rdbtype == RDB_TYPE_ZSET_LISTPACK ||
rdbtype == RDB_TYPE_HASH_ZIPLIST ||
rdbtype == RDB_TYPE_HASH_LISTPACK)
{
@@ -1947,30 +2066,53 @@ robj *rdbLoadObject(int rdbtype, rio *rdb, sds key, int dbid, int *error) {
setTypeConvert(o,OBJ_ENCODING_HT);
break;
case RDB_TYPE_ZSET_ZIPLIST:
+ {
+ unsigned char *lp = lpNew(encoded_len);
+ if (!ziplistPairsConvertAndValidateIntegrity(encoded, encoded_len, &lp)) {
+ rdbReportCorruptRDB("Zset ziplist integrity check failed.");
+ zfree(lp);
+ zfree(encoded);
+ o->ptr = NULL;
+ decrRefCount(o);
+ return NULL;
+ }
+
+ zfree(o->ptr);
+ o->type = OBJ_ZSET;
+ o->ptr = lp;
+ o->encoding = OBJ_ENCODING_LISTPACK;
+ if (zsetLength(o) == 0) {
+ decrRefCount(o);
+ goto emptykey;
+ }
+
+ if (zsetLength(o) > server.zset_max_listpack_entries)
+ zsetConvert(o,OBJ_ENCODING_SKIPLIST);
+ break;
+ }
+ case RDB_TYPE_ZSET_LISTPACK:
if (deep_integrity_validation) server.stat_dump_payload_sanitizations++;
- if (!zsetZiplistValidateIntegrity(encoded, encoded_len, deep_integrity_validation)) {
- rdbReportCorruptRDB("Zset ziplist integrity check failed.");
+ if (!lpPairsValidateIntegrityAndDups(encoded, encoded_len, deep_integrity_validation)) {
+ rdbReportCorruptRDB("Zset listpack integrity check failed.");
zfree(encoded);
o->ptr = NULL;
decrRefCount(o);
return NULL;
}
o->type = OBJ_ZSET;
- o->encoding = OBJ_ENCODING_ZIPLIST;
+ o->encoding = OBJ_ENCODING_LISTPACK;
if (zsetLength(o) == 0) {
- zfree(encoded);
- o->ptr = NULL;
decrRefCount(o);
goto emptykey;
}
- if (zsetLength(o) > server.zset_max_ziplist_entries)
+ if (zsetLength(o) > server.zset_max_listpack_entries)
zsetConvert(o,OBJ_ENCODING_SKIPLIST);
break;
case RDB_TYPE_HASH_ZIPLIST:
{
unsigned char *lp = lpNew(encoded_len);
- if (!hashZiplistConvertAndValidateIntegrity(encoded, encoded_len, &lp)) {
+ if (!ziplistPairsConvertAndValidateIntegrity(encoded, encoded_len, &lp)) {
rdbReportCorruptRDB("Hash ziplist integrity check failed.");
zfree(lp);
zfree(encoded);
@@ -1984,8 +2126,6 @@ robj *rdbLoadObject(int rdbtype, rio *rdb, sds key, int dbid, int *error) {
o->type = OBJ_HASH;
o->encoding = OBJ_ENCODING_LISTPACK;
if (hashTypeLength(o) == 0) {
- zfree(o->ptr);
- o->ptr = NULL;
decrRefCount(o);
goto emptykey;
}
@@ -1997,7 +2137,7 @@ robj *rdbLoadObject(int rdbtype, rio *rdb, sds key, int dbid, int *error) {
}
case RDB_TYPE_HASH_LISTPACK:
if (deep_integrity_validation) server.stat_dump_payload_sanitizations++;
- if (!hashListpackValidateIntegrity(encoded, encoded_len, deep_integrity_validation)) {
+ if (!lpPairsValidateIntegrityAndDups(encoded, encoded_len, deep_integrity_validation)) {
rdbReportCorruptRDB("Hash listpack integrity check failed.");
zfree(encoded);
o->ptr = NULL;
@@ -2007,8 +2147,6 @@ robj *rdbLoadObject(int rdbtype, rio *rdb, sds key, int dbid, int *error) {
o->type = OBJ_HASH;
o->encoding = OBJ_ENCODING_LISTPACK;
if (hashTypeLength(o) == 0) {
- zfree(encoded);
- o->ptr = NULL;
decrRefCount(o);
goto emptykey;
}
diff --git a/src/rdb.h b/src/rdb.h
index e3a0658f5..0439ec821 100644
--- a/src/rdb.h
+++ b/src/rdb.h
@@ -92,10 +92,11 @@
#define RDB_TYPE_LIST_QUICKLIST 14
#define RDB_TYPE_STREAM_LISTPACKS 15
#define RDB_TYPE_HASH_LISTPACK 16
+#define RDB_TYPE_ZSET_LISTPACK 17
/* NOTE: WHEN ADDING NEW RDB TYPE, UPDATE rdbIsObjectType() BELOW */
/* Test if a type is an object type. */
-#define rdbIsObjectType(t) ((t >= 0 && t <= 7) || (t >= 9 && t <= 16))
+#define rdbIsObjectType(t) ((t >= 0 && t <= 7) || (t >= 9 && t <= 17))
/* Special RDB opcodes (saved/loaded with rdbSaveType/rdbLoadType). */
#define RDB_OPCODE_MODULE_AUX 247 /* Module auxiliary data. */
diff --git a/src/redis-check-rdb.c b/src/redis-check-rdb.c
index 9e62e25db..9bcf3aef9 100644
--- a/src/redis-check-rdb.c
+++ b/src/redis-check-rdb.c
@@ -92,6 +92,7 @@ char *rdb_type_string[] = {
"quicklist",
"stream",
"hash-listpack"
+ "zset-listpack"
};
/* Show a few stats collected into 'rdbstate' */
diff --git a/src/server.h b/src/server.h
index ce5b0db76..21551fac0 100644
--- a/src/server.h
+++ b/src/server.h
@@ -1576,8 +1576,8 @@ struct redisServer {
size_t hash_max_listpack_entries;
size_t hash_max_listpack_value;
size_t set_max_intset_entries;
- size_t zset_max_ziplist_entries;
- size_t zset_max_ziplist_value;
+ size_t zset_max_listpack_entries;
+ size_t zset_max_listpack_value;
size_t hll_sparse_max_bytes;
size_t stream_node_max_bytes;
long long stream_node_max_entries;
@@ -2047,7 +2047,7 @@ robj *createSetObject(void);
robj *createIntsetObject(void);
robj *createHashObject(void);
robj *createZsetObject(void);
-robj *createZsetZiplistObject(void);
+robj *createZsetListpackObject(void);
robj *createStreamObject(void);
robj *createModuleObject(moduleType *mt, void *value);
int getLongFromObjectOrReply(client *c, robj *o, long *target, const char *msg);
@@ -2233,16 +2233,15 @@ unsigned char *zzlFirstInRange(unsigned char *zl, zrangespec *range);
unsigned char *zzlLastInRange(unsigned char *zl, zrangespec *range);
unsigned long zsetLength(const robj *zobj);
void zsetConvert(robj *zobj, int encoding);
-void zsetConvertToZiplistIfNeeded(robj *zobj, size_t maxelelen);
+void zsetConvertToListpackIfNeeded(robj *zobj, size_t maxelelen);
int zsetScore(robj *zobj, sds member, double *score);
unsigned long zslGetRank(zskiplist *zsl, double score, sds o);
int zsetAdd(robj *zobj, double score, sds ele, int in_flags, int *out_flags, double *newscore);
long zsetRank(robj *zobj, sds ele, int reverse);
int zsetDel(robj *zobj, sds ele);
robj *zsetDup(robj *o);
-int zsetZiplistValidateIntegrity(unsigned char *zl, size_t size, int deep);
void genericZpopCommand(client *c, robj **keyv, int keyc, int where, int emitkey, robj *countarg);
-sds ziplistGetObject(unsigned char *sptr);
+sds lpGetObject(unsigned char *sptr);
int zslValueGteMin(double value, zrangespec *spec);
int zslValueLteMax(double value, zrangespec *spec);
void zslFreeLexRange(zlexrangespec *spec);
@@ -2359,8 +2358,6 @@ robj *hashTypeLookupWriteOrCreate(client *c, robj *key);
robj *hashTypeGetValueObject(robj *o, sds field);
int hashTypeSet(robj *o, sds field, sds value, int flags);
robj *hashTypeDup(robj *o);
-int hashZiplistConvertAndValidateIntegrity(unsigned char *zl, size_t size, unsigned char **lp);
-int hashListpackValidateIntegrity(unsigned char *lp, size_t size, int deep);
/* Pub / Sub */
int pubsubUnsubscribeAllChannels(client *c, int notify);
diff --git a/src/t_hash.c b/src/t_hash.c
index 26089fa72..d0f81c0d7 100644
--- a/src/t_hash.c
+++ b/src/t_hash.c
@@ -279,8 +279,8 @@ int hashTypeDelete(robj *o, sds field) {
if (fptr != NULL) {
fptr = lpFind(zl, fptr, (unsigned char*)field, sdslen(field), 1);
if (fptr != NULL) {
- zl = lpDelete(zl,fptr,&fptr); /* Delete the key. */
- zl = lpDelete(zl,fptr,&fptr); /* Delete the value. */
+ /* Delete both of the key and the value. */
+ zl = lpDeleteRangeWithEntry(zl,&fptr,2);
o->ptr = zl;
deleted = 1;
}
@@ -541,114 +541,6 @@ robj *hashTypeDup(robj *o) {
return hobj;
}
-/* callback for hashZiplistConvertAndValidateIntegrity.
- * Check that the ziplist doesn't have duplicate hash field names.
- * The ziplist element pointed by 'p' will be converted and stored into listpack. */
-static int _hashZiplistEntryConvertAndValidation(unsigned char *p, void *userdata) {
- unsigned char *str;
- unsigned int slen;
- long long vll;
-
- struct {
- long count;
- dict *fields;
- unsigned char **lp;
- } *data = userdata;
-
- if (!ziplistGet(p, &str, &slen, &vll))
- return 0;
-
- /* Even records are field names, add to dict and check that's not a dup */
- if (((data->count) & 1) == 0) {
- sds field = str? sdsnewlen(str, slen): sdsfromlonglong(vll);
- if (dictAdd(data->fields, field, NULL) != DICT_OK) {
- /* Duplicate, return an error */
- sdsfree(field);
- return 0;
- }
- }
-
- if (str) {
- *(data->lp) = lpAppend(*(data->lp), (unsigned char*)str, slen);
- } else {
- *(data->lp) = lpAppendInteger(*(data->lp), vll);
- }
-
- (data->count)++;
- return 1;
-}
-
-/* callback for to check the listpack doesn't have duplicate records */
-static int _hashListpackEntryValidation(unsigned char *p, void *userdata) {
- struct {
- long count;
- dict *fields;
- } *data = userdata;
-
- /* Even records are field names, add to dict and check that's not a dup */
- if (((data->count) & 1) == 0) {
- unsigned char *str;
- int64_t slen;
- unsigned char buf[LP_INTBUF_SIZE];
-
- str = lpGet(p, &slen, buf);
- sds field = sdsnewlen(str, slen);
- if (dictAdd(data->fields, field, NULL) != DICT_OK) {
- /* Duplicate, return an error */
- sdsfree(field);
- return 0;
- }
- }
-
- (data->count)++;
- return 1;
-}
-
-/* Validate the integrity of the data structure while converting it to
- * listpack and storing it at 'lp'.
- * The function is safe to call on non-validated ziplists, it returns 0
- * when encounter an integrity validation issue. */
-int hashZiplistConvertAndValidateIntegrity(unsigned char *zl, size_t size, unsigned char **lp) {
- /* Keep track of the field names to locate duplicate ones */
- struct {
- long count;
- dict *fields;
- unsigned char **lp;
- } data = {0, dictCreate(&hashDictType), lp};
-
- int ret = ziplistValidateIntegrity(zl, size, 1, _hashZiplistEntryConvertAndValidation, &data);
-
- /* make sure we have an even number of records. */
- if (data.count & 1)
- ret = 0;
-
- dictRelease(data.fields);
- return ret;
-}
-
-/* Validate the integrity of the listpack 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 hashListpackValidateIntegrity(unsigned char *lp, size_t size, int deep) {
- if (!deep)
- return lpValidateIntegrity(lp, size, 0, NULL, NULL);
-
- /* Keep track of the field names to locate duplicate ones */
- struct {
- long count;
- dict *fields;
- } data = {0, dictCreate(&hashDictType)};
-
- int ret = lpValidateIntegrity(lp, size, 1, _hashListpackEntryValidation, &data);
-
- /* make sure we have an even number of records. */
- if (data.count & 1)
- ret = 0;
-
- dictRelease(data.fields);
- return ret;
-}
-
/* Create a new sds string from the listpack entry. */
sds hashSdsFromListpackEntry(listpackEntry *e) {
return e->sval ? sdsnewlen(e->sval, e->slen) : sdsfromlonglong(e->lval);
diff --git a/src/t_zset.c b/src/t_zset.c
index 5bbb3e1c3..a15967e49 100644
--- a/src/t_zset.c
+++ b/src/t_zset.c
@@ -715,7 +715,7 @@ zskiplistNode *zslLastInLexRange(zskiplist *zsl, zlexrangespec *range) {
}
/*-----------------------------------------------------------------------------
- * Ziplist-backed sorted set API
+ * Listpack-backed sorted set API
*----------------------------------------------------------------------------*/
double zzlStrtod(unsigned char *vstr, unsigned int vlen) {
@@ -734,7 +734,7 @@ double zzlGetScore(unsigned char *sptr) {
double score;
serverAssert(sptr != NULL);
- serverAssert(ziplistGet(sptr,&vstr,&vlen,&vlong));
+ vstr = lpGetValue(sptr,&vlen,&vlong);
if (vstr) {
score = zzlStrtod(vstr,vlen);
@@ -745,14 +745,14 @@ double zzlGetScore(unsigned char *sptr) {
return score;
}
-/* Return a ziplist element as an SDS string. */
-sds ziplistGetObject(unsigned char *sptr) {
+/* Return a listpack element as an SDS string. */
+sds lpGetObject(unsigned char *sptr) {
unsigned char *vstr;
unsigned int vlen;
long long vlong;
serverAssert(sptr != NULL);
- serverAssert(ziplistGet(sptr,&vstr,&vlen,&vlong));
+ vstr = lpGetValue(sptr,&vlen,&vlong);
if (vstr) {
return sdsnewlen((char*)vstr,vlen);
@@ -769,7 +769,7 @@ int zzlCompareElements(unsigned char *eptr, unsigned char *cstr, unsigned int cl
unsigned char vbuf[32];
int minlen, cmp;
- serverAssert(ziplistGet(eptr,&vstr,&vlen,&vlong));
+ vstr = lpGetValue(eptr,&vlen,&vlong);
if (vstr == NULL) {
/* Store string representation of long long in buf. */
vlen = ll2string((char*)vbuf,sizeof(vbuf),vlong);
@@ -783,7 +783,7 @@ int zzlCompareElements(unsigned char *eptr, unsigned char *cstr, unsigned int cl
}
unsigned int zzlLength(unsigned char *zl) {
- return ziplistLen(zl)/2;
+ return lpLength(zl)/2;
}
/* Move to next entry based on the values in eptr and sptr. Both are set to
@@ -792,9 +792,9 @@ void zzlNext(unsigned char *zl, unsigned char **eptr, unsigned char **sptr) {
unsigned char *_eptr, *_sptr;
serverAssert(*eptr != NULL && *sptr != NULL);
- _eptr = ziplistNext(zl,*sptr);
+ _eptr = lpNext(zl,*sptr);
if (_eptr != NULL) {
- _sptr = ziplistNext(zl,_eptr);
+ _sptr = lpNext(zl,_eptr);
serverAssert(_sptr != NULL);
} else {
/* No next entry. */
@@ -811,9 +811,9 @@ void zzlPrev(unsigned char *zl, unsigned char **eptr, unsigned char **sptr) {
unsigned char *_eptr, *_sptr;
serverAssert(*eptr != NULL && *sptr != NULL);
- _sptr = ziplistPrev(zl,*eptr);
+ _sptr = lpPrev(zl,*eptr);
if (_sptr != NULL) {
- _eptr = ziplistPrev(zl,_sptr);
+ _eptr = lpPrev(zl,_sptr);
serverAssert(_eptr != NULL);
} else {
/* No previous entry. */
@@ -835,13 +835,13 @@ int zzlIsInRange(unsigned char *zl, zrangespec *range) {
(range->min == range->max && (range->minex || range->maxex)))
return 0;
- p = ziplistIndex(zl,-1); /* Last score. */
+ p = lpSeek(zl,-1); /* Last score. */
if (p == NULL) return 0; /* Empty sorted set */
score = zzlGetScore(p);
if (!zslValueGteMin(score,range))
return 0;
- p = ziplistIndex(zl,1); /* First score. */
+ p = lpSeek(zl,1); /* First score. */
serverAssert(p != NULL);
score = zzlGetScore(p);
if (!zslValueLteMax(score,range))
@@ -853,14 +853,14 @@ int zzlIsInRange(unsigned char *zl, zrangespec *range) {
/* Find pointer to the first element contained in the specified range.
* Returns NULL when no element is contained in the range. */
unsigned char *zzlFirstInRange(unsigned char *zl, zrangespec *range) {
- unsigned char *eptr = ziplistIndex(zl,0), *sptr;
+ unsigned char *eptr = lpSeek(zl,0), *sptr;
double score;
/* If everything is out of range, return early. */
if (!zzlIsInRange(zl,range)) return NULL;
while (eptr != NULL) {
- sptr = ziplistNext(zl,eptr);
+ sptr = lpNext(zl,eptr);
serverAssert(sptr != NULL);
score = zzlGetScore(sptr);
@@ -872,7 +872,7 @@ unsigned char *zzlFirstInRange(unsigned char *zl, zrangespec *range) {
}
/* Move to next element. */
- eptr = ziplistNext(zl,sptr);
+ eptr = lpNext(zl,sptr);
}
return NULL;
@@ -881,14 +881,14 @@ unsigned char *zzlFirstInRange(unsigned char *zl, zrangespec *range) {
/* Find pointer to the last element contained in the specified range.
* Returns NULL when no element is contained in the range. */
unsigned char *zzlLastInRange(unsigned char *zl, zrangespec *range) {
- unsigned char *eptr = ziplistIndex(zl,-2), *sptr;
+ unsigned char *eptr = lpSeek(zl,-2), *sptr;
double score;
/* If everything is out of range, return early. */
if (!zzlIsInRange(zl,range)) return NULL;
while (eptr != NULL) {
- sptr = ziplistNext(zl,eptr);
+ sptr = lpNext(zl,eptr);
serverAssert(sptr != NULL);
score = zzlGetScore(sptr);
@@ -901,9 +901,9 @@ unsigned char *zzlLastInRange(unsigned char *zl, zrangespec *range) {
/* Move to previous element by moving to the score of previous element.
* When this returns NULL, we know there also is no element. */
- sptr = ziplistPrev(zl,eptr);
+ sptr = lpPrev(zl,eptr);
if (sptr != NULL)
- serverAssert((eptr = ziplistPrev(zl,sptr)) != NULL);
+ serverAssert((eptr = lpPrev(zl,sptr)) != NULL);
else
eptr = NULL;
}
@@ -912,14 +912,14 @@ unsigned char *zzlLastInRange(unsigned char *zl, zrangespec *range) {
}
int zzlLexValueGteMin(unsigned char *p, zlexrangespec *spec) {
- sds value = ziplistGetObject(p);
+ sds value = lpGetObject(p);
int res = zslLexValueGteMin(value,spec);
sdsfree(value);
return res;
}
int zzlLexValueLteMax(unsigned char *p, zlexrangespec *spec) {
- sds value = ziplistGetObject(p);
+ sds value = lpGetObject(p);
int res = zslLexValueLteMax(value,spec);
sdsfree(value);
return res;
@@ -935,12 +935,12 @@ int zzlIsInLexRange(unsigned char *zl, zlexrangespec *range) {
if (cmp > 0 || (cmp == 0 && (range->minex || range->maxex)))
return 0;
- p = ziplistIndex(zl,-2); /* Last element. */
+ p = lpSeek(zl,-2); /* Last element. */
if (p == NULL) return 0;
if (!zzlLexValueGteMin(p,range))
return 0;
- p = ziplistIndex(zl,0); /* First element. */
+ p = lpSeek(zl,0); /* First element. */
serverAssert(p != NULL);
if (!zzlLexValueLteMax(p,range))
return 0;
@@ -951,7 +951,7 @@ int zzlIsInLexRange(unsigned char *zl, zlexrangespec *range) {
/* Find pointer to the first element contained in the specified lex range.
* Returns NULL when no element is contained in the range. */
unsigned char *zzlFirstInLexRange(unsigned char *zl, zlexrangespec *range) {
- unsigned char *eptr = ziplistIndex(zl,0), *sptr;
+ unsigned char *eptr = lpSeek(zl,0), *sptr;
/* If everything is out of range, return early. */
if (!zzlIsInLexRange(zl,range)) return NULL;
@@ -965,9 +965,9 @@ unsigned char *zzlFirstInLexRange(unsigned char *zl, zlexrangespec *range) {
}
/* Move to next element. */
- sptr = ziplistNext(zl,eptr); /* This element score. Skip it. */
+ sptr = lpNext(zl,eptr); /* This element score. Skip it. */
serverAssert(sptr != NULL);
- eptr = ziplistNext(zl,sptr); /* Next element. */
+ eptr = lpNext(zl,sptr); /* Next element. */
}
return NULL;
@@ -976,7 +976,7 @@ unsigned char *zzlFirstInLexRange(unsigned char *zl, zlexrangespec *range) {
/* Find pointer to the last element contained in the specified lex range.
* Returns NULL when no element is contained in the range. */
unsigned char *zzlLastInLexRange(unsigned char *zl, zlexrangespec *range) {
- unsigned char *eptr = ziplistIndex(zl,-2), *sptr;
+ unsigned char *eptr = lpSeek(zl,-2), *sptr;
/* If everything is out of range, return early. */
if (!zzlIsInLexRange(zl,range)) return NULL;
@@ -991,9 +991,9 @@ unsigned char *zzlLastInLexRange(unsigned char *zl, zlexrangespec *range) {
/* Move to previous element by moving to the score of previous element.
* When this returns NULL, we know there also is no element. */
- sptr = ziplistPrev(zl,eptr);
+ sptr = lpPrev(zl,eptr);
if (sptr != NULL)
- serverAssert((eptr = ziplistPrev(zl,sptr)) != NULL);
+ serverAssert((eptr = lpPrev(zl,sptr)) != NULL);
else
eptr = NULL;
}
@@ -1001,67 +1001,56 @@ unsigned char *zzlLastInLexRange(unsigned char *zl, zlexrangespec *range) {
return NULL;
}
-unsigned char *zzlFind(unsigned char *zl, sds ele, double *score) {
- unsigned char *eptr = ziplistIndex(zl,0), *sptr;
+unsigned char *zzlFind(unsigned char *lp, sds ele, double *score) {
+ unsigned char *eptr, *sptr;
- while (eptr != NULL) {
- sptr = ziplistNext(zl,eptr);
+ if ((eptr = lpFirst(lp)) == NULL) return NULL;
+ eptr = lpFind(lp, eptr, (unsigned char*)ele, sdslen(ele), 1);
+ if (eptr) {
+ sptr = lpNext(lp,eptr);
serverAssert(sptr != NULL);
- if (ziplistCompare(eptr,(unsigned char*)ele,sdslen(ele))) {
- /* Matching element, pull out score. */
- if (score != NULL) *score = zzlGetScore(sptr);
- return eptr;
- }
-
- /* Move to next element. */
- eptr = ziplistNext(zl,sptr);
+ /* Matching element, pull out score. */
+ if (score != NULL) *score = zzlGetScore(sptr);
+ return eptr;
}
+
return NULL;
}
-/* Delete (element,score) pair from ziplist. Use local copy of eptr because we
+/* Delete (element,score) pair from listpack. Use local copy of eptr because we
* don't want to modify the one given as argument. */
unsigned char *zzlDelete(unsigned char *zl, unsigned char *eptr) {
- unsigned char *p = eptr;
-
- /* TODO: add function to ziplist API to delete N elements from offset. */
- zl = ziplistDelete(zl,&p);
- zl = ziplistDelete(zl,&p);
- return zl;
+ return lpDeleteRangeWithEntry(zl,&eptr,2);
}
unsigned char *zzlInsertAt(unsigned char *zl, unsigned char *eptr, sds ele, double score) {
unsigned char *sptr;
char scorebuf[128];
int scorelen;
- size_t offset;
scorelen = d2string(scorebuf,sizeof(scorebuf),score);
if (eptr == NULL) {
- zl = ziplistPush(zl,(unsigned char*)ele,sdslen(ele),ZIPLIST_TAIL);
- zl = ziplistPush(zl,(unsigned char*)scorebuf,scorelen,ZIPLIST_TAIL);
+ zl = lpAppend(zl,(unsigned char*)ele,sdslen(ele));
+ zl = lpAppend(zl,(unsigned char*)scorebuf,scorelen);
} else {
- /* Keep offset relative to zl, as it might be re-allocated. */
- offset = eptr-zl;
- zl = ziplistInsert(zl,eptr,(unsigned char*)ele,sdslen(ele));
- eptr = zl+offset;
+ /* Insert member before the element 'eptr'. */
+ zl = lpInsertString(zl,(unsigned char*)ele,sdslen(ele),eptr,LP_BEFORE,&sptr);
- /* Insert score after the element. */
- serverAssert((sptr = ziplistNext(zl,eptr)) != NULL);
- zl = ziplistInsert(zl,sptr,(unsigned char*)scorebuf,scorelen);
+ /* Insert score after the member. */
+ zl = lpInsertString(zl,(unsigned char*)scorebuf,scorelen,sptr,LP_AFTER,NULL);
}
return zl;
}
-/* Insert (element,score) pair in ziplist. This function assumes the element is
+/* Insert (element,score) pair in listpack. This function assumes the element is
* not yet present in the list. */
unsigned char *zzlInsert(unsigned char *zl, sds ele, double score) {
- unsigned char *eptr = ziplistIndex(zl,0), *sptr;
+ unsigned char *eptr = lpSeek(zl,0), *sptr;
double s;
while (eptr != NULL) {
- sptr = ziplistNext(zl,eptr);
+ sptr = lpNext(zl,eptr);
serverAssert(sptr != NULL);
s = zzlGetScore(sptr);
@@ -1080,7 +1069,7 @@ unsigned char *zzlInsert(unsigned char *zl, sds ele, double score) {
}
/* Move to next element. */
- eptr = ziplistNext(zl,sptr);
+ eptr = lpNext(zl,sptr);
}
/* Push on tail of list when it was not yet inserted. */
@@ -1099,14 +1088,12 @@ unsigned char *zzlDeleteRangeByScore(unsigned char *zl, zrangespec *range, unsig
eptr = zzlFirstInRange(zl,range);
if (eptr == NULL) return zl;
- /* When the tail of the ziplist is deleted, eptr will point to the sentinel
- * byte and ziplistNext will return NULL. */
- while ((sptr = ziplistNext(zl,eptr)) != NULL) {
+ /* When the tail of the listpack is deleted, eptr will be NULL. */
+ while (eptr && (sptr = lpNext(zl,eptr)) != NULL) {
score = zzlGetScore(sptr);
if (zslValueLteMax(score,range)) {
/* Delete both the element and the score. */
- zl = ziplistDelete(zl,&eptr);
- zl = ziplistDelete(zl,&eptr);
+ zl = lpDeleteRangeWithEntry(zl,&eptr,2);
num++;
} else {
/* No longer in range. */
@@ -1127,13 +1114,11 @@ unsigned char *zzlDeleteRangeByLex(unsigned char *zl, zlexrangespec *range, unsi
eptr = zzlFirstInLexRange(zl,range);
if (eptr == NULL) return zl;
- /* When the tail of the ziplist is deleted, eptr will point to the sentinel
- * byte and ziplistNext will return NULL. */
- while ((sptr = ziplistNext(zl,eptr)) != NULL) {
+ /* When the tail of the listpack is deleted, eptr will be NULL. */
+ while (eptr && (sptr = lpNext(zl,eptr)) != NULL) {
if (zzlLexValueLteMax(eptr,range)) {
/* Delete both the element and the score. */
- zl = ziplistDelete(zl,&eptr);
- zl = ziplistDelete(zl,&eptr);
+ zl = lpDeleteRangeWithEntry(zl,&eptr,2);
num++;
} else {
/* No longer in range. */
@@ -1150,7 +1135,7 @@ unsigned char *zzlDeleteRangeByLex(unsigned char *zl, zlexrangespec *range, unsi
unsigned char *zzlDeleteRangeByRank(unsigned char *zl, unsigned int start, unsigned int end, unsigned long *deleted) {
unsigned int num = (end-start)+1;
if (deleted) *deleted = num;
- zl = ziplistDeleteRange(zl,2*(start-1),2*num);
+ zl = lpDeleteRange(zl,2*(start-1),2*num);
return zl;
}
@@ -1160,7 +1145,7 @@ unsigned char *zzlDeleteRangeByRank(unsigned char *zl, unsigned int start, unsig
unsigned long zsetLength(const robj *zobj) {
unsigned long length = 0;
- if (zobj->encoding == OBJ_ENCODING_ZIPLIST) {
+ if (zobj->encoding == OBJ_ENCODING_LISTPACK) {
length = zzlLength(zobj->ptr);
} else if (zobj->encoding == OBJ_ENCODING_SKIPLIST) {
length = ((const zset*)zobj->ptr)->zsl->length;
@@ -1177,7 +1162,7 @@ void zsetConvert(robj *zobj, int encoding) {
double score;
if (zobj->encoding == encoding) return;
- if (zobj->encoding == OBJ_ENCODING_ZIPLIST) {
+ if (zobj->encoding == OBJ_ENCODING_LISTPACK) {
unsigned char *zl = zobj->ptr;
unsigned char *eptr, *sptr;
unsigned char *vstr;
@@ -1191,14 +1176,14 @@ void zsetConvert(robj *zobj, int encoding) {
zs->dict = dictCreate(&zsetDictType);
zs->zsl = zslCreate();
- eptr = ziplistIndex(zl,0);
+ eptr = lpSeek(zl,0);
serverAssertWithInfo(NULL,zobj,eptr != NULL);
- sptr = ziplistNext(zl,eptr);
+ sptr = lpNext(zl,eptr);
serverAssertWithInfo(NULL,zobj,sptr != NULL);
while (eptr != NULL) {
score = zzlGetScore(sptr);
- serverAssertWithInfo(NULL,zobj,ziplistGet(eptr,&vstr,&vlen,&vlong));
+ vstr = lpGetValue(eptr,&vlen,&vlong);
if (vstr == NULL)
ele = sdsfromlonglong(vlong);
else
@@ -1213,13 +1198,13 @@ void zsetConvert(robj *zobj, int encoding) {
zobj->ptr = zs;
zobj->encoding = OBJ_ENCODING_SKIPLIST;
} else if (zobj->encoding == OBJ_ENCODING_SKIPLIST) {
- unsigned char *zl = ziplistNew();
+ unsigned char *zl = lpNew(0);
- if (encoding != OBJ_ENCODING_ZIPLIST)
+ if (encoding != OBJ_ENCODING_LISTPACK)
serverPanic("Unknown target encoding");
/* Approach similar to zslFree(), since we want to free the skiplist at
- * the same time as creating the ziplist. */
+ * the same time as creating the listpack. */
zs = zobj->ptr;
dictRelease(zs->dict);
node = zs->zsl->header->level[0].forward;
@@ -1235,22 +1220,22 @@ void zsetConvert(robj *zobj, int encoding) {
zfree(zs);
zobj->ptr = zl;
- zobj->encoding = OBJ_ENCODING_ZIPLIST;
+ zobj->encoding = OBJ_ENCODING_LISTPACK;
} else {
serverPanic("Unknown sorted set encoding");
}
}
-/* Convert the sorted set object into a ziplist if it is not already a ziplist
+/* Convert the sorted set object into a listpack if it is not already a listpack
* and if the number of elements and the maximum element size is within the
* expected ranges. */
-void zsetConvertToZiplistIfNeeded(robj *zobj, size_t maxelelen) {
- if (zobj->encoding == OBJ_ENCODING_ZIPLIST) return;
+void zsetConvertToListpackIfNeeded(robj *zobj, size_t maxelelen) {
+ if (zobj->encoding == OBJ_ENCODING_LISTPACK) return;
zset *zset = zobj->ptr;
- if (zset->zsl->length <= server.zset_max_ziplist_entries &&
- maxelelen <= server.zset_max_ziplist_value)
- zsetConvert(zobj,OBJ_ENCODING_ZIPLIST);
+ if (zset->zsl->length <= server.zset_max_listpack_entries &&
+ maxelelen <= server.zset_max_listpack_value)
+ zsetConvert(zobj,OBJ_ENCODING_LISTPACK);
}
/* Return (by reference) the score of the specified member of the sorted set
@@ -1260,7 +1245,7 @@ void zsetConvertToZiplistIfNeeded(robj *zobj, size_t maxelelen) {
int zsetScore(robj *zobj, sds member, double *score) {
if (!zobj || !member) return C_ERR;
- if (zobj->encoding == OBJ_ENCODING_ZIPLIST) {
+ if (zobj->encoding == OBJ_ENCODING_LISTPACK) {
if (zzlFind(zobj->ptr, member, score) == NULL) return C_ERR;
} else if (zobj->encoding == OBJ_ENCODING_SKIPLIST) {
zset *zs = zobj->ptr;
@@ -1312,7 +1297,7 @@ int zsetScore(robj *zobj, sds member, double *score) {
* start.
*
* The command as a side effect of adding a new element may convert the sorted
- * set internal encoding from ziplist to hashtable+skiplist.
+ * set internal encoding from listpack to hashtable+skiplist.
*
* Memory management of 'ele':
*
@@ -1335,7 +1320,7 @@ int zsetAdd(robj *zobj, double score, sds ele, int in_flags, int *out_flags, dou
}
/* Update the sorted set according to its encoding. */
- if (zobj->encoding == OBJ_ENCODING_ZIPLIST) {
+ if (zobj->encoding == OBJ_ENCODING_LISTPACK) {
unsigned char *eptr;
if ((eptr = zzlFind(zobj->ptr,ele,&curscore)) != NULL) {
@@ -1373,8 +1358,8 @@ int zsetAdd(robj *zobj, double score, sds ele, int in_flags, int *out_flags, dou
/* Optimize: check if the element is too large or the list
* becomes too long *before* executing zzlInsert. */
zobj->ptr = zzlInsert(zobj->ptr,ele,score);
- if (zzlLength(zobj->ptr) > server.zset_max_ziplist_entries ||
- sdslen(ele) > server.zset_max_ziplist_value)
+ if (zzlLength(zobj->ptr) > server.zset_max_listpack_entries ||
+ sdslen(ele) > server.zset_max_listpack_value)
zsetConvert(zobj,OBJ_ENCODING_SKIPLIST);
if (newscore) *newscore = score;
*out_flags |= ZADD_OUT_ADDED;
@@ -1475,7 +1460,7 @@ static int zsetRemoveFromSkiplist(zset *zs, sds ele) {
/* Delete the element 'ele' from the sorted set, returning 1 if the element
* existed and was deleted, 0 otherwise (the element was not there). */
int zsetDel(robj *zobj, sds ele) {
- if (zobj->encoding == OBJ_ENCODING_ZIPLIST) {
+ if (zobj->encoding == OBJ_ENCODING_LISTPACK) {
unsigned char *eptr;
if ((eptr = zzlFind(zobj->ptr,ele,NULL)) != NULL) {
@@ -1511,18 +1496,18 @@ long zsetRank(robj *zobj, sds ele, int reverse) {
llen = zsetLength(zobj);
- if (zobj->encoding == OBJ_ENCODING_ZIPLIST) {
+ if (zobj->encoding == OBJ_ENCODING_LISTPACK) {
unsigned char *zl = zobj->ptr;
unsigned char *eptr, *sptr;
- eptr = ziplistIndex(zl,0);
+ eptr = lpSeek(zl,0);
serverAssert(eptr != NULL);
- sptr = ziplistNext(zl,eptr);
+ sptr = lpNext(zl,eptr);
serverAssert(sptr != NULL);
rank = 1;
while(eptr != NULL) {
- if (ziplistCompare(eptr,(unsigned char*)ele,sdslen(ele)))
+ if (lpCompare(eptr,(unsigned char*)ele,sdslen(ele)))
break;
rank++;
zzlNext(zl,&eptr,&sptr);
@@ -1573,13 +1558,13 @@ robj *zsetDup(robj *o) {
serverAssert(o->type == OBJ_ZSET);
/* Create a new sorted set object that have the same encoding as the original object's encoding */
- if (o->encoding == OBJ_ENCODING_ZIPLIST) {
+ if (o->encoding == OBJ_ENCODING_LISTPACK) {
unsigned char *zl = o->ptr;
- size_t sz = ziplistBlobLen(zl);
+ size_t sz = lpBytes(zl);
unsigned char *new_zl = zmalloc(sz);
memcpy(new_zl, zl, sz);
zobj = createObject(OBJ_ZSET, new_zl);
- zobj->encoding = OBJ_ENCODING_ZIPLIST;
+ zobj->encoding = OBJ_ENCODING_LISTPACK;
} else if (o->encoding == OBJ_ENCODING_SKIPLIST) {
zobj = createZsetObject();
zs = o->ptr;
@@ -1610,62 +1595,13 @@ robj *zsetDup(robj *o) {
return zobj;
}
-/* callback for to check the ziplist doesn't have duplicate records */
-static int _zsetZiplistValidateIntegrity(unsigned char *p, void *userdata) {
- struct {
- long count;
- dict *fields;
- } *data = userdata;
-
- /* Even records are field names, add to dict and check that's not a dup */
- if (((data->count) & 1) == 0) {
- unsigned char *str;
- unsigned int slen;
- long long vll;
- if (!ziplistGet(p, &str, &slen, &vll))
- return 0;
- sds field = str? sdsnewlen(str, slen): sdsfromlonglong(vll);
- if (dictAdd(data->fields, field, NULL) != DICT_OK) {
- /* Duplicate, return an error */
- sdsfree(field);
- return 0;
- }
- }
-
- (data->count)++;
- return 1;
-}
-
-/* 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 zsetZiplistValidateIntegrity(unsigned char *zl, size_t size, int deep) {
- if (!deep)
- return ziplistValidateIntegrity(zl, size, 0, NULL, NULL);
-
- /* Keep track of the field names to locate duplicate ones */
- struct {
- long count;
- dict *fields;
- } data = {0, dictCreate(&hashDictType)};
-
- int ret = ziplistValidateIntegrity(zl, size, 1, _zsetZiplistValidateIntegrity, &data);
-
- /* make sure we have an even number of records. */
- if (data.count & 1)
- ret = 0;
-
- dictRelease(data.fields);
- return ret;
-}
-
-/* Create a new sds string from the ziplist entry. */
-sds zsetSdsFromZiplistEntry(ziplistEntry *e) {
+/* Create a new sds string from the listpack entry. */
+sds zsetSdsFromListpackEntry(listpackEntry *e) {
return e->sval ? sdsnewlen(e->sval, e->slen) : sdsfromlonglong(e->lval);
}
-/* Reply with bulk string from the ziplist entry. */
-void zsetReplyFromZiplistEntry(client *c, ziplistEntry *e) {
+/* Reply with bulk string from the listpack entry. */
+void zsetReplyFromListpackEntry(client *c, listpackEntry *e) {
if (e->sval)
addReplyBulkCBuffer(c, e->sval, e->slen);
else
@@ -1677,7 +1613,7 @@ void zsetReplyFromZiplistEntry(client *c, ziplistEntry *e) {
* 'key' and 'val' will be set to hold the element.
* The memory in `key` is not to be freed or modified by the caller.
* 'score' can be NULL in which case it's not extracted. */
-void zsetTypeRandomElement(robj *zsetobj, unsigned long zsetsize, ziplistEntry *key, double *score) {
+void zsetTypeRandomElement(robj *zsetobj, unsigned long zsetsize, listpackEntry *key, double *score) {
if (zsetobj->encoding == OBJ_ENCODING_SKIPLIST) {
zset *zs = zsetobj->ptr;
dictEntry *de = dictGetFairRandomKey(zs->dict);
@@ -1686,9 +1622,9 @@ void zsetTypeRandomElement(robj *zsetobj, unsigned long zsetsize, ziplistEntry *
key->slen = sdslen(s);
if (score)
*score = *(double*)dictGetVal(de);
- } else if (zsetobj->encoding == OBJ_ENCODING_ZIPLIST) {
- ziplistEntry val;
- ziplistRandomPair(zsetobj->ptr, zsetsize, key, &val);
+ } else if (zsetobj->encoding == OBJ_ENCODING_LISTPACK) {
+ listpackEntry val;
+ lpRandomPair(zsetobj->ptr, zsetsize, key, &val);
if (score) {
if (val.sval) {
*score = zzlStrtod(val.sval,val.slen);
@@ -1787,12 +1723,12 @@ void zaddGenericCommand(client *c, int flags) {
if (checkType(c,zobj,OBJ_ZSET)) goto cleanup;
if (zobj == NULL) {
if (xx) goto reply_to_client; /* No key + XX option: nothing to do. */
- if (server.zset_max_ziplist_entries == 0 ||
- server.zset_max_ziplist_value < sdslen(c->argv[scoreidx+1]->ptr))
+ if (server.zset_max_listpack_entries == 0 ||
+ server.zset_max_listpack_value < sdslen(c->argv[scoreidx+1]->ptr))
{
zobj = createZsetObject();
} else {
- zobj = createZsetZiplistObject();
+ zobj = createZsetListpackObject();
}
dbAdd(c->db,key,zobj);
}
@@ -1930,7 +1866,7 @@ void zremrangeGenericCommand(client *c, zrange_type rangetype) {
}
/* Step 3: Perform the range deletion operation. */
- if (zobj->encoding == OBJ_ENCODING_ZIPLIST) {
+ if (zobj->encoding == OBJ_ENCODING_LISTPACK) {
switch(rangetype) {
case ZRANGE_AUTO:
case ZRANGE_RANK:
@@ -2076,11 +2012,11 @@ void zuiInitIterator(zsetopsrc *op) {
* the insertion of the elements in a new list as in
* ZDIFF/ZINTER/ZUNION */
iterzset *it = &op->iter.zset;
- if (op->encoding == OBJ_ENCODING_ZIPLIST) {
+ if (op->encoding == OBJ_ENCODING_LISTPACK) {
it->zl.zl = op->subject->ptr;
- it->zl.eptr = ziplistIndex(it->zl.zl,-2);
+ it->zl.eptr = lpSeek(it->zl.zl,-2);
if (it->zl.eptr != NULL) {
- it->zl.sptr = ziplistNext(it->zl.zl,it->zl.eptr);
+ it->zl.sptr = lpNext(it->zl.zl,it->zl.eptr);
serverAssert(it->zl.sptr != NULL);
}
} else if (op->encoding == OBJ_ENCODING_SKIPLIST) {
@@ -2109,7 +2045,7 @@ void zuiClearIterator(zsetopsrc *op) {
}
} else if (op->type == OBJ_ZSET) {
iterzset *it = &op->iter.zset;
- if (op->encoding == OBJ_ENCODING_ZIPLIST) {
+ if (op->encoding == OBJ_ENCODING_LISTPACK) {
UNUSED(it); /* skip */
} else if (op->encoding == OBJ_ENCODING_SKIPLIST) {
UNUSED(it); /* skip */
@@ -2135,7 +2071,7 @@ unsigned long zuiLength(zsetopsrc *op) {
serverPanic("Unknown set encoding");
}
} else if (op->type == OBJ_ZSET) {
- if (op->encoding == OBJ_ENCODING_ZIPLIST) {
+ if (op->encoding == OBJ_ENCODING_LISTPACK) {
return zzlLength(op->subject->ptr);
} else if (op->encoding == OBJ_ENCODING_SKIPLIST) {
zset *zs = op->subject->ptr;
@@ -2185,11 +2121,11 @@ int zuiNext(zsetopsrc *op, zsetopval *val) {
}
} else if (op->type == OBJ_ZSET) {
iterzset *it = &op->iter.zset;
- if (op->encoding == OBJ_ENCODING_ZIPLIST) {
+ if (op->encoding == OBJ_ENCODING_LISTPACK) {
/* No need to check both, but better be explicit. */
if (it->zl.eptr == NULL || it->zl.sptr == NULL)
return 0;
- serverAssert(ziplistGet(it->zl.eptr,&val->estr,&val->elen,&val->ell));
+ val->estr = lpGetValue(it->zl.eptr,&val->elen,&val->ell);
val->score = zzlGetScore(it->zl.sptr);
/* Move to next element (going backwards, see zuiInitIterator). */
@@ -2303,7 +2239,7 @@ int zuiFind(zsetopsrc *op, zsetopval *val, double *score) {
} else if (op->type == OBJ_ZSET) {
zuiSdsFromValue(val);
- if (op->encoding == OBJ_ENCODING_ZIPLIST) {
+ if (op->encoding == OBJ_ENCODING_LISTPACK) {
if (zzlFind(op->subject->ptr,val->ele,score) != NULL) {
/* Score is already set by zzlFind. */
return 1;
@@ -2738,7 +2674,7 @@ void zunionInterDiffGenericCommand(client *c, robj *dstkey, int numkeysIndex, in
if (!existing) {
tmp = zuiNewSdsFromValue(&zval);
/* Remember the longest single element encountered,
- * to understand if it's possible to convert to ziplist
+ * to understand if it's possible to convert to listpack
* at the end. */
if (sdslen(tmp) > maxelelen) maxelelen = sdslen(tmp);
/* Update the element with its initial score. */
@@ -2781,7 +2717,7 @@ void zunionInterDiffGenericCommand(client *c, robj *dstkey, int numkeysIndex, in
if (dstkey) {
if (dstzset->zsl->length) {
- zsetConvertToZiplistIfNeeded(dstobj, maxelelen);
+ zsetConvertToListpackIfNeeded(dstobj, maxelelen);
setKey(c, c->db, dstkey, dstobj);
addReplyLongLong(c, zsetLength(dstobj));
notifyKeyspaceEvent(NOTIFY_ZSET,
@@ -2940,7 +2876,7 @@ static void zrangeResultFinalizeClient(zrange_result_handler *handler,
/* Result handler methods for storing the ZRANGESTORE to a zset. */
static void zrangeResultBeginStore(zrange_result_handler *handler)
{
- handler->dstobj = createZsetZiplistObject();
+ handler->dstobj = createZsetListpackObject();
}
static void zrangeResultEmitCBufferForStore(zrange_result_handler *handler,
@@ -3046,7 +2982,7 @@ void genericZrangebyrankCommand(zrange_result_handler *handler,
rangelen = (end-start)+1;
result_cardinality = rangelen;
- if (zobj->encoding == OBJ_ENCODING_ZIPLIST) {
+ if (zobj->encoding == OBJ_ENCODING_LISTPACK) {
unsigned char *zl = zobj->ptr;
unsigned char *eptr, *sptr;
unsigned char *vstr;
@@ -3055,16 +2991,16 @@ void genericZrangebyrankCommand(zrange_result_handler *handler,
double score = 0.0;
if (reverse)
- eptr = ziplistIndex(zl,-2-(2*start));
+ eptr = lpSeek(zl,-2-(2*start));
else
- eptr = ziplistIndex(zl,2*start);
+ eptr = lpSeek(zl,2*start);
serverAssertWithInfo(c,zobj,eptr != NULL);
- sptr = ziplistNext(zl,eptr);
+ sptr = lpNext(zl,eptr);
while (rangelen--) {
serverAssertWithInfo(c,zobj,eptr != NULL && sptr != NULL);
- serverAssertWithInfo(c,zobj,ziplistGet(eptr,&vstr,&vlen,&vlong));
+ vstr = lpGetValue(eptr,&vlen,&vlong);
if (withscores) /* don't bother to extract the score if it's gonna be ignored. */
score = zzlGetScore(sptr);
@@ -3137,8 +3073,6 @@ void zrevrangeCommand(client *c) {
void genericZrangebyscoreCommand(zrange_result_handler *handler,
zrangespec *range, robj *zobj, long offset, long limit,
int reverse) {
-
- client *c = handler->client;
unsigned long rangelen = 0;
handler->beginResultEmission(handler);
@@ -3149,7 +3083,7 @@ void genericZrangebyscoreCommand(zrange_result_handler *handler,
return;
}
- if (zobj->encoding == OBJ_ENCODING_ZIPLIST) {
+ if (zobj->encoding == OBJ_ENCODING_LISTPACK) {
unsigned char *zl = zobj->ptr;
unsigned char *eptr, *sptr;
unsigned char *vstr;
@@ -3165,7 +3099,7 @@ void genericZrangebyscoreCommand(zrange_result_handler *handler,
/* Get score pointer for the first element. */
if (eptr)
- sptr = ziplistNext(zl,eptr);
+ sptr = lpNext(zl,eptr);
/* If there is an offset, just traverse the number of elements without
* checking the score because that is done in the next loop. */
@@ -3187,10 +3121,7 @@ void genericZrangebyscoreCommand(zrange_result_handler *handler,
if (!zslValueLteMax(score,range)) break;
}
- /* We know the element exists, so ziplistGet should always
- * succeed */
- serverAssertWithInfo(c,zobj,ziplistGet(eptr,&vstr,&vlen,&vlong));
-
+ vstr = lpGetValue(eptr,&vlen,&vlong);
rangelen++;
if (vstr == NULL) {
handler->emitResultFromLongLong(handler, vlong, score);
@@ -3282,7 +3213,7 @@ void zcountCommand(client *c) {
if ((zobj = lookupKeyReadOrReply(c, key, shared.czero)) == NULL ||
checkType(c, zobj, OBJ_ZSET)) return;
- if (zobj->encoding == OBJ_ENCODING_ZIPLIST) {
+ if (zobj->encoding == OBJ_ENCODING_LISTPACK) {
unsigned char *zl = zobj->ptr;
unsigned char *eptr, *sptr;
double score;
@@ -3297,7 +3228,7 @@ void zcountCommand(client *c) {
}
/* First element is in range */
- sptr = ziplistNext(zl,eptr);
+ sptr = lpNext(zl,eptr);
score = zzlGetScore(sptr);
serverAssertWithInfo(c,zobj,zslValueLteMax(score,&range));
@@ -3363,7 +3294,7 @@ void zlexcountCommand(client *c) {
return;
}
- if (zobj->encoding == OBJ_ENCODING_ZIPLIST) {
+ if (zobj->encoding == OBJ_ENCODING_LISTPACK) {
unsigned char *zl = zobj->ptr;
unsigned char *eptr, *sptr;
@@ -3378,7 +3309,7 @@ void zlexcountCommand(client *c) {
}
/* First element is in range */
- sptr = ziplistNext(zl,eptr);
+ sptr = lpNext(zl,eptr);
serverAssertWithInfo(c,zobj,zzlLexValueLteMax(eptr,&range));
/* Iterate over elements in range */
@@ -3427,12 +3358,11 @@ void genericZrangebylexCommand(zrange_result_handler *handler,
zlexrangespec *range, robj *zobj, int withscores, long offset, long limit,
int reverse)
{
- client *c = handler->client;
unsigned long rangelen = 0;
handler->beginResultEmission(handler);
- if (zobj->encoding == OBJ_ENCODING_ZIPLIST) {
+ if (zobj->encoding == OBJ_ENCODING_LISTPACK) {
unsigned char *zl = zobj->ptr;
unsigned char *eptr, *sptr;
unsigned char *vstr;
@@ -3448,7 +3378,7 @@ void genericZrangebylexCommand(zrange_result_handler *handler,
/* Get score pointer for the first element. */
if (eptr)
- sptr = ziplistNext(zl,eptr);
+ sptr = lpNext(zl,eptr);
/* If there is an offset, just traverse the number of elements without
* checking the score because that is done in the next loop. */
@@ -3472,10 +3402,7 @@ void genericZrangebylexCommand(zrange_result_handler *handler,
if (!zzlLexValueLteMax(eptr,range)) break;
}
- /* We know the element exists, so ziplistGet should always
- * succeed. */
- serverAssertWithInfo(c,zobj,ziplistGet(eptr,&vstr,&vlen,&vlong));
-
+ vstr = lpGetValue(eptr,&vlen,&vlong);
rangelen++;
if (vstr == NULL) {
handler->emitResultFromLongLong(handler, vlong, score);
@@ -3846,7 +3773,7 @@ void genericZpopCommand(client *c, robj **keyv, int keyc, int where, int emitkey
/* Remove the element. */
do {
- if (zobj->encoding == OBJ_ENCODING_ZIPLIST) {
+ if (zobj->encoding == OBJ_ENCODING_LISTPACK) {
unsigned char *zl = zobj->ptr;
unsigned char *eptr, *sptr;
unsigned char *vstr;
@@ -3854,16 +3781,16 @@ void genericZpopCommand(client *c, robj **keyv, int keyc, int where, int emitkey
long long vlong;
/* Get the first or last element in the sorted set. */
- eptr = ziplistIndex(zl,where == ZSET_MAX ? -2 : 0);
+ eptr = lpSeek(zl,where == ZSET_MAX ? -2 : 0);
serverAssertWithInfo(c,zobj,eptr != NULL);
- serverAssertWithInfo(c,zobj,ziplistGet(eptr,&vstr,&vlen,&vlong));
+ vstr = lpGetValue(eptr,&vlen,&vlong);
if (vstr == NULL)
ele = sdsfromlonglong(vlong);
else
ele = sdsnewlen(vstr,vlen);
/* Get the score. */
- sptr = ziplistNext(zl,eptr);
+ sptr = lpNext(zl,eptr);
serverAssertWithInfo(c,zobj,sptr != NULL);
score = zzlGetScore(sptr);
} else if (zobj->encoding == OBJ_ENCODING_SKIPLIST) {
@@ -3980,7 +3907,7 @@ void bzpopmaxCommand(client *c) {
blockingGenericZpopCommand(c,ZSET_MAX);
}
-static void zarndmemberReplyWithZiplist(client *c, unsigned int count, ziplistEntry *keys, ziplistEntry *vals) {
+static void zarndmemberReplyWithListpack(client *c, unsigned int count, listpackEntry *keys, listpackEntry *vals) {
for (unsigned long i = 0; i < count; i++) {
if (vals && c->resp > 2)
addReplyArrayLen(c,2);
@@ -4050,18 +3977,18 @@ void zrandmemberWithCountCommand(client *c, long l, int withscores) {
if (withscores)
addReplyDouble(c, *(double*)dictGetVal(de));
}
- } else if (zsetobj->encoding == OBJ_ENCODING_ZIPLIST) {
- ziplistEntry *keys, *vals = NULL;
+ } else if (zsetobj->encoding == OBJ_ENCODING_LISTPACK) {
+ listpackEntry *keys, *vals = NULL;
unsigned long limit, sample_count;
limit = count > ZRANDMEMBER_RANDOM_SAMPLE_LIMIT ? ZRANDMEMBER_RANDOM_SAMPLE_LIMIT : count;
- keys = zmalloc(sizeof(ziplistEntry)*limit);
+ keys = zmalloc(sizeof(listpackEntry)*limit);
if (withscores)
- vals = zmalloc(sizeof(ziplistEntry)*limit);
+ vals = zmalloc(sizeof(listpackEntry)*limit);
while (count) {
sample_count = count > limit ? limit : count;
count -= sample_count;
- ziplistRandomPairs(zsetobj->ptr, sample_count, keys, vals);
- zarndmemberReplyWithZiplist(c, sample_count, keys, vals);
+ lpRandomPairs(zsetobj->ptr, sample_count, keys, vals);
+ zarndmemberReplyWithListpack(c, sample_count, keys, vals);
}
zfree(keys);
zfree(vals);
@@ -4152,15 +4079,15 @@ void zrandmemberWithCountCommand(client *c, long l, int withscores) {
* to the temporary set, trying to eventually get enough unique elements
* to reach the specified count. */
else {
- if (zsetobj->encoding == OBJ_ENCODING_ZIPLIST) {
+ if (zsetobj->encoding == OBJ_ENCODING_LISTPACK) {
/* it is inefficient to repeatedly pick one random element from a
- * ziplist. so we use this instead: */
- ziplistEntry *keys, *vals = NULL;
- keys = zmalloc(sizeof(ziplistEntry)*count);
+ * listpack. so we use this instead: */
+ listpackEntry *keys, *vals = NULL;
+ keys = zmalloc(sizeof(listpackEntry)*count);
if (withscores)
- vals = zmalloc(sizeof(ziplistEntry)*count);
- serverAssert(ziplistRandomPairsUnique(zsetobj->ptr, count, keys, vals) == count);
- zarndmemberReplyWithZiplist(c, count, keys, vals);
+ vals = zmalloc(sizeof(listpackEntry)*count);
+ serverAssert(lpRandomPairsUnique(zsetobj->ptr, count, keys, vals) == count);
+ zarndmemberReplyWithListpack(c, count, keys, vals);
zfree(keys);
zfree(vals);
zuiClearIterator(&src);
@@ -4173,14 +4100,14 @@ void zrandmemberWithCountCommand(client *c, long l, int withscores) {
dictExpand(d, count);
while (added < count) {
- ziplistEntry key;
+ listpackEntry key;
double score;
zsetTypeRandomElement(zsetobj, size, &key, withscores ? &score: NULL);
/* Try to add the object to the dictionary. If it already exists
* free it, otherwise increment the number of objects we have
* in the result dictionary. */
- sds skey = zsetSdsFromZiplistEntry(&key);
+ sds skey = zsetSdsFromListpackEntry(&key);
if (dictAdd(d,skey,NULL) != DICT_OK) {
sdsfree(skey);
continue;
@@ -4189,7 +4116,7 @@ void zrandmemberWithCountCommand(client *c, long l, int withscores) {
if (withscores && c->resp > 2)
addReplyArrayLen(c,2);
- zsetReplyFromZiplistEntry(c, &key);
+ zsetReplyFromListpackEntry(c, &key);
if (withscores)
addReplyDouble(c, score);
}
@@ -4205,7 +4132,7 @@ void zrandmemberCommand(client *c) {
long l;
int withscores = 0;
robj *zset;
- ziplistEntry ele;
+ listpackEntry ele;
if (c->argc >= 3) {
if (getLongFromObjectOrReply(c,c->argv[2],&l,NULL) != C_OK) return;
@@ -4225,5 +4152,5 @@ void zrandmemberCommand(client *c) {
}
zsetTypeRandomElement(zset, zsetLength(zset), &ele,NULL);
- zsetReplyFromZiplistEntry(c,&ele);
+ zsetReplyFromListpackEntry(c,&ele);
}
diff --git a/src/ziplist.c b/src/ziplist.c
index b55c85fcf..34adad622 100644
--- a/src/ziplist.c
+++ b/src/ziplist.c
@@ -1498,6 +1498,7 @@ int ziplistValidateIntegrity(unsigned char *zl, size_t size, int deep,
return 1;
unsigned int count = 0;
+ unsigned int header_count = intrev16ifbe(ZIPLIST_LENGTH(zl));
unsigned char *p = ZIPLIST_ENTRY_HEAD(zl);
unsigned char *prev = NULL;
size_t prev_raw_size = 0;
@@ -1512,7 +1513,7 @@ int ziplistValidateIntegrity(unsigned char *zl, size_t size, int deep,
return 0;
/* Optionally let the caller validate the entry too. */
- if (entry_cb && !entry_cb(p, cb_userdata))
+ if (entry_cb && !entry_cb(p, header_count, cb_userdata))
return 0;
/* Move to the next entry */
@@ -1531,7 +1532,6 @@ int ziplistValidateIntegrity(unsigned char *zl, size_t size, int deep,
return 0;
/* Check that the count in the header is correct */
- unsigned int header_count = intrev16ifbe(ZIPLIST_LENGTH(zl));
if (header_count != UINT16_MAX && count != header_count)
return 0;
@@ -2464,6 +2464,32 @@ int ziplistTest(int argc, char **argv, int accurate) {
printf("%lld\n", usec()-start);
}
+ printf("Benchmark ziplistCompare with string\n");
+ {
+ unsigned long long start = usec();
+ for (int i = 0; i < 2000; i++) {
+ unsigned char *eptr = ziplistIndex(zl,0);
+ while (eptr != NULL) {
+ ziplistCompare(eptr,(unsigned char*)"nothing",7);
+ eptr = ziplistNext(zl,eptr);
+ }
+ }
+ printf("Done. usec=%lld\n", usec()-start);
+ }
+
+ printf("Benchmark ziplistCompare with number\n");
+ {
+ unsigned long long start = usec();
+ for (int i = 0; i < 2000; i++) {
+ unsigned char *eptr = ziplistIndex(zl,0);
+ while (eptr != NULL) {
+ ziplistCompare(eptr,(unsigned char*)"99999",5);
+ eptr = ziplistNext(zl,eptr);
+ }
+ }
+ printf("Done. usec=%lld\n", usec()-start);
+ }
+
zfree(zl);
}
diff --git a/src/ziplist.h b/src/ziplist.h
index 9e7997ad8..f13f4bf30 100644
--- a/src/ziplist.h
+++ b/src/ziplist.h
@@ -59,7 +59,7 @@ unsigned char *ziplistFind(unsigned char *zl, unsigned char *p, unsigned char *v
unsigned int ziplistLen(unsigned char *zl);
size_t ziplistBlobLen(unsigned char *zl);
void ziplistRepr(unsigned char *zl);
-typedef int (*ziplistValidateEntryCB)(unsigned char* p, void* userdata);
+typedef int (*ziplistValidateEntryCB)(unsigned char* p, unsigned int head_count, void* userdata);
int ziplistValidateIntegrity(unsigned char *zl, size_t size, int deep,
ziplistValidateEntryCB entry_cb, void *cb_userdata);
void ziplistRandomPair(unsigned char *zl, unsigned long total_count, ziplistEntry *key, ziplistEntry *val);
diff --git a/tests/assets/corrupt_empty_keys.rdb b/tests/assets/corrupt_empty_keys.rdb
index 8f260d493..98b6a143a 100644
--- a/tests/assets/corrupt_empty_keys.rdb
+++ b/tests/assets/corrupt_empty_keys.rdb
Binary files differ
diff --git a/tests/assets/zset-ziplist.rdb b/tests/assets/zset-ziplist.rdb
new file mode 100644
index 000000000..d5549475a
--- /dev/null
+++ b/tests/assets/zset-ziplist.rdb
Binary files differ
diff --git a/tests/integration/convert-ziplist-zset-on-load.tcl b/tests/integration/convert-ziplist-zset-on-load.tcl
new file mode 100644
index 000000000..0fbb20138
--- /dev/null
+++ b/tests/integration/convert-ziplist-zset-on-load.tcl
@@ -0,0 +1,28 @@
+tags {"external:skip"} {
+
+# Copy RDB with ziplist encoded hash to server path
+set server_path [tmpdir "server.convert-ziplist-hash-on-load"]
+
+exec cp -f tests/assets/zset-ziplist.rdb $server_path
+start_server [list overrides [list "dir" $server_path "dbfilename" "zset-ziplist.rdb"]] {
+ test "RDB load ziplist zset: converts to listpack when RDB loading" {
+ r select 0
+
+ assert_encoding listpack zset
+ assert_equal 2 [r zcard zset]
+ assert_match {one 1 two 2} [r zrange zset 0 -1 withscores]
+ }
+}
+
+exec cp -f tests/assets/zset-ziplist.rdb $server_path
+start_server [list overrides [list "dir" $server_path "dbfilename" "zset-ziplist.rdb" "zset-max-ziplist-entries" 1]] {
+ test "RDB load ziplist zset: converts to skiplist when zset-max-ziplist-entries is exceeded" {
+ r select 0
+
+ assert_encoding skiplist zset
+ assert_equal 2 [r zcard zset]
+ assert_match {one 1 two 2} [r zrange zset 0 -1 withscores]
+ }
+}
+
+}
diff --git a/tests/integration/corrupt-dump.tcl b/tests/integration/corrupt-dump.tcl
index ff956796c..c91027531 100644
--- a/tests/integration/corrupt-dump.tcl
+++ b/tests/integration/corrupt-dump.tcl
@@ -181,7 +181,8 @@ foreach sanitize_dump {no yes} {
verify_log_message 0 "*skipping empty key: hash_ziplist*" 0
verify_log_message 0 "*skipping empty key: zset*" 0
verify_log_message 0 "*skipping empty key: zset_ziplist*" 0
- verify_log_message 0 "*empty keys skipped: 8*" 0
+ verify_log_message 0 "*skipping empty key: zset_listpack*" 0
+ verify_log_message 0 "*empty keys skipped: 9*" 0
}
}
}
@@ -394,14 +395,13 @@ test {corrupt payload: fuzzer findings - empty intset} {
}
}
-test {corrupt payload: fuzzer findings - valgrind ziplist - crash report prints freed memory} {
+test {corrupt payload: fuzzer findings - zset ziplist entry lensize is 0} {
start_server [list overrides [list loglevel verbose use-exit-on-panic yes crash-memcheck-enabled no] ] {
r config set sanitize-dump-payload no
r debug set-skip-checksum-validation 1
- r RESTORE _zsetbig 0 "\x0C\x3D\x3D\x00\x00\x00\x3A\x00\x00\x00\x14\x00\x00\xF1\x02\xF1\x02\x02\x5F\x31\x04\xF2\x02\xF3\x02\xF3\x02\x02\x5F\x33\x04\xF4\x02\xEE\x02\xF5\x02\x02\x5F\x35\x04\xF6\x02\xF7\x02\xF7\x02\x02\x5F\x37\x04\xF8\x02\xF9\x02\xF9\x02\x02\x5F\x39\x04\xFA\xFF\x09\x00\xAE\xF9\x77\x2A\x47\x24\x33\xF6"
- catch { r ZREMRANGEBYSCORE _zsetbig -1050966020 724 }
- assert_equal [count_log_message 0 "crashed by signal"] 0
- assert_equal [count_log_message 0 "ASSERTION FAILED"] 1
+ catch {r RESTORE _zsetbig 0 "\x0C\x3D\x3D\x00\x00\x00\x3A\x00\x00\x00\x14\x00\x00\xF1\x02\xF1\x02\x02\x5F\x31\x04\xF2\x02\xF3\x02\xF3\x02\x02\x5F\x33\x04\xF4\x02\xEE\x02\xF5\x02\x02\x5F\x35\x04\xF6\x02\xF7\x02\xF7\x02\x02\x5F\x37\x04\xF8\x02\xF9\x02\xF9\x02\x02\x5F\x39\x04\xFA\xFF\x09\x00\xAE\xF9\x77\x2A\x47\x24\x33\xF6"} err
+ assert_match "*Bad data format*" $err
+ verify_log_message 0 "*Zset ziplist integrity check failed*" 0
}
}
@@ -523,15 +523,13 @@ test {corrupt payload: fuzzer findings - OOM in dictExpand} {
}
-test {corrupt payload: fuzzer findings - invalid tail offset after removal} {
+test {corrupt payload: fuzzer findings - zset ziplist invalid tail offset} {
start_server [list overrides [list loglevel verbose use-exit-on-panic yes crash-memcheck-enabled no] ] {
r config set sanitize-dump-payload no
r debug set-skip-checksum-validation 1
- r RESTORE _zset 0 "\x0C\x19\x19\x00\x00\x00\x02\x00\x00\x00\x06\x00\x00\xF1\x02\xF1\x02\x02\x5F\x31\x04\xF2\x02\xF3\x02\xF3\xFF\x09\x00\x4D\x72\x7B\x97\xCD\x9A\x70\xC1"
- catch {r ZPOPMIN _zset}
- catch {r ZPOPMAX _zset}
- assert_equal [count_log_message 0 "crashed by signal"] 0
- assert_equal [count_log_message 0 "ASSERTION FAILED"] 1
+ catch {r RESTORE _zset 0 "\x0C\x19\x19\x00\x00\x00\x02\x00\x00\x00\x06\x00\x00\xF1\x02\xF1\x02\x02\x5F\x31\x04\xF2\x02\xF3\x02\xF3\xFF\x09\x00\x4D\x72\x7B\x97\xCD\x9A\x70\xC1"} err
+ assert_match "*Bad data format*" $err
+ verify_log_message 0 "*Zset ziplist integrity check failed*" 0
}
}
diff --git a/tests/test_helper.tcl b/tests/test_helper.tcl
index b7b07ec41..0d8757aaf 100644
--- a/tests/test_helper.tcl
+++ b/tests/test_helper.tcl
@@ -49,6 +49,7 @@ set ::all_tests {
integration/corrupt-dump-fuzzer
integration/convert-zipmap-hash-on-load
integration/convert-ziplist-hash-on-load
+ integration/convert-ziplist-zset-on-load
integration/logging
integration/psync2
integration/psync2-reg
diff --git a/tests/unit/aofrw.tcl b/tests/unit/aofrw.tcl
index 451966d03..702348a9b 100644
--- a/tests/unit/aofrw.tcl
+++ b/tests/unit/aofrw.tcl
@@ -153,10 +153,10 @@ start_server {tags {"aofrw external:skip"} overrides {aof-use-rdb-preamble no}}
}
foreach d {string int} {
- foreach e {ziplist skiplist} {
+ foreach e {listpack skiplist} {
test "AOF rewrite of zset with $e encoding, $d data" {
r flushall
- if {$e eq {ziplist}} {set len 10} else {set len 1000}
+ if {$e eq {listpack}} {set len 10} else {set len 1000}
for {set j 0} {$j < $len} {incr j} {
if {$d eq {string}} {
set data [randstring 0 16 alpha]
diff --git a/tests/unit/keyspace.tcl b/tests/unit/keyspace.tcl
index d39f2fc6e..284f41de7 100644
--- a/tests/unit/keyspace.tcl
+++ b/tests/unit/keyspace.tcl
@@ -282,10 +282,10 @@ start_server {tags {"keyspace"}} {
assert_equal $digest [debug_digest_value newset2{t}]
}
- test {COPY basic usage for ziplist sorted set} {
+ test {COPY basic usage for listpack sorted set} {
r del zset1{t} newzset1{t}
r zadd zset1{t} 123 foobar
- assert_encoding ziplist zset1{t}
+ assert_encoding listpack zset1{t}
r copy zset1{t} newzset1{t}
set digest [debug_digest_value zset1{t}]
assert_equal $digest [debug_digest_value newzset1{t}]
diff --git a/tests/unit/scan.tcl b/tests/unit/scan.tcl
index 870f1a145..5dea76be7 100644
--- a/tests/unit/scan.tcl
+++ b/tests/unit/scan.tcl
@@ -172,11 +172,11 @@ start_server {tags {"scan network"}} {
}
}
- foreach enc {ziplist skiplist} {
+ foreach enc {listpack skiplist} {
test "ZSCAN with encoding $enc" {
# Create the Sorted Set
r del zset
- if {$enc eq {ziplist}} {
+ if {$enc eq {listpack}} {
set count 30
} else {
set count 1000
diff --git a/tests/unit/type/zset.tcl b/tests/unit/type/zset.tcl
index 75d51bb2e..84449a83a 100644
--- a/tests/unit/type/zset.tcl
+++ b/tests/unit/type/zset.tcl
@@ -9,7 +9,7 @@ start_server {tags {"zset"}} {
proc basics {encoding} {
set original_max_entries [lindex [r config get zset-max-ziplist-entries] 1]
set original_max_value [lindex [r config get zset-max-ziplist-value] 1]
- if {$encoding == "ziplist"} {
+ if {$encoding == "listpack"} {
r config set zset-max-ziplist-entries 128
r config set zset-max-ziplist-value 64
} elseif {$encoding == "skiplist"} {
@@ -1007,7 +1007,7 @@ start_server {tags {"zset"}} {
r config set zset-max-ziplist-value $original_max_value
}
- basics ziplist
+ basics listpack
basics skiplist
test {ZINTERSTORE regression with two sets, intset+hashtable} {
@@ -1104,7 +1104,7 @@ start_server {tags {"zset"}} {
proc stressers {encoding} {
set original_max_entries [lindex [r config get zset-max-ziplist-entries] 1]
set original_max_value [lindex [r config get zset-max-ziplist-value] 1]
- if {$encoding == "ziplist"} {
+ if {$encoding == "listpack"} {
# Little extra to allow proper fuzzing in the sorting stresser
r config set zset-max-ziplist-entries 256
r config set zset-max-ziplist-value 64
@@ -1533,7 +1533,7 @@ start_server {tags {"zset"}} {
}
tags {"slow"} {
- stressers ziplist
+ stressers listpack
stressers skiplist
}
@@ -1686,7 +1686,7 @@ start_server {tags {"zset"}} {
}
}
- foreach {type contents} "ziplist {1 a 2 b 3 c} skiplist {1 a 2 b 3 [randstring 70 90 alpha]}" {
+ foreach {type contents} "listpack {1 a 2 b 3 c} skiplist {1 a 2 b 3 [randstring 70 90 alpha]}" {
set original_max_value [lindex [r config get zset-max-ziplist-value] 1]
r config set zset-max-ziplist-value 10
create_zset myzset $contents
@@ -1739,7 +1739,7 @@ start_server {tags {"zset"}} {
foreach {type contents} "
skiplist {1 a 2 b 3 c 4 d 5 e 6 f 7 g 7 h 9 i 10 [randstring 70 90 alpha]}
- ziplist {1 a 2 b 3 c 4 d 5 e 6 f 7 g 7 h 9 i 10 j} " {
+ listpack {1 a 2 b 3 c 4 d 5 e 6 f 7 g 7 h 9 i 10 j} " {
test "ZRANDMEMBER with <count> - $type" {
set original_max_value [lindex [r config get zset-max-ziplist-value] 1]
r config set zset-max-ziplist-value 10
View Lorry Controller Status