| 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 |