]> git.saurik.com Git - redis.git/blame_incremental - src/zipmap.c
Fix (cosmetic) typos in dict.h
[redis.git] / src / zipmap.c
... / ...
CommitLineData
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 of 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 after the string, resulting
60 * from modification of values associated to a key. For instance if "foo"
61 * is set to "bar", and later "foo" will be set to "hi", it will have a
62 * free byte to use if the value will enlarge again later, or even in
63 * 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 "endianconv.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. */
98unsigned 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' */
107static 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. */
118static 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. */
140static 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
170static 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) */
180static 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) */
187static 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). */
199static unsigned int zipmapRawEntryLength(unsigned char *p) {
200 unsigned int l = zipmapRawKeyLength(p);
201 return l + zipmapRawValueLength(p+l);
202}
203
204static 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. */
213unsigned 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. */
283unsigned 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 before iterating through elements via zipmapNext() */
302unsigned 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 */
317unsigned 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. */
336int 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. */
347int 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 */
352unsigned 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. */
369size_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
376void 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
409int 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 through 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