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 a 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 * 253, it's a single-byte length. If it is 254 then a four bytes unsigned
55 * integer follows (in the host byte ordering). A value of 255 is used to
56 * signal the end of the hash.
57 *
58 * <free> is the number of free unused bytes after the string, resulting
59 * from modification of values associated to a key. For instance if "foo"
60 * is set to "bar", and later "foo" will be set to "hi", it will have a
61 * free byte to use if the value will enlarge again later, or even in
62 * 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, the zipmap will be
66 * reallocated to make sure it is as small as possible.
67 *
68 * The most compact representation of the above two elements hash is actually:
69 *
70 * "\x02\x03foo\x03\x00bar\x05hello\x05\x00world\xff"
71 *
72 * Note that because keys and values are prefixed length "objects",
73 * the lookup will take O(N) where N is the number of elements
74 * in the zipmap and *not* the number of bytes needed to represent the zipmap.
75 * This lowers the constant times considerably.
76 */
77
78#include <stdio.h>
79#include <string.h>
80#include "zmalloc.h"
81#include "endianconv.h"
82
83#define ZIPMAP_BIGLEN 254
84#define ZIPMAP_END 255
85
86/* The following defines the max value for the <free> field described in the
87 * comments above, that is, the max number of trailing bytes in a value. */
88#define ZIPMAP_VALUE_MAX_FREE 4
89
90/* The following macro returns the number of bytes needed to encode the length
91 * for the integer value _l, that is, 1 byte for lengths < ZIPMAP_BIGLEN and
92 * 5 bytes for all the other lengths. */
93#define ZIPMAP_LEN_BYTES(_l) (((_l) < ZIPMAP_BIGLEN) ? 1 : sizeof(unsigned int)+1)
94
95/* Create a new empty zipmap. */
96unsigned char *zipmapNew(void) {
97 unsigned char *zm = zmalloc(2);
98
99 zm[0] = 0; /* Length */
100 zm[1] = ZIPMAP_END;
101 return zm;
102}
103
104/* Decode the encoded length pointed by 'p' */
105static unsigned int zipmapDecodeLength(unsigned char *p) {
106 unsigned int len = *p;
107
108 if (len < ZIPMAP_BIGLEN) return len;
109 memcpy(&len,p+1,sizeof(unsigned int));
110 memrev32ifbe(&len);
111 return len;
112}
113
114static unsigned int zipmapGetEncodedLengthSize(unsigned char *p) {
115 return (*p < ZIPMAP_BIGLEN) ? 1: 5;
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. */
120static unsigned int zipmapEncodeLength(unsigned char *p, unsigned int len) {
121 if (p == NULL) {
122 return ZIPMAP_LEN_BYTES(len);
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 memrev32ifbe(p+1);
131 return 1+sizeof(len);
132 }
133 }
134}
135
136/* Search for a matching key, returning a pointer to the entry inside the
137 * zipmap. Returns NULL if the key is not found.
138 *
139 * If NULL is returned, and totlen is not NULL, it is set to the entire
140 * size of the zipmap, so that the calling function will be able to
141 * reallocate the original zipmap to make room for more entries. */
142static unsigned char *zipmapLookupRaw(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned int *totlen) {
143 unsigned char *p = zm+1, *k = NULL;
144 unsigned int l,llen;
145
146 while(*p != ZIPMAP_END) {
147 unsigned char free;
148
149 /* Match or skip the key */
150 l = zipmapDecodeLength(p);
151 llen = zipmapEncodeLength(NULL,l);
152 if (key != NULL && k == NULL && l == klen && !memcmp(p+llen,key,l)) {
153 /* Only return when the user doesn't care
154 * for the total length of the zipmap. */
155 if (totlen != NULL) {
156 k = p;
157 } else {
158 return p;
159 }
160 }
161 p += llen+l;
162 /* Skip the value as well */
163 l = zipmapDecodeLength(p);
164 p += zipmapEncodeLength(NULL,l);
165 free = p[0];
166 p += l+1+free; /* +1 to skip the free byte */
167 }
168 if (totlen != NULL) *totlen = (unsigned int)(p-zm)+1;
169 return k;
170}
171
172static unsigned long zipmapRequiredLength(unsigned int klen, unsigned int vlen) {
173 unsigned int l;
174
175 l = klen+vlen+3;
176 if (klen >= ZIPMAP_BIGLEN) l += 4;
177 if (vlen >= ZIPMAP_BIGLEN) l += 4;
178 return l;
179}
180
181/* Return the total amount used by a key (encoded length + payload) */
182static unsigned int zipmapRawKeyLength(unsigned char *p) {
183 unsigned int l = zipmapDecodeLength(p);
184 return zipmapEncodeLength(NULL,l) + l;
185}
186
187/* Return the total amount used by a value
188 * (encoded length + single byte free count + payload) */
189static unsigned int zipmapRawValueLength(unsigned char *p) {
190 unsigned int l = zipmapDecodeLength(p);
191 unsigned int used;
192
193 used = zipmapEncodeLength(NULL,l);
194 used += p[used] + 1 + l;
195 return used;
196}
197
198/* If 'p' points to a key, this function returns the total amount of
199 * bytes used to store this entry (entry = key + associated value + trailing
200 * free space if any). */
201static unsigned int zipmapRawEntryLength(unsigned char *p) {
202 unsigned int l = zipmapRawKeyLength(p);
203 return l + zipmapRawValueLength(p+l);
204}
205
206static inline unsigned char *zipmapResize(unsigned char *zm, unsigned int len) {
207 zm = zrealloc(zm, len);
208 zm[len-1] = ZIPMAP_END;
209 return zm;
210}
211
212/* Set key to value, creating the key if it does not already exist.
213 * If 'update' is not NULL, *update is set to 1 if the key was
214 * already preset, otherwise to 0. */
215unsigned char *zipmapSet(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned char *val, unsigned int vlen, int *update) {
216 unsigned int zmlen, offset;
217 unsigned int freelen, reqlen = zipmapRequiredLength(klen,vlen);
218 unsigned int empty, vempty;
219 unsigned char *p;
220
221 freelen = reqlen;
222 if (update) *update = 0;
223 p = zipmapLookupRaw(zm,key,klen,&zmlen);
224 if (p == NULL) {
225 /* Key not found: enlarge */
226 zm = zipmapResize(zm, zmlen+reqlen);
227 p = zm+zmlen-1;
228 zmlen = zmlen+reqlen;
229
230 /* Increase zipmap length (this is an insert) */
231 if (zm[0] < ZIPMAP_BIGLEN) zm[0]++;
232 } else {
233 /* Key found. Is there enough space for the new value? */
234 /* Compute the total length: */
235 if (update) *update = 1;
236 freelen = zipmapRawEntryLength(p);
237 if (freelen < reqlen) {
238 /* Store the offset of this key within the current zipmap, so
239 * it can be resized. Then, move the tail backwards so this
240 * pair fits at the current position. */
241 offset = p-zm;
242 zm = zipmapResize(zm, zmlen-freelen+reqlen);
243 p = zm+offset;
244
245 /* The +1 in the number of bytes to be moved is caused by the
246 * end-of-zipmap byte. Note: the *original* zmlen is used. */
247 memmove(p+reqlen, p+freelen, zmlen-(offset+freelen+1));
248 zmlen = zmlen-freelen+reqlen;
249 freelen = reqlen;
250 }
251 }
252
253 /* We now have a suitable block where the key/value entry can
254 * be written. If there is too much free space, move the tail
255 * of the zipmap a few bytes to the front and shrink the zipmap,
256 * as we want zipmaps to be very space efficient. */
257 empty = freelen-reqlen;
258 if (empty >= ZIPMAP_VALUE_MAX_FREE) {
259 /* First, move the tail <empty> bytes to the front, then resize
260 * the zipmap to be <empty> bytes smaller. */
261 offset = p-zm;
262 memmove(p+reqlen, p+freelen, zmlen-(offset+freelen+1));
263 zmlen -= empty;
264 zm = zipmapResize(zm, zmlen);
265 p = zm+offset;
266 vempty = 0;
267 } else {
268 vempty = empty;
269 }
270
271 /* Just write the key + value and we are done. */
272 /* Key: */
273 p += zipmapEncodeLength(p,klen);
274 memcpy(p,key,klen);
275 p += klen;
276 /* Value: */
277 p += zipmapEncodeLength(p,vlen);
278 *p++ = vempty;
279 memcpy(p,val,vlen);
280 return zm;
281}
282
283/* Remove the specified key. If 'deleted' is not NULL the pointed integer is
284 * set to 0 if the key was not found, to 1 if it was found and deleted. */
285unsigned char *zipmapDel(unsigned char *zm, unsigned char *key, unsigned int klen, int *deleted) {
286 unsigned int zmlen, freelen;
287 unsigned char *p = zipmapLookupRaw(zm,key,klen,&zmlen);
288 if (p) {
289 freelen = zipmapRawEntryLength(p);
290 memmove(p, p+freelen, zmlen-((p-zm)+freelen+1));
291 zm = zipmapResize(zm, zmlen-freelen);
292
293 /* Decrease zipmap length */
294 if (zm[0] < ZIPMAP_BIGLEN) zm[0]--;
295
296 if (deleted) *deleted = 1;
297 } else {
298 if (deleted) *deleted = 0;
299 }
300 return zm;
301}
302
303/* Call before iterating through elements via zipmapNext() */
304unsigned char *zipmapRewind(unsigned char *zm) {
305 return zm+1;
306}
307
308/* This function is used to iterate through all the zipmap elements.
309 * In the first call the first argument is the pointer to the zipmap + 1.
310 * In the next calls what zipmapNext returns is used as first argument.
311 * Example:
312 *
313 * unsigned char *i = zipmapRewind(my_zipmap);
314 * while((i = zipmapNext(i,&key,&klen,&value,&vlen)) != NULL) {
315 * printf("%d bytes key at $p\n", klen, key);
316 * printf("%d bytes value at $p\n", vlen, value);
317 * }
318 */
319unsigned char *zipmapNext(unsigned char *zm, unsigned char **key, unsigned int *klen, unsigned char **value, unsigned int *vlen) {
320 if (zm[0] == ZIPMAP_END) return NULL;
321 if (key) {
322 *key = zm;
323 *klen = zipmapDecodeLength(zm);
324 *key += ZIPMAP_LEN_BYTES(*klen);
325 }
326 zm += zipmapRawKeyLength(zm);
327 if (value) {
328 *value = zm+1;
329 *vlen = zipmapDecodeLength(zm);
330 *value += ZIPMAP_LEN_BYTES(*vlen);
331 }
332 zm += zipmapRawValueLength(zm);
333 return zm;
334}
335
336/* Search a key and retrieve the pointer and len of the associated value.
337 * If the key is found the function returns 1, otherwise 0. */
338int zipmapGet(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned char **value, unsigned int *vlen) {
339 unsigned char *p;
340
341 if ((p = zipmapLookupRaw(zm,key,klen,NULL)) == NULL) return 0;
342 p += zipmapRawKeyLength(p);
343 *vlen = zipmapDecodeLength(p);
344 *value = p + ZIPMAP_LEN_BYTES(*vlen) + 1;
345 return 1;
346}
347
348/* Return 1 if the key exists, otherwise 0 is returned. */
349int zipmapExists(unsigned char *zm, unsigned char *key, unsigned int klen) {
350 return zipmapLookupRaw(zm,key,klen,NULL) != NULL;
351}
352
353/* Return the number of entries inside a zipmap */
354unsigned int zipmapLen(unsigned char *zm) {
355 unsigned int len = 0;
356 if (zm[0] < ZIPMAP_BIGLEN) {
357 len = zm[0];
358 } else {
359 unsigned char *p = zipmapRewind(zm);
360 while((p = zipmapNext(p,NULL,NULL,NULL,NULL)) != NULL) len++;
361
362 /* Re-store length if small enough */
363 if (len < ZIPMAP_BIGLEN) zm[0] = len;
364 }
365 return len;
366}
367
368/* Return the raw size in bytes of a zipmap, so that we can serialize
369 * the zipmap on disk (or everywhere is needed) just writing the returned
370 * amount of bytes of the C array starting at the zipmap pointer. */
371size_t zipmapBlobLen(unsigned char *zm) {
372 unsigned int totlen;
373 zipmapLookupRaw(zm,NULL,0,&totlen);
374 return totlen;
375}
376
377/* Validate the integrity of the data structure.
378 * when `deep` is 0, only the integrity of the header is validated.
379 * when `deep` is 1, we scan all the entries one by one. */
380int zipmapValidateIntegrity(unsigned char *zm, size_t size, int deep) {
381#define OUT_OF_RANGE(p) ( \
382 (p) < zm + 2 || \
383 (p) > zm + size - 1)
384 unsigned int l, s, e;
385
386 /* check that we can actually read the header (or ZIPMAP_END). */
387 if (size < 2)
388 return 0;
389
390 /* the last byte must be the terminator. */
391 if (zm[size-1] != ZIPMAP_END)
392 return 0;
393
394 if (!deep)
395 return 1;
396
397 unsigned int count = 0;
398 unsigned char *p = zm + 1; /* skip the count */
399 while(*p != ZIPMAP_END) {
400 /* read the field name length encoding type */
401 s = zipmapGetEncodedLengthSize(p);
402 /* make sure the entry length doesn't reach outside the edge of the zipmap */
403 if (OUT_OF_RANGE(p+s))
404 return 0;
405
406 /* read the field name length */
407 l = zipmapDecodeLength(p);
408 p += s; /* skip the encoded field size */
409 p += l; /* skip the field */
410
411 /* make sure the entry doesn't reach outside the edge of the zipmap */
412 if (OUT_OF_RANGE(p))
413 return 0;
414
415 /* read the value length encoding type */
416 s = zipmapGetEncodedLengthSize(p);
417 /* make sure the entry length doesn't reach outside the edge of the zipmap */
418 if (OUT_OF_RANGE(p+s))
419 return 0;
420
421 /* read the value length */
422 l = zipmapDecodeLength(p);
423 p += s; /* skip the encoded value size*/
424 e = *p++; /* skip the encoded free space (always encoded in one byte) */
425 p += l+e; /* skip the value and free space */
426 count++;
427
428 /* make sure the entry doesn't reach outside the edge of the zipmap */
429 if (OUT_OF_RANGE(p))
430 return 0;
431 }
432
433 /* check that the zipmap is not empty. */
434 if (count == 0) return 0;
435
436 /* check that the count in the header is correct */
437 if (zm[0] != ZIPMAP_BIGLEN && zm[0] != count)
438 return 0;
439
440 return 1;
441#undef OUT_OF_RANGE
442}
443
444#ifdef REDIS_TEST
445static void zipmapRepr(unsigned char *p) {
446 unsigned int l;
447
448 printf("{status %u}",*p++);
449 while(1) {
450 if (p[0] == ZIPMAP_END) {
451 printf("{end}");
452 break;
453 } else {
454 unsigned char e;
455
456 l = zipmapDecodeLength(p);
457 printf("{key %u}",l);
458 p += zipmapEncodeLength(NULL,l);
459 if (l != 0 && fwrite(p,l,1,stdout) == 0) perror("fwrite");
460 p += l;
461
462 l = zipmapDecodeLength(p);
463 printf("{value %u}",l);
464 p += zipmapEncodeLength(NULL,l);
465 e = *p++;
466 if (l != 0 && fwrite(p,l,1,stdout) == 0) perror("fwrite");
467 p += l+e;
468 if (e) {
469 printf("[");
470 while(e--) printf(".");
471 printf("]");
472 }
473 }
474 }
475 printf("\n");
476}
477
478#define UNUSED(x) (void)(x)
479int zipmapTest(int argc, char *argv[], int flags) {
480 unsigned char *zm;
481
482 UNUSED(argc);
483 UNUSED(argv);
484 UNUSED(flags);
485
486 zm = zipmapNew();
487
488 zm = zipmapSet(zm,(unsigned char*) "name",4, (unsigned char*) "foo",3,NULL);
489 zm = zipmapSet(zm,(unsigned char*) "surname",7, (unsigned char*) "foo",3,NULL);
490 zm = zipmapSet(zm,(unsigned char*) "age",3, (unsigned char*) "foo",3,NULL);
491 zipmapRepr(zm);
492
493 zm = zipmapSet(zm,(unsigned char*) "hello",5, (unsigned char*) "world!",6,NULL);
494 zm = zipmapSet(zm,(unsigned char*) "foo",3, (unsigned char*) "bar",3,NULL);
495 zm = zipmapSet(zm,(unsigned char*) "foo",3, (unsigned char*) "!",1,NULL);
496 zipmapRepr(zm);
497 zm = zipmapSet(zm,(unsigned char*) "foo",3, (unsigned char*) "12345",5,NULL);
498 zipmapRepr(zm);
499 zm = zipmapSet(zm,(unsigned char*) "new",3, (unsigned char*) "xx",2,NULL);
500 zm = zipmapSet(zm,(unsigned char*) "noval",5, (unsigned char*) "",0,NULL);
501 zipmapRepr(zm);
502 zm = zipmapDel(zm,(unsigned char*) "new",3,NULL);
503 zipmapRepr(zm);
504
505 printf("\nLook up large key:\n");
506 {
507 unsigned char buf[512];
508 unsigned char *value;
509 unsigned int vlen, i;
510 for (i = 0; i < 512; i++) buf[i] = 'a';
511
512 zm = zipmapSet(zm,buf,512,(unsigned char*) "long",4,NULL);
513 if (zipmapGet(zm,buf,512,&value,&vlen)) {
514 printf(" <long key> is associated to the %d bytes value: %.*s\n",
515 vlen, vlen, value);
516 }
517 }
518
519 printf("\nPerform a direct lookup:\n");
520 {
521 unsigned char *value;
522 unsigned int vlen;
523
524 if (zipmapGet(zm,(unsigned char*) "foo",3,&value,&vlen)) {
525 printf(" foo is associated to the %d bytes value: %.*s\n",
526 vlen, vlen, value);
527 }
528 }
529 printf("\nIterate through elements:\n");
530 {
531 unsigned char *i = zipmapRewind(zm);
532 unsigned char *key, *value;
533 unsigned int klen, vlen;
534
535 while((i = zipmapNext(i,&key,&klen,&value,&vlen)) != NULL) {
536 printf(" %d:%.*s => %d:%.*s\n", klen, klen, key, vlen, vlen, value);
537 }
538 }
539 zfree(zm);
540 return 0;
541}
542#endif
543