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