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