diff options
Diffstat (limited to 'src/quicklist.h')
| -rw-r--r-- | src/quicklist.h | 214 |
1 files changed, 214 insertions, 0 deletions
diff --git a/src/quicklist.h b/src/quicklist.h new file mode 100644 index 0000000..f17834b --- /dev/null +++ b/src/quicklist.h @@ -0,0 +1,214 @@ +/* quicklist.h - A generic doubly linked quicklist implementation + * + * 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 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 <stdint.h> // 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__ */ |