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  * <status><len>"foo"<len><free>"bar"<len>"hello"<len><free>"world"
  46  *
  47  * <status> is 1 byte status. Currently only 1 bit is used: if the least
  48  * significant bit is set, it means the zipmap needs to be defragmented.
  49  *
  50  * <len> is the length of the following string (key or value).
  51  * <len> lengths are encoded in a single value or in a 5 bytes value.
  52  * If the first byte value (as an unsigned 8 bit value) is between 0 and
  53  * 252, it's a single-byte length. If it is 253 then a four bytes unsigned
  54  * integer follows (in the host byte ordering). A value fo 255 is used to
  55  * signal the end of the hash. The special value 254 is used to mark
  56  * empty space that can be used to add new key/value pairs.
  57  *
  58  * <free> is the number of free unused bytes
  59  * after the string, resulting from modification of values associated to a
  60  * key (for instance if "foo" is set to "bar', and later "foo" will be se to
  61  * "hi", I'll have a free byte to use if the value will enlarge again later,
  62  * or even in order to add a key/value pair if it fits.
  63  *
  64  * <free> is always an unsigned 8 bit number, because if after an
  65  * update operation there are more than a few free bytes, they'll be converted
  66  * into empty space prefixed by the special value 254.
  67  *
  68  * The most compact representation of the above two elements hash is actually:
  69  *
  70  * "\x00\x03foo\x03\x00bar\x05hello\x05\x00world\xff"
  71  *
  72  * Empty space is marked using a 254 bytes + a <len> (coded as already
  73  * specified). The length includes the 254 bytes in the count and the
  74  * space taken by the <len> field. So for instance removing the "foo" key
  75  * from the zipmap above will lead to the following representation:
  76  *
  77  * "\x00\xfd\x10........\x05hello\x05\x00world\xff"
  78  *
  79  * Note that because empty space, keys, values, are all prefixed length
  80  * "objects", the lookup will take O(N) where N is the numeber of elements
  81  * in the zipmap and *not* the number of bytes needed to represent the zipmap.
  82  * This lowers the constant times considerably.
  83  */
  84
  85 #include <stdio.h>
  86 #include <string.h>
  87 #include <assert.h>
  88 #include "zmalloc.h"
  89
  90 #define ZIPMAP_BIGLEN 253
  91 #define ZIPMAP_EMPTY 254
  92 #define ZIPMAP_END 255
  93
  94 #define ZIPMAP_STATUS_FRAGMENTED 1
  95
  96 /* The following defines the max value for the <free> field described in the
  97  * comments above, that is, the max number of trailing bytes in a value. */
  98 #define ZIPMAP_VALUE_MAX_FREE 5
  99
 100 /* Create a new empty zipmap. */
 101 unsigned char *zipmapNew(void) {
 102     unsigned char *zm = zmalloc(2);
 103
 104     zm[0] = 0; /* Status */
 105     zm[1] = ZIPMAP_END;
 106     return zm;
 107 }
 108
 109 /* Decode the encoded length pointed by 'p' */
 110 static unsigned int zipmapDecodeLength(unsigned char *p) {
 111     unsigned int len = *p;
 112
 113     if (len < ZIPMAP_BIGLEN) return len;
 114     memcpy(&len,p,sizeof(unsigned int));
 115     return len;
 116 }
 117
 118 /* Encode the length 'l' writing it in 'p'. If p is NULL it just returns
 119  * the amount of bytes required to encode such a length. */
 120 static unsigned int zipmapEncodeLength(unsigned char *p, unsigned int len) {
 121     if (p == NULL) {
 122         return (len < ZIPMAP_BIGLEN) ? 1 : 1+sizeof(unsigned int);
 123     } else {
 124         if (len < ZIPMAP_BIGLEN) {
 125             p[0] = len;
 126             return 1;
 127         } else {
 128             p[0] = ZIPMAP_BIGLEN;
 129             memcpy(p+1,&len,sizeof(len));
 130             return 1+sizeof(len);
 131         }
 132     }
 133 }
 134
 135 /* Search for a matching key, returning a pointer to the entry inside the
 136  * zipmap. Returns NULL if the key is not found.
 137  *
 138  * If NULL is returned, and totlen is not NULL, it is set to the entire
 139  * size of the zimap, so that the calling function will be able to
 140  * reallocate the original zipmap to make room for more entries.
 141  *
 142  * If NULL is returned, and freeoff and freelen are not NULL, they are set
 143  * to the offset of the first empty space that can hold '*freelen' bytes
 144  * (freelen is an integer pointer used both to signal the required length
 145  * and to get the reply from the function). If there is not a suitable
 146  * free space block to hold the requested bytes, *freelen is set to 0. */
 147 static unsigned char *zipmapLookupRaw(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned int *totlen, unsigned int *freeoff, unsigned int *freelen) {
 148     unsigned char *p = zm+1;
 149     unsigned int l;
 150     unsigned int reqfreelen = 0; /* initialized just to prevent warning */
 151
 152     if (freelen) {
 153         reqfreelen = *freelen;
 154         *freelen = 0;
 155         assert(reqfreelen != 0);
 156     }
 157     while(*p != ZIPMAP_END) {
 158         if (*p == ZIPMAP_EMPTY) {
 159             l = zipmapDecodeLength(p+1);
 160             /* if the user want a free space report, and this space is
 161              * enough, and we did't already found a suitable space... */
 162             if (freelen && l >= reqfreelen && *freelen == 0) {
 163                 *freelen = l;
 164                 *freeoff = p-zm;
 165             }
 166             p += l;
 167             zm[0] |= ZIPMAP_STATUS_FRAGMENTED;
 168         } else {
 169             unsigned char free;
 170
 171             /* Match or skip the key */
 172             l = zipmapDecodeLength(p);
 173             if (l == klen && !memcmp(p+1,key,l)) return p;
 174             p += zipmapEncodeLength(NULL,l) + l;
 175             /* Skip the value as well */
 176             l = zipmapDecodeLength(p);
 177             p += zipmapEncodeLength(NULL,l);
 178             free = p[0];
 179             p += l+1+free; /* +1 to skip the free byte */
 180         }
 181     }
 182     if (totlen != NULL) *totlen = (unsigned int)(p-zm)+1;
 183     return NULL;
 184 }
 185
 186 static unsigned long zipmapRequiredLength(unsigned int klen, unsigned int vlen) {
 187     unsigned int l;
 188
 189     l = klen+vlen+3;
 190     if (klen >= ZIPMAP_BIGLEN) l += 4;
 191     if (vlen >= ZIPMAP_BIGLEN) l += 4;
 192     return l;
 193 }
 194
 195 /* Return the total amount used by a key (encoded length + payload) */
 196 static unsigned int zipmapRawKeyLength(unsigned char *p) {
 197     unsigned int l = zipmapDecodeLength(p);
 198
 199     return zipmapEncodeLength(NULL,l) + l;
 200 }
 201
 202 /* Return the total amount used by a value
 203  * (encoded length + single byte free count + payload) */
 204 static unsigned int zipmapRawValueLength(unsigned char *p) {
 205     unsigned int l = zipmapDecodeLength(p);
 206     unsigned int used;
 207
 208     used = zipmapEncodeLength(NULL,l);
 209     used += p[used] + 1 + l;
 210     return used;
 211 }
 212
 213 /* If 'p' points to a key, this function returns the total amount of
 214  * bytes used to store this entry (entry = key + associated value + trailing
 215  * free space if any). */
 216 static unsigned int zipmapRawEntryLength(unsigned char *p) {
 217     unsigned int l = zipmapRawKeyLength(p);
 218
 219     return l + zipmapRawValueLength(p+l);
 220 }
 221
 222 /* Set key to value, creating the key if it does not already exist. */
 223 unsigned char *zipmapSet(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned char *val, unsigned int vlen) {
 224     unsigned int oldlen = 0, freeoff = 0, freelen;
 225     unsigned int reqlen = zipmapRequiredLength(klen,vlen);
 226     unsigned int empty, vempty;
 227     unsigned char *p;
 228
 229     freelen = reqlen;
 230     p = zipmapLookupRaw(zm,key,klen,&oldlen,&freeoff,&freelen);
 231     if (p == NULL && freelen == 0) {
 232         printf("HERE oldlen:%u required:%u\n",oldlen,reqlen);
 233         /* Key not found, and not space for the new key. Enlarge */
 234         zm = zrealloc(zm,oldlen+reqlen);
 235         p = zm+oldlen-1;
 236         zm[oldlen+reqlen-1] = ZIPMAP_END;
 237         freelen = reqlen;
 238         printf("New total length is: %u\n", oldlen+reqlen);
 239     } else if (p == NULL) {
 240         /* Key not found, but there is enough free space. */
 241         p = zm+freeoff;
 242         /* note: freelen is already set in this case */
 243     } else {
 244         unsigned char *b = p;
 245
 246         /* Key found. Is there enough space for the new value? */
 247         /* Compute the total length: */
 248         freelen = zipmapRawKeyLength(b);
 249         b += freelen;
 250         freelen += zipmapRawValueLength(b);
 251         if (freelen < reqlen) {
 252             /* Mark this entry as free and recurse */
 253             p[0] = ZIPMAP_EMPTY;
 254             zipmapEncodeLength(p+1,freelen);
 255             zm[0] |= ZIPMAP_STATUS_FRAGMENTED;
 256             return zipmapSet(zm,key,klen,val,vlen);
 257         }
 258     }
 259
 260     /* Ok we have a suitable block where to write the new key/value
 261      * entry. */
 262     empty = freelen-reqlen;
 263     /* If there is too much free space mark it as a free block instead
 264      * of adding it as trailing empty space for the value, as we want
 265      * zipmaps to be very space efficient. */
 266     if (empty > ZIPMAP_VALUE_MAX_FREE) {
 267         unsigned char *e;
 268
 269         e = p+reqlen;
 270         e[0] = ZIPMAP_EMPTY;
 271         zipmapEncodeLength(e+1,empty);
 272         vempty = 0;
 273         zm[0] |= ZIPMAP_STATUS_FRAGMENTED;
 274     } else {
 275         vempty = empty;
 276     }
 277
 278     /* Just write the key + value and we are done. */
 279     /* Key: */
 280     p += zipmapEncodeLength(p,klen);
 281     memcpy(p,key,klen);
 282     p += klen;
 283     /* Value: */
 284     p += zipmapEncodeLength(p,vlen);
 285     *p++ = vempty;
 286     memcpy(p,val,vlen);
 287     return zm;
 288 }
 289
 290 /* Remove the specified key. If 'deleted' is not NULL the pointed integer is
 291  * set to 0 if the key was not found, to 1 if it was found and deleted. */
 292 unsigned char *zipmapDel(unsigned char *zm, unsigned char *key, unsigned int klen, int *deleted) {
 293     unsigned char *p = zipmapLookupRaw(zm,key,klen,NULL,NULL,NULL);
 294     if (p) {
 295         unsigned int freelen = zipmapRawEntryLength(p);
 296
 297         p[0] = ZIPMAP_EMPTY;
 298         zipmapEncodeLength(p+1,freelen);
 299         zm[0] |= ZIPMAP_STATUS_FRAGMENTED;
 300         if (deleted) *deleted = 1;
 301     } else {
 302         if (deleted) *deleted = 0;
 303     }
 304     return zm;
 305 }
 306
 307 /* This function is used to iterate through all the zipmap elements.
 308  * In the first call the first argument is the pointer to the zipmap + 1.
 309  * In the next calls what zipmapNext returns is used as first argument.
 310  * Example:
 311  *
 312  * unsigned char *i = my_zipmap+1;
 313  * while((i = zipmapNext(i,&key,&klen,&value,&vlen)) != NULL) {
 314  *     printf("%d bytes key at $p\n", klen, key);
 315  *     printf("%d bytes value at $p\n", vlen, value);
 316  * }
 317  */
 318 unsigned char *zipmapNext(unsigned char *zm, unsigned char **key,
 319             unsigned int *klen, unsigned char **value, unsigned int *vlen) {
 320     while(zm[0] == ZIPMAP_EMPTY)
 321         zm += zipmapDecodeLength(zm+1);
 322     if (zm[0] == ZIPMAP_END) return NULL;
 323     if (key) {
 324         *key = zm;
 325         *klen = zipmapDecodeLength(zm);
 326         *key += (*klen < ZIPMAP_BIGLEN) ? 1 : sizeof(unsigned int);
 327     }
 328     zm += zipmapRawKeyLength(zm);
 329     if (value) {
 330         *value = zm+1;
 331         *vlen = zipmapDecodeLength(zm);
 332         *value += (*vlen < ZIPMAP_BIGLEN) ? 1 : sizeof(unsigned int);
 333     }
 334     zm += zipmapRawValueLength(zm);
 335     return zm;
 336 }
 337
 338 void zipmapRepr(unsigned char *p) {
 339     unsigned int l;
 340
 341     printf("{status %u}",*p++);
 342     while(1) {
 343         if (p[0] == ZIPMAP_END) {
 344             printf("{end}");
 345             break;
 346         } else if (p[0] == ZIPMAP_EMPTY) {
 347             l = zipmapDecodeLength(p+1);
 348             printf("{%u empty block}", l);
 349             p += l;
 350         } else {
 351             unsigned char e;
 352
 353             l = zipmapDecodeLength(p);
 354             printf("{key %u}",l);
 355             p += zipmapEncodeLength(NULL,l);
 356             fwrite(p,l,1,stdout);
 357             p += l;
 358
 359             l = zipmapDecodeLength(p);
 360             printf("{value %u}",l);
 361             p += zipmapEncodeLength(NULL,l);
 362             e = *p++;
 363             fwrite(p,l,1,stdout);
 364             p += l+e;
 365             if (e) {
 366                 printf("[");
 367                 while(e--) printf(".");
 368                 printf("]");
 369             }
 370         }
 371     }
 372     printf("\n");
 373 }
 374
 375 int main(void) {
 376     unsigned char *zm;
 377
 378     zm = zipmapNew();
 379     zm = zipmapSet(zm,(unsigned char*) "hello",5, (unsigned char*) "world!",6);
 380     zm = zipmapSet(zm,(unsigned char*) "foo",3, (unsigned char*) "bar",3);
 381     zm = zipmapSet(zm,(unsigned char*) "foo",3, (unsigned char*) "!",1);
 382     zipmapRepr(zm);
 383     zm = zipmapSet(zm,(unsigned char*) "foo",3, (unsigned char*) "12345",5);
 384     zipmapRepr(zm);
 385     zm = zipmapSet(zm,(unsigned char*) "new",3, (unsigned char*) "xx",2);
 386     zipmapRepr(zm);
 387     zm = zipmapDel(zm,(unsigned char*) "new",3,NULL);
 388     zipmapRepr(zm);
 389     printf("Iterate trought elements:\n");
 390     {
 391         unsigned char *i = zm+1;
 392         unsigned char *key, *value;
 393         unsigned int klen, vlen;
 394
 395         while((i = zipmapNext(i,&key,&klen,&value,&vlen)) != NULL) {
 396             printf("%d:%.*s => %d:%.*s\n", klen, klen, key, vlen, vlen, value);
 397         }
 398     }
 399     return 0;
 400 }