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;
 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 /* Set key to value, creating the key if it does not already exist. */
 214 unsigned char *zipmapSet(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned char *val, unsigned int vlen) {
 215     unsigned int oldlen = 0, freeoff = 0, freelen;
 216     unsigned int reqlen = zipmapRequiredLength(klen,vlen);
 217     unsigned int empty, vempty;
 218     unsigned char *p;
 219
 220     freelen = reqlen;
 221     p = zipmapLookupRaw(zm,key,klen,&oldlen,&freeoff,&freelen);
 222     if (p == NULL && freelen == 0) {
 223         printf("HERE oldlen:%u required:%u\n",oldlen,reqlen);
 224         /* Key not found, and not space for the new key. Enlarge */
 225         zm = zrealloc(zm,oldlen+reqlen);
 226         p = zm+oldlen-1;
 227         zm[oldlen+reqlen-1] = ZIPMAP_END;
 228         freelen = reqlen;
 229         printf("New total length is: %u\n", oldlen+reqlen);
 230     } else if (p == NULL) {
 231         /* Key not found, but there is enough free space. */
 232         p = zm+freeoff;
 233         /* note: freelen is already set in this case */
 234     } else {
 235         unsigned char *b = p;
 236
 237         /* Key found. Is there enough space for the new value? */
 238         /* Compute the total length: */
 239         freelen = zipmapRawKeyLength(b);
 240         b += freelen;
 241         freelen += zipmapRawValueLength(b);
 242         if (freelen < reqlen) {
 243             /* Mark this entry as free and recurse */
 244             p[0] = ZIPMAP_EMPTY;
 245             zipmapEncodeLength(p+1,freelen);
 246             zm[0] |= ZIPMAP_STATUS_FRAGMENTED;
 247             return zipmapSet(zm,key,klen,val,vlen);
 248         }
 249     }
 250
 251     /* Ok we have a suitable block where to write the new key/value
 252      * entry. */
 253     empty = freelen-reqlen;
 254     /* If there is too much free space mark it as a free block instead
 255      * of adding it as trailing empty space for the value, as we want
 256      * zipmaps to be very space efficient. */
 257     if (empty > ZIPMAP_VALUE_MAX_FREE) {
 258         unsigned char *e;
 259
 260         e = p+reqlen;
 261         e[0] = ZIPMAP_EMPTY;
 262         zipmapEncodeLength(e+1,empty);
 263         vempty = 0;
 264         zm[0] |= ZIPMAP_STATUS_FRAGMENTED;
 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 void zipmapRepr(unsigned char *p) {
 282     unsigned int l;
 283
 284     printf("{status %u}",*p++);
 285     while(1) {
 286         if (p[0] == ZIPMAP_END) {
 287             printf("{end}");
 288             break;
 289         } else if (p[0] == ZIPMAP_EMPTY) {
 290             l = zipmapDecodeLength(p+1);
 291             printf("{%u empty block}", l);
 292             p += l;
 293         } else {
 294             unsigned char e;
 295
 296             l = zipmapDecodeLength(p);
 297             printf("{key %u}",l);
 298             p += zipmapEncodeLength(NULL,l);
 299             fwrite(p,l,1,stdout);
 300             p += l;
 301
 302             l = zipmapDecodeLength(p);
 303             printf("{value %u}",l);
 304             p += zipmapEncodeLength(NULL,l);
 305             e = *p++;
 306             fwrite(p,l,1,stdout);
 307             p += l+e;
 308             if (e) {
 309                 printf("[");
 310                 while(e--) printf(".");
 311                 printf("]");
 312             }
 313         }
 314     }
 315     printf("\n");
 316 }
 317
 318 int main(void) {
 319     unsigned char *zm;
 320
 321     zm = zipmapNew();
 322     zm = zipmapSet(zm,(unsigned char*) "hello",5, (unsigned char*) "world!",6);
 323     zm = zipmapSet(zm,(unsigned char*) "foo",3, (unsigned char*) "bar",3);
 324     zm = zipmapSet(zm,(unsigned char*) "foo",3, (unsigned char*) "!",1);
 325     zipmapRepr(zm);
 326     zm = zipmapSet(zm,(unsigned char*) "foo",3, (unsigned char*) "12345",5);
 327     zipmapRepr(zm);
 328     zm = zipmapSet(zm,(unsigned char*) "new",3, (unsigned char*) "xx",2);
 329     zipmapRepr(zm);
 330     return 0;
 331 }