############################### ADVANCED CONFIG ###############################
-# Hashes are encoded in a special way (much more memory efficient) when they
-# have at max a given number of elements, and the biggest element does not
-# exceed a given threshold. You can configure this limits with the following
-# configuration directives.
-hash-max-zipmap-entries 512
-hash-max-zipmap-value 64
+# Hashes are encoded using a memory efficient data structure when they have a
+# small number of entries, and the biggest entry does not exceed a given
+# threshold. These thresholds can be configured using the following directives.
+hash-max-ziplist-entries 512
+hash-max-ziplist-value 64
# Similarly to hashes, small lists are also encoded in a special way in order
# to save a lot of space. The special representation is only used when
return 1;
}
+static int rioWriteHashIteratorCursor(rio *r, hashTypeIterator *hi, int what) {
+ if (hi->encoding == REDIS_ENCODING_ZIPLIST) {
+ unsigned char *vstr = NULL;
+ unsigned int vlen = UINT_MAX;
+ long long vll = LLONG_MAX;
+
+ hashTypeCurrentFromZiplist(hi, what, &vstr, &vlen, &vll);
+ if (vstr) {
+ return rioWriteBulkString(r, (char*)vstr, vlen);
+ } else {
+ return rioWriteBulkLongLong(r, vll);
+ }
+
+ } else if (hi->encoding == REDIS_ENCODING_HT) {
+ robj *value;
+
+ hashTypeCurrentFromHashTable(hi, what, &value);
+ return rioWriteBulkObject(r, value);
+ }
+
+ redisPanic("Unknown hash encoding");
+ return 0;
+}
+
/* Emit the commands needed to rebuild a hash object.
* The function returns 0 on error, 1 on success. */
int rewriteHashObject(rio *r, robj *key, robj *o) {
+ hashTypeIterator *hi;
long long count = 0, items = hashTypeLength(o);
- if (o->encoding == REDIS_ENCODING_ZIPMAP) {
- unsigned char *p = zipmapRewind(o->ptr);
- unsigned char *field, *val;
- unsigned int flen, vlen;
+ hi = hashTypeInitIterator(o);
+ while (hashTypeNext(hi) != REDIS_ERR) {
+ if (count == 0) {
+ int cmd_items = (items > REDIS_AOF_REWRITE_ITEMS_PER_CMD) ?
+ REDIS_AOF_REWRITE_ITEMS_PER_CMD : items;
- while((p = zipmapNext(p,&field,&flen,&val,&vlen)) != NULL) {
- if (count == 0) {
- int cmd_items = (items > REDIS_AOF_REWRITE_ITEMS_PER_CMD) ?
- REDIS_AOF_REWRITE_ITEMS_PER_CMD : items;
-
- if (rioWriteBulkCount(r,'*',2+cmd_items*2) == 0) return 0;
- if (rioWriteBulkString(r,"HMSET",5) == 0) return 0;
- if (rioWriteBulkObject(r,key) == 0) return 0;
- }
- if (rioWriteBulkString(r,(char*)field,flen) == 0) return 0;
- if (rioWriteBulkString(r,(char*)val,vlen) == 0) return 0;
- if (++count == REDIS_AOF_REWRITE_ITEMS_PER_CMD) count = 0;
- items--;
+ if (rioWriteBulkCount(r,'*',2+cmd_items*2) == 0) return 0;
+ if (rioWriteBulkString(r,"HMSET",5) == 0) return 0;
+ if (rioWriteBulkObject(r,key) == 0) return 0;
}
- } else {
- dictIterator *di = dictGetIterator(o->ptr);
- dictEntry *de;
- while((de = dictNext(di)) != NULL) {
- robj *field = dictGetKey(de);
- robj *val = dictGetVal(de);
+ if (rioWriteHashIteratorCursor(r, hi, REDIS_HASH_KEY) == 0) return 0;
+ if (rioWriteHashIteratorCursor(r, hi, REDIS_HASH_VALUE) == 0) return 0;
+ if (++count == REDIS_AOF_REWRITE_ITEMS_PER_CMD) count = 0;
+ items--;
+ }
- if (count == 0) {
- int cmd_items = (items > REDIS_AOF_REWRITE_ITEMS_PER_CMD) ?
- REDIS_AOF_REWRITE_ITEMS_PER_CMD : items;
+ hashTypeReleaseIterator(hi);
- if (rioWriteBulkCount(r,'*',2+cmd_items*2) == 0) return 0;
- if (rioWriteBulkString(r,"HMSET",5) == 0) return 0;
- if (rioWriteBulkObject(r,key) == 0) return 0;
- }
- if (rioWriteBulkObject(r,field) == 0) return 0;
- if (rioWriteBulkObject(r,val) == 0) return 0;
- if (++count == REDIS_AOF_REWRITE_ITEMS_PER_CMD) count = 0;
- items--;
- }
- dictReleaseIterator(di);
- }
return 1;
}
zfree(server.rdb_filename);
server.rdb_filename = zstrdup(argv[1]);
} else if (!strcasecmp(argv[0],"hash-max-zipmap-entries") && argc == 2) {
- server.hash_max_zipmap_entries = memtoll(argv[1], NULL);
+ redisLog(REDIS_WARNING, "Deprecated configuration directive: \"%s\"", argv[0]);
+ server.hash_max_ziplist_entries = memtoll(argv[1], NULL);
} else if (!strcasecmp(argv[0],"hash-max-zipmap-value") && argc == 2) {
- server.hash_max_zipmap_value = memtoll(argv[1], NULL);
+ redisLog(REDIS_WARNING, "Deprecated configuration directive: \"%s\"", argv[0]);
+ server.hash_max_ziplist_value = memtoll(argv[1], NULL);
+ } else if (!strcasecmp(argv[0],"hash-max-ziplist-entries") && argc == 2) {
+ server.hash_max_ziplist_entries = memtoll(argv[1], NULL);
+ } else if (!strcasecmp(argv[0],"hash-max-ziplist-value") && argc == 2) {
+ server.hash_max_ziplist_value = memtoll(argv[1], NULL);
} else if (!strcasecmp(argv[0],"list-max-ziplist-entries") && argc == 2){
server.list_max_ziplist_entries = memtoll(argv[1], NULL);
} else if (!strcasecmp(argv[0],"list-max-ziplist-value") && argc == 2) {
addReplyErrorFormat(c,"Changing directory: %s", strerror(errno));
return;
}
- } else if (!strcasecmp(c->argv[2]->ptr,"hash-max-zipmap-entries")) {
+ } else if (!strcasecmp(c->argv[2]->ptr,"hash-max-ziplist-entries")) {
if (getLongLongFromObject(o,&ll) == REDIS_ERR || ll < 0) goto badfmt;
- server.hash_max_zipmap_entries = ll;
- } else if (!strcasecmp(c->argv[2]->ptr,"hash-max-zipmap-value")) {
+ server.hash_max_ziplist_entries = ll;
+ } else if (!strcasecmp(c->argv[2]->ptr,"hash-max-ziplist-value")) {
if (getLongLongFromObject(o,&ll) == REDIS_ERR || ll < 0) goto badfmt;
- server.hash_max_zipmap_value = ll;
+ server.hash_max_ziplist_value = ll;
} else if (!strcasecmp(c->argv[2]->ptr,"list-max-ziplist-entries")) {
if (getLongLongFromObject(o,&ll) == REDIS_ERR || ll < 0) goto badfmt;
server.list_max_ziplist_entries = ll;
server.aof_rewrite_perc);
config_get_numerical_field("auto-aof-rewrite-min-size",
server.aof_rewrite_min_size);
- config_get_numerical_field("hash-max-zipmap-entries",
- server.hash_max_zipmap_entries);
- config_get_numerical_field("hash-max-zipmap-value",
- server.hash_max_zipmap_value);
+ config_get_numerical_field("hash-max-ziplist-entries",
+ server.hash_max_ziplist_entries);
+ config_get_numerical_field("hash-max-ziplist-value",
+ server.hash_max_ziplist_value);
config_get_numerical_field("list-max-ziplist-entries",
server.list_max_ziplist_entries);
config_get_numerical_field("list-max-ziplist-value",
}
robj *createHashObject(void) {
- /* All the Hashes start as zipmaps. Will be automatically converted
- * into hash tables if there are enough elements or big elements
- * inside. */
- unsigned char *zm = zipmapNew();
- robj *o = createObject(REDIS_HASH,zm);
- o->encoding = REDIS_ENCODING_ZIPMAP;
+ unsigned char *zl = ziplistNew();
+ robj *o = createObject(REDIS_HASH, zl);
+ o->encoding = REDIS_ENCODING_ZIPLIST;
return o;
}
case REDIS_ENCODING_HT:
dictRelease((dict*) o->ptr);
break;
- case REDIS_ENCODING_ZIPMAP:
+ case REDIS_ENCODING_ZIPLIST:
zfree(o->ptr);
break;
default:
case REDIS_ENCODING_RAW: return "raw";
case REDIS_ENCODING_INT: return "int";
case REDIS_ENCODING_HT: return "hashtable";
- case REDIS_ENCODING_ZIPMAP: return "zipmap";
case REDIS_ENCODING_LINKEDLIST: return "linkedlist";
case REDIS_ENCODING_ZIPLIST: return "ziplist";
case REDIS_ENCODING_INTSET: return "intset";
#include "redis.h"
#include "lzf.h" /* LZF compression library */
+#include "zipmap.h"
#include <math.h>
#include <sys/types.h>
else
redisPanic("Unknown sorted set encoding");
case REDIS_HASH:
- if (o->encoding == REDIS_ENCODING_ZIPMAP)
- return rdbSaveType(rdb,REDIS_RDB_TYPE_HASH_ZIPMAP);
+ if (o->encoding == REDIS_ENCODING_ZIPLIST)
+ return rdbSaveType(rdb,REDIS_RDB_TYPE_HASH_ZIPLIST);
else if (o->encoding == REDIS_ENCODING_HT)
return rdbSaveType(rdb,REDIS_RDB_TYPE_HASH);
else
}
} else if (o->type == REDIS_HASH) {
/* Save a hash value */
- if (o->encoding == REDIS_ENCODING_ZIPMAP) {
- size_t l = zipmapBlobLen((unsigned char*)o->ptr);
+ if (o->encoding == REDIS_ENCODING_ZIPLIST) {
+ size_t l = ziplistBlobLen((unsigned char*)o->ptr);
if ((n = rdbSaveRawString(rdb,o->ptr,l)) == -1) return -1;
nwritten += n;
- } else {
+
+ } else if (o->encoding == REDIS_ENCODING_HT) {
dictIterator *di = dictGetIterator(o->ptr);
dictEntry *de;
nwritten += n;
}
dictReleaseIterator(di);
+
+ } else {
+ redisPanic("Unknown hash encoding");
}
+
} else {
redisPanic("Unknown object type");
}
maxelelen <= server.zset_max_ziplist_value)
zsetConvert(o,REDIS_ENCODING_ZIPLIST);
} else if (rdbtype == REDIS_RDB_TYPE_HASH) {
- size_t hashlen;
+ size_t len;
+ int ret;
+
+ len = rdbLoadLen(rdb, NULL);
+ if (len == REDIS_RDB_LENERR) return NULL;
- if ((hashlen = rdbLoadLen(rdb,NULL)) == REDIS_RDB_LENERR) return NULL;
o = createHashObject();
+
/* Too many entries? Use an hash table. */
- if (hashlen > server.hash_max_zipmap_entries)
- convertToRealHash(o);
- /* Load every key/value, then set it into the zipmap or hash
- * table, as needed. */
- while(hashlen--) {
- robj *key, *val;
-
- if ((key = rdbLoadEncodedStringObject(rdb)) == NULL) return NULL;
- if ((val = rdbLoadEncodedStringObject(rdb)) == NULL) return NULL;
- /* If we are using a zipmap and there are too big values
- * the object is converted to real hash table encoding. */
- if (o->encoding != REDIS_ENCODING_HT &&
- ((key->encoding == REDIS_ENCODING_RAW &&
- sdslen(key->ptr) > server.hash_max_zipmap_value) ||
- (val->encoding == REDIS_ENCODING_RAW &&
- sdslen(val->ptr) > server.hash_max_zipmap_value)))
+ if (len > server.hash_max_ziplist_entries)
+ hashTypeConvert(o, REDIS_ENCODING_HT);
+
+ /* Load every field and value into the ziplist */
+ while (o->encoding == REDIS_ENCODING_ZIPLIST && len-- > 0) {
+ robj *field, *value;
+
+ /* Load raw strings */
+ field = rdbLoadStringObject(rdb);
+ if (field == NULL) return NULL;
+ redisAssert(field->encoding == REDIS_ENCODING_RAW);
+ value = rdbLoadStringObject(rdb);
+ if (value == NULL) return NULL;
+ redisAssert(field->encoding == REDIS_ENCODING_RAW);
+
+ /* Convert to hash table if size threshold is exceeded */
+ if (sdslen(field->ptr) > server.hash_max_ziplist_value ||
+ sdslen(value->ptr) > server.hash_max_ziplist_value)
{
- convertToRealHash(o);
+ hashTypeConvert(o, REDIS_ENCODING_HT);
+ break;
}
- if (o->encoding == REDIS_ENCODING_ZIPMAP) {
- unsigned char *zm = o->ptr;
- robj *deckey, *decval;
-
- /* We need raw string objects to add them to the zipmap */
- deckey = getDecodedObject(key);
- decval = getDecodedObject(val);
- zm = zipmapSet(zm,deckey->ptr,sdslen(deckey->ptr),
- decval->ptr,sdslen(decval->ptr),NULL);
- o->ptr = zm;
- decrRefCount(deckey);
- decrRefCount(decval);
- decrRefCount(key);
- decrRefCount(val);
- } else {
- key = tryObjectEncoding(key);
- val = tryObjectEncoding(val);
- dictAdd((dict*)o->ptr,key,val);
- }
+ /* Add pair to ziplist */
+ o->ptr = ziplistPush(o->ptr, field->ptr, sdslen(field->ptr), ZIPLIST_TAIL);
+ o->ptr = ziplistPush(o->ptr, value->ptr, sdslen(value->ptr), ZIPLIST_TAIL);
}
+
+ /* Load remaining fields and values into the hash table */
+ while (o->encoding == REDIS_ENCODING_HT && len-- > 0) {
+ robj *field, *value;
+
+ /* Load encoded strings */
+ field = rdbLoadEncodedStringObject(rdb);
+ if (field == NULL) return NULL;
+ value = rdbLoadEncodedStringObject(rdb);
+ if (value == NULL) return NULL;
+
+ field = tryObjectEncoding(field);
+ value = tryObjectEncoding(value);
+
+ /* Add pair to hash table */
+ ret = dictAdd((dict*)o->ptr, field, value);
+ redisAssert(ret == REDIS_OK);
+ }
+
+ /* All pairs should be read by now */
+ redisAssert(len == 0);
+
} else if (rdbtype == REDIS_RDB_TYPE_HASH_ZIPMAP ||
rdbtype == REDIS_RDB_TYPE_LIST_ZIPLIST ||
rdbtype == REDIS_RDB_TYPE_SET_INTSET ||
- rdbtype == REDIS_RDB_TYPE_ZSET_ZIPLIST)
+ rdbtype == REDIS_RDB_TYPE_ZSET_ZIPLIST ||
+ rdbtype == REDIS_RDB_TYPE_HASH_ZIPLIST)
{
robj *aux = rdbLoadStringObject(rdb);
* converted. */
switch(rdbtype) {
case REDIS_RDB_TYPE_HASH_ZIPMAP:
- o->type = REDIS_HASH;
- o->encoding = REDIS_ENCODING_ZIPMAP;
- if (zipmapLen(o->ptr) > server.hash_max_zipmap_entries)
- convertToRealHash(o);
+ /* Convert to ziplist encoded hash. This must be deprecated
+ * when loading dumps created by Redis 2.4 gets deprecated. */
+ {
+ unsigned char *zl = ziplistNew();
+ unsigned char *zi = zipmapRewind(o->ptr);
+ unsigned char *fstr, *vstr;
+ unsigned int flen, vlen;
+ unsigned int maxlen = 0;
+
+ while ((zi = zipmapNext(zi, &fstr, &flen, &vstr, &vlen)) != NULL) {
+ if (flen > maxlen) maxlen = flen;
+ if (vlen > maxlen) maxlen = vlen;
+ zl = ziplistPush(zl, fstr, flen, ZIPLIST_TAIL);
+ zl = ziplistPush(zl, vstr, vlen, ZIPLIST_TAIL);
+ }
+
+ zfree(o->ptr);
+ o->ptr = zl;
+ o->type = REDIS_HASH;
+ o->encoding = REDIS_ENCODING_ZIPLIST;
+
+ if (hashTypeLength(o) > server.hash_max_ziplist_entries ||
+ maxlen > server.hash_max_ziplist_value)
+ {
+ hashTypeConvert(o, REDIS_ENCODING_HT);
+ }
+ }
break;
case REDIS_RDB_TYPE_LIST_ZIPLIST:
o->type = REDIS_LIST;
if (zsetLength(o) > server.zset_max_ziplist_entries)
zsetConvert(o,REDIS_ENCODING_SKIPLIST);
break;
+ case REDIS_RDB_TYPE_HASH_ZIPLIST:
+ o->type = REDIS_HASH;
+ o->encoding = REDIS_ENCODING_ZIPLIST;
+ if (hashTypeLength(o) > server.hash_max_ziplist_entries)
+ hashTypeConvert(o, REDIS_ENCODING_HT);
+ break;
default:
redisPanic("Unknown encoding");
break;
#define REDIS_RDB_TYPE_LIST_ZIPLIST 10
#define REDIS_RDB_TYPE_SET_INTSET 11
#define REDIS_RDB_TYPE_ZSET_ZIPLIST 12
+#define REDIS_RDB_TYPE_HASH_ZIPLIST 13
/* Test if a type is an object type. */
#define rdbIsObjectType(t) ((t >= 0 && t <= 4) || (t >= 9 && t <= 12))
server.maxmemory = 0;
server.maxmemory_policy = REDIS_MAXMEMORY_VOLATILE_LRU;
server.maxmemory_samples = 3;
- server.hash_max_zipmap_entries = REDIS_HASH_MAX_ZIPMAP_ENTRIES;
- server.hash_max_zipmap_value = REDIS_HASH_MAX_ZIPMAP_VALUE;
+ server.hash_max_ziplist_entries = REDIS_HASH_MAX_ZIPLIST_ENTRIES;
+ server.hash_max_ziplist_value = REDIS_HASH_MAX_ZIPLIST_VALUE;
server.list_max_ziplist_entries = REDIS_LIST_MAX_ZIPLIST_ENTRIES;
server.list_max_ziplist_value = REDIS_LIST_MAX_ZIPLIST_VALUE;
server.set_max_intset_entries = REDIS_SET_MAX_INTSET_ENTRIES;
#include "adlist.h" /* Linked lists */
#include "zmalloc.h" /* total memory usage aware version of malloc/free */
#include "anet.h" /* Networking the easy way */
-#include "zipmap.h" /* Compact string -> string data structure */
#include "ziplist.h" /* Compact list data structure */
#include "intset.h" /* Compact integer set structure */
#include "version.h" /* Version macro */
#define AOF_FSYNC_EVERYSEC 2
/* Zip structure related defaults */
-#define REDIS_HASH_MAX_ZIPMAP_ENTRIES 512
-#define REDIS_HASH_MAX_ZIPMAP_VALUE 64
+#define REDIS_HASH_MAX_ZIPLIST_ENTRIES 512
+#define REDIS_HASH_MAX_ZIPLIST_VALUE 64
#define REDIS_LIST_MAX_ZIPLIST_ENTRIES 512
#define REDIS_LIST_MAX_ZIPLIST_VALUE 64
#define REDIS_SET_MAX_INTSET_ENTRIES 512
int sort_alpha;
int sort_bypattern;
/* Zip structure config, see redis.conf for more information */
- size_t hash_max_zipmap_entries;
- size_t hash_max_zipmap_value;
+ size_t hash_max_ziplist_entries;
+ size_t hash_max_ziplist_value;
size_t list_max_ziplist_entries;
size_t list_max_ziplist_value;
size_t set_max_intset_entries;
* not both are required, store pointers in the iterator to avoid
* unnecessary memory allocation for fields/values. */
typedef struct {
+ robj *subject;
int encoding;
- unsigned char *zi;
- unsigned char *zk, *zv;
- unsigned int zklen, zvlen;
+
+ unsigned char *fptr, *vptr;
dictIterator *di;
dictEntry *de;
void setTypeConvert(robj *subject, int enc);
/* Hash data type */
-void convertToRealHash(robj *o);
+void hashTypeConvert(robj *o, int enc);
void hashTypeTryConversion(robj *subject, robj **argv, int start, int end);
void hashTypeTryObjectEncoding(robj *subject, robj **o1, robj **o2);
-int hashTypeGet(robj *o, robj *key, robj **objval, unsigned char **v, unsigned int *vlen);
robj *hashTypeGetObject(robj *o, robj *key);
int hashTypeExists(robj *o, robj *key);
int hashTypeSet(robj *o, robj *key, robj *value);
hashTypeIterator *hashTypeInitIterator(robj *subject);
void hashTypeReleaseIterator(hashTypeIterator *hi);
int hashTypeNext(hashTypeIterator *hi);
-int hashTypeCurrent(hashTypeIterator *hi, int what, robj **objval, unsigned char **v, unsigned int *vlen);
+void hashTypeCurrentFromZiplist(hashTypeIterator *hi, int what,
+ unsigned char **vstr,
+ unsigned int *vlen,
+ long long *vll);
+void hashTypeCurrentFromHashTable(hashTypeIterator *hi, int what, robj **dst);
robj *hashTypeCurrentObject(hashTypeIterator *hi, int what);
robj *hashTypeLookupWriteOrCreate(redisClient *c, robj *key);
#include "redis.h"
-
#include <math.h>
/*-----------------------------------------------------------------------------
*----------------------------------------------------------------------------*/
/* Check the length of a number of objects to see if we need to convert a
- * zipmap to a real hash. Note that we only check string encoded objects
+ * ziplist to a real hash. Note that we only check string encoded objects
* as their string length can be queried in constant time. */
-void hashTypeTryConversion(robj *subject, robj **argv, int start, int end) {
+void hashTypeTryConversion(robj *o, robj **argv, int start, int end) {
int i;
- if (subject->encoding != REDIS_ENCODING_ZIPMAP) return;
+
+ if (o->encoding != REDIS_ENCODING_ZIPLIST) return;
for (i = start; i <= end; i++) {
if (argv[i]->encoding == REDIS_ENCODING_RAW &&
- sdslen(argv[i]->ptr) > server.hash_max_zipmap_value)
+ sdslen(argv[i]->ptr) > server.hash_max_ziplist_value)
{
- convertToRealHash(subject);
- return;
+ hashTypeConvert(o, REDIS_ENCODING_HT);
+ break;
}
}
}
}
}
-/* Get the value from a hash identified by key.
- *
- * If the string is found either REDIS_ENCODING_HT or REDIS_ENCODING_ZIPMAP
- * is returned, and either **objval or **v and *vlen are set accordingly,
- * so that objects in hash tables are returend as objects and pointers
- * inside a zipmap are returned as such.
- *
- * If the object was not found -1 is returned.
- *
- * This function is copy on write friendly as there is no incr/decr
- * of refcount needed if objects are accessed just for reading operations. */
-int hashTypeGet(robj *o, robj *key, robj **objval, unsigned char **v,
- unsigned int *vlen)
+/* Get the value from a ziplist encoded hash, identified by field.
+ * Returns -1 when the field cannot be found. */
+int hashTypeGetFromZiplist(robj *o, robj *field,
+ unsigned char **vstr,
+ unsigned int *vlen,
+ long long *vll)
{
- if (o->encoding == REDIS_ENCODING_ZIPMAP) {
- int found;
+ unsigned char *zl, *fptr = NULL, *vptr = NULL;
+ int ret;
- key = getDecodedObject(key);
- found = zipmapGet(o->ptr,key->ptr,sdslen(key->ptr),v,vlen);
- decrRefCount(key);
- if (!found) return -1;
- } else {
- dictEntry *de = dictFind(o->ptr,key);
- if (de == NULL) return -1;
- *objval = dictGetVal(de);
+ redisAssert(o->encoding == REDIS_ENCODING_ZIPLIST);
+
+ field = getDecodedObject(field);
+
+ zl = o->ptr;
+ fptr = ziplistIndex(zl, ZIPLIST_HEAD);
+ if (fptr != NULL) {
+ fptr = ziplistFind(fptr, field->ptr, sdslen(field->ptr), 1);
+ if (fptr != NULL) {
+ /* Grab pointer to the value (fptr points to the field) */
+ vptr = ziplistNext(zl, fptr);
+ redisAssert(vptr != NULL);
+ }
}
- return o->encoding;
+
+ decrRefCount(field);
+
+ if (vptr != NULL) {
+ ret = ziplistGet(vptr, vstr, vlen, vll);
+ redisAssert(ret);
+ return 0;
+ }
+
+ return -1;
}
-/* Higher level function of hashTypeGet() that always returns a Redis
+/* Get the value from a hash table encoded hash, identified by field.
+ * Returns -1 when the field cannot be found. */
+int hashTypeGetFromHashTable(robj *o, robj *field, robj **value) {
+ dictEntry *de;
+
+ redisAssert(o->encoding == REDIS_ENCODING_HT);
+
+ de = dictFind(o->ptr, field);
+ if (de == NULL) {
+ return -1;
+ }
+
+ *value = dictGetVal(de);
+ return 0;
+}
+
+/* Higher level function of hashTypeGet*() that always returns a Redis
* object (either new or with refcount incremented), so that the caller
* can retain a reference or call decrRefCount after the usage.
*
* The lower level function can prevent copy on write so it is
* the preferred way of doing read operations. */
-robj *hashTypeGetObject(robj *o, robj *key) {
- robj *objval;
- unsigned char *v;
- unsigned int vlen;
-
- int encoding = hashTypeGet(o,key,&objval,&v,&vlen);
- switch(encoding) {
- case REDIS_ENCODING_HT:
- incrRefCount(objval);
- return objval;
- case REDIS_ENCODING_ZIPMAP:
- objval = createStringObject((char*)v,vlen);
- return objval;
- default: return NULL;
- }
-}
-
-/* Test if the key exists in the given hash. Returns 1 if the key
- * exists and 0 when it doesn't. */
-int hashTypeExists(robj *o, robj *key) {
- if (o->encoding == REDIS_ENCODING_ZIPMAP) {
- key = getDecodedObject(key);
- if (zipmapExists(o->ptr,key->ptr,sdslen(key->ptr))) {
- decrRefCount(key);
- return 1;
+robj *hashTypeGetObject(robj *o, robj *field) {
+ robj *value = NULL;
+
+ if (o->encoding == REDIS_ENCODING_ZIPLIST) {
+ unsigned char *vstr = NULL;
+ unsigned int vlen = UINT_MAX;
+ long long vll = LLONG_MAX;
+
+ if (hashTypeGetFromZiplist(o, field, &vstr, &vlen, &vll) == 0) {
+ if (vstr) {
+ value = createStringObject((char*)vstr, vlen);
+ } else {
+ value = createStringObjectFromLongLong(vll);
+ }
+ }
+
+ } else if (o->encoding == REDIS_ENCODING_HT) {
+ robj *aux;
+
+ if (hashTypeGetFromHashTable(o, field, &aux) == 0) {
+ incrRefCount(aux);
+ value = aux;
}
- decrRefCount(key);
+
} else {
- if (dictFind(o->ptr,key) != NULL) {
+ redisPanic("Unknown hash encoding");
+ }
+
+ return value;
+}
+
+/* Test if the specified field exists in the given hash. Returns 1 if the field
+ * exists, and 0 when it doesn't. */
+int hashTypeExists(robj *o, robj *field) {
+ if (o->encoding == REDIS_ENCODING_ZIPLIST) {
+ unsigned char *vstr = NULL;
+ unsigned int vlen = UINT_MAX;
+ long long vll = LLONG_MAX;
+
+ if (hashTypeGetFromZiplist(o, field, &vstr, &vlen, &vll) == 0) {
return 1;
}
+
+ } else if (o->encoding == REDIS_ENCODING_HT) {
+ robj *aux;
+
+ if (hashTypeGetFromHashTable(o, field, &aux) == 0) {
+ return 1;
+ }
+
+ } else {
+ redisPanic("Unknown hash encoding");
}
+
return 0;
}
/* Add an element, discard the old if the key already exists.
* Return 0 on insert and 1 on update. */
-int hashTypeSet(robj *o, robj *key, robj *value) {
+int hashTypeSet(robj *o, robj *field, robj *value) {
int update = 0;
- if (o->encoding == REDIS_ENCODING_ZIPMAP) {
- key = getDecodedObject(key);
+
+ if (o->encoding == REDIS_ENCODING_ZIPLIST) {
+ unsigned char *zl, *fptr, *vptr;
+
+ field = getDecodedObject(field);
value = getDecodedObject(value);
- o->ptr = zipmapSet(o->ptr,
- key->ptr,sdslen(key->ptr),
- value->ptr,sdslen(value->ptr), &update);
- decrRefCount(key);
+
+ zl = o->ptr;
+ fptr = ziplistIndex(zl, ZIPLIST_HEAD);
+ if (fptr != NULL) {
+ fptr = ziplistFind(fptr, field->ptr, sdslen(field->ptr), 1);
+ if (fptr != NULL) {
+ /* Grab pointer to the value (fptr points to the field) */
+ vptr = ziplistNext(zl, fptr);
+ redisAssert(vptr != NULL);
+ update = 1;
+
+ /* Delete value */
+ zl = ziplistDelete(zl, &vptr);
+
+ /* Insert new value */
+ zl = ziplistInsert(zl, vptr, value->ptr, sdslen(value->ptr));
+ }
+ }
+
+ if (!update) {
+ /* Push new field/value pair onto the tail of the ziplist */
+ zl = ziplistPush(zl, field->ptr, sdslen(field->ptr), ZIPLIST_TAIL);
+ zl = ziplistPush(zl, value->ptr, sdslen(value->ptr), ZIPLIST_TAIL);
+ }
+
+ o->ptr = zl;
+
+ decrRefCount(field);
decrRefCount(value);
- /* Check if the zipmap needs to be upgraded to a real hash table */
- if (zipmapLen(o->ptr) > server.hash_max_zipmap_entries)
- convertToRealHash(o);
- } else {
- if (dictReplace(o->ptr,key,value)) {
- /* Insert */
- incrRefCount(key);
- } else {
- /* Update */
+ /* Check if the ziplist needs to be converted to a hash table */
+ if (hashTypeLength(o) > server.hash_max_ziplist_entries) {
+ hashTypeConvert(o, REDIS_ENCODING_HT);
+ }
+
+ } else if (o->encoding == REDIS_ENCODING_HT) {
+ if (dictReplace(o->ptr, field, value)) { /* Insert */
+ incrRefCount(field);
+ } else { /* Update */
update = 1;
}
+
incrRefCount(value);
+
+ } else {
+ redisPanic("Unknown hash encoding");
}
+
return update;
}
/* Delete an element from a hash.
* Return 1 on deleted and 0 on not found. */
-int hashTypeDelete(robj *o, robj *key) {
+int hashTypeDelete(robj *o, robj *field) {
int deleted = 0;
- if (o->encoding == REDIS_ENCODING_ZIPMAP) {
- key = getDecodedObject(key);
- o->ptr = zipmapDel(o->ptr,key->ptr,sdslen(key->ptr), &deleted);
- decrRefCount(key);
+
+ if (o->encoding == REDIS_ENCODING_ZIPLIST) {
+ unsigned char *zl, *fptr;
+
+ field = getDecodedObject(field);
+
+ zl = o->ptr;
+ fptr = ziplistIndex(zl, ZIPLIST_HEAD);
+ if (fptr != NULL) {
+ fptr = ziplistFind(fptr, field->ptr, sdslen(field->ptr), 1);
+ if (fptr != NULL) {
+ zl = ziplistDelete(zl,&fptr);
+ zl = ziplistDelete(zl,&fptr);
+ o->ptr = zl;
+ deleted = 1;
+ }
+ }
+
+ decrRefCount(field);
+
+ } else if (o->encoding == REDIS_ENCODING_HT) {
+ if (dictDelete((dict*)o->ptr, field) == REDIS_OK) {
+ deleted = 1;
+
+ /* Always check if the dictionary needs a resize after a delete. */
+ if (htNeedsResize(o->ptr)) dictResize(o->ptr);
+ }
+
} else {
- deleted = dictDelete((dict*)o->ptr,key) == DICT_OK;
- /* Always check if the dictionary needs a resize after a delete. */
- if (deleted && htNeedsResize(o->ptr)) dictResize(o->ptr);
+ redisPanic("Unknown hash encoding");
}
+
return deleted;
}
/* Return the number of elements in a hash. */
unsigned long hashTypeLength(robj *o) {
- return (o->encoding == REDIS_ENCODING_ZIPMAP) ?
- zipmapLen((unsigned char*)o->ptr) : dictSize((dict*)o->ptr);
+ unsigned long length = ULONG_MAX;
+
+ if (o->encoding == REDIS_ENCODING_ZIPLIST) {
+ length = ziplistLen(o->ptr) / 2;
+ } else if (o->encoding == REDIS_ENCODING_HT) {
+ length = dictSize((dict*)o->ptr);
+ } else {
+ redisPanic("Unknown hash encoding");
+ }
+
+ return length;
}
hashTypeIterator *hashTypeInitIterator(robj *subject) {
hashTypeIterator *hi = zmalloc(sizeof(hashTypeIterator));
+ hi->subject = subject;
hi->encoding = subject->encoding;
- if (hi->encoding == REDIS_ENCODING_ZIPMAP) {
- hi->zi = zipmapRewind(subject->ptr);
+
+ if (hi->encoding == REDIS_ENCODING_ZIPLIST) {
+ hi->fptr = NULL;
+ hi->vptr = NULL;
} else if (hi->encoding == REDIS_ENCODING_HT) {
hi->di = dictGetIterator(subject->ptr);
} else {
- redisAssertWithInfo(NULL,subject,0);
+ redisPanic("Unknown hash encoding");
}
+
return hi;
}
if (hi->encoding == REDIS_ENCODING_HT) {
dictReleaseIterator(hi->di);
}
+
zfree(hi);
}
/* Move to the next entry in the hash. Return REDIS_OK when the next entry
* could be found and REDIS_ERR when the iterator reaches the end. */
int hashTypeNext(hashTypeIterator *hi) {
- if (hi->encoding == REDIS_ENCODING_ZIPMAP) {
- if ((hi->zi = zipmapNext(hi->zi, &hi->zk, &hi->zklen,
- &hi->zv, &hi->zvlen)) == NULL) return REDIS_ERR;
+ if (hi->encoding == REDIS_ENCODING_ZIPLIST) {
+ unsigned char *zl;
+ unsigned char *fptr, *vptr;
+
+ zl = hi->subject->ptr;
+ fptr = hi->fptr;
+ vptr = hi->vptr;
+
+ if (fptr == NULL) {
+ /* Initialize cursor */
+ redisAssert(vptr == NULL);
+ fptr = ziplistIndex(zl, 0);
+ } else {
+ /* Advance cursor */
+ redisAssert(vptr != NULL);
+ fptr = ziplistNext(zl, vptr);
+ }
+
+ if (fptr == NULL) {
+ return REDIS_ERR;
+ }
+
+ /* Grab pointer to the value (fptr points to the field) */
+ vptr = ziplistNext(zl, fptr);
+ redisAssert(vptr != NULL);
+
+ /* fptr, vptr now point to the first or next pair */
+ hi->fptr = fptr;
+ hi->vptr = vptr;
+
+ } else if (hi->encoding == REDIS_ENCODING_HT) {
+ if ((hi->de = dictNext(hi->di)) == NULL) {
+ return REDIS_ERR;
+ }
+
} else {
- if ((hi->de = dictNext(hi->di)) == NULL) return REDIS_ERR;
+ redisPanic("Unknown hash encoding");
}
+
return REDIS_OK;
}
-/* Get key or value object at current iteration position.
- * The returned item differs with the hash object encoding:
- * - When encoding is REDIS_ENCODING_HT, the objval pointer is populated
- * with the original object.
- * - When encoding is REDIS_ENCODING_ZIPMAP, a pointer to the string and
- * its length is retunred populating the v and vlen pointers.
- * This function is copy on write friendly as accessing objects in read only
- * does not require writing to any memory page.
- *
- * The function returns the encoding of the object, so that the caller
- * can underestand if the key or value was returned as object or C string. */
-int hashTypeCurrent(hashTypeIterator *hi, int what, robj **objval, unsigned char **v, unsigned int *vlen) {
- if (hi->encoding == REDIS_ENCODING_ZIPMAP) {
- if (what & REDIS_HASH_KEY) {
- *v = hi->zk;
- *vlen = hi->zklen;
- } else {
- *v = hi->zv;
- *vlen = hi->zvlen;
- }
+/* Get the field or value at iterator cursor, for an iterator on a hash value
+ * encoded as a ziplist. Prototype is similar to `hashTypeGetFromZiplist`. */
+void hashTypeCurrentFromZiplist(hashTypeIterator *hi, int what,
+ unsigned char **vstr,
+ unsigned int *vlen,
+ long long *vll)
+{
+ int ret;
+
+ redisAssert(hi->encoding == REDIS_ENCODING_ZIPLIST);
+
+ if (what & REDIS_HASH_KEY) {
+ ret = ziplistGet(hi->fptr, vstr, vlen, vll);
+ redisAssert(ret);
+ } else {
+ ret = ziplistGet(hi->vptr, vstr, vlen, vll);
+ redisAssert(ret);
+ }
+}
+
+/* Get the field or value at iterator cursor, for an iterator on a hash value
+ * encoded as a ziplist. Prototype is similar to `hashTypeGetFromHashTable`. */
+void hashTypeCurrentFromHashTable(hashTypeIterator *hi, int what, robj **dst) {
+ redisAssert(hi->encoding == REDIS_ENCODING_HT);
+
+ if (what & REDIS_HASH_KEY) {
+ *dst = dictGetKey(hi->de);
} else {
- if (what & REDIS_HASH_KEY)
- *objval = dictGetKey(hi->de);
- else
- *objval = dictGetVal(hi->de);
+ *dst = dictGetVal(hi->de);
}
- return hi->encoding;
}
-/* A non copy-on-write friendly but higher level version of hashTypeCurrent()
- * that always returns an object with refcount incremented by one (or a new
- * object), so it's up to the caller to decrRefCount() the object if no
- * reference is retained. */
+/* A non copy-on-write friendly but higher level version of hashTypeCurrent*()
+ * that returns an object with incremented refcount (or a new object). It is up
+ * to the caller to decrRefCount() the object if no reference is retained. */
robj *hashTypeCurrentObject(hashTypeIterator *hi, int what) {
- robj *obj;
- unsigned char *v = NULL;
- unsigned int vlen = 0;
- int encoding = hashTypeCurrent(hi,what,&obj,&v,&vlen);
-
- if (encoding == REDIS_ENCODING_HT) {
- incrRefCount(obj);
- return obj;
+ robj *dst;
+
+ if (hi->encoding == REDIS_ENCODING_ZIPLIST) {
+ unsigned char *vstr = NULL;
+ unsigned int vlen = UINT_MAX;
+ long long vll = LLONG_MAX;
+
+ hashTypeCurrentFromZiplist(hi, what, &vstr, &vlen, &vll);
+ if (vstr) {
+ dst = createStringObject((char*)vstr, vlen);
+ } else {
+ dst = createStringObjectFromLongLong(vll);
+ }
+
+ } else if (hi->encoding == REDIS_ENCODING_HT) {
+ hashTypeCurrentFromHashTable(hi, what, &dst);
+ incrRefCount(dst);
+
} else {
- return createStringObject((char*)v,vlen);
+ redisPanic("Unknown hash encoding");
}
+
+ return dst;
}
robj *hashTypeLookupWriteOrCreate(redisClient *c, robj *key) {
return o;
}
-void convertToRealHash(robj *o) {
- unsigned char *key, *val, *p, *zm = o->ptr;
- unsigned int klen, vlen;
- dict *dict = dictCreate(&hashDictType,NULL);
+void hashTypeConvertZiplist(robj *o, int enc) {
+ redisAssert(o->encoding == REDIS_ENCODING_ZIPLIST);
+
+ if (enc == REDIS_ENCODING_ZIPLIST) {
+ /* Nothing to do... */
+
+ } else if (enc == REDIS_ENCODING_HT) {
+ hashTypeIterator *hi;
+ dict *dict;
+ int ret;
- redisAssertWithInfo(NULL,o,o->type == REDIS_HASH && o->encoding != REDIS_ENCODING_HT);
- p = zipmapRewind(zm);
- while((p = zipmapNext(p,&key,&klen,&val,&vlen)) != NULL) {
- robj *keyobj, *valobj;
+ hi = hashTypeInitIterator(o);
+ dict = dictCreate(&hashDictType, NULL);
- keyobj = createStringObject((char*)key,klen);
- valobj = createStringObject((char*)val,vlen);
- keyobj = tryObjectEncoding(keyobj);
- valobj = tryObjectEncoding(valobj);
- dictAdd(dict,keyobj,valobj);
+ while (hashTypeNext(hi) != REDIS_ERR) {
+ robj *field, *value;
+
+ field = hashTypeCurrentObject(hi, REDIS_HASH_KEY);
+ field = tryObjectEncoding(field);
+ value = hashTypeCurrentObject(hi, REDIS_HASH_VALUE);
+ value = tryObjectEncoding(value);
+ ret = dictAdd(dict, field, value);
+ redisAssert(ret == DICT_OK);
+ }
+
+ hashTypeReleaseIterator(hi);
+ zfree(o->ptr);
+
+ o->encoding = REDIS_ENCODING_HT;
+ o->ptr = dict;
+
+ } else {
+ redisPanic("Unknown hash encoding");
+ }
+}
+
+void hashTypeConvert(robj *o, int enc) {
+ if (o->encoding == REDIS_ENCODING_ZIPLIST) {
+ hashTypeConvertZiplist(o, enc);
+ } else if (o->encoding == REDIS_ENCODING_HT) {
+ redisPanic("Not implemented");
+ } else {
+ redisPanic("Unknown hash encoding");
}
- o->encoding = REDIS_ENCODING_HT;
- o->ptr = dict;
- zfree(zm);
}
/*-----------------------------------------------------------------------------
server.dirty++;
}
+static void addHashFieldToReply(redisClient *c, robj *o, robj *field) {
+ int ret;
+
+ if (o == NULL) {
+ addReply(c, shared.nullbulk);
+ return;
+ }
+
+ if (o->encoding == REDIS_ENCODING_ZIPLIST) {
+ unsigned char *vstr = NULL;
+ unsigned int vlen = UINT_MAX;
+ long long vll = LLONG_MAX;
+
+ ret = hashTypeGetFromZiplist(o, field, &vstr, &vlen, &vll);
+ if (ret < 0) {
+ addReply(c, shared.nullbulk);
+ } else {
+ if (vstr) {
+ addReplyBulkCBuffer(c, vstr, vlen);
+ } else {
+ addReplyBulkLongLong(c, vll);
+ }
+ }
+
+ } else if (o->encoding == REDIS_ENCODING_HT) {
+ robj *value;
+
+ ret = hashTypeGetFromHashTable(o, field, &value);
+ if (ret < 0) {
+ addReply(c, shared.nullbulk);
+ } else {
+ addReplyBulk(c, value);
+ }
+
+ } else {
+ redisPanic("Unknown hash encoding");
+ }
+}
+
void hgetCommand(redisClient *c) {
- robj *o, *value;
- unsigned char *v;
- unsigned int vlen;
- int encoding;
+ robj *o;
if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.nullbulk)) == NULL ||
checkType(c,o,REDIS_HASH)) return;
- if ((encoding = hashTypeGet(o,c->argv[2],&value,&v,&vlen)) != -1) {
- if (encoding == REDIS_ENCODING_HT)
- addReplyBulk(c,value);
- else
- addReplyBulkCBuffer(c,v,vlen);
- } else {
- addReply(c,shared.nullbulk);
- }
+ addHashFieldToReply(c, o, c->argv[2]);
}
void hmgetCommand(redisClient *c) {
- int i, encoding;
- robj *o, *value;
- unsigned char *v;
- unsigned int vlen;
+ robj *o;
+ int i;
- o = lookupKeyRead(c->db,c->argv[1]);
+ /* Don't abort when the key cannot be found. Non-existing keys are empty
+ * hashes, where HMGET should respond with a series of null bulks. */
+ o = lookupKeyRead(c->db, c->argv[1]);
if (o != NULL && o->type != REDIS_HASH) {
- addReply(c,shared.wrongtypeerr);
+ addReply(c, shared.wrongtypeerr);
return;
}
- /* Note the check for o != NULL happens inside the loop. This is
- * done because objects that cannot be found are considered to be
- * an empty hash. The reply should then be a series of NULLs. */
- addReplyMultiBulkLen(c,c->argc-2);
+ addReplyMultiBulkLen(c, c->argc-2);
for (i = 2; i < c->argc; i++) {
- if (o != NULL &&
- (encoding = hashTypeGet(o,c->argv[i],&value,&v,&vlen)) != -1) {
- if (encoding == REDIS_ENCODING_HT)
- addReplyBulk(c,value);
- else
- addReplyBulkCBuffer(c,v,vlen);
- } else {
- addReply(c,shared.nullbulk);
- }
+ addHashFieldToReply(c, o, c->argv[i]);
}
}
addReplyLongLong(c,hashTypeLength(o));
}
+static void addHashIteratorCursorToReply(redisClient *c, hashTypeIterator *hi, int what) {
+ if (hi->encoding == REDIS_ENCODING_ZIPLIST) {
+ unsigned char *vstr = NULL;
+ unsigned int vlen = UINT_MAX;
+ long long vll = LLONG_MAX;
+
+ hashTypeCurrentFromZiplist(hi, what, &vstr, &vlen, &vll);
+ if (vstr) {
+ addReplyBulkCBuffer(c, vstr, vlen);
+ } else {
+ addReplyBulkLongLong(c, vll);
+ }
+
+ } else if (hi->encoding == REDIS_ENCODING_HT) {
+ robj *value;
+
+ hashTypeCurrentFromHashTable(hi, what, &value);
+ addReplyBulk(c, value);
+
+ } else {
+ redisPanic("Unknown hash encoding");
+ }
+}
+
void genericHgetallCommand(redisClient *c, int flags) {
robj *o;
- unsigned long count = 0;
hashTypeIterator *hi;
- void *replylen = NULL;
+ int multiplier = 0;
+ int length, count = 0;
if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.emptymultibulk)) == NULL
|| checkType(c,o,REDIS_HASH)) return;
- replylen = addDeferredMultiBulkLength(c);
+ if (flags & REDIS_HASH_KEY) multiplier++;
+ if (flags & REDIS_HASH_VALUE) multiplier++;
+
+ length = hashTypeLength(o) * multiplier;
+ addReplyMultiBulkLen(c, length);
+
hi = hashTypeInitIterator(o);
while (hashTypeNext(hi) != REDIS_ERR) {
- robj *obj;
- unsigned char *v = NULL;
- unsigned int vlen = 0;
- int encoding;
-
if (flags & REDIS_HASH_KEY) {
- encoding = hashTypeCurrent(hi,REDIS_HASH_KEY,&obj,&v,&vlen);
- if (encoding == REDIS_ENCODING_HT)
- addReplyBulk(c,obj);
- else
- addReplyBulkCBuffer(c,v,vlen);
+ addHashIteratorCursorToReply(c, hi, REDIS_HASH_KEY);
count++;
}
if (flags & REDIS_HASH_VALUE) {
- encoding = hashTypeCurrent(hi,REDIS_HASH_VALUE,&obj,&v,&vlen);
- if (encoding == REDIS_ENCODING_HT)
- addReplyBulk(c,obj);
- else
- addReplyBulkCBuffer(c,v,vlen);
+ addHashIteratorCursorToReply(c, hi, REDIS_HASH_VALUE);
count++;
}
}
+
hashTypeReleaseIterator(hi);
- setDeferredMultiBulkLength(c,replylen,count);
+ redisAssert(count == length);
}
void hkeysCommand(redisClient *c) {
/* Convert a string into a long long. Returns 1 if the string could be parsed
* into a (non-overflowing) long long, 0 otherwise. The value will be set to
* the parsed value when appropriate. */
-int string2ll(char *s, size_t slen, long long *value) {
- char *p = s;
+int string2ll(const char *s, size_t slen, long long *value) {
+ const char *p = s;
size_t plen = 0;
int negative = 0;
unsigned long long v;
/* Convert a string into a long. Returns 1 if the string could be parsed into a
* (non-overflowing) long, 0 otherwise. The value will be set to the parsed
* value when appropriate. */
-int string2l(char *s, size_t slen, long *lval) {
+int string2l(const char *s, size_t slen, long *lval) {
long long llval;
if (!string2ll(s,slen,&llval))
int stringmatch(const char *p, const char *s, int nocase);
long long memtoll(const char *p, int *err);
int ll2string(char *s, size_t len, long long value);
-int string2ll(char *s, size_t slen, long long *value);
-int string2l(char *s, size_t slen, long *value);
+int string2ll(const char *s, size_t slen, long long *value);
+int string2l(const char *s, size_t slen, long *value);
int d2string(char *buf, size_t len, double value);
#endif
#define ZIP_BIGLEN 254
/* Different encoding/length possibilities */
+#define ZIP_STR_MASK (0xc0)
+#define ZIP_INT_MASK (0x30)
#define ZIP_STR_06B (0 << 6)
#define ZIP_STR_14B (1 << 6)
#define ZIP_STR_32B (2 << 6)
#define ZIP_INT_32B (0xc0 | 1<<4)
#define ZIP_INT_64B (0xc0 | 2<<4)
-/* Macro's to determine type */
-#define ZIP_IS_STR(enc) (((enc) & 0xc0) < 0xc0)
-#define ZIP_IS_INT(enc) (!ZIP_IS_STR(enc) && ((enc) & 0x30) < 0x30)
+/* Macro to determine type */
+#define ZIP_IS_STR(enc) (((enc) & ZIP_STR_MASK) < ZIP_STR_MASK)
/* Utility macros */
#define ZIPLIST_BYTES(zl) (*((uint32_t*)(zl)))
unsigned char *p;
} zlentry;
-/* Return the encoding pointer to by 'p'. */
-static unsigned int zipEntryEncoding(unsigned char *p) {
- /* String encoding: 2 MSBs */
- unsigned char b = p[0] & 0xc0;
- if (b < 0xc0) {
- return b;
- } else {
- /* Integer encoding: 4 MSBs */
- return p[0] & 0xf0;
- }
- assert(NULL);
- return 0;
-}
+#define ZIP_ENTRY_ENCODING(ptr, encoding) do { \
+ (encoding) = (ptr[0]) & (ZIP_STR_MASK | ZIP_INT_MASK); \
+ if (((encoding) & ZIP_STR_MASK) < ZIP_STR_MASK) { \
+ /* String encoding: 2 MSBs */ \
+ (encoding) &= ZIP_STR_MASK; \
+ } \
+} while(0)
/* Return bytes needed to store integer encoded by 'encoding' */
static unsigned int zipIntSize(unsigned char encoding) {
return 0;
}
-/* Decode the encoded length pointed by 'p'. If a pointer to 'lensize' is
- * provided, it is set to the number of bytes required to encode the length. */
-static unsigned int zipDecodeLength(unsigned char *p, unsigned int *lensize) {
- unsigned char encoding = zipEntryEncoding(p);
- unsigned int len = 0;
-
- if (ZIP_IS_STR(encoding)) {
- switch(encoding) {
- case ZIP_STR_06B:
- len = p[0] & 0x3f;
- if (lensize) *lensize = 1;
- break;
- case ZIP_STR_14B:
- len = ((p[0] & 0x3f) << 8) | p[1];
- if (lensize) *lensize = 2;
- break;
- case ZIP_STR_32B:
- len = (p[1] << 24) | (p[2] << 16) | (p[3] << 8) | p[4];
- if (lensize) *lensize = 5;
- break;
- default:
- assert(NULL);
- }
- } else {
- len = zipIntSize(encoding);
- if (lensize) *lensize = 1;
- }
- return len;
-}
-
/* Encode the length 'l' writing it in 'p'. If p is NULL it just returns
* the amount of bytes required to encode such a length. */
static unsigned int zipEncodeLength(unsigned char *p, unsigned char encoding, unsigned int rawlen) {
return len;
}
-/* Decode the length of the previous element stored at "p". */
-static unsigned int zipPrevDecodeLength(unsigned char *p, unsigned int *lensize) {
- unsigned int len = *p;
- if (len < ZIP_BIGLEN) {
- if (lensize) *lensize = 1;
- } else {
- if (lensize) *lensize = 1+sizeof(len);
- memcpy(&len,p+1,sizeof(len));
- memrev32ifbe(&len);
- }
- return len;
-}
+/* Decode the length encoded in 'ptr'. The 'encoding' variable will hold the
+ * entries encoding, the 'lensize' variable will hold the number of bytes
+ * required to encode the entries length, and the 'len' variable will hold the
+ * entries length. */
+#define ZIP_DECODE_LENGTH(ptr, encoding, lensize, len) do { \
+ ZIP_ENTRY_ENCODING((ptr), (encoding)); \
+ if ((encoding) < ZIP_STR_MASK) { \
+ if ((encoding) == ZIP_STR_06B) { \
+ (lensize) = 1; \
+ (len) = (ptr)[0] & 0x3f; \
+ } else if ((encoding) == ZIP_STR_14B) { \
+ (lensize) = 2; \
+ (len) = (((ptr)[0] & 0x3f) << 8) | (ptr)[1]; \
+ } else if (encoding == ZIP_STR_32B) { \
+ (lensize) = 5; \
+ (len) = ((ptr)[1] << 24) | \
+ ((ptr)[2] << 16) | \
+ ((ptr)[3] << 8) | \
+ ((ptr)[4]); \
+ } else { \
+ assert(NULL); \
+ } \
+ } else { \
+ (lensize) = 1; \
+ (len) = zipIntSize(encoding); \
+ } \
+} while(0);
/* Encode the length of the previous entry and write it to "p". Return the
* number of bytes needed to encode this length if "p" is NULL. */
memrev32ifbe(p+1);
}
-/* Return the difference in number of bytes needed to store the new length
- * "len" on the entry pointed to by "p". */
+/* Decode the number of bytes required to store the length of the previous
+ * element, from the perspective of the entry pointed to by 'ptr'. */
+#define ZIP_DECODE_PREVLENSIZE(ptr, prevlensize) do { \
+ if ((ptr)[0] < ZIP_BIGLEN) { \
+ (prevlensize) = 1; \
+ } else { \
+ (prevlensize) = 5; \
+ } \
+} while(0);
+
+/* Decode the length of the previous element, from the perspective of the entry
+ * pointed to by 'ptr'. */
+#define ZIP_DECODE_PREVLEN(ptr, prevlensize, prevlen) do { \
+ ZIP_DECODE_PREVLENSIZE(ptr, prevlensize); \
+ if ((prevlensize) == 1) { \
+ (prevlen) = (ptr)[0]; \
+ } else if ((prevlensize) == 5) { \
+ assert(sizeof((prevlensize)) == 4); \
+ memcpy(&(prevlen), ((char*)(ptr)) + 1, 4); \
+ memrev32ifbe(&len); \
+ } \
+} while(0);
+
+/* Return the difference in number of bytes needed to store the length of the
+ * previous element 'len', in the entry pointed to by 'p'. */
static int zipPrevLenByteDiff(unsigned char *p, unsigned int len) {
unsigned int prevlensize;
- zipPrevDecodeLength(p,&prevlensize);
- return zipPrevEncodeLength(NULL,len)-prevlensize;
+ ZIP_DECODE_PREVLENSIZE(p, prevlensize);
+ return zipPrevEncodeLength(NULL, len) - prevlensize;
+}
+
+/* Return the total number of bytes used by the entry pointed to by 'p'. */
+static unsigned int zipRawEntryLength(unsigned char *p) {
+ unsigned int prevlensize, encoding, lensize, len;
+ ZIP_DECODE_PREVLENSIZE(p, prevlensize);
+ ZIP_DECODE_LENGTH(p + prevlensize, encoding, lensize, len);
+ return prevlensize + lensize + len;
}
/* Check if string pointed to by 'entry' can be encoded as an integer.
/* Return a struct with all information about an entry. */
static zlentry zipEntry(unsigned char *p) {
zlentry e;
- e.prevrawlen = zipPrevDecodeLength(p,&e.prevrawlensize);
- e.len = zipDecodeLength(p+e.prevrawlensize,&e.lensize);
- e.headersize = e.prevrawlensize+e.lensize;
- e.encoding = zipEntryEncoding(p+e.prevrawlensize);
+
+ ZIP_DECODE_PREVLEN(p, e.prevrawlensize, e.prevrawlen);
+ ZIP_DECODE_LENGTH(p + e.prevrawlensize, e.encoding, e.lensize, e.len);
+ e.headersize = e.prevrawlensize + e.lensize;
e.p = p;
return e;
}
-/* Return the total number of bytes used by the entry at "p". */
-static unsigned int zipRawEntryLength(unsigned char *p) {
- zlentry e = zipEntry(p);
- return e.headersize + e.len;
-}
-
/* Create a new empty ziplist. */
unsigned char *ziplistNew(void) {
unsigned int bytes = ZIPLIST_HEADER_SIZE+1;
* when the *next* element is ZIP_END (there is no next entry). */
if (p[0] == ZIP_END) {
return NULL;
- } else {
- p = p+zipRawEntryLength(p);
- return (p[0] == ZIP_END) ? NULL : p;
}
+
+ p += zipRawEntryLength(p);
+ if (p[0] == ZIP_END) {
+ return NULL;
+ }
+
+ return p;
}
/* Return pointer to previous entry in ziplist. */
return 0;
}
+/* 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 *ziplistFind(unsigned char *p, unsigned char *vstr, unsigned int vlen, unsigned int skip) {
+ int skipcnt = 0;
+ unsigned char vencoding = 0;
+ long long vll = 0;
+
+ while (p[0] != ZIP_END) {
+ unsigned int prevlensize, encoding, lensize, len;
+ unsigned char *q;
+
+ ZIP_DECODE_PREVLENSIZE(p, prevlensize);
+ ZIP_DECODE_LENGTH(p + prevlensize, encoding, lensize, len);
+ q = p + prevlensize + lensize;
+
+ if (skipcnt == 0) {
+ /* Compare current entry with specified entry */
+ if (ZIP_IS_STR(encoding)) {
+ if (len == vlen && memcmp(q, vstr, vlen) == 0) {
+ return p;
+ }
+ } else {
+ /* Find out if the specified entry can be encoded */
+ if (vencoding == 0) {
+ /* UINT_MAX when the entry CANNOT be encoded */
+ if (!zipTryEncoding(vstr, vlen, &vll, &vencoding)) {
+ vencoding = UCHAR_MAX;
+ }
+
+ /* Must be non-zero by now */
+ assert(vencoding);
+ }
+
+ /* Compare current entry with specified entry */
+ if (encoding == vencoding) {
+ long long ll = zipLoadInteger(q, encoding);
+ if (ll == vll) {
+ return p;
+ }
+ }
+ }
+
+ /* Reset skip count */
+ skipcnt = skip;
+ } else {
+ /* Skip entry */
+ skipcnt--;
+ }
+
+ /* Move to next entry */
+ p = q + len;
+ }
+
+ return NULL;
+}
+
/* Return length of ziplist. */
unsigned int ziplistLen(unsigned char *zl) {
unsigned int len = 0;
unsigned char *ziplistDelete(unsigned char *zl, unsigned char **p);
unsigned char *ziplistDeleteRange(unsigned char *zl, unsigned int index, unsigned int num);
unsigned int ziplistCompare(unsigned char *p, unsigned char *s, unsigned int slen);
+unsigned char *ziplistFind(unsigned char *p, unsigned char *vstr, unsigned int vlen, unsigned int skip);
unsigned int ziplistLen(unsigned char *zl);
size_t ziplistBlobLen(unsigned char *zl);
--- /dev/null
+set server_path [tmpdir "server.convert-zipmap-hash-on-load"]
+
+# Copy RDB with zipmap encoded hash to server path
+exec cp tests/assets/hash-zipmap.rdb $server_path
+
+start_server [list overrides [list "dir" $server_path "dbfilename" "hash-zipmap.rdb"]] {
+ test "RDB load zipmap hash: converts to ziplist" {
+ r select 0
+
+ assert_match "*ziplist*" [r debug object hash]
+ assert_equal 2 [r hlen hash]
+ assert_match {v1 v2} [r hmget hash f1 f2]
+ }
+}
+
+start_server [list overrides [list "dir" $server_path "dbfilename" "hash-zipmap.rdb" "hash-max-ziplist-entries" 1]] {
+ test "RDB load zipmap hash: converts to hash table when hash-max-ziplist-entries is exceeded" {
+ r select 0
+
+ assert_match "*hashtable*" [r debug object hash]
+ assert_equal 2 [r hlen hash]
+ assert_match {v1 v2} [r hmget hash f1 f2]
+ }
+}
+
+start_server [list overrides [list "dir" $server_path "dbfilename" "hash-zipmap.rdb" "hash-max-ziplist-value" 1]] {
+ test "RDB load zipmap hash: converts to hash table when hash-max-ziplist-value is exceeded" {
+ r select 0
+
+ assert_match "*hashtable*" [r debug object hash]
+ assert_equal 2 [r hlen hash]
+ assert_match {v1 v2} [r hmget hash f1 f2]
+ }
+}
}
foreach d {string int} {
- foreach e {zipmap hashtable} {
+ foreach e {ziplist hashtable} {
test "AOF rewrite of hash with $e encoding, $d data" {
r flushall
- if {$e eq {zipmap}} {set len 10} else {set len 1000}
+ if {$e eq {ziplist}} {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]
list [r hlen smallhash]
} {8}
- test {Is the small hash encoded with a zipmap?} {
- assert_encoding zipmap smallhash
+ test {Is the small hash encoded with a ziplist?} {
+ assert_encoding ziplist smallhash
}
test {HSET/HLEN - Big hash creation} {
list [r hlen bighash]
} {1024}
- test {Is the big hash encoded with a zipmap?} {
+ test {Is the big hash encoded with a ziplist?} {
assert_encoding hashtable bighash
}
lappend rv [r hexists bighash nokey]
} {1 0 1 0}
- test {Is a zipmap encoded Hash promoted on big payload?} {
+ test {Is a ziplist encoded Hash promoted on big payload?} {
r hset smallhash foo [string repeat a 1024]
r debug object smallhash
} {*hashtable*}
lappend rv [string match "ERR*not*float*" $bigerr]
} {1 1}
- test {Hash zipmap regression test for large keys} {
+ test {Hash ziplist regression test for large keys} {
r hset hash kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk a
r hset hash kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk b
r hget hash kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk
projects / redis.git / commitdiff
