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 */ |
46 | typedef 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 : 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 */ |
64 | typedef 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). */ |
77 | typedef 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. */ |
105 | typedef 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 | |
116 | typedef 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 | |
124 | typedef 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 */ |
154 | quicklist *quicklistCreate(void); |
155 | quicklist *quicklistNew(int fill, int compress); |
156 | void quicklistSetCompressDepth(quicklist *quicklist, int depth); |
157 | void quicklistSetFill(quicklist *quicklist, int fill); |
158 | void quicklistSetOptions(quicklist *quicklist, int fill, int depth); |
159 | void quicklistRelease(quicklist *quicklist); |
160 | int quicklistPushHead(quicklist *quicklist, void *value, const size_t sz); |
161 | int quicklistPushTail(quicklist *quicklist, void *value, const size_t sz); |
162 | void quicklistPush(quicklist *quicklist, void *value, const size_t sz, |
163 | int where); |
164 | void quicklistAppendListpack(quicklist *quicklist, unsigned char *zl); |
165 | void quicklistAppendPlainNode(quicklist *quicklist, unsigned char *data, size_t sz); |
166 | void quicklistInsertAfter(quicklistIter *iter, quicklistEntry *entry, |
167 | void *value, const size_t sz); |
168 | void quicklistInsertBefore(quicklistIter *iter, quicklistEntry *entry, |
169 | void *value, const size_t sz); |
170 | void quicklistDelEntry(quicklistIter *iter, quicklistEntry *entry); |
171 | void quicklistReplaceEntry(quicklistIter *iter, quicklistEntry *entry, |
172 | void *data, size_t sz); |
173 | int quicklistReplaceAtIndex(quicklist *quicklist, long index, void *data, |
174 | const size_t sz); |
175 | int quicklistDelRange(quicklist *quicklist, const long start, const long stop); |
176 | quicklistIter *quicklistGetIterator(quicklist *quicklist, int direction); |
177 | quicklistIter *quicklistGetIteratorAtIdx(quicklist *quicklist, |
178 | int direction, const long long idx); |
179 | quicklistIter *quicklistGetIteratorEntryAtIdx(quicklist *quicklist, const long long index, |
180 | quicklistEntry *entry); |
181 | int quicklistNext(quicklistIter *iter, quicklistEntry *entry); |
182 | void quicklistSetDirection(quicklistIter *iter, int direction); |
183 | void quicklistReleaseIterator(quicklistIter *iter); |
184 | quicklist *quicklistDup(quicklist *orig); |
185 | void quicklistRotate(quicklist *quicklist); |
186 | int quicklistPopCustom(quicklist *quicklist, int where, unsigned char **data, |
187 | size_t *sz, long long *sval, |
188 | void *(*saver)(unsigned char *data, size_t sz)); |
189 | int quicklistPop(quicklist *quicklist, int where, unsigned char **data, |
190 | size_t *sz, long long *slong); |
191 | unsigned long quicklistCount(const quicklist *ql); |
192 | int quicklistCompare(quicklistEntry *entry, unsigned char *p2, const size_t p2_len); |
193 | size_t quicklistGetLzf(const quicklistNode *node, void **data); |
194 | void quicklistRepr(unsigned char *ql, int full); |
195 | |
196 | /* bookmarks */ |
197 | int quicklistBookmarkCreate(quicklist **ql_ref, const char *name, quicklistNode *node); |
198 | int quicklistBookmarkDelete(quicklist *ql, const char *name); |
199 | quicklistNode *quicklistBookmarkFind(quicklist *ql, const char *name); |
200 | void quicklistBookmarksClear(quicklist *ql); |
201 | int quicklistisSetPackedThreshold(size_t sz); |
202 | |
203 | #ifdef REDIS_TEST |
204 | int 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 | |