1 /* quicklist.h - A generic doubly linked quicklist implementation 2 * 3 * Copyright (c) 2014, Matt Stancliff <[email protected]> 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions are met: 8 * 9 * * Redistributions of source code must retain the above copyright notice, 10 * this quicklist of conditions and the following disclaimer. 11 * * Redistributions in binary form must reproduce the above copyright 12 * notice, this quicklist of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * * Neither the name of Redis nor the names of its contributors may be used 15 * to endorse or promote products derived from this software without 16 * specific prior written permission. 17 * 18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 19 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 21 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 22 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 23 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 24 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 25 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 26 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 27 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 28 * POSSIBILITY OF SUCH DAMAGE. 29 */ 30 31 #ifndef __QUICKLIST_H__ 32 #define __QUICKLIST_H__ 33 34 /* Node, quicklist, and Iterator are the only data structures used currently. */ 35 36 /* quicklistNode is a 32 byte struct describing a ziplist for a quicklist. 37 * We use bit fields keep the quicklistNode at 32 bytes. 38 * count: 16 bits, max 65536 (max zl bytes is 65k, so max count actually < 32k). 39 * encoding: 2 bits, RAW=1, LZF=2. 40 * container: 2 bits, NONE=1, ZIPLIST=2. 41 * recompress: 1 bit, bool, true if node is temporarry decompressed for usage. 42 * attempted_compress: 1 bit, boolean, used for verifying during testing. 43 * extra: 12 bits, free for future use; pads out the remainder of 32 bits */ 44 typedef struct quicklistNode { 45 struct quicklistNode *prev; 46 struct quicklistNode *next; 47 unsigned char *zl; 48 unsigned int sz; /* ziplist size in bytes */ 49 unsigned int count : 16; /* count of items in ziplist */ 50 unsigned int encoding : 2; /* RAW==1 or LZF==2 */ 51 unsigned int container : 2; /* NONE==1 or ZIPLIST==2 */ 52 unsigned int recompress : 1; /* was this node previous compressed? */ 53 unsigned int attempted_compress : 1; /* node can't compress; too small */ 54 unsigned int extra : 10; /* more bits to steal for future usage */ 55 } quicklistNode; 56 57 /* quicklistLZF is a 4+N byte struct holding 'sz' followed by 'compressed'. 58 * 'sz' is byte length of 'compressed' field. 59 * 'compressed' is LZF data with total (compressed) length 'sz' 60 * NOTE: uncompressed length is stored in quicklistNode->sz. 61 * When quicklistNode->zl is compressed, node->zl points to a quicklistLZF */ 62 typedef struct quicklistLZF { 63 unsigned int sz; /* LZF size in bytes*/ 64 char compressed[]; 65 } quicklistLZF; 66 67 /* quicklist is a 32 byte struct (on 64-bit systems) describing a quicklist. 68 * 'count' is the number of total entries. 69 * 'len' is the number of quicklist nodes. 70 * 'compress' is: -1 if compression disabled, otherwise it's the number 71 * of quicklistNodes to leave uncompressed at ends of quicklist. 72 * 'fill' is the user-requested (or default) fill factor. */ 73 typedef struct quicklist { 74 quicklistNode *head; 75 quicklistNode *tail; 76 unsigned long count; /* total count of all entries in all ziplists */ 77 unsigned int len; /* number of quicklistNodes */ 78 int fill : 16; /* fill factor for individual nodes */ 79 unsigned int compress : 16; /* depth of end nodes not to compress;0=off */ 80 } quicklist; 81 82 typedef struct quicklistIter { 83 const quicklist *quicklist; 84 quicklistNode *current; 85 unsigned char *zi; 86 long offset; /* offset in current ziplist */ 87 int direction; 88 } quicklistIter; 89 90 typedef struct quicklistEntry { 91 const quicklist *quicklist; 92 quicklistNode *node; 93 unsigned char *zi; 94 unsigned char *value; 95 long long longval; 96 unsigned int sz; 97 int offset; 98 } quicklistEntry; 99 100 #define QUICKLIST_HEAD 0 101 #define QUICKLIST_TAIL -1 102 103 /* quicklist node encodings */ 104 #define QUICKLIST_NODE_ENCODING_RAW 1 105 #define QUICKLIST_NODE_ENCODING_LZF 2 106 107 /* quicklist compression disable */ 108 #define QUICKLIST_NOCOMPRESS 0 109 110 /* quicklist container formats */ 111 #define QUICKLIST_NODE_CONTAINER_NONE 1 112 #define QUICKLIST_NODE_CONTAINER_ZIPLIST 2 113 114 #define quicklistNodeIsCompressed(node) \ 115 ((node)->encoding == QUICKLIST_NODE_ENCODING_LZF) 116 117 /* Prototypes */ 118 quicklist *quicklistCreate(void); 119 quicklist *quicklistNew(int fill, int compress); 120 void quicklistSetCompressDepth(quicklist *quicklist, int depth); 121 void quicklistSetFill(quicklist *quicklist, int fill); 122 void quicklistSetOptions(quicklist *quicklist, int fill, int depth); 123 void quicklistRelease(quicklist *quicklist); 124 int quicklistPushHead(quicklist *quicklist, void *value, const size_t sz); 125 int quicklistPushTail(quicklist *quicklist, void *value, const size_t sz); 126 void quicklistPush(quicklist *quicklist, void *value, const size_t sz, 127 int where); 128 void quicklistAppendZiplist(quicklist *quicklist, unsigned char *zl); 129 quicklist *quicklistAppendValuesFromZiplist(quicklist *quicklist, 130 unsigned char *zl); 131 quicklist *quicklistCreateFromZiplist(int fill, int compress, 132 unsigned char *zl); 133 void quicklistInsertAfter(quicklist *quicklist, quicklistEntry *node, 134 void *value, const size_t sz); 135 void quicklistInsertBefore(quicklist *quicklist, quicklistEntry *node, 136 void *value, const size_t sz); 137 void quicklistDelEntry(quicklistIter *iter, quicklistEntry *entry); 138 int quicklistReplaceAtIndex(quicklist *quicklist, long index, void *data, 139 int sz); 140 int quicklistDelRange(quicklist *quicklist, const long start, const long stop); 141 quicklistIter *quicklistGetIterator(const quicklist *quicklist, int direction); 142 quicklistIter *quicklistGetIteratorAtIdx(const quicklist *quicklist, 143 int direction, const long long idx); 144 int quicklistNext(quicklistIter *iter, quicklistEntry *node); 145 void quicklistReleaseIterator(quicklistIter *iter); 146 quicklist *quicklistDup(quicklist *orig); 147 int quicklistIndex(const quicklist *quicklist, const long long index, 148 quicklistEntry *entry); 149 void quicklistRewind(quicklist *quicklist, quicklistIter *li); 150 void quicklistRewindTail(quicklist *quicklist, quicklistIter *li); 151 void quicklistRotate(quicklist *quicklist); 152 int quicklistPopCustom(quicklist *quicklist, int where, unsigned char **data, 153 unsigned int *sz, long long *sval, 154 void *(*saver)(unsigned char *data, unsigned int sz)); 155 int quicklistPop(quicklist *quicklist, int where, unsigned char **data, 156 unsigned int *sz, long long *slong); 157 unsigned int quicklistCount(quicklist *ql); 158 int quicklistCompare(unsigned char *p1, unsigned char *p2, int p2_len); 159 size_t quicklistGetLzf(const quicklistNode *node, void **data); 160 161 #ifdef REDIS_TEST 162 int quicklistTest(int argc, char *argv[]); 163 #endif 164 165 /* Directions for iterators */ 166 #define AL_START_HEAD 0 167 #define AL_START_TAIL 1 168 169 #endif /* __QUICKLIST_H__ */ 170