[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 <stdlib.h>
#include <string.h>
#include <assert.h>
#include <limits.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), reqlen;
    unsigned char *p;
    char encoding = ZIP_ENC_RAW;
    long long value;

    /* See if the entry can be encoded */
    if (zipTryEncoding(entry,&value,&encoding)) {
        reqlen = zipEncodingSize(encoding);
    } else {
        reqlen = elen;
    }
    reqlen += zipEncodeLength(NULL,encoding,elen);

    /* Resize the ziplist and move if needed */
    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,encoding,elen);
    if (encoding != ZIP_ENC_RAW) {
        zipSaveInteger(p,value,encoding);
    } else {
        memcpy(p,entry,elen);
    }
    ZIPLIST_INCR_LENGTH(zl,1);
    return zl;
}

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

    /* Get pointer to element to remove */
    p = (where == ZIPLIST_HEAD) ? ziplistHead(zl) : ziplistTail(zl);
    if (*p == ZIP_END) return zl;
    len = zipDecodeLength(p,&lensize);
    if (target) {
        if (ZIP_ENCODING(p) == ZIP_ENC_RAW) {
            *target = sdsnewlen(p+lensize,len);
        } else {
            value = zipLoadInteger(p+lensize,ZIP_ENCODING(p));
            *target = sdscatprintf(sdsempty(), "%lld", value);
        }
    }

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

    /* Resize and update length */
    zl = ziplistResize(zl,curlen-rawlen);
    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) {
    unsigned int lensize;
    if (*p == ZIP_END) return NULL;
    if (entry) {
        *elen = zipDecodeLength(p,&lensize);
        *entry = p+lensize;
    }
    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, encoding;
    unsigned int l, lsize;
    long long value;

    printf("{total bytes %d} {length %u}\n",ZIPLIST_BYTES(zl), ZIPLIST_LENGTH(zl));
    p = ziplistHead(zl);
    while(*p != ZIP_END) {
        l = zipDecodeLength(p,&lsize);
        printf("{header %u, payload %u} ",lsize,l);
        encoding = ZIP_ENCODING(p);
        p += lsize;
        if (encoding == ZIP_ENC_RAW) {
            fwrite(p,l,1,stdout);
        } else {
            printf("%lld", zipLoadInteger(p,encoding));
        }
        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;
}

unsigned char *createIntList() {
    unsigned char *zl = ziplistNew();
    char buf[32];

    sprintf(buf, "100");
    zl = ziplistPush(zl, buf, strlen(buf), ZIPLIST_TAIL);
    sprintf(buf, "128000");
    zl = ziplistPush(zl, buf, strlen(buf), ZIPLIST_TAIL);
    sprintf(buf, "-100");
    zl = ziplistPush(zl, buf, strlen(buf), ZIPLIST_HEAD);
    sprintf(buf, "4294967296");
    zl = ziplistPush(zl, buf, strlen(buf), ZIPLIST_HEAD);
    sprintf(buf, "non integer");
    zl = ziplistPush(zl, buf, strlen(buf), ZIPLIST_TAIL);
    sprintf(buf, "much much longer non integer");
    zl = ziplistPush(zl, buf, strlen(buf), ZIPLIST_TAIL);
    return zl;
}

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

    zl = createIntList();
    ziplistRepr(zl);

    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>
29b14d5f	18	#include <stdlib.h>
11ac6ff6 PN	19	#include <string.h>
11ac6ff6 PN	20	#include <assert.h>
29b14d5f	21	#include <limits.h>
11ac6ff6 PN	22	#include "zmalloc.h"
	23	#include "sds.h"
	24	#include "ziplist.h"
	25	#include "zip.c"
	26
	27	#define ZIPLIST_BYTES(zl) (((unsigned int)(zl)))
	28	#define ZIPLIST_LENGTH(zl) (*((zl)+sizeof(unsigned int)))
	29	#define ZIPLIST_HEADER_SIZE (sizeof(unsigned int)+1)
f6eb1747 PN	30	#define ZIPLIST_INCR_LENGTH(zl,incr) { \
f6eb1747 PN	31	if (ZIPLIST_LENGTH(zl) < (ZIP_END-1)) ZIPLIST_LENGTH(zl)+=incr; }
11ac6ff6 PN	32
	33	/* Create a new empty ziplist. */
	34	unsigned char *ziplistNew(void) {
	35	unsigned int bytes = ZIPLIST_HEADER_SIZE+1;
	36	unsigned char *zl = zmalloc(bytes);
	37	ZIPLIST_BYTES(zl) = bytes;
	38	ZIPLIST_LENGTH(zl) = 0;
	39	zl[bytes-1] = ZIP_END;
	40	return zl;
	41	}
	42
	43	static unsigned char ziplistResize(unsigned char zl, unsigned int len) {
	44	zl = zipResize(zl,len);
	45	ZIPLIST_BYTES(zl) = len;
	46	zl[len-1] = ZIP_END;
	47	return zl;
	48	}
	49
	50	static unsigned char ziplistHead(unsigned char zl) {
	51	return zl+ZIPLIST_HEADER_SIZE;
	52	}
	53
	54	static unsigned char ziplistTail(unsigned char zl) {
	55	unsigned char p, q;
	56	p = q = ziplistHead(zl);
	57	while (*p != ZIP_END) {
	58	q = p;
	59	p += zipRawEntryLength(p);
	60	}
	61	return q;
	62	}
	63
	64	unsigned char ziplistPush(unsigned char zl, unsigned char *entry, unsigned int elen, int where) {
29b14d5f	65	unsigned int curlen = ZIPLIST_BYTES(zl), reqlen;
11ac6ff6	66	unsigned char *p;
29b14d5f PN	67	char encoding = ZIP_ENC_RAW;
29b14d5f PN	68	long long value;
11ac6ff6	69
29b14d5f PN	70	/* See if the entry can be encoded */
	71	if (zipTryEncoding(entry,&value,&encoding)) {
	72	reqlen = zipEncodingSize(encoding);
	73	} else {
	74	reqlen = elen;
	75	}
	76	reqlen += zipEncodeLength(NULL,encoding,elen);
11ac6ff6	77
29b14d5f PN	78	/* Resize the ziplist and move if needed */
29b14d5f PN	79	zl = ziplistResize(zl,curlen+reqlen);
11ac6ff6 PN	80	if (where == ZIPLIST_HEAD) {
	81	p = zl+ZIPLIST_HEADER_SIZE;
	82	if (*p != ZIP_END) {
	83	/* Subtract one because of the ZIP_END bytes */
	84	memmove(p+reqlen,p,curlen-ZIPLIST_HEADER_SIZE-1);
	85	}
	86	} else {
	87	p = zl+curlen-1;
	88	}
	89
11ac6ff6	90	/* Write the entry */
29b14d5f PN	91	p += zipEncodeLength(p,encoding,elen);
	92	if (encoding != ZIP_ENC_RAW) {
	93	zipSaveInteger(p,value,encoding);
	94	} else {
	95	memcpy(p,entry,elen);
	96	}
f6eb1747	97	ZIPLIST_INCR_LENGTH(zl,1);
11ac6ff6 PN	98	return zl;
	99	}
	100
29b14d5f PN	101	unsigned char ziplistPop(unsigned char zl, sds *target, int where) {
	102	unsigned int curlen = ZIPLIST_BYTES(zl), rawlen;
	103	unsigned int len, lensize;
11ac6ff6	104	unsigned char *p;
29b14d5f PN	105	long long value;
29b14d5f PN	106	if (target) *target = NULL;
11ac6ff6 PN	107
	108	/* Get pointer to element to remove */
	109	p = (where == ZIPLIST_HEAD) ? ziplistHead(zl) : ziplistTail(zl);
	110	if (*p == ZIP_END) return zl;
29b14d5f PN	111	len = zipDecodeLength(p,&lensize);
	112	if (target) {
	113	if (ZIP_ENCODING(p) == ZIP_ENC_RAW) {
	114	*target = sdsnewlen(p+lensize,len);
	115	} else {
	116	value = zipLoadInteger(p+lensize,ZIP_ENCODING(p));
	117	*target = sdscatprintf(sdsempty(), "%lld", value);
	118	}
	119	}
11ac6ff6 PN	120
11ac6ff6 PN	121	/* Move list to front when popping from the head */
29b14d5f	122	rawlen = lensize+len;
11ac6ff6	123	if (where == ZIPLIST_HEAD) {
29b14d5f	124	memmove(p,p+rawlen,curlen-ZIPLIST_HEADER_SIZE-len);
11ac6ff6 PN	125	}
	126
	127	/* Resize and update length */
29b14d5f	128	zl = ziplistResize(zl,curlen-rawlen);
f6eb1747	129	ZIPLIST_INCR_LENGTH(zl,-1);
11ac6ff6 PN	130	return zl;
	131	}
	132
08253bf4 PN	133	/* Returns an offset to use for iterating with ziplistNext. */
	134	unsigned char ziplistIndex(unsigned char zl, unsigned int index) {
	135	unsigned char *p = zl+ZIPLIST_HEADER_SIZE;
	136	unsigned int i = 0;
	137	for (; i < index; i++) {
	138	if (*p == ZIP_END) break;
	139	p += zipRawEntryLength(p);
	140	}
	141	return p;
	142	}
	143
	144	/* Store entry at current position in sds *value and return pointer
	145	* to the next entry. */
924727d9	146	unsigned char ziplistNext(unsigned char p, unsigned char q, unsigned char entry, unsigned int *elen) {
29b14d5f	147	unsigned int lensize;
08253bf4	148	if (*p == ZIP_END) return NULL;
335d16bc	149	if (entry) {
29b14d5f PN	150	*elen = zipDecodeLength(p,&lensize);
29b14d5f PN	151	*entry = p+lensize;
08253bf4	152	}
924727d9	153	if (q != NULL) *q = p;
08253bf4 PN	154	p += zipRawEntryLength(p);
	155	return p;
	156	}
	157
ba5b4bde PN	158	/* Delete a range of entries from the ziplist. */
ba5b4bde PN	159	unsigned char ziplistDeleteRange(unsigned char zl, unsigned int index, unsigned int num) {
779deb60 PN	160	unsigned char p, first = ziplistIndex(zl, index);
	161	unsigned int i, deleted = 0, totlen, newlen;
	162	for (p = first, i = 0; *p != ZIP_END && i < num; i++) {
	163	p += zipRawEntryLength(p);
	164	deleted++;
	165	}
	166
	167	totlen = p-first;
	168	if (totlen > 0) {
	169	/* Move current tail to the new tail when there is a tail */
	170	if (*p != ZIP_END) memmove(first,p,ZIPLIST_BYTES(zl)-(p-zl)-1);
	171
	172	/* Resize and update length */
	173	zl = ziplistResize(zl, ZIPLIST_BYTES(zl)-totlen);
f6eb1747	174	ZIPLIST_INCR_LENGTH(zl,-deleted);
779deb60 PN	175	}
	176	return zl;
	177	}
	178
0f10458c PN	179	/* Delete a single entry from the ziplist, pointed to by *p.
	180	* Also update *p in place, to be able to iterate over the
	181	* ziplist, while deleting entries. */
	182	unsigned char ziplistDelete(unsigned char zl, unsigned char **p) {
	183	unsigned int offset = *p-zl, tail, len;
	184	len = zipRawEntryLength(*p);
	185	tail = ZIPLIST_BYTES(zl)-offset-len-1;
	186
	187	/* Move current tail to the new tail when there is a tail */
	188	if (tail > 0) memmove(p,p+len,tail);
	189
	190	/* Resize and update length */
	191	zl = ziplistResize(zl, ZIPLIST_BYTES(zl)-len);
f6eb1747	192	ZIPLIST_INCR_LENGTH(zl,-1);
0f10458c PN	193
	194	/* Store new pointer to current element in p.
	195	* This needs to be done because zl can change on realloc. */
	196	*p = zl+offset;
	197	return zl;
	198	}
	199
11ac6ff6	200	void ziplistRepr(unsigned char *zl) {
29b14d5f PN	201	unsigned char *p, encoding;
	202	unsigned int l, lsize;
	203	long long value;
11ac6ff6	204
29b14d5f	205	printf("{total bytes %d} {length %u}\n",ZIPLIST_BYTES(zl), ZIPLIST_LENGTH(zl));
11ac6ff6 PN	206	p = ziplistHead(zl);
11ac6ff6 PN	207	while(*p != ZIP_END) {
29b14d5f PN	208	l = zipDecodeLength(p,&lsize);
	209	printf("{header %u, payload %u} ",lsize,l);
	210	encoding = ZIP_ENCODING(p);
	211	p += lsize;
	212	if (encoding == ZIP_ENC_RAW) {
	213	fwrite(p,l,1,stdout);
	214	} else {
	215	printf("%lld", zipLoadInteger(p,encoding));
	216	}
11ac6ff6 PN	217	printf("\n");
	218	p += l;
	219	}
	220	printf("{end}\n\n");
	221	}
	222
	223	#ifdef ZIPLIST_TEST_MAIN
11ac6ff6	224
08253bf4 PN	225	unsigned char *createList() {
08253bf4 PN	226	unsigned char *zl = ziplistNew();
11ac6ff6	227	zl = ziplistPush(zl, (unsigned char*)"foo", 3, ZIPLIST_TAIL);
11ac6ff6	228	zl = ziplistPush(zl, (unsigned char*)"quux", 4, ZIPLIST_TAIL);
11ac6ff6	229	zl = ziplistPush(zl, (unsigned char*)"hello", 5, ZIPLIST_HEAD);
08253bf4 PN	230	return zl;
	231	}
	232
29b14d5f PN	233	unsigned char *createIntList() {
	234	unsigned char *zl = ziplistNew();
	235	char buf[32];
	236
	237	sprintf(buf, "100");
	238	zl = ziplistPush(zl, buf, strlen(buf), ZIPLIST_TAIL);
	239	sprintf(buf, "128000");
	240	zl = ziplistPush(zl, buf, strlen(buf), ZIPLIST_TAIL);
	241	sprintf(buf, "-100");
	242	zl = ziplistPush(zl, buf, strlen(buf), ZIPLIST_HEAD);
	243	sprintf(buf, "4294967296");
	244	zl = ziplistPush(zl, buf, strlen(buf), ZIPLIST_HEAD);
	245	sprintf(buf, "non integer");
	246	zl = ziplistPush(zl, buf, strlen(buf), ZIPLIST_TAIL);
	247	sprintf(buf, "much much longer non integer");
	248	zl = ziplistPush(zl, buf, strlen(buf), ZIPLIST_TAIL);
	249	return zl;
	250	}
	251
08253bf4	252	int main(int argc, char **argv) {
0f10458c	253	unsigned char zl, p, q, entry;
335d16bc	254	unsigned int elen;
08253bf4 PN	255	sds s;
08253bf4 PN	256
29b14d5f PN	257	zl = createIntList();
	258	ziplistRepr(zl);
	259
08253bf4	260	zl = createList();
11ac6ff6 PN	261	ziplistRepr(zl);
	262
	263	zl = ziplistPop(zl, &s, ZIPLIST_TAIL);
	264	printf("Pop tail: %s (length %ld)\n", s, sdslen(s));
	265	ziplistRepr(zl);
	266
	267	zl = ziplistPop(zl, &s, ZIPLIST_HEAD);
	268	printf("Pop head: %s (length %ld)\n", s, sdslen(s));
	269	ziplistRepr(zl);
	270
08253bf4 PN	271	printf("Iterate list from 0 to end:\n");
	272	{
	273	zl = createList();
	274	p = ziplistIndex(zl, 0);
924727d9	275	while ((p = ziplistNext(p, NULL, &entry, &elen)) != NULL) {
335d16bc PN	276	printf("Entry: ");
	277	fwrite(entry,elen,1,stdout);
	278	printf(" (length %d)\n", elen);
08253bf4 PN	279	}
	280	printf("\n");
	281	}
	282
	283	printf("Iterate list from 1 to end:\n");
	284	{
	285	zl = createList();
	286	p = ziplistIndex(zl, 1);
924727d9	287	while ((p = ziplistNext(p, NULL, &entry, &elen)) != NULL) {
335d16bc PN	288	printf("Entry: ");
	289	fwrite(entry,elen,1,stdout);
	290	printf(" (length %d)\n", elen);
08253bf4 PN	291	}
	292	printf("\n");
	293	}
	294
	295	printf("Iterate list from 2 to end:\n");
	296	{
	297	zl = createList();
	298	p = ziplistIndex(zl, 2);
924727d9	299	while ((p = ziplistNext(p, NULL, &entry, &elen)) != NULL) {
335d16bc PN	300	printf("Entry: ");
	301	fwrite(entry,elen,1,stdout);
	302	printf(" (length %d)\n", elen);
08253bf4 PN	303	}
	304	printf("\n");
	305	}
	306
	307	printf("Iterate starting out of range:\n");
	308	{
	309	zl = createList();
	310	p = ziplistIndex(zl, 3);
924727d9	311	if (ziplistNext(p, &entry, NULL, &elen) == NULL) {
08253bf4 PN	312	printf("No entry\n");
	313	} else {
	314	printf("ERROR\n");
	315	}
779deb60 PN	316	printf("\n");
	317	}
	318
	319	printf("Delete inclusive range 0,0:\n");
	320	{
	321	zl = createList();
ba5b4bde	322	zl = ziplistDeleteRange(zl, 0, 1);
779deb60 PN	323	ziplistRepr(zl);
	324	}
	325
	326	printf("Delete inclusive range 0,1:\n");
	327	{
	328	zl = createList();
ba5b4bde	329	zl = ziplistDeleteRange(zl, 0, 2);
779deb60 PN	330	ziplistRepr(zl);
	331	}
	332
	333	printf("Delete inclusive range 1,2:\n");
	334	{
	335	zl = createList();
ba5b4bde	336	zl = ziplistDeleteRange(zl, 1, 2);
779deb60 PN	337	ziplistRepr(zl);
	338	}
	339
	340	printf("Delete with start index out of range:\n");
	341	{
	342	zl = createList();
ba5b4bde	343	zl = ziplistDeleteRange(zl, 5, 1);
779deb60 PN	344	ziplistRepr(zl);
	345	}
	346
	347	printf("Delete with num overflow:\n");
	348	{
	349	zl = createList();
ba5b4bde	350	zl = ziplistDeleteRange(zl, 1, 5);
779deb60	351	ziplistRepr(zl);
08253bf4 PN	352	}
08253bf4 PN	353
0f10458c PN	354	printf("Delete foo while iterating:\n");
	355	{
	356	zl = createList();
	357	p = ziplistIndex(zl, 0);
	358	while ((p = ziplistNext(p, &q, &entry, &elen)) != NULL) {
	359	if (strncmp("foo", entry, elen) == 0) {
	360	printf("Delete foo\n");
	361	zl = ziplistDelete(zl, &q);
	362	p = q;
	363	} else {
	364	printf("Entry: ");
	365	fwrite(entry,elen,1,stdout);
	366	printf(" (length %d)\n", elen);
	367	}
	368	}
	369	printf("\n");
	370	ziplistRepr(zl);
	371	printf("\n");
	372	}
	373
11ac6ff6 PN	374	return 0;
	375	}
	376	#endif