src/zipmap.c

   1 /* String -> String Map data structure optimized for size.
   2  * This file implements a data structure mapping strings to other strings
   3  * implementing an O(n) lookup data structure designed to be very memory
   4  * efficient.
   5  *
   6  * The Redis Hash type uses this data structure for hashes composed of a small
   7  * number of elements, to switch to an hash table once a given number of
   8  * elements is reached.
   9  *
  10  * Given that many times Redis Hashes are used to represent objects composed
  11  * of few fields, this is a very big win in terms of used memory.
  12  *
  13  * --------------------------------------------------------------------------
  14  *
  15  * Copyright (c) 2009-2010, Salvatore Sanfilippo <antirez at gmail dot com>
  16  * All rights reserved.
  17  *
  18  * Redistribution and use in source and binary forms, with or without
  19  * modification, are permitted provided that the following conditions are met:
  20  *
  21  *   * Redistributions of source code must retain the above copyright notice,
  22  *     this list of conditions and the following disclaimer.
  23  *   * Redistributions in binary form must reproduce the above copyright
  24  *     notice, this list of conditions and the following disclaimer in the
  25  *     documentation and/or other materials provided with the distribution.
  26  *   * Neither the name of Redis nor the names of its contributors may be used
  27  *     to endorse or promote products derived from this software without
  28  *     specific prior written permission.
  29  *
  30  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  31  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  32  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  33  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
  34  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  35  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  36  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  37  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  38  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  39  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  40  * POSSIBILITY OF SUCH DAMAGE.
  41  */
  42
  43 /* Memory layout of a zipmap, for the map "foo" => "bar", "hello" => "world":
  44  *
  45  * <zmlen><len>"foo"<len><free>"bar"<len>"hello"<len><free>"world"
  46  *
  47  * <zmlen> is 1 byte length that holds the current size of the zipmap.
  48  * When the zipmap length is greater than or equal to 254, this value
  49  * is not used and the zipmap needs to be traversed to find out the length.
  50  *
  51  * <len> is the length of the following string (key or value).
  52  * <len> lengths are encoded in a single value or in a 5 bytes value.
  53  * If the first byte value (as an unsigned 8 bit value) is between 0 and
  54  * 252, it's a single-byte length. If it is 253 then a four bytes unsigned
  55  * integer follows (in the host byte ordering). A value fo 255 is used to
  56  * signal the end of the hash. The special value 254 is used to mark
  57  * empty space that can be used to add new key/value pairs.
  58  *
  59  * <free> is the number of free unused bytes
  60  * after the string, resulting from modification of values associated to a
  61  * key (for instance if "foo" is set to "bar', and later "foo" will be se to
  62  * "hi", I'll have a free byte to use if the value will enlarge again later,
  63  * or even in order to add a key/value pair if it fits.
  64  *
  65  * <free> is always an unsigned 8 bit number, because if after an
  66  * update operation there are more than a few free bytes, the zipmap will be
  67  * reallocated to make sure it is as small as possible.
  68  *
  69  * The most compact representation of the above two elements hash is actually:
  70  *
  71  * "\x02\x03foo\x03\x00bar\x05hello\x05\x00world\xff"
  72  *
  73  * Note that because keys and values are prefixed length "objects",
  74  * the lookup will take O(N) where N is the number of elements
  75  * in the zipmap and *not* the number of bytes needed to represent the zipmap.
  76  * This lowers the constant times considerably.
  77  */
  78
  79 #include <stdio.h>
  80 #include <string.h>
  81 #include <assert.h>
  82 #include "zmalloc.h"
  83 #include "endian.h"
  84
  85 #define ZIPMAP_BIGLEN 254
  86 #define ZIPMAP_END 255
  87
  88 /* The following defines the max value for the <free> field described in the
  89  * comments above, that is, the max number of trailing bytes in a value. */
  90 #define ZIPMAP_VALUE_MAX_FREE 4
  91
  92 /* The following macro returns the number of bytes needed to encode the length
  93  * for the integer value _l, that is, 1 byte for lengths < ZIPMAP_BIGLEN and
  94  * 5 bytes for all the other lengths. */
  95 #define ZIPMAP_LEN_BYTES(_l) (((_l) < ZIPMAP_BIGLEN) ? 1 : sizeof(unsigned int)+1)
  96
  97 /* Create a new empty zipmap. */
  98 unsigned char *zipmapNew(void) {
  99     unsigned char *zm = zmalloc(2);
 100
 101     zm[0] = 0; /* Length */
 102     zm[1] = ZIPMAP_END;
 103     return zm;
 104 }
 105
 106 /* Decode the encoded length pointed by 'p' */
 107 static unsigned int zipmapDecodeLength(unsigned char *p) {
 108     unsigned int len = *p;
 109
 110     if (len < ZIPMAP_BIGLEN) return len;
 111     memcpy(&len,p+1,sizeof(unsigned int));
 112     memrev32ifbe(&len);
 113     return len;
 114 }
 115
 116 /* Encode the length 'l' writing it in 'p'. If p is NULL it just returns
 117  * the amount of bytes required to encode such a length. */
 118 static unsigned int zipmapEncodeLength(unsigned char *p, unsigned int len) {
 119     if (p == NULL) {
 120         return ZIPMAP_LEN_BYTES(len);
 121     } else {
 122         if (len < ZIPMAP_BIGLEN) {
 123             p[0] = len;
 124             return 1;
 125         } else {
 126             p[0] = ZIPMAP_BIGLEN;
 127             memcpy(p+1,&len,sizeof(len));
 128             memrev32ifbe(p+1);
 129             return 1+sizeof(len);
 130         }
 131     }
 132 }
 133
 134 /* Search for a matching key, returning a pointer to the entry inside the
 135  * zipmap. Returns NULL if the key is not found.
 136  *
 137  * If NULL is returned, and totlen is not NULL, it is set to the entire
 138  * size of the zimap, so that the calling function will be able to
 139  * reallocate the original zipmap to make room for more entries. */
 140 static unsigned char *zipmapLookupRaw(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned int *totlen) {
 141     unsigned char *p = zm+1, *k = NULL;
 142     unsigned int l,llen;
 143
 144     while(*p != ZIPMAP_END) {
 145         unsigned char free;
 146
 147         /* Match or skip the key */
 148         l = zipmapDecodeLength(p);
 149         llen = zipmapEncodeLength(NULL,l);
 150         if (key != NULL && k == NULL && l == klen && !memcmp(p+llen,key,l)) {
 151             /* Only return when the user doesn't care
 152              * for the total length of the zipmap. */
 153             if (totlen != NULL) {
 154                 k = p;
 155             } else {
 156                 return p;
 157             }
 158         }
 159         p += llen+l;
 160         /* Skip the value as well */
 161         l = zipmapDecodeLength(p);
 162         p += zipmapEncodeLength(NULL,l);
 163         free = p[0];
 164         p += l+1+free; /* +1 to skip the free byte */
 165     }
 166     if (totlen != NULL) *totlen = (unsigned int)(p-zm)+1;
 167     return k;
 168 }
 169
 170 static unsigned long zipmapRequiredLength(unsigned int klen, unsigned int vlen) {
 171     unsigned int l;
 172
 173     l = klen+vlen+3;
 174     if (klen >= ZIPMAP_BIGLEN) l += 4;
 175     if (vlen >= ZIPMAP_BIGLEN) l += 4;
 176     return l;
 177 }
 178
 179 /* Return the total amount used by a key (encoded length + payload) */
 180 static unsigned int zipmapRawKeyLength(unsigned char *p) {
 181     unsigned int l = zipmapDecodeLength(p);
 182     return zipmapEncodeLength(NULL,l) + l;
 183 }
 184
 185 /* Return the total amount used by a value
 186  * (encoded length + single byte free count + payload) */
 187 static unsigned int zipmapRawValueLength(unsigned char *p) {
 188     unsigned int l = zipmapDecodeLength(p);
 189     unsigned int used;
 190
 191     used = zipmapEncodeLength(NULL,l);
 192     used += p[used] + 1 + l;
 193     return used;
 194 }
 195
 196 /* If 'p' points to a key, this function returns the total amount of
 197  * bytes used to store this entry (entry = key + associated value + trailing
 198  * free space if any). */
 199 static unsigned int zipmapRawEntryLength(unsigned char *p) {
 200     unsigned int l = zipmapRawKeyLength(p);
 201     return l + zipmapRawValueLength(p+l);
 202 }
 203
 204 static inline unsigned char *zipmapResize(unsigned char *zm, unsigned int len) {
 205     zm = zrealloc(zm, len);
 206     zm[len-1] = ZIPMAP_END;
 207     return zm;
 208 }
 209
 210 /* Set key to value, creating the key if it does not already exist.
 211  * If 'update' is not NULL, *update is set to 1 if the key was
 212  * already preset, otherwise to 0. */
 213 unsigned char *zipmapSet(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned char *val, unsigned int vlen, int *update) {
 214     unsigned int zmlen, offset;
 215     unsigned int freelen, reqlen = zipmapRequiredLength(klen,vlen);
 216     unsigned int empty, vempty;
 217     unsigned char *p;
 218
 219     freelen = reqlen;
 220     if (update) *update = 0;
 221     p = zipmapLookupRaw(zm,key,klen,&zmlen);
 222     if (p == NULL) {
 223         /* Key not found: enlarge */
 224         zm = zipmapResize(zm, zmlen+reqlen);
 225         p = zm+zmlen-1;
 226         zmlen = zmlen+reqlen;
 227
 228         /* Increase zipmap length (this is an insert) */
 229         if (zm[0] < ZIPMAP_BIGLEN) zm[0]++;
 230     } else {
 231         /* Key found. Is there enough space for the new value? */
 232         /* Compute the total length: */
 233         if (update) *update = 1;
 234         freelen = zipmapRawEntryLength(p);
 235         if (freelen < reqlen) {
 236             /* Store the offset of this key within the current zipmap, so
 237              * it can be resized. Then, move the tail backwards so this
 238              * pair fits at the current position. */
 239             offset = p-zm;
 240             zm = zipmapResize(zm, zmlen-freelen+reqlen);
 241             p = zm+offset;
 242
 243             /* The +1 in the number of bytes to be moved is caused by the
 244              * end-of-zipmap byte. Note: the *original* zmlen is used. */
 245             memmove(p+reqlen, p+freelen, zmlen-(offset+freelen+1));
 246             zmlen = zmlen-freelen+reqlen;
 247             freelen = reqlen;
 248         }
 249     }
 250
 251     /* We now have a suitable block where the key/value entry can
 252      * be written. If there is too much free space, move the tail
 253      * of the zipmap a few bytes to the front and shrink the zipmap,
 254      * as we want zipmaps to be very space efficient. */
 255     empty = freelen-reqlen;
 256     if (empty >= ZIPMAP_VALUE_MAX_FREE) {
 257         /* First, move the tail <empty> bytes to the front, then resize
 258          * the zipmap to be <empty> bytes smaller. */
 259         offset = p-zm;
 260         memmove(p+reqlen, p+freelen, zmlen-(offset+freelen+1));
 261         zmlen -= empty;
 262         zm = zipmapResize(zm, zmlen);
 263         p = zm+offset;
 264         vempty = 0;
 265     } else {
 266         vempty = empty;
 267     }
 268
 269     /* Just write the key + value and we are done. */
 270     /* Key: */
 271     p += zipmapEncodeLength(p,klen);
 272     memcpy(p,key,klen);
 273     p += klen;
 274     /* Value: */
 275     p += zipmapEncodeLength(p,vlen);
 276     *p++ = vempty;
 277     memcpy(p,val,vlen);
 278     return zm;
 279 }
 280
 281 /* Remove the specified key. If 'deleted' is not NULL the pointed integer is
 282  * set to 0 if the key was not found, to 1 if it was found and deleted. */
 283 unsigned char *zipmapDel(unsigned char *zm, unsigned char *key, unsigned int klen, int *deleted) {
 284     unsigned int zmlen, freelen;
 285     unsigned char *p = zipmapLookupRaw(zm,key,klen,&zmlen);
 286     if (p) {
 287         freelen = zipmapRawEntryLength(p);
 288         memmove(p, p+freelen, zmlen-((p-zm)+freelen+1));
 289         zm = zipmapResize(zm, zmlen-freelen);
 290
 291         /* Decrease zipmap length */
 292         if (zm[0] < ZIPMAP_BIGLEN) zm[0]--;
 293
 294         if (deleted) *deleted = 1;
 295     } else {
 296         if (deleted) *deleted = 0;
 297     }
 298     return zm;
 299 }
 300
 301 /* Call it before to iterate trought elements via zipmapNext() */
 302 unsigned char *zipmapRewind(unsigned char *zm) {
 303     return zm+1;
 304 }
 305
 306 /* This function is used to iterate through all the zipmap elements.
 307  * In the first call the first argument is the pointer to the zipmap + 1.
 308  * In the next calls what zipmapNext returns is used as first argument.
 309  * Example:
 310  *
 311  * unsigned char *i = zipmapRewind(my_zipmap);
 312  * while((i = zipmapNext(i,&key,&klen,&value,&vlen)) != NULL) {
 313  *     printf("%d bytes key at $p\n", klen, key);
 314  *     printf("%d bytes value at $p\n", vlen, value);
 315  * }
 316  */
 317 unsigned char *zipmapNext(unsigned char *zm, unsigned char **key, unsigned int *klen, unsigned char **value, unsigned int *vlen) {
 318     if (zm[0] == ZIPMAP_END) return NULL;
 319     if (key) {
 320         *key = zm;
 321         *klen = zipmapDecodeLength(zm);
 322         *key += ZIPMAP_LEN_BYTES(*klen);
 323     }
 324     zm += zipmapRawKeyLength(zm);
 325     if (value) {
 326         *value = zm+1;
 327         *vlen = zipmapDecodeLength(zm);
 328         *value += ZIPMAP_LEN_BYTES(*vlen);
 329     }
 330     zm += zipmapRawValueLength(zm);
 331     return zm;
 332 }
 333
 334 /* Search a key and retrieve the pointer and len of the associated value.
 335  * If the key is found the function returns 1, otherwise 0. */
 336 int zipmapGet(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned char **value, unsigned int *vlen) {
 337     unsigned char *p;
 338
 339     if ((p = zipmapLookupRaw(zm,key,klen,NULL)) == NULL) return 0;
 340     p += zipmapRawKeyLength(p);
 341     *vlen = zipmapDecodeLength(p);
 342     *value = p + ZIPMAP_LEN_BYTES(*vlen) + 1;
 343     return 1;
 344 }
 345
 346 /* Return 1 if the key exists, otherwise 0 is returned. */
 347 int zipmapExists(unsigned char *zm, unsigned char *key, unsigned int klen) {
 348     return zipmapLookupRaw(zm,key,klen,NULL) != NULL;
 349 }
 350
 351 /* Return the number of entries inside a zipmap */
 352 unsigned int zipmapLen(unsigned char *zm) {
 353     unsigned int len = 0;
 354     if (zm[0] < ZIPMAP_BIGLEN) {
 355         len = zm[0];
 356     } else {
 357         unsigned char *p = zipmapRewind(zm);
 358         while((p = zipmapNext(p,NULL,NULL,NULL,NULL)) != NULL) len++;
 359
 360         /* Re-store length if small enough */
 361         if (len < ZIPMAP_BIGLEN) zm[0] = len;
 362     }
 363     return len;
 364 }
 365
 366 /* Return the raw size in bytes of a zipmap, so that we can serialize
 367  * the zipmap on disk (or everywhere is needed) just writing the returned
 368  * amount of bytes of the C array starting at the zipmap pointer. */
 369 size_t zipmapBlobLen(unsigned char *zm) {
 370     unsigned int totlen;
 371     zipmapLookupRaw(zm,NULL,0,&totlen);
 372     return totlen;
 373 }
 374
 375 #ifdef ZIPMAP_TEST_MAIN
 376 void zipmapRepr(unsigned char *p) {
 377     unsigned int l;
 378
 379     printf("{status %u}",*p++);
 380     while(1) {
 381         if (p[0] == ZIPMAP_END) {
 382             printf("{end}");
 383             break;
 384         } else {
 385             unsigned char e;
 386
 387             l = zipmapDecodeLength(p);
 388             printf("{key %u}",l);
 389             p += zipmapEncodeLength(NULL,l);
 390             if (l != 0 && fwrite(p,l,1,stdout) == 0) perror("fwrite");
 391             p += l;
 392
 393             l = zipmapDecodeLength(p);
 394             printf("{value %u}",l);
 395             p += zipmapEncodeLength(NULL,l);
 396             e = *p++;
 397             if (l != 0 && fwrite(p,l,1,stdout) == 0) perror("fwrite");
 398             p += l+e;
 399             if (e) {
 400                 printf("[");
 401                 while(e--) printf(".");
 402                 printf("]");
 403             }
 404         }
 405     }
 406     printf("\n");
 407 }
 408
 409 int main(void) {
 410     unsigned char *zm;
 411
 412     zm = zipmapNew();
 413
 414     zm = zipmapSet(zm,(unsigned char*) "name",4, (unsigned char*) "foo",3,NULL);
 415     zm = zipmapSet(zm,(unsigned char*) "surname",7, (unsigned char*) "foo",3,NULL);
 416     zm = zipmapSet(zm,(unsigned char*) "age",3, (unsigned char*) "foo",3,NULL);
 417     zipmapRepr(zm);
 418
 419     zm = zipmapSet(zm,(unsigned char*) "hello",5, (unsigned char*) "world!",6,NULL);
 420     zm = zipmapSet(zm,(unsigned char*) "foo",3, (unsigned char*) "bar",3,NULL);
 421     zm = zipmapSet(zm,(unsigned char*) "foo",3, (unsigned char*) "!",1,NULL);
 422     zipmapRepr(zm);
 423     zm = zipmapSet(zm,(unsigned char*) "foo",3, (unsigned char*) "12345",5,NULL);
 424     zipmapRepr(zm);
 425     zm = zipmapSet(zm,(unsigned char*) "new",3, (unsigned char*) "xx",2,NULL);
 426     zm = zipmapSet(zm,(unsigned char*) "noval",5, (unsigned char*) "",0,NULL);
 427     zipmapRepr(zm);
 428     zm = zipmapDel(zm,(unsigned char*) "new",3,NULL);
 429     zipmapRepr(zm);
 430
 431     printf("\nLook up large key:\n");
 432     {
 433         unsigned char buf[512];
 434         unsigned char *value;
 435         unsigned int vlen, i;
 436         for (i = 0; i < 512; i++) buf[i] = 'a';
 437
 438         zm = zipmapSet(zm,buf,512,(unsigned char*) "long",4,NULL);
 439         if (zipmapGet(zm,buf,512,&value,&vlen)) {
 440             printf("  <long key> is associated to the %d bytes value: %.*s\n",
 441                 vlen, vlen, value);
 442         }
 443     }
 444
 445     printf("\nPerform a direct lookup:\n");
 446     {
 447         unsigned char *value;
 448         unsigned int vlen;
 449
 450         if (zipmapGet(zm,(unsigned char*) "foo",3,&value,&vlen)) {
 451             printf("  foo is associated to the %d bytes value: %.*s\n",
 452                 vlen, vlen, value);
 453         }
 454     }
 455     printf("\nIterate trought elements:\n");
 456     {
 457         unsigned char *i = zipmapRewind(zm);
 458         unsigned char *key, *value;
 459         unsigned int klen, vlen;
 460
 461         while((i = zipmapNext(i,&key,&klen,&value,&vlen)) != NULL) {
 462             printf("  %d:%.*s => %d:%.*s\n", klen, klen, key, vlen, vlen, value);
 463         }
 464     }
 465     return 0;
 466 }
 467 #endif