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