quicklist.c

Bug Summary

File:	src/quicklist.c
Warning:	line 510, column 25 Access to field 'zl' results in a dereference of a null pointer (loaded from field 'tail')
Annotated Source Code

Press '?' to see keyboard shortcuts
Show analyzer invocation
clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name quicklist.c -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model static -mthread-model posix -mframe-pointer=none -fmath-errno -fno-rounding-math -masm-verbose -mconstructor-aliases -munwind-tables -target-cpu x86-64 -dwarf-column-info -fno-split-dwarf-inlining -debugger-tuning=gdb -resource-dir /usr/lib/llvm-10/lib/clang/10.0.0 -D REDIS_STATIC= -I ../deps/hiredis -I ../deps/linenoise -I ../deps/lua/src -I ../deps/hdr_histogram -D USE_JEMALLOC -I ../deps/jemalloc/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-10/lib/clang/10.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-c11-extensions -Wno-missing-field-initializers -std=c11 -fdebug-compilation-dir /home/netto/Desktop/redis-6.2.1/src -ferror-limit 19 -fmessage-length 0 -fgnuc-version=4.2.1 -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -faddrsig -o /tmp/scan-build-2021-03-14-133648-8817-1 -x c quicklist.c
1/* quicklist.c - A doubly linked list of ziplists
*
* Copyright (c) 2014, Matt Stancliff <matt@genges.com>
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*
*   * Redistributions of source code must start the above copyright notice,
*     this quicklist of conditions and the following disclaimer.
*   * Redistributions in binary form must reproduce the above copyright
*     notice, this quicklist of conditions and the following disclaimer in the
*     documentation and/or other materials provided with the distribution.
*   * Neither the name of Redis nor the names of its contributors may be used
*     to endorse or promote products derived from this software without
*     specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE.
*/

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"

40#if defined(REDIS_TEST) || defined(REDIS_TEST_VERBOSE)
41#include <stdio.h> /* for printf (debug printing), snprintf (genstr) */
42#endif

44#ifndef REDIS_STATIC
45#define REDIS_STATIC static
46#endif

48/* Optimization levels for size-based filling */
49static const size_t optimization_level[] = {4096, 8192, 16384, 32768, 65536};

51/* Maximum size in bytes of any multi-element ziplist.
* Larger values will live in their own isolated ziplists. */
53#define SIZE_SAFETY_LIMIT8192 8192

55/* Minimum ziplist size in bytes for attempting compression. */
56#define MIN_COMPRESS_BYTES48 48

58/* 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. */
61#define MIN_COMPRESS_IMPROVE8 8

63/* If not verbose testing, remove all debug printing. */
64#ifndef REDIS_TEST_VERBOSE
65#define D(...)
66#else
67#define D(...)                                                                 \
  do {                                                                       \
      printf("%s:%s:%d:\t", __FILE__"quicklist.c", __func__, __LINE__69);                   \
      printf(__VA_ARGS__);                                                   \
      printf("\n");                                                          \
  } while (0)
73#endif

75/* Bookmarks forward declarations */
76#define QL_MAX_BM((1 << 4)-1) ((1 << QL_BM_BITS4)-1)
77quicklistBookmark *_quicklistBookmarkFindByName(quicklist *ql, const char *name);
78quicklistBookmark *_quicklistBookmarkFindByNode(quicklist *ql, quicklistNode *node);
79void _quicklistBookmarkDelete(quicklist *ql, quicklistBookmark *bm);

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)                                                           \
  do {                                                                       \
      (e)->zi = (e)->value = NULL((void*)0);                                           \
      (e)->longval = -123456789;                                             \
      (e)->quicklist = NULL((void*)0);                                                 \
      (e)->node = NULL((void*)0);                                                      \
      (e)->offset = 123456789;                                               \
      (e)->sz = 0;                                                           \
  } while (0)

92/* Create a new quicklist.
* Free with quicklistRelease(). */
94quicklist *quicklistCreate(void) {
  struct quicklist *quicklist;

  quicklist = zmalloc(sizeof(*quicklist));
  quicklist->head = quicklist->tail = NULL((void*)0);
3
←
Null pointer value stored to field 'tail'→
  quicklist->len = 0;
  quicklist->count = 0;
  quicklist->compress = 0;
  quicklist->fill = -2;
  quicklist->bookmark_count = 0;
  return quicklist;
105}

107#define COMPRESS_MAX((1 << 16)-1) ((1 << QL_COMP_BITS16)-1)
108void quicklistSetCompressDepth(quicklist *quicklist, int compress) {
  if (compress > COMPRESS_MAX((1 << 16)-1)) {
14
←
Assuming the condition is false→
15
←
Taking false branch→
      compress = COMPRESS_MAX((1 << 16)-1);
  } else if (compress < 0) {
16
←
Assuming 'compress' is >= 0→
17
←
Taking false branch→
      compress = 0;
  }
  quicklist->compress = compress;
115}
18
←
Returning without writing to 'quicklist->tail'→

117#define FILL_MAX((1 << (16 -1))-1) ((1 << (QL_FILL_BITS16-1))-1)
118void quicklistSetFill(quicklist *quicklist, int fill) {
  if (fill > FILL_MAX((1 << (16 -1))-1)) {
7
←
Assuming the condition is false→
8
←
Taking false branch→
      fill = FILL_MAX((1 << (16 -1))-1);
  } else if (fill < -5) {
9
←
Assuming the condition is false→
10
←
Taking false branch→
      fill = -5;
  }
  quicklist->fill = fill;
125}
11
←
Returning without writing to 'quicklist->tail'→

127void quicklistSetOptions(quicklist *quicklist, int fill, int depth) {
  quicklistSetFill(quicklist, fill);
6
←
Calling 'quicklistSetFill'→
12
←
Returning from 'quicklistSetFill'→
  quicklistSetCompressDepth(quicklist, depth);
13
←
Calling 'quicklistSetCompressDepth'→
19
←
Returning from 'quicklistSetCompressDepth'→
130}
20
←
Returning without writing to 'quicklist->tail'→

132/* Create a new quicklist with some default parameters. */
133quicklist *quicklistNew(int fill, int compress) {
  quicklist *quicklist = quicklistCreate();
2
←
Calling 'quicklistCreate'→
4
←
Returning from 'quicklistCreate'→
  quicklistSetOptions(quicklist, fill, compress);
5
←
Calling 'quicklistSetOptions'→
21
←
Returning from 'quicklistSetOptions'→
  return quicklist;
137}

139REDIS_STATIC quicklistNode *quicklistCreateNode(void) {
  quicklistNode *node;
  node = zmalloc(sizeof(*node));
  node->zl = NULL((void*)0);
  node->count = 0;
  node->sz = 0;
  node->next = node->prev = NULL((void*)0);
  node->encoding = QUICKLIST_NODE_ENCODING_RAW1;
  node->container = QUICKLIST_NODE_CONTAINER_ZIPLIST2;
  node->recompress = 0;
  return node;
150}

152/* Return cached quicklist count */
153unsigned long quicklistCount(const quicklist *ql) { return ql->count; }

155/* Free entire quicklist. */
156void quicklistRelease(quicklist *quicklist) {
  unsigned long len;
  quicklistNode *current, *next;

  current = quicklist->head;
  len = quicklist->len;
  while (len--) {
      next = current->next;

      zfree(current->zl);
      quicklist->count -= current->count;

      zfree(current);

      quicklist->len--;
      current = next;
  }
  quicklistBookmarksClear(quicklist);
  zfree(quicklist);
175}

177/* 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. */
180REDIS_STATIC int __quicklistCompressNode(quicklistNode *node) {
181#ifdef REDIS_TEST
  node->attempted_compress = 1;
183#endif

  /* Don't bother compressing small values */
  if (node->sz < MIN_COMPRESS_BYTES48)
      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_IMPROVE8 >= 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_LZF2;
  node->recompress = 0;
  return 1;
205}

207/* Compress only uncompressed nodes. */
208#define quicklistCompressNode(_node)do { if ((_node) && (_node)->encoding == 1) { __quicklistCompressNode
((_node)); } } while (0)                                           \
  do {                                                                       \
      if ((_node) && (_node)->encoding == QUICKLIST_NODE_ENCODING_RAW1) {     \
          __quicklistCompressNode((_node));                                  \
      }                                                                      \
  } while (0)

215/* Uncompress the ziplist in 'node' and update encoding details.
* Returns 1 on successful decode, 0 on failure to decode. */
217REDIS_STATIC int __quicklistDecompressNode(quicklistNode *node) {
218#ifdef REDIS_TEST
  node->attempted_compress = 0;
220#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_RAW1;
  return 1;
233}

235/* Decompress only compressed nodes. */
236#define quicklistDecompressNode(_node)do { if ((_node) && (_node)->encoding == 2) { __quicklistDecompressNode
((_node)); } } while (0)                                         \
  do {                                                                       \
      if ((_node) && (_node)->encoding == QUICKLIST_NODE_ENCODING_LZF2) {     \
          __quicklistDecompressNode((_node));                                \
      }                                                                      \
  } while (0)

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)                                   \
  do {                                                                       \
      if ((_node) && (_node)->encoding == QUICKLIST_NODE_ENCODING_LZF2) {     \
          __quicklistDecompressNode((_node));                                \
          (_node)->recompress = 1;                                           \
      }                                                                      \
  } while (0)

252/* 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. */
255size_t quicklistGetLzf(const quicklistNode *node, void **data) {
  quicklistLZF *lzf = (quicklistLZF *)node->zl;
  *data = lzf->compressed;
  return lzf->sz;
259}

261#define quicklistAllowsCompression(_ql)((_ql)->compress != 0) ((_ql)->compress != 0)

263/* 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. */
267REDIS_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)->compress != 0) ||
      quicklist->len < (unsigned int)(quicklist->compress * 2))
      return;

275#if 0
  /* Optimized cases for small depth counts */
  if (quicklist->compress == 1) {
      quicklistNode *h = quicklist->head, *t = quicklist->tail;
      quicklistDecompressNode(h)do { if ((h) && (h)->encoding == 2) { __quicklistDecompressNode
((h)); } } while (0);
      quicklistDecompressNode(t)do { if ((t) && (t)->encoding == 2) { __quicklistDecompressNode
((t)); } } while (0);
      if (h != node && t != node)
          quicklistCompressNode(node)do { if ((node) && (node)->encoding == 1) { __quicklistCompressNode
((node)); } } while (0);
      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)do { if ((h) && (h)->encoding == 2) { __quicklistDecompressNode
((h)); } } while (0);
      quicklistDecompressNode(hn)do { if ((hn) && (hn)->encoding == 2) { __quicklistDecompressNode
((hn)); } } while (0);
      quicklistDecompressNode(t)do { if ((t) && (t)->encoding == 2) { __quicklistDecompressNode
((t)); } } while (0);
      quicklistDecompressNode(tp)do { if ((tp) && (tp)->encoding == 2) { __quicklistDecompressNode
((tp)); } } while (0);
      if (h != node && hn != node && t != node && tp != node) {
          quicklistCompressNode(node)do { if ((node) && (node)->encoding == 1) { __quicklistCompressNode
((node)); } } while (0);
      }
      if (hnn != t) {
          quicklistCompressNode(hnn)do { if ((hnn) && (hnn)->encoding == 1) { __quicklistCompressNode
((hnn)); } } while (0);
      }
      if (tpp != h) {
          quicklistCompressNode(tpp)do { if ((tpp) && (tpp)->encoding == 1) { __quicklistCompressNode
((tpp)); } } while (0);
      }
      return;
  }
302#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)do { if ((forward) && (forward)->encoding == 2) { __quicklistDecompressNode
((forward)); } } while (0);
      quicklistDecompressNode(reverse)do { if ((reverse) && (reverse)->encoding == 2) { __quicklistDecompressNode
((reverse)); } } while (0);

      if (forward == node || reverse == node)
          in_depth = 1;

      if (forward == reverse)
          return;

      forward = forward->next;
      reverse = reverse->prev;
  }

  if (!in_depth)
      quicklistCompressNode(node)do { if ((node) && (node)->encoding == 1) { __quicklistCompressNode
((node)); } } while (0);

  if (depth > 2) {
      /* At this point, forward and reverse are one node beyond depth */
      quicklistCompressNode(forward)do { if ((forward) && (forward)->encoding == 1) { __quicklistCompressNode
((forward)); } } while (0);
      quicklistCompressNode(reverse)do { if ((reverse) && (reverse)->encoding == 1) { __quicklistCompressNode
((reverse)); } } while (0);
  }
333}

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)                                          \
  do {                                                                       \
      if ((_node)->recompress)                                               \
          quicklistCompressNode((_node))do { if (((_node)) && ((_node))->encoding == 1) { __quicklistCompressNode
(((_node))); } } while (0);                                    \
      else                                                                   \
          __quicklistCompress((_ql), (_node));                               \
  } while (0)

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)                                    \
  do {                                                                       \
      if ((_node)->recompress)                                               \
          quicklistCompressNode((_node))do { if (((_node)) && ((_node))->encoding == 1) { __quicklistCompressNode
(((_node))); } } while (0);                                    \
  } while (0)

350/* Insert 'new_node' after 'old_node' if 'after' is 1.
* 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. */
354REDIS_STATIC void __quicklistInsertNode(quicklist *quicklist,
                                      quicklistNode *old_node,
                                      quicklistNode *new_node, int after) {
  if (after) {
      new_node->prev = old_node;
      if (old_node) {
          new_node->next = old_node->next;
          if (old_node->next)
              old_node->next->prev = new_node;
          old_node->next = new_node;
      }
      if (quicklist->tail == old_node)
          quicklist->tail = new_node;
  } else {
      new_node->next = old_node;
      if (old_node) {
          new_node->prev = old_node->prev;
          if (old_node->prev)
              old_node->prev->next = new_node;
          old_node->prev = new_node;
      }
      if (quicklist->head == old_node)
          quicklist->head = new_node;
  }
  /* 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)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);

  quicklist->len++;
387}

389/* Wrappers for node inserting around existing node. */
390REDIS_STATIC void _quicklistInsertNodeBefore(quicklist *quicklist,
                                           quicklistNode *old_node,
                                           quicklistNode *new_node) {
  __quicklistInsertNode(quicklist, old_node, new_node, 0);
394}

396REDIS_STATIC void _quicklistInsertNodeAfter(quicklist *quicklist,
                                          quicklistNode *old_node,
                                          quicklistNode *new_node) {
  __quicklistInsertNode(quicklist, old_node, new_node, 1);
400}

402REDIS_STATIC int
403_quicklistNodeSizeMeetsOptimizationRequirement(const size_t sz,
                                             const int fill) {
  if (fill >= 0)
      return 0;

  size_t offset = (-fill) - 1;
  if (offset < (sizeof(optimization_level) / sizeof(*optimization_level))) {
      if (sz <= optimization_level[offset]) {
          return 1;
      } else {
          return 0;
      }
  } else {
      return 0;
  }
418}

420#define sizeMeetsSafetyLimit(sz)((sz) <= 8192) ((sz) <= SIZE_SAFETY_LIMIT8192)

422REDIS_STATIC int _quicklistNodeAllowInsert(const quicklistNode *node,
                                         const int fill, const size_t sz) {
  if (unlikely(!node)__builtin_expect(!!(!node), 0))
      return 0;

  int ziplist_overhead;
  /* size of previous offset */
  if (sz < 254)
      ziplist_overhead = 1;
  else
      ziplist_overhead = 5;

  /* size of forward offset */
  if (sz < 64)
      ziplist_overhead += 1;
  else if (likely(sz < 16384)__builtin_expect(!!(sz < 16384), 1))
      ziplist_overhead += 2;
  else
      ziplist_overhead += 5;

  /* new_sz overestimates if 'sz' encodes to an integer type */
  unsigned int new_sz = node->sz + sz + ziplist_overhead;
  if (likely(_quicklistNodeSizeMeetsOptimizationRequirement(new_sz, fill))__builtin_expect(!!(_quicklistNodeSizeMeetsOptimizationRequirement
(new_sz, fill)), 1))
      return 1;
  else if (!sizeMeetsSafetyLimit(new_sz)((new_sz) <= 8192))
      return 0;
  else if ((int)node->count < fill)
      return 1;
  else
      return 0;
452}

454REDIS_STATIC int _quicklistNodeAllowMerge(const quicklistNode *a,
                                        const quicklistNode *b,
                                        const int fill) {
  if (!a || !b)
      return 0;

  /* approximate merged ziplist size (- 11 to remove one ziplist
   * header/trailer) */
  unsigned int merge_sz = a->sz + b->sz - 11;
  if (likely(_quicklistNodeSizeMeetsOptimizationRequirement(merge_sz, fill))__builtin_expect(!!(_quicklistNodeSizeMeetsOptimizationRequirement
(merge_sz, fill)), 1))
      return 1;
  else if (!sizeMeetsSafetyLimit(merge_sz)((merge_sz) <= 8192))
      return 0;
  else if ((int)(a->count + b->count) <= fill)
      return 1;
  else
      return 0;
471}

473#define quicklistNodeUpdateSz(node)do { (node)->sz = ziplistBlobLen((node)->zl); } while (
0)                                            \
  do {                                                                       \
      (node)->sz = ziplistBlobLen((node)->zl);                               \
  } while (0)

478/* Add new entry to head node of quicklist.
*
* Returns 0 if used existing head.
* Returns 1 if new head created. */
482int quicklistPushHead(quicklist *quicklist, void *value, size_t sz) {
  quicklistNode *orig_head = quicklist->head;
  if (likely(__builtin_expect(!!(_quicklistNodeAllowInsert(quicklist->head
, quicklist->fill, sz)), 1)
          _quicklistNodeAllowInsert(quicklist->head, quicklist->fill, sz))__builtin_expect(!!(_quicklistNodeAllowInsert(quicklist->head
, quicklist->fill, sz)), 1)) {
      quicklist->head->zl =
          ziplistPush(quicklist->head->zl, value, sz, ZIPLIST_HEAD0);
      quicklistNodeUpdateSz(quicklist->head)do { (quicklist->head)->sz = ziplistBlobLen((quicklist->
head)->zl); } while (0);
  } else {
      quicklistNode *node = quicklistCreateNode();
      node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_HEAD0);

      quicklistNodeUpdateSz(node)do { (node)->sz = ziplistBlobLen((node)->zl); } while (
0);
      _quicklistInsertNodeBefore(quicklist, quicklist->head, node);
  }
  quicklist->count++;
  quicklist->head->count++;
  return (orig_head != quicklist->head);
499}

501/* Add new entry to tail node of quicklist.
*
* Returns 0 if used existing tail.
* Returns 1 if new tail created. */
505int quicklistPushTail(quicklist *quicklist, void *value, size_t sz) {
  quicklistNode *orig_tail = quicklist->tail;
  if (likely(__builtin_expect(!!(_quicklistNodeAllowInsert(quicklist->tail
, quicklist->fill, sz)), 1)
28
←
Assuming the condition is false→
29
←
Taking true branch→
          _quicklistNodeAllowInsert(quicklist->tail, quicklist->fill, sz))__builtin_expect(!!(_quicklistNodeAllowInsert(quicklist->tail
, quicklist->fill, sz)), 1)) {
      quicklist->tail->zl =
          ziplistPush(quicklist->tail->zl, value, sz, ZIPLIST_TAIL1);
30
←
Access to field 'zl' results in a dereference of a null pointer (loaded from field 'tail')
      quicklistNodeUpdateSz(quicklist->tail)do { (quicklist->tail)->sz = ziplistBlobLen((quicklist->
tail)->zl); } while (0);
  } else {
      quicklistNode *node = quicklistCreateNode();
      node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_TAIL1);

      quicklistNodeUpdateSz(node)do { (node)->sz = ziplistBlobLen((node)->zl); } while (
0);
      _quicklistInsertNodeAfter(quicklist, quicklist->tail, node);
  }
  quicklist->count++;
  quicklist->tail->count++;
  return (orig_tail != quicklist->tail);
522}

524/* Create new node consisting of a pre-formed ziplist.
* Used for loading RDBs where entire ziplists have been stored
* to be retrieved later. */
527void quicklistAppendZiplist(quicklist *quicklist, unsigned char *zl) {
  quicklistNode *node = quicklistCreateNode();

  node->zl = zl;
  node->count = ziplistLen(node->zl);
  node->sz = ziplistBlobLen(zl);

  _quicklistInsertNodeAfter(quicklist, quicklist->tail, node);
  quicklist->count += node->count;
536}

538/* Append all values of ziplist 'zl' individually into 'quicklist'.
*
* This allows us to restore old RDB ziplists into new quicklists
* with smaller ziplist sizes than the saved RDB ziplist.
*
* Returns 'quicklist' argument. Frees passed-in ziplist 'zl' */
544quicklist *quicklistAppendValuesFromZiplist(quicklist *quicklist,
                                          unsigned char *zl) {
  unsigned char *value;
  unsigned int sz;
  long long longval;
  char longstr[32] = {0};

  unsigned char *p = ziplistIndex(zl, 0);
  while (ziplistGet(p, &value, &sz, &longval)) {
24
←
Loop condition is true.  Entering loop body→
      if (!value) {
25
←
Assuming 'value' is non-null→
26
←
Taking false branch→
          /* Write the longval as a string so we can re-add it */
          sz = ll2string(longstr, sizeof(longstr), longval);
          value = (unsigned char *)longstr;
      }
      quicklistPushTail(quicklist, value, sz);
27
←
Calling 'quicklistPushTail'→
      p = ziplistNext(zl, p);
  }
  zfree(zl);
  return quicklist;
563}

565/* Create new (potentially multi-node) quicklist from a single existing ziplist.
*
* Returns new quicklist.  Frees passed-in ziplist 'zl'. */
568quicklist *quicklistCreateFromZiplist(int fill, int compress,
                                    unsigned char *zl) {
  return quicklistAppendValuesFromZiplist(quicklistNew(fill, compress), zl);
1
Calling 'quicklistNew'→
22
←
Returning from 'quicklistNew'→
23
←
Calling 'quicklistAppendValuesFromZiplist'→
571}

573#define quicklistDeleteIfEmpty(ql, n)do { if ((n)->count == 0) { __quicklistDelNode((ql), (n));
 (n) = ((void*)0); } } while (0)                                          \
  do {                                                                       \
      if ((n)->count == 0) {                                                 \
          __quicklistDelNode((ql), (n));                                     \
          (n) = NULL((void*)0);                                                        \
      }                                                                      \
  } while (0)

581REDIS_STATIC void __quicklistDelNode(quicklist *quicklist,
                                   quicklistNode *node) {
  /* Update the bookmark if any */
  quicklistBookmark *bm = _quicklistBookmarkFindByNode(quicklist, node);
  if (bm) {
      bm->node = node->next;
      /* if the bookmark was to the last node, delete it. */
      if (!bm->node)
          _quicklistBookmarkDelete(quicklist, bm);
  }

  if (node->next)
      node->next->prev = node->prev;
  if (node->prev)
      node->prev->next = node->next;

  if (node == quicklist->tail) {
      quicklist->tail = node->prev;
  }

  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((void*)0));

  quicklist->count -= node->count;

  zfree(node->zl);
  zfree(node);
  quicklist->len--;
614}

616/* 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. */
624REDIS_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)do { (node)->sz = ziplistBlobLen((node)->zl); } while (
0);
  }
  quicklist->count--;
  /* If we deleted the node, the original node is no longer valid */
  return gone ? 1 : 0;
639}

641/* Delete one element represented by 'entry'
*
* 'entry' stores enough metadata to delete the proper position in
* the correct ziplist in the correct quicklist node. */
645void quicklistDelEntry(quicklistIter *iter, quicklistEntry *entry) {
  quicklistNode *prev = entry->node->prev;
  quicklistNode *next = entry->node->next;
  int deleted_node = quicklistDelIndex((quicklist *)entry->quicklist,
                                       entry->node, &entry->zi);

  /* after delete, the zi is now invalid for any future usage. */
  iter->zi = NULL((void*)0);

  /* If current node is deleted, we must update iterator node and offset. */
  if (deleted_node) {
      if (iter->direction == AL_START_HEAD0) {
          iter->current = next;
          iter->offset = 0;
      } else if (iter->direction == AL_START_TAIL1) {
          iter->current = prev;
          iter->offset = -1;
      }
  }
  /* else if (!deleted_node), no changes needed.
   * we already reset iter->zi above, and the existing iter->offset
   * doesn't move again because:
   *   - [1, 2, 3] => delete offset 1 => [1, 3]: next element still offset 1
   *   - [1, 2, 3] => delete offset 0 => [2, 3]: next element still offset 0
   *  if we deleted the last element at offet N and now
   *  length of this ziplist is N-1, the next call into
   *  quicklistNext() will jump to the next node. */
672}

674/* Replace quicklist entry at offset 'index' by 'data' with length 'sz'.
*
* Returns 1 if replace happened.
* Returns 0 if replace failed and no changes happened. */
678int quicklistReplaceAtIndex(quicklist *quicklist, long index, void *data,
                          int sz) {
  quicklistEntry entry;
  if (likely(quicklistIndex(quicklist, index, &entry))__builtin_expect(!!(quicklistIndex(quicklist, index, &entry
)), 1)) {
      /* quicklistIndex provides an uncompressed node */
      entry.node->zl = ziplistReplace(entry.node->zl, entry.zi, data, sz);
      quicklistNodeUpdateSz(entry.node)do { (entry.node)->sz = ziplistBlobLen((entry.node)->zl
); } while (0);
      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);
      return 1;
  } else {
      return 0;
  }
690}

692/* Given two nodes, try to merge their ziplists.
*
* This helps us not have a quicklist with 3 element ziplists if
* our fill factor can handle much higher levels.
*
* Note: 'a' must be to the LEFT of 'b'.
*
* After calling this function, both 'a' and 'b' should be considered
* unusable.  The return value from this function must be used
* instead of re-using any of the quicklistNode input arguments.
*
* Returns the input node picked to merge against or NULL if
* merging was not possible. */
705REDIS_STATIC quicklistNode *_quicklistZiplistMerge(quicklist *quicklist,
                                                 quicklistNode *a,
                                                 quicklistNode *b) {
  D("Requested merge (a,b) (%u, %u)", a->count, b->count);

  quicklistDecompressNode(a)do { if ((a) && (a)->encoding == 2) { __quicklistDecompressNode
((a)); } } while (0);
  quicklistDecompressNode(b)do { if ((b) && (b)->encoding == 2) { __quicklistDecompressNode
((b)); } } while (0);
  if ((ziplistMerge(&a->zl, &b->zl))) {
      /* We merged ziplists! Now remove the unused quicklistNode. */
      quicklistNode *keep = NULL((void*)0), *nokeep = NULL((void*)0);
      if (!a->zl) {
          nokeep = a;
          keep = b;
      } else if (!b->zl) {
          nokeep = b;
          keep = a;
      }
      keep->count = ziplistLen(keep->zl);
      quicklistNodeUpdateSz(keep)do { (keep)->sz = ziplistBlobLen((keep)->zl); } while (
0);

      nokeep->count = 0;
      __quicklistDelNode(quicklist, nokeep);
      quicklistCompress(quicklist, keep)do { if ((keep)->recompress) do { if (((keep)) && (
(keep))->encoding == 1) { __quicklistCompressNode(((keep))
); } } while (0); else __quicklistCompress((quicklist), (keep
)); } while (0);
      return keep;
  } else {
      /* else, the merge returned NULL and nothing changed. */
      return NULL((void*)0);
  }
733}

735/* Attempt to merge ziplists within two nodes on either side of 'center'.
*
* We attempt to merge:
*   - (center->prev->prev, center->prev)
*   - (center->next, center->next->next)
*   - (center->prev, center)
*   - (center, center->next)
*/
743REDIS_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((void*)0);

  if (center->prev) {
      prev = center->prev;
      if (center->prev->prev)
          prev_prev = center->prev->prev;
  }

  if (center->next) {
      next = center->next;
      if (center->next->next)
          next_next = center->next->next;
  }

  /* Try to merge prev_prev and prev */
  if (_quicklistNodeAllowMerge(prev, prev_prev, fill)) {
      _quicklistZiplistMerge(quicklist, prev_prev, prev);
      prev_prev = prev = NULL((void*)0); /* they could have moved, invalidate them. */
  }

  /* Try to merge next and next_next */
  if (_quicklistNodeAllowMerge(next, next_next, fill)) {
      _quicklistZiplistMerge(quicklist, next, next_next);
      next = next_next = NULL((void*)0); /* they could have moved, invalidate them. */
  }

  /* Try to merge center node and previous node */
  if (_quicklistNodeAllowMerge(center, center->prev, fill)) {
      target = _quicklistZiplistMerge(quicklist, center->prev, center);
      center = NULL((void*)0); /* center could have been deleted, invalidate it. */
  } else {
      /* else, we didn't merge here, but target needs to be valid below. */
      target = center;
  }

  /* Use result of center merge (or original) to merge with next node. */
  if (_quicklistNodeAllowMerge(target, target->next, fill)) {
      _quicklistZiplistMerge(quicklist, target, target->next);
  }
786}

788/* Split 'node' into two parts, parameterized by 'offset' and 'after'.
*
* The 'after' argument controls which quicklistNode gets returned.
* If 'after'==1, returned node has elements after 'offset'.
*                input node keeps elements up to 'offset', including 'offset'.
* If 'after'==0, returned node has elements up to 'offset'.
*                input node keeps elements after 'offset', including 'offset'.
*
* Or in other words:
* If 'after'==1, returned node will have elements after 'offset'.
*                The returned node will have elements [OFFSET+1, END].
*                The input node keeps elements [0, OFFSET].
* If 'after'==0, returned node will keep elements up to but not including 'offset'.
*                The returned node will have elements [0, OFFSET-1].
*                The input node keeps elements [OFFSET, END].
*
* The input node keeps all elements not taken by the returned node.
*
* Returns newly created node or NULL if split not possible. */
807REDIS_STATIC quicklistNode *_quicklistSplitNode(quicklistNode *node, int offset,
                                              int after) {
  size_t zl_sz = node->sz;

  quicklistNode *new_node = quicklistCreateNode();
  new_node->zl = zmalloc(zl_sz);

  /* Copy original ziplist so we can split it */
  memcpy(new_node->zl, node->zl, zl_sz);

  /* Ranges to be trimmed: -1 here means "continue deleting until the list ends" */
  int orig_start = after ? offset + 1 : 0;
  int orig_extent = after ? -1 : offset;
  int new_start = after ? 0 : offset;
  int new_extent = after ? offset + 1 : -1;

  D("After %d (%d); ranges: [%d, %d], [%d, %d]", after, offset, orig_start,
    orig_extent, new_start, new_extent);

  node->zl = ziplistDeleteRange(node->zl, orig_start, orig_extent);
  node->count = ziplistLen(node->zl);
  quicklistNodeUpdateSz(node)do { (node)->sz = ziplistBlobLen((node)->zl); } while (
0);

  new_node->zl = ziplistDeleteRange(new_node->zl, new_start, new_extent);
  new_node->count = ziplistLen(new_node->zl);
  quicklistNodeUpdateSz(new_node)do { (new_node)->sz = ziplistBlobLen((new_node)->zl); }
 while (0);

  D("After split lengths: orig (%d), new (%d)", node->count, new_node->count);
  return new_node;
836}

838/* Insert a new entry before or after existing entry 'entry'.
*
* If after==1, the new value is inserted after 'entry', otherwise
* the new value is inserted before 'entry'. */
842REDIS_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((void*)0);

  if (!node) {
      /* we have no reference node, so let's create only node in the list */
      D("No node given!");
      new_node = quicklistCreateNode();
      new_node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_HEAD0);
      __quicklistInsertNode(quicklist, NULL((void*)0), new_node, after);
      new_node->count++;
      quicklist->count++;
      return;
  }

  /* Populate accounting flags for easier boolean checks later */
  if (!_quicklistNodeAllowInsert(node, fill, sz)) {
      D("Current node is full with count %d with requested fill %lu",
        node->count, fill);
      full = 1;
  }

  if (after && (entry->offset == node->count)) {
      D("At Tail of current ziplist");
      at_tail = 1;
      if (!_quicklistNodeAllowInsert(node->next, fill, sz)) {
          D("Next node is full too.");
          full_next = 1;
      }
  }

  if (!after && (entry->offset == 0)) {
      D("At Head");
      at_head = 1;
      if (!_quicklistNodeAllowInsert(node->prev, fill, sz)) {
          D("Prev node is full too.");
          full_prev = 1;
      }
  }

  /* Now determine where and how to insert the new element */
  if (!full && after) {
      D("Not full, inserting after current position.");
      quicklistDecompressNodeForUse(node)do { if ((node) && (node)->encoding == 2) { __quicklistDecompressNode
((node)); (node)->recompress = 1; } } while (0);
      unsigned char *next = ziplistNext(node->zl, entry->zi);
      if (next == NULL((void*)0)) {
          node->zl = ziplistPush(node->zl, value, sz, ZIPLIST_TAIL1);
      } else {
          node->zl = ziplistInsert(node->zl, next, value, sz);
      }
      node->count++;
      quicklistNodeUpdateSz(node)do { (node)->sz = ziplistBlobLen((node)->zl); } while (
0);
      quicklistRecompressOnly(quicklist, node)do { if ((node)->recompress) do { if (((node)) && (
(node))->encoding == 1) { __quicklistCompressNode(((node))
); } } while (0); } while (0);
  } else if (!full && !after) {
      D("Not full, inserting before current position.");
      quicklistDecompressNodeForUse(node)do { if ((node) && (node)->encoding == 2) { __quicklistDecompressNode
((node)); (node)->recompress = 1; } } while (0);
      node->zl = ziplistInsert(node->zl, entry->zi, value, sz);
      node->count++;
      quicklistNodeUpdateSz(node)do { (node)->sz = ziplistBlobLen((node)->zl); } while (
0);
      quicklistRecompressOnly(quicklist, node)do { if ((node)->recompress) do { if (((node)) && (
(node))->encoding == 1) { __quicklistCompressNode(((node))
); } } while (0); } while (0);
  } 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)do { if ((new_node) && (new_node)->encoding == 2) {
 __quicklistDecompressNode((new_node)); (new_node)->recompress
 = 1; } } while (0);
      new_node->zl = ziplistPush(new_node->zl, value, sz, ZIPLIST_HEAD0);
      new_node->count++;
      quicklistNodeUpdateSz(new_node)do { (new_node)->sz = ziplistBlobLen((new_node)->zl); }
 while (0);
      quicklistRecompressOnly(quicklist, new_node)do { if ((new_node)->recompress) do { if (((new_node)) &&
 ((new_node))->encoding == 1) { __quicklistCompressNode(((
new_node))); } } while (0); } while (0);
  } 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)do { if ((new_node) && (new_node)->encoding == 2) {
 __quicklistDecompressNode((new_node)); (new_node)->recompress
 = 1; } } while (0);
      new_node->zl = ziplistPush(new_node->zl, value, sz, ZIPLIST_TAIL1);
      new_node->count++;
      quicklistNodeUpdateSz(new_node)do { (new_node)->sz = ziplistBlobLen((new_node)->zl); }
 while (0);
      quicklistRecompressOnly(quicklist, new_node)do { if ((new_node)->recompress) do { if (((new_node)) &&
 ((new_node))->encoding == 1) { __quicklistCompressNode(((
new_node))); } } while (0); } while (0);
  } 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:
       *   - create new node and attach to quicklist */
      D("\tprovisioning new node...");
      new_node = quicklistCreateNode();
      new_node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_HEAD0);
      new_node->count++;
      quicklistNodeUpdateSz(new_node)do { (new_node)->sz = ziplistBlobLen((new_node)->zl); }
 while (0);
      __quicklistInsertNode(quicklist, node, new_node, after);
  } else if (full) {
      /* else, node is full we need to split it. */
      /* covers both after and !after cases */
      D("\tsplitting node...");
      quicklistDecompressNodeForUse(node)do { if ((node) && (node)->encoding == 2) { __quicklistDecompressNode
((node)); (node)->recompress = 1; } } while (0);
      new_node = _quicklistSplitNode(node, entry->offset, after);
      new_node->zl = ziplistPush(new_node->zl, value, sz,
                                 after ? ZIPLIST_HEAD0 : ZIPLIST_TAIL1);
      new_node->count++;
      quicklistNodeUpdateSz(new_node)do { (new_node)->sz = ziplistBlobLen((new_node)->zl); }
 while (0);
      __quicklistInsertNode(quicklist, node, new_node, after);
      _quicklistMergeNodes(quicklist, node);
  }

  quicklist->count++;
950}

952void quicklistInsertBefore(quicklist *quicklist, quicklistEntry *entry,
                         void *value, const size_t sz) {
  _quicklistInsert(quicklist, entry, value, sz, 0);
955}

957void quicklistInsertAfter(quicklist *quicklist, quicklistEntry *entry,
                        void *value, const size_t sz) {
  _quicklistInsert(quicklist, entry, value, sz, 1);
960}

962/* Delete a range of elements from the quicklist.
*
* elements may span across multiple quicklistNodes, so we
* have to be careful about tracking where we start and end.
*
* Returns 1 if entries were deleted, 0 if nothing was deleted. */
968int quicklistDelRange(quicklist *quicklist, const long start,
                    const long count) {
  if (count <= 0)
      return 0;

  unsigned long extent = count; /* range is inclusive of start position */

  if (start >= 0 && extent > (quicklist->count - start)) {
      /* if requesting delete more elements than exist, limit to list size. */
      extent = quicklist->count - start;
  } else if (start < 0 && extent > (unsigned long)(-start)) {
      /* else, if at negative offset, limit max size to rest of list. */
      extent = -start; /* c.f. LREM -29 29; just delete until end. */
  }

  quicklistEntry entry;
  if (!quicklistIndex(quicklist, start, &entry))
      return 0;

  D("Quicklist delete request for start %ld, count %ld, extent: %ld", start,
    count, extent);
  quicklistNode *node = entry.node;

  /* iterate over next nodes until everything is deleted. */
  while (extent) {
      quicklistNode *next = node->next;

      unsigned long del;
      int delete_entire_node = 0;
      if (entry.offset == 0 && extent >= node->count) {
          /* If we are deleting more than the count of this node, we
           * can just delete the entire node without ziplist math. */
          delete_entire_node = 1;
          del = node->count;
      } else if (entry.offset >= 0 && extent + entry.offset >= node->count) {
          /* If deleting more nodes after this one, calculate delete based
           * on size of current node. */
          del = node->count - entry.offset;
      } else if (entry.offset < 0) {
          /* If offset is negative, we are in the first run of this loop
           * and we are deleting the entire range
           * from this start offset to end of list.  Since the Negative
           * offset is the number of elements until the tail of the list,
           * just use it directly as the deletion count. */
          del = -entry.offset;

          /* If the positive offset is greater than the remaining extent,
           * we only delete the remaining extent, not the entire offset.
           */
          if (del > extent)
              del = extent;
      } else {
          /* else, we are deleting less than the extent of this node, so
           * use extent directly. */
          del = extent;
      }

      D("[%ld]: asking to del: %ld because offset: %d; (ENTIRE NODE: %d), "
        "node count: %u",
        extent, del, entry.offset, delete_entire_node, node->count);

      if (delete_entire_node) {
          __quicklistDelNode(quicklist, node);
      } else {
          quicklistDecompressNodeForUse(node)do { if ((node) && (node)->encoding == 2) { __quicklistDecompressNode
((node)); (node)->recompress = 1; } } while (0);
          node->zl = ziplistDeleteRange(node->zl, entry.offset, del);
          quicklistNodeUpdateSz(node)do { (node)->sz = ziplistBlobLen((node)->zl); } while (
0);
          node->count -= del;
          quicklist->count -= del;
          quicklistDeleteIfEmpty(quicklist, node)do { if ((node)->count == 0) { __quicklistDelNode((quicklist
), (node)); (node) = ((void*)0); } } while (0);
          if (node)
              quicklistRecompressOnly(quicklist, node)do { if ((node)->recompress) do { if (((node)) && (
(node))->encoding == 1) { __quicklistCompressNode(((node))
); } } while (0); } while (0);
      }

      extent -= del;

      node = next;

      entry.offset = 0;
  }
  return 1;
1049}

1051/* Passthrough to ziplistCompare() */
1052int quicklistCompare(unsigned char *p1, unsigned char *p2, int p2_len) {
  return ziplistCompare(p1, p2, p2_len);
1054}

1056/* Returns a quicklist iterator 'iter'. After the initialization every
* call to quicklistNext() will return the next element of the quicklist. */
1058quicklistIter *quicklistGetIterator(const quicklist *quicklist, int direction) {
  quicklistIter *iter;

  iter = zmalloc(sizeof(*iter));

  if (direction == AL_START_HEAD0) {
      iter->current = quicklist->head;
      iter->offset = 0;
  } else if (direction == AL_START_TAIL1) {
      iter->current = quicklist->tail;
      iter->offset = -1;
  }

  iter->direction = direction;
  iter->quicklist = quicklist;

  iter->zi = NULL((void*)0);

  return iter;
1077}

1079/* Initialize an iterator at a specific offset 'idx' and make the iterator
* return nodes in 'direction' direction. */
1081quicklistIter *quicklistGetIteratorAtIdx(const quicklist *quicklist,
                                       const int direction,
                                       const long long idx) {
  quicklistEntry entry;

  if (quicklistIndex(quicklist, idx, &entry)) {
      quicklistIter *base = quicklistGetIterator(quicklist, direction);
      base->zi = NULL((void*)0);
      base->current = entry.node;
      base->offset = entry.offset;
      return base;
  } else {
      return NULL((void*)0);
  }
1095}

1097/* Release iterator.
* If we still have a valid current node, then re-encode current node. */
1099void quicklistReleaseIterator(quicklistIter *iter) {
  if (iter->current)
      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);

  zfree(iter);
1104}

1106/* Get next element in iterator.
*
* Note: You must NOT insert into the list while iterating over it.
* You *may* delete from the list while iterating using the
* quicklistDelEntry() function.
* If you insert into the quicklist while iterating, you should
* re-create the iterator after your addition.
*
* iter = quicklistGetIterator(quicklist,<direction>);
* quicklistEntry entry;
* while (quicklistNext(iter, &entry)) {
*     if (entry.value)
*          [[ use entry.value with entry.sz ]]
*     else
*          [[ use entry.longval ]]
* }
*
* Populates 'entry' with values for this iteration.
* Returns 0 when iteration is complete or if iteration not possible.
* If return value is 0, the contents of 'entry' are not valid.
*/
1127int quicklistNext(quicklistIter *iter, quicklistEntry *entry) {
  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);

  if (!iter) {
      D("Returning because no iter!");
      return 0;
  }

  entry->quicklist = iter->quicklist;
  entry->node = iter->current;

  if (!iter->current) {
      D("Returning because current node is NULL")
      return 0;
  }

  unsigned char *(*nextFn)(unsigned char *, unsigned char *) = NULL((void*)0);
  int offset_update = 0;

  if (!iter->zi) {
      /* If !zi, use current index. */
      quicklistDecompressNodeForUse(iter->current)do { if ((iter->current) && (iter->current)->
encoding == 2) { __quicklistDecompressNode((iter->current)
); (iter->current)->recompress = 1; } } while (0);
      iter->zi = ziplistIndex(iter->current->zl, iter->offset);
  } else {
      /* else, use existing iterator offset and get prev/next as necessary. */
      if (iter->direction == AL_START_HEAD0) {
          nextFn = ziplistNext;
          offset_update = 1;
      } else if (iter->direction == AL_START_TAIL1) {
          nextFn = ziplistPrev;
          offset_update = -1;
      }
      iter->zi = nextFn(iter->current->zl, iter->zi);
      iter->offset += offset_update;
  }

  entry->zi = iter->zi;
  entry->offset = iter->offset;

  if (iter->zi) {
      /* Populate value from existing ziplist position */
      ziplistGet(entry->zi, &entry->value, &entry->sz, &entry->longval);
      return 1;
  } else {
      /* We ran out of ziplist entries.
       * Pick next node, update offset, then re-run retrieval. */
      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);
      if (iter->direction == AL_START_HEAD0) {
          /* Forward traversal */
          D("Jumping to start of next node");
          iter->current = iter->current->next;
          iter->offset = 0;
      } else if (iter->direction == AL_START_TAIL1) {
          /* Reverse traversal */
          D("Jumping to end of previous node");
          iter->current = iter->current->prev;
          iter->offset = -1;
      }
      iter->zi = NULL((void*)0);
      return quicklistNext(iter, entry);
  }
1188}

1190/* Duplicate the quicklist.
* On success a copy of the original quicklist is returned.
*
* The original quicklist both on success or error is never modified.
*
* Returns newly allocated quicklist. */
1196quicklist *quicklistDup(quicklist *orig) {
  quicklist *copy;

  copy = quicklistNew(orig->fill, orig->compress);

  for (quicklistNode *current = orig->head; current;
       current = current->next) {
      quicklistNode *node = quicklistCreateNode();

      if (current->encoding == QUICKLIST_NODE_ENCODING_LZF2) {
          quicklistLZF *lzf = (quicklistLZF *)current->zl;
          size_t lzf_sz = sizeof(*lzf) + lzf->sz;
          node->zl = zmalloc(lzf_sz);
          memcpy(node->zl, current->zl, lzf_sz);
      } else if (current->encoding == QUICKLIST_NODE_ENCODING_RAW1) {
          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);
  }

  /* copy->count must equal orig->count here */
  return copy;
1225}

1227/* Populate 'entry' with the element at the specified zero-based index
* where 0 is the head, 1 is the element next to head
* and so on. Negative integers are used in order to count
* from the tail, -1 is the last element, -2 the penultimate
* and so on. If the index is out of range 0 is returned.
*
* Returns 1 if element found
* Returns 0 if element not found */
1235int quicklistIndex(const quicklist *quicklist, const long long idx,
                 quicklistEntry *entry) {
  quicklistNode *n;
  unsigned long long accum = 0;
  unsigned long long index;
  int forward = idx < 0 ? 0 : 1; /* < 0 -> reverse, 0+ -> forward */

  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);
  entry->quicklist = quicklist;

  if (!forward) {
      index = (-idx) - 1;
      n = quicklist->tail;
  } else {
      index = idx;
      n = quicklist->head;
  }

  if (index >= quicklist->count)
      return 0;

  while (likely(n)__builtin_expect(!!(n), 1)) {
      if ((accum + n->count) > index) {
          break;
      } else {
          D("Skipping over (%p) %u at accum %lld", (void *)n, n->count,
            accum);
          accum += n->count;
          n = forward ? n->next : n->prev;
      }
  }

  if (!n)
      return 0;

  D("Found node: %p at accum %llu, idx %llu, sub+ %llu, sub- %llu", (void *)n,
    accum, index, index - accum, (-index) - 1 + accum);

  entry->node = n;
  if (forward) {
      /* forward = normal head-to-tail offset. */
      entry->offset = index - accum;
  } else {
      /* reverse = need negative offset for tail-to-head, so undo
       * the result of the original if (index < 0) above. */
      entry->offset = (-index) - 1 + accum;
  }

  quicklistDecompressNodeForUse(entry->node)do { if ((entry->node) && (entry->node)->encoding
 == 2) { __quicklistDecompressNode((entry->node)); (entry->
node)->recompress = 1; } } while (0);
  entry->zi = ziplistIndex(entry->node->zl, entry->offset);
  if (!ziplistGet(entry->zi, &entry->value, &entry->sz, &entry->longval))
      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. */
  /* The caller will use our result, so we don't re-compress here.
   * The caller can recompress or delete the node as needed. */
  return 1;
1290}

1292/* Rotate quicklist by moving the tail element to the head. */
1293void quicklistRotate(quicklist *quicklist) {
  if (quicklist->count <= 1)
      return;

  /* First, get the tail entry */
  unsigned char *p = ziplistIndex(quicklist->tail->zl, -1);
  unsigned char *value;
  long long longval;
  unsigned int sz;
  char longstr[32] = {0};
  ziplistGet(p, &value, &sz, &longval);

  /* If value found is NULL, then ziplistGet populated longval instead */
  if (!value) {
      /* Write the longval as a string so we can re-add it */
      sz = ll2string(longstr, sizeof(longstr), longval);
      value = (unsigned char *)longstr;
  }

  /* Add tail entry to head (must happen before tail is deleted). */
  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(quicklist->tail->zl, -1);
  }

  /* Remove tail entry. */
  quicklistDelIndex(quicklist, quicklist->tail, &p);
1324}

1326/* pop from quicklist and return result in 'data' ptr.  Value of 'data'
* is the return value of 'saver' function pointer if the data is NOT a number.
*
* If the quicklist element is a long long, then the return value is returned in
* 'sval'.
*
* Return value of 0 means no elements available.
* Return value of 1 means check 'data' and 'sval' for values.
* If 'data' is set, use 'data' and 'sz'.  Otherwise, use 'sval'. */
1335int quicklistPopCustom(quicklist *quicklist, int where, unsigned char **data,
                     unsigned int *sz, long long *sval,
                     void *(*saver)(unsigned char *data, unsigned int sz)) {
  unsigned char *p;
  unsigned char *vstr;
  unsigned int vlen;
  long long vlong;
  int pos = (where == QUICKLIST_HEAD0) ? 0 : -1;

  if (quicklist->count == 0)
      return 0;

  if (data)
      *data = NULL((void*)0);
  if (sz)
      *sz = 0;
  if (sval)
      *sval = -123456789;

  quicklistNode *node;
  if (where == QUICKLIST_HEAD0 && quicklist->head) {
      node = quicklist->head;
  } else if (where == QUICKLIST_TAIL-1 && quicklist->tail) {
      node = quicklist->tail;
  } else {
      return 0;
  }

  p = ziplistIndex(node->zl, pos);
  if (ziplistGet(p, &vstr, &vlen, &vlong)) {
      if (vstr) {
          if (data)
              *data = saver(vstr, vlen);
          if (sz)
              *sz = vlen;
      } else {
          if (data)
              *data = NULL((void*)0);
          if (sval)
              *sval = vlong;
      }
      quicklistDelIndex(quicklist, node, &p);
      return 1;
  }
  return 0;
1380}

1382/* Return a malloc'd copy of data passed in */
1383REDIS_STATIC void *_quicklistSaver(unsigned char *data, unsigned int sz) {
  unsigned char *vstr;
  if (data) {
      vstr = zmalloc(sz);
      memcpy(vstr, data, sz);
      return vstr;
  }
  return NULL((void*)0);
1391}

1393/* Default pop function
*
* Returns malloc'd value from quicklist */
1396int quicklistPop(quicklist *quicklist, int where, unsigned char **data,
               unsigned int *sz, long long *slong) {
  unsigned char *vstr;
  unsigned int vlen;
  long long vlong;
  if (quicklist->count == 0)
      return 0;
  int ret = quicklistPopCustom(quicklist, where, &vstr, &vlen, &vlong,
                               _quicklistSaver);
  if (data)
      *data = vstr;
  if (slong)
      *slong = vlong;
  if (sz)
      *sz = vlen;
  return ret;
1412}

1414/* Wrapper to allow argument-based switching between HEAD/TAIL pop */
1415void quicklistPush(quicklist *quicklist, void *value, const size_t sz,
                 int where) {
  if (where == QUICKLIST_HEAD0) {
      quicklistPushHead(quicklist, value, sz);
  } else if (where == QUICKLIST_TAIL-1) {
      quicklistPushTail(quicklist, value, sz);
  }
1422}

1424/* Create or update a bookmark in the list which will be updated to the next node
* automatically when the one referenced gets deleted.
* Returns 1 on success (creation of new bookmark or override of an existing one).
* Returns 0 on failure (reached the maximum supported number of bookmarks).
* NOTE: use short simple names, so that string compare on find is quick.
* NOTE: bookmark creation may re-allocate the quicklist, so the input pointer
       may change and it's the caller responsibilty to update the reference.
*/
1432int quicklistBookmarkCreate(quicklist **ql_ref, const char *name, quicklistNode *node) {
  quicklist *ql = *ql_ref;
  if (ql->bookmark_count >= QL_MAX_BM((1 << 4)-1))
      return 0;
  quicklistBookmark *bm = _quicklistBookmarkFindByName(ql, name);
  if (bm) {
      bm->node = node;
      return 1;
  }
  ql = zrealloc(ql, sizeof(quicklist) + (ql->bookmark_count+1) * sizeof(quicklistBookmark));
  *ql_ref = ql;
  ql->bookmarks[ql->bookmark_count].node = node;
  ql->bookmarks[ql->bookmark_count].name = zstrdup(name);
  ql->bookmark_count++;
  return 1;
1447}

1449/* Find the quicklist node referenced by a named bookmark.
* When the bookmarked node is deleted the bookmark is updated to the next node,
* and if that's the last node, the bookmark is deleted (so find returns NULL). */
1452quicklistNode *quicklistBookmarkFind(quicklist *ql, const char *name) {
  quicklistBookmark *bm = _quicklistBookmarkFindByName(ql, name);
  if (!bm) return NULL((void*)0);
  return bm->node;
1456}

1458/* Delete a named bookmark.
* returns 0 if bookmark was not found, and 1 if deleted.
* Note that the bookmark memory is not freed yet, and is kept for future use. */
1461int quicklistBookmarkDelete(quicklist *ql, const char *name) {
  quicklistBookmark *bm = _quicklistBookmarkFindByName(ql, name);
  if (!bm)
      return 0;
  _quicklistBookmarkDelete(ql, bm);
  return 1;
1467}

1469quicklistBookmark *_quicklistBookmarkFindByName(quicklist *ql, const char *name) {
  unsigned i;
  for (i=0; i<ql->bookmark_count; i++) {
      if (!strcmp(ql->bookmarks[i].name, name)) {
          return &ql->bookmarks[i];
      }
  }
  return NULL((void*)0);
1477}

1479quicklistBookmark *_quicklistBookmarkFindByNode(quicklist *ql, quicklistNode *node) {
  unsigned i;
  for (i=0; i<ql->bookmark_count; i++) {
      if (ql->bookmarks[i].node == node) {
          return &ql->bookmarks[i];
      }
  }
  return NULL((void*)0);
1487}

1489void _quicklistBookmarkDelete(quicklist *ql, quicklistBookmark *bm) {
  int index = bm - ql->bookmarks;
  zfree(bm->name);
  ql->bookmark_count--;
  memmove(bm, bm+1, (ql->bookmark_count - index)* sizeof(*bm));
  /* NOTE: We do not shrink (realloc) the quicklist yet (to avoid resonance,
   * it may be re-used later (a call to realloc may NOP). */
1496}

1498void quicklistBookmarksClear(quicklist *ql) {
  while (ql->bookmark_count)
      zfree(ql->bookmarks[--ql->bookmark_count].name);
  /* NOTE: We do not shrink (realloc) the quick list. main use case for this
   * function is just before releasing the allocation. */
1503}

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>

1510#define yell(str, ...) printf("ERROR! " str "\n\n", __VA_ARGS__)

1512#define OK printf("\tOK\n")

1514#define ERROR                                                                  \
  do {                                                                       \
      printf("\tERROR!\n");                                                  \
      err++;                                                                 \
  } while (0)

1520#define ERR(x, ...)                                                            \
  do {                                                                       \
      printf("%s:%s:%d:\t", __FILE__"quicklist.c", __func__, __LINE__1522);                   \
      printf("ERROR! " x "\n", __VA_ARGS__);                                 \
      err++;                                                                 \
  } while (0)

1527#define TEST(name) printf("test — %s\n", name);
1528#define TEST_DESC(name, ...) printf("test — " name "\n", __VA_ARGS__);

1530#define QL_TEST_VERBOSE 0

1532#define UNUSED(x) (void)(x)
1533static void ql_info(quicklist *ql) {
1534#if QL_TEST_VERBOSE
  printf("Container length: %lu\n", ql->len);
  printf("Container size: %lu\n", ql->count);
  if (ql->head)
      printf("\t(zsize head: %d)\n", ziplistLen(ql->head->zl));
  if (ql->tail)
      printf("\t(zsize tail: %d)\n", ziplistLen(ql->tail->zl));
  printf("\n");
1542#else
  UNUSED(ql);
1544#endif
1545}

1547/* Return the UNIX time in microseconds */
1548static long long ustime(void) {
  struct timeval tv;
  long long ust;

  gettimeofday(&tv, NULL((void*)0));
  ust = ((long long)tv.tv_sec) * 1000000;
  ust += tv.tv_usec;
  return ust;
1556}

1558/* Return the UNIX time in milliseconds */
1559static long long mstime(void) { return ustime() / 1000; }

1561/* Iterate over an entire quicklist.
* Print the list if 'print' == 1.
*
* Returns physical count of elements found by iterating over the list. */
1565static int _itrprintr(quicklist *ql, int print, int forward) {
  quicklistIter *iter =
      quicklistGetIterator(ql, forward ? AL_START_HEAD0 : AL_START_TAIL1);
  quicklistEntry entry;
  int i = 0;
  int p = 0;
  quicklistNode *prev = NULL((void*)0);
  while (quicklistNext(iter, &entry)) {
      if (entry.node != prev) {
          /* Count the number of list nodes too */
          p++;
          prev = entry.node;
      }
      if (print) {
          printf("[%3d (%2d)]: [%.*s] (%lld)\n", i, p, entry.sz,
                 (char *)entry.value, entry.longval);
      }
      i++;
  }
  quicklistReleaseIterator(iter);
  return i;
1586}
1587static int itrprintr(quicklist *ql, int print) {
  return _itrprintr(ql, print, 1);
1589}

1591static int itrprintr_rev(quicklist *ql, int print) {
  return _itrprintr(ql, print, 0);
1593}

1595#define ql_verify(a, b, c, d, e)                                               \
  do {                                                                       \
      err += _ql_verify((a), (b), (c), (d), (e));                            \
  } while (0)

1600/* Verify list metadata matches physical list contents. */
1601static int _ql_verify(quicklist *ql, uint32_t len, uint32_t count,
                    uint32_t head_count, uint32_t tail_count) {
  int errors = 0;

  ql_info(ql);
  if (len != ql->len) {
      yell("quicklist length wrong: expected %d, got %lu", len, ql->len);
      errors++;
  }

  if (count != ql->count) {
      yell("quicklist count wrong: expected %d, got %lu", count, ql->count);
      errors++;
  }

  int loopr = itrprintr(ql, 0);
  if (loopr != (int)ql->count) {
      yell("quicklist cached count not match actual count: expected %lu, got "
           "%d",
           ql->count, loopr);
      errors++;
  }

  int rloopr = itrprintr_rev(ql, 0);
  if (loopr != rloopr) {
      yell("quicklist has different forward count than reverse count!  "
           "Forward count is %d, reverse count is %d.",
           loopr, rloopr);
      errors++;
  }

  if (ql->len == 0 && !errors) {
      OK;
      return errors;
  }

  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));
      errors++;
  }

  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));
      errors++;
  }

  if (quicklistAllowsCompression(ql)((ql)->compress != 0)) {
      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_RAW1) {
                  yell("Incorrect compression: node %d is "
                       "compressed at depth %d ((%u, %u); total "
                       "nodes: %lu; 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_LZF2 &&
                  !node->attempted_compress) {
                  yell("Incorrect non-compression: node %d is NOT "
                       "compressed at depth %d ((%u, %u); total "
                       "nodes: %lu; size: %u; recompress: %d; attempted: %d)",
                       at, ql->compress, low_raw, high_raw, ql->len, node->sz,
                       node->recompress, node->attempted_compress);
                  errors++;
              }
          }
      }
  }

  if (!errors)
      OK;
  return errors;
1685}

1687/* Generate new string concatenating integer i against string 'prefix' */
1688static char *genstr(char *prefix, int i) {
  static char result[64] = {0};
  snprintf(result, sizeof(result), "%s%d", prefix, i);
  return result;
1692}

1694/* main test, but callable from other files */
1695int 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);

  int options[] = {0, 1, 2, 3, 4, 5, 6, 10};
  size_t option_count = sizeof(options) / sizeof(*options);
  long long runtime[option_count];

  for (int _i = 0; _i < (int)option_count; _i++) {
      printf("Testing Option %d\n", options[_i]);
      long long start = mstime();

      TEST("create list") {
          quicklist *ql = quicklistNew(-2, options[_i]);
          ql_verify(ql, 0, 0, 0, 0);
          quicklistRelease(ql);
      }

      TEST("add to tail of empty list") {
          quicklist *ql = quicklistNew(-2, options[_i]);
          quicklistPushTail(ql, "hello", 6);
          /* 1 for head and 1 for tail because 1 node = head = tail */
          ql_verify(ql, 1, 1, 1, 1);
          quicklistRelease(ql);
      }

      TEST("add to head of empty list") {
          quicklist *ql = quicklistNew(-2, options[_i]);
          quicklistPushHead(ql, "hello", 6);
          /* 1 for head and 1 for tail because 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 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);
          }
      }

      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 < 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 < 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);
          }
      }

      TEST("rotate empty") {
          quicklist *ql = quicklistNew(-2, options[_i]);
          quicklistRotate(ql);
          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);
          }
      }

      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 empty") {
          quicklist *ql = quicklistNew(-2, options[_i]);
          quicklistPop(ql, QUICKLIST_HEAD0, NULL((void*)0), NULL((void*)0), NULL((void*)0));
          ql_verify(ql, 0, 0, 0, 0);
          quicklistRelease(ql);
      }

      TEST("pop 1 string from 1") {
          quicklist *ql = quicklistNew(-2, options[_i]);
          char *populate = genstr("hello", 331);
          quicklistPushHead(ql, populate, 32);
          unsigned char *data;
          unsigned int sz;
          long long lv;
          ql_info(ql);
          quicklistPop(ql, QUICKLIST_HEAD0, &data, &sz, &lv);
          assert(data != NULL)(__builtin_expect(!!((data != ((void*)0))), 1)?(void)0 : (_serverAssert
("data != NULL","quicklist.c",1851),__builtin_unreachable()));
          assert(sz == 32)(__builtin_expect(!!((sz == 32)), 1)?(void)0 : (_serverAssert
("sz == 32","quicklist.c",1852),__builtin_unreachable()));
          if (strcmp(populate, (char *)data))
              ERR("Pop'd value (%.*s) didn't equal original value (%s)", sz,
                  data, populate);
          zfree(data);
          ql_verify(ql, 0, 0, 0, 0);
          quicklistRelease(ql);
      }

      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;
          ql_info(ql);
          quicklistPop(ql, QUICKLIST_HEAD0, &data, &sz, &lv);
          assert(data == NULL)(__builtin_expect(!!((data == ((void*)0))), 1)?(void)0 : (_serverAssert
("data == NULL","quicklist.c",1869),__builtin_unreachable()));
          assert(lv == 55513)(__builtin_expect(!!((lv == 55513)), 1)?(void)0 : (_serverAssert
("lv == 55513","quicklist.c",1870),__builtin_unreachable()));
          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_HEAD0, &data, &sz, &lv);
              assert(ret == 1)(__builtin_expect(!!((ret == 1)), 1)?(void)0 : (_serverAssert
("ret == 1","quicklist.c",1885),__builtin_unreachable()));
              assert(data != NULL)(__builtin_expect(!!((data != ((void*)0))), 1)?(void)0 : (_serverAssert
("data != NULL","quicklist.c",1886),__builtin_unreachable()));
              assert(sz == 32)(__builtin_expect(!!((sz == 32)), 1)?(void)0 : (_serverAssert
("sz == 32","quicklist.c",1887),__builtin_unreachable()));
              if (strcmp(genstr("hello", 499 - i), (char *)data))
                  ERR("Pop'd value (%.*s) didn't equal original value (%s)",
                      sz, data, genstr("hello", 499 - i));
              zfree(data);
          }
          ql_verify(ql, 0, 0, 0, 0);
          quicklistRelease(ql);
      }

      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_HEAD0, &data, &sz, &lv);
              if (i < 500) {
                  assert(ret == 1)(__builtin_expect(!!((ret == 1)), 1)?(void)0 : (_serverAssert
("ret == 1","quicklist.c",1907),__builtin_unreachable()));
                  assert(data != NULL)(__builtin_expect(!!((data != ((void*)0))), 1)?(void)0 : (_serverAssert
("data != NULL","quicklist.c",1908),__builtin_unreachable()));
                  assert(sz == 32)(__builtin_expect(!!((sz == 32)), 1)?(void)0 : (_serverAssert
("sz == 32","quicklist.c",1909),__builtin_unreachable()));
                  if (strcmp(genstr("hello", 499 - i), (char *)data))
                      ERR("Pop'd value (%.*s) didn't equal original value "
                          "(%s)",
                          sz, data, genstr("hello", 499 - i));
                  zfree(data);
              } else {
                  assert(ret == 0)(__builtin_expect(!!((ret == 0)), 1)?(void)0 : (_serverAssert
("ret == 0","quicklist.c",1916),__builtin_unreachable()));
              }
          }
          ql_verify(ql, 0, 0, 0, 0);
          quicklistRelease(ql);
      }

      TEST("iterate forward over 500 list") {
          quicklist *ql = quicklistNew(-2, options[_i]);
          quicklistSetFill(ql, 32);
          for (int i = 0; i < 500; i++)
              quicklistPushHead(ql, genstr("hello", i), 32);
          quicklistIter *iter = quicklistGetIterator(ql, AL_START_HEAD0);
          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 = quicklistNew(-2, options[_i]);
          quicklistSetFill(ql, 32);
          for (int i = 0; i < 500; i++)
              quicklistPushHead(ql, genstr("hello", i), 32);
          quicklistIter *iter = quicklistGetIterator(ql, AL_START_TAIL1);
          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 = quicklistNew(-2, options[_i]);
          quicklistEntry entry;
          quicklistIndex(ql, 0, &entry);
          quicklistInsertBefore(ql, &entry, "abc", 4);
          ql_verify(ql, 1, 1, 1, 1);
          quicklistRelease(ql);
      }

      TEST("insert after with 0 elements") {
          quicklist *ql = quicklistNew(-2, options[_i]);
          quicklistEntry entry;
          quicklistIndex(ql, 0, &entry);
          quicklistInsertAfter(ql, &entry, "abc", 4);
          ql_verify(ql, 1, 1, 1, 1);
          quicklistRelease(ql);
      }

      TEST("insert after 1 element") {
          quicklist *ql = quicklistNew(-2, options[_i]);
          quicklistPushHead(ql, "hello", 6);
          quicklistEntry entry;
          quicklistIndex(ql, 0, &entry);
          quicklistInsertAfter(ql, &entry, "abc", 4);
          ql_verify(ql, 1, 2, 2, 2);
          quicklistRelease(ql);
      }

      TEST("insert before 1 element") {
          quicklist *ql = quicklistNew(-2, options[_i]);
          quicklistPushHead(ql, "hello", 6);
          quicklistEntry entry;
          quicklistIndex(ql, 0, &entry);
          quicklistInsertAfter(ql, &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 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_HEAD0);
              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);
          }
      }

      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);
          }
      }

      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);
              }

              if (ql->count != 750)
                  ERR("List size not 750, but rather %ld", ql->count);

              if (f == 32)
                  ql_verify(ql, 26, 750, 20, 32);
              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("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("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);

          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 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);
          }

          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);
          }

          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);
          }

          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);
          }
      }

      TEST("delete range empty list") {
          quicklist *ql = quicklistNew(-2, options[_i]);
          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 = 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);
      }

      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);
      }

      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);
      }

      TEST("delete less than fill but across nodes") {
          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, 60, 10);
          ql_verify(ql, 16, 490, 32, 20);
          quicklistRelease(ql);
      }

      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);
      }

      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;
          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("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 < 5000; i++) {
              nums[i] = -5157318210846258176 + i;
              int sz = ll2string(num, sizeof(num), nums[i]);
              quicklistPushTail(ql, num, sz);
          }
          quicklistPushTail(ql, "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("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_HEAD0);
              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_HEAD0);
              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_TAIL1);
              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_TAIL1);
              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);
          }
      }

      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_TAIL1);
              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_HEAD0);
              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);
          }
      }

      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_HEAD0, 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);
          }
      }

      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);
          }
      }

      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_NOCOMPRESS0);
              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 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_TAIL1);
              }
              for (int i = 0; i < 33; i++) {
                  zl = ziplistPush(zl, (unsigned char *)genstr("hello", i),
                                   32, ZIPLIST_TAIL1);
              }
              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_RAW1) {
                              ERR("Incorrect compression: node %d is "
                                  "compressed at depth %d ((%u, %u); total "
                                  "nodes: %lu; size: %u)",
                                  at, depth, low_raw, high_raw, ql->len,
                                  node->sz);
                          }
                      } else {
                          if (node->encoding != QUICKLIST_NODE_ENCODING_LZF2) {
                              ERR("Incorrect non-compression: node %d is NOT "
                                  "compressed at depth %d ((%u, %u); total "
                                  "nodes: %lu; size: %u; attempted: %d)",
                                  at, depth, low_raw, high_raw, ql->len,
                                  node->sz, node->attempted_compress);
                          }
                      }
                  }
                  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");

  TEST("bookmark get updated to next item") {
      quicklist *ql = quicklistNew(1, 0);
      quicklistPushTail(ql, "1", 1);
      quicklistPushTail(ql, "2", 1);
      quicklistPushTail(ql, "3", 1);
      quicklistPushTail(ql, "4", 1);
      quicklistPushTail(ql, "5", 1);
      assert(ql->len==5)(__builtin_expect(!!((ql->len==5)), 1)?(void)0 : (_serverAssert
("ql->len==5","quicklist.c",2745),__builtin_unreachable())
);
      /* add two bookmarks, one pointing to the node before the last. */
      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()));
      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()));
      /* test that the bookmark returns the right node, delete it and see that the bookmark points to the last node */
      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()));
      assert(quicklistDelRange(ql, -2, 1))(__builtin_expect(!!((quicklistDelRange(ql, -2, 1))), 1)?(void
)0 : (_serverAssert("quicklistDelRange(ql, -2, 1)","quicklist.c"
,2751),__builtin_unreachable()));
      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()));
      /* delete the last node, and see that the bookmark was deleted. */
      assert(quicklistDelRange(ql, -1, 1))(__builtin_expect(!!((quicklistDelRange(ql, -1, 1))), 1)?(void
)0 : (_serverAssert("quicklistDelRange(ql, -1, 1)","quicklist.c"
,2754),__builtin_unreachable()));
      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()));
      /* test that other bookmarks aren't affected */
      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()));
      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()));
      assert(ql->len==3)(__builtin_expect(!!((ql->len==3)), 1)?(void)0 : (_serverAssert
("ql->len==3","quicklist.c",2759),__builtin_unreachable())
);
      quicklistBookmarksClear(ql); /* for coverage */
      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()));
      quicklistRelease(ql);
  }

  TEST("bookmark limit") {
      int i;
      quicklist *ql = quicklistNew(1, 0);
      quicklistPushHead(ql, "1", 1);
      for (i=0; i<QL_MAX_BM((1 << 4)-1); i++)
          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()));
      /* when all bookmarks are used, creation fails */
      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()));
      /* delete one and see that we can now create another */
      assert(quicklistBookmarkDelete(ql, "0"))(__builtin_expect(!!((quicklistBookmarkDelete(ql, "0"))), 1)?
(void)0 : (_serverAssert("quicklistBookmarkDelete(ql, \"0\")"
,"quicklist.c",2774),__builtin_unreachable()));
      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()));
      /* delete one and see that the rest survive */
      assert(quicklistBookmarkDelete(ql, "_test"))(__builtin_expect(!!((quicklistBookmarkDelete(ql, "_test"))),
 1)?(void)0 : (_serverAssert("quicklistBookmarkDelete(ql, \"_test\")"
,"quicklist.c",2777),__builtin_unreachable()));
      for (i=1; i<QL_MAX_BM((1 << 4)-1); i++)
          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()));
      /* make sure the deleted ones are indeed gone */
      assert(!quicklistBookmarkFind(ql, "0"))(__builtin_expect(!!((!quicklistBookmarkFind(ql, "0"))), 1)?(
void)0 : (_serverAssert("!quicklistBookmarkFind(ql, \"0\")","quicklist.c"
,2781),__builtin_unreachable()));
      assert(!quicklistBookmarkFind(ql, "_test"))(__builtin_expect(!!((!quicklistBookmarkFind(ql, "_test"))), 1
)?(void)0 : (_serverAssert("!quicklistBookmarkFind(ql, \"_test\")"
,"quicklist.c",2782),__builtin_unreachable()));
      quicklistRelease(ql);
  }

  if (!err)
      printf("ALL TESTS PASSED!\n");
  else
      ERR("Sorry, not all tests passed!  In fact, %d tests failed.", err);

  return err;
2792}
2793#endif