tskiplist.h 7.7 KB
Newer Older
H
hzcheng 已提交
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
/*
 * Copyright (c) 2019 TAOS Data, Inc. <jhtao@taosdata.com>
 *
 * This program is free software: you can use, redistribute, and/or modify
 * it under the terms of the GNU Affero General Public License, version 3
 * or later ("AGPL"), as published by the Free Software Foundation.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.
 *
 * You should have received a copy of the GNU Affero General Public License
 * along with this program. If not, see <http://www.gnu.org/licenses/>.
 */

16 17
#ifndef TDENGINE_TSKIPLIST_H
#define TDENGINE_TSKIPLIST_H
H
hzcheng 已提交
18 19 20 21 22

#ifdef __cplusplus
extern "C" {
#endif

S
slguan 已提交
23
#include "os.h"
H
hzcheng 已提交
24
#include "taosdef.h"
H
more  
hzcheng 已提交
25
#include "tarray.h"
H
hzcheng 已提交
26

H
more  
hzcheng 已提交
27 28 29 30 31 32 33
#define MAX_SKIP_LIST_LEVEL 15
#define SKIP_LIST_RECORD_PERFORMANCE 0

typedef char *SSkipListKey;
typedef char *(*__sl_key_fn_t)(const void *);

/**
34
 * the skip list node is located in a consecutive memory area,
H
more  
hzcheng 已提交
35 36 37 38 39 40 41 42
 * the format of skip list node is as follows:
 * +------------+-----------------------+------------------------+-----+------+
 * | node level | forward pointer array | backward pointer array | key | data |
 * +------------+-----------------------+------------------------+-----+------+
 */
typedef struct SSkipListNode {
  uint8_t level;
} SSkipListNode;
H
hzcheng 已提交
43

H
more  
hzcheng 已提交
44
#define SL_NODE_HEADER_SIZE(_l) (sizeof(SSkipListNode) + ((_l) << 1u) * POINTER_BYTES)
H
hzcheng 已提交
45

H
more  
hzcheng 已提交
46 47 48
#define SL_GET_FORWARD_POINTER(n, _l) ((SSkipListNode **)((char *)(n) + sizeof(SSkipListNode)))[(_l)]
#define SL_GET_BACKWARD_POINTER(n, _l) \
  ((SSkipListNode **)((char *)(n) + sizeof(SSkipListNode) + ((n)->level) * POINTER_BYTES))[(_l)]
H
hzcheng 已提交
49

H
hjxilinx 已提交
50
#define SL_GET_NODE_DATA(n) ((char *)(n) + SL_NODE_HEADER_SIZE((n)->level))
H
more  
hzcheng 已提交
51
#define SL_GET_NODE_KEY(s, n) ((s)->keyFn(SL_GET_NODE_DATA(n)))
52

53
#define SL_GET_SL_MIN_KEY(s) (SL_GET_NODE_KEY((s), SL_GET_FORWARD_POINTER((s)->pHead, 0)))
H
Haojun Liao 已提交
54
#define SL_GET_SL_MAX_KEY(s) (SL_GET_NODE_KEY((s), SL_GET_BACKWARD_POINTER((s)->pTail, 0)))
55

H
hzcheng 已提交
56
#define SL_GET_NODE_LEVEL(n) *(uint8_t *)((n))
H
hzcheng 已提交
57 58

/*
H
more  
hzcheng 已提交
59
 * @version 0.3
H
hzcheng 已提交
60
 * @date   2017/11/12
H
more  
hzcheng 已提交
61 62
 * the simple version of skip list.
 *
S
slguan 已提交
63
 * for multi-thread safe purpose, we employ pthread_rwlock_t to guarantee to generate
H
more  
hzcheng 已提交
64 65 66
 * deterministic result. Later, we will remove the lock in SkipList to further enhance the performance.
 * In this case, one should use the concurrent skip list (by using michael-scott algorithm) instead of
 * this simple version in a multi-thread environment, to achieve higher performance of read/write operations.
H
hzcheng 已提交
67 68
 *
 * Note: Duplicated primary key situation.
S
slguan 已提交
69
 * In case of duplicated primary key, two ways can be employed to handle this situation:
H
more  
hzcheng 已提交
70 71 72
 * 1. add as normal insertion without special process.
 * 2. add an overflow pointer at each list node, all nodes with the same key will be added in the overflow pointer.
 *    In this case, the total steps of each search will be reduced significantly.
S
slguan 已提交
73 74 75 76
 *    Currently, we implement the skip list in a line with the first means, maybe refactor it soon.
 *
 *    Memory consumption: the memory alignment causes many memory wasted. So, employ a memory
 *    pool will significantly reduce the total memory consumption, as well as the calloc/malloc operation costs.
H
hzcheng 已提交
77 78 79 80 81 82 83 84 85
 *
 */

// state struct, record following information:
// number of links in each level.
// avg search steps, for latest 1000 queries
// avg search rsp time, for latest 1000 queries
// total memory size
typedef struct tSkipListState {
H
more  
hzcheng 已提交
86
  // in bytes, sizeof(SSkipList)+sizeof(SSkipListNode)*SSkipList->nSize
H
hzcheng 已提交
87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105
  uint64_t nTotalMemSize;
  uint64_t nLevelNodeCnt[MAX_SKIP_LIST_LEVEL];
  uint64_t queryCount;  // total query count

  /*
   * only record latest 1000 queries
   * when the value==1000, = 0,
   * nTotalStepsForQueries = 0,
   * nTotalElapsedTimeForQueries = 0
   */
  uint64_t nRecQueries;
  uint16_t nTotalStepsForQueries;
  uint64_t nTotalElapsedTimeForQueries;

  uint16_t nInsertObjs;
  uint16_t nTotalStepsForInsert;
  uint64_t nTotalElapsedTimeForInsert;
} tSkipListState;

H
more  
hzcheng 已提交
106 107
typedef struct SSkipListKeyInfo {
  uint8_t dupKey : 2;  // if allow duplicated key in the skip list
H
hjxilinx 已提交
108 109
  uint8_t type : 4;    // key type
  uint8_t freeNode:2;  // free node when destroy the skiplist
H
more  
hzcheng 已提交
110 111 112 113
  uint8_t len;         // maximum key length, used in case of string key
} SSkipListKeyInfo;

typedef struct SSkipList {
H
hjxilinx 已提交
114 115 116 117 118 119
  __compar_fn_t     comparFn;
  __sl_key_fn_t     keyFn;
  uint32_t          size;
  uint8_t           maxLevel;
  uint8_t           level;
  SSkipListKeyInfo  keyInfo;
H
more  
hzcheng 已提交
120
  pthread_rwlock_t *lock;
H
hjxilinx 已提交
121 122
  SSkipListNode *   pHead;    // point to the first element
  SSkipListNode *   pTail;    // point to the last element
H
more  
hzcheng 已提交
123 124 125 126
#if SKIP_LIST_RECORD_PERFORMANCE
  tSkipListState state;  // skiplist state
#endif
} SSkipList;
H
hzcheng 已提交
127

S
slguan 已提交
128 129 130 131
/*
 * iterate the skiplist
 * this will cause the multi-thread problem, when the skiplist is destroyed, the iterate may
 * continue iterating the skiplist, so add the reference count for skiplist
H
more  
hzcheng 已提交
132
 * TODO add the ref for skip list when one iterator is created
S
slguan 已提交
133 134
 */
typedef struct SSkipListIterator {
H
more  
hzcheng 已提交
135 136
  SSkipList *    pSkipList;
  SSkipListNode *cur;
137 138
  int32_t        step;          // the number of nodes that have been checked already
  int32_t        order;         // order of the iterator
S
slguan 已提交
139 140
} SSkipListIterator;

H
more  
hzcheng 已提交
141 142 143 144 145 146
/**
 *
 * @param nMaxLevel   maximum skip list level
 * @param keyType     type of key
 * @param dupKey      allow the duplicated key in the skip list
 * @return
H
hzcheng 已提交
147
 */
H
more  
hzcheng 已提交
148
SSkipList *tSkipListCreate(uint8_t nMaxLevel, uint8_t keyType, uint8_t keyLen, uint8_t dupKey, uint8_t threadsafe,
H
hjxilinx 已提交
149
    uint8_t freeNode, __sl_key_fn_t fn);
H
hzcheng 已提交
150

H
more  
hzcheng 已提交
151 152 153 154 155 156
/**
 *
 * @param pSkipList
 * @return                NULL will always be returned
 */
void *tSkipListDestroy(SSkipList *pSkipList);
H
hzcheng 已提交
157

H
more  
hzcheng 已提交
158 159 160 161 162 163
/**
 *
 * @param pSkipList
 * @param level
 * @param headSize
 */
164
void tSkipListNewNodeInfo(SSkipList *pSkipList, int32_t *level, int32_t *headSize);
H
hzcheng 已提交
165

H
more  
hzcheng 已提交
166 167 168 169 170 171 172
/**
 * put the skip list node into the skip list.
 * If failed, NULL will be returned, otherwise, the pNode will be returned.
 *
 * @param pSkipList
 * @param pNode
 * @return
H
hzcheng 已提交
173
 */
H
more  
hzcheng 已提交
174
SSkipListNode *tSkipListPut(SSkipList *pSkipList, SSkipListNode *pNode);
H
hzcheng 已提交
175

H
more  
hzcheng 已提交
176
/**
177
 * get *all* nodes which key are equivalent to pKey
H
more  
hzcheng 已提交
178 179 180 181
 *
 * @param pSkipList
 * @param pKey
 * @return
H
hzcheng 已提交
182
 */
183
SArray *tSkipListGet(SSkipList *pSkipList, SSkipListKey pKey);
H
hzcheng 已提交
184

H
more  
hzcheng 已提交
185
/**
H
hjxilinx 已提交
186
 * get the size of skip list
H
more  
hzcheng 已提交
187 188 189
 * @param pSkipList
 * @return
 */
H
hjxilinx 已提交
190 191 192 193 194 195 196 197
size_t tSkipListGetSize(const SSkipList *pSkipList);

/**
 * display skip list of the given level, for debug purpose only
 * @param pSkipList
 * @param nlevel
 */
void tSkipListPrint(SSkipList *pSkipList, int16_t nlevel);
H
hjxilinx 已提交
198 199 200 201 202 203

/**
 * create skiplist iterator
 * @param pSkipList
 * @return
 */
H
hjxilinx 已提交
204
SSkipListIterator *tSkipListCreateIter(SSkipList *pSkipList);
H
hjxilinx 已提交
205

206 207 208 209 210 211 212 213 214
/**
 * create skip list iterator from the given node and specified the order
 * @param pSkipList
 * @param pNode     start position, instead of the first node in skip list
 * @param order     traverse order of the iterator
 * @return
 */
SSkipListIterator *tSkipListCreateIterFromVal(SSkipList* pSkipList, const char* val, int32_t type, int32_t order);

H
hjxilinx 已提交
215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233
/**
 * forward the skip list iterator
 * @param iter
 * @return
 */
bool tSkipListIterNext(SSkipListIterator *iter);

/**
 * get the element of skip list node
 * @param iter
 * @return
 */
SSkipListNode *tSkipListIterGet(SSkipListIterator *iter);

/**
 * destroy the skip list node
 * @param iter
 * @return
 */
H
hjxilinx 已提交
234
void *tSkipListDestroyIter(SSkipListIterator *iter);
H
hzcheng 已提交
235 236

/*
237 238
 * remove nodes of the pKey value.
 * If more than one node has the same value, all will be removed
H
hzcheng 已提交
239 240
 *
 * @Return
241
 * the count of removed nodes
H
hzcheng 已提交
242
 */
243
uint32_t tSkipListRemove(SSkipList *pSkipList, SSkipListKey key);
H
hzcheng 已提交
244 245 246 247

/*
 * remove the specified node in parameters
 */
H
more  
hzcheng 已提交
248
void tSkipListRemoveNode(SSkipList *pSkipList, SSkipListNode *pNode);
H
hzcheng 已提交
249 250 251 252 253

#ifdef __cplusplus
}
#endif

254
#endif  // TDENGINE_TSKIPLIST_H