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 = dictGetVal(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 = dictGetKey(hi->de);
 210         else
 211             *objval = dictGetVal(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, oldvalue;
 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     oldvalue = value;
 340     if ((incr < 0 && oldvalue < 0 && incr < (LLONG_MIN-oldvalue)) ||
 341         (incr > 0 && oldvalue > 0 && incr > (LLONG_MAX-oldvalue))) {
 342         addReplyError(c,"increment or decrement would overflow");
 343         return;
 344     }
 345     value += incr;
 346     new = createStringObjectFromLongLong(value);
 347     hashTypeTryObjectEncoding(o,&c->argv[2],NULL);
 348     hashTypeSet(o,c->argv[2],new);
 349     decrRefCount(new);
 350     addReplyLongLong(c,value);
 351     signalModifiedKey(c->db,c->argv[1]);
 352     server.dirty++;
 353 }
 354
 355 void hincrbyfloatCommand(redisClient *c) {
 356     double long value, incr;
 357     robj *o, *current, *new;
 358
 359     if (getLongDoubleFromObjectOrReply(c,c->argv[3],&incr,NULL) != REDIS_OK) return;
 360     if ((o = hashTypeLookupWriteOrCreate(c,c->argv[1])) == NULL) return;
 361     if ((current = hashTypeGetObject(o,c->argv[2])) != NULL) {
 362         if (getLongDoubleFromObjectOrReply(c,current,&value,
 363             "hash value is not a valid float") != REDIS_OK) {
 364             decrRefCount(current);
 365             return;
 366         }
 367         decrRefCount(current);
 368     } else {
 369         value = 0;
 370     }
 371
 372     value += incr;
 373     new = createStringObjectFromLongDouble(value);
 374     hashTypeTryObjectEncoding(o,&c->argv[2],NULL);
 375     hashTypeSet(o,c->argv[2],new);
 376     addReplyBulk(c,new);
 377     decrRefCount(new);
 378     signalModifiedKey(c->db,c->argv[1]);
 379     server.dirty++;
 380 }
 381
 382 void hgetCommand(redisClient *c) {
 383     robj *o, *value;
 384     unsigned char *v;
 385     unsigned int vlen;
 386     int encoding;
 387
 388     if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.nullbulk)) == NULL ||
 389         checkType(c,o,REDIS_HASH)) return;
 390
 391     if ((encoding = hashTypeGet(o,c->argv[2],&value,&v,&vlen)) != -1) {
 392         if (encoding == REDIS_ENCODING_HT)
 393             addReplyBulk(c,value);
 394         else
 395             addReplyBulkCBuffer(c,v,vlen);
 396     } else {
 397         addReply(c,shared.nullbulk);
 398     }
 399 }
 400
 401 void hmgetCommand(redisClient *c) {
 402     int i, encoding;
 403     robj *o, *value;
 404     unsigned char *v;
 405     unsigned int vlen;
 406
 407     o = lookupKeyRead(c->db,c->argv[1]);
 408     if (o != NULL && o->type != REDIS_HASH) {
 409         addReply(c,shared.wrongtypeerr);
 410         return;
 411     }
 412
 413     /* Note the check for o != NULL happens inside the loop. This is
 414      * done because objects that cannot be found are considered to be
 415      * an empty hash. The reply should then be a series of NULLs. */
 416     addReplyMultiBulkLen(c,c->argc-2);
 417     for (i = 2; i < c->argc; i++) {
 418         if (o != NULL &&
 419             (encoding = hashTypeGet(o,c->argv[i],&value,&v,&vlen)) != -1) {
 420             if (encoding == REDIS_ENCODING_HT)
 421                 addReplyBulk(c,value);
 422             else
 423                 addReplyBulkCBuffer(c,v,vlen);
 424         } else {
 425             addReply(c,shared.nullbulk);
 426         }
 427     }
 428 }
 429
 430 void hdelCommand(redisClient *c) {
 431     robj *o;
 432     int j, deleted = 0;
 433
 434     if ((o = lookupKeyWriteOrReply(c,c->argv[1],shared.czero)) == NULL ||
 435         checkType(c,o,REDIS_HASH)) return;
 436
 437     for (j = 2; j < c->argc; j++) {
 438         if (hashTypeDelete(o,c->argv[j])) {
 439             deleted++;
 440             if (hashTypeLength(o) == 0) {
 441                 dbDelete(c->db,c->argv[1]);
 442                 break;
 443             }
 444         }
 445     }
 446     if (deleted) {
 447         signalModifiedKey(c->db,c->argv[1]);
 448         server.dirty += deleted;
 449     }
 450     addReplyLongLong(c,deleted);
 451 }
 452
 453 void hlenCommand(redisClient *c) {
 454     robj *o;
 455     if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.czero)) == NULL ||
 456         checkType(c,o,REDIS_HASH)) return;
 457
 458     addReplyLongLong(c,hashTypeLength(o));
 459 }
 460
 461 void genericHgetallCommand(redisClient *c, int flags) {
 462     robj *o;
 463     unsigned long count = 0;
 464     hashTypeIterator *hi;
 465     void *replylen = NULL;
 466
 467     if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.emptymultibulk)) == NULL
 468         || checkType(c,o,REDIS_HASH)) return;
 469
 470     replylen = addDeferredMultiBulkLength(c);
 471     hi = hashTypeInitIterator(o);
 472     while (hashTypeNext(hi) != REDIS_ERR) {
 473         robj *obj;
 474         unsigned char *v = NULL;
 475         unsigned int vlen = 0;
 476         int encoding;
 477
 478         if (flags & REDIS_HASH_KEY) {
 479             encoding = hashTypeCurrent(hi,REDIS_HASH_KEY,&obj,&v,&vlen);
 480             if (encoding == REDIS_ENCODING_HT)
 481                 addReplyBulk(c,obj);
 482             else
 483                 addReplyBulkCBuffer(c,v,vlen);
 484             count++;
 485         }
 486         if (flags & REDIS_HASH_VALUE) {
 487             encoding = hashTypeCurrent(hi,REDIS_HASH_VALUE,&obj,&v,&vlen);
 488             if (encoding == REDIS_ENCODING_HT)
 489                 addReplyBulk(c,obj);
 490             else
 491                 addReplyBulkCBuffer(c,v,vlen);
 492             count++;
 493         }
 494     }
 495     hashTypeReleaseIterator(hi);
 496     setDeferredMultiBulkLength(c,replylen,count);
 497 }
 498
 499 void hkeysCommand(redisClient *c) {
 500     genericHgetallCommand(c,REDIS_HASH_KEY);
 501 }
 502
 503 void hvalsCommand(redisClient *c) {
 504     genericHgetallCommand(c,REDIS_HASH_VALUE);
 505 }
 506
 507 void hgetallCommand(redisClient *c) {
 508     genericHgetallCommand(c,REDIS_HASH_KEY|REDIS_HASH_VALUE);
 509 }
 510
 511 void hexistsCommand(redisClient *c) {
 512     robj *o;
 513     if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.czero)) == NULL ||
 514         checkType(c,o,REDIS_HASH)) return;
 515
 516     addReply(c, hashTypeExists(o,c->argv[2]) ? shared.cone : shared.czero);
 517 }