From abdd1414a896c407c23a8f4165cfd6f027cf2b60 Mon Sep 17 00:00:00 2001 From: Matt Stancliff Date: Wed, 10 Dec 2014 21:26:31 -0500 Subject: Allow compression of interior quicklist nodes Let user set how many nodes to *not* compress. We can specify a compression "depth" of how many nodes to leave uncompressed on each end of the quicklist. Depth 0 = disable compression. Depth 1 = only leave head/tail uncompressed. - (read as: "skip 1 node on each end of the list before compressing") Depth 2 = leave head, head->next, tail->prev, tail uncompressed. - ("skip 2 nodes on each end of the list before compressing") Depth 3 = Depth 2 + head->next->next + tail->prev->prev - ("skip 3 nodes...") etc. This also: - updates RDB storage to use native quicklist compression (if node is already compressed) instead of uncompressing, generating the RDB string, then re-compressing the quicklist node. - internalizes the "fill" parameter for the quicklist so we don't need to pass it to _every_ function. Now it's just a property of the list. - allows a runtime-configurable compression option, so we can expose a compresion parameter in the configuration file if people want to trade slight request-per-second performance for up to 90%+ memory savings in some situations. - updates the quicklist tests to do multiple passes: 200k+ tests now. --- src/quicklist.c | 2130 +++++++++++++++++++++++++++++++++---------------------- 1 file changed, 1278 insertions(+), 852 deletions(-) (limited to 'src/quicklist.c') diff --git a/src/quicklist.c b/src/quicklist.c index 27ec4e02e..92ce50649 100644 --- a/src/quicklist.c +++ b/src/quicklist.c @@ -33,6 +33,7 @@ #include "zmalloc.h" #include "ziplist.h" #include "util.h" /* for ll2string */ +#include "lzf.h" #if defined(REDIS_TEST) || defined(REDIS_TEST_VERBOSE) #include /* for printf (debug printing), snprintf (genstr) */ @@ -41,8 +42,18 @@ /* Optimization levels for size-based filling */ static const size_t optimization_level[] = { 4096, 8192, 16384, 32768, 65536 }; +/* Maximum size in bytes of any multi-element ziplist. + * Larger values will live in their own isolated ziplists. */ #define SIZE_SAFETY_LIMIT 8192 +/* Minimum ziplist size in bytes for attempting compression. */ +#define MIN_COMPRESS_BYTES 48 + +/* Minimum size reduction in bytes to store compressed quicklistNode data. + * This also prevents us from storing compression if the compression + * resulted in a larger size than the original data. */ +#define MIN_COMPRESS_IMPROVE 8 + /* If not verbose testing, remove all debug printing. */ #ifndef REDIS_TEST_VERBOSE #define D(...) @@ -75,6 +86,40 @@ quicklist *quicklistCreate(void) { quicklist->head = quicklist->tail = NULL; quicklist->len = 0; quicklist->count = 0; + quicklist->compress = 0; + quicklist->fill = -2; + return quicklist; +} + +#define COMPRESS_MAX (1 << 16) +void quicklistSetCompressDepth(quicklist *quicklist, int compress) { + if (compress > COMPRESS_MAX) { + compress = COMPRESS_MAX; + } else if (compress < 0) { + compress = 0; + } + quicklist->compress = compress; +} + +#define FILL_MAX (1 << 15) +void quicklistSetFill(quicklist *quicklist, int fill) { + if (fill > FILL_MAX) { + fill = FILL_MAX; + } else if (fill < -5) { + fill = -5; + } + quicklist->fill = fill; +} + +void quicklistSetOptions(quicklist *quicklist, int fill, int depth) { + quicklistSetFill(quicklist, fill); + quicklistSetCompressDepth(quicklist, depth); +} + +/* Create a new quicklist with some default parameters. */ +quicklist *quicklistNew(int fill, int compress) { + quicklist *quicklist = quicklistCreate(); + quicklistSetOptions(quicklist, fill, compress); return quicklist; } @@ -85,6 +130,9 @@ static quicklistNode *quicklistCreateNode(void) { node->count = 0; node->sz = 0; node->next = node->prev = NULL; + node->encoding = QUICKLIST_NODE_ENCODING_RAW; + node->container = QUICKLIST_NODE_CONTAINER_ZIPLIST; + node->recompress = 0; return node; } @@ -112,8 +160,183 @@ void quicklistRelease(quicklist *quicklist) { zfree(quicklist); } +/* Compress the ziplist in 'node' and update encoding details. + * Returns 1 if ziplist compressed successfully. + * Returns 0 if compression failed or if ziplist too small to compress. */ +static int __quicklistCompressNode(quicklistNode *node) { +#ifdef REDIS_TEST + node->attempted_compress = 1; +#endif + + /* Don't bother compressing small values */ + if (node->sz < MIN_COMPRESS_BYTES) + return 0; + + quicklistLZF *lzf = zmalloc(sizeof(*lzf) + node->sz); + + /* Cancel if compression fails or doesn't compress small enough */ + if (((lzf->sz = lzf_compress(node->zl, node->sz, lzf->compressed, + node->sz)) == 0) || + lzf->sz + MIN_COMPRESS_IMPROVE >= node->sz) { + /* lzf_compress aborts/rejects compression if value not compressable. */ + zfree(lzf); + return 0; + } + lzf = zrealloc(lzf, sizeof(*lzf) + lzf->sz); + zfree(node->zl); + node->zl = (unsigned char *)lzf; + node->encoding = QUICKLIST_NODE_ENCODING_LZF; + node->recompress = 0; + return 1; +} + +/* Compress only uncompressed nodes. */ +#define quicklistCompressNode(_node) \ + do { \ + if ((_node) && (_node)->encoding == QUICKLIST_NODE_ENCODING_RAW) { \ + __quicklistCompressNode((_node)); \ + } \ + } while (0) + +/* Uncompress the ziplist in 'node' and update encoding details. + * Returns 1 on successful decode, 0 on failure to decode. */ +static int __quicklistDecompressNode(quicklistNode *node) { +#ifdef REDIS_TEST + node->attempted_compress = 0; +#endif + + void *decompressed = zmalloc(node->sz); + quicklistLZF *lzf = (quicklistLZF *)node->zl; + if (lzf_decompress(lzf->compressed, lzf->sz, decompressed, node->sz) == 0) { + /* Someone requested decompress, but we can't decompress. Not good. */ + zfree(decompressed); + return 0; + } + zfree(lzf); + node->zl = decompressed; + node->encoding = QUICKLIST_NODE_ENCODING_RAW; + return 1; +} + +/* Decompress only compressed nodes. */ +#define quicklistDecompressNode(_node) \ + do { \ + if ((_node) && (_node)->encoding == QUICKLIST_NODE_ENCODING_LZF) { \ + __quicklistDecompressNode((_node)); \ + } \ + } while (0) + +/* Force node to not be immediately re-compresable */ +#define quicklistDecompressNodeForUse(_node) \ + do { \ + if ((_node) && (_node)->encoding == QUICKLIST_NODE_ENCODING_LZF) { \ + __quicklistDecompressNode((_node)); \ + (_node)->recompress = 1; \ + } \ + } while (0) + +/* Extract the raw LZF data from this quicklistNode. + * Pointer to LZF data is assigned to '*data'. + * Return value is the length of compressed LZF data. */ +size_t quicklistGetLzf(const quicklistNode *node, void **data) { + quicklistLZF *lzf = (quicklistLZF *)node->zl; + *data = lzf->compressed; + return lzf->sz; +} + +#define quicklistAllowsCompression(_ql) ((_ql)->compress != 0) + +/* Force 'quicklist' to meet compression guidelines set by compress depth. + * The only way to guarantee interior nodes get compressed is to iterate + * to our "interior" compress depth then compress the next node we find. + * If compress depth is larger than the entire list, we return immediately. */ +static void __quicklistCompress(const quicklist *quicklist, + quicklistNode *node) { + /* If length is less than our compress depth (from both sides), + * we can't compress anything. */ + if (!quicklistAllowsCompression(quicklist) || + quicklist->len < (unsigned int)(quicklist->compress * 2)) + return; + +#if 0 + /* Optimized cases for small depth counts */ + if (quicklist->compress == 1) { + quicklistNode *h = quicklist->head, *t = quicklist->tail; + quicklistDecompressNode(h); + quicklistDecompressNode(t); + if (h != node && t != node) + quicklistCompressNode(node); + return; + } else if (quicklist->compress == 2) { + quicklistNode *h = quicklist->head, *hn = h->next, *hnn = hn->next; + quicklistNode *t = quicklist->tail, *tp = t->prev, *tpp = tp->prev; + quicklistDecompressNode(h); + quicklistDecompressNode(hn); + quicklistDecompressNode(t); + quicklistDecompressNode(tp); + if (h != node && hn != node && t != node && tp != node) { + quicklistCompressNode(node); + } + if (hnn != t) { + quicklistCompressNode(hnn); + } + if (tpp != h) { + quicklistCompressNode(tpp); + } + return; + } +#endif + + /* Iterate until we reach compress depth for both sides of the list.a + * Note: because we do length checks at the *top* of this function, + * we can skip explicit null checks below. Everything exists. */ + quicklistNode *forward = quicklist->head; + quicklistNode *reverse = quicklist->tail; + int depth = 0; + int in_depth = 0; + while (depth++ < quicklist->compress) { + quicklistDecompressNode(forward); + quicklistDecompressNode(reverse); + + if (forward == node || reverse == node) + in_depth = 1; + + if (forward == reverse) + return; + + forward = forward->next; + reverse = reverse->prev; + } + + if (!in_depth) + quicklistCompressNode(node); + + if (depth > 2) { + /* At this point, forward and reverse are one node beyond depth */ + quicklistCompressNode(forward); + quicklistCompressNode(reverse); + } +} + +#define quicklistCompress(_ql, _node) \ + do { \ + if ((_node)->recompress) \ + quicklistCompressNode((_node)); \ + else \ + __quicklistCompress((_ql), (_node)); \ + } while (0) + +/* If we previously used quicklistDecompressNodeForUse(), just recompress. */ +#define quicklistRecompressOnly(_ql, _node) \ + do { \ + if ((_node)->recompress) \ + quicklistCompressNode((_node)); \ + } while (0) + /* Insert 'new_node' after 'old_node' if 'after' is 1. - * Insert 'new_node' before 'old_node' if 'after' is 0. */ + * Insert 'new_node' before 'old_node' if 'after' is 0. + * Note: 'new_node' is *always* uncompressed, so if we assign it to + * head or tail, we do not need to uncompress it. */ static void __quicklistInsertNode(quicklist *quicklist, quicklistNode *old_node, quicklistNode *new_node, int after) { if (after) { @@ -137,11 +360,14 @@ static void __quicklistInsertNode(quicklist *quicklist, quicklistNode *old_node, if (quicklist->head == old_node) quicklist->head = new_node; } - /* If this insert creates the first element in this quicklist, we - * need to initialize head/tail too. */ + /* If this insert creates the only element so far, initialize head/tail. */ if (quicklist->len == 0) { quicklist->head = quicklist->tail = new_node; } + + if (old_node) + quicklistCompress(quicklist, old_node); + quicklist->len++; } @@ -232,44 +458,48 @@ static int _quicklistNodeAllowMerge(const quicklistNode *a, (node)->sz = ziplistBlobLen((node)->zl); \ } while (0) -/* Add new entry to head of quicklist. +/* Add new entry to head node of quicklist. * - * Returns 'quicklist' argument. */ -quicklist *quicklistPushHead(quicklist *quicklist, const int fill, void *value, - size_t sz) { - if (_quicklistNodeAllowInsert(quicklist->head, fill, sz)) { + * Returns 0 if used existing head. + * Returns 1 if new head created. */ +int quicklistPushHead(quicklist *quicklist, void *value, size_t sz) { + quicklistNode *orig_head = quicklist->head; + if (_quicklistNodeAllowInsert(quicklist->head, quicklist->fill, sz)) { quicklist->head->zl = ziplistPush(quicklist->head->zl, value, sz, ZIPLIST_HEAD); + quicklistNodeUpdateSz(quicklist->head); } else { quicklistNode *node = quicklistCreateNode(); node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_HEAD); + quicklistNodeUpdateSz(node); _quicklistInsertNodeBefore(quicklist, quicklist->head, node); } quicklist->count++; quicklist->head->count++; - quicklistNodeUpdateSz(quicklist->head); - return quicklist; + return (orig_head != quicklist->head); } -/* Add new node to tail of quicklist. +/* Add new entry to tail node of quicklist. * - * Returns 'quicklist' argument. */ -quicklist *quicklistPushTail(quicklist *quicklist, const int fill, void *value, - size_t sz) { - if (_quicklistNodeAllowInsert(quicklist->tail, fill, sz)) { + * Returns 0 if used existing tail. + * Returns 1 if new tail created. */ +int quicklistPushTail(quicklist *quicklist, void *value, size_t sz) { + quicklistNode *orig_tail = quicklist->tail; + if (_quicklistNodeAllowInsert(quicklist->tail, quicklist->fill, sz)) { quicklist->tail->zl = ziplistPush(quicklist->tail->zl, value, sz, ZIPLIST_TAIL); + quicklistNodeUpdateSz(quicklist->tail); } else { quicklistNode *node = quicklistCreateNode(); node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_TAIL); + quicklistNodeUpdateSz(node); _quicklistInsertNodeAfter(quicklist, quicklist->tail, node); } quicklist->count++; quicklist->tail->count++; - quicklistNodeUpdateSz(quicklist->tail); - return quicklist; + return (orig_tail != quicklist->tail); } /* Create new node consisting of a pre-formed ziplist. @@ -293,7 +523,7 @@ void quicklistAppendZiplist(quicklist *quicklist, unsigned char *zl) { * * Returns 'quicklist' argument. Frees passed-in ziplist 'zl' */ quicklist *quicklistAppendValuesFromZiplist(quicklist *quicklist, - const int fill, unsigned char *zl) { + unsigned char *zl) { unsigned char *value; unsigned int sz; long long longval; @@ -306,7 +536,7 @@ quicklist *quicklistAppendValuesFromZiplist(quicklist *quicklist, sz = ll2string(longstr, sizeof(longstr), longval); value = (unsigned char *)longstr; } - quicklistPushTail(quicklist, fill, value, sz); + quicklistPushTail(quicklist, value, sz); p = ziplistNext(zl, p); } zfree(zl); @@ -316,14 +546,16 @@ quicklist *quicklistAppendValuesFromZiplist(quicklist *quicklist, /* Create new (potentially multi-node) quicklist from a single existing ziplist. * * Returns new quicklist. Frees passed-in ziplist 'zl'. */ -quicklist *quicklistCreateFromZiplist(int fill, unsigned char *zl) { - return quicklistAppendValuesFromZiplist(quicklistCreate(), fill, zl); +quicklist *quicklistCreateFromZiplist(int fill, int compress, + unsigned char *zl) { + return quicklistAppendValuesFromZiplist(quicklistNew(fill, compress), zl); } #define quicklistDeleteIfEmpty(ql, n) \ do { \ if ((n)->count == 0) { \ __quicklistDelNode((ql), (n)); \ + (n) = NULL; \ } \ } while (0) @@ -333,11 +565,17 @@ static void __quicklistDelNode(quicklist *quicklist, quicklistNode *node) { if (node->prev) node->prev->next = node->next; - if (node == quicklist->tail) + if (node == quicklist->tail) { quicklist->tail = node->prev; + } - if (node == quicklist->head) + if (node == quicklist->head) { quicklist->head = node->next; + } + + /* If we deleted a node within our compress depth, we + * now have compressed nodes needing to be decompressed. */ + __quicklistCompress(quicklist, NULL); quicklist->count -= node->count; @@ -349,21 +587,25 @@ static void __quicklistDelNode(quicklist *quicklist, quicklistNode *node) { /* Delete one entry from list given the node for the entry and a pointer * to the entry in the node. * + * Note: quicklistDelIndex() *requires* uncompressed nodes because you + * already had to get *p from an uncompressed node somewhere. + * * Returns 1 if the entire node was deleted, 0 if node still exists. * Also updates in/out param 'p' with the next offset in the ziplist. */ static int quicklistDelIndex(quicklist *quicklist, quicklistNode *node, unsigned char **p) { int gone = 0; + node->zl = ziplistDelete(node->zl, p); node->count--; if (node->count == 0) { gone = 1; + __quicklistDelNode(quicklist, node); } else { quicklistNodeUpdateSz(node); } quicklist->count--; - quicklistDeleteIfEmpty(quicklist, node); - /* If we deleted all the nodes, our returned pointer is no longer valid */ + /* If we deleted the node, the original node is no longer valid */ return gone ? 1 : 0; } @@ -408,8 +650,10 @@ int quicklistReplaceAtIndex(quicklist *quicklist, long index, void *data, int sz) { quicklistEntry entry; if (quicklistIndex(quicklist, index, &entry)) { + // quicklistDecompressNode(entry.node); entry.node->zl = ziplistDelete(entry.node->zl, &entry.zi); entry.node->zl = ziplistInsert(entry.node->zl, entry.zi, data, sz); + quicklistCompress(quicklist, entry.node); return 1; } else { return 0; @@ -434,6 +678,8 @@ static quicklistNode *_quicklistZiplistMerge(quicklist *quicklist, quicklistNode *b) { D("Requested merge (a,b) (%u, %u)", a->count, b->count); + quicklistDecompressNode(a); + quicklistDecompressNode(b); if ((ziplistMerge(&a->zl, &b->zl))) { /* We merged ziplists! Now remove the unused quicklistNode. */ quicklistNode *keep = NULL, *nokeep = NULL; @@ -449,7 +695,7 @@ static quicklistNode *_quicklistZiplistMerge(quicklist *quicklist, nokeep->count = 0; __quicklistDelNode(quicklist, nokeep); - + quicklistCompress(quicklist, keep); return keep; } else { /* else, the merge returned NULL and nothing changed. */ @@ -465,8 +711,8 @@ static quicklistNode *_quicklistZiplistMerge(quicklist *quicklist, * - (center->prev, center) * - (center, center->next) */ -static void _quicklistMergeNodes(quicklist *quicklist, const int fill, - quicklistNode *center) { +static void _quicklistMergeNodes(quicklist *quicklist, quicklistNode *center) { + int fill = quicklist->fill; quicklistNode *prev, *prev_prev, *next, *next_next, *target; prev = prev_prev = next = next_next = target = NULL; @@ -530,7 +776,7 @@ static void _quicklistMergeNodes(quicklist *quicklist, const int fill, * Returns newly created node or NULL if split not possible. */ static quicklistNode *_quicklistSplitNode(quicklistNode *node, int offset, int after) { - size_t zl_sz = ziplistBlobLen(node->zl); + size_t zl_sz = node->sz; quicklistNode *new_node = quicklistCreateNode(); new_node->zl = zmalloc(zl_sz); @@ -563,10 +809,10 @@ static quicklistNode *_quicklistSplitNode(quicklistNode *node, int offset, * * If after==1, the new value is inserted after 'entry', otherwise * the new value is inserted before 'entry'. */ -static void _quicklistInsert(quicklist *quicklist, const int fill, - quicklistEntry *entry, void *value, - const size_t sz, int after) { +static void _quicklistInsert(quicklist *quicklist, quicklistEntry *entry, + void *value, const size_t sz, int after) { int full = 0, at_tail = 0, at_head = 0, full_next = 0, full_prev = 0; + int fill = quicklist->fill; quicklistNode *node = entry->node; quicklistNode *new_node = NULL; @@ -588,7 +834,7 @@ static void _quicklistInsert(quicklist *quicklist, const int fill, full = 1; } - if (after && (ziplistNext(node->zl, entry->zi) == NULL)) { + if (after && (entry->offset == node->count)) { D("At Tail of current ziplist"); at_tail = 1; if (!_quicklistNodeAllowInsert(node->next, fill, sz)) { @@ -597,7 +843,7 @@ static void _quicklistInsert(quicklist *quicklist, const int fill, } } - if (!after && (ziplistPrev(node->zl, entry->zi) == NULL)) { + if (!after && (entry->offset == 0)) { D("At Head"); at_head = 1; if (!_quicklistNodeAllowInsert(node->prev, fill, sz)) { @@ -609,6 +855,7 @@ static void _quicklistInsert(quicklist *quicklist, const int fill, /* Now determine where and how to insert the new element */ if (!full && after) { D("Not full, inserting after current position."); + quicklistDecompressNodeForUse(node); unsigned char *next = ziplistNext(node->zl, entry->zi); if (next == NULL) { node->zl = ziplistPush(node->zl, value, sz, ZIPLIST_TAIL); @@ -617,27 +864,34 @@ static void _quicklistInsert(quicklist *quicklist, const int fill, } node->count++; quicklistNodeUpdateSz(node); + quicklistRecompressOnly(quicklist, node); } else if (!full && !after) { D("Not full, inserting before current position."); + quicklistDecompressNodeForUse(node); node->zl = ziplistInsert(node->zl, entry->zi, value, sz); node->count++; quicklistNodeUpdateSz(node); + quicklistRecompressOnly(quicklist, node); } else if (full && at_tail && node->next && !full_next && after) { /* If we are: at tail, next has free space, and inserting after: * - insert entry at head of next node. */ D("Full and tail, but next isn't full; inserting next node head"); new_node = node->next; + quicklistDecompressNodeForUse(new_node); new_node->zl = ziplistPush(new_node->zl, value, sz, ZIPLIST_HEAD); new_node->count++; quicklistNodeUpdateSz(new_node); + quicklistRecompressOnly(quicklist, new_node); } else if (full && at_head && node->prev && !full_prev && !after) { /* If we are: at head, previous has free space, and inserting before: * - insert entry at tail of previous node. */ D("Full and head, but prev isn't full, inserting prev node tail"); new_node = node->prev; + quicklistDecompressNodeForUse(new_node); new_node->zl = ziplistPush(new_node->zl, value, sz, ZIPLIST_TAIL); new_node->count++; quicklistNodeUpdateSz(new_node); + quicklistRecompressOnly(quicklist, new_node); } else if (full && ((at_tail && node->next && full_next && after) || (at_head && node->prev && full_prev && !after))) { /* If we are: full, and our prev/next is full, then: @@ -652,27 +906,27 @@ static void _quicklistInsert(quicklist *quicklist, const int fill, /* else, node is full we need to split it. */ /* covers both after and !after cases */ D("\tsplitting node..."); + quicklistDecompressNodeForUse(node); new_node = _quicklistSplitNode(node, entry->offset, after); new_node->zl = ziplistPush(new_node->zl, value, sz, after ? ZIPLIST_HEAD : ZIPLIST_TAIL); new_node->count++; quicklistNodeUpdateSz(new_node); __quicklistInsertNode(quicklist, node, new_node, after); - _quicklistMergeNodes(quicklist, fill, node); + _quicklistMergeNodes(quicklist, node); } quicklist->count++; } -void quicklistInsertBefore(quicklist *quicklist, const int fill, - quicklistEntry *entry, void *value, - const size_t sz) { - _quicklistInsert(quicklist, fill, entry, value, sz, 0); +void quicklistInsertBefore(quicklist *quicklist, quicklistEntry *entry, + void *value, const size_t sz) { + _quicklistInsert(quicklist, entry, value, sz, 0); } -void quicklistInsertAfter(quicklist *quicklist, const int fill, - quicklistEntry *entry, void *value, const size_t sz) { - _quicklistInsert(quicklist, fill, entry, value, sz, 1); +void quicklistInsertAfter(quicklist *quicklist, quicklistEntry *entry, + void *value, const size_t sz) { + _quicklistInsert(quicklist, entry, value, sz, 1); } /* Delete a range of elements from the quicklist. @@ -745,11 +999,14 @@ int quicklistDelRange(quicklist *quicklist, const long start, if (delete_entire_node) { __quicklistDelNode(quicklist, node); } else { + quicklistDecompressNodeForUse(node); node->zl = ziplistDeleteRange(node->zl, entry.offset, del); - node->count -= del; quicklistNodeUpdateSz(node); + node->count -= del; quicklist->count -= del; quicklistDeleteIfEmpty(quicklist, node); + if (node) + quicklistRecompressOnly(quicklist, node); } extent -= del; @@ -807,8 +1064,14 @@ quicklistIter *quicklistGetIteratorAtIdx(const quicklist *quicklist, } } -/* Release iterator */ -void quicklistReleaseIterator(quicklistIter *iter) { zfree(iter); } +/* Release iterator. + * If we still have a valid current node, then re-encode current node. */ +void quicklistReleaseIterator(quicklistIter *iter) { + if (iter->current) + quicklistCompress(iter->quicklist, iter->current); + + zfree(iter); +} /* Get next element in iterator. * @@ -852,6 +1115,7 @@ int quicklistNext(quicklistIter *iter, quicklistEntry *entry) { if (!iter->zi) { /* If !zi, use current index. */ + quicklistDecompressNodeForUse(iter->current); iter->zi = ziplistIndex(iter->current->zl, iter->offset); } else { /* else, use existing iterator offset and get prev/next as necessary. */ @@ -876,6 +1140,7 @@ int quicklistNext(quicklistIter *iter, quicklistEntry *entry) { } else { /* We ran out of ziplist entries. * Pick next node, update offset, then re-run retrieval. */ + quicklistCompress(iter->quicklist, iter->current); if (iter->direction == AL_START_HEAD) { /* Forward traversal */ D("Jumping to start of next node"); @@ -901,19 +1166,26 @@ int quicklistNext(quicklistIter *iter, quicklistEntry *entry) { quicklist *quicklistDup(quicklist *orig) { quicklist *copy; - copy = quicklistCreate(); + copy = quicklistNew(orig->fill, orig->compress); for (quicklistNode *current = orig->head; current; current = current->next) { quicklistNode *node = quicklistCreateNode(); - size_t ziplen = ziplistBlobLen(current->zl); - node->zl = zmalloc(ziplen); - memcpy(node->zl, current->zl, ziplen); + if (node->encoding == QUICKLIST_NODE_ENCODING_LZF) { + quicklistLZF *lzf = (quicklistLZF *)node->zl; + size_t lzf_sz = sizeof(*lzf) + lzf->sz; + node->zl = zmalloc(lzf_sz); + memcpy(node->zl, current->zl, lzf_sz); + } else if (node->encoding == QUICKLIST_NODE_ENCODING_RAW) { + node->zl = zmalloc(current->sz); + memcpy(node->zl, current->zl, current->sz); + } node->count = current->count; copy->count += node->count; node->sz = current->sz; + node->encoding = current->encoding; _quicklistInsertNodeAfter(copy, copy->tail, node); } @@ -978,19 +1250,20 @@ int quicklistIndex(const quicklist *quicklist, const long long idx, entry->offset = (-index) - 1 + accum; } + quicklistDecompressNodeForUse(entry->node); entry->zi = ziplistIndex(entry->node->zl, entry->offset); ziplistGet(entry->zi, &entry->value, &entry->sz, &entry->longval); + // quicklistCompress(quicklist, entry->node); return 1; } /* Rotate quicklist by moving the tail element to the head. */ -void quicklistRotate(quicklist *quicklist, const int fill) { +void quicklistRotate(quicklist *quicklist) { if (quicklist->count <= 1) return; /* First, get the tail entry */ - quicklistNode *tail = quicklist->tail; - unsigned char *p = ziplistIndex(tail->zl, -1); + unsigned char *p = ziplistIndex(quicklist->tail->zl, -1); unsigned char *value; long long longval; unsigned int sz; @@ -1005,16 +1278,17 @@ void quicklistRotate(quicklist *quicklist, const int fill) { } /* Add tail entry to head (must happen before tail is deleted). */ - quicklistPushHead(quicklist, fill, value, sz); + quicklistPushHead(quicklist, value, sz); /* If quicklist has only one node, the head ziplist is also the * tail ziplist and PushHead() could have reallocated our single ziplist, * which would make our pre-existing 'p' unusable. */ - if (quicklist->len == 1) - p = ziplistIndex(tail->zl, -1); + if (quicklist->len == 1) { + p = ziplistIndex(quicklist->tail->zl, -1); + } /* Remove tail entry. */ - quicklistDelIndex(quicklist, tail, &p); + quicklistDelIndex(quicklist, quicklist->tail, &p); } /* pop from quicklist and return result in 'data' ptr. Value of 'data' @@ -1106,18 +1380,19 @@ int quicklistPop(quicklist *quicklist, int where, unsigned char **data, } /* Wrapper to allow argument-based switching between HEAD/TAIL pop */ -void quicklistPush(quicklist *quicklist, const int fill, void *value, - const size_t sz, int where) { +void quicklistPush(quicklist *quicklist, void *value, const size_t sz, + int where) { if (where == QUICKLIST_HEAD) { - quicklistPushHead(quicklist, fill, value, sz); + quicklistPushHead(quicklist, value, sz); } else if (where == QUICKLIST_TAIL) { - quicklistPushTail(quicklist, fill, value, sz); + quicklistPushTail(quicklist, value, sz); } } /* The rest of this file is test cases and test helpers. */ #ifdef REDIS_TEST #include +#include #define assert(_e) \ do { \ @@ -1165,6 +1440,20 @@ static void ql_info(quicklist *ql) { #endif } +/* Return the UNIX time in microseconds */ +static long long ustime(void) { + struct timeval tv; + long long ust; + + gettimeofday(&tv, NULL); + ust = ((long long)tv.tv_sec) * 1000000; + ust += tv.tv_usec; + return ust; +} + +/* Return the UNIX time in milliseconds */ +static long long mstime(void) { return ustime() / 1000; } + /* Iterate over an entire quicklist. * Print the list if 'print' == 1. * @@ -1207,17 +1496,17 @@ static int itrprintr_rev(quicklist *ql, int print) { /* Verify list metadata matches physical list contents. */ static int _ql_verify(quicklist *ql, uint32_t len, uint32_t count, uint32_t head_count, uint32_t tail_count) { - int ok = 1; + int errors = 0; ql_info(ql); if (len != ql->len) { - yell("quicklist length wrong: expected %d, got %lu", len, ql->len); - ok = 0; + yell("quicklist length wrong: expected %d, got %u", len, ql->len); + errors++; } if (count != ql->count) { yell("quicklist count wrong: expected %d, got %lu", count, ql->count); - ok = 0; + errors++; } int loopr = itrprintr(ql, 0); @@ -1225,7 +1514,7 @@ static int _ql_verify(quicklist *ql, uint32_t len, uint32_t count, yell("quicklist cached count not match actual count: expected %lu, got " "%d", ql->count, loopr); - ok = 0; + errors++; } int rloopr = itrprintr_rev(ql, 0); @@ -1233,32 +1522,62 @@ static int _ql_verify(quicklist *ql, uint32_t len, uint32_t count, yell("quicklist has different forward count than reverse count! " "Forward count is %d, reverse count is %d.", loopr, rloopr); - ok = 0; + errors++; } - if (ql->len == 0 && ok) { + if (ql->len == 0 && !errors) { OK; - return !ok; + return errors; } - if (head_count != ql->head->count && + if (ql->head && head_count != ql->head->count && head_count != ziplistLen(ql->head->zl)) { yell("quicklist head count wrong: expected %d, " "got cached %d vs. actual %d", head_count, ql->head->count, ziplistLen(ql->head->zl)); - ok = 0; + errors++; } - if (tail_count != ql->tail->count && + if (ql->tail && tail_count != ql->tail->count && tail_count != ziplistLen(ql->tail->zl)) { yell("quicklist tail count wrong: expected %d, " "got cached %u vs. actual %d", tail_count, ql->tail->count, ziplistLen(ql->tail->zl)); - ok = 0; + errors++; + } + + if (quicklistAllowsCompression(ql)) { + quicklistNode *node = ql->head; + unsigned int low_raw = ql->compress; + unsigned int high_raw = ql->len - ql->compress; + + for (unsigned int at = 0; at < ql->len; at++, node = node->next) { + if (node && (at < low_raw || at >= high_raw)) { + if (node->encoding != QUICKLIST_NODE_ENCODING_RAW) { + yell("Incorrect compression: node %d is " + "compressed at depth %d ((%u, %u); total " + "nodes: %u; size: %u; recompress: %d)", + at, ql->compress, low_raw, high_raw, ql->len, node->sz, + node->recompress); + errors++; + } + } else { + if (node->encoding != QUICKLIST_NODE_ENCODING_LZF && + !node->attempted_compress) { + yell("Incorrect non-compression: node %d is NOT " + "compressed at depth %d ((%u, %u); total " + "nodes: %u; size: %u; recompress: %d; attempted: %d)", + at, ql->compress, low_raw, high_raw, ql->len, node->sz, + node->recompress, node->attempted_compress); + errors++; + } + } + } } - if (ok) + + if (!errors) OK; - return !ok; + return errors; } /* Generate new string concatenating integer i against string 'prefix' */ @@ -1268,920 +1587,1027 @@ static char *genstr(char *prefix, int i) { return result; } -/* Test fill cap */ -#define F 32 /* main test, but callable from other files */ int quicklistTest(int argc, char *argv[]) { + UNUSED(argc); + UNUSED(argv); + unsigned int err = 0; int optimize_start = -(int)(sizeof(optimization_level) / sizeof(*optimization_level)); printf("Starting optimization offset at: %d\n", optimize_start); - UNUSED(argc); - UNUSED(argv); + int options[] = { 0, 1, 2, 3, 4, 5, 6, 10 }; + size_t option_count = sizeof(options) / sizeof(*options); + long long runtime[option_count]; - TEST("create list") { - quicklist *ql = quicklistCreate(); - ql_verify(ql, 0, 0, 0, 0); - quicklistRelease(ql); - } + for (int _i = 0; _i < (int)option_count; _i++) { + printf("Testing Option %d\n", options[_i]); + long long start = mstime(); - TEST("add to tail of empty list") { - quicklist *ql = quicklistCreate(); - quicklistPushTail(ql, F, "hello", 6); - /* 1 for head and 1 for tail beacuse 1 node = head = tail */ - ql_verify(ql, 1, 1, 1, 1); - quicklistRelease(ql); - } - - TEST("add to head of empty list") { - quicklist *ql = quicklistCreate(); - quicklistPushHead(ql, F, "hello", 6); - /* 1 for head and 1 for tail beacuse 1 node = head = tail */ - ql_verify(ql, 1, 1, 1, 1); - quicklistRelease(ql); - } - - for (int f = optimize_start; f < 32; f++) { - TEST_DESC("add to tail 5x at fill %d", f) { - quicklist *ql = quicklistCreate(); - for (int i = 0; i < 5; i++) - quicklistPushTail(ql, f, genstr("hello", i), 32); - if (ql->count != 5) - ERROR; - if (f == 32) - ql_verify(ql, 1, 5, 5, 5); + TEST("create list") { + quicklist *ql = quicklistNew(-2, options[_i]); + ql_verify(ql, 0, 0, 0, 0); quicklistRelease(ql); } - } - for (int f = optimize_start; f < 32; f++) { - TEST_DESC("add to head 5x at fill %d", f) { - quicklist *ql = quicklistCreate(); - for (int i = 0; i < 5; i++) - quicklistPushHead(ql, f, genstr("hello", i), 32); - if (ql->count != 5) - ERROR; - if (f == 32) - ql_verify(ql, 1, 5, 5, 5); + TEST("add to tail of empty list") { + quicklist *ql = quicklistNew(-2, options[_i]); + quicklistPushTail(ql, "hello", 6); + /* 1 for head and 1 for tail beacuse 1 node = head = tail */ + ql_verify(ql, 1, 1, 1, 1); quicklistRelease(ql); } - } - for (int f = optimize_start; f < 512; f++) { - TEST_DESC("add to tail 500x at fill %d", f) { - quicklist *ql = quicklistCreate(); - for (int i = 0; i < 500; i++) - quicklistPushTail(ql, f, genstr("hello", i), 32); - if (ql->count != 500) - ERROR; - if (f == 32) - ql_verify(ql, 16, 500, 32, 20); + TEST("add to head of empty list") { + quicklist *ql = quicklistNew(-2, options[_i]); + quicklistPushHead(ql, "hello", 6); + /* 1 for head and 1 for tail beacuse 1 node = head = tail */ + ql_verify(ql, 1, 1, 1, 1); quicklistRelease(ql); } - } - for (int f = optimize_start; f < 512; f++) { - TEST_DESC("add to head 500x at fill %d", f) { - quicklist *ql = quicklistCreate(); - for (int i = 0; i < 500; i++) - quicklistPushHead(ql, f, genstr("hello", i), 32); - if (ql->count != 500) - ERROR; - if (f == 32) - ql_verify(ql, 16, 500, 20, 32); - quicklistRelease(ql); + for (int f = optimize_start; f < 32; f++) { + TEST_DESC("add to tail 5x at fill %d at compress %d", f, + options[_i]) { + quicklist *ql = quicklistNew(f, options[_i]); + for (int i = 0; i < 5; i++) + quicklistPushTail(ql, genstr("hello", i), 32); + if (ql->count != 5) + ERROR; + if (f == 32) + ql_verify(ql, 1, 5, 5, 5); + quicklistRelease(ql); + } } - } - TEST("rotate empty") { - quicklist *ql = quicklistCreate(); - quicklistRotate(ql, F); - ql_verify(ql, 0, 0, 0, 0); - quicklistRelease(ql); - } + for (int f = optimize_start; f < 32; f++) { + TEST_DESC("add to head 5x at fill %d at compress %d", f, + options[_i]) { + quicklist *ql = quicklistNew(f, options[_i]); + for (int i = 0; i < 5; i++) + quicklistPushHead(ql, genstr("hello", i), 32); + if (ql->count != 5) + ERROR; + if (f == 32) + ql_verify(ql, 1, 5, 5, 5); + quicklistRelease(ql); + } + } - for (int f = optimize_start; f < 32; f++) { - TEST("rotate one val once") { - quicklist *ql = quicklistCreate(); - quicklistPushHead(ql, F, "hello", 6); - quicklistRotate(ql, F); - ql_verify(ql, 1, 1, 1, 1); - quicklistRelease(ql); + for (int f = optimize_start; f < 512; f++) { + TEST_DESC("add to tail 500x at fill %d at compress %d", f, + options[_i]) { + quicklist *ql = quicklistNew(f, options[_i]); + for (int i = 0; i < 500; i++) + quicklistPushTail(ql, genstr("hello", i), 64); + if (ql->count != 500) + ERROR; + if (f == 32) + ql_verify(ql, 16, 500, 32, 20); + quicklistRelease(ql); + } } - } - for (int f = optimize_start; f < 1024; f++) { - TEST_DESC("rotate 500 val 5000 times at fill %d", f) { - quicklist *ql = quicklistCreate(); - quicklistPushHead(ql, f, "900", 3); - quicklistPushHead(ql, f, "7000", 4); - quicklistPushHead(ql, f, "-1200", 5); - quicklistPushHead(ql, f, "42", 2); - for (int i = 0; i < 500; i++) - quicklistPushHead(ql, f, genstr("hello", i), 32); - ql_info(ql); - for (int i = 0; i < 5000; i++) { - ql_info(ql); - quicklistRotate(ql, f); + for (int f = optimize_start; f < 512; f++) { + TEST_DESC("add to head 500x at fill %d at compress %d", f, + options[_i]) { + quicklist *ql = quicklistNew(f, options[_i]); + for (int i = 0; i < 500; i++) + quicklistPushHead(ql, genstr("hello", i), 32); + if (ql->count != 500) + ERROR; + if (f == 32) + ql_verify(ql, 16, 500, 20, 32); + quicklistRelease(ql); } - if (f == 1) - ql_verify(ql, 504, 504, 1, 1); - else if (f == 2) - ql_verify(ql, 252, 504, 2, 2); - else if (f == 32) - ql_verify(ql, 16, 504, 32, 24); + } + + TEST("rotate empty") { + quicklist *ql = quicklistNew(-2, options[_i]); + quicklistRotate(ql); + ql_verify(ql, 0, 0, 0, 0); quicklistRelease(ql); } - } - TEST("pop empty") { - quicklist *ql = quicklistCreate(); - quicklistPop(ql, QUICKLIST_HEAD, NULL, NULL, NULL); - ql_verify(ql, 0, 0, 0, 0); - quicklistRelease(ql); - } + for (int f = optimize_start; f < 32; f++) { + TEST("rotate one val once") { + quicklist *ql = quicklistNew(f, options[_i]); + quicklistPushHead(ql, "hello", 6); + quicklistRotate(ql); + /* Ignore compression verify because ziplist is + * too small to compress. */ + ql_verify(ql, 1, 1, 1, 1); + quicklistRelease(ql); + } + } - TEST("pop 1 string from 1") { - quicklist *ql = quicklistCreate(); - quicklistPushHead(ql, F, genstr("hello", 331), 32); - unsigned char *data; - unsigned int sz; - long long lv; - ql_info(ql); - quicklistPop(ql, QUICKLIST_HEAD, &data, &sz, &lv); - assert(data != NULL); - assert(sz == 32); - zfree(data); - ql_verify(ql, 0, 0, 0, 0); - quicklistRelease(ql); - } + for (int f = optimize_start; f < 3; f++) { + TEST_DESC("rotate 500 val 5000 times at fill %d at compress %d", f, + options[_i]) { + quicklist *ql = quicklistNew(f, options[_i]); + quicklistPushHead(ql, "900", 3); + quicklistPushHead(ql, "7000", 4); + quicklistPushHead(ql, "-1200", 5); + quicklistPushHead(ql, "42", 2); + for (int i = 0; i < 500; i++) + quicklistPushHead(ql, genstr("hello", i), 64); + ql_info(ql); + for (int i = 0; i < 5000; i++) { + ql_info(ql); + quicklistRotate(ql); + } + if (f == 1) + ql_verify(ql, 504, 504, 1, 1); + else if (f == 2) + ql_verify(ql, 252, 504, 2, 2); + else if (f == 32) + ql_verify(ql, 16, 504, 32, 24); + quicklistRelease(ql); + } + } - TEST("pop head 1 number from 1") { - quicklist *ql = quicklistCreate(); - quicklistPushHead(ql, F, "55513", 5); - unsigned char *data; - unsigned int sz; - long long lv; - ql_info(ql); - quicklistPop(ql, QUICKLIST_HEAD, &data, &sz, &lv); - assert(data == NULL); - assert(lv == 55513); - ql_verify(ql, 0, 0, 0, 0); - quicklistRelease(ql); - } + TEST("pop empty") { + quicklist *ql = quicklistNew(-2, options[_i]); + quicklistPop(ql, QUICKLIST_HEAD, NULL, NULL, NULL); + ql_verify(ql, 0, 0, 0, 0); + quicklistRelease(ql); + } - TEST("pop head 500 from 500") { - quicklist *ql = quicklistCreate(); - for (int i = 0; i < 500; i++) - quicklistPushHead(ql, F, genstr("hello", i), 32); - ql_info(ql); - for (int i = 0; i < 500; i++) { + TEST("pop 1 string from 1") { + quicklist *ql = quicklistNew(-2, options[_i]); + quicklistPushHead(ql, genstr("hello", 331), 32); unsigned char *data; unsigned int sz; long long lv; - int ret = quicklistPop(ql, QUICKLIST_HEAD, &data, &sz, &lv); - assert(ret == 1); + ql_info(ql); + quicklistPop(ql, QUICKLIST_HEAD, &data, &sz, &lv); assert(data != NULL); assert(sz == 32); zfree(data); + ql_verify(ql, 0, 0, 0, 0); + quicklistRelease(ql); } - ql_verify(ql, 0, 0, 0, 0); - quicklistRelease(ql); - } - TEST("pop head 5000 from 500") { - quicklist *ql = quicklistCreate(); - for (int i = 0; i < 500; i++) - quicklistPushHead(ql, F, genstr("hello", i), 32); - for (int i = 0; i < 5000; i++) { + TEST("pop head 1 number from 1") { + quicklist *ql = quicklistNew(-2, options[_i]); + quicklistPushHead(ql, "55513", 5); unsigned char *data; unsigned int sz; long long lv; - int ret = quicklistPop(ql, QUICKLIST_HEAD, &data, &sz, &lv); - if (i < 500) { + ql_info(ql); + quicklistPop(ql, QUICKLIST_HEAD, &data, &sz, &lv); + assert(data == NULL); + assert(lv == 55513); + ql_verify(ql, 0, 0, 0, 0); + quicklistRelease(ql); + } + + TEST("pop head 500 from 500") { + quicklist *ql = quicklistNew(-2, options[_i]); + for (int i = 0; i < 500; i++) + quicklistPushHead(ql, genstr("hello", i), 32); + ql_info(ql); + for (int i = 0; i < 500; i++) { + unsigned char *data; + unsigned int sz; + long long lv; + int ret = quicklistPop(ql, QUICKLIST_HEAD, &data, &sz, &lv); assert(ret == 1); assert(data != NULL); assert(sz == 32); zfree(data); - } else { - assert(ret == 0); } + ql_verify(ql, 0, 0, 0, 0); + quicklistRelease(ql); } - ql_verify(ql, 0, 0, 0, 0); - quicklistRelease(ql); - } - - TEST("iterate forward over 500 list") { - quicklist *ql = quicklistCreate(); - for (int i = 0; i < 500; i++) - quicklistPushHead(ql, F, genstr("hello", i), 32); - quicklistIter *iter = quicklistGetIterator(ql, AL_START_HEAD); - quicklistEntry entry; - int i = 499, count = 0; - while (quicklistNext(iter, &entry)) { - char *h = genstr("hello", i); - if (strcmp((char *)entry.value, h)) - ERR("value [%s] didn't match [%s] at position %d", entry.value, - h, i); - i--; - count++; - } - if (count != 500) - ERR("Didn't iterate over exactly 500 elements (%d)", i); - ql_verify(ql, 16, 500, 20, 32); - quicklistReleaseIterator(iter); - quicklistRelease(ql); - } - - TEST("iterate reverse over 500 list") { - quicklist *ql = quicklistCreate(); - for (int i = 0; i < 500; i++) - quicklistPushHead(ql, F, genstr("hello", i), 32); - quicklistIter *iter = quicklistGetIterator(ql, AL_START_TAIL); - quicklistEntry entry; - int i = 0; - while (quicklistNext(iter, &entry)) { - char *h = genstr("hello", i); - if (strcmp((char *)entry.value, h)) - ERR("value [%s] didn't match [%s] at position %d", entry.value, - h, i); - i++; - } - if (i != 500) - ERR("Didn't iterate over exactly 500 elements (%d)", i); - ql_verify(ql, 16, 500, 20, 32); - quicklistReleaseIterator(iter); - quicklistRelease(ql); - } - - TEST("insert before with 0 elements") { - quicklist *ql = quicklistCreate(); - quicklistEntry entry; - quicklistIndex(ql, 0, &entry); - quicklistInsertBefore(ql, F, &entry, "abc", 4); - ql_verify(ql, 1, 1, 1, 1); - quicklistRelease(ql); - } - - TEST("insert after with 0 elements") { - quicklist *ql = quicklistCreate(); - quicklistEntry entry; - quicklistIndex(ql, 0, &entry); - quicklistInsertAfter(ql, F, &entry, "abc", 4); - ql_verify(ql, 1, 1, 1, 1); - quicklistRelease(ql); - } - TEST("insert after 1 element") { - quicklist *ql = quicklistCreate(); - quicklistPushHead(ql, F, "hello", 6); - quicklistEntry entry; - quicklistIndex(ql, 0, &entry); - quicklistInsertAfter(ql, F, &entry, "abc", 4); - ql_verify(ql, 1, 2, 2, 2); - quicklistRelease(ql); - } - - TEST("insert before 1 element") { - quicklist *ql = quicklistCreate(); - quicklistPushHead(ql, F, "hello", 6); - quicklistEntry entry; - quicklistIndex(ql, 0, &entry); - quicklistInsertAfter(ql, F, &entry, "abc", 4); - ql_verify(ql, 1, 2, 2, 2); - quicklistRelease(ql); - } - - for (int f = optimize_start; f < 12; f++) { - TEST_DESC("insert once in elements while iterating at fill %d\n", f) { - quicklist *ql = quicklistCreate(); - quicklistPushTail(ql, f, "abc", 3); - quicklistPushTail(ql, 1, "def", 3); /* force to unique node */ - quicklistPushTail(ql, f, "bob", 3); /* force to reset for +3 */ - quicklistPushTail(ql, f, "foo", 3); - quicklistPushTail(ql, f, "zoo", 3); - - itrprintr(ql, 1); - /* insert "bar" before "bob" while iterating over list. */ - quicklistIter *iter = quicklistGetIterator(ql, AL_START_HEAD); - quicklistEntry entry; - while (quicklistNext(iter, &entry)) { - if (!strncmp((char *)entry.value, "bob", 3)) { - /* Insert as fill = 1 so it spills into new node. */ - quicklistInsertBefore(ql, f, &entry, "bar", 3); - /* NOTE! You can't continue iterating after an insert into - * the list. You *must* re-create your iterator again if - * you want to traverse all entires. */ - break; + TEST("pop head 5000 from 500") { + quicklist *ql = quicklistNew(-2, options[_i]); + for (int i = 0; i < 500; i++) + quicklistPushHead(ql, genstr("hello", i), 32); + for (int i = 0; i < 5000; i++) { + unsigned char *data; + unsigned int sz; + long long lv; + int ret = quicklistPop(ql, QUICKLIST_HEAD, &data, &sz, &lv); + if (i < 500) { + assert(ret == 1); + assert(data != NULL); + assert(sz == 32); + zfree(data); + } else { + assert(ret == 0); } } - itrprintr(ql, 1); - - /* verify results */ - quicklistIndex(ql, 0, &entry); - if (strncmp((char *)entry.value, "abc", 3)) - ERR("Value 0 didn't match, instead got: %.*s", entry.sz, - entry.value); - quicklistIndex(ql, 1, &entry); - if (strncmp((char *)entry.value, "def", 3)) - ERR("Value 1 didn't match, instead got: %.*s", entry.sz, - entry.value); - quicklistIndex(ql, 2, &entry); - if (strncmp((char *)entry.value, "bar", 3)) - ERR("Value 2 didn't match, instead got: %.*s", entry.sz, - entry.value); - quicklistIndex(ql, 3, &entry); - if (strncmp((char *)entry.value, "bob", 3)) - ERR("Value 3 didn't match, instead got: %.*s", entry.sz, - entry.value); - quicklistIndex(ql, 4, &entry); - if (strncmp((char *)entry.value, "foo", 3)) - ERR("Value 4 didn't match, instead got: %.*s", entry.sz, - entry.value); - quicklistIndex(ql, 5, &entry); - if (strncmp((char *)entry.value, "zoo", 3)) - ERR("Value 5 didn't match, instead got: %.*s", entry.sz, - entry.value); - quicklistReleaseIterator(iter); + ql_verify(ql, 0, 0, 0, 0); quicklistRelease(ql); } - } - for (int f = optimize_start; f < 1024; f++) { - TEST_DESC("insert [before] 250 new in middle of 500 elements at fill" - " %d", - f) { - quicklist *ql = quicklistCreate(); + TEST("iterate forward over 500 list") { + quicklist *ql = quicklistNew(-2, options[_i]); + quicklistSetFill(ql, 32); for (int i = 0; i < 500; i++) - quicklistPushTail(ql, f, genstr("hello", i), 32); - for (int i = 0; i < 250; i++) { - quicklistEntry entry; - quicklistIndex(ql, 250, &entry); - quicklistInsertBefore(ql, f, &entry, genstr("abc", i), 32); + quicklistPushHead(ql, genstr("hello", i), 32); + quicklistIter *iter = quicklistGetIterator(ql, AL_START_HEAD); + quicklistEntry entry; + int i = 499, count = 0; + while (quicklistNext(iter, &entry)) { + char *h = genstr("hello", i); + if (strcmp((char *)entry.value, h)) + ERR("value [%s] didn't match [%s] at position %d", + entry.value, h, i); + i--; + count++; } - if (f == 32) - ql_verify(ql, 25, 750, 32, 20); + if (count != 500) + ERR("Didn't iterate over exactly 500 elements (%d)", i); + ql_verify(ql, 16, 500, 20, 32); + quicklistReleaseIterator(iter); quicklistRelease(ql); } - } - for (int f = optimize_start; f < 1024; f++) { - TEST_DESC("insert [after] 250 new in middle of 500 elements at fill %d", - f) { - quicklist *ql = quicklistCreate(); + TEST("iterate reverse over 500 list") { + quicklist *ql = quicklistNew(-2, options[_i]); + quicklistSetFill(ql, 32); for (int i = 0; i < 500; i++) - quicklistPushHead(ql, f, genstr("hello", i), 32); - for (int i = 0; i < 250; i++) { - quicklistEntry entry; - quicklistIndex(ql, 250, &entry); - quicklistInsertAfter(ql, f, &entry, genstr("abc", i), 32); + quicklistPushHead(ql, genstr("hello", i), 32); + quicklistIter *iter = quicklistGetIterator(ql, AL_START_TAIL); + quicklistEntry entry; + int i = 0; + while (quicklistNext(iter, &entry)) { + char *h = genstr("hello", i); + if (strcmp((char *)entry.value, h)) + ERR("value [%s] didn't match [%s] at position %d", + entry.value, h, i); + i++; } - - if (ql->count != 750) - ERR("List size not 750, but rather %ld", ql->count); - - if (f == 32) - ql_verify(ql, 26, 750, 20, 32); + if (i != 500) + ERR("Didn't iterate over exactly 500 elements (%d)", i); + ql_verify(ql, 16, 500, 20, 32); + quicklistReleaseIterator(iter); quicklistRelease(ql); } - } - - TEST("duplicate empty list") { - quicklist *ql = quicklistCreate(); - ql_verify(ql, 0, 0, 0, 0); - quicklist *copy = quicklistDup(ql); - ql_verify(copy, 0, 0, 0, 0); - quicklistRelease(ql); - quicklistRelease(copy); - } - - TEST("duplicate list of 1 element") { - quicklist *ql = quicklistCreate(); - quicklistPushHead(ql, F, genstr("hello", 3), 32); - ql_verify(ql, 1, 1, 1, 1); - quicklist *copy = quicklistDup(ql); - ql_verify(copy, 1, 1, 1, 1); - quicklistRelease(ql); - quicklistRelease(copy); - } - - TEST("duplicate list of 500") { - quicklist *ql = quicklistCreate(); - for (int i = 0; i < 500; i++) - quicklistPushHead(ql, F, genstr("hello", i), 32); - ql_verify(ql, 16, 500, 20, 32); - quicklist *copy = quicklistDup(ql); - ql_verify(copy, 16, 500, 20, 32); - quicklistRelease(ql); - quicklistRelease(copy); - } - - for (int f = optimize_start; f < 512; f++) { - TEST_DESC("index 1,200 from 500 list at fill %d", f) { - quicklist *ql = quicklistCreate(); - for (int i = 0; i < 500; i++) - quicklistPushTail(ql, f, genstr("hello", i + 1), 32); + TEST("insert before with 0 elements") { + quicklist *ql = quicklistNew(-2, options[_i]); quicklistEntry entry; - quicklistIndex(ql, 1, &entry); - if (!strcmp((char *)entry.value, "hello2")) - OK; - else - ERR("Value: %s", entry.value); - quicklistIndex(ql, 200, &entry); - if (!strcmp((char *)entry.value, "hello201")) - OK; - else - ERR("Value: %s", entry.value); + quicklistIndex(ql, 0, &entry); + quicklistInsertBefore(ql, &entry, "abc", 4); + ql_verify(ql, 1, 1, 1, 1); quicklistRelease(ql); } - TEST_DESC("index -1,-2 from 500 list at fill %d", f) { - quicklist *ql = quicklistCreate(); - for (int i = 0; i < 500; i++) - quicklistPushTail(ql, f, genstr("hello", i + 1), 32); + TEST("insert after with 0 elements") { + quicklist *ql = quicklistNew(-2, options[_i]); quicklistEntry entry; - quicklistIndex(ql, -1, &entry); - if (!strcmp((char *)entry.value, "hello500")) - OK; - else - ERR("Value: %s", entry.value); - quicklistIndex(ql, -2, &entry); - if (!strcmp((char *)entry.value, "hello499")) - OK; - else - ERR("Value: %s", entry.value); + quicklistIndex(ql, 0, &entry); + quicklistInsertAfter(ql, &entry, "abc", 4); + ql_verify(ql, 1, 1, 1, 1); quicklistRelease(ql); } - TEST_DESC("index -100 from 500 list at fill %d", f) { - quicklist *ql = quicklistCreate(); - for (int i = 0; i < 500; i++) - quicklistPushTail(ql, f, genstr("hello", i + 1), 32); + TEST("insert after 1 element") { + quicklist *ql = quicklistNew(-2, options[_i]); + quicklistPushHead(ql, "hello", 6); quicklistEntry entry; - quicklistIndex(ql, -100, &entry); - if (!strcmp((char *)entry.value, "hello401")) - OK; - else - ERR("Value: %s", entry.value); + quicklistIndex(ql, 0, &entry); + quicklistInsertAfter(ql, &entry, "abc", 4); + ql_verify(ql, 1, 2, 2, 2); quicklistRelease(ql); } - TEST_DESC("index too big +1 from 50 list at fill %d", f) { - quicklist *ql = quicklistCreate(); - for (int i = 0; i < 50; i++) - quicklistPushTail(ql, f, genstr("hello", i + 1), 32); + TEST("insert before 1 element") { + quicklist *ql = quicklistNew(-2, options[_i]); + quicklistPushHead(ql, "hello", 6); quicklistEntry entry; - if (quicklistIndex(ql, 50, &entry)) - ERR("Index found at 50 with 50 list: %.*s", entry.sz, - entry.value); - else - OK; + quicklistIndex(ql, 0, &entry); + quicklistInsertAfter(ql, &entry, "abc", 4); + ql_verify(ql, 1, 2, 2, 2); quicklistRelease(ql); } - } - - TEST("delete range empty list") { - quicklist *ql = quicklistCreate(); - quicklistDelRange(ql, 5, 20); - ql_verify(ql, 0, 0, 0, 0); - quicklistRelease(ql); - } - - TEST("delete range of entire node in list of one node") { - quicklist *ql = quicklistCreate(); - for (int i = 0; i < 32; i++) - quicklistPushHead(ql, F, genstr("hello", i), 32); - ql_verify(ql, 1, 32, 32, 32); - quicklistDelRange(ql, 0, 32); - ql_verify(ql, 0, 0, 0, 0); - quicklistRelease(ql); - } - TEST("delete range of entire node with overflow counts") { - quicklist *ql = quicklistCreate(); - for (int i = 0; i < 32; i++) - quicklistPushHead(ql, F, genstr("hello", i), 32); - ql_verify(ql, 1, 32, 32, 32); - quicklistDelRange(ql, 0, 128); - ql_verify(ql, 0, 0, 0, 0); - quicklistRelease(ql); - } + for (int f = optimize_start; f < 12; f++) { + TEST_DESC("insert once in elements while iterating at fill %d at " + "compress %d\n", + f, options[_i]) { + quicklist *ql = quicklistNew(f, options[_i]); + quicklistPushTail(ql, "abc", 3); + quicklistSetFill(ql, 1); + quicklistPushTail(ql, "def", 3); /* force to unique node */ + quicklistSetFill(ql, f); + quicklistPushTail(ql, "bob", 3); /* force to reset for +3 */ + quicklistPushTail(ql, "foo", 3); + quicklistPushTail(ql, "zoo", 3); + + itrprintr(ql, 0); + /* insert "bar" before "bob" while iterating over list. */ + quicklistIter *iter = quicklistGetIterator(ql, AL_START_HEAD); + quicklistEntry entry; + while (quicklistNext(iter, &entry)) { + if (!strncmp((char *)entry.value, "bob", 3)) { + /* Insert as fill = 1 so it spills into new node. */ + quicklistInsertBefore(ql, &entry, "bar", 3); + break; /* didn't we fix insert-while-iterating? */ + } + } + itrprintr(ql, 0); + + /* verify results */ + quicklistIndex(ql, 0, &entry); + if (strncmp((char *)entry.value, "abc", 3)) + ERR("Value 0 didn't match, instead got: %.*s", entry.sz, + entry.value); + quicklistIndex(ql, 1, &entry); + if (strncmp((char *)entry.value, "def", 3)) + ERR("Value 1 didn't match, instead got: %.*s", entry.sz, + entry.value); + quicklistIndex(ql, 2, &entry); + if (strncmp((char *)entry.value, "bar", 3)) + ERR("Value 2 didn't match, instead got: %.*s", entry.sz, + entry.value); + quicklistIndex(ql, 3, &entry); + if (strncmp((char *)entry.value, "bob", 3)) + ERR("Value 3 didn't match, instead got: %.*s", entry.sz, + entry.value); + quicklistIndex(ql, 4, &entry); + if (strncmp((char *)entry.value, "foo", 3)) + ERR("Value 4 didn't match, instead got: %.*s", entry.sz, + entry.value); + quicklistIndex(ql, 5, &entry); + if (strncmp((char *)entry.value, "zoo", 3)) + ERR("Value 5 didn't match, instead got: %.*s", entry.sz, + entry.value); + quicklistReleaseIterator(iter); + quicklistRelease(ql); + } + } - TEST("delete middle 100 of 500 list") { - quicklist *ql = quicklistCreate(); - for (int i = 0; i < 500; i++) - quicklistPushTail(ql, F, genstr("hello", i + 1), 32); - ql_verify(ql, 16, 500, 32, 20); - quicklistDelRange(ql, 200, 100); - ql_verify(ql, 14, 400, 32, 20); - quicklistRelease(ql); - } + for (int f = optimize_start; f < 1024; f++) { + TEST_DESC( + "insert [before] 250 new in middle of 500 elements at fill" + " %d at compress %d", + f, options[_i]) { + quicklist *ql = quicklistNew(f, options[_i]); + for (int i = 0; i < 500; i++) + quicklistPushTail(ql, genstr("hello", i), 32); + for (int i = 0; i < 250; i++) { + quicklistEntry entry; + quicklistIndex(ql, 250, &entry); + quicklistInsertBefore(ql, &entry, genstr("abc", i), 32); + } + if (f == 32) + ql_verify(ql, 25, 750, 32, 20); + quicklistRelease(ql); + } + } - TEST("delete negative 1 from 500 list") { - quicklist *ql = quicklistCreate(); - for (int i = 0; i < 500; i++) - quicklistPushTail(ql, F, genstr("hello", i + 1), 32); - ql_verify(ql, 16, 500, 32, 20); - quicklistDelRange(ql, -1, 1); - ql_verify(ql, 16, 499, 32, 19); - quicklistRelease(ql); - } + for (int f = optimize_start; f < 1024; f++) { + TEST_DESC("insert [after] 250 new in middle of 500 elements at " + "fill %d at compress %d", + f, options[_i]) { + quicklist *ql = quicklistNew(f, options[_i]); + for (int i = 0; i < 500; i++) + quicklistPushHead(ql, genstr("hello", i), 32); + for (int i = 0; i < 250; i++) { + quicklistEntry entry; + quicklistIndex(ql, 250, &entry); + quicklistInsertAfter(ql, &entry, genstr("abc", i), 32); + } - TEST("delete negative 1 from 500 list with overflow counts") { - quicklist *ql = quicklistCreate(); - for (int i = 0; i < 500; i++) - quicklistPushTail(ql, F, genstr("hello", i + 1), 32); - ql_verify(ql, 16, 500, 32, 20); - quicklistDelRange(ql, -1, 128); - ql_verify(ql, 16, 499, 32, 19); - quicklistRelease(ql); - } + if (ql->count != 750) + ERR("List size not 750, but rather %ld", ql->count); - TEST("delete negative 100 from 500 list") { - quicklist *ql = quicklistCreate(); - for (int i = 0; i < 500; i++) - quicklistPushTail(ql, F, genstr("hello", i + 1), 32); - quicklistDelRange(ql, -100, 100); - ql_verify(ql, 13, 400, 32, 16); - quicklistRelease(ql); - } + if (f == 32) + ql_verify(ql, 26, 750, 20, 32); + quicklistRelease(ql); + } + } - TEST("delete -10 count 5 from 50 list") { - quicklist *ql = quicklistCreate(); - for (int i = 0; i < 50; i++) - quicklistPushTail(ql, F, genstr("hello", i + 1), 32); - ql_verify(ql, 2, 50, 32, 18); - quicklistDelRange(ql, -10, 5); - ql_verify(ql, 2, 45, 32, 13); - quicklistRelease(ql); - } + TEST("duplicate empty list") { + quicklist *ql = quicklistNew(-2, options[_i]); + ql_verify(ql, 0, 0, 0, 0); + quicklist *copy = quicklistDup(ql); + ql_verify(copy, 0, 0, 0, 0); + quicklistRelease(ql); + quicklistRelease(copy); + } - TEST("numbers only list read") { - quicklist *ql = quicklistCreate(); - quicklistPushTail(ql, F, "1111", 4); - quicklistPushTail(ql, F, "2222", 4); - quicklistPushTail(ql, F, "3333", 4); - quicklistPushTail(ql, F, "4444", 4); - ql_verify(ql, 1, 4, 4, 4); - quicklistEntry entry; - quicklistIndex(ql, 0, &entry); - if (entry.longval != 1111) - ERR("Not 1111, %lld", entry.longval); - quicklistIndex(ql, 1, &entry); - if (entry.longval != 2222) - ERR("Not 2222, %lld", entry.longval); - quicklistIndex(ql, 2, &entry); - if (entry.longval != 3333) - ERR("Not 3333, %lld", entry.longval); - quicklistIndex(ql, 3, &entry); - if (entry.longval != 4444) - ERR("Not 4444, %lld", entry.longval); - if (quicklistIndex(ql, 4, &entry)) - ERR("Index past elements: %lld", entry.longval); - quicklistIndex(ql, -1, &entry); - if (entry.longval != 4444) - ERR("Not 4444 (reverse), %lld", entry.longval); - quicklistIndex(ql, -2, &entry); - if (entry.longval != 3333) - ERR("Not 3333 (reverse), %lld", entry.longval); - quicklistIndex(ql, -3, &entry); - if (entry.longval != 2222) - ERR("Not 2222 (reverse), %lld", entry.longval); - quicklistIndex(ql, -4, &entry); - if (entry.longval != 1111) - ERR("Not 1111 (reverse), %lld", entry.longval); - if (quicklistIndex(ql, -5, &entry)) - ERR("Index past elements (reverse), %lld", entry.longval); - quicklistRelease(ql); - } + TEST("duplicate list of 1 element") { + quicklist *ql = quicklistNew(-2, options[_i]); + quicklistPushHead(ql, genstr("hello", 3), 32); + ql_verify(ql, 1, 1, 1, 1); + quicklist *copy = quicklistDup(ql); + ql_verify(copy, 1, 1, 1, 1); + quicklistRelease(ql); + quicklistRelease(copy); + } - TEST("numbers larger list read") { - quicklist *ql = quicklistCreate(); - char num[32]; - long long nums[5000]; - for (int i = 0; i < 5000; i++) { - nums[i] = -5157318210846258176 + i; - int sz = ll2string(num, sizeof(num), nums[i]); - quicklistPushTail(ql, F, num, sz); - } - quicklistPushTail(ql, F, "xxxxxxxxxxxxxxxxxxxx", 20); - quicklistEntry entry; - for (int i = 0; i < 5000; i++) { - quicklistIndex(ql, i, &entry); - if (entry.longval != nums[i]) - ERR("[%d] Not longval %lld but rather %lld", i, nums[i], - entry.longval); - entry.longval = 0xdeadbeef; - } - quicklistIndex(ql, 5000, &entry); - if (strncmp((char *)entry.value, "xxxxxxxxxxxxxxxxxxxx", 20)) - ERR("String val not match: %s", entry.value); - ql_verify(ql, 157, 5001, 32, 9); - quicklistRelease(ql); - } + TEST("duplicate list of 500") { + quicklist *ql = quicklistNew(-2, options[_i]); + quicklistSetFill(ql, 32); + for (int i = 0; i < 500; i++) + quicklistPushHead(ql, genstr("hello", i), 32); + ql_verify(ql, 16, 500, 20, 32); - TEST("numbers larger list read B") { - quicklist *ql = quicklistCreate(); - quicklistPushTail(ql, F, "99", 2); - quicklistPushTail(ql, F, "98", 2); - quicklistPushTail(ql, F, "xxxxxxxxxxxxxxxxxxxx", 20); - quicklistPushTail(ql, F, "96", 2); - quicklistPushTail(ql, F, "95", 2); - quicklistReplaceAtIndex(ql, 1, "foo", 3); - quicklistReplaceAtIndex(ql, -1, "bar", 3); - quicklistRelease(ql); - OK; - } + quicklist *copy = quicklistDup(ql); + ql_verify(copy, 16, 500, 20, 32); + quicklistRelease(ql); + quicklistRelease(copy); + } - for (int f = optimize_start; f < 16; f++) { - TEST_DESC("lrem test at fill %d", f) { - quicklist *ql = quicklistCreate(); - char *words[] = { "abc", "foo", "bar", "foobar", "foobared", - "zap", "bar", "test", "foo" }; - char *result[] = { "abc", "foo", "foobar", "foobared", - "zap", "test", "foo" }; - char *resultB[] = { "abc", "foo", "foobar", - "foobared", "zap", "test" }; - for (int i = 0; i < 9; i++) - quicklistPushTail(ql, f, words[i], strlen(words[i])); - - /* lrem 0 bar */ - quicklistIter *iter = quicklistGetIterator(ql, AL_START_HEAD); - quicklistEntry entry; - int i = 0; - while (quicklistNext(iter, &entry)) { - if (quicklistCompare(entry.zi, (unsigned char *)"bar", 3)) { - quicklistDelEntry(iter, &entry); - } - i++; + for (int f = optimize_start; f < 512; f++) { + TEST_DESC("index 1,200 from 500 list at fill %d at compress %d", f, + options[_i]) { + quicklist *ql = quicklistNew(f, options[_i]); + for (int i = 0; i < 500; i++) + quicklistPushTail(ql, genstr("hello", i + 1), 32); + quicklistEntry entry; + quicklistIndex(ql, 1, &entry); + if (!strcmp((char *)entry.value, "hello2")) + OK; + else + ERR("Value: %s", entry.value); + quicklistIndex(ql, 200, &entry); + if (!strcmp((char *)entry.value, "hello201")) + OK; + else + ERR("Value: %s", entry.value); + quicklistRelease(ql); } - quicklistReleaseIterator(iter); - /* check result of lrem 0 bar */ - iter = quicklistGetIterator(ql, AL_START_HEAD); - i = 0; - int ok = 1; - while (quicklistNext(iter, &entry)) { - /* Result must be: abc, foo, foobar, foobared, zap, test, foo */ - if (strncmp((char *)entry.value, result[i], entry.sz)) { - ERR("No match at position %d, got %.*s instead of %s", i, - entry.sz, entry.value, result[i]); - ok = 0; - } - i++; + TEST_DESC("index -1,-2 from 500 list at fill %d at compress %d", f, + options[_i]) { + quicklist *ql = quicklistNew(f, options[_i]); + for (int i = 0; i < 500; i++) + quicklistPushTail(ql, genstr("hello", i + 1), 32); + quicklistEntry entry; + quicklistIndex(ql, -1, &entry); + if (!strcmp((char *)entry.value, "hello500")) + OK; + else + ERR("Value: %s", entry.value); + quicklistIndex(ql, -2, &entry); + if (!strcmp((char *)entry.value, "hello499")) + OK; + else + ERR("Value: %s", entry.value); + quicklistRelease(ql); } - quicklistReleaseIterator(iter); - quicklistPushTail(ql, f, "foo", 3); - - /* lrem -2 foo */ - iter = quicklistGetIterator(ql, AL_START_TAIL); - i = 0; - int del = 2; - while (quicklistNext(iter, &entry)) { - if (quicklistCompare(entry.zi, (unsigned char *)"foo", 3)) { - quicklistDelEntry(iter, &entry); - del--; - } - if (!del) - break; - i++; + TEST_DESC("index -100 from 500 list at fill %d at compress %d", f, + options[_i]) { + quicklist *ql = quicklistNew(f, options[_i]); + for (int i = 0; i < 500; i++) + quicklistPushTail(ql, genstr("hello", i + 1), 32); + quicklistEntry entry; + quicklistIndex(ql, -100, &entry); + if (!strcmp((char *)entry.value, "hello401")) + OK; + else + ERR("Value: %s", entry.value); + quicklistRelease(ql); } - quicklistReleaseIterator(iter); - /* check result of lrem -2 foo */ - /* (we're ignoring the '2' part and still deleting all foo because - * we only have two foo) */ - iter = quicklistGetIterator(ql, AL_START_TAIL); - i = 0; - size_t resB = sizeof(resultB) / sizeof(*resultB); - while (quicklistNext(iter, &entry)) { - /* Result must be: abc, foo, foobar, foobared, zap, test, foo */ - if (strncmp((char *)entry.value, resultB[resB - 1 - i], - entry.sz)) { - ERR("No match at position %d, got %.*s instead of %s", i, - entry.sz, entry.value, resultB[resB - 1 - i]); - ok = 0; - } - i++; + TEST_DESC("index too big +1 from 50 list at fill %d at compress %d", + f, options[_i]) { + quicklist *ql = quicklistNew(f, options[_i]); + for (int i = 0; i < 50; i++) + quicklistPushTail(ql, genstr("hello", i + 1), 32); + quicklistEntry entry; + if (quicklistIndex(ql, 50, &entry)) + ERR("Index found at 50 with 50 list: %.*s", entry.sz, + entry.value); + else + OK; + quicklistRelease(ql); } + } - quicklistReleaseIterator(iter); - /* final result of all tests */ - if (ok) - OK; + TEST("delete range empty list") { + quicklist *ql = quicklistNew(-2, options[_i]); + quicklistDelRange(ql, 5, 20); + ql_verify(ql, 0, 0, 0, 0); quicklistRelease(ql); } - } - for (int f = optimize_start; f < 16; f++) { - TEST_DESC("iterate reverse + delete at fill %d", f) { - quicklist *ql = quicklistCreate(); - quicklistPushTail(ql, f, "abc", 3); - quicklistPushTail(ql, f, "def", 3); - quicklistPushTail(ql, f, "hij", 3); - quicklistPushTail(ql, f, "jkl", 3); - quicklistPushTail(ql, f, "oop", 3); + TEST("delete range of entire node in list of one node") { + quicklist *ql = quicklistNew(-2, options[_i]); + for (int i = 0; i < 32; i++) + quicklistPushHead(ql, genstr("hello", i), 32); + ql_verify(ql, 1, 32, 32, 32); + quicklistDelRange(ql, 0, 32); + ql_verify(ql, 0, 0, 0, 0); + quicklistRelease(ql); + } - quicklistEntry entry; - quicklistIter *iter = quicklistGetIterator(ql, AL_START_TAIL); - int i = 0; - while (quicklistNext(iter, &entry)) { - if (quicklistCompare(entry.zi, (unsigned char *)"hij", 3)) { - quicklistDelEntry(iter, &entry); - } - i++; - } - quicklistReleaseIterator(iter); + TEST("delete range of entire node with overflow counts") { + quicklist *ql = quicklistNew(-2, options[_i]); + for (int i = 0; i < 32; i++) + quicklistPushHead(ql, genstr("hello", i), 32); + ql_verify(ql, 1, 32, 32, 32); + quicklistDelRange(ql, 0, 128); + ql_verify(ql, 0, 0, 0, 0); + quicklistRelease(ql); + } - if (i != 5) - ERR("Didn't iterate 5 times, iterated %d times.", i); + TEST("delete middle 100 of 500 list") { + quicklist *ql = quicklistNew(-2, options[_i]); + quicklistSetFill(ql, 32); + for (int i = 0; i < 500; i++) + quicklistPushTail(ql, genstr("hello", i + 1), 32); + ql_verify(ql, 16, 500, 32, 20); + quicklistDelRange(ql, 200, 100); + ql_verify(ql, 14, 400, 32, 20); + quicklistRelease(ql); + } - /* Check results after deletion of "hij" */ - iter = quicklistGetIterator(ql, AL_START_HEAD); - i = 0; - char *vals[] = { "abc", "def", "jkl", "oop" }; - while (quicklistNext(iter, &entry)) { - if (!quicklistCompare(entry.zi, (unsigned char *)vals[i], 3)) { - ERR("Value at %d didn't match %s\n", i, vals[i]); - } - i++; - } - quicklistReleaseIterator(iter); + TEST("delete negative 1 from 500 list") { + quicklist *ql = quicklistNew(-2, options[_i]); + quicklistSetFill(ql, 32); + for (int i = 0; i < 500; i++) + quicklistPushTail(ql, genstr("hello", i + 1), 32); + ql_verify(ql, 16, 500, 32, 20); + quicklistDelRange(ql, -1, 1); + ql_verify(ql, 16, 499, 32, 19); quicklistRelease(ql); } - } - for (int f = optimize_start; f < 800; f++) { - TEST_DESC("iterator at index test at fill %d", f) { - quicklist *ql = quicklistCreate(); - char num[32]; - long long nums[5000]; - for (int i = 0; i < 760; i++) { - nums[i] = -5157318210846258176 + i; - int sz = ll2string(num, sizeof(num), nums[i]); - quicklistPushTail(ql, f, num, sz); - } + TEST("delete negative 1 from 500 list with overflow counts") { + quicklist *ql = quicklistNew(-2, options[_i]); + quicklistSetFill(ql, 32); + for (int i = 0; i < 500; i++) + quicklistPushTail(ql, genstr("hello", i + 1), 32); + ql_verify(ql, 16, 500, 32, 20); + quicklistDelRange(ql, -1, 128); + ql_verify(ql, 16, 499, 32, 19); + quicklistRelease(ql); + } + + TEST("delete negative 100 from 500 list") { + quicklist *ql = quicklistNew(-2, options[_i]); + quicklistSetFill(ql, 32); + for (int i = 0; i < 500; i++) + quicklistPushTail(ql, genstr("hello", i + 1), 32); + quicklistDelRange(ql, -100, 100); + ql_verify(ql, 13, 400, 32, 16); + quicklistRelease(ql); + } + TEST("delete -10 count 5 from 50 list") { + quicklist *ql = quicklistNew(-2, options[_i]); + quicklistSetFill(ql, 32); + for (int i = 0; i < 50; i++) + quicklistPushTail(ql, genstr("hello", i + 1), 32); + ql_verify(ql, 2, 50, 32, 18); + quicklistDelRange(ql, -10, 5); + ql_verify(ql, 2, 45, 32, 13); + quicklistRelease(ql); + } + + TEST("numbers only list read") { + quicklist *ql = quicklistNew(-2, options[_i]); + quicklistPushTail(ql, "1111", 4); + quicklistPushTail(ql, "2222", 4); + quicklistPushTail(ql, "3333", 4); + quicklistPushTail(ql, "4444", 4); + ql_verify(ql, 1, 4, 4, 4); quicklistEntry entry; - quicklistIter *iter = - quicklistGetIteratorAtIdx(ql, AL_START_HEAD, 437); - int i = 437; - while (quicklistNext(iter, &entry)) { - if (entry.longval != nums[i]) - ERR("Expected %lld, but got %lld", entry.longval, nums[i]); - i++; - } - quicklistReleaseIterator(iter); + quicklistIndex(ql, 0, &entry); + if (entry.longval != 1111) + ERR("Not 1111, %lld", entry.longval); + quicklistIndex(ql, 1, &entry); + if (entry.longval != 2222) + ERR("Not 2222, %lld", entry.longval); + quicklistIndex(ql, 2, &entry); + if (entry.longval != 3333) + ERR("Not 3333, %lld", entry.longval); + quicklistIndex(ql, 3, &entry); + if (entry.longval != 4444) + ERR("Not 4444, %lld", entry.longval); + if (quicklistIndex(ql, 4, &entry)) + ERR("Index past elements: %lld", entry.longval); + quicklistIndex(ql, -1, &entry); + if (entry.longval != 4444) + ERR("Not 4444 (reverse), %lld", entry.longval); + quicklistIndex(ql, -2, &entry); + if (entry.longval != 3333) + ERR("Not 3333 (reverse), %lld", entry.longval); + quicklistIndex(ql, -3, &entry); + if (entry.longval != 2222) + ERR("Not 2222 (reverse), %lld", entry.longval); + quicklistIndex(ql, -4, &entry); + if (entry.longval != 1111) + ERR("Not 1111 (reverse), %lld", entry.longval); + if (quicklistIndex(ql, -5, &entry)) + ERR("Index past elements (reverse), %lld", entry.longval); quicklistRelease(ql); } - } - for (int f = optimize_start; f < 40; f++) { - TEST_DESC("ltrim test A at fill %d", f) { - quicklist *ql = quicklistCreate(); + TEST("numbers larger list read") { + quicklist *ql = quicklistNew(-2, options[_i]); + quicklistSetFill(ql, 32); char num[32]; long long nums[5000]; - for (int i = 0; i < 32; i++) { + for (int i = 0; i < 5000; i++) { nums[i] = -5157318210846258176 + i; int sz = ll2string(num, sizeof(num), nums[i]); - quicklistPushTail(ql, f, num, sz); + quicklistPushTail(ql, num, sz); } - if (f == 32) - ql_verify(ql, 1, 32, 32, 32); - /* ltrim 25 53 (keep [25,32] inclusive = 7 remaining) */ - quicklistDelRange(ql, 0, 25); - quicklistDelRange(ql, 0, 0); + quicklistPushTail(ql, "xxxxxxxxxxxxxxxxxxxx", 20); quicklistEntry entry; - for (int i = 0; i < 7; i++) { + for (int i = 0; i < 5000; i++) { quicklistIndex(ql, i, &entry); - if (entry.longval != nums[25 + i]) - ERR("Deleted invalid range! Expected %lld but got %lld", - entry.longval, nums[25 + i]); + if (entry.longval != nums[i]) + ERR("[%d] Not longval %lld but rather %lld", i, nums[i], + entry.longval); + entry.longval = 0xdeadbeef; } - if (f == 32) - ql_verify(ql, 1, 7, 7, 7); + quicklistIndex(ql, 5000, &entry); + if (strncmp((char *)entry.value, "xxxxxxxxxxxxxxxxxxxx", 20)) + ERR("String val not match: %s", entry.value); + ql_verify(ql, 157, 5001, 32, 9); quicklistRelease(ql); } - } - for (int f = optimize_start; f < 40; f++) { - TEST_DESC("ltrim test B at fill %d", f) { - quicklist *ql = quicklistCreate(); - char num[32]; - long long nums[5000]; - for (int i = 0; i < 33; i++) { - nums[i] = i; - int sz = ll2string(num, sizeof(num), nums[i]); - quicklistPushTail(ql, f, num, sz); + TEST("numbers larger list read B") { + quicklist *ql = quicklistNew(-2, options[_i]); + quicklistPushTail(ql, "99", 2); + quicklistPushTail(ql, "98", 2); + quicklistPushTail(ql, "xxxxxxxxxxxxxxxxxxxx", 20); + quicklistPushTail(ql, "96", 2); + quicklistPushTail(ql, "95", 2); + quicklistReplaceAtIndex(ql, 1, "foo", 3); + quicklistReplaceAtIndex(ql, -1, "bar", 3); + quicklistRelease(ql); + OK; + } + + for (int f = optimize_start; f < 16; f++) { + TEST_DESC("lrem test at fill %d at compress %d", f, options[_i]) { + quicklist *ql = quicklistNew(f, options[_i]); + char *words[] = { "abc", "foo", "bar", "foobar", "foobared", + "zap", "bar", "test", "foo" }; + char *result[] = { "abc", "foo", "foobar", "foobared", + "zap", "test", "foo" }; + char *resultB[] = { "abc", "foo", "foobar", + "foobared", "zap", "test" }; + for (int i = 0; i < 9; i++) + quicklistPushTail(ql, words[i], strlen(words[i])); + + /* lrem 0 bar */ + quicklistIter *iter = quicklistGetIterator(ql, AL_START_HEAD); + quicklistEntry entry; + int i = 0; + while (quicklistNext(iter, &entry)) { + if (quicklistCompare(entry.zi, (unsigned char *)"bar", 3)) { + quicklistDelEntry(iter, &entry); + } + i++; + } + quicklistReleaseIterator(iter); + + /* check result of lrem 0 bar */ + iter = quicklistGetIterator(ql, AL_START_HEAD); + i = 0; + int ok = 1; + while (quicklistNext(iter, &entry)) { + /* Result must be: abc, foo, foobar, foobared, zap, test, + * foo */ + if (strncmp((char *)entry.value, result[i], entry.sz)) { + ERR("No match at position %d, got %.*s instead of %s", + i, entry.sz, entry.value, result[i]); + ok = 0; + } + i++; + } + quicklistReleaseIterator(iter); + + quicklistPushTail(ql, "foo", 3); + + /* lrem -2 foo */ + iter = quicklistGetIterator(ql, AL_START_TAIL); + i = 0; + int del = 2; + while (quicklistNext(iter, &entry)) { + if (quicklistCompare(entry.zi, (unsigned char *)"foo", 3)) { + quicklistDelEntry(iter, &entry); + del--; + } + if (!del) + break; + i++; + } + quicklistReleaseIterator(iter); + + /* check result of lrem -2 foo */ + /* (we're ignoring the '2' part and still deleting all foo + * because + * we only have two foo) */ + iter = quicklistGetIterator(ql, AL_START_TAIL); + i = 0; + size_t resB = sizeof(resultB) / sizeof(*resultB); + while (quicklistNext(iter, &entry)) { + /* Result must be: abc, foo, foobar, foobared, zap, test, + * foo */ + if (strncmp((char *)entry.value, resultB[resB - 1 - i], + entry.sz)) { + ERR("No match at position %d, got %.*s instead of %s", + i, entry.sz, entry.value, resultB[resB - 1 - i]); + ok = 0; + } + i++; + } + + quicklistReleaseIterator(iter); + /* final result of all tests */ + if (ok) + OK; + quicklistRelease(ql); } - if (f == 32) - ql_verify(ql, 2, 33, 32, 1); - /* ltrim 5 16 (keep [5,16] inclusive = 12 remaining) */ - quicklistDelRange(ql, 0, 5); - quicklistDelRange(ql, -16, 16); - if (f == 32) - ql_verify(ql, 1, 12, 12, 12); - quicklistEntry entry; - quicklistIndex(ql, 0, &entry); - if (entry.longval != 5) - ERR("A: longval not 5, but %lld", entry.longval); - else - OK; - quicklistIndex(ql, -1, &entry); - if (entry.longval != 16) - ERR("B! got instead: %lld", entry.longval); - else - OK; - quicklistPushTail(ql, f, "bobobob", 7); - quicklistIndex(ql, -1, &entry); - if (strncmp((char *)entry.value, "bobobob", 7)) - ERR("Tail doesn't match bobobob, it's %.*s instead", entry.sz, - entry.value); - for (int i = 0; i < 12; i++) { - quicklistIndex(ql, i, &entry); - if (entry.longval != nums[5 + i]) - ERR("Deleted invalid range! Expected %lld but got %lld", - entry.longval, nums[5 + i]); + } + + for (int f = optimize_start; f < 16; f++) { + TEST_DESC("iterate reverse + delete at fill %d at compress %d", f, + options[_i]) { + quicklist *ql = quicklistNew(f, options[_i]); + quicklistPushTail(ql, "abc", 3); + quicklistPushTail(ql, "def", 3); + quicklistPushTail(ql, "hij", 3); + quicklistPushTail(ql, "jkl", 3); + quicklistPushTail(ql, "oop", 3); + + quicklistEntry entry; + quicklistIter *iter = quicklistGetIterator(ql, AL_START_TAIL); + int i = 0; + while (quicklistNext(iter, &entry)) { + if (quicklistCompare(entry.zi, (unsigned char *)"hij", 3)) { + quicklistDelEntry(iter, &entry); + } + i++; + } + quicklistReleaseIterator(iter); + + if (i != 5) + ERR("Didn't iterate 5 times, iterated %d times.", i); + + /* Check results after deletion of "hij" */ + iter = quicklistGetIterator(ql, AL_START_HEAD); + i = 0; + char *vals[] = { "abc", "def", "jkl", "oop" }; + while (quicklistNext(iter, &entry)) { + if (!quicklistCompare(entry.zi, (unsigned char *)vals[i], + 3)) { + ERR("Value at %d didn't match %s\n", i, vals[i]); + } + i++; + } + quicklistReleaseIterator(iter); + quicklistRelease(ql); } - quicklistRelease(ql); } - } - for (int f = optimize_start; f < 40; f++) { - TEST_DESC("ltrim test C at fill %d", f) { - quicklist *ql = quicklistCreate(); - char num[32]; - long long nums[5000]; - for (int i = 0; i < 33; i++) { - nums[i] = -5157318210846258176 + i; - int sz = ll2string(num, sizeof(num), nums[i]); - quicklistPushTail(ql, f, num, sz); + for (int f = optimize_start; f < 800; f++) { + TEST_DESC("iterator at index test at fill %d at compress %d", f, + options[_i]) { + quicklist *ql = quicklistNew(f, options[_i]); + char num[32]; + long long nums[5000]; + for (int i = 0; i < 760; i++) { + nums[i] = -5157318210846258176 + i; + int sz = ll2string(num, sizeof(num), nums[i]); + quicklistPushTail(ql, num, sz); + } + + quicklistEntry entry; + quicklistIter *iter = + quicklistGetIteratorAtIdx(ql, AL_START_HEAD, 437); + int i = 437; + while (quicklistNext(iter, &entry)) { + if (entry.longval != nums[i]) + ERR("Expected %lld, but got %lld", entry.longval, + nums[i]); + i++; + } + quicklistReleaseIterator(iter); + quicklistRelease(ql); } - if (f == 32) - ql_verify(ql, 2, 33, 32, 1); - /* ltrim 3 3 (keep [3,3] inclusive = 1 remaining) */ - quicklistDelRange(ql, 0, 3); - quicklistDelRange(ql, -29, 4000); /* make sure not loop forever */ - if (f == 32) - ql_verify(ql, 1, 1, 1, 1); - quicklistEntry entry; - quicklistIndex(ql, 0, &entry); - if (entry.longval != -5157318210846258173) - ERROR; - else - OK; - quicklistRelease(ql); } - } - for (int f = optimize_start; f < 40; f++) { - TEST_DESC("ltrim test D at fill %d", f) { - quicklist *ql = quicklistCreate(); - char num[32]; - long long nums[5000]; - for (int i = 0; i < 33; i++) { - nums[i] = -5157318210846258176 + i; - int sz = ll2string(num, sizeof(num), nums[i]); - quicklistPushTail(ql, f, num, sz); + for (int f = optimize_start; f < 40; f++) { + TEST_DESC("ltrim test A at fill %d at compress %d", f, + options[_i]) { + quicklist *ql = quicklistNew(f, options[_i]); + char num[32]; + long long nums[5000]; + for (int i = 0; i < 32; i++) { + nums[i] = -5157318210846258176 + i; + int sz = ll2string(num, sizeof(num), nums[i]); + quicklistPushTail(ql, num, sz); + } + if (f == 32) + ql_verify(ql, 1, 32, 32, 32); + /* ltrim 25 53 (keep [25,32] inclusive = 7 remaining) */ + quicklistDelRange(ql, 0, 25); + quicklistDelRange(ql, 0, 0); + quicklistEntry entry; + for (int i = 0; i < 7; i++) { + quicklistIndex(ql, i, &entry); + if (entry.longval != nums[25 + i]) + ERR("Deleted invalid range! Expected %lld but got " + "%lld", + entry.longval, nums[25 + i]); + } + if (f == 32) + ql_verify(ql, 1, 7, 7, 7); + quicklistRelease(ql); } - if (f == 32) - ql_verify(ql, 2, 33, 32, 1); - quicklistDelRange(ql, -12, 3); - if (ql->count != 30) - ERR("Didn't delete exactly three elements! Count is: %lu", - ql->count); - quicklistRelease(ql); } - } - for (int f = optimize_start; f < 72; f++) { - TEST_DESC("create quicklist from ziplist at fill %d", f) { - unsigned char *zl = ziplistNew(); - long long nums[32]; - char num[32]; - for (int i = 0; i < 33; i++) { - nums[i] = -5157318210846258176 + i; - int sz = ll2string(num, sizeof(num), nums[i]); - zl = ziplistPush(zl, (unsigned char *)num, sz, ZIPLIST_TAIL); + for (int f = optimize_start; f < 40; f++) { + TEST_DESC("ltrim test B at fill %d at compress %d", f, + options[_i]) { + /* Force-disable compression because our 33 sequential + * integers don't compress and the check always fails. */ + quicklist *ql = quicklistNew(f, QUICKLIST_NOCOMPRESS); + char num[32]; + long long nums[5000]; + for (int i = 0; i < 33; i++) { + nums[i] = i; + int sz = ll2string(num, sizeof(num), nums[i]); + quicklistPushTail(ql, num, sz); + } + if (f == 32) + ql_verify(ql, 2, 33, 32, 1); + /* ltrim 5 16 (keep [5,16] inclusive = 12 remaining) */ + quicklistDelRange(ql, 0, 5); + quicklistDelRange(ql, -16, 16); + if (f == 32) + ql_verify(ql, 1, 12, 12, 12); + quicklistEntry entry; + quicklistIndex(ql, 0, &entry); + if (entry.longval != 5) + ERR("A: longval not 5, but %lld", entry.longval); + else + OK; + quicklistIndex(ql, -1, &entry); + if (entry.longval != 16) + ERR("B! got instead: %lld", entry.longval); + else + OK; + quicklistPushTail(ql, "bobobob", 7); + quicklistIndex(ql, -1, &entry); + if (strncmp((char *)entry.value, "bobobob", 7)) + ERR("Tail doesn't match bobobob, it's %.*s instead", + entry.sz, entry.value); + for (int i = 0; i < 12; i++) { + quicklistIndex(ql, i, &entry); + if (entry.longval != nums[5 + i]) + ERR("Deleted invalid range! Expected %lld but got " + "%lld", + entry.longval, nums[5 + i]); + } + quicklistRelease(ql); } - for (int i = 0; i < 33; i++) { - zl = ziplistPush(zl, (unsigned char *)genstr("hello", i), 32, - ZIPLIST_TAIL); + } + + for (int f = optimize_start; f < 40; f++) { + TEST_DESC("ltrim test C at fill %d at compress %d", f, + options[_i]) { + quicklist *ql = quicklistNew(f, options[_i]); + char num[32]; + long long nums[5000]; + for (int i = 0; i < 33; i++) { + nums[i] = -5157318210846258176 + i; + int sz = ll2string(num, sizeof(num), nums[i]); + quicklistPushTail(ql, num, sz); + } + if (f == 32) + ql_verify(ql, 2, 33, 32, 1); + /* ltrim 3 3 (keep [3,3] inclusive = 1 remaining) */ + quicklistDelRange(ql, 0, 3); + quicklistDelRange(ql, -29, + 4000); /* make sure not loop forever */ + if (f == 32) + ql_verify(ql, 1, 1, 1, 1); + quicklistEntry entry; + quicklistIndex(ql, 0, &entry); + if (entry.longval != -5157318210846258173) + ERROR; + else + OK; + quicklistRelease(ql); + } + } + + for (int f = optimize_start; f < 40; f++) { + TEST_DESC("ltrim test D at fill %d at compress %d", f, + options[_i]) { + quicklist *ql = quicklistNew(f, options[_i]); + char num[32]; + long long nums[5000]; + for (int i = 0; i < 33; i++) { + nums[i] = -5157318210846258176 + i; + int sz = ll2string(num, sizeof(num), nums[i]); + quicklistPushTail(ql, num, sz); + } + if (f == 32) + ql_verify(ql, 2, 33, 32, 1); + quicklistDelRange(ql, -12, 3); + if (ql->count != 30) + ERR("Didn't delete exactly three elements! Count is: %lu", + ql->count); + quicklistRelease(ql); + } + } + + for (int f = optimize_start; f < 72; f++) { + TEST_DESC("create quicklist from ziplist at fill %d at compress %d", + f, options[_i]) { + unsigned char *zl = ziplistNew(); + long long nums[64]; + char num[64]; + for (int i = 0; i < 33; i++) { + nums[i] = -5157318210846258176 + i; + int sz = ll2string(num, sizeof(num), nums[i]); + zl = + ziplistPush(zl, (unsigned char *)num, sz, ZIPLIST_TAIL); + } + for (int i = 0; i < 33; i++) { + zl = ziplistPush(zl, (unsigned char *)genstr("hello", i), + 32, ZIPLIST_TAIL); + } + quicklist *ql = quicklistCreateFromZiplist(f, options[_i], zl); + if (f == 1) + ql_verify(ql, 66, 66, 1, 1); + else if (f == 32) + ql_verify(ql, 3, 66, 32, 2); + else if (f == 66) + ql_verify(ql, 1, 66, 66, 66); + quicklistRelease(ql); + } + } + + long long stop = mstime(); + runtime[_i] = stop - start; + } + + /* Run a longer test of compression depth outside of primary test loop. */ + int list_sizes[] = { 250, 251, 500, 999, 1000 }; + long long start = mstime(); + for (int list = 0; list < (int)(sizeof(list_sizes) / sizeof(*list_sizes)); + list++) { + for (int f = optimize_start; f < 128; f++) { + for (int depth = 1; depth < 40; depth++) { + /* skip over many redundant test cases */ + TEST_DESC("verify specific compression of interior nodes with " + "%d list " + "at fill %d at compress %d", + list_sizes[list], f, depth) { + quicklist *ql = quicklistNew(f, depth); + for (int i = 0; i < list_sizes[list]; i++) { + quicklistPushTail(ql, genstr("hello TAIL", i + 1), 64); + quicklistPushHead(ql, genstr("hello HEAD", i + 1), 64); + } + + quicklistNode *node = ql->head; + unsigned int low_raw = ql->compress; + unsigned int high_raw = ql->len - ql->compress; + + for (unsigned int at = 0; at < ql->len; + at++, node = node->next) { + if (at < low_raw || at >= high_raw) { + if (node->encoding != QUICKLIST_NODE_ENCODING_RAW) { + ERR("Incorrect compression: node %d is " + "compressed at depth %d ((%u, %u); total " + "nodes: %u; size: %u)", + at, depth, low_raw, high_raw, ql->len, + node->sz); + } + } else { + if (node->encoding != QUICKLIST_NODE_ENCODING_LZF) { + ERR("Incorrect non-compression: node %d is NOT " + "compressed at depth %d ((%u, %u); total " + "nodes: %u; size: %u; attempted: %d)", + at, depth, low_raw, high_raw, ql->len, + node->sz, node->attempted_compress); + } + } + } + quicklistRelease(ql); + } } - quicklist *ql = quicklistCreateFromZiplist(f, zl); - if (f == 1) - ql_verify(ql, 66, 66, 1, 1); - else if (f == 32) - ql_verify(ql, 3, 66, 32, 2); - else if (f == 66) - ql_verify(ql, 1, 66, 66, 66); - quicklistRelease(ql); } } + long long stop = mstime(); + + printf("\n"); + for (size_t i = 0; i < option_count; i++) + printf("Test Loop %02d: %0.2f seconds.\n", options[i], + (float)runtime[i] / 1000); + printf("Compressions: %0.2f seconds.\n", (float)(stop - start) / 1000); + printf("\n"); if (!err) printf("ALL TESTS PASSED!\n"); -- cgit v1.2.1