File: | src/quicklist.c |
Warning: | line 722, column 34 Access to field 'zl' results in a dereference of a null pointer (loaded from variable 'keep') |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | /* quicklist.c - A doubly linked list of ziplists | ||||
2 | * | ||||
3 | * Copyright (c) 2014, Matt Stancliff <matt@genges.com> | ||||
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 start 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 <string.h> /* for memcpy */ | ||||
32 | #include "quicklist.h" | ||||
33 | #include "zmalloc.h" | ||||
34 | #include "config.h" | ||||
35 | #include "ziplist.h" | ||||
36 | #include "util.h" /* for ll2string */ | ||||
37 | #include "lzf.h" | ||||
38 | #include "redisassert.h" | ||||
39 | |||||
40 | #if defined(REDIS_TEST) || defined(REDIS_TEST_VERBOSE) | ||||
41 | #include <stdio.h> /* for printf (debug printing), snprintf (genstr) */ | ||||
42 | #endif | ||||
43 | |||||
44 | #ifndef REDIS_STATIC | ||||
45 | #define REDIS_STATIC static | ||||
46 | #endif | ||||
47 | |||||
48 | /* Optimization levels for size-based filling */ | ||||
49 | static const size_t optimization_level[] = {4096, 8192, 16384, 32768, 65536}; | ||||
50 | |||||
51 | /* Maximum size in bytes of any multi-element ziplist. | ||||
52 | * Larger values will live in their own isolated ziplists. */ | ||||
53 | #define SIZE_SAFETY_LIMIT8192 8192 | ||||
54 | |||||
55 | /* Minimum ziplist size in bytes for attempting compression. */ | ||||
56 | #define MIN_COMPRESS_BYTES48 48 | ||||
57 | |||||
58 | /* Minimum size reduction in bytes to store compressed quicklistNode data. | ||||
59 | * This also prevents us from storing compression if the compression | ||||
60 | * resulted in a larger size than the original data. */ | ||||
61 | #define MIN_COMPRESS_IMPROVE8 8 | ||||
62 | |||||
63 | /* If not verbose testing, remove all debug printing. */ | ||||
64 | #ifndef REDIS_TEST_VERBOSE | ||||
65 | #define D(...) | ||||
66 | #else | ||||
67 | #define D(...) \ | ||||
68 | do { \ | ||||
69 | printf("%s:%s:%d:\t", __FILE__"quicklist.c", __func__, __LINE__69); \ | ||||
70 | printf(__VA_ARGS__); \ | ||||
71 | printf("\n"); \ | ||||
72 | } while (0) | ||||
73 | #endif | ||||
74 | |||||
75 | /* Bookmarks forward declarations */ | ||||
76 | #define QL_MAX_BM((1 << 4)-1) ((1 << QL_BM_BITS4)-1) | ||||
77 | quicklistBookmark *_quicklistBookmarkFindByName(quicklist *ql, const char *name); | ||||
78 | quicklistBookmark *_quicklistBookmarkFindByNode(quicklist *ql, quicklistNode *node); | ||||
79 | void _quicklistBookmarkDelete(quicklist *ql, quicklistBookmark *bm); | ||||
80 | |||||
81 | /* Simple way to give quicklistEntry structs default values with one call. */ | ||||
82 | #define initEntry(e)do { (e)->zi = (e)->value = ((void*)0); (e)->longval = -123456789; (e)->quicklist = ((void*)0); (e)->node = ((void*)0); (e)->offset = 123456789; (e)->sz = 0; } while (0) \ | ||||
83 | do { \ | ||||
84 | (e)->zi = (e)->value = NULL((void*)0); \ | ||||
85 | (e)->longval = -123456789; \ | ||||
86 | (e)->quicklist = NULL((void*)0); \ | ||||
87 | (e)->node = NULL((void*)0); \ | ||||
88 | (e)->offset = 123456789; \ | ||||
89 | (e)->sz = 0; \ | ||||
90 | } while (0) | ||||
91 | |||||
92 | /* Create a new quicklist. | ||||
93 | * Free with quicklistRelease(). */ | ||||
94 | quicklist *quicklistCreate(void) { | ||||
95 | struct quicklist *quicklist; | ||||
96 | |||||
97 | quicklist = zmalloc(sizeof(*quicklist)); | ||||
98 | quicklist->head = quicklist->tail = NULL((void*)0); | ||||
99 | quicklist->len = 0; | ||||
100 | quicklist->count = 0; | ||||
101 | quicklist->compress = 0; | ||||
102 | quicklist->fill = -2; | ||||
103 | quicklist->bookmark_count = 0; | ||||
104 | return quicklist; | ||||
105 | } | ||||
106 | |||||
107 | #define COMPRESS_MAX((1 << 16)-1) ((1 << QL_COMP_BITS16)-1) | ||||
108 | void quicklistSetCompressDepth(quicklist *quicklist, int compress) { | ||||
109 | if (compress > COMPRESS_MAX((1 << 16)-1)) { | ||||
110 | compress = COMPRESS_MAX((1 << 16)-1); | ||||
111 | } else if (compress < 0) { | ||||
112 | compress = 0; | ||||
113 | } | ||||
114 | quicklist->compress = compress; | ||||
115 | } | ||||
116 | |||||
117 | #define FILL_MAX((1 << (16 -1))-1) ((1 << (QL_FILL_BITS16-1))-1) | ||||
118 | void quicklistSetFill(quicklist *quicklist, int fill) { | ||||
119 | if (fill > FILL_MAX((1 << (16 -1))-1)) { | ||||
120 | fill = FILL_MAX((1 << (16 -1))-1); | ||||
121 | } else if (fill < -5) { | ||||
122 | fill = -5; | ||||
123 | } | ||||
124 | quicklist->fill = fill; | ||||
125 | } | ||||
126 | |||||
127 | void quicklistSetOptions(quicklist *quicklist, int fill, int depth) { | ||||
128 | quicklistSetFill(quicklist, fill); | ||||
129 | quicklistSetCompressDepth(quicklist, depth); | ||||
130 | } | ||||
131 | |||||
132 | /* Create a new quicklist with some default parameters. */ | ||||
133 | quicklist *quicklistNew(int fill, int compress) { | ||||
134 | quicklist *quicklist = quicklistCreate(); | ||||
135 | quicklistSetOptions(quicklist, fill, compress); | ||||
136 | return quicklist; | ||||
137 | } | ||||
138 | |||||
139 | REDIS_STATIC quicklistNode *quicklistCreateNode(void) { | ||||
140 | quicklistNode *node; | ||||
141 | node = zmalloc(sizeof(*node)); | ||||
142 | node->zl = NULL((void*)0); | ||||
143 | node->count = 0; | ||||
144 | node->sz = 0; | ||||
145 | node->next = node->prev = NULL((void*)0); | ||||
146 | node->encoding = QUICKLIST_NODE_ENCODING_RAW1; | ||||
147 | node->container = QUICKLIST_NODE_CONTAINER_ZIPLIST2; | ||||
148 | node->recompress = 0; | ||||
149 | return node; | ||||
150 | } | ||||
151 | |||||
152 | /* Return cached quicklist count */ | ||||
153 | unsigned long quicklistCount(const quicklist *ql) { return ql->count; } | ||||
154 | |||||
155 | /* Free entire quicklist. */ | ||||
156 | void quicklistRelease(quicklist *quicklist) { | ||||
157 | unsigned long len; | ||||
158 | quicklistNode *current, *next; | ||||
159 | |||||
160 | current = quicklist->head; | ||||
161 | len = quicklist->len; | ||||
162 | while (len--) { | ||||
163 | next = current->next; | ||||
164 | |||||
165 | zfree(current->zl); | ||||
166 | quicklist->count -= current->count; | ||||
167 | |||||
168 | zfree(current); | ||||
169 | |||||
170 | quicklist->len--; | ||||
171 | current = next; | ||||
172 | } | ||||
173 | quicklistBookmarksClear(quicklist); | ||||
174 | zfree(quicklist); | ||||
175 | } | ||||
176 | |||||
177 | /* Compress the ziplist in 'node' and update encoding details. | ||||
178 | * Returns 1 if ziplist compressed successfully. | ||||
179 | * Returns 0 if compression failed or if ziplist too small to compress. */ | ||||
180 | REDIS_STATIC int __quicklistCompressNode(quicklistNode *node) { | ||||
181 | #ifdef REDIS_TEST | ||||
182 | node->attempted_compress = 1; | ||||
183 | #endif | ||||
184 | |||||
185 | /* Don't bother compressing small values */ | ||||
186 | if (node->sz < MIN_COMPRESS_BYTES48) | ||||
187 | return 0; | ||||
188 | |||||
189 | quicklistLZF *lzf = zmalloc(sizeof(*lzf) + node->sz); | ||||
190 | |||||
191 | /* Cancel if compression fails or doesn't compress small enough */ | ||||
192 | if (((lzf->sz = lzf_compress(node->zl, node->sz, lzf->compressed, | ||||
193 | node->sz)) == 0) || | ||||
194 | lzf->sz + MIN_COMPRESS_IMPROVE8 >= node->sz) { | ||||
195 | /* lzf_compress aborts/rejects compression if value not compressable. */ | ||||
196 | zfree(lzf); | ||||
197 | return 0; | ||||
198 | } | ||||
199 | lzf = zrealloc(lzf, sizeof(*lzf) + lzf->sz); | ||||
200 | zfree(node->zl); | ||||
201 | node->zl = (unsigned char *)lzf; | ||||
202 | node->encoding = QUICKLIST_NODE_ENCODING_LZF2; | ||||
203 | node->recompress = 0; | ||||
204 | return 1; | ||||
205 | } | ||||
206 | |||||
207 | /* Compress only uncompressed nodes. */ | ||||
208 | #define quicklistCompressNode(_node)do { if ((_node) && (_node)->encoding == 1) { __quicklistCompressNode ((_node)); } } while (0) \ | ||||
209 | do { \ | ||||
210 | if ((_node) && (_node)->encoding == QUICKLIST_NODE_ENCODING_RAW1) { \ | ||||
211 | __quicklistCompressNode((_node)); \ | ||||
212 | } \ | ||||
213 | } while (0) | ||||
214 | |||||
215 | /* Uncompress the ziplist in 'node' and update encoding details. | ||||
216 | * Returns 1 on successful decode, 0 on failure to decode. */ | ||||
217 | REDIS_STATIC int __quicklistDecompressNode(quicklistNode *node) { | ||||
218 | #ifdef REDIS_TEST | ||||
219 | node->attempted_compress = 0; | ||||
220 | #endif | ||||
221 | |||||
222 | void *decompressed = zmalloc(node->sz); | ||||
223 | quicklistLZF *lzf = (quicklistLZF *)node->zl; | ||||
224 | if (lzf_decompress(lzf->compressed, lzf->sz, decompressed, node->sz) == 0) { | ||||
225 | /* Someone requested decompress, but we can't decompress. Not good. */ | ||||
226 | zfree(decompressed); | ||||
227 | return 0; | ||||
228 | } | ||||
229 | zfree(lzf); | ||||
230 | node->zl = decompressed; | ||||
231 | node->encoding = QUICKLIST_NODE_ENCODING_RAW1; | ||||
232 | return 1; | ||||
233 | } | ||||
234 | |||||
235 | /* Decompress only compressed nodes. */ | ||||
236 | #define quicklistDecompressNode(_node)do { if ((_node) && (_node)->encoding == 2) { __quicklistDecompressNode ((_node)); } } while (0) \ | ||||
237 | do { \ | ||||
238 | if ((_node) && (_node)->encoding == QUICKLIST_NODE_ENCODING_LZF2) { \ | ||||
239 | __quicklistDecompressNode((_node)); \ | ||||
240 | } \ | ||||
241 | } while (0) | ||||
242 | |||||
243 | /* Force node to not be immediately re-compresable */ | ||||
244 | #define quicklistDecompressNodeForUse(_node)do { if ((_node) && (_node)->encoding == 2) { __quicklistDecompressNode ((_node)); (_node)->recompress = 1; } } while (0) \ | ||||
245 | do { \ | ||||
246 | if ((_node) && (_node)->encoding == QUICKLIST_NODE_ENCODING_LZF2) { \ | ||||
247 | __quicklistDecompressNode((_node)); \ | ||||
248 | (_node)->recompress = 1; \ | ||||
249 | } \ | ||||
250 | } while (0) | ||||
251 | |||||
252 | /* Extract the raw LZF data from this quicklistNode. | ||||
253 | * Pointer to LZF data is assigned to '*data'. | ||||
254 | * Return value is the length of compressed LZF data. */ | ||||
255 | size_t quicklistGetLzf(const quicklistNode *node, void **data) { | ||||
256 | quicklistLZF *lzf = (quicklistLZF *)node->zl; | ||||
257 | *data = lzf->compressed; | ||||
258 | return lzf->sz; | ||||
259 | } | ||||
260 | |||||
261 | #define quicklistAllowsCompression(_ql)((_ql)->compress != 0) ((_ql)->compress != 0) | ||||
262 | |||||
263 | /* Force 'quicklist' to meet compression guidelines set by compress depth. | ||||
264 | * The only way to guarantee interior nodes get compressed is to iterate | ||||
265 | * to our "interior" compress depth then compress the next node we find. | ||||
266 | * If compress depth is larger than the entire list, we return immediately. */ | ||||
267 | REDIS_STATIC void __quicklistCompress(const quicklist *quicklist, | ||||
268 | quicklistNode *node) { | ||||
269 | /* If length is less than our compress depth (from both sides), | ||||
270 | * we can't compress anything. */ | ||||
271 | if (!quicklistAllowsCompression(quicklist)((quicklist)->compress != 0) || | ||||
272 | quicklist->len < (unsigned int)(quicklist->compress * 2)) | ||||
273 | return; | ||||
274 | |||||
275 | #if 0 | ||||
276 | /* Optimized cases for small depth counts */ | ||||
277 | if (quicklist->compress == 1) { | ||||
278 | quicklistNode *h = quicklist->head, *t = quicklist->tail; | ||||
279 | quicklistDecompressNode(h)do { if ((h) && (h)->encoding == 2) { __quicklistDecompressNode ((h)); } } while (0); | ||||
280 | quicklistDecompressNode(t)do { if ((t) && (t)->encoding == 2) { __quicklistDecompressNode ((t)); } } while (0); | ||||
281 | if (h != node && t != node) | ||||
282 | quicklistCompressNode(node)do { if ((node) && (node)->encoding == 1) { __quicklistCompressNode ((node)); } } while (0); | ||||
283 | return; | ||||
284 | } else if (quicklist->compress == 2) { | ||||
285 | quicklistNode *h = quicklist->head, *hn = h->next, *hnn = hn->next; | ||||
286 | quicklistNode *t = quicklist->tail, *tp = t->prev, *tpp = tp->prev; | ||||
287 | quicklistDecompressNode(h)do { if ((h) && (h)->encoding == 2) { __quicklistDecompressNode ((h)); } } while (0); | ||||
288 | quicklistDecompressNode(hn)do { if ((hn) && (hn)->encoding == 2) { __quicklistDecompressNode ((hn)); } } while (0); | ||||
289 | quicklistDecompressNode(t)do { if ((t) && (t)->encoding == 2) { __quicklistDecompressNode ((t)); } } while (0); | ||||
290 | quicklistDecompressNode(tp)do { if ((tp) && (tp)->encoding == 2) { __quicklistDecompressNode ((tp)); } } while (0); | ||||
291 | if (h != node && hn != node && t != node && tp != node) { | ||||
292 | quicklistCompressNode(node)do { if ((node) && (node)->encoding == 1) { __quicklistCompressNode ((node)); } } while (0); | ||||
293 | } | ||||
294 | if (hnn != t) { | ||||
295 | quicklistCompressNode(hnn)do { if ((hnn) && (hnn)->encoding == 1) { __quicklistCompressNode ((hnn)); } } while (0); | ||||
296 | } | ||||
297 | if (tpp != h) { | ||||
298 | quicklistCompressNode(tpp)do { if ((tpp) && (tpp)->encoding == 1) { __quicklistCompressNode ((tpp)); } } while (0); | ||||
299 | } | ||||
300 | return; | ||||
301 | } | ||||
302 | #endif | ||||
303 | |||||
304 | /* Iterate until we reach compress depth for both sides of the list.a | ||||
305 | * Note: because we do length checks at the *top* of this function, | ||||
306 | * we can skip explicit null checks below. Everything exists. */ | ||||
307 | quicklistNode *forward = quicklist->head; | ||||
308 | quicklistNode *reverse = quicklist->tail; | ||||
309 | int depth = 0; | ||||
310 | int in_depth = 0; | ||||
311 | while (depth++ < quicklist->compress) { | ||||
312 | quicklistDecompressNode(forward)do { if ((forward) && (forward)->encoding == 2) { __quicklistDecompressNode ((forward)); } } while (0); | ||||
313 | quicklistDecompressNode(reverse)do { if ((reverse) && (reverse)->encoding == 2) { __quicklistDecompressNode ((reverse)); } } while (0); | ||||
314 | |||||
315 | if (forward == node || reverse == node) | ||||
316 | in_depth = 1; | ||||
317 | |||||
318 | if (forward == reverse) | ||||
319 | return; | ||||
320 | |||||
321 | forward = forward->next; | ||||
322 | reverse = reverse->prev; | ||||
323 | } | ||||
324 | |||||
325 | if (!in_depth) | ||||
326 | quicklistCompressNode(node)do { if ((node) && (node)->encoding == 1) { __quicklistCompressNode ((node)); } } while (0); | ||||
327 | |||||
328 | if (depth > 2) { | ||||
329 | /* At this point, forward and reverse are one node beyond depth */ | ||||
330 | quicklistCompressNode(forward)do { if ((forward) && (forward)->encoding == 1) { __quicklistCompressNode ((forward)); } } while (0); | ||||
331 | quicklistCompressNode(reverse)do { if ((reverse) && (reverse)->encoding == 1) { __quicklistCompressNode ((reverse)); } } while (0); | ||||
332 | } | ||||
333 | } | ||||
334 | |||||
335 | #define quicklistCompress(_ql, _node)do { if ((_node)->recompress) do { if (((_node)) && ((_node))->encoding == 1) { __quicklistCompressNode(((_node ))); } } while (0); else __quicklistCompress((_ql), (_node)); } while (0) \ | ||||
336 | do { \ | ||||
337 | if ((_node)->recompress) \ | ||||
338 | quicklistCompressNode((_node))do { if (((_node)) && ((_node))->encoding == 1) { __quicklistCompressNode (((_node))); } } while (0); \ | ||||
339 | else \ | ||||
340 | __quicklistCompress((_ql), (_node)); \ | ||||
341 | } while (0) | ||||
342 | |||||
343 | /* If we previously used quicklistDecompressNodeForUse(), just recompress. */ | ||||
344 | #define quicklistRecompressOnly(_ql, _node)do { if ((_node)->recompress) do { if (((_node)) && ((_node))->encoding == 1) { __quicklistCompressNode(((_node ))); } } while (0); } while (0) \ | ||||
345 | do { \ | ||||
346 | if ((_node)->recompress) \ | ||||
347 | quicklistCompressNode((_node))do { if (((_node)) && ((_node))->encoding == 1) { __quicklistCompressNode (((_node))); } } while (0); \ | ||||
348 | } while (0) | ||||
349 | |||||
350 | /* Insert 'new_node' after 'old_node' if 'after' is 1. | ||||
351 | * Insert 'new_node' before 'old_node' if 'after' is 0. | ||||
352 | * Note: 'new_node' is *always* uncompressed, so if we assign it to | ||||
353 | * head or tail, we do not need to uncompress it. */ | ||||
354 | REDIS_STATIC void __quicklistInsertNode(quicklist *quicklist, | ||||
355 | quicklistNode *old_node, | ||||
356 | quicklistNode *new_node, int after) { | ||||
357 | if (after) { | ||||
358 | new_node->prev = old_node; | ||||
359 | if (old_node) { | ||||
360 | new_node->next = old_node->next; | ||||
361 | if (old_node->next) | ||||
362 | old_node->next->prev = new_node; | ||||
363 | old_node->next = new_node; | ||||
364 | } | ||||
365 | if (quicklist->tail == old_node) | ||||
366 | quicklist->tail = new_node; | ||||
367 | } else { | ||||
368 | new_node->next = old_node; | ||||
369 | if (old_node) { | ||||
370 | new_node->prev = old_node->prev; | ||||
371 | if (old_node->prev) | ||||
372 | old_node->prev->next = new_node; | ||||
373 | old_node->prev = new_node; | ||||
374 | } | ||||
375 | if (quicklist->head == old_node) | ||||
376 | quicklist->head = new_node; | ||||
377 | } | ||||
378 | /* If this insert creates the only element so far, initialize head/tail. */ | ||||
379 | if (quicklist->len == 0) { | ||||
380 | quicklist->head = quicklist->tail = new_node; | ||||
381 | } | ||||
382 | |||||
383 | if (old_node) | ||||
384 | quicklistCompress(quicklist, old_node)do { if ((old_node)->recompress) do { if (((old_node)) && ((old_node))->encoding == 1) { __quicklistCompressNode((( old_node))); } } while (0); else __quicklistCompress((quicklist ), (old_node)); } while (0); | ||||
385 | |||||
386 | quicklist->len++; | ||||
387 | } | ||||
388 | |||||
389 | /* Wrappers for node inserting around existing node. */ | ||||
390 | REDIS_STATIC void _quicklistInsertNodeBefore(quicklist *quicklist, | ||||
391 | quicklistNode *old_node, | ||||
392 | quicklistNode *new_node) { | ||||
393 | __quicklistInsertNode(quicklist, old_node, new_node, 0); | ||||
394 | } | ||||
395 | |||||
396 | REDIS_STATIC void _quicklistInsertNodeAfter(quicklist *quicklist, | ||||
397 | quicklistNode *old_node, | ||||
398 | quicklistNode *new_node) { | ||||
399 | __quicklistInsertNode(quicklist, old_node, new_node, 1); | ||||
400 | } | ||||
401 | |||||
402 | REDIS_STATIC int | ||||
403 | _quicklistNodeSizeMeetsOptimizationRequirement(const size_t sz, | ||||
404 | const int fill) { | ||||
405 | if (fill >= 0) | ||||
406 | return 0; | ||||
407 | |||||
408 | size_t offset = (-fill) - 1; | ||||
409 | if (offset < (sizeof(optimization_level) / sizeof(*optimization_level))) { | ||||
410 | if (sz <= optimization_level[offset]) { | ||||
411 | return 1; | ||||
412 | } else { | ||||
413 | return 0; | ||||
414 | } | ||||
415 | } else { | ||||
416 | return 0; | ||||
417 | } | ||||
418 | } | ||||
419 | |||||
420 | #define sizeMeetsSafetyLimit(sz)((sz) <= 8192) ((sz) <= SIZE_SAFETY_LIMIT8192) | ||||
421 | |||||
422 | REDIS_STATIC int _quicklistNodeAllowInsert(const quicklistNode *node, | ||||
423 | const int fill, const size_t sz) { | ||||
424 | if (unlikely(!node)__builtin_expect(!!(!node), 0)) | ||||
425 | return 0; | ||||
426 | |||||
427 | int ziplist_overhead; | ||||
428 | /* size of previous offset */ | ||||
429 | if (sz < 254) | ||||
430 | ziplist_overhead = 1; | ||||
431 | else | ||||
432 | ziplist_overhead = 5; | ||||
433 | |||||
434 | /* size of forward offset */ | ||||
435 | if (sz < 64) | ||||
436 | ziplist_overhead += 1; | ||||
437 | else if (likely(sz < 16384)__builtin_expect(!!(sz < 16384), 1)) | ||||
438 | ziplist_overhead += 2; | ||||
439 | else | ||||
440 | ziplist_overhead += 5; | ||||
441 | |||||
442 | /* new_sz overestimates if 'sz' encodes to an integer type */ | ||||
443 | unsigned int new_sz = node->sz + sz + ziplist_overhead; | ||||
444 | if (likely(_quicklistNodeSizeMeetsOptimizationRequirement(new_sz, fill))__builtin_expect(!!(_quicklistNodeSizeMeetsOptimizationRequirement (new_sz, fill)), 1)) | ||||
445 | return 1; | ||||
446 | else if (!sizeMeetsSafetyLimit(new_sz)((new_sz) <= 8192)) | ||||
447 | return 0; | ||||
448 | else if ((int)node->count < fill) | ||||
449 | return 1; | ||||
450 | else | ||||
451 | return 0; | ||||
452 | } | ||||
453 | |||||
454 | REDIS_STATIC int _quicklistNodeAllowMerge(const quicklistNode *a, | ||||
455 | const quicklistNode *b, | ||||
456 | const int fill) { | ||||
457 | if (!a || !b) | ||||
458 | return 0; | ||||
459 | |||||
460 | /* approximate merged ziplist size (- 11 to remove one ziplist | ||||
461 | * header/trailer) */ | ||||
462 | unsigned int merge_sz = a->sz + b->sz - 11; | ||||
463 | if (likely(_quicklistNodeSizeMeetsOptimizationRequirement(merge_sz, fill))__builtin_expect(!!(_quicklistNodeSizeMeetsOptimizationRequirement (merge_sz, fill)), 1)) | ||||
464 | return 1; | ||||
465 | else if (!sizeMeetsSafetyLimit(merge_sz)((merge_sz) <= 8192)) | ||||
466 | return 0; | ||||
467 | else if ((int)(a->count + b->count) <= fill) | ||||
468 | return 1; | ||||
469 | else | ||||
470 | return 0; | ||||
471 | } | ||||
472 | |||||
473 | #define quicklistNodeUpdateSz(node)do { (node)->sz = ziplistBlobLen((node)->zl); } while ( 0) \ | ||||
474 | do { \ | ||||
475 | (node)->sz = ziplistBlobLen((node)->zl); \ | ||||
476 | } while (0) | ||||
477 | |||||
478 | /* Add new entry to head node of quicklist. | ||||
479 | * | ||||
480 | * Returns 0 if used existing head. | ||||
481 | * Returns 1 if new head created. */ | ||||
482 | int quicklistPushHead(quicklist *quicklist, void *value, size_t sz) { | ||||
483 | quicklistNode *orig_head = quicklist->head; | ||||
484 | if (likely(__builtin_expect(!!(_quicklistNodeAllowInsert(quicklist->head , quicklist->fill, sz)), 1) | ||||
485 | _quicklistNodeAllowInsert(quicklist->head, quicklist->fill, sz))__builtin_expect(!!(_quicklistNodeAllowInsert(quicklist->head , quicklist->fill, sz)), 1)) { | ||||
486 | quicklist->head->zl = | ||||
487 | ziplistPush(quicklist->head->zl, value, sz, ZIPLIST_HEAD0); | ||||
488 | quicklistNodeUpdateSz(quicklist->head)do { (quicklist->head)->sz = ziplistBlobLen((quicklist-> head)->zl); } while (0); | ||||
489 | } else { | ||||
490 | quicklistNode *node = quicklistCreateNode(); | ||||
491 | node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_HEAD0); | ||||
492 | |||||
493 | quicklistNodeUpdateSz(node)do { (node)->sz = ziplistBlobLen((node)->zl); } while ( 0); | ||||
494 | _quicklistInsertNodeBefore(quicklist, quicklist->head, node); | ||||
495 | } | ||||
496 | quicklist->count++; | ||||
497 | quicklist->head->count++; | ||||
498 | return (orig_head != quicklist->head); | ||||
499 | } | ||||
500 | |||||
501 | /* Add new entry to tail node of quicklist. | ||||
502 | * | ||||
503 | * Returns 0 if used existing tail. | ||||
504 | * Returns 1 if new tail created. */ | ||||
505 | int quicklistPushTail(quicklist *quicklist, void *value, size_t sz) { | ||||
506 | quicklistNode *orig_tail = quicklist->tail; | ||||
507 | if (likely(__builtin_expect(!!(_quicklistNodeAllowInsert(quicklist->tail , quicklist->fill, sz)), 1) | ||||
508 | _quicklistNodeAllowInsert(quicklist->tail, quicklist->fill, sz))__builtin_expect(!!(_quicklistNodeAllowInsert(quicklist->tail , quicklist->fill, sz)), 1)) { | ||||
509 | quicklist->tail->zl = | ||||
510 | ziplistPush(quicklist->tail->zl, value, sz, ZIPLIST_TAIL1); | ||||
511 | quicklistNodeUpdateSz(quicklist->tail)do { (quicklist->tail)->sz = ziplistBlobLen((quicklist-> tail)->zl); } while (0); | ||||
512 | } else { | ||||
513 | quicklistNode *node = quicklistCreateNode(); | ||||
514 | node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_TAIL1); | ||||
515 | |||||
516 | quicklistNodeUpdateSz(node)do { (node)->sz = ziplistBlobLen((node)->zl); } while ( 0); | ||||
517 | _quicklistInsertNodeAfter(quicklist, quicklist->tail, node); | ||||
518 | } | ||||
519 | quicklist->count++; | ||||
520 | quicklist->tail->count++; | ||||
521 | return (orig_tail != quicklist->tail); | ||||
522 | } | ||||
523 | |||||
524 | /* Create new node consisting of a pre-formed ziplist. | ||||
525 | * Used for loading RDBs where entire ziplists have been stored | ||||
526 | * to be retrieved later. */ | ||||
527 | void quicklistAppendZiplist(quicklist *quicklist, unsigned char *zl) { | ||||
528 | quicklistNode *node = quicklistCreateNode(); | ||||
529 | |||||
530 | node->zl = zl; | ||||
531 | node->count = ziplistLen(node->zl); | ||||
532 | node->sz = ziplistBlobLen(zl); | ||||
533 | |||||
534 | _quicklistInsertNodeAfter(quicklist, quicklist->tail, node); | ||||
535 | quicklist->count += node->count; | ||||
536 | } | ||||
537 | |||||
538 | /* Append all values of ziplist 'zl' individually into 'quicklist'. | ||||
539 | * | ||||
540 | * This allows us to restore old RDB ziplists into new quicklists | ||||
541 | * with smaller ziplist sizes than the saved RDB ziplist. | ||||
542 | * | ||||
543 | * Returns 'quicklist' argument. Frees passed-in ziplist 'zl' */ | ||||
544 | quicklist *quicklistAppendValuesFromZiplist(quicklist *quicklist, | ||||
545 | unsigned char *zl) { | ||||
546 | unsigned char *value; | ||||
547 | unsigned int sz; | ||||
548 | long long longval; | ||||
549 | char longstr[32] = {0}; | ||||
550 | |||||
551 | unsigned char *p = ziplistIndex(zl, 0); | ||||
552 | while (ziplistGet(p, &value, &sz, &longval)) { | ||||
553 | if (!value) { | ||||
554 | /* Write the longval as a string so we can re-add it */ | ||||
555 | sz = ll2string(longstr, sizeof(longstr), longval); | ||||
556 | value = (unsigned char *)longstr; | ||||
557 | } | ||||
558 | quicklistPushTail(quicklist, value, sz); | ||||
559 | p = ziplistNext(zl, p); | ||||
560 | } | ||||
561 | zfree(zl); | ||||
562 | return quicklist; | ||||
563 | } | ||||
564 | |||||
565 | /* Create new (potentially multi-node) quicklist from a single existing ziplist. | ||||
566 | * | ||||
567 | * Returns new quicklist. Frees passed-in ziplist 'zl'. */ | ||||
568 | quicklist *quicklistCreateFromZiplist(int fill, int compress, | ||||
569 | unsigned char *zl) { | ||||
570 | return quicklistAppendValuesFromZiplist(quicklistNew(fill, compress), zl); | ||||
571 | } | ||||
572 | |||||
573 | #define quicklistDeleteIfEmpty(ql, n)do { if ((n)->count == 0) { __quicklistDelNode((ql), (n)); (n) = ((void*)0); } } while (0) \ | ||||
574 | do { \ | ||||
575 | if ((n)->count == 0) { \ | ||||
576 | __quicklistDelNode((ql), (n)); \ | ||||
577 | (n) = NULL((void*)0); \ | ||||
578 | } \ | ||||
579 | } while (0) | ||||
580 | |||||
581 | REDIS_STATIC void __quicklistDelNode(quicklist *quicklist, | ||||
582 | quicklistNode *node) { | ||||
583 | /* Update the bookmark if any */ | ||||
584 | quicklistBookmark *bm = _quicklistBookmarkFindByNode(quicklist, node); | ||||
585 | if (bm) { | ||||
586 | bm->node = node->next; | ||||
587 | /* if the bookmark was to the last node, delete it. */ | ||||
588 | if (!bm->node) | ||||
589 | _quicklistBookmarkDelete(quicklist, bm); | ||||
590 | } | ||||
591 | |||||
592 | if (node->next) | ||||
593 | node->next->prev = node->prev; | ||||
594 | if (node->prev) | ||||
595 | node->prev->next = node->next; | ||||
596 | |||||
597 | if (node == quicklist->tail) { | ||||
598 | quicklist->tail = node->prev; | ||||
599 | } | ||||
600 | |||||
601 | if (node == quicklist->head) { | ||||
602 | quicklist->head = node->next; | ||||
603 | } | ||||
604 | |||||
605 | /* If we deleted a node within our compress depth, we | ||||
606 | * now have compressed nodes needing to be decompressed. */ | ||||
607 | __quicklistCompress(quicklist, NULL((void*)0)); | ||||
608 | |||||
609 | quicklist->count -= node->count; | ||||
610 | |||||
611 | zfree(node->zl); | ||||
612 | zfree(node); | ||||
613 | quicklist->len--; | ||||
614 | } | ||||
615 | |||||
616 | /* Delete one entry from list given the node for the entry and a pointer | ||||
617 | * to the entry in the node. | ||||
618 | * | ||||
619 | * Note: quicklistDelIndex() *requires* uncompressed nodes because you | ||||
620 | * already had to get *p from an uncompressed node somewhere. | ||||
621 | * | ||||
622 | * Returns 1 if the entire node was deleted, 0 if node still exists. | ||||
623 | * Also updates in/out param 'p' with the next offset in the ziplist. */ | ||||
624 | REDIS_STATIC int quicklistDelIndex(quicklist *quicklist, quicklistNode *node, | ||||
625 | unsigned char **p) { | ||||
626 | int gone = 0; | ||||
627 | |||||
628 | node->zl = ziplistDelete(node->zl, p); | ||||
629 | node->count--; | ||||
630 | if (node->count == 0) { | ||||
631 | gone = 1; | ||||
632 | __quicklistDelNode(quicklist, node); | ||||
633 | } else { | ||||
634 | quicklistNodeUpdateSz(node)do { (node)->sz = ziplistBlobLen((node)->zl); } while ( 0); | ||||
635 | } | ||||
636 | quicklist->count--; | ||||
637 | /* If we deleted the node, the original node is no longer valid */ | ||||
638 | return gone ? 1 : 0; | ||||
639 | } | ||||
640 | |||||
641 | /* Delete one element represented by 'entry' | ||||
642 | * | ||||
643 | * 'entry' stores enough metadata to delete the proper position in | ||||
644 | * the correct ziplist in the correct quicklist node. */ | ||||
645 | void quicklistDelEntry(quicklistIter *iter, quicklistEntry *entry) { | ||||
646 | quicklistNode *prev = entry->node->prev; | ||||
647 | quicklistNode *next = entry->node->next; | ||||
648 | int deleted_node = quicklistDelIndex((quicklist *)entry->quicklist, | ||||
649 | entry->node, &entry->zi); | ||||
650 | |||||
651 | /* after delete, the zi is now invalid for any future usage. */ | ||||
652 | iter->zi = NULL((void*)0); | ||||
653 | |||||
654 | /* If current node is deleted, we must update iterator node and offset. */ | ||||
655 | if (deleted_node) { | ||||
656 | if (iter->direction == AL_START_HEAD0) { | ||||
657 | iter->current = next; | ||||
658 | iter->offset = 0; | ||||
659 | } else if (iter->direction == AL_START_TAIL1) { | ||||
660 | iter->current = prev; | ||||
661 | iter->offset = -1; | ||||
662 | } | ||||
663 | } | ||||
664 | /* else if (!deleted_node), no changes needed. | ||||
665 | * we already reset iter->zi above, and the existing iter->offset | ||||
666 | * doesn't move again because: | ||||
667 | * - [1, 2, 3] => delete offset 1 => [1, 3]: next element still offset 1 | ||||
668 | * - [1, 2, 3] => delete offset 0 => [2, 3]: next element still offset 0 | ||||
669 | * if we deleted the last element at offet N and now | ||||
670 | * length of this ziplist is N-1, the next call into | ||||
671 | * quicklistNext() will jump to the next node. */ | ||||
672 | } | ||||
673 | |||||
674 | /* Replace quicklist entry at offset 'index' by 'data' with length 'sz'. | ||||
675 | * | ||||
676 | * Returns 1 if replace happened. | ||||
677 | * Returns 0 if replace failed and no changes happened. */ | ||||
678 | int quicklistReplaceAtIndex(quicklist *quicklist, long index, void *data, | ||||
679 | int sz) { | ||||
680 | quicklistEntry entry; | ||||
681 | if (likely(quicklistIndex(quicklist, index, &entry))__builtin_expect(!!(quicklistIndex(quicklist, index, &entry )), 1)) { | ||||
682 | /* quicklistIndex provides an uncompressed node */ | ||||
683 | entry.node->zl = ziplistReplace(entry.node->zl, entry.zi, data, sz); | ||||
684 | quicklistNodeUpdateSz(entry.node)do { (entry.node)->sz = ziplistBlobLen((entry.node)->zl ); } while (0); | ||||
685 | quicklistCompress(quicklist, entry.node)do { if ((entry.node)->recompress) do { if (((entry.node)) && ((entry.node))->encoding == 1) { __quicklistCompressNode (((entry.node))); } } while (0); else __quicklistCompress((quicklist ), (entry.node)); } while (0); | ||||
686 | return 1; | ||||
687 | } else { | ||||
688 | return 0; | ||||
689 | } | ||||
690 | } | ||||
691 | |||||
692 | /* Given two nodes, try to merge their ziplists. | ||||
693 | * | ||||
694 | * This helps us not have a quicklist with 3 element ziplists if | ||||
695 | * our fill factor can handle much higher levels. | ||||
696 | * | ||||
697 | * Note: 'a' must be to the LEFT of 'b'. | ||||
698 | * | ||||
699 | * After calling this function, both 'a' and 'b' should be considered | ||||
700 | * unusable. The return value from this function must be used | ||||
701 | * instead of re-using any of the quicklistNode input arguments. | ||||
702 | * | ||||
703 | * Returns the input node picked to merge against or NULL if | ||||
704 | * merging was not possible. */ | ||||
705 | REDIS_STATIC quicklistNode *_quicklistZiplistMerge(quicklist *quicklist, | ||||
706 | quicklistNode *a, | ||||
707 | quicklistNode *b) { | ||||
708 | D("Requested merge (a,b) (%u, %u)", a->count, b->count); | ||||
709 | |||||
710 | quicklistDecompressNode(a)do { if ((a) && (a)->encoding == 2) { __quicklistDecompressNode ((a)); } } while (0); | ||||
711 | quicklistDecompressNode(b)do { if ((b) && (b)->encoding == 2) { __quicklistDecompressNode ((b)); } } while (0); | ||||
712 | if ((ziplistMerge(&a->zl, &b->zl))) { | ||||
713 | /* We merged ziplists! Now remove the unused quicklistNode. */ | ||||
714 | quicklistNode *keep = NULL((void*)0), *nokeep = NULL((void*)0); | ||||
715 | if (!a->zl) { | ||||
716 | nokeep = a; | ||||
717 | keep = b; | ||||
718 | } else if (!b->zl) { | ||||
719 | nokeep = b; | ||||
720 | keep = a; | ||||
721 | } | ||||
722 | keep->count = ziplistLen(keep->zl); | ||||
| |||||
723 | quicklistNodeUpdateSz(keep)do { (keep)->sz = ziplistBlobLen((keep)->zl); } while ( 0); | ||||
724 | |||||
725 | nokeep->count = 0; | ||||
726 | __quicklistDelNode(quicklist, nokeep); | ||||
727 | quicklistCompress(quicklist, keep)do { if ((keep)->recompress) do { if (((keep)) && ( (keep))->encoding == 1) { __quicklistCompressNode(((keep)) ); } } while (0); else __quicklistCompress((quicklist), (keep )); } while (0); | ||||
728 | return keep; | ||||
729 | } else { | ||||
730 | /* else, the merge returned NULL and nothing changed. */ | ||||
731 | return NULL((void*)0); | ||||
732 | } | ||||
733 | } | ||||
734 | |||||
735 | /* Attempt to merge ziplists within two nodes on either side of 'center'. | ||||
736 | * | ||||
737 | * We attempt to merge: | ||||
738 | * - (center->prev->prev, center->prev) | ||||
739 | * - (center->next, center->next->next) | ||||
740 | * - (center->prev, center) | ||||
741 | * - (center, center->next) | ||||
742 | */ | ||||
743 | REDIS_STATIC void _quicklistMergeNodes(quicklist *quicklist, | ||||
744 | quicklistNode *center) { | ||||
745 | int fill = quicklist->fill; | ||||
746 | quicklistNode *prev, *prev_prev, *next, *next_next, *target; | ||||
747 | prev = prev_prev = next = next_next = target = NULL((void*)0); | ||||
748 | |||||
749 | if (center->prev) { | ||||
750 | prev = center->prev; | ||||
751 | if (center->prev->prev) | ||||
752 | prev_prev = center->prev->prev; | ||||
753 | } | ||||
754 | |||||
755 | if (center->next) { | ||||
756 | next = center->next; | ||||
757 | if (center->next->next) | ||||
758 | next_next = center->next->next; | ||||
759 | } | ||||
760 | |||||
761 | /* Try to merge prev_prev and prev */ | ||||
762 | if (_quicklistNodeAllowMerge(prev, prev_prev, fill)) { | ||||
763 | _quicklistZiplistMerge(quicklist, prev_prev, prev); | ||||
764 | prev_prev = prev = NULL((void*)0); /* they could have moved, invalidate them. */ | ||||
765 | } | ||||
766 | |||||
767 | /* Try to merge next and next_next */ | ||||
768 | if (_quicklistNodeAllowMerge(next, next_next, fill)) { | ||||
769 | _quicklistZiplistMerge(quicklist, next, next_next); | ||||
770 | next = next_next = NULL((void*)0); /* they could have moved, invalidate them. */ | ||||
771 | } | ||||
772 | |||||
773 | /* Try to merge center node and previous node */ | ||||
774 | if (_quicklistNodeAllowMerge(center, center->prev, fill)) { | ||||
775 | target = _quicklistZiplistMerge(quicklist, center->prev, center); | ||||
776 | center = NULL((void*)0); /* center could have been deleted, invalidate it. */ | ||||
777 | } else { | ||||
778 | /* else, we didn't merge here, but target needs to be valid below. */ | ||||
779 | target = center; | ||||
780 | } | ||||
781 | |||||
782 | /* Use result of center merge (or original) to merge with next node. */ | ||||
783 | if (_quicklistNodeAllowMerge(target, target->next, fill)) { | ||||
784 | _quicklistZiplistMerge(quicklist, target, target->next); | ||||
785 | } | ||||
786 | } | ||||
787 | |||||
788 | /* Split 'node' into two parts, parameterized by 'offset' and 'after'. | ||||
789 | * | ||||
790 | * The 'after' argument controls which quicklistNode gets returned. | ||||
791 | * If 'after'==1, returned node has elements after 'offset'. | ||||
792 | * input node keeps elements up to 'offset', including 'offset'. | ||||
793 | * If 'after'==0, returned node has elements up to 'offset'. | ||||
794 | * input node keeps elements after 'offset', including 'offset'. | ||||
795 | * | ||||
796 | * Or in other words: | ||||
797 | * If 'after'==1, returned node will have elements after 'offset'. | ||||
798 | * The returned node will have elements [OFFSET+1, END]. | ||||
799 | * The input node keeps elements [0, OFFSET]. | ||||
800 | * If 'after'==0, returned node will keep elements up to but not including 'offset'. | ||||
801 | * The returned node will have elements [0, OFFSET-1]. | ||||
802 | * The input node keeps elements [OFFSET, END]. | ||||
803 | * | ||||
804 | * The input node keeps all elements not taken by the returned node. | ||||
805 | * | ||||
806 | * Returns newly created node or NULL if split not possible. */ | ||||
807 | REDIS_STATIC quicklistNode *_quicklistSplitNode(quicklistNode *node, int offset, | ||||
808 | int after) { | ||||
809 | size_t zl_sz = node->sz; | ||||
810 | |||||
811 | quicklistNode *new_node = quicklistCreateNode(); | ||||
812 | new_node->zl = zmalloc(zl_sz); | ||||
813 | |||||
814 | /* Copy original ziplist so we can split it */ | ||||
815 | memcpy(new_node->zl, node->zl, zl_sz); | ||||
816 | |||||
817 | /* Ranges to be trimmed: -1 here means "continue deleting until the list ends" */ | ||||
818 | int orig_start = after ? offset + 1 : 0; | ||||
819 | int orig_extent = after ? -1 : offset; | ||||
820 | int new_start = after ? 0 : offset; | ||||
821 | int new_extent = after ? offset + 1 : -1; | ||||
822 | |||||
823 | D("After %d (%d); ranges: [%d, %d], [%d, %d]", after, offset, orig_start, | ||||
824 | orig_extent, new_start, new_extent); | ||||
825 | |||||
826 | node->zl = ziplistDeleteRange(node->zl, orig_start, orig_extent); | ||||
827 | node->count = ziplistLen(node->zl); | ||||
828 | quicklistNodeUpdateSz(node)do { (node)->sz = ziplistBlobLen((node)->zl); } while ( 0); | ||||
829 | |||||
830 | new_node->zl = ziplistDeleteRange(new_node->zl, new_start, new_extent); | ||||
831 | new_node->count = ziplistLen(new_node->zl); | ||||
832 | quicklistNodeUpdateSz(new_node)do { (new_node)->sz = ziplistBlobLen((new_node)->zl); } while (0); | ||||
833 | |||||
834 | D("After split lengths: orig (%d), new (%d)", node->count, new_node->count); | ||||
835 | return new_node; | ||||
836 | } | ||||
837 | |||||
838 | /* Insert a new entry before or after existing entry 'entry'. | ||||
839 | * | ||||
840 | * If after==1, the new value is inserted after 'entry', otherwise | ||||
841 | * the new value is inserted before 'entry'. */ | ||||
842 | REDIS_STATIC void _quicklistInsert(quicklist *quicklist, quicklistEntry *entry, | ||||
843 | void *value, const size_t sz, int after) { | ||||
844 | int full = 0, at_tail = 0, at_head = 0, full_next = 0, full_prev = 0; | ||||
845 | int fill = quicklist->fill; | ||||
846 | quicklistNode *node = entry->node; | ||||
847 | quicklistNode *new_node = NULL((void*)0); | ||||
848 | |||||
849 | if (!node) { | ||||
| |||||
850 | /* we have no reference node, so let's create only node in the list */ | ||||
851 | D("No node given!"); | ||||
852 | new_node = quicklistCreateNode(); | ||||
853 | new_node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_HEAD0); | ||||
854 | __quicklistInsertNode(quicklist, NULL((void*)0), new_node, after); | ||||
855 | new_node->count++; | ||||
856 | quicklist->count++; | ||||
857 | return; | ||||
858 | } | ||||
859 | |||||
860 | /* Populate accounting flags for easier boolean checks later */ | ||||
861 | if (!_quicklistNodeAllowInsert(node, fill, sz)) { | ||||
862 | D("Current node is full with count %d with requested fill %lu", | ||||
863 | node->count, fill); | ||||
864 | full = 1; | ||||
865 | } | ||||
866 | |||||
867 | if (after && (entry->offset == node->count)) { | ||||
868 | D("At Tail of current ziplist"); | ||||
869 | at_tail = 1; | ||||
870 | if (!_quicklistNodeAllowInsert(node->next, fill, sz)) { | ||||
871 | D("Next node is full too."); | ||||
872 | full_next = 1; | ||||
873 | } | ||||
874 | } | ||||
875 | |||||
876 | if (!after
| ||||
877 | D("At Head"); | ||||
878 | at_head = 1; | ||||
879 | if (!_quicklistNodeAllowInsert(node->prev, fill, sz)) { | ||||
880 | D("Prev node is full too."); | ||||
881 | full_prev = 1; | ||||
882 | } | ||||
883 | } | ||||
884 | |||||
885 | /* Now determine where and how to insert the new element */ | ||||
886 | if (!full
| ||||
887 | D("Not full, inserting after current position."); | ||||
888 | quicklistDecompressNodeForUse(node)do { if ((node) && (node)->encoding == 2) { __quicklistDecompressNode ((node)); (node)->recompress = 1; } } while (0); | ||||
889 | unsigned char *next = ziplistNext(node->zl, entry->zi); | ||||
890 | if (next == NULL((void*)0)) { | ||||
891 | node->zl = ziplistPush(node->zl, value, sz, ZIPLIST_TAIL1); | ||||
892 | } else { | ||||
893 | node->zl = ziplistInsert(node->zl, next, value, sz); | ||||
894 | } | ||||
895 | node->count++; | ||||
896 | quicklistNodeUpdateSz(node)do { (node)->sz = ziplistBlobLen((node)->zl); } while ( 0); | ||||
897 | quicklistRecompressOnly(quicklist, node)do { if ((node)->recompress) do { if (((node)) && ( (node))->encoding == 1) { __quicklistCompressNode(((node)) ); } } while (0); } while (0); | ||||
898 | } else if (!full
| ||||
899 | D("Not full, inserting before current position."); | ||||
900 | quicklistDecompressNodeForUse(node)do { if ((node) && (node)->encoding == 2) { __quicklistDecompressNode ((node)); (node)->recompress = 1; } } while (0); | ||||
901 | node->zl = ziplistInsert(node->zl, entry->zi, value, sz); | ||||
902 | node->count++; | ||||
903 | quicklistNodeUpdateSz(node)do { (node)->sz = ziplistBlobLen((node)->zl); } while ( 0); | ||||
904 | quicklistRecompressOnly(quicklist, node)do { if ((node)->recompress) do { if (((node)) && ( (node))->encoding == 1) { __quicklistCompressNode(((node)) ); } } while (0); } while (0); | ||||
905 | } else if (full
| ||||
906 | /* If we are: at tail, next has free space, and inserting after: | ||||
907 | * - insert entry at head of next node. */ | ||||
908 | D("Full and tail, but next isn't full; inserting next node head"); | ||||
909 | new_node = node->next; | ||||
910 | quicklistDecompressNodeForUse(new_node)do { if ((new_node) && (new_node)->encoding == 2) { __quicklistDecompressNode((new_node)); (new_node)->recompress = 1; } } while (0); | ||||
911 | new_node->zl = ziplistPush(new_node->zl, value, sz, ZIPLIST_HEAD0); | ||||
912 | new_node->count++; | ||||
913 | quicklistNodeUpdateSz(new_node)do { (new_node)->sz = ziplistBlobLen((new_node)->zl); } while (0); | ||||
914 | quicklistRecompressOnly(quicklist, new_node)do { if ((new_node)->recompress) do { if (((new_node)) && ((new_node))->encoding == 1) { __quicklistCompressNode((( new_node))); } } while (0); } while (0); | ||||
915 | } else if (full
| ||||
916 | /* If we are: at head, previous has free space, and inserting before: | ||||
917 | * - insert entry at tail of previous node. */ | ||||
918 | D("Full and head, but prev isn't full, inserting prev node tail"); | ||||
919 | new_node = node->prev; | ||||
920 | quicklistDecompressNodeForUse(new_node)do { if ((new_node) && (new_node)->encoding == 2) { __quicklistDecompressNode((new_node)); (new_node)->recompress = 1; } } while (0); | ||||
921 | new_node->zl = ziplistPush(new_node->zl, value, sz, ZIPLIST_TAIL1); | ||||
922 | new_node->count++; | ||||
923 | quicklistNodeUpdateSz(new_node)do { (new_node)->sz = ziplistBlobLen((new_node)->zl); } while (0); | ||||
924 | quicklistRecompressOnly(quicklist, new_node)do { if ((new_node)->recompress) do { if (((new_node)) && ((new_node))->encoding == 1) { __quicklistCompressNode((( new_node))); } } while (0); } while (0); | ||||
925 | } else if (full
| ||||
926 | (at_head
| ||||
927 | /* If we are: full, and our prev/next is full, then: | ||||
928 | * - create new node and attach to quicklist */ | ||||
929 | D("\tprovisioning new node..."); | ||||
930 | new_node = quicklistCreateNode(); | ||||
931 | new_node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_HEAD0); | ||||
932 | new_node->count++; | ||||
933 | quicklistNodeUpdateSz(new_node)do { (new_node)->sz = ziplistBlobLen((new_node)->zl); } while (0); | ||||
934 | __quicklistInsertNode(quicklist, node, new_node, after); | ||||
935 | } else if (full
| ||||
936 | /* else, node is full we need to split it. */ | ||||
937 | /* covers both after and !after cases */ | ||||
938 | D("\tsplitting node..."); | ||||
939 | quicklistDecompressNodeForUse(node)do { if ((node) && (node)->encoding == 2) { __quicklistDecompressNode ((node)); (node)->recompress = 1; } } while (0); | ||||
940 | new_node = _quicklistSplitNode(node, entry->offset, after); | ||||
941 | new_node->zl = ziplistPush(new_node->zl, value, sz, | ||||
942 | after
| ||||
943 | new_node->count++; | ||||
944 | quicklistNodeUpdateSz(new_node)do { (new_node)->sz = ziplistBlobLen((new_node)->zl); } while (0); | ||||
945 | __quicklistInsertNode(quicklist, node, new_node, after); | ||||
946 | _quicklistMergeNodes(quicklist, node); | ||||
947 | } | ||||
948 | |||||
949 | quicklist->count++; | ||||
950 | } | ||||
951 | |||||
952 | void quicklistInsertBefore(quicklist *quicklist, quicklistEntry *entry, | ||||
953 | void *value, const size_t sz) { | ||||
954 | _quicklistInsert(quicklist, entry, value, sz, 0); | ||||
955 | } | ||||
956 | |||||
957 | void quicklistInsertAfter(quicklist *quicklist, quicklistEntry *entry, | ||||
958 | void *value, const size_t sz) { | ||||
959 | _quicklistInsert(quicklist, entry, value, sz, 1); | ||||
960 | } | ||||
961 | |||||
962 | /* Delete a range of elements from the quicklist. | ||||
963 | * | ||||
964 | * elements may span across multiple quicklistNodes, so we | ||||
965 | * have to be careful about tracking where we start and end. | ||||
966 | * | ||||
967 | * Returns 1 if entries were deleted, 0 if nothing was deleted. */ | ||||
968 | int quicklistDelRange(quicklist *quicklist, const long start, | ||||
969 | const long count) { | ||||
970 | if (count <= 0) | ||||
971 | return 0; | ||||
972 | |||||
973 | unsigned long extent = count; /* range is inclusive of start position */ | ||||
974 | |||||
975 | if (start >= 0 && extent > (quicklist->count - start)) { | ||||
976 | /* if requesting delete more elements than exist, limit to list size. */ | ||||
977 | extent = quicklist->count - start; | ||||
978 | } else if (start < 0 && extent > (unsigned long)(-start)) { | ||||
979 | /* else, if at negative offset, limit max size to rest of list. */ | ||||
980 | extent = -start; /* c.f. LREM -29 29; just delete until end. */ | ||||
981 | } | ||||
982 | |||||
983 | quicklistEntry entry; | ||||
984 | if (!quicklistIndex(quicklist, start, &entry)) | ||||
985 | return 0; | ||||
986 | |||||
987 | D("Quicklist delete request for start %ld, count %ld, extent: %ld", start, | ||||
988 | count, extent); | ||||
989 | quicklistNode *node = entry.node; | ||||
990 | |||||
991 | /* iterate over next nodes until everything is deleted. */ | ||||
992 | while (extent) { | ||||
993 | quicklistNode *next = node->next; | ||||
994 | |||||
995 | unsigned long del; | ||||
996 | int delete_entire_node = 0; | ||||
997 | if (entry.offset == 0 && extent >= node->count) { | ||||
998 | /* If we are deleting more than the count of this node, we | ||||
999 | * can just delete the entire node without ziplist math. */ | ||||
1000 | delete_entire_node = 1; | ||||
1001 | del = node->count; | ||||
1002 | } else if (entry.offset >= 0 && extent + entry.offset >= node->count) { | ||||
1003 | /* If deleting more nodes after this one, calculate delete based | ||||
1004 | * on size of current node. */ | ||||
1005 | del = node->count - entry.offset; | ||||
1006 | } else if (entry.offset < 0) { | ||||
1007 | /* If offset is negative, we are in the first run of this loop | ||||
1008 | * and we are deleting the entire range | ||||
1009 | * from this start offset to end of list. Since the Negative | ||||
1010 | * offset is the number of elements until the tail of the list, | ||||
1011 | * just use it directly as the deletion count. */ | ||||
1012 | del = -entry.offset; | ||||
1013 | |||||
1014 | /* If the positive offset is greater than the remaining extent, | ||||
1015 | * we only delete the remaining extent, not the entire offset. | ||||
1016 | */ | ||||
1017 | if (del > extent) | ||||
1018 | del = extent; | ||||
1019 | } else { | ||||
1020 | /* else, we are deleting less than the extent of this node, so | ||||
1021 | * use extent directly. */ | ||||
1022 | del = extent; | ||||
1023 | } | ||||
1024 | |||||
1025 | D("[%ld]: asking to del: %ld because offset: %d; (ENTIRE NODE: %d), " | ||||
1026 | "node count: %u", | ||||
1027 | extent, del, entry.offset, delete_entire_node, node->count); | ||||
1028 | |||||
1029 | if (delete_entire_node) { | ||||
1030 | __quicklistDelNode(quicklist, node); | ||||
1031 | } else { | ||||
1032 | quicklistDecompressNodeForUse(node)do { if ((node) && (node)->encoding == 2) { __quicklistDecompressNode ((node)); (node)->recompress = 1; } } while (0); | ||||
1033 | node->zl = ziplistDeleteRange(node->zl, entry.offset, del); | ||||
1034 | quicklistNodeUpdateSz(node)do { (node)->sz = ziplistBlobLen((node)->zl); } while ( 0); | ||||
1035 | node->count -= del; | ||||
1036 | quicklist->count -= del; | ||||
1037 | quicklistDeleteIfEmpty(quicklist, node)do { if ((node)->count == 0) { __quicklistDelNode((quicklist ), (node)); (node) = ((void*)0); } } while (0); | ||||
1038 | if (node) | ||||
1039 | quicklistRecompressOnly(quicklist, node)do { if ((node)->recompress) do { if (((node)) && ( (node))->encoding == 1) { __quicklistCompressNode(((node)) ); } } while (0); } while (0); | ||||
1040 | } | ||||
1041 | |||||
1042 | extent -= del; | ||||
1043 | |||||
1044 | node = next; | ||||
1045 | |||||
1046 | entry.offset = 0; | ||||
1047 | } | ||||
1048 | return 1; | ||||
1049 | } | ||||
1050 | |||||
1051 | /* Passthrough to ziplistCompare() */ | ||||
1052 | int quicklistCompare(unsigned char *p1, unsigned char *p2, int p2_len) { | ||||
1053 | return ziplistCompare(p1, p2, p2_len); | ||||
1054 | } | ||||
1055 | |||||
1056 | /* Returns a quicklist iterator 'iter'. After the initialization every | ||||
1057 | * call to quicklistNext() will return the next element of the quicklist. */ | ||||
1058 | quicklistIter *quicklistGetIterator(const quicklist *quicklist, int direction) { | ||||
1059 | quicklistIter *iter; | ||||
1060 | |||||
1061 | iter = zmalloc(sizeof(*iter)); | ||||
1062 | |||||
1063 | if (direction == AL_START_HEAD0) { | ||||
1064 | iter->current = quicklist->head; | ||||
1065 | iter->offset = 0; | ||||
1066 | } else if (direction == AL_START_TAIL1) { | ||||
1067 | iter->current = quicklist->tail; | ||||
1068 | iter->offset = -1; | ||||
1069 | } | ||||
1070 | |||||
1071 | iter->direction = direction; | ||||
1072 | iter->quicklist = quicklist; | ||||
1073 | |||||
1074 | iter->zi = NULL((void*)0); | ||||
1075 | |||||
1076 | return iter; | ||||
1077 | } | ||||
1078 | |||||
1079 | /* Initialize an iterator at a specific offset 'idx' and make the iterator | ||||
1080 | * return nodes in 'direction' direction. */ | ||||
1081 | quicklistIter *quicklistGetIteratorAtIdx(const quicklist *quicklist, | ||||
1082 | const int direction, | ||||
1083 | const long long idx) { | ||||
1084 | quicklistEntry entry; | ||||
1085 | |||||
1086 | if (quicklistIndex(quicklist, idx, &entry)) { | ||||
1087 | quicklistIter *base = quicklistGetIterator(quicklist, direction); | ||||
1088 | base->zi = NULL((void*)0); | ||||
1089 | base->current = entry.node; | ||||
1090 | base->offset = entry.offset; | ||||
1091 | return base; | ||||
1092 | } else { | ||||
1093 | return NULL((void*)0); | ||||
1094 | } | ||||
1095 | } | ||||
1096 | |||||
1097 | /* Release iterator. | ||||
1098 | * If we still have a valid current node, then re-encode current node. */ | ||||
1099 | void quicklistReleaseIterator(quicklistIter *iter) { | ||||
1100 | if (iter->current) | ||||
1101 | quicklistCompress(iter->quicklist, iter->current)do { if ((iter->current)->recompress) do { if (((iter-> current)) && ((iter->current))->encoding == 1) { __quicklistCompressNode(((iter->current))); } } while (0) ; else __quicklistCompress((iter->quicklist), (iter->current )); } while (0); | ||||
1102 | |||||
1103 | zfree(iter); | ||||
1104 | } | ||||
1105 | |||||
1106 | /* Get next element in iterator. | ||||
1107 | * | ||||
1108 | * Note: You must NOT insert into the list while iterating over it. | ||||
1109 | * You *may* delete from the list while iterating using the | ||||
1110 | * quicklistDelEntry() function. | ||||
1111 | * If you insert into the quicklist while iterating, you should | ||||
1112 | * re-create the iterator after your addition. | ||||
1113 | * | ||||
1114 | * iter = quicklistGetIterator(quicklist,<direction>); | ||||
1115 | * quicklistEntry entry; | ||||
1116 | * while (quicklistNext(iter, &entry)) { | ||||
1117 | * if (entry.value) | ||||
1118 | * [[ use entry.value with entry.sz ]] | ||||
1119 | * else | ||||
1120 | * [[ use entry.longval ]] | ||||
1121 | * } | ||||
1122 | * | ||||
1123 | * Populates 'entry' with values for this iteration. | ||||
1124 | * Returns 0 when iteration is complete or if iteration not possible. | ||||
1125 | * If return value is 0, the contents of 'entry' are not valid. | ||||
1126 | */ | ||||
1127 | int quicklistNext(quicklistIter *iter, quicklistEntry *entry) { | ||||
1128 | initEntry(entry)do { (entry)->zi = (entry)->value = ((void*)0); (entry) ->longval = -123456789; (entry)->quicklist = ((void*)0) ; (entry)->node = ((void*)0); (entry)->offset = 123456789 ; (entry)->sz = 0; } while (0); | ||||
1129 | |||||
1130 | if (!iter) { | ||||
1131 | D("Returning because no iter!"); | ||||
1132 | return 0; | ||||
1133 | } | ||||
1134 | |||||
1135 | entry->quicklist = iter->quicklist; | ||||
1136 | entry->node = iter->current; | ||||
1137 | |||||
1138 | if (!iter->current) { | ||||
1139 | D("Returning because current node is NULL") | ||||
1140 | return 0; | ||||
1141 | } | ||||
1142 | |||||
1143 | unsigned char *(*nextFn)(unsigned char *, unsigned char *) = NULL((void*)0); | ||||
1144 | int offset_update = 0; | ||||
1145 | |||||
1146 | if (!iter->zi) { | ||||
1147 | /* If !zi, use current index. */ | ||||
1148 | quicklistDecompressNodeForUse(iter->current)do { if ((iter->current) && (iter->current)-> encoding == 2) { __quicklistDecompressNode((iter->current) ); (iter->current)->recompress = 1; } } while (0); | ||||
1149 | iter->zi = ziplistIndex(iter->current->zl, iter->offset); | ||||
1150 | } else { | ||||
1151 | /* else, use existing iterator offset and get prev/next as necessary. */ | ||||
1152 | if (iter->direction == AL_START_HEAD0) { | ||||
1153 | nextFn = ziplistNext; | ||||
1154 | offset_update = 1; | ||||
1155 | } else if (iter->direction == AL_START_TAIL1) { | ||||
1156 | nextFn = ziplistPrev; | ||||
1157 | offset_update = -1; | ||||
1158 | } | ||||
1159 | iter->zi = nextFn(iter->current->zl, iter->zi); | ||||
1160 | iter->offset += offset_update; | ||||
1161 | } | ||||
1162 | |||||
1163 | entry->zi = iter->zi; | ||||
1164 | entry->offset = iter->offset; | ||||
1165 | |||||
1166 | if (iter->zi) { | ||||
1167 | /* Populate value from existing ziplist position */ | ||||
1168 | ziplistGet(entry->zi, &entry->value, &entry->sz, &entry->longval); | ||||
1169 | return 1; | ||||
1170 | } else { | ||||
1171 | /* We ran out of ziplist entries. | ||||
1172 | * Pick next node, update offset, then re-run retrieval. */ | ||||
1173 | quicklistCompress(iter->quicklist, iter->current)do { if ((iter->current)->recompress) do { if (((iter-> current)) && ((iter->current))->encoding == 1) { __quicklistCompressNode(((iter->current))); } } while (0) ; else __quicklistCompress((iter->quicklist), (iter->current )); } while (0); | ||||
1174 | if (iter->direction == AL_START_HEAD0) { | ||||
1175 | /* Forward traversal */ | ||||
1176 | D("Jumping to start of next node"); | ||||
1177 | iter->current = iter->current->next; | ||||
1178 | iter->offset = 0; | ||||
1179 | } else if (iter->direction == AL_START_TAIL1) { | ||||
1180 | /* Reverse traversal */ | ||||
1181 | D("Jumping to end of previous node"); | ||||
1182 | iter->current = iter->current->prev; | ||||
1183 | iter->offset = -1; | ||||
1184 | } | ||||
1185 | iter->zi = NULL((void*)0); | ||||
1186 | return quicklistNext(iter, entry); | ||||
1187 | } | ||||
1188 | } | ||||
1189 | |||||
1190 | /* Duplicate the quicklist. | ||||
1191 | * On success a copy of the original quicklist is returned. | ||||
1192 | * | ||||
1193 | * The original quicklist both on success or error is never modified. | ||||
1194 | * | ||||
1195 | * Returns newly allocated quicklist. */ | ||||
1196 | quicklist *quicklistDup(quicklist *orig) { | ||||
1197 | quicklist *copy; | ||||
1198 | |||||
1199 | copy = quicklistNew(orig->fill, orig->compress); | ||||
1200 | |||||
1201 | for (quicklistNode *current = orig->head; current; | ||||
1202 | current = current->next) { | ||||
1203 | quicklistNode *node = quicklistCreateNode(); | ||||
1204 | |||||
1205 | if (current->encoding == QUICKLIST_NODE_ENCODING_LZF2) { | ||||
1206 | quicklistLZF *lzf = (quicklistLZF *)current->zl; | ||||
1207 | size_t lzf_sz = sizeof(*lzf) + lzf->sz; | ||||
1208 | node->zl = zmalloc(lzf_sz); | ||||
1209 | memcpy(node->zl, current->zl, lzf_sz); | ||||
1210 | } else if (current->encoding == QUICKLIST_NODE_ENCODING_RAW1) { | ||||
1211 | node->zl = zmalloc(current->sz); | ||||
1212 | memcpy(node->zl, current->zl, current->sz); | ||||
1213 | } | ||||
1214 | |||||
1215 | node->count = current->count; | ||||
1216 | copy->count += node->count; | ||||
1217 | node->sz = current->sz; | ||||
1218 | node->encoding = current->encoding; | ||||
1219 | |||||
1220 | _quicklistInsertNodeAfter(copy, copy->tail, node); | ||||
1221 | } | ||||
1222 | |||||
1223 | /* copy->count must equal orig->count here */ | ||||
1224 | return copy; | ||||
1225 | } | ||||
1226 | |||||
1227 | /* Populate 'entry' with the element at the specified zero-based index | ||||
1228 | * where 0 is the head, 1 is the element next to head | ||||
1229 | * and so on. Negative integers are used in order to count | ||||
1230 | * from the tail, -1 is the last element, -2 the penultimate | ||||
1231 | * and so on. If the index is out of range 0 is returned. | ||||
1232 | * | ||||
1233 | * Returns 1 if element found | ||||
1234 | * Returns 0 if element not found */ | ||||
1235 | int quicklistIndex(const quicklist *quicklist, const long long idx, | ||||
1236 | quicklistEntry *entry) { | ||||
1237 | quicklistNode *n; | ||||
1238 | unsigned long long accum = 0; | ||||
1239 | unsigned long long index; | ||||
1240 | int forward = idx < 0 ? 0 : 1; /* < 0 -> reverse, 0+ -> forward */ | ||||
1241 | |||||
1242 | initEntry(entry)do { (entry)->zi = (entry)->value = ((void*)0); (entry) ->longval = -123456789; (entry)->quicklist = ((void*)0) ; (entry)->node = ((void*)0); (entry)->offset = 123456789 ; (entry)->sz = 0; } while (0); | ||||
1243 | entry->quicklist = quicklist; | ||||
1244 | |||||
1245 | if (!forward) { | ||||
1246 | index = (-idx) - 1; | ||||
1247 | n = quicklist->tail; | ||||
1248 | } else { | ||||
1249 | index = idx; | ||||
1250 | n = quicklist->head; | ||||
1251 | } | ||||
1252 | |||||
1253 | if (index >= quicklist->count) | ||||
1254 | return 0; | ||||
1255 | |||||
1256 | while (likely(n)__builtin_expect(!!(n), 1)) { | ||||
1257 | if ((accum + n->count) > index) { | ||||
1258 | break; | ||||
1259 | } else { | ||||
1260 | D("Skipping over (%p) %u at accum %lld", (void *)n, n->count, | ||||
1261 | accum); | ||||
1262 | accum += n->count; | ||||
1263 | n = forward ? n->next : n->prev; | ||||
1264 | } | ||||
1265 | } | ||||
1266 | |||||
1267 | if (!n) | ||||
1268 | return 0; | ||||
1269 | |||||
1270 | D("Found node: %p at accum %llu, idx %llu, sub+ %llu, sub- %llu", (void *)n, | ||||
1271 | accum, index, index - accum, (-index) - 1 + accum); | ||||
1272 | |||||
1273 | entry->node = n; | ||||
1274 | if (forward) { | ||||
1275 | /* forward = normal head-to-tail offset. */ | ||||
1276 | entry->offset = index - accum; | ||||
1277 | } else { | ||||
1278 | /* reverse = need negative offset for tail-to-head, so undo | ||||
1279 | * the result of the original if (index < 0) above. */ | ||||
1280 | entry->offset = (-index) - 1 + accum; | ||||
1281 | } | ||||
1282 | |||||
1283 | quicklistDecompressNodeForUse(entry->node)do { if ((entry->node) && (entry->node)->encoding == 2) { __quicklistDecompressNode((entry->node)); (entry-> node)->recompress = 1; } } while (0); | ||||
1284 | entry->zi = ziplistIndex(entry->node->zl, entry->offset); | ||||
1285 | if (!ziplistGet(entry->zi, &entry->value, &entry->sz, &entry->longval)) | ||||
1286 | assert(0)(__builtin_expect(!!((0)), 1)?(void)0 : (_serverAssert("0","quicklist.c" ,1286),__builtin_unreachable())); /* This can happen on corrupt ziplist with fake entry count. */ | ||||
1287 | /* The caller will use our result, so we don't re-compress here. | ||||
1288 | * The caller can recompress or delete the node as needed. */ | ||||
1289 | return 1; | ||||
1290 | } | ||||
1291 | |||||
1292 | /* Rotate quicklist by moving the tail element to the head. */ | ||||
1293 | void quicklistRotate(quicklist *quicklist) { | ||||
1294 | if (quicklist->count <= 1) | ||||
1295 | return; | ||||
1296 | |||||
1297 | /* First, get the tail entry */ | ||||
1298 | unsigned char *p = ziplistIndex(quicklist->tail->zl, -1); | ||||
1299 | unsigned char *value; | ||||
1300 | long long longval; | ||||
1301 | unsigned int sz; | ||||
1302 | char longstr[32] = {0}; | ||||
1303 | ziplistGet(p, &value, &sz, &longval); | ||||
1304 | |||||
1305 | /* If value found is NULL, then ziplistGet populated longval instead */ | ||||
1306 | if (!value) { | ||||
1307 | /* Write the longval as a string so we can re-add it */ | ||||
1308 | sz = ll2string(longstr, sizeof(longstr), longval); | ||||
1309 | value = (unsigned char *)longstr; | ||||
1310 | } | ||||
1311 | |||||
1312 | /* Add tail entry to head (must happen before tail is deleted). */ | ||||
1313 | quicklistPushHead(quicklist, value, sz); | ||||
1314 | |||||
1315 | /* If quicklist has only one node, the head ziplist is also the | ||||
1316 | * tail ziplist and PushHead() could have reallocated our single ziplist, | ||||
1317 | * which would make our pre-existing 'p' unusable. */ | ||||
1318 | if (quicklist->len == 1) { | ||||
1319 | p = ziplistIndex(quicklist->tail->zl, -1); | ||||
1320 | } | ||||
1321 | |||||
1322 | /* Remove tail entry. */ | ||||
1323 | quicklistDelIndex(quicklist, quicklist->tail, &p); | ||||
1324 | } | ||||
1325 | |||||
1326 | /* pop from quicklist and return result in 'data' ptr. Value of 'data' | ||||
1327 | * is the return value of 'saver' function pointer if the data is NOT a number. | ||||
1328 | * | ||||
1329 | * If the quicklist element is a long long, then the return value is returned in | ||||
1330 | * 'sval'. | ||||
1331 | * | ||||
1332 | * Return value of 0 means no elements available. | ||||
1333 | * Return value of 1 means check 'data' and 'sval' for values. | ||||
1334 | * If 'data' is set, use 'data' and 'sz'. Otherwise, use 'sval'. */ | ||||
1335 | int quicklistPopCustom(quicklist *quicklist, int where, unsigned char **data, | ||||
1336 | unsigned int *sz, long long *sval, | ||||
1337 | void *(*saver)(unsigned char *data, unsigned int sz)) { | ||||
1338 | unsigned char *p; | ||||
1339 | unsigned char *vstr; | ||||
1340 | unsigned int vlen; | ||||
1341 | long long vlong; | ||||
1342 | int pos = (where == QUICKLIST_HEAD0) ? 0 : -1; | ||||
1343 | |||||
1344 | if (quicklist->count == 0) | ||||
1345 | return 0; | ||||
1346 | |||||
1347 | if (data) | ||||
1348 | *data = NULL((void*)0); | ||||
1349 | if (sz) | ||||
1350 | *sz = 0; | ||||
1351 | if (sval) | ||||
1352 | *sval = -123456789; | ||||
1353 | |||||
1354 | quicklistNode *node; | ||||
1355 | if (where == QUICKLIST_HEAD0 && quicklist->head) { | ||||
1356 | node = quicklist->head; | ||||
1357 | } else if (where == QUICKLIST_TAIL-1 && quicklist->tail) { | ||||
1358 | node = quicklist->tail; | ||||
1359 | } else { | ||||
1360 | return 0; | ||||
1361 | } | ||||
1362 | |||||
1363 | p = ziplistIndex(node->zl, pos); | ||||
1364 | if (ziplistGet(p, &vstr, &vlen, &vlong)) { | ||||
1365 | if (vstr) { | ||||
1366 | if (data) | ||||
1367 | *data = saver(vstr, vlen); | ||||
1368 | if (sz) | ||||
1369 | *sz = vlen; | ||||
1370 | } else { | ||||
1371 | if (data) | ||||
1372 | *data = NULL((void*)0); | ||||
1373 | if (sval) | ||||
1374 | *sval = vlong; | ||||
1375 | } | ||||
1376 | quicklistDelIndex(quicklist, node, &p); | ||||
1377 | return 1; | ||||
1378 | } | ||||
1379 | return 0; | ||||
1380 | } | ||||
1381 | |||||
1382 | /* Return a malloc'd copy of data passed in */ | ||||
1383 | REDIS_STATIC void *_quicklistSaver(unsigned char *data, unsigned int sz) { | ||||
1384 | unsigned char *vstr; | ||||
1385 | if (data) { | ||||
1386 | vstr = zmalloc(sz); | ||||
1387 | memcpy(vstr, data, sz); | ||||
1388 | return vstr; | ||||
1389 | } | ||||
1390 | return NULL((void*)0); | ||||
1391 | } | ||||
1392 | |||||
1393 | /* Default pop function | ||||
1394 | * | ||||
1395 | * Returns malloc'd value from quicklist */ | ||||
1396 | int quicklistPop(quicklist *quicklist, int where, unsigned char **data, | ||||
1397 | unsigned int *sz, long long *slong) { | ||||
1398 | unsigned char *vstr; | ||||
1399 | unsigned int vlen; | ||||
1400 | long long vlong; | ||||
1401 | if (quicklist->count == 0) | ||||
1402 | return 0; | ||||
1403 | int ret = quicklistPopCustom(quicklist, where, &vstr, &vlen, &vlong, | ||||
1404 | _quicklistSaver); | ||||
1405 | if (data) | ||||
1406 | *data = vstr; | ||||
1407 | if (slong) | ||||
1408 | *slong = vlong; | ||||
1409 | if (sz) | ||||
1410 | *sz = vlen; | ||||
1411 | return ret; | ||||
1412 | } | ||||
1413 | |||||
1414 | /* Wrapper to allow argument-based switching between HEAD/TAIL pop */ | ||||
1415 | void quicklistPush(quicklist *quicklist, void *value, const size_t sz, | ||||
1416 | int where) { | ||||
1417 | if (where == QUICKLIST_HEAD0) { | ||||
1418 | quicklistPushHead(quicklist, value, sz); | ||||
1419 | } else if (where == QUICKLIST_TAIL-1) { | ||||
1420 | quicklistPushTail(quicklist, value, sz); | ||||
1421 | } | ||||
1422 | } | ||||
1423 | |||||
1424 | /* Create or update a bookmark in the list which will be updated to the next node | ||||
1425 | * automatically when the one referenced gets deleted. | ||||
1426 | * Returns 1 on success (creation of new bookmark or override of an existing one). | ||||
1427 | * Returns 0 on failure (reached the maximum supported number of bookmarks). | ||||
1428 | * NOTE: use short simple names, so that string compare on find is quick. | ||||
1429 | * NOTE: bookmark creation may re-allocate the quicklist, so the input pointer | ||||
1430 | may change and it's the caller responsibilty to update the reference. | ||||
1431 | */ | ||||
1432 | int quicklistBookmarkCreate(quicklist **ql_ref, const char *name, quicklistNode *node) { | ||||
1433 | quicklist *ql = *ql_ref; | ||||
1434 | if (ql->bookmark_count >= QL_MAX_BM((1 << 4)-1)) | ||||
1435 | return 0; | ||||
1436 | quicklistBookmark *bm = _quicklistBookmarkFindByName(ql, name); | ||||
1437 | if (bm) { | ||||
1438 | bm->node = node; | ||||
1439 | return 1; | ||||
1440 | } | ||||
1441 | ql = zrealloc(ql, sizeof(quicklist) + (ql->bookmark_count+1) * sizeof(quicklistBookmark)); | ||||
1442 | *ql_ref = ql; | ||||
1443 | ql->bookmarks[ql->bookmark_count].node = node; | ||||
1444 | ql->bookmarks[ql->bookmark_count].name = zstrdup(name); | ||||
1445 | ql->bookmark_count++; | ||||
1446 | return 1; | ||||
1447 | } | ||||
1448 | |||||
1449 | /* Find the quicklist node referenced by a named bookmark. | ||||
1450 | * When the bookmarked node is deleted the bookmark is updated to the next node, | ||||
1451 | * and if that's the last node, the bookmark is deleted (so find returns NULL). */ | ||||
1452 | quicklistNode *quicklistBookmarkFind(quicklist *ql, const char *name) { | ||||
1453 | quicklistBookmark *bm = _quicklistBookmarkFindByName(ql, name); | ||||
1454 | if (!bm) return NULL((void*)0); | ||||
1455 | return bm->node; | ||||
1456 | } | ||||
1457 | |||||
1458 | /* Delete a named bookmark. | ||||
1459 | * returns 0 if bookmark was not found, and 1 if deleted. | ||||
1460 | * Note that the bookmark memory is not freed yet, and is kept for future use. */ | ||||
1461 | int quicklistBookmarkDelete(quicklist *ql, const char *name) { | ||||
1462 | quicklistBookmark *bm = _quicklistBookmarkFindByName(ql, name); | ||||
1463 | if (!bm) | ||||
1464 | return 0; | ||||
1465 | _quicklistBookmarkDelete(ql, bm); | ||||
1466 | return 1; | ||||
1467 | } | ||||
1468 | |||||
1469 | quicklistBookmark *_quicklistBookmarkFindByName(quicklist *ql, const char *name) { | ||||
1470 | unsigned i; | ||||
1471 | for (i=0; i<ql->bookmark_count; i++) { | ||||
1472 | if (!strcmp(ql->bookmarks[i].name, name)) { | ||||
1473 | return &ql->bookmarks[i]; | ||||
1474 | } | ||||
1475 | } | ||||
1476 | return NULL((void*)0); | ||||
1477 | } | ||||
1478 | |||||
1479 | quicklistBookmark *_quicklistBookmarkFindByNode(quicklist *ql, quicklistNode *node) { | ||||
1480 | unsigned i; | ||||
1481 | for (i=0; i<ql->bookmark_count; i++) { | ||||
1482 | if (ql->bookmarks[i].node == node) { | ||||
1483 | return &ql->bookmarks[i]; | ||||
1484 | } | ||||
1485 | } | ||||
1486 | return NULL((void*)0); | ||||
1487 | } | ||||
1488 | |||||
1489 | void _quicklistBookmarkDelete(quicklist *ql, quicklistBookmark *bm) { | ||||
1490 | int index = bm - ql->bookmarks; | ||||
1491 | zfree(bm->name); | ||||
1492 | ql->bookmark_count--; | ||||
1493 | memmove(bm, bm+1, (ql->bookmark_count - index)* sizeof(*bm)); | ||||
1494 | /* NOTE: We do not shrink (realloc) the quicklist yet (to avoid resonance, | ||||
1495 | * it may be re-used later (a call to realloc may NOP). */ | ||||
1496 | } | ||||
1497 | |||||
1498 | void quicklistBookmarksClear(quicklist *ql) { | ||||
1499 | while (ql->bookmark_count) | ||||
1500 | zfree(ql->bookmarks[--ql->bookmark_count].name); | ||||
1501 | /* NOTE: We do not shrink (realloc) the quick list. main use case for this | ||||
1502 | * function is just before releasing the allocation. */ | ||||
1503 | } | ||||
1504 | |||||
1505 | /* The rest of this file is test cases and test helpers. */ | ||||
1506 | #ifdef REDIS_TEST | ||||
1507 | #include <stdint.h> | ||||
1508 | #include <sys/time.h> | ||||
1509 | |||||
1510 | #define yell(str, ...) printf("ERROR! " str "\n\n", __VA_ARGS__) | ||||
1511 | |||||
1512 | #define OK printf("\tOK\n") | ||||
1513 | |||||
1514 | #define ERROR \ | ||||
1515 | do { \ | ||||
1516 | printf("\tERROR!\n"); \ | ||||
1517 | err++; \ | ||||
1518 | } while (0) | ||||
1519 | |||||
1520 | #define ERR(x, ...) \ | ||||
1521 | do { \ | ||||
1522 | printf("%s:%s:%d:\t", __FILE__"quicklist.c", __func__, __LINE__1522); \ | ||||
1523 | printf("ERROR! " x "\n", __VA_ARGS__); \ | ||||
1524 | err++; \ | ||||
1525 | } while (0) | ||||
1526 | |||||
1527 | #define TEST(name) printf("test — %s\n", name); | ||||
1528 | #define TEST_DESC(name, ...) printf("test — " name "\n", __VA_ARGS__); | ||||
1529 | |||||
1530 | #define QL_TEST_VERBOSE 0 | ||||
1531 | |||||
1532 | #define UNUSED(x) (void)(x) | ||||
1533 | static void ql_info(quicklist *ql) { | ||||
1534 | #if QL_TEST_VERBOSE | ||||
1535 | printf("Container length: %lu\n", ql->len); | ||||
1536 | printf("Container size: %lu\n", ql->count); | ||||
1537 | if (ql->head) | ||||
1538 | printf("\t(zsize head: %d)\n", ziplistLen(ql->head->zl)); | ||||
1539 | if (ql->tail) | ||||
1540 | printf("\t(zsize tail: %d)\n", ziplistLen(ql->tail->zl)); | ||||
1541 | printf("\n"); | ||||
1542 | #else | ||||
1543 | UNUSED(ql); | ||||
1544 | #endif | ||||
1545 | } | ||||
1546 | |||||
1547 | /* Return the UNIX time in microseconds */ | ||||
1548 | static long long ustime(void) { | ||||
1549 | struct timeval tv; | ||||
1550 | long long ust; | ||||
1551 | |||||
1552 | gettimeofday(&tv, NULL((void*)0)); | ||||
1553 | ust = ((long long)tv.tv_sec) * 1000000; | ||||
1554 | ust += tv.tv_usec; | ||||
1555 | return ust; | ||||
1556 | } | ||||
1557 | |||||
1558 | /* Return the UNIX time in milliseconds */ | ||||
1559 | static long long mstime(void) { return ustime() / 1000; } | ||||
1560 | |||||
1561 | /* Iterate over an entire quicklist. | ||||
1562 | * Print the list if 'print' == 1. | ||||
1563 | * | ||||
1564 | * Returns physical count of elements found by iterating over the list. */ | ||||
1565 | static int _itrprintr(quicklist *ql, int print, int forward) { | ||||
1566 | quicklistIter *iter = | ||||
1567 | quicklistGetIterator(ql, forward ? AL_START_HEAD0 : AL_START_TAIL1); | ||||
1568 | quicklistEntry entry; | ||||
1569 | int i = 0; | ||||
1570 | int p = 0; | ||||
1571 | quicklistNode *prev = NULL((void*)0); | ||||
1572 | while (quicklistNext(iter, &entry)) { | ||||
1573 | if (entry.node != prev) { | ||||
1574 | /* Count the number of list nodes too */ | ||||
1575 | p++; | ||||
1576 | prev = entry.node; | ||||
1577 | } | ||||
1578 | if (print) { | ||||
1579 | printf("[%3d (%2d)]: [%.*s] (%lld)\n", i, p, entry.sz, | ||||
1580 | (char *)entry.value, entry.longval); | ||||
1581 | } | ||||
1582 | i++; | ||||
1583 | } | ||||
1584 | quicklistReleaseIterator(iter); | ||||
1585 | return i; | ||||
1586 | } | ||||
1587 | static int itrprintr(quicklist *ql, int print) { | ||||
1588 | return _itrprintr(ql, print, 1); | ||||
1589 | } | ||||
1590 | |||||
1591 | static int itrprintr_rev(quicklist *ql, int print) { | ||||
1592 | return _itrprintr(ql, print, 0); | ||||
1593 | } | ||||
1594 | |||||
1595 | #define ql_verify(a, b, c, d, e) \ | ||||
1596 | do { \ | ||||
1597 | err += _ql_verify((a), (b), (c), (d), (e)); \ | ||||
1598 | } while (0) | ||||
1599 | |||||
1600 | /* Verify list metadata matches physical list contents. */ | ||||
1601 | static int _ql_verify(quicklist *ql, uint32_t len, uint32_t count, | ||||
1602 | uint32_t head_count, uint32_t tail_count) { | ||||
1603 | int errors = 0; | ||||
1604 | |||||
1605 | ql_info(ql); | ||||
1606 | if (len != ql->len) { | ||||
1607 | yell("quicklist length wrong: expected %d, got %lu", len, ql->len); | ||||
1608 | errors++; | ||||
1609 | } | ||||
1610 | |||||
1611 | if (count != ql->count) { | ||||
1612 | yell("quicklist count wrong: expected %d, got %lu", count, ql->count); | ||||
1613 | errors++; | ||||
1614 | } | ||||
1615 | |||||
1616 | int loopr = itrprintr(ql, 0); | ||||
1617 | if (loopr != (int)ql->count) { | ||||
1618 | yell("quicklist cached count not match actual count: expected %lu, got " | ||||
1619 | "%d", | ||||
1620 | ql->count, loopr); | ||||
1621 | errors++; | ||||
1622 | } | ||||
1623 | |||||
1624 | int rloopr = itrprintr_rev(ql, 0); | ||||
1625 | if (loopr != rloopr) { | ||||
1626 | yell("quicklist has different forward count than reverse count! " | ||||
1627 | "Forward count is %d, reverse count is %d.", | ||||
1628 | loopr, rloopr); | ||||
1629 | errors++; | ||||
1630 | } | ||||
1631 | |||||
1632 | if (ql->len == 0 && !errors) { | ||||
1633 | OK; | ||||
1634 | return errors; | ||||
1635 | } | ||||
1636 | |||||
1637 | if (ql->head && head_count != ql->head->count && | ||||
1638 | head_count != ziplistLen(ql->head->zl)) { | ||||
1639 | yell("quicklist head count wrong: expected %d, " | ||||
1640 | "got cached %d vs. actual %d", | ||||
1641 | head_count, ql->head->count, ziplistLen(ql->head->zl)); | ||||
1642 | errors++; | ||||
1643 | } | ||||
1644 | |||||
1645 | if (ql->tail && tail_count != ql->tail->count && | ||||
1646 | tail_count != ziplistLen(ql->tail->zl)) { | ||||
1647 | yell("quicklist tail count wrong: expected %d, " | ||||
1648 | "got cached %u vs. actual %d", | ||||
1649 | tail_count, ql->tail->count, ziplistLen(ql->tail->zl)); | ||||
1650 | errors++; | ||||
1651 | } | ||||
1652 | |||||
1653 | if (quicklistAllowsCompression(ql)((ql)->compress != 0)) { | ||||
1654 | quicklistNode *node = ql->head; | ||||
1655 | unsigned int low_raw = ql->compress; | ||||
1656 | unsigned int high_raw = ql->len - ql->compress; | ||||
1657 | |||||
1658 | for (unsigned int at = 0; at < ql->len; at++, node = node->next) { | ||||
1659 | if (node && (at < low_raw || at >= high_raw)) { | ||||
1660 | if (node->encoding != QUICKLIST_NODE_ENCODING_RAW1) { | ||||
1661 | yell("Incorrect compression: node %d is " | ||||
1662 | "compressed at depth %d ((%u, %u); total " | ||||
1663 | "nodes: %lu; size: %u; recompress: %d)", | ||||
1664 | at, ql->compress, low_raw, high_raw, ql->len, node->sz, | ||||
1665 | node->recompress); | ||||
1666 | errors++; | ||||
1667 | } | ||||
1668 | } else { | ||||
1669 | if (node->encoding != QUICKLIST_NODE_ENCODING_LZF2 && | ||||
1670 | !node->attempted_compress) { | ||||
1671 | yell("Incorrect non-compression: node %d is NOT " | ||||
1672 | "compressed at depth %d ((%u, %u); total " | ||||
1673 | "nodes: %lu; size: %u; recompress: %d; attempted: %d)", | ||||
1674 | at, ql->compress, low_raw, high_raw, ql->len, node->sz, | ||||
1675 | node->recompress, node->attempted_compress); | ||||
1676 | errors++; | ||||
1677 | } | ||||
1678 | } | ||||
1679 | } | ||||
1680 | } | ||||
1681 | |||||
1682 | if (!errors) | ||||
1683 | OK; | ||||
1684 | return errors; | ||||
1685 | } | ||||
1686 | |||||
1687 | /* Generate new string concatenating integer i against string 'prefix' */ | ||||
1688 | static char *genstr(char *prefix, int i) { | ||||
1689 | static char result[64] = {0}; | ||||
1690 | snprintf(result, sizeof(result), "%s%d", prefix, i); | ||||
1691 | return result; | ||||
1692 | } | ||||
1693 | |||||
1694 | /* main test, but callable from other files */ | ||||
1695 | int quicklistTest(int argc, char *argv[]) { | ||||
1696 | UNUSED(argc); | ||||
1697 | UNUSED(argv); | ||||
1698 | |||||
1699 | unsigned int err = 0; | ||||
1700 | int optimize_start = | ||||
1701 | -(int)(sizeof(optimization_level) / sizeof(*optimization_level)); | ||||
1702 | |||||
1703 | printf("Starting optimization offset at: %d\n", optimize_start); | ||||
1704 | |||||
1705 | int options[] = {0, 1, 2, 3, 4, 5, 6, 10}; | ||||
1706 | size_t option_count = sizeof(options) / sizeof(*options); | ||||
1707 | long long runtime[option_count]; | ||||
1708 | |||||
1709 | for (int _i = 0; _i < (int)option_count; _i++) { | ||||
1710 | printf("Testing Option %d\n", options[_i]); | ||||
1711 | long long start = mstime(); | ||||
1712 | |||||
1713 | TEST("create list") { | ||||
1714 | quicklist *ql = quicklistNew(-2, options[_i]); | ||||
1715 | ql_verify(ql, 0, 0, 0, 0); | ||||
1716 | quicklistRelease(ql); | ||||
1717 | } | ||||
1718 | |||||
1719 | TEST("add to tail of empty list") { | ||||
1720 | quicklist *ql = quicklistNew(-2, options[_i]); | ||||
1721 | quicklistPushTail(ql, "hello", 6); | ||||
1722 | /* 1 for head and 1 for tail because 1 node = head = tail */ | ||||
1723 | ql_verify(ql, 1, 1, 1, 1); | ||||
1724 | quicklistRelease(ql); | ||||
1725 | } | ||||
1726 | |||||
1727 | TEST("add to head of empty list") { | ||||
1728 | quicklist *ql = quicklistNew(-2, options[_i]); | ||||
1729 | quicklistPushHead(ql, "hello", 6); | ||||
1730 | /* 1 for head and 1 for tail because 1 node = head = tail */ | ||||
1731 | ql_verify(ql, 1, 1, 1, 1); | ||||
1732 | quicklistRelease(ql); | ||||
1733 | } | ||||
1734 | |||||
1735 | for (int f = optimize_start; f < 32; f++) { | ||||
1736 | TEST_DESC("add to tail 5x at fill %d at compress %d", f, | ||||
1737 | options[_i]) { | ||||
1738 | quicklist *ql = quicklistNew(f, options[_i]); | ||||
1739 | for (int i = 0; i < 5; i++) | ||||
1740 | quicklistPushTail(ql, genstr("hello", i), 32); | ||||
1741 | if (ql->count != 5) | ||||
1742 | ERROR; | ||||
1743 | if (f == 32) | ||||
1744 | ql_verify(ql, 1, 5, 5, 5); | ||||
1745 | quicklistRelease(ql); | ||||
1746 | } | ||||
1747 | } | ||||
1748 | |||||
1749 | for (int f = optimize_start; f < 32; f++) { | ||||
1750 | TEST_DESC("add to head 5x at fill %d at compress %d", f, | ||||
1751 | options[_i]) { | ||||
1752 | quicklist *ql = quicklistNew(f, options[_i]); | ||||
1753 | for (int i = 0; i < 5; i++) | ||||
1754 | quicklistPushHead(ql, genstr("hello", i), 32); | ||||
1755 | if (ql->count != 5) | ||||
1756 | ERROR; | ||||
1757 | if (f == 32) | ||||
1758 | ql_verify(ql, 1, 5, 5, 5); | ||||
1759 | quicklistRelease(ql); | ||||
1760 | } | ||||
1761 | } | ||||
1762 | |||||
1763 | for (int f = optimize_start; f < 512; f++) { | ||||
1764 | TEST_DESC("add to tail 500x at fill %d at compress %d", f, | ||||
1765 | options[_i]) { | ||||
1766 | quicklist *ql = quicklistNew(f, options[_i]); | ||||
1767 | for (int i = 0; i < 500; i++) | ||||
1768 | quicklistPushTail(ql, genstr("hello", i), 64); | ||||
1769 | if (ql->count != 500) | ||||
1770 | ERROR; | ||||
1771 | if (f == 32) | ||||
1772 | ql_verify(ql, 16, 500, 32, 20); | ||||
1773 | quicklistRelease(ql); | ||||
1774 | } | ||||
1775 | } | ||||
1776 | |||||
1777 | for (int f = optimize_start; f < 512; f++) { | ||||
1778 | TEST_DESC("add to head 500x at fill %d at compress %d", f, | ||||
1779 | options[_i]) { | ||||
1780 | quicklist *ql = quicklistNew(f, options[_i]); | ||||
1781 | for (int i = 0; i < 500; i++) | ||||
1782 | quicklistPushHead(ql, genstr("hello", i), 32); | ||||
1783 | if (ql->count != 500) | ||||
1784 | ERROR; | ||||
1785 | if (f == 32) | ||||
1786 | ql_verify(ql, 16, 500, 20, 32); | ||||
1787 | quicklistRelease(ql); | ||||
1788 | } | ||||
1789 | } | ||||
1790 | |||||
1791 | TEST("rotate empty") { | ||||
1792 | quicklist *ql = quicklistNew(-2, options[_i]); | ||||
1793 | quicklistRotate(ql); | ||||
1794 | ql_verify(ql, 0, 0, 0, 0); | ||||
1795 | quicklistRelease(ql); | ||||
1796 | } | ||||
1797 | |||||
1798 | for (int f = optimize_start; f < 32; f++) { | ||||
1799 | TEST("rotate one val once") { | ||||
1800 | quicklist *ql = quicklistNew(f, options[_i]); | ||||
1801 | quicklistPushHead(ql, "hello", 6); | ||||
1802 | quicklistRotate(ql); | ||||
1803 | /* Ignore compression verify because ziplist is | ||||
1804 | * too small to compress. */ | ||||
1805 | ql_verify(ql, 1, 1, 1, 1); | ||||
1806 | quicklistRelease(ql); | ||||
1807 | } | ||||
1808 | } | ||||
1809 | |||||
1810 | for (int f = optimize_start; f < 3; f++) { | ||||
1811 | TEST_DESC("rotate 500 val 5000 times at fill %d at compress %d", f, | ||||
1812 | options[_i]) { | ||||
1813 | quicklist *ql = quicklistNew(f, options[_i]); | ||||
1814 | quicklistPushHead(ql, "900", 3); | ||||
1815 | quicklistPushHead(ql, "7000", 4); | ||||
1816 | quicklistPushHead(ql, "-1200", 5); | ||||
1817 | quicklistPushHead(ql, "42", 2); | ||||
1818 | for (int i = 0; i < 500; i++) | ||||
1819 | quicklistPushHead(ql, genstr("hello", i), 64); | ||||
1820 | ql_info(ql); | ||||
1821 | for (int i = 0; i < 5000; i++) { | ||||
1822 | ql_info(ql); | ||||
1823 | quicklistRotate(ql); | ||||
1824 | } | ||||
1825 | if (f == 1) | ||||
1826 | ql_verify(ql, 504, 504, 1, 1); | ||||
1827 | else if (f == 2) | ||||
1828 | ql_verify(ql, 252, 504, 2, 2); | ||||
1829 | else if (f == 32) | ||||
1830 | ql_verify(ql, 16, 504, 32, 24); | ||||
1831 | quicklistRelease(ql); | ||||
1832 | } | ||||
1833 | } | ||||
1834 | |||||
1835 | TEST("pop empty") { | ||||
1836 | quicklist *ql = quicklistNew(-2, options[_i]); | ||||
1837 | quicklistPop(ql, QUICKLIST_HEAD0, NULL((void*)0), NULL((void*)0), NULL((void*)0)); | ||||
1838 | ql_verify(ql, 0, 0, 0, 0); | ||||
1839 | quicklistRelease(ql); | ||||
1840 | } | ||||
1841 | |||||
1842 | TEST("pop 1 string from 1") { | ||||
1843 | quicklist *ql = quicklistNew(-2, options[_i]); | ||||
1844 | char *populate = genstr("hello", 331); | ||||
1845 | quicklistPushHead(ql, populate, 32); | ||||
1846 | unsigned char *data; | ||||
1847 | unsigned int sz; | ||||
1848 | long long lv; | ||||
1849 | ql_info(ql); | ||||
1850 | quicklistPop(ql, QUICKLIST_HEAD0, &data, &sz, &lv); | ||||
1851 | assert(data != NULL)(__builtin_expect(!!((data != ((void*)0))), 1)?(void)0 : (_serverAssert ("data != NULL","quicklist.c",1851),__builtin_unreachable())); | ||||
1852 | assert(sz == 32)(__builtin_expect(!!((sz == 32)), 1)?(void)0 : (_serverAssert ("sz == 32","quicklist.c",1852),__builtin_unreachable())); | ||||
1853 | if (strcmp(populate, (char *)data)) | ||||
1854 | ERR("Pop'd value (%.*s) didn't equal original value (%s)", sz, | ||||
1855 | data, populate); | ||||
1856 | zfree(data); | ||||
1857 | ql_verify(ql, 0, 0, 0, 0); | ||||
1858 | quicklistRelease(ql); | ||||
1859 | } | ||||
1860 | |||||
1861 | TEST("pop head 1 number from 1") { | ||||
1862 | quicklist *ql = quicklistNew(-2, options[_i]); | ||||
1863 | quicklistPushHead(ql, "55513", 5); | ||||
1864 | unsigned char *data; | ||||
1865 | unsigned int sz; | ||||
1866 | long long lv; | ||||
1867 | ql_info(ql); | ||||
1868 | quicklistPop(ql, QUICKLIST_HEAD0, &data, &sz, &lv); | ||||
1869 | assert(data == NULL)(__builtin_expect(!!((data == ((void*)0))), 1)?(void)0 : (_serverAssert ("data == NULL","quicklist.c",1869),__builtin_unreachable())); | ||||
1870 | assert(lv == 55513)(__builtin_expect(!!((lv == 55513)), 1)?(void)0 : (_serverAssert ("lv == 55513","quicklist.c",1870),__builtin_unreachable())); | ||||
1871 | ql_verify(ql, 0, 0, 0, 0); | ||||
1872 | quicklistRelease(ql); | ||||
1873 | } | ||||
1874 | |||||
1875 | TEST("pop head 500 from 500") { | ||||
1876 | quicklist *ql = quicklistNew(-2, options[_i]); | ||||
1877 | for (int i = 0; i < 500; i++) | ||||
1878 | quicklistPushHead(ql, genstr("hello", i), 32); | ||||
1879 | ql_info(ql); | ||||
1880 | for (int i = 0; i < 500; i++) { | ||||
1881 | unsigned char *data; | ||||
1882 | unsigned int sz; | ||||
1883 | long long lv; | ||||
1884 | int ret = quicklistPop(ql, QUICKLIST_HEAD0, &data, &sz, &lv); | ||||
1885 | assert(ret == 1)(__builtin_expect(!!((ret == 1)), 1)?(void)0 : (_serverAssert ("ret == 1","quicklist.c",1885),__builtin_unreachable())); | ||||
1886 | assert(data != NULL)(__builtin_expect(!!((data != ((void*)0))), 1)?(void)0 : (_serverAssert ("data != NULL","quicklist.c",1886),__builtin_unreachable())); | ||||
1887 | assert(sz == 32)(__builtin_expect(!!((sz == 32)), 1)?(void)0 : (_serverAssert ("sz == 32","quicklist.c",1887),__builtin_unreachable())); | ||||
1888 | if (strcmp(genstr("hello", 499 - i), (char *)data)) | ||||
1889 | ERR("Pop'd value (%.*s) didn't equal original value (%s)", | ||||
1890 | sz, data, genstr("hello", 499 - i)); | ||||
1891 | zfree(data); | ||||
1892 | } | ||||
1893 | ql_verify(ql, 0, 0, 0, 0); | ||||
1894 | quicklistRelease(ql); | ||||
1895 | } | ||||
1896 | |||||
1897 | TEST("pop head 5000 from 500") { | ||||
1898 | quicklist *ql = quicklistNew(-2, options[_i]); | ||||
1899 | for (int i = 0; i < 500; i++) | ||||
1900 | quicklistPushHead(ql, genstr("hello", i), 32); | ||||
1901 | for (int i = 0; i < 5000; i++) { | ||||
1902 | unsigned char *data; | ||||
1903 | unsigned int sz; | ||||
1904 | long long lv; | ||||
1905 | int ret = quicklistPop(ql, QUICKLIST_HEAD0, &data, &sz, &lv); | ||||
1906 | if (i < 500) { | ||||
1907 | assert(ret == 1)(__builtin_expect(!!((ret == 1)), 1)?(void)0 : (_serverAssert ("ret == 1","quicklist.c",1907),__builtin_unreachable())); | ||||
1908 | assert(data != NULL)(__builtin_expect(!!((data != ((void*)0))), 1)?(void)0 : (_serverAssert ("data != NULL","quicklist.c",1908),__builtin_unreachable())); | ||||
1909 | assert(sz == 32)(__builtin_expect(!!((sz == 32)), 1)?(void)0 : (_serverAssert ("sz == 32","quicklist.c",1909),__builtin_unreachable())); | ||||
1910 | if (strcmp(genstr("hello", 499 - i), (char *)data)) | ||||
1911 | ERR("Pop'd value (%.*s) didn't equal original value " | ||||
1912 | "(%s)", | ||||
1913 | sz, data, genstr("hello", 499 - i)); | ||||
1914 | zfree(data); | ||||
1915 | } else { | ||||
1916 | assert(ret == 0)(__builtin_expect(!!((ret == 0)), 1)?(void)0 : (_serverAssert ("ret == 0","quicklist.c",1916),__builtin_unreachable())); | ||||
1917 | } | ||||
1918 | } | ||||
1919 | ql_verify(ql, 0, 0, 0, 0); | ||||
1920 | quicklistRelease(ql); | ||||
1921 | } | ||||
1922 | |||||
1923 | TEST("iterate forward over 500 list") { | ||||
1924 | quicklist *ql = quicklistNew(-2, options[_i]); | ||||
1925 | quicklistSetFill(ql, 32); | ||||
1926 | for (int i = 0; i < 500; i++) | ||||
1927 | quicklistPushHead(ql, genstr("hello", i), 32); | ||||
1928 | quicklistIter *iter = quicklistGetIterator(ql, AL_START_HEAD0); | ||||
1929 | quicklistEntry entry; | ||||
1930 | int i = 499, count = 0; | ||||
1931 | while (quicklistNext(iter, &entry)) { | ||||
1932 | char *h = genstr("hello", i); | ||||
1933 | if (strcmp((char *)entry.value, h)) | ||||
1934 | ERR("value [%s] didn't match [%s] at position %d", | ||||
1935 | entry.value, h, i); | ||||
1936 | i--; | ||||
1937 | count++; | ||||
1938 | } | ||||
1939 | if (count != 500) | ||||
1940 | ERR("Didn't iterate over exactly 500 elements (%d)", i); | ||||
1941 | ql_verify(ql, 16, 500, 20, 32); | ||||
1942 | quicklistReleaseIterator(iter); | ||||
1943 | quicklistRelease(ql); | ||||
1944 | } | ||||
1945 | |||||
1946 | TEST("iterate reverse over 500 list") { | ||||
1947 | quicklist *ql = quicklistNew(-2, options[_i]); | ||||
1948 | quicklistSetFill(ql, 32); | ||||
1949 | for (int i = 0; i < 500; i++) | ||||
1950 | quicklistPushHead(ql, genstr("hello", i), 32); | ||||
1951 | quicklistIter *iter = quicklistGetIterator(ql, AL_START_TAIL1); | ||||
1952 | quicklistEntry entry; | ||||
1953 | int i = 0; | ||||
1954 | while (quicklistNext(iter, &entry)) { | ||||
1955 | char *h = genstr("hello", i); | ||||
1956 | if (strcmp((char *)entry.value, h)) | ||||
1957 | ERR("value [%s] didn't match [%s] at position %d", | ||||
1958 | entry.value, h, i); | ||||
1959 | i++; | ||||
1960 | } | ||||
1961 | if (i != 500) | ||||
1962 | ERR("Didn't iterate over exactly 500 elements (%d)", i); | ||||
1963 | ql_verify(ql, 16, 500, 20, 32); | ||||
1964 | quicklistReleaseIterator(iter); | ||||
1965 | quicklistRelease(ql); | ||||
1966 | } | ||||
1967 | |||||
1968 | TEST("insert before with 0 elements") { | ||||
1969 | quicklist *ql = quicklistNew(-2, options[_i]); | ||||
1970 | quicklistEntry entry; | ||||
1971 | quicklistIndex(ql, 0, &entry); | ||||
1972 | quicklistInsertBefore(ql, &entry, "abc", 4); | ||||
1973 | ql_verify(ql, 1, 1, 1, 1); | ||||
1974 | quicklistRelease(ql); | ||||
1975 | } | ||||
1976 | |||||
1977 | TEST("insert after with 0 elements") { | ||||
1978 | quicklist *ql = quicklistNew(-2, options[_i]); | ||||
1979 | quicklistEntry entry; | ||||
1980 | quicklistIndex(ql, 0, &entry); | ||||
1981 | quicklistInsertAfter(ql, &entry, "abc", 4); | ||||
1982 | ql_verify(ql, 1, 1, 1, 1); | ||||
1983 | quicklistRelease(ql); | ||||
1984 | } | ||||
1985 | |||||
1986 | TEST("insert after 1 element") { | ||||
1987 | quicklist *ql = quicklistNew(-2, options[_i]); | ||||
1988 | quicklistPushHead(ql, "hello", 6); | ||||
1989 | quicklistEntry entry; | ||||
1990 | quicklistIndex(ql, 0, &entry); | ||||
1991 | quicklistInsertAfter(ql, &entry, "abc", 4); | ||||
1992 | ql_verify(ql, 1, 2, 2, 2); | ||||
1993 | quicklistRelease(ql); | ||||
1994 | } | ||||
1995 | |||||
1996 | TEST("insert before 1 element") { | ||||
1997 | quicklist *ql = quicklistNew(-2, options[_i]); | ||||
1998 | quicklistPushHead(ql, "hello", 6); | ||||
1999 | quicklistEntry entry; | ||||
2000 | quicklistIndex(ql, 0, &entry); | ||||
2001 | quicklistInsertAfter(ql, &entry, "abc", 4); | ||||
2002 | ql_verify(ql, 1, 2, 2, 2); | ||||
2003 | quicklistRelease(ql); | ||||
2004 | } | ||||
2005 | |||||
2006 | for (int f = optimize_start; f < 12; f++) { | ||||
2007 | TEST_DESC("insert once in elements while iterating at fill %d at " | ||||
2008 | "compress %d\n", | ||||
2009 | f, options[_i]) { | ||||
2010 | quicklist *ql = quicklistNew(f, options[_i]); | ||||
2011 | quicklistPushTail(ql, "abc", 3); | ||||
2012 | quicklistSetFill(ql, 1); | ||||
2013 | quicklistPushTail(ql, "def", 3); /* force to unique node */ | ||||
2014 | quicklistSetFill(ql, f); | ||||
2015 | quicklistPushTail(ql, "bob", 3); /* force to reset for +3 */ | ||||
2016 | quicklistPushTail(ql, "foo", 3); | ||||
2017 | quicklistPushTail(ql, "zoo", 3); | ||||
2018 | |||||
2019 | itrprintr(ql, 0); | ||||
2020 | /* insert "bar" before "bob" while iterating over list. */ | ||||
2021 | quicklistIter *iter = quicklistGetIterator(ql, AL_START_HEAD0); | ||||
2022 | quicklistEntry entry; | ||||
2023 | while (quicklistNext(iter, &entry)) { | ||||
2024 | if (!strncmp((char *)entry.value, "bob", 3)) { | ||||
2025 | /* Insert as fill = 1 so it spills into new node. */ | ||||
2026 | quicklistInsertBefore(ql, &entry, "bar", 3); | ||||
2027 | break; /* didn't we fix insert-while-iterating? */ | ||||
2028 | } | ||||
2029 | } | ||||
2030 | itrprintr(ql, 0); | ||||
2031 | |||||
2032 | /* verify results */ | ||||
2033 | quicklistIndex(ql, 0, &entry); | ||||
2034 | if (strncmp((char *)entry.value, "abc", 3)) | ||||
2035 | ERR("Value 0 didn't match, instead got: %.*s", entry.sz, | ||||
2036 | entry.value); | ||||
2037 | quicklistIndex(ql, 1, &entry); | ||||
2038 | if (strncmp((char *)entry.value, "def", 3)) | ||||
2039 | ERR("Value 1 didn't match, instead got: %.*s", entry.sz, | ||||
2040 | entry.value); | ||||
2041 | quicklistIndex(ql, 2, &entry); | ||||
2042 | if (strncmp((char *)entry.value, "bar", 3)) | ||||
2043 | ERR("Value 2 didn't match, instead got: %.*s", entry.sz, | ||||
2044 | entry.value); | ||||
2045 | quicklistIndex(ql, 3, &entry); | ||||
2046 | if (strncmp((char *)entry.value, "bob", 3)) | ||||
2047 | ERR("Value 3 didn't match, instead got: %.*s", entry.sz, | ||||
2048 | entry.value); | ||||
2049 | quicklistIndex(ql, 4, &entry); | ||||
2050 | if (strncmp((char *)entry.value, "foo", 3)) | ||||
2051 | ERR("Value 4 didn't match, instead got: %.*s", entry.sz, | ||||
2052 | entry.value); | ||||
2053 | quicklistIndex(ql, 5, &entry); | ||||
2054 | if (strncmp((char *)entry.value, "zoo", 3)) | ||||
2055 | ERR("Value 5 didn't match, instead got: %.*s", entry.sz, | ||||
2056 | entry.value); | ||||
2057 | quicklistReleaseIterator(iter); | ||||
2058 | quicklistRelease(ql); | ||||
2059 | } | ||||
2060 | } | ||||
2061 | |||||
2062 | for (int f = optimize_start; f < 1024; f++) { | ||||
2063 | TEST_DESC( | ||||
2064 | "insert [before] 250 new in middle of 500 elements at fill" | ||||
2065 | " %d at compress %d", | ||||
2066 | f, options[_i]) { | ||||
2067 | quicklist *ql = quicklistNew(f, options[_i]); | ||||
2068 | for (int i = 0; i < 500; i++) | ||||
2069 | quicklistPushTail(ql, genstr("hello", i), 32); | ||||
2070 | for (int i = 0; i < 250; i++) { | ||||
2071 | quicklistEntry entry; | ||||
2072 | quicklistIndex(ql, 250, &entry); | ||||
2073 | quicklistInsertBefore(ql, &entry, genstr("abc", i), 32); | ||||
2074 | } | ||||
2075 | if (f == 32) | ||||
2076 | ql_verify(ql, 25, 750, 32, 20); | ||||
2077 | quicklistRelease(ql); | ||||
2078 | } | ||||
2079 | } | ||||
2080 | |||||
2081 | for (int f = optimize_start; f < 1024; f++) { | ||||
2082 | TEST_DESC("insert [after] 250 new in middle of 500 elements at " | ||||
2083 | "fill %d at compress %d", | ||||
2084 | f, options[_i]) { | ||||
2085 | quicklist *ql = quicklistNew(f, options[_i]); | ||||
2086 | for (int i = 0; i < 500; i++) | ||||
2087 | quicklistPushHead(ql, genstr("hello", i), 32); | ||||
2088 | for (int i = 0; i < 250; i++) { | ||||
2089 | quicklistEntry entry; | ||||
2090 | quicklistIndex(ql, 250, &entry); | ||||
2091 | quicklistInsertAfter(ql, &entry, genstr("abc", i), 32); | ||||
2092 | } | ||||
2093 | |||||
2094 | if (ql->count != 750) | ||||
2095 | ERR("List size not 750, but rather %ld", ql->count); | ||||
2096 | |||||
2097 | if (f == 32) | ||||
2098 | ql_verify(ql, 26, 750, 20, 32); | ||||
2099 | quicklistRelease(ql); | ||||
2100 | } | ||||
2101 | } | ||||
2102 | |||||
2103 | TEST("duplicate empty list") { | ||||
2104 | quicklist *ql = quicklistNew(-2, options[_i]); | ||||
2105 | ql_verify(ql, 0, 0, 0, 0); | ||||
2106 | quicklist *copy = quicklistDup(ql); | ||||
2107 | ql_verify(copy, 0, 0, 0, 0); | ||||
2108 | quicklistRelease(ql); | ||||
2109 | quicklistRelease(copy); | ||||
2110 | } | ||||
2111 | |||||
2112 | TEST("duplicate list of 1 element") { | ||||
2113 | quicklist *ql = quicklistNew(-2, options[_i]); | ||||
2114 | quicklistPushHead(ql, genstr("hello", 3), 32); | ||||
2115 | ql_verify(ql, 1, 1, 1, 1); | ||||
2116 | quicklist *copy = quicklistDup(ql); | ||||
2117 | ql_verify(copy, 1, 1, 1, 1); | ||||
2118 | quicklistRelease(ql); | ||||
2119 | quicklistRelease(copy); | ||||
2120 | } | ||||
2121 | |||||
2122 | TEST("duplicate list of 500") { | ||||
2123 | quicklist *ql = quicklistNew(-2, options[_i]); | ||||
2124 | quicklistSetFill(ql, 32); | ||||
2125 | for (int i = 0; i < 500; i++) | ||||
2126 | quicklistPushHead(ql, genstr("hello", i), 32); | ||||
2127 | ql_verify(ql, 16, 500, 20, 32); | ||||
2128 | |||||
2129 | quicklist *copy = quicklistDup(ql); | ||||
2130 | ql_verify(copy, 16, 500, 20, 32); | ||||
2131 | quicklistRelease(ql); | ||||
2132 | quicklistRelease(copy); | ||||
2133 | } | ||||
2134 | |||||
2135 | for (int f = optimize_start; f < 512; f++) { | ||||
2136 | TEST_DESC("index 1,200 from 500 list at fill %d at compress %d", f, | ||||
2137 | options[_i]) { | ||||
2138 | quicklist *ql = quicklistNew(f, options[_i]); | ||||
2139 | for (int i = 0; i < 500; i++) | ||||
2140 | quicklistPushTail(ql, genstr("hello", i + 1), 32); | ||||
2141 | quicklistEntry entry; | ||||
2142 | quicklistIndex(ql, 1, &entry); | ||||
2143 | if (!strcmp((char *)entry.value, "hello2")) | ||||
2144 | OK; | ||||
2145 | else | ||||
2146 | ERR("Value: %s", entry.value); | ||||
2147 | quicklistIndex(ql, 200, &entry); | ||||
2148 | if (!strcmp((char *)entry.value, "hello201")) | ||||
2149 | OK; | ||||
2150 | else | ||||
2151 | ERR("Value: %s", entry.value); | ||||
2152 | quicklistRelease(ql); | ||||
2153 | } | ||||
2154 | |||||
2155 | TEST_DESC("index -1,-2 from 500 list at fill %d at compress %d", f, | ||||
2156 | options[_i]) { | ||||
2157 | quicklist *ql = quicklistNew(f, options[_i]); | ||||
2158 | for (int i = 0; i < 500; i++) | ||||
2159 | quicklistPushTail(ql, genstr("hello", i + 1), 32); | ||||
2160 | quicklistEntry entry; | ||||
2161 | quicklistIndex(ql, -1, &entry); | ||||
2162 | if (!strcmp((char *)entry.value, "hello500")) | ||||
2163 | OK; | ||||
2164 | else | ||||
2165 | ERR("Value: %s", entry.value); | ||||
2166 | quicklistIndex(ql, -2, &entry); | ||||
2167 | if (!strcmp((char *)entry.value, "hello499")) | ||||
2168 | OK; | ||||
2169 | else | ||||
2170 | ERR("Value: %s", entry.value); | ||||
2171 | quicklistRelease(ql); | ||||
2172 | } | ||||
2173 | |||||
2174 | TEST_DESC("index -100 from 500 list at fill %d at compress %d", f, | ||||
2175 | options[_i]) { | ||||
2176 | quicklist *ql = quicklistNew(f, options[_i]); | ||||
2177 | for (int i = 0; i < 500; i++) | ||||
2178 | quicklistPushTail(ql, genstr("hello", i + 1), 32); | ||||
2179 | quicklistEntry entry; | ||||
2180 | quicklistIndex(ql, -100, &entry); | ||||
2181 | if (!strcmp((char *)entry.value, "hello401")) | ||||
2182 | OK; | ||||
2183 | else | ||||
2184 | ERR("Value: %s", entry.value); | ||||
2185 | quicklistRelease(ql); | ||||
2186 | } | ||||
2187 | |||||
2188 | TEST_DESC("index too big +1 from 50 list at fill %d at compress %d", | ||||
2189 | f, options[_i]) { | ||||
2190 | quicklist *ql = quicklistNew(f, options[_i]); | ||||
2191 | for (int i = 0; i < 50; i++) | ||||
2192 | quicklistPushTail(ql, genstr("hello", i + 1), 32); | ||||
2193 | quicklistEntry entry; | ||||
2194 | if (quicklistIndex(ql, 50, &entry)) | ||||
2195 | ERR("Index found at 50 with 50 list: %.*s", entry.sz, | ||||
2196 | entry.value); | ||||
2197 | else | ||||
2198 | OK; | ||||
2199 | quicklistRelease(ql); | ||||
2200 | } | ||||
2201 | } | ||||
2202 | |||||
2203 | TEST("delete range empty list") { | ||||
2204 | quicklist *ql = quicklistNew(-2, options[_i]); | ||||
2205 | quicklistDelRange(ql, 5, 20); | ||||
2206 | ql_verify(ql, 0, 0, 0, 0); | ||||
2207 | quicklistRelease(ql); | ||||
2208 | } | ||||
2209 | |||||
2210 | TEST("delete range of entire node in list of one node") { | ||||
2211 | quicklist *ql = quicklistNew(-2, options[_i]); | ||||
2212 | for (int i = 0; i < 32; i++) | ||||
2213 | quicklistPushHead(ql, genstr("hello", i), 32); | ||||
2214 | ql_verify(ql, 1, 32, 32, 32); | ||||
2215 | quicklistDelRange(ql, 0, 32); | ||||
2216 | ql_verify(ql, 0, 0, 0, 0); | ||||
2217 | quicklistRelease(ql); | ||||
2218 | } | ||||
2219 | |||||
2220 | TEST("delete range of entire node with overflow counts") { | ||||
2221 | quicklist *ql = quicklistNew(-2, options[_i]); | ||||
2222 | for (int i = 0; i < 32; i++) | ||||
2223 | quicklistPushHead(ql, genstr("hello", i), 32); | ||||
2224 | ql_verify(ql, 1, 32, 32, 32); | ||||
2225 | quicklistDelRange(ql, 0, 128); | ||||
2226 | ql_verify(ql, 0, 0, 0, 0); | ||||
2227 | quicklistRelease(ql); | ||||
2228 | } | ||||
2229 | |||||
2230 | TEST("delete middle 100 of 500 list") { | ||||
2231 | quicklist *ql = quicklistNew(-2, options[_i]); | ||||
2232 | quicklistSetFill(ql, 32); | ||||
2233 | for (int i = 0; i < 500; i++) | ||||
2234 | quicklistPushTail(ql, genstr("hello", i + 1), 32); | ||||
2235 | ql_verify(ql, 16, 500, 32, 20); | ||||
2236 | quicklistDelRange(ql, 200, 100); | ||||
2237 | ql_verify(ql, 14, 400, 32, 20); | ||||
2238 | quicklistRelease(ql); | ||||
2239 | } | ||||
2240 | |||||
2241 | TEST("delete less than fill but across nodes") { | ||||
2242 | quicklist *ql = quicklistNew(-2, options[_i]); | ||||
2243 | quicklistSetFill(ql, 32); | ||||
2244 | for (int i = 0; i < 500; i++) | ||||
2245 | quicklistPushTail(ql, genstr("hello", i + 1), 32); | ||||
2246 | ql_verify(ql, 16, 500, 32, 20); | ||||
2247 | quicklistDelRange(ql, 60, 10); | ||||
2248 | ql_verify(ql, 16, 490, 32, 20); | ||||
2249 | quicklistRelease(ql); | ||||
2250 | } | ||||
2251 | |||||
2252 | TEST("delete negative 1 from 500 list") { | ||||
2253 | quicklist *ql = quicklistNew(-2, options[_i]); | ||||
2254 | quicklistSetFill(ql, 32); | ||||
2255 | for (int i = 0; i < 500; i++) | ||||
2256 | quicklistPushTail(ql, genstr("hello", i + 1), 32); | ||||
2257 | ql_verify(ql, 16, 500, 32, 20); | ||||
2258 | quicklistDelRange(ql, -1, 1); | ||||
2259 | ql_verify(ql, 16, 499, 32, 19); | ||||
2260 | quicklistRelease(ql); | ||||
2261 | } | ||||
2262 | |||||
2263 | TEST("delete negative 1 from 500 list with overflow counts") { | ||||
2264 | quicklist *ql = quicklistNew(-2, options[_i]); | ||||
2265 | quicklistSetFill(ql, 32); | ||||
2266 | for (int i = 0; i < 500; i++) | ||||
2267 | quicklistPushTail(ql, genstr("hello", i + 1), 32); | ||||
2268 | ql_verify(ql, 16, 500, 32, 20); | ||||
2269 | quicklistDelRange(ql, -1, 128); | ||||
2270 | ql_verify(ql, 16, 499, 32, 19); | ||||
2271 | quicklistRelease(ql); | ||||
2272 | } | ||||
2273 | |||||
2274 | TEST("delete negative 100 from 500 list") { | ||||
2275 | quicklist *ql = quicklistNew(-2, options[_i]); | ||||
2276 | quicklistSetFill(ql, 32); | ||||
2277 | for (int i = 0; i < 500; i++) | ||||
2278 | quicklistPushTail(ql, genstr("hello", i + 1), 32); | ||||
2279 | quicklistDelRange(ql, -100, 100); | ||||
2280 | ql_verify(ql, 13, 400, 32, 16); | ||||
2281 | quicklistRelease(ql); | ||||
2282 | } | ||||
2283 | |||||
2284 | TEST("delete -10 count 5 from 50 list") { | ||||
2285 | quicklist *ql = quicklistNew(-2, options[_i]); | ||||
2286 | quicklistSetFill(ql, 32); | ||||
2287 | for (int i = 0; i < 50; i++) | ||||
2288 | quicklistPushTail(ql, genstr("hello", i + 1), 32); | ||||
2289 | ql_verify(ql, 2, 50, 32, 18); | ||||
2290 | quicklistDelRange(ql, -10, 5); | ||||
2291 | ql_verify(ql, 2, 45, 32, 13); | ||||
2292 | quicklistRelease(ql); | ||||
2293 | } | ||||
2294 | |||||
2295 | TEST("numbers only list read") { | ||||
2296 | quicklist *ql = quicklistNew(-2, options[_i]); | ||||
2297 | quicklistPushTail(ql, "1111", 4); | ||||
2298 | quicklistPushTail(ql, "2222", 4); | ||||
2299 | quicklistPushTail(ql, "3333", 4); | ||||
2300 | quicklistPushTail(ql, "4444", 4); | ||||
2301 | ql_verify(ql, 1, 4, 4, 4); | ||||
2302 | quicklistEntry entry; | ||||
2303 | quicklistIndex(ql, 0, &entry); | ||||
2304 | if (entry.longval != 1111) | ||||
2305 | ERR("Not 1111, %lld", entry.longval); | ||||
2306 | quicklistIndex(ql, 1, &entry); | ||||
2307 | if (entry.longval != 2222) | ||||
2308 | ERR("Not 2222, %lld", entry.longval); | ||||
2309 | quicklistIndex(ql, 2, &entry); | ||||
2310 | if (entry.longval != 3333) | ||||
2311 | ERR("Not 3333, %lld", entry.longval); | ||||
2312 | quicklistIndex(ql, 3, &entry); | ||||
2313 | if (entry.longval != 4444) | ||||
2314 | ERR("Not 4444, %lld", entry.longval); | ||||
2315 | if (quicklistIndex(ql, 4, &entry)) | ||||
2316 | ERR("Index past elements: %lld", entry.longval); | ||||
2317 | quicklistIndex(ql, -1, &entry); | ||||
2318 | if (entry.longval != 4444) | ||||
2319 | ERR("Not 4444 (reverse), %lld", entry.longval); | ||||
2320 | quicklistIndex(ql, -2, &entry); | ||||
2321 | if (entry.longval != 3333) | ||||
2322 | ERR("Not 3333 (reverse), %lld", entry.longval); | ||||
2323 | quicklistIndex(ql, -3, &entry); | ||||
2324 | if (entry.longval != 2222) | ||||
2325 | ERR("Not 2222 (reverse), %lld", entry.longval); | ||||
2326 | quicklistIndex(ql, -4, &entry); | ||||
2327 | if (entry.longval != 1111) | ||||
2328 | ERR("Not 1111 (reverse), %lld", entry.longval); | ||||
2329 | if (quicklistIndex(ql, -5, &entry)) | ||||
2330 | ERR("Index past elements (reverse), %lld", entry.longval); | ||||
2331 | quicklistRelease(ql); | ||||
2332 | } | ||||
2333 | |||||
2334 | TEST("numbers larger list read") { | ||||
2335 | quicklist *ql = quicklistNew(-2, options[_i]); | ||||
2336 | quicklistSetFill(ql, 32); | ||||
2337 | char num[32]; | ||||
2338 | long long nums[5000]; | ||||
2339 | for (int i = 0; i < 5000; i++) { | ||||
2340 | nums[i] = -5157318210846258176 + i; | ||||
2341 | int sz = ll2string(num, sizeof(num), nums[i]); | ||||
2342 | quicklistPushTail(ql, num, sz); | ||||
2343 | } | ||||
2344 | quicklistPushTail(ql, "xxxxxxxxxxxxxxxxxxxx", 20); | ||||
2345 | quicklistEntry entry; | ||||
2346 | for (int i = 0; i < 5000; i++) { | ||||
2347 | quicklistIndex(ql, i, &entry); | ||||
2348 | if (entry.longval != nums[i]) | ||||
2349 | ERR("[%d] Not longval %lld but rather %lld", i, nums[i], | ||||
2350 | entry.longval); | ||||
2351 | entry.longval = 0xdeadbeef; | ||||
2352 | } | ||||
2353 | quicklistIndex(ql, 5000, &entry); | ||||
2354 | if (strncmp((char *)entry.value, "xxxxxxxxxxxxxxxxxxxx", 20)) | ||||
2355 | ERR("String val not match: %s", entry.value); | ||||
2356 | ql_verify(ql, 157, 5001, 32, 9); | ||||
2357 | quicklistRelease(ql); | ||||
2358 | } | ||||
2359 | |||||
2360 | TEST("numbers larger list read B") { | ||||
2361 | quicklist *ql = quicklistNew(-2, options[_i]); | ||||
2362 | quicklistPushTail(ql, "99", 2); | ||||
2363 | quicklistPushTail(ql, "98", 2); | ||||
2364 | quicklistPushTail(ql, "xxxxxxxxxxxxxxxxxxxx", 20); | ||||
2365 | quicklistPushTail(ql, "96", 2); | ||||
2366 | quicklistPushTail(ql, "95", 2); | ||||
2367 | quicklistReplaceAtIndex(ql, 1, "foo", 3); | ||||
2368 | quicklistReplaceAtIndex(ql, -1, "bar", 3); | ||||
2369 | quicklistRelease(ql); | ||||
2370 | OK; | ||||
2371 | } | ||||
2372 | |||||
2373 | for (int f = optimize_start; f < 16; f++) { | ||||
2374 | TEST_DESC("lrem test at fill %d at compress %d", f, options[_i]) { | ||||
2375 | quicklist *ql = quicklistNew(f, options[_i]); | ||||
2376 | char *words[] = {"abc", "foo", "bar", "foobar", "foobared", | ||||
2377 | "zap", "bar", "test", "foo"}; | ||||
2378 | char *result[] = {"abc", "foo", "foobar", "foobared", | ||||
2379 | "zap", "test", "foo"}; | ||||
2380 | char *resultB[] = {"abc", "foo", "foobar", | ||||
2381 | "foobared", "zap", "test"}; | ||||
2382 | for (int i = 0; i < 9; i++) | ||||
2383 | quicklistPushTail(ql, words[i], strlen(words[i])); | ||||
2384 | |||||
2385 | /* lrem 0 bar */ | ||||
2386 | quicklistIter *iter = quicklistGetIterator(ql, AL_START_HEAD0); | ||||
2387 | quicklistEntry entry; | ||||
2388 | int i = 0; | ||||
2389 | while (quicklistNext(iter, &entry)) { | ||||
2390 | if (quicklistCompare(entry.zi, (unsigned char *)"bar", 3)) { | ||||
2391 | quicklistDelEntry(iter, &entry); | ||||
2392 | } | ||||
2393 | i++; | ||||
2394 | } | ||||
2395 | quicklistReleaseIterator(iter); | ||||
2396 | |||||
2397 | /* check result of lrem 0 bar */ | ||||
2398 | iter = quicklistGetIterator(ql, AL_START_HEAD0); | ||||
2399 | i = 0; | ||||
2400 | int ok = 1; | ||||
2401 | while (quicklistNext(iter, &entry)) { | ||||
2402 | /* Result must be: abc, foo, foobar, foobared, zap, test, | ||||
2403 | * foo */ | ||||
2404 | if (strncmp((char *)entry.value, result[i], entry.sz)) { | ||||
2405 | ERR("No match at position %d, got %.*s instead of %s", | ||||
2406 | i, entry.sz, entry.value, result[i]); | ||||
2407 | ok = 0; | ||||
2408 | } | ||||
2409 | i++; | ||||
2410 | } | ||||
2411 | quicklistReleaseIterator(iter); | ||||
2412 | |||||
2413 | quicklistPushTail(ql, "foo", 3); | ||||
2414 | |||||
2415 | /* lrem -2 foo */ | ||||
2416 | iter = quicklistGetIterator(ql, AL_START_TAIL1); | ||||
2417 | i = 0; | ||||
2418 | int del = 2; | ||||
2419 | while (quicklistNext(iter, &entry)) { | ||||
2420 | if (quicklistCompare(entry.zi, (unsigned char *)"foo", 3)) { | ||||
2421 | quicklistDelEntry(iter, &entry); | ||||
2422 | del--; | ||||
2423 | } | ||||
2424 | if (!del) | ||||
2425 | break; | ||||
2426 | i++; | ||||
2427 | } | ||||
2428 | quicklistReleaseIterator(iter); | ||||
2429 | |||||
2430 | /* check result of lrem -2 foo */ | ||||
2431 | /* (we're ignoring the '2' part and still deleting all foo | ||||
2432 | * because | ||||
2433 | * we only have two foo) */ | ||||
2434 | iter = quicklistGetIterator(ql, AL_START_TAIL1); | ||||
2435 | i = 0; | ||||
2436 | size_t resB = sizeof(resultB) / sizeof(*resultB); | ||||
2437 | while (quicklistNext(iter, &entry)) { | ||||
2438 | /* Result must be: abc, foo, foobar, foobared, zap, test, | ||||
2439 | * foo */ | ||||
2440 | if (strncmp((char *)entry.value, resultB[resB - 1 - i], | ||||
2441 | entry.sz)) { | ||||
2442 | ERR("No match at position %d, got %.*s instead of %s", | ||||
2443 | i, entry.sz, entry.value, resultB[resB - 1 - i]); | ||||
2444 | ok = 0; | ||||
2445 | } | ||||
2446 | i++; | ||||
2447 | } | ||||
2448 | |||||
2449 | quicklistReleaseIterator(iter); | ||||
2450 | /* final result of all tests */ | ||||
2451 | if (ok) | ||||
2452 | OK; | ||||
2453 | quicklistRelease(ql); | ||||
2454 | } | ||||
2455 | } | ||||
2456 | |||||
2457 | for (int f = optimize_start; f < 16; f++) { | ||||
2458 | TEST_DESC("iterate reverse + delete at fill %d at compress %d", f, | ||||
2459 | options[_i]) { | ||||
2460 | quicklist *ql = quicklistNew(f, options[_i]); | ||||
2461 | quicklistPushTail(ql, "abc", 3); | ||||
2462 | quicklistPushTail(ql, "def", 3); | ||||
2463 | quicklistPushTail(ql, "hij", 3); | ||||
2464 | quicklistPushTail(ql, "jkl", 3); | ||||
2465 | quicklistPushTail(ql, "oop", 3); | ||||
2466 | |||||
2467 | quicklistEntry entry; | ||||
2468 | quicklistIter *iter = quicklistGetIterator(ql, AL_START_TAIL1); | ||||
2469 | int i = 0; | ||||
2470 | while (quicklistNext(iter, &entry)) { | ||||
2471 | if (quicklistCompare(entry.zi, (unsigned char *)"hij", 3)) { | ||||
2472 | quicklistDelEntry(iter, &entry); | ||||
2473 | } | ||||
2474 | i++; | ||||
2475 | } | ||||
2476 | quicklistReleaseIterator(iter); | ||||
2477 | |||||
2478 | if (i != 5) | ||||
2479 | ERR("Didn't iterate 5 times, iterated %d times.", i); | ||||
2480 | |||||
2481 | /* Check results after deletion of "hij" */ | ||||
2482 | iter = quicklistGetIterator(ql, AL_START_HEAD0); | ||||
2483 | i = 0; | ||||
2484 | char *vals[] = {"abc", "def", "jkl", "oop"}; | ||||
2485 | while (quicklistNext(iter, &entry)) { | ||||
2486 | if (!quicklistCompare(entry.zi, (unsigned char *)vals[i], | ||||
2487 | 3)) { | ||||
2488 | ERR("Value at %d didn't match %s\n", i, vals[i]); | ||||
2489 | } | ||||
2490 | i++; | ||||
2491 | } | ||||
2492 | quicklistReleaseIterator(iter); | ||||
2493 | quicklistRelease(ql); | ||||
2494 | } | ||||
2495 | } | ||||
2496 | |||||
2497 | for (int f = optimize_start; f < 800; f++) { | ||||
2498 | TEST_DESC("iterator at index test at fill %d at compress %d", f, | ||||
2499 | options[_i]) { | ||||
2500 | quicklist *ql = quicklistNew(f, options[_i]); | ||||
2501 | char num[32]; | ||||
2502 | long long nums[5000]; | ||||
2503 | for (int i = 0; i < 760; i++) { | ||||
2504 | nums[i] = -5157318210846258176 + i; | ||||
2505 | int sz = ll2string(num, sizeof(num), nums[i]); | ||||
2506 | quicklistPushTail(ql, num, sz); | ||||
2507 | } | ||||
2508 | |||||
2509 | quicklistEntry entry; | ||||
2510 | quicklistIter *iter = | ||||
2511 | quicklistGetIteratorAtIdx(ql, AL_START_HEAD0, 437); | ||||
2512 | int i = 437; | ||||
2513 | while (quicklistNext(iter, &entry)) { | ||||
2514 | if (entry.longval != nums[i]) | ||||
2515 | ERR("Expected %lld, but got %lld", entry.longval, | ||||
2516 | nums[i]); | ||||
2517 | i++; | ||||
2518 | } | ||||
2519 | quicklistReleaseIterator(iter); | ||||
2520 | quicklistRelease(ql); | ||||
2521 | } | ||||
2522 | } | ||||
2523 | |||||
2524 | for (int f = optimize_start; f < 40; f++) { | ||||
2525 | TEST_DESC("ltrim test A at fill %d at compress %d", f, | ||||
2526 | options[_i]) { | ||||
2527 | quicklist *ql = quicklistNew(f, options[_i]); | ||||
2528 | char num[32]; | ||||
2529 | long long nums[5000]; | ||||
2530 | for (int i = 0; i < 32; i++) { | ||||
2531 | nums[i] = -5157318210846258176 + i; | ||||
2532 | int sz = ll2string(num, sizeof(num), nums[i]); | ||||
2533 | quicklistPushTail(ql, num, sz); | ||||
2534 | } | ||||
2535 | if (f == 32) | ||||
2536 | ql_verify(ql, 1, 32, 32, 32); | ||||
2537 | /* ltrim 25 53 (keep [25,32] inclusive = 7 remaining) */ | ||||
2538 | quicklistDelRange(ql, 0, 25); | ||||
2539 | quicklistDelRange(ql, 0, 0); | ||||
2540 | quicklistEntry entry; | ||||
2541 | for (int i = 0; i < 7; i++) { | ||||
2542 | quicklistIndex(ql, i, &entry); | ||||
2543 | if (entry.longval != nums[25 + i]) | ||||
2544 | ERR("Deleted invalid range! Expected %lld but got " | ||||
2545 | "%lld", | ||||
2546 | entry.longval, nums[25 + i]); | ||||
2547 | } | ||||
2548 | if (f == 32) | ||||
2549 | ql_verify(ql, 1, 7, 7, 7); | ||||
2550 | quicklistRelease(ql); | ||||
2551 | } | ||||
2552 | } | ||||
2553 | |||||
2554 | for (int f = optimize_start; f < 40; f++) { | ||||
2555 | TEST_DESC("ltrim test B at fill %d at compress %d", f, | ||||
2556 | options[_i]) { | ||||
2557 | /* Force-disable compression because our 33 sequential | ||||
2558 | * integers don't compress and the check always fails. */ | ||||
2559 | quicklist *ql = quicklistNew(f, QUICKLIST_NOCOMPRESS0); | ||||
2560 | char num[32]; | ||||
2561 | long long nums[5000]; | ||||
2562 | for (int i = 0; i < 33; i++) { | ||||
2563 | nums[i] = i; | ||||
2564 | int sz = ll2string(num, sizeof(num), nums[i]); | ||||
2565 | quicklistPushTail(ql, num, sz); | ||||
2566 | } | ||||
2567 | if (f == 32) | ||||
2568 | ql_verify(ql, 2, 33, 32, 1); | ||||
2569 | /* ltrim 5 16 (keep [5,16] inclusive = 12 remaining) */ | ||||
2570 | quicklistDelRange(ql, 0, 5); | ||||
2571 | quicklistDelRange(ql, -16, 16); | ||||
2572 | if (f == 32) | ||||
2573 | ql_verify(ql, 1, 12, 12, 12); | ||||
2574 | quicklistEntry entry; | ||||
2575 | quicklistIndex(ql, 0, &entry); | ||||
2576 | if (entry.longval != 5) | ||||
2577 | ERR("A: longval not 5, but %lld", entry.longval); | ||||
2578 | else | ||||
2579 | OK; | ||||
2580 | quicklistIndex(ql, -1, &entry); | ||||
2581 | if (entry.longval != 16) | ||||
2582 | ERR("B! got instead: %lld", entry.longval); | ||||
2583 | else | ||||
2584 | OK; | ||||
2585 | quicklistPushTail(ql, "bobobob", 7); | ||||
2586 | quicklistIndex(ql, -1, &entry); | ||||
2587 | if (strncmp((char *)entry.value, "bobobob", 7)) | ||||
2588 | ERR("Tail doesn't match bobobob, it's %.*s instead", | ||||
2589 | entry.sz, entry.value); | ||||
2590 | for (int i = 0; i < 12; i++) { | ||||
2591 | quicklistIndex(ql, i, &entry); | ||||
2592 | if (entry.longval != nums[5 + i]) | ||||
2593 | ERR("Deleted invalid range! Expected %lld but got " | ||||
2594 | "%lld", | ||||
2595 | entry.longval, nums[5 + i]); | ||||
2596 | } | ||||
2597 | quicklistRelease(ql); | ||||
2598 | } | ||||
2599 | } | ||||
2600 | |||||
2601 | for (int f = optimize_start; f < 40; f++) { | ||||
2602 | TEST_DESC("ltrim test C at fill %d at compress %d", f, | ||||
2603 | options[_i]) { | ||||
2604 | quicklist *ql = quicklistNew(f, options[_i]); | ||||
2605 | char num[32]; | ||||
2606 | long long nums[5000]; | ||||
2607 | for (int i = 0; i < 33; i++) { | ||||
2608 | nums[i] = -5157318210846258176 + i; | ||||
2609 | int sz = ll2string(num, sizeof(num), nums[i]); | ||||
2610 | quicklistPushTail(ql, num, sz); | ||||
2611 | } | ||||
2612 | if (f == 32) | ||||
2613 | ql_verify(ql, 2, 33, 32, 1); | ||||
2614 | /* ltrim 3 3 (keep [3,3] inclusive = 1 remaining) */ | ||||
2615 | quicklistDelRange(ql, 0, 3); | ||||
2616 | quicklistDelRange(ql, -29, | ||||
2617 | 4000); /* make sure not loop forever */ | ||||
2618 | if (f == 32) | ||||
2619 | ql_verify(ql, 1, 1, 1, 1); | ||||
2620 | quicklistEntry entry; | ||||
2621 | quicklistIndex(ql, 0, &entry); | ||||
2622 | if (entry.longval != -5157318210846258173) | ||||
2623 | ERROR; | ||||
2624 | else | ||||
2625 | OK; | ||||
2626 | quicklistRelease(ql); | ||||
2627 | } | ||||
2628 | } | ||||
2629 | |||||
2630 | for (int f = optimize_start; f < 40; f++) { | ||||
2631 | TEST_DESC("ltrim test D at fill %d at compress %d", f, | ||||
2632 | options[_i]) { | ||||
2633 | quicklist *ql = quicklistNew(f, options[_i]); | ||||
2634 | char num[32]; | ||||
2635 | long long nums[5000]; | ||||
2636 | for (int i = 0; i < 33; i++) { | ||||
2637 | nums[i] = -5157318210846258176 + i; | ||||
2638 | int sz = ll2string(num, sizeof(num), nums[i]); | ||||
2639 | quicklistPushTail(ql, num, sz); | ||||
2640 | } | ||||
2641 | if (f == 32) | ||||
2642 | ql_verify(ql, 2, 33, 32, 1); | ||||
2643 | quicklistDelRange(ql, -12, 3); | ||||
2644 | if (ql->count != 30) | ||||
2645 | ERR("Didn't delete exactly three elements! Count is: %lu", | ||||
2646 | ql->count); | ||||
2647 | quicklistRelease(ql); | ||||
2648 | } | ||||
2649 | } | ||||
2650 | |||||
2651 | for (int f = optimize_start; f < 72; f++) { | ||||
2652 | TEST_DESC("create quicklist from ziplist at fill %d at compress %d", | ||||
2653 | f, options[_i]) { | ||||
2654 | unsigned char *zl = ziplistNew(); | ||||
2655 | long long nums[64]; | ||||
2656 | char num[64]; | ||||
2657 | for (int i = 0; i < 33; i++) { | ||||
2658 | nums[i] = -5157318210846258176 + i; | ||||
2659 | int sz = ll2string(num, sizeof(num), nums[i]); | ||||
2660 | zl = | ||||
2661 | ziplistPush(zl, (unsigned char *)num, sz, ZIPLIST_TAIL1); | ||||
2662 | } | ||||
2663 | for (int i = 0; i < 33; i++) { | ||||
2664 | zl = ziplistPush(zl, (unsigned char *)genstr("hello", i), | ||||
2665 | 32, ZIPLIST_TAIL1); | ||||
2666 | } | ||||
2667 | quicklist *ql = quicklistCreateFromZiplist(f, options[_i], zl); | ||||
2668 | if (f == 1) | ||||
2669 | ql_verify(ql, 66, 66, 1, 1); | ||||
2670 | else if (f == 32) | ||||
2671 | ql_verify(ql, 3, 66, 32, 2); | ||||
2672 | else if (f == 66) | ||||
2673 | ql_verify(ql, 1, 66, 66, 66); | ||||
2674 | quicklistRelease(ql); | ||||
2675 | } | ||||
2676 | } | ||||
2677 | |||||
2678 | long long stop = mstime(); | ||||
2679 | runtime[_i] = stop - start; | ||||
2680 | } | ||||
2681 | |||||
2682 | /* Run a longer test of compression depth outside of primary test loop. */ | ||||
2683 | int list_sizes[] = {250, 251, 500, 999, 1000}; | ||||
2684 | long long start = mstime(); | ||||
2685 | for (int list = 0; list < (int)(sizeof(list_sizes) / sizeof(*list_sizes)); | ||||
2686 | list++) { | ||||
2687 | for (int f = optimize_start; f < 128; f++) { | ||||
2688 | for (int depth = 1; depth < 40; depth++) { | ||||
2689 | /* skip over many redundant test cases */ | ||||
2690 | TEST_DESC("verify specific compression of interior nodes with " | ||||
2691 | "%d list " | ||||
2692 | "at fill %d at compress %d", | ||||
2693 | list_sizes[list], f, depth) { | ||||
2694 | quicklist *ql = quicklistNew(f, depth); | ||||
2695 | for (int i = 0; i < list_sizes[list]; i++) { | ||||
2696 | quicklistPushTail(ql, genstr("hello TAIL", i + 1), 64); | ||||
2697 | quicklistPushHead(ql, genstr("hello HEAD", i + 1), 64); | ||||
2698 | } | ||||
2699 | |||||
2700 | quicklistNode *node = ql->head; | ||||
2701 | unsigned int low_raw = ql->compress; | ||||
2702 | unsigned int high_raw = ql->len - ql->compress; | ||||
2703 | |||||
2704 | for (unsigned int at = 0; at < ql->len; | ||||
2705 | at++, node = node->next) { | ||||
2706 | if (at < low_raw || at >= high_raw) { | ||||
2707 | if (node->encoding != QUICKLIST_NODE_ENCODING_RAW1) { | ||||
2708 | ERR("Incorrect compression: node %d is " | ||||
2709 | "compressed at depth %d ((%u, %u); total " | ||||
2710 | "nodes: %lu; size: %u)", | ||||
2711 | at, depth, low_raw, high_raw, ql->len, | ||||
2712 | node->sz); | ||||
2713 | } | ||||
2714 | } else { | ||||
2715 | if (node->encoding != QUICKLIST_NODE_ENCODING_LZF2) { | ||||
2716 | ERR("Incorrect non-compression: node %d is NOT " | ||||
2717 | "compressed at depth %d ((%u, %u); total " | ||||
2718 | "nodes: %lu; size: %u; attempted: %d)", | ||||
2719 | at, depth, low_raw, high_raw, ql->len, | ||||
2720 | node->sz, node->attempted_compress); | ||||
2721 | } | ||||
2722 | } | ||||
2723 | } | ||||
2724 | quicklistRelease(ql); | ||||
2725 | } | ||||
2726 | } | ||||
2727 | } | ||||
2728 | } | ||||
2729 | long long stop = mstime(); | ||||
2730 | |||||
2731 | printf("\n"); | ||||
2732 | for (size_t i = 0; i < option_count; i++) | ||||
2733 | printf("Test Loop %02d: %0.2f seconds.\n", options[i], | ||||
2734 | (float)runtime[i] / 1000); | ||||
2735 | printf("Compressions: %0.2f seconds.\n", (float)(stop - start) / 1000); | ||||
2736 | printf("\n"); | ||||
2737 | |||||
2738 | TEST("bookmark get updated to next item") { | ||||
2739 | quicklist *ql = quicklistNew(1, 0); | ||||
2740 | quicklistPushTail(ql, "1", 1); | ||||
2741 | quicklistPushTail(ql, "2", 1); | ||||
2742 | quicklistPushTail(ql, "3", 1); | ||||
2743 | quicklistPushTail(ql, "4", 1); | ||||
2744 | quicklistPushTail(ql, "5", 1); | ||||
2745 | assert(ql->len==5)(__builtin_expect(!!((ql->len==5)), 1)?(void)0 : (_serverAssert ("ql->len==5","quicklist.c",2745),__builtin_unreachable()) ); | ||||
2746 | /* add two bookmarks, one pointing to the node before the last. */ | ||||
2747 | assert(quicklistBookmarkCreate(&ql, "_dummy", ql->head->next))(__builtin_expect(!!((quicklistBookmarkCreate(&ql, "_dummy" , ql->head->next))), 1)?(void)0 : (_serverAssert("quicklistBookmarkCreate(&ql, \"_dummy\", ql->head->next)" ,"quicklist.c",2747),__builtin_unreachable())); | ||||
2748 | assert(quicklistBookmarkCreate(&ql, "_test", ql->tail->prev))(__builtin_expect(!!((quicklistBookmarkCreate(&ql, "_test" , ql->tail->prev))), 1)?(void)0 : (_serverAssert("quicklistBookmarkCreate(&ql, \"_test\", ql->tail->prev)" ,"quicklist.c",2748),__builtin_unreachable())); | ||||
2749 | /* test that the bookmark returns the right node, delete it and see that the bookmark points to the last node */ | ||||
2750 | assert(quicklistBookmarkFind(ql, "_test") == ql->tail->prev)(__builtin_expect(!!((quicklistBookmarkFind(ql, "_test") == ql ->tail->prev)), 1)?(void)0 : (_serverAssert("quicklistBookmarkFind(ql, \"_test\") == ql->tail->prev" ,"quicklist.c",2750),__builtin_unreachable())); | ||||
2751 | assert(quicklistDelRange(ql, -2, 1))(__builtin_expect(!!((quicklistDelRange(ql, -2, 1))), 1)?(void )0 : (_serverAssert("quicklistDelRange(ql, -2, 1)","quicklist.c" ,2751),__builtin_unreachable())); | ||||
2752 | assert(quicklistBookmarkFind(ql, "_test") == ql->tail)(__builtin_expect(!!((quicklistBookmarkFind(ql, "_test") == ql ->tail)), 1)?(void)0 : (_serverAssert("quicklistBookmarkFind(ql, \"_test\") == ql->tail" ,"quicklist.c",2752),__builtin_unreachable())); | ||||
2753 | /* delete the last node, and see that the bookmark was deleted. */ | ||||
2754 | assert(quicklistDelRange(ql, -1, 1))(__builtin_expect(!!((quicklistDelRange(ql, -1, 1))), 1)?(void )0 : (_serverAssert("quicklistDelRange(ql, -1, 1)","quicklist.c" ,2754),__builtin_unreachable())); | ||||
2755 | assert(quicklistBookmarkFind(ql, "_test") == NULL)(__builtin_expect(!!((quicklistBookmarkFind(ql, "_test") == ( (void*)0))), 1)?(void)0 : (_serverAssert("quicklistBookmarkFind(ql, \"_test\") == NULL" ,"quicklist.c",2755),__builtin_unreachable())); | ||||
2756 | /* test that other bookmarks aren't affected */ | ||||
2757 | assert(quicklistBookmarkFind(ql, "_dummy") == ql->head->next)(__builtin_expect(!!((quicklistBookmarkFind(ql, "_dummy") == ql ->head->next)), 1)?(void)0 : (_serverAssert("quicklistBookmarkFind(ql, \"_dummy\") == ql->head->next" ,"quicklist.c",2757),__builtin_unreachable())); | ||||
2758 | assert(quicklistBookmarkFind(ql, "_missing") == NULL)(__builtin_expect(!!((quicklistBookmarkFind(ql, "_missing") == ((void*)0))), 1)?(void)0 : (_serverAssert("quicklistBookmarkFind(ql, \"_missing\") == NULL" ,"quicklist.c",2758),__builtin_unreachable())); | ||||
2759 | assert(ql->len==3)(__builtin_expect(!!((ql->len==3)), 1)?(void)0 : (_serverAssert ("ql->len==3","quicklist.c",2759),__builtin_unreachable()) ); | ||||
2760 | quicklistBookmarksClear(ql); /* for coverage */ | ||||
2761 | assert(quicklistBookmarkFind(ql, "_dummy") == NULL)(__builtin_expect(!!((quicklistBookmarkFind(ql, "_dummy") == ( (void*)0))), 1)?(void)0 : (_serverAssert("quicklistBookmarkFind(ql, \"_dummy\") == NULL" ,"quicklist.c",2761),__builtin_unreachable())); | ||||
2762 | quicklistRelease(ql); | ||||
2763 | } | ||||
2764 | |||||
2765 | TEST("bookmark limit") { | ||||
2766 | int i; | ||||
2767 | quicklist *ql = quicklistNew(1, 0); | ||||
2768 | quicklistPushHead(ql, "1", 1); | ||||
2769 | for (i=0; i<QL_MAX_BM((1 << 4)-1); i++) | ||||
2770 | assert(quicklistBookmarkCreate(&ql, genstr("",i), ql->head))(__builtin_expect(!!((quicklistBookmarkCreate(&ql, genstr ("",i), ql->head))), 1)?(void)0 : (_serverAssert("quicklistBookmarkCreate(&ql, genstr(\"\",i), ql->head)" ,"quicklist.c",2770),__builtin_unreachable())); | ||||
2771 | /* when all bookmarks are used, creation fails */ | ||||
2772 | assert(!quicklistBookmarkCreate(&ql, "_test", ql->head))(__builtin_expect(!!((!quicklistBookmarkCreate(&ql, "_test" , ql->head))), 1)?(void)0 : (_serverAssert("!quicklistBookmarkCreate(&ql, \"_test\", ql->head)" ,"quicklist.c",2772),__builtin_unreachable())); | ||||
2773 | /* delete one and see that we can now create another */ | ||||
2774 | assert(quicklistBookmarkDelete(ql, "0"))(__builtin_expect(!!((quicklistBookmarkDelete(ql, "0"))), 1)? (void)0 : (_serverAssert("quicklistBookmarkDelete(ql, \"0\")" ,"quicklist.c",2774),__builtin_unreachable())); | ||||
2775 | assert(quicklistBookmarkCreate(&ql, "_test", ql->head))(__builtin_expect(!!((quicklistBookmarkCreate(&ql, "_test" , ql->head))), 1)?(void)0 : (_serverAssert("quicklistBookmarkCreate(&ql, \"_test\", ql->head)" ,"quicklist.c",2775),__builtin_unreachable())); | ||||
2776 | /* delete one and see that the rest survive */ | ||||
2777 | assert(quicklistBookmarkDelete(ql, "_test"))(__builtin_expect(!!((quicklistBookmarkDelete(ql, "_test"))), 1)?(void)0 : (_serverAssert("quicklistBookmarkDelete(ql, \"_test\")" ,"quicklist.c",2777),__builtin_unreachable())); | ||||
2778 | for (i=1; i<QL_MAX_BM((1 << 4)-1); i++) | ||||
2779 | assert(quicklistBookmarkFind(ql, genstr("",i)) == ql->head)(__builtin_expect(!!((quicklistBookmarkFind(ql, genstr("",i)) == ql->head)), 1)?(void)0 : (_serverAssert("quicklistBookmarkFind(ql, genstr(\"\",i)) == ql->head" ,"quicklist.c",2779),__builtin_unreachable())); | ||||
2780 | /* make sure the deleted ones are indeed gone */ | ||||
2781 | assert(!quicklistBookmarkFind(ql, "0"))(__builtin_expect(!!((!quicklistBookmarkFind(ql, "0"))), 1)?( void)0 : (_serverAssert("!quicklistBookmarkFind(ql, \"0\")","quicklist.c" ,2781),__builtin_unreachable())); | ||||
2782 | assert(!quicklistBookmarkFind(ql, "_test"))(__builtin_expect(!!((!quicklistBookmarkFind(ql, "_test"))), 1 )?(void)0 : (_serverAssert("!quicklistBookmarkFind(ql, \"_test\")" ,"quicklist.c",2782),__builtin_unreachable())); | ||||
2783 | quicklistRelease(ql); | ||||
2784 | } | ||||
2785 | |||||
2786 | if (!err) | ||||
2787 | printf("ALL TESTS PASSED!\n"); | ||||
2788 | else | ||||
2789 | ERR("Sorry, not all tests passed! In fact, %d tests failed.", err); | ||||
2790 | |||||
2791 | return err; | ||||
2792 | } | ||||
2793 | #endif |