/* quicklist.h - A generic doubly linked quicklist implementation * * Copyright (c) 2014, Matt Stancliff * 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 retain 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. */ #include // for UINTPTR_MAX #ifndef __QUICKLIST_H__ #define __QUICKLIST_H__ /* Node, quicklist, and Iterator are the only data structures used currently. */ /* quicklistNode is a 32 byte struct describing a listpack for a quicklist. * We use bit fields keep the quicklistNode at 32 bytes. * count: 16 bits, max 65536 (max lp bytes is 65k, so max count actually < 32k). * encoding: 2 bits, RAW=1, LZF=2. * container: 2 bits, PLAIN=1 (a single item as char array), PACKED=2 (listpack with multiple items). * recompress: 1 bit, bool, true if node is temporary decompressed for usage. * attempted_compress: 1 bit, boolean, used for verifying during testing. * extra: 10 bits, free for future use; pads out the remainder of 32 bits */ typedef struct quicklistNode { struct quicklistNode *prev; struct quicklistNode *next; unsigned char *entry; size_t sz; /* entry size in bytes */ unsigned int count : 16; /* count of items in listpack */ unsigned int encoding : 2; /* RAW==1 or LZF==2 */ unsigned int container : 2; /* PLAIN==1 or PACKED==2 */ unsigned int recompress : 1; /* was this node previous compressed? */ unsigned int attempted_compress : 1; /* node can't compress; too small */ unsigned int dont_compress : 1; /* prevent compression of entry that will be used later */ unsigned int extra : 9; /* more bits to steal for future usage */ } quicklistNode; /* quicklistLZF is a 8+N byte struct holding 'sz' followed by 'compressed'. * 'sz' is byte length of 'compressed' field. * 'compressed' is LZF data with total (compressed) length 'sz' * NOTE: uncompressed length is stored in quicklistNode->sz. * When quicklistNode->entry is compressed, node->entry points to a quicklistLZF */ typedef struct quicklistLZF { size_t sz; /* LZF size in bytes*/ char compressed[]; } quicklistLZF; /* Bookmarks are padded with realloc at the end of of the quicklist struct. * They should only be used for very big lists if thousands of nodes were the * excess memory usage is negligible, and there's a real need to iterate on them * in portions. * When not used, they don't add any memory overhead, but when used and then * deleted, some overhead remains (to avoid resonance). * The number of bookmarks used should be kept to minimum since it also adds * overhead on node deletion (searching for a bookmark to update). */ typedef struct quicklistBookmark { quicklistNode *node; char *name; } quicklistBookmark; #if UINTPTR_MAX == 0xffffffff /* 32-bit */ # define QL_FILL_BITS 14 # define QL_COMP_BITS 14 # define QL_BM_BITS 4 #elif UINTPTR_MAX == 0xffffffffffffffff /* 64-bit */ # define QL_FILL_BITS 16 # define QL_COMP_BITS 16 # define QL_BM_BITS 4 /* we can encode more, but we rather limit the user since they cause performance degradation. */ #else # error unknown arch bits count #endif /* quicklist is a 40 byte struct (on 64-bit systems) describing a quicklist. * 'count' is the number of total entries. * 'len' is the number of quicklist nodes. * 'compress' is: 0 if compression disabled, otherwise it's the number * of quicklistNodes to leave uncompressed at ends of quicklist. * 'fill' is the user-requested (or default) fill factor. * 'bookmarks are an optional feature that is used by realloc this struct, * so that they don't consume memory when not used. */ typedef struct quicklist { quicklistNode *head; quicklistNode *tail; unsigned long count; /* total count of all entries in all listpacks */ unsigned long len; /* number of quicklistNodes */ signed int fill : QL_FILL_BITS; /* fill factor for individual nodes */ unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */ unsigned int bookmark_count: QL_BM_BITS; quicklistBookmark bookmarks[]; } quicklist; typedef struct quicklistIter { quicklist *quicklist; quicklistNode *current; unsigned char *zi; /* points to the current element */ long offset; /* offset in current listpack */ int direction; } quicklistIter; typedef struct quicklistEntry { const quicklist *quicklist; quicklistNode *node; unsigned char *zi; unsigned char *value; long long longval; size_t sz; int offset; } quicklistEntry; #define QUICKLIST_HEAD 0 #define QUICKLIST_TAIL -1 /* quicklist node encodings */ #define QUICKLIST_NODE_ENCODING_RAW 1 #define QUICKLIST_NODE_ENCODING_LZF 2 /* quicklist compression disable */ #define QUICKLIST_NOCOMPRESS 0 /* quicklist node container formats */ #define QUICKLIST_NODE_CONTAINER_PLAIN 1 #define QUICKLIST_NODE_CONTAINER_PACKED 2 #define QL_NODE_IS_PLAIN(node) ((node)->container == QUICKLIST_NODE_CONTAINER_PLAIN) #define quicklistNodeIsCompressed(node) \ ((node)->encoding == QUICKLIST_NODE_ENCODING_LZF) /* Prototypes */ quicklist *quicklistCreate(void); quicklist *quicklistNew(int fill, int compress); void quicklistSetCompressDepth(quicklist *quicklist, int depth); void quicklistSetFill(quicklist *quicklist, int fill); void quicklistSetOptions(quicklist *quicklist, int fill, int depth); void quicklistRelease(quicklist *quicklist); int quicklistPushHead(quicklist *quicklist, void *value, const size_t sz); int quicklistPushTail(quicklist *quicklist, void *value, const size_t sz); void quicklistPush(quicklist *quicklist, void *value, const size_t sz, int where); void quicklistAppendListpack(quicklist *quicklist, unsigned char *zl); void quicklistAppendPlainNode(quicklist *quicklist, unsigned char *data, size_t sz); void quicklistInsertAfter(quicklistIter *iter, quicklistEntry *entry, void *value, const size_t sz); void quicklistInsertBefore(quicklistIter *iter, quicklistEntry *entry, void *value, const size_t sz); void quicklistDelEntry(quicklistIter *iter, quicklistEntry *entry); void quicklistReplaceEntry(quicklistIter *iter, quicklistEntry *entry, void *data, size_t sz); int quicklistReplaceAtIndex(quicklist *quicklist, long index, void *data, const size_t sz); int quicklistDelRange(quicklist *quicklist, const long start, const long stop); quicklistIter *quicklistGetIterator(quicklist *quicklist, int direction); quicklistIter *quicklistGetIteratorAtIdx(quicklist *quicklist, int direction, const long long idx); quicklistIter *quicklistGetIteratorEntryAtIdx(quicklist *quicklist, const long long index, quicklistEntry *entry); int quicklistNext(quicklistIter *iter, quicklistEntry *entry); void quicklistSetDirection(quicklistIter *iter, int direction); void quicklistReleaseIterator(quicklistIter *iter); quicklist *quicklistDup(quicklist *orig); void quicklistRotate(quicklist *quicklist); int quicklistPopCustom(quicklist *quicklist, int where, unsigned char **data, size_t *sz, long long *sval, void *(*saver)(unsigned char *data, size_t sz)); int quicklistPop(quicklist *quicklist, int where, unsigned char **data, size_t *sz, long long *slong); unsigned long quicklistCount(const quicklist *ql); int quicklistCompare(quicklistEntry *entry, unsigned char *p2, const size_t p2_len); size_t quicklistGetLzf(const quicklistNode *node, void **data); void quicklistNodeLimit(int fill, size_t *size, unsigned int *count); int quicklistNodeExceedsLimit(int fill, size_t new_sz, unsigned int new_count); void quicklistRepr(unsigned char *ql, int full); /* bookmarks */ int quicklistBookmarkCreate(quicklist **ql_ref, const char *name, quicklistNode *node); int quicklistBookmarkDelete(quicklist *ql, const char *name); quicklistNode *quicklistBookmarkFind(quicklist *ql, const char *name); void quicklistBookmarksClear(quicklist *ql); int quicklistisSetPackedThreshold(size_t sz); #ifdef REDIS_TEST int quicklistTest(int argc, char *argv[], int flags); #endif /* Directions for iterators */ #define AL_START_HEAD 0 #define AL_START_TAIL 1 #endif /* __QUICKLIST_H__ */