summaryrefslogtreecommitdiffstats
path: root/src/quicklist.h
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-14 13:40:54 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-14 13:40:54 +0000
commit317c0644ccf108aa23ef3fd8358bd66c2840bfc0 (patch)
treec417b3d25c86b775989cb5ac042f37611b626c8a /src/quicklist.h
parentInitial commit. (diff)
downloadredis-317c0644ccf108aa23ef3fd8358bd66c2840bfc0.tar.xz
redis-317c0644ccf108aa23ef3fd8358bd66c2840bfc0.zip
Adding upstream version 5:7.2.4.upstream/5%7.2.4
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'src/quicklist.h')
-rw-r--r--src/quicklist.h214
1 files changed, 214 insertions, 0 deletions
diff --git a/src/quicklist.h b/src/quicklist.h
new file mode 100644
index 0000000..f17834b
--- /dev/null
+++ b/src/quicklist.h
@@ -0,0 +1,214 @@
+/* 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.
+ */
+
+#include <stdint.h> // for UINTPTR_MAX
+
+#ifndef __QUICKLIST_H__
+#define __QUICKLIST_H__
+
+/* Node, quicklist, and Iterator are the only data structures used currently. */
+
+/* quicklistNode is a 32 byte struct describing a listpack for a quicklist.
+ * We use bit fields keep the quicklistNode at 32 bytes.
+ * count: 16 bits, max 65536 (max lp bytes is 65k, so max count actually < 32k).
+ * encoding: 2 bits, RAW=1, LZF=2.
+ * container: 2 bits, PLAIN=1 (a single item as char array), PACKED=2 (listpack with multiple items).
+ * recompress: 1 bit, bool, true if node is temporary decompressed for usage.
+ * attempted_compress: 1 bit, boolean, used for verifying during testing.
+ * extra: 10 bits, free for future use; pads out the remainder of 32 bits */
+typedef struct quicklistNode {
+ struct quicklistNode *prev;
+ struct quicklistNode *next;
+ unsigned char *entry;
+ size_t sz; /* entry size in bytes */
+ unsigned int count : 16; /* count of items in listpack */
+ unsigned int encoding : 2; /* RAW==1 or LZF==2 */
+ unsigned int container : 2; /* PLAIN==1 or PACKED==2 */
+ unsigned int recompress : 1; /* was this node previous compressed? */
+ unsigned int attempted_compress : 1; /* node can't compress; too small */
+ unsigned int dont_compress : 1; /* prevent compression of entry that will be used later */
+ unsigned int extra : 9; /* more bits to steal for future usage */
+} quicklistNode;
+
+/* quicklistLZF is a 8+N byte struct holding 'sz' followed by 'compressed'.
+ * 'sz' is byte length of 'compressed' field.
+ * 'compressed' is LZF data with total (compressed) length 'sz'
+ * NOTE: uncompressed length is stored in quicklistNode->sz.
+ * When quicklistNode->entry is compressed, node->entry points to a quicklistLZF */
+typedef struct quicklistLZF {
+ size_t sz; /* LZF size in bytes*/
+ char compressed[];
+} quicklistLZF;
+
+/* Bookmarks are padded with realloc at the end of of the quicklist struct.
+ * They should only be used for very big lists if thousands of nodes were the
+ * excess memory usage is negligible, and there's a real need to iterate on them
+ * in portions.
+ * When not used, they don't add any memory overhead, but when used and then
+ * deleted, some overhead remains (to avoid resonance).
+ * The number of bookmarks used should be kept to minimum since it also adds
+ * overhead on node deletion (searching for a bookmark to update). */
+typedef struct quicklistBookmark {
+ quicklistNode *node;
+ char *name;
+} quicklistBookmark;
+
+#if UINTPTR_MAX == 0xffffffff
+/* 32-bit */
+# define QL_FILL_BITS 14
+# define QL_COMP_BITS 14
+# define QL_BM_BITS 4
+#elif UINTPTR_MAX == 0xffffffffffffffff
+/* 64-bit */
+# define QL_FILL_BITS 16
+# define QL_COMP_BITS 16
+# define QL_BM_BITS 4 /* we can encode more, but we rather limit the user
+ since they cause performance degradation. */
+#else
+# error unknown arch bits count
+#endif
+
+/* quicklist is a 40 byte struct (on 64-bit systems) describing a quicklist.
+ * 'count' is the number of total entries.
+ * 'len' is the number of quicklist nodes.
+ * 'compress' is: 0 if compression disabled, otherwise it's the number
+ * of quicklistNodes to leave uncompressed at ends of quicklist.
+ * 'fill' is the user-requested (or default) fill factor.
+ * 'bookmarks are an optional feature that is used by realloc this struct,
+ * so that they don't consume memory when not used. */
+typedef struct quicklist {
+ quicklistNode *head;
+ quicklistNode *tail;
+ unsigned long count; /* total count of all entries in all listpacks */
+ unsigned long len; /* number of quicklistNodes */
+ signed int fill : QL_FILL_BITS; /* fill factor for individual nodes */
+ unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */
+ unsigned int bookmark_count: QL_BM_BITS;
+ quicklistBookmark bookmarks[];
+} quicklist;
+
+typedef struct quicklistIter {
+ quicklist *quicklist;
+ quicklistNode *current;
+ unsigned char *zi; /* points to the current element */
+ long offset; /* offset in current listpack */
+ int direction;
+} quicklistIter;
+
+typedef struct quicklistEntry {
+ const quicklist *quicklist;
+ quicklistNode *node;
+ unsigned char *zi;
+ unsigned char *value;
+ long long longval;
+ size_t sz;
+ int offset;
+} quicklistEntry;
+
+#define QUICKLIST_HEAD 0
+#define QUICKLIST_TAIL -1
+
+/* quicklist node encodings */
+#define QUICKLIST_NODE_ENCODING_RAW 1
+#define QUICKLIST_NODE_ENCODING_LZF 2
+
+/* quicklist compression disable */
+#define QUICKLIST_NOCOMPRESS 0
+
+/* quicklist node container formats */
+#define QUICKLIST_NODE_CONTAINER_PLAIN 1
+#define QUICKLIST_NODE_CONTAINER_PACKED 2
+
+#define QL_NODE_IS_PLAIN(node) ((node)->container == QUICKLIST_NODE_CONTAINER_PLAIN)
+
+#define quicklistNodeIsCompressed(node) \
+ ((node)->encoding == QUICKLIST_NODE_ENCODING_LZF)
+
+/* Prototypes */
+quicklist *quicklistCreate(void);
+quicklist *quicklistNew(int fill, int compress);
+void quicklistSetCompressDepth(quicklist *quicklist, int depth);
+void quicklistSetFill(quicklist *quicklist, int fill);
+void quicklistSetOptions(quicklist *quicklist, int fill, int depth);
+void quicklistRelease(quicklist *quicklist);
+int quicklistPushHead(quicklist *quicklist, void *value, const size_t sz);
+int quicklistPushTail(quicklist *quicklist, void *value, const size_t sz);
+void quicklistPush(quicklist *quicklist, void *value, const size_t sz,
+ int where);
+void quicklistAppendListpack(quicklist *quicklist, unsigned char *zl);
+void quicklistAppendPlainNode(quicklist *quicklist, unsigned char *data, size_t sz);
+void quicklistInsertAfter(quicklistIter *iter, quicklistEntry *entry,
+ void *value, const size_t sz);
+void quicklistInsertBefore(quicklistIter *iter, quicklistEntry *entry,
+ void *value, const size_t sz);
+void quicklistDelEntry(quicklistIter *iter, quicklistEntry *entry);
+void quicklistReplaceEntry(quicklistIter *iter, quicklistEntry *entry,
+ void *data, size_t sz);
+int quicklistReplaceAtIndex(quicklist *quicklist, long index, void *data,
+ const size_t sz);
+int quicklistDelRange(quicklist *quicklist, const long start, const long stop);
+quicklistIter *quicklistGetIterator(quicklist *quicklist, int direction);
+quicklistIter *quicklistGetIteratorAtIdx(quicklist *quicklist,
+ int direction, const long long idx);
+quicklistIter *quicklistGetIteratorEntryAtIdx(quicklist *quicklist, const long long index,
+ quicklistEntry *entry);
+int quicklistNext(quicklistIter *iter, quicklistEntry *entry);
+void quicklistSetDirection(quicklistIter *iter, int direction);
+void quicklistReleaseIterator(quicklistIter *iter);
+quicklist *quicklistDup(quicklist *orig);
+void quicklistRotate(quicklist *quicklist);
+int quicklistPopCustom(quicklist *quicklist, int where, unsigned char **data,
+ size_t *sz, long long *sval,
+ void *(*saver)(unsigned char *data, size_t sz));
+int quicklistPop(quicklist *quicklist, int where, unsigned char **data,
+ size_t *sz, long long *slong);
+unsigned long quicklistCount(const quicklist *ql);
+int quicklistCompare(quicklistEntry *entry, unsigned char *p2, const size_t p2_len);
+size_t quicklistGetLzf(const quicklistNode *node, void **data);
+void quicklistNodeLimit(int fill, size_t *size, unsigned int *count);
+int quicklistNodeExceedsLimit(int fill, size_t new_sz, unsigned int new_count);
+void quicklistRepr(unsigned char *ql, int full);
+
+/* bookmarks */
+int quicklistBookmarkCreate(quicklist **ql_ref, const char *name, quicklistNode *node);
+int quicklistBookmarkDelete(quicklist *ql, const char *name);
+quicklistNode *quicklistBookmarkFind(quicklist *ql, const char *name);
+void quicklistBookmarksClear(quicklist *ql);
+int quicklistisSetPackedThreshold(size_t sz);
+
+#ifdef REDIS_TEST
+int quicklistTest(int argc, char *argv[], int flags);
+#endif
+
+/* Directions for iterators */
+#define AL_START_HEAD 0
+#define AL_START_TAIL 1
+
+#endif /* __QUICKLIST_H__ */