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 "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. */
98 0 : unsigned char *zipmapNew(void) {
99 0 : unsigned char *zm = zmalloc(2);
100 :
101 0 : zm[0] = 0; /* Length */
102 0 : zm[1] = ZIPMAP_END;
103 0 : return zm;
104 : }
105 :
106 : /* Decode the encoded length pointed by 'p' */
107 24 : static unsigned int zipmapDecodeLength(unsigned char *p) {
108 24 : unsigned int len = *p;
109 :
110 24 : if (len < ZIPMAP_BIGLEN) return len;
111 0 : memcpy(&len,p+1,sizeof(unsigned int));
112 : memrev32ifbe(&len);
113 0 : 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 12 : static unsigned int zipmapEncodeLength(unsigned char *p, unsigned int len) {
119 12 : if (p == NULL) {
120 12 : return ZIPMAP_LEN_BYTES(len);
121 : } else {
122 0 : if (len < ZIPMAP_BIGLEN) {
123 0 : p[0] = len;
124 0 : return 1;
125 : } else {
126 0 : p[0] = ZIPMAP_BIGLEN;
127 0 : memcpy(p+1,&len,sizeof(len));
128 : memrev32ifbe(p+1);
129 0 : 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 0 : static unsigned char *zipmapLookupRaw(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned int *totlen) {
141 0 : unsigned char *p = zm+1, *k = NULL;
142 : unsigned int l,llen;
143 :
144 0 : while(*p != ZIPMAP_END) {
145 : unsigned char free;
146 :
147 : /* Match or skip the key */
148 0 : l = zipmapDecodeLength(p);
149 0 : llen = zipmapEncodeLength(NULL,l);
150 0 : 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 0 : if (totlen != NULL) {
154 0 : k = p;
155 : } else {
156 0 : return p;
157 : }
158 : }
159 0 : p += llen+l;
160 : /* Skip the value as well */
161 0 : l = zipmapDecodeLength(p);
162 0 : p += zipmapEncodeLength(NULL,l);
163 0 : free = p[0];
164 0 : p += l+1+free; /* +1 to skip the free byte */
165 : }
166 0 : if (totlen != NULL) *totlen = (unsigned int)(p-zm)+1;
167 0 : return k;
168 : }
169 :
170 : static unsigned long zipmapRequiredLength(unsigned int klen, unsigned int vlen) {
171 : unsigned int l;
172 :
173 0 : l = klen+vlen+3;
174 0 : if (klen >= ZIPMAP_BIGLEN) l += 4;
175 0 : if (vlen >= ZIPMAP_BIGLEN) l += 4;
176 0 : return l;
177 : }
178 :
179 : /* Return the total amount used by a key (encoded length + payload) */
180 6 : static unsigned int zipmapRawKeyLength(unsigned char *p) {
181 6 : unsigned int l = zipmapDecodeLength(p);
182 6 : 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 6 : static unsigned int zipmapRawValueLength(unsigned char *p) {
188 6 : unsigned int l = zipmapDecodeLength(p);
189 : unsigned int used;
190 :
191 6 : used = zipmapEncodeLength(NULL,l);
192 6 : used += p[used] + 1 + l;
193 6 : 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 0 : static unsigned int zipmapRawEntryLength(unsigned char *p) {
200 0 : unsigned int l = zipmapRawKeyLength(p);
201 0 : return l + zipmapRawValueLength(p+l);
202 : }
203 :
204 : static inline unsigned char *zipmapResize(unsigned char *zm, unsigned int len) {
205 0 : zm = zrealloc(zm, len);
206 0 : zm[len-1] = ZIPMAP_END;
207 0 : 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 0 : 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 0 : unsigned int freelen, reqlen = zipmapRequiredLength(klen,vlen);
216 : unsigned int empty, vempty;
217 : unsigned char *p;
218 :
219 0 : freelen = reqlen;
220 0 : if (update) *update = 0;
221 0 : p = zipmapLookupRaw(zm,key,klen,&zmlen);
222 0 : if (p == NULL) {
223 : /* Key not found: enlarge */
224 0 : zm = zipmapResize(zm, zmlen+reqlen);
225 0 : p = zm+zmlen-1;
226 0 : zmlen = zmlen+reqlen;
227 :
228 : /* Increase zipmap length (this is an insert) */
229 0 : 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 0 : if (update) *update = 1;
234 0 : freelen = zipmapRawEntryLength(p);
235 0 : 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 0 : offset = p-zm;
240 0 : zm = zipmapResize(zm, zmlen-freelen+reqlen);
241 0 : 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 0 : memmove(p+reqlen, p+freelen, zmlen-(offset+freelen+1));
246 0 : zmlen = zmlen-freelen+reqlen;
247 0 : 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 0 : empty = freelen-reqlen;
256 0 : 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 0 : offset = p-zm;
260 0 : memmove(p+reqlen, p+freelen, zmlen-(offset+freelen+1));
261 0 : zmlen -= empty;
262 0 : zm = zipmapResize(zm, zmlen);
263 0 : p = zm+offset;
264 0 : vempty = 0;
265 : } else {
266 0 : vempty = empty;
267 : }
268 :
269 : /* Just write the key + value and we are done. */
270 : /* Key: */
271 0 : p += zipmapEncodeLength(p,klen);
272 0 : memcpy(p,key,klen);
273 0 : p += klen;
274 : /* Value: */
275 0 : p += zipmapEncodeLength(p,vlen);
276 0 : *p++ = vempty;
277 0 : memcpy(p,val,vlen);
278 0 : 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 0 : unsigned char *zipmapDel(unsigned char *zm, unsigned char *key, unsigned int klen, int *deleted) {
284 : unsigned int zmlen, freelen;
285 0 : unsigned char *p = zipmapLookupRaw(zm,key,klen,&zmlen);
286 0 : if (p) {
287 0 : freelen = zipmapRawEntryLength(p);
288 0 : memmove(p, p+freelen, zmlen-((p-zm)+freelen+1));
289 0 : zm = zipmapResize(zm, zmlen-freelen);
290 :
291 : /* Decrease zipmap length */
292 0 : if (zm[0] < ZIPMAP_BIGLEN) zm[0]--;
293 :
294 0 : if (deleted) *deleted = 1;
295 : } else {
296 0 : if (deleted) *deleted = 0;
297 : }
298 0 : return zm;
299 : }
300 :
301 : /* Call before iterating through elements via zipmapNext() */
302 3 : unsigned char *zipmapRewind(unsigned char *zm) {
303 3 : 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 9 : unsigned char *zipmapNext(unsigned char *zm, unsigned char **key, unsigned int *klen, unsigned char **value, unsigned int *vlen) {
318 9 : if (zm[0] == ZIPMAP_END) return NULL;
319 6 : if (key) {
320 6 : *key = zm;
321 6 : *klen = zipmapDecodeLength(zm);
322 6 : *key += ZIPMAP_LEN_BYTES(*klen);
323 : }
324 6 : zm += zipmapRawKeyLength(zm);
325 6 : if (value) {
326 6 : *value = zm+1;
327 6 : *vlen = zipmapDecodeLength(zm);
328 6 : *value += ZIPMAP_LEN_BYTES(*vlen);
329 : }
330 6 : zm += zipmapRawValueLength(zm);
331 6 : 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 0 : int zipmapGet(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned char **value, unsigned int *vlen) {
337 : unsigned char *p;
338 :
339 0 : if ((p = zipmapLookupRaw(zm,key,klen,NULL)) == NULL) return 0;
340 0 : p += zipmapRawKeyLength(p);
341 0 : *vlen = zipmapDecodeLength(p);
342 0 : *value = p + ZIPMAP_LEN_BYTES(*vlen) + 1;
343 0 : return 1;
344 : }
345 :
346 : /* Return 1 if the key exists, otherwise 0 is returned. */
347 0 : int zipmapExists(unsigned char *zm, unsigned char *key, unsigned int klen) {
348 0 : return zipmapLookupRaw(zm,key,klen,NULL) != NULL;
349 : }
350 :
351 : /* Return the number of entries inside a zipmap */
352 0 : unsigned int zipmapLen(unsigned char *zm) {
353 0 : unsigned int len = 0;
354 0 : if (zm[0] < ZIPMAP_BIGLEN) {
355 0 : len = zm[0];
356 : } else {
357 0 : unsigned char *p = zipmapRewind(zm);
358 0 : while((p = zipmapNext(p,NULL,NULL,NULL,NULL)) != NULL) len++;
359 :
360 : /* Re-store length if small enough */
361 0 : if (len < ZIPMAP_BIGLEN) zm[0] = len;
362 : }
363 0 : 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 0 : size_t zipmapBlobLen(unsigned char *zm) {
370 : unsigned int totlen;
371 0 : zipmapLookupRaw(zm,NULL,0,&totlen);
372 0 : 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 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
|
