X-Git-Url: https://git.saurik.com/redis.git/blobdiff_plain/eb46f4bd7bf086089b0a48f1e2bed2aadb46d185..b3f83f127273da21506f697e256ae010587b10f1:/zipmap.c diff --git a/zipmap.c b/zipmap.c index ba5ea0e3..f45ef0dd 100644 --- a/zipmap.c +++ b/zipmap.c @@ -67,14 +67,14 @@ * * The most compact representation of the above two elements hash is actually: * - * "\x00\x03\x00foo\x03\x00bar\x05\x00hello\x05\x00world\xff" + * "\x00\x03foo\x03\x00bar\x05hello\x05\x00world\xff" * * Empty space is marked using a 254 bytes + a (coded as already * specified). The length includes the 254 bytes in the count and the * space taken by the field. So for instance removing the "foo" key * from the zipmap above will lead to the following representation: * - * "\xfd\x10........\x05\x00hello\x05\x00world\xff" + * "\x00\xfd\x10........\x05hello\x05\x00world\xff" * * Note that because empty space, keys, values, are all prefixed length * "objects", the lookup will take O(N) where N is the numeber of elements @@ -97,6 +97,11 @@ * comments above, that is, the max number of trailing bytes in a value. */ #define ZIPMAP_VALUE_MAX_FREE 5 +/* The following macro returns the number of bytes needed to encode the length + * for the integer value _l, that is, 1 byte for lengths < ZIPMAP_BIGLEN and + * 5 bytes for all the other lengths. */ +#define ZIPMAP_LEN_BYTES(_l) (((_l) < ZIPMAP_BIGLEN) ? 1 : sizeof(unsigned int)+1) + /* Create a new empty zipmap. */ unsigned char *zipmapNew(void) { unsigned char *zm = zmalloc(2); @@ -111,7 +116,7 @@ static unsigned int zipmapDecodeLength(unsigned char *p) { unsigned int len = *p; if (len < ZIPMAP_BIGLEN) return len; - memcpy(&len,p,sizeof(unsigned int)); + memcpy(&len,p+1,sizeof(unsigned int)); return len; } @@ -119,7 +124,7 @@ static unsigned int zipmapDecodeLength(unsigned char *p) { * the amount of bytes required to encode such a length. */ static unsigned int zipmapEncodeLength(unsigned char *p, unsigned int len) { if (p == NULL) { - return (len < ZIPMAP_BIGLEN) ? 1 : 1+sizeof(unsigned int); + return ZIPMAP_LEN_BYTES(len); } else { if (len < ZIPMAP_BIGLEN) { p[0] = len; @@ -147,7 +152,7 @@ static unsigned int zipmapEncodeLength(unsigned char *p, unsigned int len) { static unsigned char *zipmapLookupRaw(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned int *totlen, unsigned int *freeoff, unsigned int *freelen) { unsigned char *p = zm+1; unsigned int l; - unsigned int reqfreelen; + unsigned int reqfreelen = 0; /* initialized just to prevent warning */ if (freelen) { reqfreelen = *freelen; @@ -192,14 +197,14 @@ static unsigned long zipmapRequiredLength(unsigned int klen, unsigned int vlen) return l; } -/* Return the total amonut used by a key (encoded length + payload) */ +/* Return the total amount used by a key (encoded length + payload) */ static unsigned int zipmapRawKeyLength(unsigned char *p) { unsigned int l = zipmapDecodeLength(p); return zipmapEncodeLength(NULL,l) + l; } -/* Return the total amonut used by a value +/* Return the total amount used by a value * (encoded length + single byte free count + payload) */ static unsigned int zipmapRawValueLength(unsigned char *p) { unsigned int l = zipmapDecodeLength(p); @@ -210,23 +215,33 @@ static unsigned int zipmapRawValueLength(unsigned char *p) { return used; } -/* Set key to value, creating the key if it does not already exist. */ -unsigned char *zipmapSet(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned char *val, unsigned int vlen) { +/* If 'p' points to a key, this function returns the total amount of + * bytes used to store this entry (entry = key + associated value + trailing + * free space if any). */ +static unsigned int zipmapRawEntryLength(unsigned char *p) { + unsigned int l = zipmapRawKeyLength(p); + + return l + zipmapRawValueLength(p+l); +} + +/* Set key to value, creating the key if it does not already exist. + * If 'update' is not NULL, *update is set to 1 if the key was + * already preset, otherwise to 0. */ +unsigned char *zipmapSet(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned char *val, unsigned int vlen, int *update) { unsigned int oldlen = 0, freeoff = 0, freelen; unsigned int reqlen = zipmapRequiredLength(klen,vlen); unsigned int empty, vempty; unsigned char *p; freelen = reqlen; + if (update) *update = 0; p = zipmapLookupRaw(zm,key,klen,&oldlen,&freeoff,&freelen); if (p == NULL && freelen == 0) { - printf("HERE oldlen:%u required:%u\n",oldlen,reqlen); /* Key not found, and not space for the new key. Enlarge */ zm = zrealloc(zm,oldlen+reqlen); p = zm+oldlen-1; zm[oldlen+reqlen-1] = ZIPMAP_END; freelen = reqlen; - printf("New total length is: %u\n", oldlen+reqlen); } else if (p == NULL) { /* Key not found, but there is enough free space. */ p = zm+freeoff; @@ -236,14 +251,16 @@ unsigned char *zipmapSet(unsigned char *zm, unsigned char *key, unsigned int kle /* Key found. Is there enough space for the new value? */ /* Compute the total length: */ + if (update) *update = 1; freelen = zipmapRawKeyLength(b); b += freelen; freelen += zipmapRawValueLength(b); if (freelen < reqlen) { - /* Mark this blog as free and recurse */ + /* Mark this entry as free and recurse */ p[0] = ZIPMAP_EMPTY; zipmapEncodeLength(p+1,freelen); - return zipmapSet(zm,key,klen,val,vlen); + zm[0] |= ZIPMAP_STATUS_FRAGMENTED; + return zipmapSet(zm,key,klen,val,vlen,NULL); } } @@ -277,6 +294,84 @@ unsigned char *zipmapSet(unsigned char *zm, unsigned char *key, unsigned int kle return zm; } +/* Remove the specified key. If 'deleted' is not NULL the pointed integer is + * set to 0 if the key was not found, to 1 if it was found and deleted. */ +unsigned char *zipmapDel(unsigned char *zm, unsigned char *key, unsigned int klen, int *deleted) { + unsigned char *p = zipmapLookupRaw(zm,key,klen,NULL,NULL,NULL); + if (p) { + unsigned int freelen = zipmapRawEntryLength(p); + + p[0] = ZIPMAP_EMPTY; + zipmapEncodeLength(p+1,freelen); + zm[0] |= ZIPMAP_STATUS_FRAGMENTED; + if (deleted) *deleted = 1; + } else { + if (deleted) *deleted = 0; + } + return zm; +} + +/* Call it before to iterate trought elements via zipmapNext() */ +unsigned char *zipmapRewind(unsigned char *zm) { + return zm+1; +} + +/* This function is used to iterate through all the zipmap elements. + * In the first call the first argument is the pointer to the zipmap + 1. + * In the next calls what zipmapNext returns is used as first argument. + * Example: + * + * unsigned char *i = zipmapRewind(my_zipmap); + * while((i = zipmapNext(i,&key,&klen,&value,&vlen)) != NULL) { + * printf("%d bytes key at $p\n", klen, key); + * printf("%d bytes value at $p\n", vlen, value); + * } + */ +unsigned char *zipmapNext(unsigned char *zm, unsigned char **key, unsigned int *klen, unsigned char **value, unsigned int *vlen) { + while(zm[0] == ZIPMAP_EMPTY) + zm += zipmapDecodeLength(zm+1); + if (zm[0] == ZIPMAP_END) return NULL; + if (key) { + *key = zm; + *klen = zipmapDecodeLength(zm); + *key += ZIPMAP_LEN_BYTES(*klen); + } + zm += zipmapRawKeyLength(zm); + if (value) { + *value = zm+1; + *vlen = zipmapDecodeLength(zm); + *value += ZIPMAP_LEN_BYTES(*vlen); + } + zm += zipmapRawValueLength(zm); + return zm; +} + +/* Search a key and retrieve the pointer and len of the associated value. + * If the key is found the function returns 1, otherwise 0. */ +int zipmapGet(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned char **value, unsigned int *vlen) { + unsigned char *p; + + if ((p = zipmapLookupRaw(zm,key,klen,NULL,NULL,NULL)) == NULL) return 0; + p += zipmapRawKeyLength(p); + *vlen = zipmapDecodeLength(p); + *value = p + ZIPMAP_LEN_BYTES(*vlen) + 1; + return 1; +} + +/* Return 1 if the key exists, otherwise 0 is returned. */ +int zipmapExists(unsigned char *zm, unsigned char *key, unsigned int klen) { + return zipmapLookupRaw(zm,key,klen,NULL,NULL,NULL) != NULL; +} + +/* Return the number of entries inside a zipmap */ +unsigned int zipmapLen(unsigned char *zm) { + unsigned char *p = zipmapRewind(zm); + unsigned int len = 0; + + while((p = zipmapNext(p,NULL,NULL,NULL,NULL)) != NULL) len++; + return len; +} + void zipmapRepr(unsigned char *p) { unsigned int l; @@ -303,7 +398,7 @@ void zipmapRepr(unsigned char *p) { p += zipmapEncodeLength(NULL,l); e = *p++; fwrite(p,l,1,stdout); - p += l; + p += l+e; if (e) { printf("["); while(e--) printf("."); @@ -314,12 +409,49 @@ void zipmapRepr(unsigned char *p) { printf("\n"); } +#ifdef ZIPMAP_TEST_MAIN int main(void) { unsigned char *zm; zm = zipmapNew(); - zm = zipmapSet(zm,(unsigned char*) "hello",5, (unsigned char*) "world!",6); - zm = zipmapSet(zm,(unsigned char*) "foo",3, (unsigned char*) "bar",3); + + zm = zipmapSet(zm,(unsigned char*) "name",4, (unsigned char*) "foo",3,NULL); + zm = zipmapSet(zm,(unsigned char*) "surname",7, (unsigned char*) "foo",3,NULL); + zm = zipmapSet(zm,(unsigned char*) "age",3, (unsigned char*) "foo",3,NULL); zipmapRepr(zm); + exit(1); + + zm = zipmapSet(zm,(unsigned char*) "hello",5, (unsigned char*) "world!",6,NULL); + zm = zipmapSet(zm,(unsigned char*) "foo",3, (unsigned char*) "bar",3,NULL); + zm = zipmapSet(zm,(unsigned char*) "foo",3, (unsigned char*) "!",1,NULL); + zipmapRepr(zm); + zm = zipmapSet(zm,(unsigned char*) "foo",3, (unsigned char*) "12345",5,NULL); + zipmapRepr(zm); + zm = zipmapSet(zm,(unsigned char*) "new",3, (unsigned char*) "xx",2,NULL); + zm = zipmapSet(zm,(unsigned char*) "noval",5, (unsigned char*) "",0,NULL); + zipmapRepr(zm); + zm = zipmapDel(zm,(unsigned char*) "new",3,NULL); + zipmapRepr(zm); + printf("\nPerform a direct lookup:\n"); + { + unsigned char *value; + unsigned int vlen; + + if (zipmapGet(zm,(unsigned char*) "foo",3,&value,&vlen)) { + printf(" foo is associated to the %d bytes value: %.*s\n", + vlen, vlen, value); + } + } + printf("\nIterate trought elements:\n"); + { + unsigned char *i = zipmapRewind(zm); + unsigned char *key, *value; + unsigned int klen, vlen; + + while((i = zipmapNext(i,&key,&klen,&value,&vlen)) != NULL) { + printf(" %d:%.*s => %d:%.*s\n", klen, klen, key, vlen, vlen, value); + } + } return 0; } +#endif