Add quicklist implementation

This replaces individual ziplist vs. linkedlist representations
for Redis list operations.

Big thanks for all the reviews and feedback from everybody in
https://github.com/antirez/redis/pull/2143

1 files changed, 120 insertions, 0 deletions

diff --git a/src/quicklist.h b/src/quicklist.h
new file mode 100644
index 000000000..93b38d880
--- /dev/null
+++ b/src/quicklist.h
@@ -0,0 +1,120 @@
+/* quicklist.h - A generic doubly linked quicklist implementation
+ *
+ * Copyright (c) 2014, Matt Stancliff <matt@genges.com>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ *
+ *   * Redistributions of source code must retain the above copyright notice,
+ *     this quicklist of conditions and the following disclaimer.
+ *   * Redistributions in binary form must reproduce the above copyright
+ *     notice, this quicklist of conditions and the following disclaimer in the
+ *     documentation and/or other materials provided with the distribution.
+ *   * Neither the name of Redis nor the names of its contributors may be used
+ *     to endorse or promote products derived from this software without
+ *     specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef __QUICKLIST_H__
+#define __QUICKLIST_H__
+
+/* Node, quicklist, and Iterator are the only data structures used currently. */
+
+typedef struct quicklistNode {
+    struct quicklistNode *prev;
+    struct quicklistNode *next;
+    unsigned char *zl;
+    unsigned int count; /* cached count of items in ziplist */
+} quicklistNode;
+
+typedef struct quicklist {
+    quicklistNode *head;
+    quicklistNode *tail;
+    unsigned long len;   /* number of quicklistNodes */
+    unsigned long count; /* total count of all entries in all ziplists */
+} quicklist;
+
+typedef struct quicklistIter {
+    const quicklist *quicklist;
+    quicklistNode *current;
+    unsigned char *zi;
+    long offset; /* offset in current ziplist */
+    int direction;
+} quicklistIter;
+
+typedef struct quicklistEntry {
+    const quicklist *quicklist;
+    quicklistNode *node;
+    unsigned char *zi;
+    unsigned char *value;
+    unsigned int sz;
+    long long longval;
+    int offset;
+} quicklistEntry;
+
+#define QUICKLIST_HEAD 0
+#define QUICKLIST_TAIL -1
+
+/* Prototypes */
+quicklist *quicklistCreate(void);
+void quicklistRelease(quicklist *quicklist);
+quicklist *quicklistPushHead(quicklist *quicklist, const size_t fill,
+                             void *value, const size_t sz);
+quicklist *quicklistPushTail(quicklist *quicklist, const size_t fill,
+                             void *value, const size_t sz);
+void quicklistPush(quicklist *quicklist, const size_t fill, void *value,
+                   const size_t sz, int where);
+void quicklistAppendZiplist(quicklist *quicklist, unsigned char *zl);
+quicklist *quicklistAppendValuesFromZiplist(quicklist *quicklist,
+                                            const size_t fill,
+                                            unsigned char *zl);
+quicklist *quicklistCreateFromZiplist(size_t fill, unsigned char *zl);
+void quicklistInsertAfter(quicklist *quicklist, const size_t fill,
+                          quicklistEntry *node, void *value, const size_t sz);
+void quicklistInsertBefore(quicklist *quicklist, const size_t fill,
+                           quicklistEntry *node, void *value, const size_t sz);
+void quicklistDelEntry(quicklistIter *iter, quicklistEntry *entry);
+int quicklistReplaceAtIndex(quicklist *quicklist, long index, void *data,
+                            int sz);
+int quicklistDelRange(quicklist *quicklist, const long start, const long stop);
+quicklistIter *quicklistGetIterator(const quicklist *quicklist, int direction);
+quicklistIter *quicklistGetIteratorAtIdx(const quicklist *quicklist,
+                                         int direction, const long long idx);
+int quicklistNext(quicklistIter *iter, quicklistEntry *node);
+void quicklistReleaseIterator(quicklistIter *iter);
+quicklist *quicklistDup(quicklist *orig);
+int quicklistIndex(const quicklist *quicklist, const long long index,
+                   quicklistEntry *entry);
+void quicklistRewind(quicklist *quicklist, quicklistIter *li);
+void quicklistRewindTail(quicklist *quicklist, quicklistIter *li);
+void quicklistRotate(quicklist *quicklist, const size_t fill);
+int quicklistPopCustom(quicklist *quicklist, int where, unsigned char **data,
+                       unsigned int *sz, long long *sval,
+                       void *(*saver)(unsigned char *data, unsigned int sz));
+int quicklistPop(quicklist *quicklist, int where, unsigned char **data,
+                 unsigned int *sz, long long *slong);
+unsigned int quicklistCount(quicklist *ql);
+int quicklistCompare(unsigned char *p1, unsigned char *p2, int p2_len);
+
+#ifdef REDIS_TEST
+int quicklistTest(int argc, char *argv[]);
+#endif
+
+/* Directions for iterators */
+#define AL_START_HEAD 0
+#define AL_START_TAIL 1
+
+#endif /* __QUICKLIST_H__ */