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