diff options
Diffstat (limited to 'examples/redis-unstable/src/quicklist.h')
| -rw-r--r-- | examples/redis-unstable/src/quicklist.h | 218 |
1 files changed, 0 insertions, 218 deletions
diff --git a/examples/redis-unstable/src/quicklist.h b/examples/redis-unstable/src/quicklist.h deleted file mode 100644 index 998ba1c..0000000 --- a/examples/redis-unstable/src/quicklist.h +++ /dev/null @@ -1,218 +0,0 @@ -/* 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. - * dont_compress: 1 bit, boolean, used for preventing compression of entry. - * extra: 9 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 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 */ - size_t alloc_size; /* total allocated memory (in bytes) */ - 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 compress); -void quicklistSetFill(quicklist *quicklist, int fill); -void quicklistSetOptions(quicklist *quicklist, int fill, int compress); -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 count); -void quicklistInitIterator(quicklistIter *iter, quicklist *quicklist, int direction); -int quicklistInitIteratorAtIdx(quicklistIter *iter, quicklist *quicklist, - int direction, const long long idx); -int quicklistInitIteratorEntryAtIdx(quicklistIter *iter, quicklist *quicklist, - const long long index, quicklistEntry *entry); -int quicklistNext(quicklistIter *iter, quicklistEntry *entry); -void quicklistSetDirection(quicklistIter *iter, int direction); -void quicklistResetIterator(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); -size_t quicklistAllocSize(const quicklist *ql); -int quicklistCompare(quicklistEntry *entry, unsigned char *p2, const size_t p2_len, - long long *cached_longval, int *cached_valid); -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 quicklistSetPackedThreshold(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__ */ |