1/* quicklist.h - A generic doubly linked quicklist implementation
2 *
3 * Copyright (c) 2014, Matt Stancliff <[email protected]>
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are met:
8 *
9 * * Redistributions of source code must retain the above copyright notice,
10 * this quicklist of conditions and the following disclaimer.
11 * * Redistributions in binary form must reproduce the above copyright
12 * notice, this quicklist of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * * Neither the name of Redis nor the names of its contributors may be used
15 * to endorse or promote products derived from this software without
16 * specific prior written permission.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
19 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
22 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
23 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
24 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
25 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
26 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
27 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
28 * POSSIBILITY OF SUCH DAMAGE.
29 */
30
31#include <stdint.h> // for UINTPTR_MAX
32
33#ifndef __QUICKLIST_H__
34#define __QUICKLIST_H__
35
36/* Node, quicklist, and Iterator are the only data structures used currently. */
37
38/* quicklistNode is a 32 byte struct describing a listpack for a quicklist.
39 * We use bit fields keep the quicklistNode at 32 bytes.
40 * count: 16 bits, max 65536 (max lp bytes is 65k, so max count actually < 32k).
41 * encoding: 2 bits, RAW=1, LZF=2.
42 * container: 2 bits, PLAIN=1 (a single item as char array), PACKED=2 (listpack with multiple items).
43 * recompress: 1 bit, bool, true if node is temporary decompressed for usage.
44 * attempted_compress: 1 bit, boolean, used for verifying during testing.
45 * extra: 10 bits, free for future use; pads out the remainder of 32 bits */
46typedef struct quicklistNode {
47 struct quicklistNode *prev;
48 struct quicklistNode *next;
49 unsigned char *entry;
50 size_t sz; /* entry size in bytes */
51 unsigned int count : 16; /* count of items in listpack */
52 unsigned int encoding : 2; /* RAW==1 or LZF==2 */
53 unsigned int container : 2; /* PLAIN==1 or PACKED==2 */
54 unsigned int recompress : 1; /* was this node previous compressed? */
55 unsigned int attempted_compress : 1; /* node can't compress; too small */
56 unsigned int extra : 10; /* more bits to steal for future usage */
57} quicklistNode;
58
59/* quicklistLZF is a 8+N byte struct holding 'sz' followed by 'compressed'.
60 * 'sz' is byte length of 'compressed' field.
61 * 'compressed' is LZF data with total (compressed) length 'sz'
62 * NOTE: uncompressed length is stored in quicklistNode->sz.
63 * When quicklistNode->entry is compressed, node->entry points to a quicklistLZF */
64typedef struct quicklistLZF {
65 size_t sz; /* LZF size in bytes*/
66 char compressed[];
67} quicklistLZF;
68
69/* Bookmarks are padded with realloc at the end of of the quicklist struct.
70 * They should only be used for very big lists if thousands of nodes were the
71 * excess memory usage is negligible, and there's a real need to iterate on them
72 * in portions.
73 * When not used, they don't add any memory overhead, but when used and then
74 * deleted, some overhead remains (to avoid resonance).
75 * The number of bookmarks used should be kept to minimum since it also adds
76 * overhead on node deletion (searching for a bookmark to update). */
77typedef struct quicklistBookmark {
78 quicklistNode *node;
79 char *name;
80} quicklistBookmark;
81
82#if UINTPTR_MAX == 0xffffffff
83/* 32-bit */
84# define QL_FILL_BITS 14
85# define QL_COMP_BITS 14
86# define QL_BM_BITS 4
87#elif UINTPTR_MAX == 0xffffffffffffffff
88/* 64-bit */
89# define QL_FILL_BITS 16
90# define QL_COMP_BITS 16
91# define QL_BM_BITS 4 /* we can encode more, but we rather limit the user
92 since they cause performance degradation. */
93#else
94# error unknown arch bits count
95#endif
96
97/* quicklist is a 40 byte struct (on 64-bit systems) describing a quicklist.
98 * 'count' is the number of total entries.
99 * 'len' is the number of quicklist nodes.
100 * 'compress' is: 0 if compression disabled, otherwise it's the number
101 * of quicklistNodes to leave uncompressed at ends of quicklist.
102 * 'fill' is the user-requested (or default) fill factor.
103 * 'bookmarks are an optional feature that is used by realloc this struct,
104 * so that they don't consume memory when not used. */
105typedef struct quicklist {
106 quicklistNode *head;
107 quicklistNode *tail;
108 unsigned long count; /* total count of all entries in all listpacks */
109 unsigned long len; /* number of quicklistNodes */
110 signed int fill : QL_FILL_BITS; /* fill factor for individual nodes */
111 unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */
112 unsigned int bookmark_count: QL_BM_BITS;
113 quicklistBookmark bookmarks[];
114} quicklist;
115
116typedef struct quicklistIter {
117 quicklist *quicklist;
118 quicklistNode *current;
119 unsigned char *zi; /* points to the current element */
120 long offset; /* offset in current listpack */
121 int direction;
122} quicklistIter;
123
124typedef struct quicklistEntry {
125 const quicklist *quicklist;
126 quicklistNode *node;
127 unsigned char *zi;
128 unsigned char *value;
129 long long longval;
130 size_t sz;
131 int offset;
132} quicklistEntry;
133
134#define QUICKLIST_HEAD 0
135#define QUICKLIST_TAIL -1
136
137/* quicklist node encodings */
138#define QUICKLIST_NODE_ENCODING_RAW 1
139#define QUICKLIST_NODE_ENCODING_LZF 2
140
141/* quicklist compression disable */
142#define QUICKLIST_NOCOMPRESS 0
143
144/* quicklist node container formats */
145#define QUICKLIST_NODE_CONTAINER_PLAIN 1
146#define QUICKLIST_NODE_CONTAINER_PACKED 2
147
148#define QL_NODE_IS_PLAIN(node) ((node)->container == QUICKLIST_NODE_CONTAINER_PLAIN)
149
150#define quicklistNodeIsCompressed(node) \
151 ((node)->encoding == QUICKLIST_NODE_ENCODING_LZF)
152
153/* Prototypes */
154quicklist *quicklistCreate(void);
155quicklist *quicklistNew(int fill, int compress);
156void quicklistSetCompressDepth(quicklist *quicklist, int depth);
157void quicklistSetFill(quicklist *quicklist, int fill);
158void quicklistSetOptions(quicklist *quicklist, int fill, int depth);
159void quicklistRelease(quicklist *quicklist);
160int quicklistPushHead(quicklist *quicklist, void *value, const size_t sz);
161int quicklistPushTail(quicklist *quicklist, void *value, const size_t sz);
162void quicklistPush(quicklist *quicklist, void *value, const size_t sz,
163 int where);
164void quicklistAppendListpack(quicklist *quicklist, unsigned char *zl);
165void quicklistAppendPlainNode(quicklist *quicklist, unsigned char *data, size_t sz);
166void quicklistInsertAfter(quicklistIter *iter, quicklistEntry *entry,
167 void *value, const size_t sz);
168void quicklistInsertBefore(quicklistIter *iter, quicklistEntry *entry,
169 void *value, const size_t sz);
170void quicklistDelEntry(quicklistIter *iter, quicklistEntry *entry);
171void quicklistReplaceEntry(quicklistIter *iter, quicklistEntry *entry,
172 void *data, size_t sz);
173int quicklistReplaceAtIndex(quicklist *quicklist, long index, void *data,
174 const size_t sz);
175int quicklistDelRange(quicklist *quicklist, const long start, const long stop);
176quicklistIter *quicklistGetIterator(quicklist *quicklist, int direction);
177quicklistIter *quicklistGetIteratorAtIdx(quicklist *quicklist,
178 int direction, const long long idx);
179quicklistIter *quicklistGetIteratorEntryAtIdx(quicklist *quicklist, const long long index,
180 quicklistEntry *entry);
181int quicklistNext(quicklistIter *iter, quicklistEntry *entry);
182void quicklistSetDirection(quicklistIter *iter, int direction);
183void quicklistReleaseIterator(quicklistIter *iter);
184quicklist *quicklistDup(quicklist *orig);
185void quicklistRotate(quicklist *quicklist);
186int quicklistPopCustom(quicklist *quicklist, int where, unsigned char **data,
187 size_t *sz, long long *sval,
188 void *(*saver)(unsigned char *data, size_t sz));
189int quicklistPop(quicklist *quicklist, int where, unsigned char **data,
190 size_t *sz, long long *slong);
191unsigned long quicklistCount(const quicklist *ql);
192int quicklistCompare(quicklistEntry *entry, unsigned char *p2, const size_t p2_len);
193size_t quicklistGetLzf(const quicklistNode *node, void **data);
194void quicklistRepr(unsigned char *ql, int full);
195
196/* bookmarks */
197int quicklistBookmarkCreate(quicklist **ql_ref, const char *name, quicklistNode *node);
198int quicklistBookmarkDelete(quicklist *ql, const char *name);
199quicklistNode *quicklistBookmarkFind(quicklist *ql, const char *name);
200void quicklistBookmarksClear(quicklist *ql);
201int quicklistisSetPackedThreshold(size_t sz);
202
203#ifdef REDIS_TEST
204int quicklistTest(int argc, char *argv[], int flags);
205#endif
206
207/* Directions for iterators */
208#define AL_START_HEAD 0
209#define AL_START_TAIL 1
210
211#endif /* __QUICKLIST_H__ */
212