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