#include <string.h> /* for memcpy */

#include "quicklist.h"

#include "zmalloc.h"

#include "ziplist.h"

#include "util.h" /* for ll2string */

#include "lzf.h"

#if defined(REDIS_TEST) || defined(REDIS_TEST_VERBOSE)

#include <stdio.h> /* for printf (debug printing), snprintf (genstr) */

#ifndef REDIS_STATIC

#define REDIS_STATIC static

static const size_t optimization_level[] = {4096, 8192, 16384, 32768, 65536};

#define SIZE_SAFETY_LIMIT 8192

#define MIN_COMPRESS_BYTES 48

#define MIN_COMPRESS_IMPROVE 8

#ifndef REDIS_TEST_VERBOSE

#define D(...)

#define D(...) \

do { \

printf("%s:%s:%d:\t", __FILE__, __FUNCTION__, __LINE__); \

printf(__VA_ARGS__); \

printf("\n"); \

} while (0);

#define initEntry(e) \

do { \

(e)->zi = (e)->value = NULL; \

(e)->longval = -123456789; \

(e)->quicklist = NULL; \

(e)->node = NULL; \

(e)->offset = 123456789; \

(e)->sz = 0; \

} while (0)

#if __GNUC__ >= 3

#define likely(x) __builtin_expect(!!(x), 1)

#define unlikely(x) __builtin_expect(!!(x), 0)

#define likely(x) (x)

#define unlikely(x) (x)

quicklist *quicklistCreate(void) {

struct quicklist *quicklist;

quicklist = zmalloc(sizeof(*quicklist));

quicklist->head = quicklist->tail = NULL;

quicklist->len = 0;

quicklist->count = 0;

quicklist->compress = 0;

quicklist->fill = -2;

return quicklist;

}

#define COMPRESS_MAX (1 << 16)

void quicklistSetCompressDepth(quicklist *quicklist, int compress) {

if (compress > COMPRESS_MAX) {

compress = COMPRESS_MAX;

} else if (compress < 0) {

compress = 0;

}

quicklist->compress = compress;

}

#define FILL_MAX (1 << 15)

void quicklistSetFill(quicklist *quicklist, int fill) {

if (fill > FILL_MAX) {

fill = FILL_MAX;

} else if (fill < -5) {

fill = -5;

}

quicklist->fill = fill;

}

void quicklistSetOptions(quicklist *quicklist, int fill, int depth) {

quicklistSetFill(quicklist, fill);

quicklistSetCompressDepth(quicklist, depth);

}

quicklist *quicklistNew(int fill, int compress) {

quicklist *quicklist = quicklistCreate();

quicklistSetOptions(quicklist, fill, compress);

return quicklist;

}

REDIS_STATIC quicklistNode *quicklistCreateNode(void) {

quicklistNode *node;

node = zmalloc(sizeof(*node));

node->zl = NULL;

node->count = 0;

node->sz = 0;

node->next = node->prev = NULL;

node->encoding = QUICKLIST_NODE_ENCODING_RAW;

node->container = QUICKLIST_NODE_CONTAINER_ZIPLIST;

node->recompress = 0;

return node;

}

unsigned int quicklistCount(const quicklist *ql) { return ql->count; }

void 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;

}

zfree(quicklist);

}

REDIS_STATIC int __quicklistCompressNode(quicklistNode *node) {

#ifdef REDIS_TEST

node->attempted_compress = 1;

/* Don't bother compressing small values */

if (node->sz < MIN_COMPRESS_BYTES)

return 0;

quicklistLZF *lzf = zmalloc(sizeof(*lzf) + node->sz);

/* Cancel if compression fails or doesn't compress small enough */

if (((lzf->sz = lzf_compress(node->zl, node->sz, lzf->compressed,

node->sz)) == 0) ||

lzf->sz + MIN_COMPRESS_IMPROVE >= node->sz) {

/* lzf_compress aborts/rejects compression if value not compressable. */

zfree(lzf);

return 0;

}

lzf = zrealloc(lzf, sizeof(*lzf) + lzf->sz);

zfree(node->zl);

node->zl = (unsigned char *)lzf;

node->encoding = QUICKLIST_NODE_ENCODING_LZF;

node->recompress = 0;

return 1;

}

#define quicklistCompressNode(_node) \

do { \

if ((_node) && (_node)->encoding == QUICKLIST_NODE_ENCODING_RAW) { \

__quicklistCompressNode((_node)); \

} \

} while (0)

REDIS_STATIC int __quicklistDecompressNode(quicklistNode *node) {

#ifdef REDIS_TEST

node->attempted_compress = 0;

void *decompressed = zmalloc(node->sz);

quicklistLZF *lzf = (quicklistLZF *)node->zl;

if (lzf_decompress(lzf->compressed, lzf->sz, decompressed, node->sz) == 0) {

/* Someone requested decompress, but we can't decompress. Not good. */

zfree(decompressed);

return 0;

}

zfree(lzf);

node->zl = decompressed;

node->encoding = QUICKLIST_NODE_ENCODING_RAW;

return 1;

}

#define quicklistDecompressNode(_node) \

do { \

if ((_node) && (_node)->encoding == QUICKLIST_NODE_ENCODING_LZF) { \

__quicklistDecompressNode((_node)); \

} \

} while (0)

#define quicklistDecompressNodeForUse(_node) \

do { \

if ((_node) && (_node)->encoding == QUICKLIST_NODE_ENCODING_LZF) { \

__quicklistDecompressNode((_node)); \

(_node)->recompress = 1; \

} \

} while (0)

size_t quicklistGetLzf(const quicklistNode *node, void **data) {

quicklistLZF *lzf = (quicklistLZF *)node->zl;

*data = lzf->compressed;

return lzf->sz;

}

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

REDIS_STATIC void __quicklistCompress(const quicklist *quicklist,

quicklistNode *node) {

/* If length is less than our compress depth (from both sides),

if (!quicklistAllowsCompression(quicklist) ||

quicklist->len < (unsigned int)(quicklist->compress * 2))

return;

#if 0

/* Optimized cases for small depth counts */

if (quicklist->compress == 1) {

quicklistNode *h = quicklist->head, *t = quicklist->tail;

quicklistDecompressNode(h);

quicklistDecompressNode(t);

if (h != node && t != node)

quicklistCompressNode(node);

return;

} else if (quicklist->compress == 2) {

quicklistNode *h = quicklist->head, *hn = h->next, *hnn = hn->next;

quicklistNode *t = quicklist->tail, *tp = t->prev, *tpp = tp->prev;

quicklistDecompressNode(h);

quicklistDecompressNode(hn);

quicklistDecompressNode(t);

quicklistDecompressNode(tp);

if (h != node && hn != node && t != node && tp != node) {

quicklistCompressNode(node);

}

if (hnn != t) {

quicklistCompressNode(hnn);

}

if (tpp != h) {

quicklistCompressNode(tpp);

}

return;

}

/* Iterate until we reach compress depth for both sides of the list.a

quicklistNode *forward = quicklist->head;

quicklistNode *reverse = quicklist->tail;

int depth = 0;

int in_depth = 0;

while (depth++ < quicklist->compress) {

quicklistDecompressNode(forward);

quicklistDecompressNode(reverse);

if (forward == node || reverse == node)

in_depth = 1;

if (forward == reverse)

return;

forward = forward->next;

reverse = reverse->prev;

}

if (!in_depth)

quicklistCompressNode(node);

if (depth > 2) {

/* At this point, forward and reverse are one node beyond depth */

quicklistCompressNode(forward);

quicklistCompressNode(reverse);

}

}

#define quicklistCompress(_ql, _node) \

do { \

if ((_node)->recompress) \

quicklistCompressNode((_node)); \

else \

__quicklistCompress((_ql), (_node)); \

} while (0)

#define quicklistRecompressOnly(_ql, _node) \

do { \

if ((_node)->recompress) \

quicklistCompressNode((_node)); \

} while (0)

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

quicklist->len++;

}

REDIS_STATIC void _quicklistInsertNodeBefore(quicklist *quicklist,

quicklistNode *old_node,

quicklistNode *new_node) {

__quicklistInsertNode(quicklist, old_node, new_node, 0);

}

REDIS_STATIC void _quicklistInsertNodeAfter(quicklist *quicklist,

quicklistNode *old_node,

quicklistNode *new_node) {

__quicklistInsertNode(quicklist, old_node, new_node, 1);

}

REDIS_STATIC int

_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;

}

}

#define sizeMeetsSafetyLimit(sz) ((sz) <= SIZE_SAFETY_LIMIT)

REDIS_STATIC int _quicklistNodeAllowInsert(const quicklistNode *node,

const int fill, const size_t sz) {

if (unlikely(!node))

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

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

return 1;

else if (!sizeMeetsSafetyLimit(new_sz))

return 0;

else if ((int)node->count < fill)

return 1;

else

return 0;

}

REDIS_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

unsigned int merge_sz = a->sz + b->sz - 11;

if (likely(_quicklistNodeSizeMeetsOptimizationRequirement(merge_sz, fill)))

return 1;

else if (!sizeMeetsSafetyLimit(merge_sz))

return 0;

else if ((int)(a->count + b->count) <= fill)

return 1;

else

return 0;

}

#define quicklistNodeUpdateSz(node) \

do { \

(node)->sz = ziplistBlobLen((node)->zl); \

} while (0)

int quicklistPushHead(quicklist *quicklist, void *value, size_t sz) {

quicklistNode *orig_head = quicklist->head;

if (likely(

_quicklistNodeAllowInsert(quicklist->head, quicklist->fill, sz))) {

quicklist->head->zl =

ziplistPush(quicklist->head->zl, value, sz, ZIPLIST_HEAD);

quicklistNodeUpdateSz(quicklist->head);

} else {

quicklistNode *node = quicklistCreateNode();

node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_HEAD);

quicklistNodeUpdateSz(node);

_quicklistInsertNodeBefore(quicklist, quicklist->head, node);

}

quicklist->count++;

quicklist->head->count++;

return (orig_head != quicklist->head);

}

int quicklistPushTail(quicklist *quicklist, void *value, size_t sz) {

quicklistNode *orig_tail = quicklist->tail;

if (likely(

_quicklistNodeAllowInsert(quicklist->tail, quicklist->fill, sz))) {

quicklist->tail->zl =

ziplistPush(quicklist->tail->zl, value, sz, ZIPLIST_TAIL);

quicklistNodeUpdateSz(quicklist->tail);

} else {

quicklistNode *node = quicklistCreateNode();

node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_TAIL);

quicklistNodeUpdateSz(node);

_quicklistInsertNodeAfter(quicklist, quicklist->tail, node);

}

quicklist->count++;

quicklist->tail->count++;

return (orig_tail != quicklist->tail);

}

void 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;

}

quicklist *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)) {

if (!value) {

/* 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);

p = ziplistNext(zl, p);

}

zfree(zl);

return quicklist;

}

quicklist *quicklistCreateFromZiplist(int fill, int compress,

unsigned char *zl) {

return quicklistAppendValuesFromZiplist(quicklistNew(fill, compress), zl);

}

#define quicklistDeleteIfEmpty(ql, n) \

do { \

if ((n)->count == 0) { \

__quicklistDelNode((ql), (n)); \

(n) = NULL; \

} \

} while (0)

REDIS_STATIC void __quicklistDelNode(quicklist *quicklist,

quicklistNode *node) {

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

__quicklistCompress(quicklist, NULL);

quicklist->count -= node->count;

zfree(node->zl);

zfree(node);

quicklist->len--;

}

REDIS_STATIC int quicklistDelIndex(quicklist *quicklist, quicklistNode *node,

unsigned char **p) {

int gone = 0;

node->zl = ziplistDelete(node->zl, p);

node->count--;

if (node->count == 0) {

gone = 1;

__quicklistDelNode(quicklist, node);

} else {

quicklistNodeUpdateSz(node);

}

quicklist->count--;

/* If we deleted the node, the original node is no longer valid */

return gone ? 1 : 0;

}

void 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;

/* If current node is deleted, we must update iterator node and offset. */

if (deleted_node) {

if (iter->direction == AL_START_HEAD) {

iter->current = next;

iter->offset = 0;

} else if (iter->direction == AL_START_TAIL) {

iter->current = prev;

iter->offset = -1;

}

}

/* else if (!deleted_node), no changes needed.

}

int quicklistReplaceAtIndex(quicklist *quicklist, long index, void *data,

int sz) {

quicklistEntry entry;

if (likely(quicklistIndex(quicklist, index, &entry))) {

/* quicklistIndex provides an uncompressed node */

entry.node->zl = ziplistDelete(entry.node->zl, &entry.zi);

entry.node->zl = ziplistInsert(entry.node->zl, entry.zi, data, sz);

quicklistNodeUpdateSz(entry.node);

quicklistCompress(quicklist, entry.node);

return 1;

} else {

return 0;

}

}

REDIS_STATIC quicklistNode *_quicklistZiplistMerge(quicklist *quicklist,

quicklistNode *a,

quicklistNode *b) {

D("Requested merge (a,b) (%u, %u)", a->count, b->count);

quicklistDecompressNode(a);

quicklistDecompressNode(b);

if ((ziplistMerge(&a->zl, &b->zl))) {

/* We merged ziplists! Now remove the unused quicklistNode. */

quicklistNode *keep = NULL, *nokeep = NULL;

if (!a->zl) {

nokeep = a;

keep = b;

} else if (!b->zl) {

nokeep = b;

keep = a;

}

keep->count = ziplistLen(keep->zl);

quicklistNodeUpdateSz(keep);

nokeep->count = 0;

__quicklistDelNode(quicklist, nokeep);

quicklistCompress(quicklist, keep);

return keep;

} else {

/* else, the merge returned NULL and nothing changed. */

return NULL;

}

}

REDIS_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;

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; /* 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; /* 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; /* 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);

}

}

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

/* -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);

new_node->zl = ziplistDeleteRange(new_node->zl, new_start, new_extent);

new_node->count = ziplistLen(new_node->zl);

quicklistNodeUpdateSz(new_node);

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

return new_node;

}

REDIS_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;

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

__quicklistInsertNode(quicklist, NULL, 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);

unsigned char *next = ziplistNext(node->zl, entry->zi);

if (next == NULL) {

node->zl = ziplistPush(node->zl, value, sz, ZIPLIST_TAIL);

} else {

node->zl = ziplistInsert(node->zl, next, value, sz);

}

node->count++;

quicklistNodeUpdateSz(node);

quicklistRecompressOnly(quicklist, node);

} else if (!full && !after) {

D("Not full, inserting before current position.");

quicklistDecompressNodeForUse(node);

node->zl = ziplistInsert(node->zl, entry->zi, value, sz);

node->count++;

quicklistNodeUpdateSz(node);

quicklistRecompressOnly(quicklist, node);

} else if (full && at_tail && node->next && !full_next && after) {

/* If we are: at tail, next has free space, and inserting after:

D("Full and tail, but next isn't full; inserting next node head");

new_node = node->next;

quicklistDecompressNodeForUse(new_node);

new_node->zl = ziplistPush(new_node->zl, value, sz, ZIPLIST_HEAD);

new_node->count++;

quicklistNodeUpdateSz(new_node);

quicklistRecompressOnly(quicklist, new_node);

} else if (full && at_head && node->prev && !full_prev && !after) {

/* If we are: at head, previous has free space, and inserting before:

D("Full and head, but prev isn't full, inserting prev node tail");

new_node = node->prev;

quicklistDecompressNodeForUse(new_node);

new_node->zl = ziplistPush(new_node->zl, value, sz, ZIPLIST_TAIL);

new_node->count++;

quicklistNodeUpdateSz(new_node);

quicklistRecompressOnly(quicklist, new_node);

} else if (full && ((at_tail && node->next && full_next && after) ||

(at_head && node->prev && full_prev && !after))) {

/* If we are: full, and our prev/next is full, then:

D("\tprovisioning new node...");

new_node = quicklistCreateNode();

new_node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_HEAD);

new_node->count++;

quicklistNodeUpdateSz(new_node);

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

new_node = _quicklistSplitNode(node, entry->offset, after);

new_node->zl = ziplistPush(new_node->zl, value, sz,

after ? ZIPLIST_HEAD : ZIPLIST_TAIL);

new_node->count++;

quicklistNodeUpdateSz(new_node);

__quicklistInsertNode(quicklist, node, new_node, after);

_quicklistMergeNodes(quicklist, node);

}

quicklist->count++;

}

void quicklistInsertBefore(quicklist *quicklist, quicklistEntry *entry,

void *value, const size_t sz) {

_quicklistInsert(quicklist, entry, value, sz, 0);

}

void quicklistInsertAfter(quicklist *quicklist, quicklistEntry *entry,

void *value, const size_t sz) {

_quicklistInsert(quicklist, entry, value, sz, 1);

}

int 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

delete_entire_node = 1;

del = node->count;

} else if (entry.offset >= 0 && extent >= node->count) {

/* If deleting more nodes after this one, calculate delete based

del = node->count - entry.offset;

} else if (entry.offset < 0) {

/* If offset is negative, we are in the first run of this loop