src/t_hash.c

   1 #include "redis.h"
   2
   3 #include <math.h>
   4
   5 /*-----------------------------------------------------------------------------
   6  * Hash type API
   7  *----------------------------------------------------------------------------*/
   8
   9 /* Check the length of a number of objects to see if we need to convert a
  10  * zipmap to a real hash. Note that we only check string encoded objects
  11  * as their string length can be queried in constant time. */
  12 void hashTypeTryConversion(robj *subject, robj **argv, int start, int end) {
  13     int i;
  14     if (subject->encoding != REDIS_ENCODING_ZIPMAP) return;
  15
  16     for (i = start; i <= end; i++) {
  17         if (argv[i]->encoding == REDIS_ENCODING_RAW &&
  18             sdslen(argv[i]->ptr) > server.hash_max_zipmap_value)
  19         {
  20             convertToRealHash(subject);
  21             return;
  22         }
  23     }
  24 }
  25
  26 /* Encode given objects in-place when the hash uses a dict. */
  27 void hashTypeTryObjectEncoding(robj *subject, robj **o1, robj **o2) {
  28     if (subject->encoding == REDIS_ENCODING_HT) {
  29         if (o1) *o1 = tryObjectEncoding(*o1);
  30         if (o2) *o2 = tryObjectEncoding(*o2);
  31     }
  32 }
  33
  34 /* Get the value from a hash identified by key.
  35  *
  36  * If the string is found either REDIS_ENCODING_HT or REDIS_ENCODING_ZIPMAP
  37  * is returned, and either **objval or **v and *vlen are set accordingly,
  38  * so that objects in hash tables are returend as objects and pointers
  39  * inside a zipmap are returned as such.
  40  *
  41  * If the object was not found -1 is returned.
  42  *
  43  * This function is copy on write friendly as there is no incr/decr
  44  * of refcount needed if objects are accessed just for reading operations. */
  45 int hashTypeGet(robj *o, robj *key, robj **objval, unsigned char **v,
  46                 unsigned int *vlen)
  47 {
  48     if (o->encoding == REDIS_ENCODING_ZIPMAP) {
  49         int found;
  50
  51         key = getDecodedObject(key);
  52         found = zipmapGet(o->ptr,key->ptr,sdslen(key->ptr),v,vlen);
  53         decrRefCount(key);
  54         if (!found) return -1;
  55     } else {
  56         dictEntry *de = dictFind(o->ptr,key);
  57         if (de == NULL) return -1;
  58         *objval = dictGetEntryVal(de);
  59     }
  60     return o->encoding;
  61 }
  62
  63 /* Higher level function of hashTypeGet() that always returns a Redis
  64  * object (either new or with refcount incremented), so that the caller
  65  * can retain a reference or call decrRefCount after the usage.
  66  *
  67  * The lower level function can prevent copy on write so it is
  68  * the preferred way of doing read operations. */
  69 robj *hashTypeGetObject(robj *o, robj *key) {
  70     robj *objval;
  71     unsigned char *v;
  72     unsigned int vlen;
  73
  74     int encoding = hashTypeGet(o,key,&objval,&v,&vlen);
  75     switch(encoding) {
  76         case REDIS_ENCODING_HT:
  77             incrRefCount(objval);
  78             return objval;
  79         case REDIS_ENCODING_ZIPMAP:
  80             objval = createStringObject((char*)v,vlen);
  81             return objval;
  82         default: return NULL;
  83     }
  84 }
  85
  86 /* Test if the key exists in the given hash. Returns 1 if the key
  87  * exists and 0 when it doesn't. */
  88 int hashTypeExists(robj *o, robj *key) {
  89     if (o->encoding == REDIS_ENCODING_ZIPMAP) {
  90         key = getDecodedObject(key);
  91         if (zipmapExists(o->ptr,key->ptr,sdslen(key->ptr))) {
  92             decrRefCount(key);
  93             return 1;
  94         }
  95         decrRefCount(key);
  96     } else {
  97         if (dictFind(o->ptr,key) != NULL) {
  98             return 1;
  99         }
 100     }
 101     return 0;
 102 }
 103
 104 /* Add an element, discard the old if the key already exists.
 105  * Return 0 on insert and 1 on update. */
 106 int hashTypeSet(robj *o, robj *key, robj *value) {
 107     int update = 0;
 108     if (o->encoding == REDIS_ENCODING_ZIPMAP) {
 109         key = getDecodedObject(key);
 110         value = getDecodedObject(value);
 111         o->ptr = zipmapSet(o->ptr,
 112             key->ptr,sdslen(key->ptr),
 113             value->ptr,sdslen(value->ptr), &update);
 114         decrRefCount(key);
 115         decrRefCount(value);
 116
 117         /* Check if the zipmap needs to be upgraded to a real hash table */
 118         if (zipmapLen(o->ptr) > server.hash_max_zipmap_entries)
 119             convertToRealHash(o);
 120     } else {
 121         if (dictReplace(o->ptr,key,value)) {
 122             /* Insert */
 123             incrRefCount(key);
 124         } else {
 125             /* Update */
 126             update = 1;
 127         }
 128         incrRefCount(value);
 129     }
 130     return update;
 131 }
 132
 133 /* Delete an element from a hash.
 134  * Return 1 on deleted and 0 on not found. */
 135 int hashTypeDelete(robj *o, robj *key) {
 136     int deleted = 0;
 137     if (o->encoding == REDIS_ENCODING_ZIPMAP) {
 138         key = getDecodedObject(key);
 139         o->ptr = zipmapDel(o->ptr,key->ptr,sdslen(key->ptr), &deleted);
 140         decrRefCount(key);
 141     } else {
 142         deleted = dictDelete((dict*)o->ptr,key) == DICT_OK;
 143         /* Always check if the dictionary needs a resize after a delete. */
 144         if (deleted && htNeedsResize(o->ptr)) dictResize(o->ptr);
 145     }
 146     return deleted;
 147 }
 148
 149 /* Return the number of elements in a hash. */
 150 unsigned long hashTypeLength(robj *o) {
 151     return (o->encoding == REDIS_ENCODING_ZIPMAP) ?
 152         zipmapLen((unsigned char*)o->ptr) : dictSize((dict*)o->ptr);
 153 }
 154
 155 hashTypeIterator *hashTypeInitIterator(robj *subject) {
 156     hashTypeIterator *hi = zmalloc(sizeof(hashTypeIterator));
 157     hi->encoding = subject->encoding;
 158     if (hi->encoding == REDIS_ENCODING_ZIPMAP) {
 159         hi->zi = zipmapRewind(subject->ptr);
 160     } else if (hi->encoding == REDIS_ENCODING_HT) {
 161         hi->di = dictGetIterator(subject->ptr);
 162     } else {
 163         redisAssertWithInfo(NULL,subject,0);
 164     }
 165     return hi;
 166 }
 167
 168 void hashTypeReleaseIterator(hashTypeIterator *hi) {
 169     if (hi->encoding == REDIS_ENCODING_HT) {
 170         dictReleaseIterator(hi->di);
 171     }
 172     zfree(hi);
 173 }
 174
 175 /* Move to the next entry in the hash. Return REDIS_OK when the next entry
 176  * could be found and REDIS_ERR when the iterator reaches the end. */
 177 int hashTypeNext(hashTypeIterator *hi) {
 178     if (hi->encoding == REDIS_ENCODING_ZIPMAP) {
 179         if ((hi->zi = zipmapNext(hi->zi, &hi->zk, &hi->zklen,
 180             &hi->zv, &hi->zvlen)) == NULL) return REDIS_ERR;
 181     } else {
 182         if ((hi->de = dictNext(hi->di)) == NULL) return REDIS_ERR;
 183     }
 184     return REDIS_OK;
 185 }
 186
 187 /* Get key or value object at current iteration position.
 188  * The returned item differs with the hash object encoding:
 189  * - When encoding is REDIS_ENCODING_HT, the objval pointer is populated
 190  *   with the original object.
 191  * - When encoding is REDIS_ENCODING_ZIPMAP, a pointer to the string and
 192  *   its length is retunred populating the v and vlen pointers.
 193  * This function is copy on write friendly as accessing objects in read only
 194  * does not require writing to any memory page.
 195  *
 196  * The function returns the encoding of the object, so that the caller
 197  * can underestand if the key or value was returned as object or C string. */
 198 int hashTypeCurrent(hashTypeIterator *hi, int what, robj **objval, unsigned char **v, unsigned int *vlen) {
 199     if (hi->encoding == REDIS_ENCODING_ZIPMAP) {
 200         if (what & REDIS_HASH_KEY) {
 201             *v = hi->zk;
 202             *vlen = hi->zklen;
 203         } else {
 204             *v = hi->zv;
 205             *vlen = hi->zvlen;
 206         }
 207     } else {
 208         if (what & REDIS_HASH_KEY)
 209             *objval = dictGetEntryKey(hi->de);
 210         else
 211             *objval = dictGetEntryVal(hi->de);
 212     }
 213     return hi->encoding;
 214 }
 215
 216 /* A non copy-on-write friendly but higher level version of hashTypeCurrent()
 217  * that always returns an object with refcount incremented by one (or a new
 218  * object), so it's up to the caller to decrRefCount() the object if no
 219  * reference is retained. */
 220 robj *hashTypeCurrentObject(hashTypeIterator *hi, int what) {
 221     robj *obj;
 222     unsigned char *v = NULL;
 223     unsigned int vlen = 0;
 224     int encoding = hashTypeCurrent(hi,what,&obj,&v,&vlen);
 225
 226     if (encoding == REDIS_ENCODING_HT) {
 227         incrRefCount(obj);
 228         return obj;
 229     } else {
 230         return createStringObject((char*)v,vlen);
 231     }
 232 }
 233
 234 robj *hashTypeLookupWriteOrCreate(redisClient *c, robj *key) {
 235     robj *o = lookupKeyWrite(c->db,key);
 236     if (o == NULL) {
 237         o = createHashObject();
 238         dbAdd(c->db,key,o);
 239     } else {
 240         if (o->type != REDIS_HASH) {
 241             addReply(c,shared.wrongtypeerr);
 242             return NULL;
 243         }
 244     }
 245     return o;
 246 }
 247
 248 void convertToRealHash(robj *o) {
 249     unsigned char *key, *val, *p, *zm = o->ptr;
 250     unsigned int klen, vlen;
 251     dict *dict = dictCreate(&hashDictType,NULL);
 252
 253     redisAssertWithInfo(NULL,o,o->type == REDIS_HASH && o->encoding != REDIS_ENCODING_HT);
 254     p = zipmapRewind(zm);
 255     while((p = zipmapNext(p,&key,&klen,&val,&vlen)) != NULL) {
 256         robj *keyobj, *valobj;
 257
 258         keyobj = createStringObject((char*)key,klen);
 259         valobj = createStringObject((char*)val,vlen);
 260         keyobj = tryObjectEncoding(keyobj);
 261         valobj = tryObjectEncoding(valobj);
 262         dictAdd(dict,keyobj,valobj);
 263     }
 264     o->encoding = REDIS_ENCODING_HT;
 265     o->ptr = dict;
 266     zfree(zm);
 267 }
 268
 269 /*-----------------------------------------------------------------------------
 270  * Hash type commands
 271  *----------------------------------------------------------------------------*/
 272
 273 void hsetCommand(redisClient *c) {
 274     int update;
 275     robj *o;
 276
 277     if ((o = hashTypeLookupWriteOrCreate(c,c->argv[1])) == NULL) return;
 278     hashTypeTryConversion(o,c->argv,2,3);
 279     hashTypeTryObjectEncoding(o,&c->argv[2], &c->argv[3]);
 280     update = hashTypeSet(o,c->argv[2],c->argv[3]);
 281     addReply(c, update ? shared.czero : shared.cone);
 282     signalModifiedKey(c->db,c->argv[1]);
 283     server.dirty++;
 284 }
 285
 286 void hsetnxCommand(redisClient *c) {
 287     robj *o;
 288     if ((o = hashTypeLookupWriteOrCreate(c,c->argv[1])) == NULL) return;
 289     hashTypeTryConversion(o,c->argv,2,3);
 290
 291     if (hashTypeExists(o, c->argv[2])) {
 292         addReply(c, shared.czero);
 293     } else {
 294         hashTypeTryObjectEncoding(o,&c->argv[2], &c->argv[3]);
 295         hashTypeSet(o,c->argv[2],c->argv[3]);
 296         addReply(c, shared.cone);
 297         signalModifiedKey(c->db,c->argv[1]);
 298         server.dirty++;
 299     }
 300 }
 301
 302 void hmsetCommand(redisClient *c) {
 303     int i;
 304     robj *o;
 305
 306     if ((c->argc % 2) == 1) {
 307         addReplyError(c,"wrong number of arguments for HMSET");
 308         return;
 309     }
 310
 311     if ((o = hashTypeLookupWriteOrCreate(c,c->argv[1])) == NULL) return;
 312     hashTypeTryConversion(o,c->argv,2,c->argc-1);
 313     for (i = 2; i < c->argc; i += 2) {
 314         hashTypeTryObjectEncoding(o,&c->argv[i], &c->argv[i+1]);
 315         hashTypeSet(o,c->argv[i],c->argv[i+1]);
 316     }
 317     addReply(c, shared.ok);
 318     signalModifiedKey(c->db,c->argv[1]);
 319     server.dirty++;
 320 }
 321
 322 void hincrbyCommand(redisClient *c) {
 323     long long value, incr;
 324     robj *o, *current, *new;
 325
 326     if (getLongLongFromObjectOrReply(c,c->argv[3],&incr,NULL) != REDIS_OK) return;
 327     if ((o = hashTypeLookupWriteOrCreate(c,c->argv[1])) == NULL) return;
 328     if ((current = hashTypeGetObject(o,c->argv[2])) != NULL) {
 329         if (getLongLongFromObjectOrReply(c,current,&value,
 330             "hash value is not an integer") != REDIS_OK) {
 331             decrRefCount(current);
 332             return;
 333         }
 334         decrRefCount(current);
 335     } else {
 336         value = 0;
 337     }
 338
 339     value += incr;
 340     new = createStringObjectFromLongLong(value);
 341     hashTypeTryObjectEncoding(o,&c->argv[2],NULL);
 342     hashTypeSet(o,c->argv[2],new);
 343     decrRefCount(new);
 344     addReplyLongLong(c,value);
 345     signalModifiedKey(c->db,c->argv[1]);
 346     server.dirty++;
 347 }
 348
 349 void hgetCommand(redisClient *c) {
 350     robj *o, *value;
 351     unsigned char *v;
 352     unsigned int vlen;
 353     int encoding;
 354
 355     if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.nullbulk)) == NULL ||
 356         checkType(c,o,REDIS_HASH)) return;
 357
 358     if ((encoding = hashTypeGet(o,c->argv[2],&value,&v,&vlen)) != -1) {
 359         if (encoding == REDIS_ENCODING_HT)
 360             addReplyBulk(c,value);
 361         else
 362             addReplyBulkCBuffer(c,v,vlen);
 363     } else {
 364         addReply(c,shared.nullbulk);
 365     }
 366 }
 367
 368 void hmgetCommand(redisClient *c) {
 369     int i, encoding;
 370     robj *o, *value;
 371     unsigned char *v;
 372     unsigned int vlen;
 373
 374     o = lookupKeyRead(c->db,c->argv[1]);
 375     if (o != NULL && o->type != REDIS_HASH) {
 376         addReply(c,shared.wrongtypeerr);
 377         return;
 378     }
 379
 380     /* Note the check for o != NULL happens inside the loop. This is
 381      * done because objects that cannot be found are considered to be
 382      * an empty hash. The reply should then be a series of NULLs. */
 383     addReplyMultiBulkLen(c,c->argc-2);
 384     for (i = 2; i < c->argc; i++) {
 385         if (o != NULL &&
 386             (encoding = hashTypeGet(o,c->argv[i],&value,&v,&vlen)) != -1) {
 387             if (encoding == REDIS_ENCODING_HT)
 388                 addReplyBulk(c,value);
 389             else
 390                 addReplyBulkCBuffer(c,v,vlen);
 391         } else {
 392             addReply(c,shared.nullbulk);
 393         }
 394     }
 395 }
 396
 397 void hdelCommand(redisClient *c) {
 398     robj *o;
 399     int j, deleted = 0;
 400
 401     if ((o = lookupKeyWriteOrReply(c,c->argv[1],shared.czero)) == NULL ||
 402         checkType(c,o,REDIS_HASH)) return;
 403
 404     for (j = 2; j < c->argc; j++) {
 405         if (hashTypeDelete(o,c->argv[j])) {
 406             deleted++;
 407             if (hashTypeLength(o) == 0) {
 408                 dbDelete(c->db,c->argv[1]);
 409                 break;
 410             }
 411         }
 412     }
 413     if (deleted) {
 414         signalModifiedKey(c->db,c->argv[1]);
 415         server.dirty += deleted;
 416     }
 417     addReplyLongLong(c,deleted);
 418 }
 419
 420 void hlenCommand(redisClient *c) {
 421     robj *o;
 422     if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.czero)) == NULL ||
 423         checkType(c,o,REDIS_HASH)) return;
 424
 425     addReplyLongLong(c,hashTypeLength(o));
 426 }
 427
 428 void genericHgetallCommand(redisClient *c, int flags) {
 429     robj *o;
 430     unsigned long count = 0;
 431     hashTypeIterator *hi;
 432     void *replylen = NULL;
 433
 434     if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.emptymultibulk)) == NULL
 435         || checkType(c,o,REDIS_HASH)) return;
 436
 437     replylen = addDeferredMultiBulkLength(c);
 438     hi = hashTypeInitIterator(o);
 439     while (hashTypeNext(hi) != REDIS_ERR) {
 440         robj *obj;
 441         unsigned char *v = NULL;
 442         unsigned int vlen = 0;
 443         int encoding;
 444
 445         if (flags & REDIS_HASH_KEY) {
 446             encoding = hashTypeCurrent(hi,REDIS_HASH_KEY,&obj,&v,&vlen);
 447             if (encoding == REDIS_ENCODING_HT)
 448                 addReplyBulk(c,obj);
 449             else
 450                 addReplyBulkCBuffer(c,v,vlen);
 451             count++;
 452         }
 453         if (flags & REDIS_HASH_VALUE) {
 454             encoding = hashTypeCurrent(hi,REDIS_HASH_VALUE,&obj,&v,&vlen);
 455             if (encoding == REDIS_ENCODING_HT)
 456                 addReplyBulk(c,obj);
 457             else
 458                 addReplyBulkCBuffer(c,v,vlen);
 459             count++;
 460         }
 461     }
 462     hashTypeReleaseIterator(hi);
 463     setDeferredMultiBulkLength(c,replylen,count);
 464 }
 465
 466 void hkeysCommand(redisClient *c) {
 467     genericHgetallCommand(c,REDIS_HASH_KEY);
 468 }
 469
 470 void hvalsCommand(redisClient *c) {
 471     genericHgetallCommand(c,REDIS_HASH_VALUE);
 472 }
 473
 474 void hgetallCommand(redisClient *c) {
 475     genericHgetallCommand(c,REDIS_HASH_KEY|REDIS_HASH_VALUE);
 476 }
 477
 478 void hexistsCommand(redisClient *c) {
 479     robj *o;
 480     if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.czero)) == NULL ||
 481         checkType(c,o,REDIS_HASH)) return;
 482
 483     addReply(c, hashTypeExists(o,c->argv[2]) ? shared.cone : shared.czero);
 484 }