Lines Matching refs:quicklist
78 (e)->quicklist = NULL; \
94 quicklist *quicklistCreate(void) { in quicklistCreate()
95 struct quicklist *quicklist; in quicklistCreate() local
97 quicklist = zmalloc(sizeof(*quicklist)); in quicklistCreate()
98 quicklist->head = quicklist->tail = NULL; in quicklistCreate()
99 quicklist->len = 0; in quicklistCreate()
100 quicklist->count = 0; in quicklistCreate()
101 quicklist->compress = 0; in quicklistCreate()
102 quicklist->fill = -2; in quicklistCreate()
103 return quicklist; in quicklistCreate()
107 void quicklistSetCompressDepth(quicklist *quicklist, int compress) { in quicklistSetCompressDepth() argument
113 quicklist->compress = compress; in quicklistSetCompressDepth()
117 void quicklistSetFill(quicklist *quicklist, int fill) { in quicklistSetFill() argument
123 quicklist->fill = fill; in quicklistSetFill()
126 void quicklistSetOptions(quicklist *quicklist, int fill, int depth) { in quicklistSetOptions() argument
127 quicklistSetFill(quicklist, fill); in quicklistSetOptions()
128 quicklistSetCompressDepth(quicklist, depth); in quicklistSetOptions()
132 quicklist *quicklistNew(int fill, int compress) { in quicklistNew()
133 quicklist *quicklist = quicklistCreate(); in quicklistNew() local
134 quicklistSetOptions(quicklist, fill, compress); in quicklistNew()
135 return quicklist; in quicklistNew()
152 unsigned long quicklistCount(const quicklist *ql) { return ql->count; } in quicklistCount()
155 void quicklistRelease(quicklist *quicklist) { in quicklistRelease() argument
159 current = quicklist->head; in quicklistRelease()
160 len = quicklist->len; in quicklistRelease()
165 quicklist->count -= current->count; in quicklistRelease()
169 quicklist->len--; in quicklistRelease()
172 zfree(quicklist); in quicklistRelease()
265 REDIS_STATIC void __quicklistCompress(const quicklist *quicklist, in __quicklistCompress() argument
269 if (!quicklistAllowsCompression(quicklist) || in __quicklistCompress()
270 quicklist->len < (unsigned int)(quicklist->compress * 2)) in __quicklistCompress()
275 if (quicklist->compress == 1) { in __quicklistCompress()
276 quicklistNode *h = quicklist->head, *t = quicklist->tail; in __quicklistCompress()
282 } else if (quicklist->compress == 2) { in __quicklistCompress()
283 quicklistNode *h = quicklist->head, *hn = h->next, *hnn = hn->next; in __quicklistCompress()
284 quicklistNode *t = quicklist->tail, *tp = t->prev, *tpp = tp->prev; in __quicklistCompress()
305 quicklistNode *forward = quicklist->head; in __quicklistCompress()
306 quicklistNode *reverse = quicklist->tail; in __quicklistCompress()
309 while (depth++ < quicklist->compress) { in __quicklistCompress()
352 REDIS_STATIC void __quicklistInsertNode(quicklist *quicklist, in __quicklistInsertNode() argument
363 if (quicklist->tail == old_node) in __quicklistInsertNode()
364 quicklist->tail = new_node; in __quicklistInsertNode()
373 if (quicklist->head == old_node) in __quicklistInsertNode()
374 quicklist->head = new_node; in __quicklistInsertNode()
377 if (quicklist->len == 0) { in __quicklistInsertNode()
378 quicklist->head = quicklist->tail = new_node; in __quicklistInsertNode()
382 quicklistCompress(quicklist, old_node); in __quicklistInsertNode()
384 quicklist->len++; in __quicklistInsertNode()
388 REDIS_STATIC void _quicklistInsertNodeBefore(quicklist *quicklist, in _quicklistInsertNodeBefore() argument
391 __quicklistInsertNode(quicklist, old_node, new_node, 0); in _quicklistInsertNodeBefore()
394 REDIS_STATIC void _quicklistInsertNodeAfter(quicklist *quicklist, in _quicklistInsertNodeAfter() argument
397 __quicklistInsertNode(quicklist, old_node, new_node, 1); in _quicklistInsertNodeAfter()
480 int quicklistPushHead(quicklist *quicklist, void *value, size_t sz) { in quicklistPushHead() argument
481 quicklistNode *orig_head = quicklist->head; in quicklistPushHead()
483 _quicklistNodeAllowInsert(quicklist->head, quicklist->fill, sz))) { in quicklistPushHead()
484 quicklist->head->zl = in quicklistPushHead()
485 ziplistPush(quicklist->head->zl, value, sz, ZIPLIST_HEAD); in quicklistPushHead()
486 quicklistNodeUpdateSz(quicklist->head); in quicklistPushHead()
492 _quicklistInsertNodeBefore(quicklist, quicklist->head, node); in quicklistPushHead()
494 quicklist->count++; in quicklistPushHead()
495 quicklist->head->count++; in quicklistPushHead()
496 return (orig_head != quicklist->head); in quicklistPushHead()
503 int quicklistPushTail(quicklist *quicklist, void *value, size_t sz) { in quicklistPushTail() argument
504 quicklistNode *orig_tail = quicklist->tail; in quicklistPushTail()
506 _quicklistNodeAllowInsert(quicklist->tail, quicklist->fill, sz))) { in quicklistPushTail()
507 quicklist->tail->zl = in quicklistPushTail()
508 ziplistPush(quicklist->tail->zl, value, sz, ZIPLIST_TAIL); in quicklistPushTail()
509 quicklistNodeUpdateSz(quicklist->tail); in quicklistPushTail()
515 _quicklistInsertNodeAfter(quicklist, quicklist->tail, node); in quicklistPushTail()
517 quicklist->count++; in quicklistPushTail()
518 quicklist->tail->count++; in quicklistPushTail()
519 return (orig_tail != quicklist->tail); in quicklistPushTail()
525 void quicklistAppendZiplist(quicklist *quicklist, unsigned char *zl) { in quicklistAppendZiplist() argument
532 _quicklistInsertNodeAfter(quicklist, quicklist->tail, node); in quicklistAppendZiplist()
533 quicklist->count += node->count; in quicklistAppendZiplist()
542 quicklist *quicklistAppendValuesFromZiplist(quicklist *quicklist, in quicklistAppendValuesFromZiplist() argument
556 quicklistPushTail(quicklist, value, sz); in quicklistAppendValuesFromZiplist()
560 return quicklist; in quicklistAppendValuesFromZiplist()
566 quicklist *quicklistCreateFromZiplist(int fill, int compress, in quicklistCreateFromZiplist()
579 REDIS_STATIC void __quicklistDelNode(quicklist *quicklist, in __quicklistDelNode() argument
586 if (node == quicklist->tail) { in __quicklistDelNode()
587 quicklist->tail = node->prev; in __quicklistDelNode()
590 if (node == quicklist->head) { in __quicklistDelNode()
591 quicklist->head = node->next; in __quicklistDelNode()
596 __quicklistCompress(quicklist, NULL); in __quicklistDelNode()
598 quicklist->count -= node->count; in __quicklistDelNode()
602 quicklist->len--; in __quicklistDelNode()
613 REDIS_STATIC int quicklistDelIndex(quicklist *quicklist, quicklistNode *node, in quicklistDelIndex() argument
621 __quicklistDelNode(quicklist, node); in quicklistDelIndex()
625 quicklist->count--; in quicklistDelIndex()
637 int deleted_node = quicklistDelIndex((quicklist *)entry->quicklist, in quicklistDelEntry()
667 int quicklistReplaceAtIndex(quicklist *quicklist, long index, void *data, in quicklistReplaceAtIndex() argument
670 if (likely(quicklistIndex(quicklist, index, &entry))) { in quicklistReplaceAtIndex()
675 quicklistCompress(quicklist, entry.node); in quicklistReplaceAtIndex()
695 REDIS_STATIC quicklistNode *_quicklistZiplistMerge(quicklist *quicklist, in _quicklistZiplistMerge() argument
716 __quicklistDelNode(quicklist, nokeep); in _quicklistZiplistMerge()
717 quicklistCompress(quicklist, keep); in _quicklistZiplistMerge()
733 REDIS_STATIC void _quicklistMergeNodes(quicklist *quicklist, in _quicklistMergeNodes() argument
735 int fill = quicklist->fill; in _quicklistMergeNodes()
753 _quicklistZiplistMerge(quicklist, prev_prev, prev); in _quicklistMergeNodes()
759 _quicklistZiplistMerge(quicklist, next, next_next); in _quicklistMergeNodes()
765 target = _quicklistZiplistMerge(quicklist, center->prev, center); in _quicklistMergeNodes()
774 _quicklistZiplistMerge(quicklist, target, target->next); in _quicklistMergeNodes()
832 REDIS_STATIC void _quicklistInsert(quicklist *quicklist, quicklistEntry *entry, in _quicklistInsert() argument
835 int fill = quicklist->fill; in _quicklistInsert()
844 __quicklistInsertNode(quicklist, NULL, new_node, after); in _quicklistInsert()
846 quicklist->count++; in _quicklistInsert()
887 quicklistRecompressOnly(quicklist, node); in _quicklistInsert()
894 quicklistRecompressOnly(quicklist, node); in _quicklistInsert()
904 quicklistRecompressOnly(quicklist, new_node); in _quicklistInsert()
914 quicklistRecompressOnly(quicklist, new_node); in _quicklistInsert()
924 __quicklistInsertNode(quicklist, node, new_node, after); in _quicklistInsert()
935 __quicklistInsertNode(quicklist, node, new_node, after); in _quicklistInsert()
936 _quicklistMergeNodes(quicklist, node); in _quicklistInsert()
939 quicklist->count++; in _quicklistInsert()
942 void quicklistInsertBefore(quicklist *quicklist, quicklistEntry *entry, in quicklistInsertBefore() argument
944 _quicklistInsert(quicklist, entry, value, sz, 0); in quicklistInsertBefore()
947 void quicklistInsertAfter(quicklist *quicklist, quicklistEntry *entry, in quicklistInsertAfter() argument
949 _quicklistInsert(quicklist, entry, value, sz, 1); in quicklistInsertAfter()
958 int quicklistDelRange(quicklist *quicklist, const long start, in quicklistDelRange() argument
965 if (start >= 0 && extent > (quicklist->count - start)) { in quicklistDelRange()
967 extent = quicklist->count - start; in quicklistDelRange()
974 if (!quicklistIndex(quicklist, start, &entry)) in quicklistDelRange()
1020 __quicklistDelNode(quicklist, node); in quicklistDelRange()
1026 quicklist->count -= del; in quicklistDelRange()
1027 quicklistDeleteIfEmpty(quicklist, node); in quicklistDelRange()
1029 quicklistRecompressOnly(quicklist, node); in quicklistDelRange()
1048 quicklistIter *quicklistGetIterator(const quicklist *quicklist, int direction) { in quicklistGetIterator() argument
1054 iter->current = quicklist->head; in quicklistGetIterator()
1057 iter->current = quicklist->tail; in quicklistGetIterator()
1062 iter->quicklist = quicklist; in quicklistGetIterator()
1071 quicklistIter *quicklistGetIteratorAtIdx(const quicklist *quicklist, in quicklistGetIteratorAtIdx() argument
1076 if (quicklistIndex(quicklist, idx, &entry)) { in quicklistGetIteratorAtIdx()
1077 quicklistIter *base = quicklistGetIterator(quicklist, direction); in quicklistGetIteratorAtIdx()
1091 quicklistCompress(iter->quicklist, iter->current); in quicklistReleaseIterator()
1125 entry->quicklist = iter->quicklist; in quicklistNext()
1163 quicklistCompress(iter->quicklist, iter->current); in quicklistNext()
1186 quicklist *quicklistDup(quicklist *orig) { in quicklistDup()
1187 quicklist *copy; in quicklistDup()
1225 int quicklistIndex(const quicklist *quicklist, const long long idx, in quicklistIndex() argument
1233 entry->quicklist = quicklist; in quicklistIndex()
1237 n = quicklist->tail; in quicklistIndex()
1240 n = quicklist->head; in quicklistIndex()
1243 if (index >= quicklist->count) in quicklistIndex()
1282 void quicklistRotate(quicklist *quicklist) { in quicklistRotate() argument
1283 if (quicklist->count <= 1) in quicklistRotate()
1287 unsigned char *p = ziplistIndex(quicklist->tail->zl, -1); in quicklistRotate()
1302 quicklistPushHead(quicklist, value, sz); in quicklistRotate()
1307 if (quicklist->len == 1) { in quicklistRotate()
1308 p = ziplistIndex(quicklist->tail->zl, -1); in quicklistRotate()
1312 quicklistDelIndex(quicklist, quicklist->tail, &p); in quicklistRotate()
1324 int quicklistPopCustom(quicklist *quicklist, int where, unsigned char **data, in quicklistPopCustom() argument
1333 if (quicklist->count == 0) in quicklistPopCustom()
1344 if (where == QUICKLIST_HEAD && quicklist->head) { in quicklistPopCustom()
1345 node = quicklist->head; in quicklistPopCustom()
1346 } else if (where == QUICKLIST_TAIL && quicklist->tail) { in quicklistPopCustom()
1347 node = quicklist->tail; in quicklistPopCustom()
1365 quicklistDelIndex(quicklist, node, &p); in quicklistPopCustom()
1385 int quicklistPop(quicklist *quicklist, int where, unsigned char **data, in quicklistPop() argument
1390 if (quicklist->count == 0) in quicklistPop()
1392 int ret = quicklistPopCustom(quicklist, where, &vstr, &vlen, &vlong, in quicklistPop()
1404 void quicklistPush(quicklist *quicklist, void *value, const size_t sz, in quicklistPush() argument
1407 quicklistPushHead(quicklist, value, sz); in quicklistPush()
1409 quicklistPushTail(quicklist, value, sz); in quicklistPush()
1450 static void ql_info(quicklist *ql) { in ql_info()
1482 static int _itrprintr(quicklist *ql, int print, int forward) { in _itrprintr()
1504 static int itrprintr(quicklist *ql, int print) { in itrprintr()
1508 static int itrprintr_rev(quicklist *ql, int print) { in itrprintr_rev()
1518 static int _ql_verify(quicklist *ql, uint32_t len, uint32_t count, in _ql_verify()
1631 quicklist *ql = quicklistNew(-2, options[_i]); in quicklistTest()
1637 quicklist *ql = quicklistNew(-2, options[_i]); in quicklistTest()
1645 quicklist *ql = quicklistNew(-2, options[_i]); in quicklistTest()
1655 quicklist *ql = quicklistNew(f, options[_i]); in quicklistTest()
1669 quicklist *ql = quicklistNew(f, options[_i]); in quicklistTest()
1683 quicklist *ql = quicklistNew(f, options[_i]); in quicklistTest()
1697 quicklist *ql = quicklistNew(f, options[_i]); in quicklistTest()
1709 quicklist *ql = quicklistNew(-2, options[_i]); in quicklistTest()
1717 quicklist *ql = quicklistNew(f, options[_i]); in quicklistTest()
1730 quicklist *ql = quicklistNew(f, options[_i]); in quicklistTest()
1753 quicklist *ql = quicklistNew(-2, options[_i]); in quicklistTest()
1760 quicklist *ql = quicklistNew(-2, options[_i]); in quicklistTest()
1779 quicklist *ql = quicklistNew(-2, options[_i]); in quicklistTest()
1793 quicklist *ql = quicklistNew(-2, options[_i]); in quicklistTest()
1815 quicklist *ql = quicklistNew(-2, options[_i]); in quicklistTest()
1841 quicklist *ql = quicklistNew(-2, options[_i]); in quicklistTest()
1864 quicklist *ql = quicklistNew(-2, options[_i]); in quicklistTest()
1886 quicklist *ql = quicklistNew(-2, options[_i]); in quicklistTest()
1895 quicklist *ql = quicklistNew(-2, options[_i]); in quicklistTest()
1904 quicklist *ql = quicklistNew(-2, options[_i]); in quicklistTest()
1914 quicklist *ql = quicklistNew(-2, options[_i]); in quicklistTest()
1927 quicklist *ql = quicklistNew(f, options[_i]); in quicklistTest()
1984 quicklist *ql = quicklistNew(f, options[_i]); in quicklistTest()
2002 quicklist *ql = quicklistNew(f, options[_i]); in quicklistTest()
2021 quicklist *ql = quicklistNew(-2, options[_i]); in quicklistTest()
2023 quicklist *copy = quicklistDup(ql); in quicklistTest()
2030 quicklist *ql = quicklistNew(-2, options[_i]); in quicklistTest()
2033 quicklist *copy = quicklistDup(ql); in quicklistTest()
2040 quicklist *ql = quicklistNew(-2, options[_i]); in quicklistTest()
2046 quicklist *copy = quicklistDup(ql); in quicklistTest()
2055 quicklist *ql = quicklistNew(f, options[_i]); in quicklistTest()
2074 quicklist *ql = quicklistNew(f, options[_i]); in quicklistTest()
2093 quicklist *ql = quicklistNew(f, options[_i]); in quicklistTest()
2107 quicklist *ql = quicklistNew(f, options[_i]); in quicklistTest()
2121 quicklist *ql = quicklistNew(-2, options[_i]); in quicklistTest()
2128 quicklist *ql = quicklistNew(-2, options[_i]); in quicklistTest()
2138 quicklist *ql = quicklistNew(-2, options[_i]); in quicklistTest()
2148 quicklist *ql = quicklistNew(-2, options[_i]); in quicklistTest()
2159 quicklist *ql = quicklistNew(-2, options[_i]); in quicklistTest()
2170 quicklist *ql = quicklistNew(-2, options[_i]); in quicklistTest()
2181 quicklist *ql = quicklistNew(-2, options[_i]); in quicklistTest()
2191 quicklist *ql = quicklistNew(-2, options[_i]); in quicklistTest()
2202 quicklist *ql = quicklistNew(-2, options[_i]); in quicklistTest()
2241 quicklist *ql = quicklistNew(-2, options[_i]); in quicklistTest()
2267 quicklist *ql = quicklistNew(-2, options[_i]); in quicklistTest()
2281 quicklist *ql = quicklistNew(f, options[_i]); in quicklistTest()
2366 quicklist *ql = quicklistNew(f, options[_i]); in quicklistTest()
2406 quicklist *ql = quicklistNew(f, options[_i]); in quicklistTest()
2433 quicklist *ql = quicklistNew(f, options[_i]); in quicklistTest()
2465 quicklist *ql = quicklistNew(f, QUICKLIST_NOCOMPRESS); in quicklistTest()
2510 quicklist *ql = quicklistNew(f, options[_i]); in quicklistTest()
2539 quicklist *ql = quicklistNew(f, options[_i]); in quicklistTest()
2573 quicklist *ql = quicklistCreateFromZiplist(f, options[_i], zl); in quicklistTest()
2600 quicklist *ql = quicklistNew(f, depth); in quicklistTest()