[redis.git] / ziplist.c

/* Memory layout of a ziplist, containing "foo", "bar", "quux":
 * <zlbytes><zllen><len>"foo"<len>"bar"<len>"quux"
 *
 * <zlbytes> is an unsigned integer to hold the number of bytes that
 * the ziplist occupies. This is stored to not have to traverse the ziplist
 * to know the new length when pushing.
 *
 * <zllen> is the number of items in the ziplist. When this value is
 * greater than 254, we need to traverse the entire list to know
 * how many items it holds.
 *
 * <len> is the number of bytes occupied by a single entry. When this
 * number is greater than 253, the length will occupy 5 bytes, where
 * the extra bytes contain an unsigned integer to hold the length.
 */

#include <stdio.h>
#include <string.h>
#include <assert.h>
#include "zmalloc.h"
#include "sds.h"
#include "ziplist.h"
#include "zip.c"

#define ZIPLIST_BYTES(zl) (*((unsigned int*)(zl)))
#define ZIPLIST_LENGTH(zl) (*((zl)+sizeof(unsigned int)))
#define ZIPLIST_HEADER_SIZE (sizeof(unsigned int)+1)
#define ZIPLIST_INCR_LENGTH(zl,incr) { \
    if (ZIPLIST_LENGTH(zl) < (ZIP_END-1)) ZIPLIST_LENGTH(zl)+=incr; }

/* Create a new empty ziplist. */
unsigned char *ziplistNew(void) {
    unsigned int bytes = ZIPLIST_HEADER_SIZE+1;
    unsigned char *zl = zmalloc(bytes);
    ZIPLIST_BYTES(zl) = bytes;
    ZIPLIST_LENGTH(zl) = 0;
    zl[bytes-1] = ZIP_END;
    return zl;
}

static unsigned char *ziplistResize(unsigned char *zl, unsigned int len) {
    zl = zipResize(zl,len);
    ZIPLIST_BYTES(zl) = len;
    zl[len-1] = ZIP_END;
    return zl;
}

static unsigned char *ziplistHead(unsigned char *zl) {
    return zl+ZIPLIST_HEADER_SIZE;
}

static unsigned char *ziplistTail(unsigned char *zl) {
    unsigned char *p, *q;
    p = q = ziplistHead(zl);
    while (*p != ZIP_END) {
        q = p;
        p += zipRawEntryLength(p);
    }
    return q;
}

unsigned char *ziplistPush(unsigned char *zl, unsigned char *entry, unsigned int elen, int where) {
    unsigned int curlen = ZIPLIST_BYTES(zl);
    unsigned int reqlen = zipEncodeLength(NULL,elen)+elen;
    unsigned char *p;

    /* Resize the ziplist */
    zl = ziplistResize(zl,curlen+reqlen);

    if (where == ZIPLIST_HEAD) {
        p = zl+ZIPLIST_HEADER_SIZE;
        if (*p != ZIP_END) {
            /* Subtract one because of the ZIP_END bytes */
            memmove(p+reqlen,p,curlen-ZIPLIST_HEADER_SIZE-1);
        }
    } else {
        p = zl+curlen-1;
    }

    /* Write the entry */
    p += zipEncodeLength(p,elen);
    memcpy(p,entry,elen);
    ZIPLIST_INCR_LENGTH(zl,1);
    return zl;
}

unsigned char *ziplistPop(unsigned char *zl, sds *value, int where) {
    unsigned int curlen = ZIPLIST_BYTES(zl), len, rlen;
    unsigned char *p;
    if (value) *value = NULL;

    /* Get pointer to element to remove */
    p = (where == ZIPLIST_HEAD) ? ziplistHead(zl) : ziplistTail(zl);
    if (*p == ZIP_END) return zl;
    len = zipDecodeLength(p);
    if (value) *value = sdsnewlen(p+zipEncodeLength(NULL,len),len);

    /* Move list to front when popping from the head */
    rlen = zipRawEntryLength(p);
    if (where == ZIPLIST_HEAD) {
        memmove(p,p+rlen,curlen-ZIPLIST_HEADER_SIZE-len);
    }

    /* Resize and update length */
    zl = ziplistResize(zl,curlen-rlen);
    ZIPLIST_INCR_LENGTH(zl,-1);
    return zl;
}

/* Returns an offset to use for iterating with ziplistNext. */
unsigned char *ziplistIndex(unsigned char *zl, unsigned int index) {
    unsigned char *p = zl+ZIPLIST_HEADER_SIZE;
    unsigned int i = 0;
    for (; i < index; i++) {
        if (*p == ZIP_END) break;
        p += zipRawEntryLength(p);
    }
    return p;
}

/* Store entry at current position in sds *value and return pointer
 * to the next entry. */
unsigned char *ziplistNext(unsigned char *p, unsigned char **q, unsigned char **entry, unsigned int *elen) {
    if (*p == ZIP_END) return NULL;
    if (entry) {
        *elen = zipDecodeLength(p);
        *entry = p+ZIP_LEN_BYTES(*elen);
    }
    if (q != NULL) *q = p;
    p += zipRawEntryLength(p);
    return p;
}

/* Delete a range of entries from the ziplist. */
unsigned char *ziplistDeleteRange(unsigned char *zl, unsigned int index, unsigned int num) {
    unsigned char *p, *first = ziplistIndex(zl, index);
    unsigned int i, deleted = 0, totlen, newlen;
    for (p = first, i = 0; *p != ZIP_END && i < num; i++) {
        p += zipRawEntryLength(p);
        deleted++;
    }

    totlen = p-first;
    if (totlen > 0) {
        /* Move current tail to the new tail when there *is* a tail */
        if (*p != ZIP_END) memmove(first,p,ZIPLIST_BYTES(zl)-(p-zl)-1);

        /* Resize and update length */
        zl = ziplistResize(zl, ZIPLIST_BYTES(zl)-totlen);
        ZIPLIST_INCR_LENGTH(zl,-deleted);
    }
    return zl;
}

/* Delete a single entry from the ziplist, pointed to by *p.
 * Also update *p in place, to be able to iterate over the
 * ziplist, while deleting entries. */
unsigned char *ziplistDelete(unsigned char *zl, unsigned char **p) {
    unsigned int offset = *p-zl, tail, len;
    len = zipRawEntryLength(*p);
    tail = ZIPLIST_BYTES(zl)-offset-len-1;

    /* Move current tail to the new tail when there *is* a tail */
    if (tail > 0) memmove(*p,*p+len,tail);

    /* Resize and update length */
    zl = ziplistResize(zl, ZIPLIST_BYTES(zl)-len);
    ZIPLIST_INCR_LENGTH(zl,-1);

    /* Store new pointer to current element in p.
     * This needs to be done because zl can change on realloc. */
    *p = zl+offset;
    return zl;
}

void ziplistRepr(unsigned char *zl) {
    unsigned char *p;
    unsigned int l;

    printf("{bytes %d} {length %u}\n",ZIPLIST_BYTES(zl), ZIPLIST_LENGTH(zl));
    p = ziplistHead(zl);
    while(*p != ZIP_END) {
        l = zipDecodeLength(p);
        printf("{key %u}",l);
        p += zipEncodeLength(NULL,l);
        fwrite(p,l,1,stdout);
        printf("\n");
        p += l;
    }
    printf("{end}\n\n");
}

#ifdef ZIPLIST_TEST_MAIN

unsigned char *createList() {
    unsigned char *zl = ziplistNew();
    zl = ziplistPush(zl, (unsigned char*)"foo", 3, ZIPLIST_TAIL);
    zl = ziplistPush(zl, (unsigned char*)"quux", 4, ZIPLIST_TAIL);
    zl = ziplistPush(zl, (unsigned char*)"hello", 5, ZIPLIST_HEAD);
    return zl;
}

int main(int argc, char **argv) {
    unsigned char *zl, *p, *q, *entry;
    unsigned int elen;
    sds s;

    zl = createList();
    ziplistRepr(zl);

    zl = ziplistPop(zl, &s, ZIPLIST_TAIL);
    printf("Pop tail: %s (length %ld)\n", s, sdslen(s));
    ziplistRepr(zl);

    zl = ziplistPop(zl, &s, ZIPLIST_HEAD);
    printf("Pop head: %s (length %ld)\n", s, sdslen(s));
    ziplistRepr(zl);

    printf("Iterate list from 0 to end:\n");
    {
        zl = createList();
        p = ziplistIndex(zl, 0);
        while ((p = ziplistNext(p, NULL, &entry, &elen)) != NULL) {
            printf("Entry: ");
            fwrite(entry,elen,1,stdout);
            printf(" (length %d)\n", elen);
        }
        printf("\n");
    }

    printf("Iterate list from 1 to end:\n");
    {
        zl = createList();
        p = ziplistIndex(zl, 1);
        while ((p = ziplistNext(p, NULL, &entry, &elen)) != NULL) {
            printf("Entry: ");
            fwrite(entry,elen,1,stdout);
            printf(" (length %d)\n", elen);
        }
        printf("\n");
    }

    printf("Iterate list from 2 to end:\n");
    {
        zl = createList();
        p = ziplistIndex(zl, 2);
        while ((p = ziplistNext(p, NULL, &entry, &elen)) != NULL) {
            printf("Entry: ");
            fwrite(entry,elen,1,stdout);
            printf(" (length %d)\n", elen);
        }
        printf("\n");
    }

    printf("Iterate starting out of range:\n");
    {
        zl = createList();
        p = ziplistIndex(zl, 3);
        if (ziplistNext(p, &entry, NULL, &elen) == NULL) {
            printf("No entry\n");
        } else {
            printf("ERROR\n");
        }
        printf("\n");
    }

    printf("Delete inclusive range 0,0:\n");
    {
        zl = createList();
        zl = ziplistDeleteRange(zl, 0, 1);
        ziplistRepr(zl);
    }

    printf("Delete inclusive range 0,1:\n");
    {
        zl = createList();
        zl = ziplistDeleteRange(zl, 0, 2);
        ziplistRepr(zl);
    }

    printf("Delete inclusive range 1,2:\n");
    {
        zl = createList();
        zl = ziplistDeleteRange(zl, 1, 2);
        ziplistRepr(zl);
    }

    printf("Delete with start index out of range:\n");
    {
        zl = createList();
        zl = ziplistDeleteRange(zl, 5, 1);
        ziplistRepr(zl);
    }

    printf("Delete with num overflow:\n");
    {
        zl = createList();
        zl = ziplistDeleteRange(zl, 1, 5);
        ziplistRepr(zl);
    }

    printf("Delete foo while iterating:\n");
    {
        zl = createList();
        p = ziplistIndex(zl, 0);
        while ((p = ziplistNext(p, &q, &entry, &elen)) != NULL) {
            if (strncmp("foo", entry, elen) == 0) {
                printf("Delete foo\n");
                zl = ziplistDelete(zl, &q);
                p = q;
            } else {
                printf("Entry: ");
                fwrite(entry,elen,1,stdout);
                printf(" (length %d)\n", elen);
            }
        }
        printf("\n");
        ziplistRepr(zl);
        printf("\n");
    }

    return 0;
}
#endif
Commit	Line	Data
11ac6ff6 PN	1	/* Memory layout of a ziplist, containing "foo", "bar", "quux":
	2	* <zlbytes><zllen><len>"foo"<len>"bar"<len>"quux"
	3	*
	4	* <zlbytes> is an unsigned integer to hold the number of bytes that
	5	* the ziplist occupies. This is stored to not have to traverse the ziplist
	6	* to know the new length when pushing.
	7	*
	8	* <zllen> is the number of items in the ziplist. When this value is
	9	* greater than 254, we need to traverse the entire list to know
	10	* how many items it holds.
	11	*
	12	* <len> is the number of bytes occupied by a single entry. When this
	13	* number is greater than 253, the length will occupy 5 bytes, where
	14	* the extra bytes contain an unsigned integer to hold the length.
	15	*/
	16
	17	#include <stdio.h>
	18	#include <string.h>
	19	#include <assert.h>
	20	#include "zmalloc.h"
	21	#include "sds.h"
	22	#include "ziplist.h"
	23	#include "zip.c"
	24
	25	#define ZIPLIST_BYTES(zl) (((unsigned int)(zl)))
	26	#define ZIPLIST_LENGTH(zl) (*((zl)+sizeof(unsigned int)))
	27	#define ZIPLIST_HEADER_SIZE (sizeof(unsigned int)+1)
f6eb1747 PN	28	#define ZIPLIST_INCR_LENGTH(zl,incr) { \
f6eb1747 PN	29	if (ZIPLIST_LENGTH(zl) < (ZIP_END-1)) ZIPLIST_LENGTH(zl)+=incr; }
11ac6ff6 PN	30
	31	/* Create a new empty ziplist. */
	32	unsigned char *ziplistNew(void) {
	33	unsigned int bytes = ZIPLIST_HEADER_SIZE+1;
	34	unsigned char *zl = zmalloc(bytes);
	35	ZIPLIST_BYTES(zl) = bytes;
	36	ZIPLIST_LENGTH(zl) = 0;
	37	zl[bytes-1] = ZIP_END;
	38	return zl;
	39	}
	40
	41	static unsigned char ziplistResize(unsigned char zl, unsigned int len) {
	42	zl = zipResize(zl,len);
	43	ZIPLIST_BYTES(zl) = len;
	44	zl[len-1] = ZIP_END;
	45	return zl;
	46	}
	47
	48	static unsigned char ziplistHead(unsigned char zl) {
	49	return zl+ZIPLIST_HEADER_SIZE;
	50	}
	51
	52	static unsigned char ziplistTail(unsigned char zl) {
	53	unsigned char p, q;
	54	p = q = ziplistHead(zl);
	55	while (*p != ZIP_END) {
	56	q = p;
	57	p += zipRawEntryLength(p);
	58	}
	59	return q;
	60	}
	61
	62	unsigned char ziplistPush(unsigned char zl, unsigned char *entry, unsigned int elen, int where) {
	63	unsigned int curlen = ZIPLIST_BYTES(zl);
	64	unsigned int reqlen = zipEncodeLength(NULL,elen)+elen;
	65	unsigned char *p;
	66
	67	/* Resize the ziplist */
	68	zl = ziplistResize(zl,curlen+reqlen);
	69
	70	if (where == ZIPLIST_HEAD) {
	71	p = zl+ZIPLIST_HEADER_SIZE;
	72	if (*p != ZIP_END) {
	73	/* Subtract one because of the ZIP_END bytes */
	74	memmove(p+reqlen,p,curlen-ZIPLIST_HEADER_SIZE-1);
	75	}
	76	} else {
	77	p = zl+curlen-1;
	78	}
	79
11ac6ff6 PN	80	/* Write the entry */
	81	p += zipEncodeLength(p,elen);
	82	memcpy(p,entry,elen);
f6eb1747	83	ZIPLIST_INCR_LENGTH(zl,1);
11ac6ff6 PN	84	return zl;
	85	}
	86
	87	unsigned char ziplistPop(unsigned char zl, sds *value, int where) {
	88	unsigned int curlen = ZIPLIST_BYTES(zl), len, rlen;
	89	unsigned char *p;
33c1269e	90	if (value) *value = NULL;
11ac6ff6 PN	91
	92	/* Get pointer to element to remove */
	93	p = (where == ZIPLIST_HEAD) ? ziplistHead(zl) : ziplistTail(zl);
	94	if (*p == ZIP_END) return zl;
	95	len = zipDecodeLength(p);
33c1269e	96	if (value) *value = sdsnewlen(p+zipEncodeLength(NULL,len),len);
11ac6ff6 PN	97
	98	/* Move list to front when popping from the head */
	99	rlen = zipRawEntryLength(p);
	100	if (where == ZIPLIST_HEAD) {
	101	memmove(p,p+rlen,curlen-ZIPLIST_HEADER_SIZE-len);
	102	}
	103
	104	/* Resize and update length */
	105	zl = ziplistResize(zl,curlen-rlen);
f6eb1747	106	ZIPLIST_INCR_LENGTH(zl,-1);
11ac6ff6 PN	107	return zl;
	108	}
	109
08253bf4 PN	110	/* Returns an offset to use for iterating with ziplistNext. */
	111	unsigned char ziplistIndex(unsigned char zl, unsigned int index) {
	112	unsigned char *p = zl+ZIPLIST_HEADER_SIZE;
	113	unsigned int i = 0;
	114	for (; i < index; i++) {
	115	if (*p == ZIP_END) break;
	116	p += zipRawEntryLength(p);
	117	}
	118	return p;
	119	}
	120
	121	/* Store entry at current position in sds *value and return pointer
	122	* to the next entry. */
924727d9	123	unsigned char ziplistNext(unsigned char p, unsigned char q, unsigned char entry, unsigned int *elen) {
08253bf4	124	if (*p == ZIP_END) return NULL;
335d16bc PN	125	if (entry) {
	126	*elen = zipDecodeLength(p);
	127	entry = p+ZIP_LEN_BYTES(elen);
08253bf4	128	}
924727d9	129	if (q != NULL) *q = p;
08253bf4 PN	130	p += zipRawEntryLength(p);
	131	return p;
	132	}
	133
ba5b4bde PN	134	/* Delete a range of entries from the ziplist. */
ba5b4bde PN	135	unsigned char ziplistDeleteRange(unsigned char zl, unsigned int index, unsigned int num) {
779deb60 PN	136	unsigned char p, first = ziplistIndex(zl, index);
	137	unsigned int i, deleted = 0, totlen, newlen;
	138	for (p = first, i = 0; *p != ZIP_END && i < num; i++) {
	139	p += zipRawEntryLength(p);
	140	deleted++;
	141	}
	142
	143	totlen = p-first;
	144	if (totlen > 0) {
	145	/* Move current tail to the new tail when there is a tail */
	146	if (*p != ZIP_END) memmove(first,p,ZIPLIST_BYTES(zl)-(p-zl)-1);
	147
	148	/* Resize and update length */
	149	zl = ziplistResize(zl, ZIPLIST_BYTES(zl)-totlen);
f6eb1747	150	ZIPLIST_INCR_LENGTH(zl,-deleted);
779deb60 PN	151	}
	152	return zl;
	153	}
	154
0f10458c PN	155	/* Delete a single entry from the ziplist, pointed to by *p.
	156	* Also update *p in place, to be able to iterate over the
	157	* ziplist, while deleting entries. */
	158	unsigned char ziplistDelete(unsigned char zl, unsigned char **p) {
	159	unsigned int offset = *p-zl, tail, len;
	160	len = zipRawEntryLength(*p);
	161	tail = ZIPLIST_BYTES(zl)-offset-len-1;
	162
	163	/* Move current tail to the new tail when there is a tail */
	164	if (tail > 0) memmove(p,p+len,tail);
	165
	166	/* Resize and update length */
	167	zl = ziplistResize(zl, ZIPLIST_BYTES(zl)-len);
f6eb1747	168	ZIPLIST_INCR_LENGTH(zl,-1);
0f10458c PN	169
	170	/* Store new pointer to current element in p.
	171	* This needs to be done because zl can change on realloc. */
	172	*p = zl+offset;
	173	return zl;
	174	}
	175
11ac6ff6 PN	176	void ziplistRepr(unsigned char *zl) {
	177	unsigned char *p;
	178	unsigned int l;
	179
	180	printf("{bytes %d} {length %u}\n",ZIPLIST_BYTES(zl), ZIPLIST_LENGTH(zl));
	181	p = ziplistHead(zl);
	182	while(*p != ZIP_END) {
	183	l = zipDecodeLength(p);
	184	printf("{key %u}",l);
	185	p += zipEncodeLength(NULL,l);
	186	fwrite(p,l,1,stdout);
	187	printf("\n");
	188	p += l;
	189	}
	190	printf("{end}\n\n");
	191	}
	192
	193	#ifdef ZIPLIST_TEST_MAIN
11ac6ff6	194
08253bf4 PN	195	unsigned char *createList() {
08253bf4 PN	196	unsigned char *zl = ziplistNew();
11ac6ff6	197	zl = ziplistPush(zl, (unsigned char*)"foo", 3, ZIPLIST_TAIL);
11ac6ff6	198	zl = ziplistPush(zl, (unsigned char*)"quux", 4, ZIPLIST_TAIL);
11ac6ff6	199	zl = ziplistPush(zl, (unsigned char*)"hello", 5, ZIPLIST_HEAD);
08253bf4 PN	200	return zl;
	201	}
	202
	203	int main(int argc, char **argv) {
0f10458c	204	unsigned char zl, p, q, entry;
335d16bc	205	unsigned int elen;
08253bf4 PN	206	sds s;
	207
	208	zl = createList();
11ac6ff6 PN	209	ziplistRepr(zl);
	210
	211	zl = ziplistPop(zl, &s, ZIPLIST_TAIL);
	212	printf("Pop tail: %s (length %ld)\n", s, sdslen(s));
	213	ziplistRepr(zl);
	214
	215	zl = ziplistPop(zl, &s, ZIPLIST_HEAD);
	216	printf("Pop head: %s (length %ld)\n", s, sdslen(s));
	217	ziplistRepr(zl);
	218
08253bf4 PN	219	printf("Iterate list from 0 to end:\n");
	220	{
	221	zl = createList();
	222	p = ziplistIndex(zl, 0);
924727d9	223	while ((p = ziplistNext(p, NULL, &entry, &elen)) != NULL) {
335d16bc PN	224	printf("Entry: ");
	225	fwrite(entry,elen,1,stdout);
	226	printf(" (length %d)\n", elen);
08253bf4 PN	227	}
	228	printf("\n");
	229	}
	230
	231	printf("Iterate list from 1 to end:\n");
	232	{
	233	zl = createList();
	234	p = ziplistIndex(zl, 1);
924727d9	235	while ((p = ziplistNext(p, NULL, &entry, &elen)) != NULL) {
335d16bc PN	236	printf("Entry: ");
	237	fwrite(entry,elen,1,stdout);
	238	printf(" (length %d)\n", elen);
08253bf4 PN	239	}
	240	printf("\n");
	241	}
	242
	243	printf("Iterate list from 2 to end:\n");
	244	{
	245	zl = createList();
	246	p = ziplistIndex(zl, 2);
924727d9	247	while ((p = ziplistNext(p, NULL, &entry, &elen)) != NULL) {
335d16bc PN	248	printf("Entry: ");
	249	fwrite(entry,elen,1,stdout);
	250	printf(" (length %d)\n", elen);
08253bf4 PN	251	}
	252	printf("\n");
	253	}
	254
	255	printf("Iterate starting out of range:\n");
	256	{
	257	zl = createList();
	258	p = ziplistIndex(zl, 3);
924727d9	259	if (ziplistNext(p, &entry, NULL, &elen) == NULL) {
08253bf4 PN	260	printf("No entry\n");
	261	} else {
	262	printf("ERROR\n");
	263	}
779deb60 PN	264	printf("\n");
	265	}
	266
	267	printf("Delete inclusive range 0,0:\n");
	268	{
	269	zl = createList();
ba5b4bde	270	zl = ziplistDeleteRange(zl, 0, 1);
779deb60 PN	271	ziplistRepr(zl);
	272	}
	273
	274	printf("Delete inclusive range 0,1:\n");
	275	{
	276	zl = createList();
ba5b4bde	277	zl = ziplistDeleteRange(zl, 0, 2);
779deb60 PN	278	ziplistRepr(zl);
	279	}
	280
	281	printf("Delete inclusive range 1,2:\n");
	282	{
	283	zl = createList();
ba5b4bde	284	zl = ziplistDeleteRange(zl, 1, 2);
779deb60 PN	285	ziplistRepr(zl);
	286	}
	287
	288	printf("Delete with start index out of range:\n");
	289	{
	290	zl = createList();
ba5b4bde	291	zl = ziplistDeleteRange(zl, 5, 1);
779deb60 PN	292	ziplistRepr(zl);
	293	}
	294
	295	printf("Delete with num overflow:\n");
	296	{
	297	zl = createList();
ba5b4bde	298	zl = ziplistDeleteRange(zl, 1, 5);
779deb60	299	ziplistRepr(zl);
08253bf4 PN	300	}
08253bf4 PN	301
0f10458c PN	302	printf("Delete foo while iterating:\n");
	303	{
	304	zl = createList();
	305	p = ziplistIndex(zl, 0);
	306	while ((p = ziplistNext(p, &q, &entry, &elen)) != NULL) {
	307	if (strncmp("foo", entry, elen) == 0) {
	308	printf("Delete foo\n");
	309	zl = ziplistDelete(zl, &q);
	310	p = q;
	311	} else {
	312	printf("Entry: ");
	313	fwrite(entry,elen,1,stdout);
	314	printf(" (length %d)\n", elen);
	315	}
	316	}
	317	printf("\n");
	318	ziplistRepr(zl);
	319	printf("\n");
	320	}
	321
11ac6ff6 PN	322	return 0;
	323	}
	324	#endif