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