thash.c 22.7 KB
Newer Older
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/>.
 */

S
hash  
Shengliang Guan 已提交
16
#define _DEFAULT_SOURCE
H
Haojun Liao 已提交
17
#include "thash.h"
H
Haojun Liao 已提交
18
#include "os.h"
L
Liu Jicong 已提交
19
#include "taoserror.h"
S
hash  
Shengliang Guan 已提交
20
#include "tlog.h"
21

22
// the add ref count operation may trigger the warning if the reference count is greater than the MAX_WARNING_REF_COUNT
H
Haojun Liao 已提交
23 24 25 26 27 28 29
#define MAX_WARNING_REF_COUNT    10000
#define HASH_MAX_CAPACITY        (1024 * 1024 * 16)
#define HASH_DEFAULT_LOAD_FACTOR (0.75)
#define HASH_INDEX(v, c)         ((v) & ((c)-1))

#define HASH_NEED_RESIZE(_h) ((_h)->size >= (_h)->capacity * HASH_DEFAULT_LOAD_FACTOR)

L
Liu Jicong 已提交
30 31 32
#define GET_HASH_NODE_KEY(_n)  ((char *)(_n) + sizeof(SHashNode) + (_n)->dataLen)
#define GET_HASH_NODE_DATA(_n) ((char *)(_n) + sizeof(SHashNode))
#define GET_HASH_PNODE(_n)     ((SHashNode *)((char *)(_n) - sizeof(SHashNode)))
H
Haojun Liao 已提交
33

34 35
#define FREE_HASH_NODE(_fp, _n) \
  do {                          \
L
Liu Jicong 已提交
36 37 38
    /*    if (_fp != NULL) {    \
          (_fp)(_n);            \
        }*/                     \
39
    taosMemoryFreeClear(_n);    \
H
Haojun Liao 已提交
40 41
  } while (0);

H
Haojun Liao 已提交
42
struct SHashNode {
L
Liu Jicong 已提交
43 44 45 46 47 48 49
  SHashNode *next;
  uint32_t   hashVal;   // the hash value of key
  uint32_t   dataLen;   // length of data
  uint32_t   keyLen;    // length of the key
  uint16_t   refCount;  // reference count
  int8_t     removed;   // flag to indicate removed
  char       data[];
H
Haojun Liao 已提交
50 51
};

H
Haojun Liao 已提交
52
typedef struct SHashEntry {
L
Liu Jicong 已提交
53 54 55
  int32_t    num;    // number of elements in current entry
  SRWLatch   latch;  // entry latch
  SHashNode *next;
H
Haojun Liao 已提交
56 57
} SHashEntry;

H
Haojun Liao 已提交
58
struct SHashObj {
L
Liu Jicong 已提交
59
  SHashEntry      **hashList;
H
Haojun Liao 已提交
60
  size_t            capacity;      // number of slots
wafwerar's avatar
wafwerar 已提交
61
  int64_t           size;          // number of elements in hash table
H
Haojun Liao 已提交
62 63 64 65 66 67
  _hash_fn_t        hashFp;        // hash function
  _equal_fn_t       equalFp;       // equal function
  _hash_free_fn_t   freeFp;        // hash node free callback function
  SRWLatch          lock;          // read-write spin lock
  SHashLockTypeE    type;          // lock type
  bool              enableUpdate;  // enable update
L
Liu Jicong 已提交
68
  SArray           *pMemBlock;     // memory block allocated for SHashEntry
H
Haojun Liao 已提交
69 70
  _hash_before_fn_t callbackFp;    // function invoked before return the value to caller
};
H
Haojun Liao 已提交
71 72 73 74 75 76 77 78 79 80 81 82 83

/*
 * Function definition
 */
static FORCE_INLINE void taosHashWLock(SHashObj *pHashObj) {
  if (pHashObj->type == HASH_NO_LOCK) {
    return;
  }
  taosWLockLatch(&pHashObj->lock);
}

static FORCE_INLINE void taosHashWUnlock(SHashObj *pHashObj) {
  if (pHashObj->type == HASH_NO_LOCK) {
H
hjxilinx 已提交
84 85
    return;
  }
H
Haojun Liao 已提交
86 87

  taosWUnLockLatch(&pHashObj->lock);
88 89
}

H
Haojun Liao 已提交
90 91
static FORCE_INLINE void taosHashRLock(SHashObj *pHashObj) {
  if (pHashObj->type == HASH_NO_LOCK) {
H
hjxilinx 已提交
92 93
    return;
  }
H
Haojun Liao 已提交
94 95

  taosRLockLatch(&pHashObj->lock);
96 97
}

H
Haojun Liao 已提交
98 99
static FORCE_INLINE void taosHashRUnlock(SHashObj *pHashObj) {
  if (pHashObj->type == HASH_NO_LOCK) {
H
hjxilinx 已提交
100 101
    return;
  }
H
Haojun Liao 已提交
102 103 104 105

  taosRUnLockLatch(&pHashObj->lock);
}

L
Liu Jicong 已提交
106
static FORCE_INLINE void taosHashEntryWLock(const SHashObj *pHashObj, SHashEntry *pe) {
H
Haojun Liao 已提交
107 108 109 110 111 112
  if (pHashObj->type == HASH_NO_LOCK) {
    return;
  }
  taosWLockLatch(&pe->latch);
}

L
Liu Jicong 已提交
113
static FORCE_INLINE void taosHashEntryWUnlock(const SHashObj *pHashObj, SHashEntry *pe) {
H
Haojun Liao 已提交
114 115 116 117 118 119 120
  if (pHashObj->type == HASH_NO_LOCK) {
    return;
  }

  taosWUnLockLatch(&pe->latch);
}

L
Liu Jicong 已提交
121
static FORCE_INLINE void taosHashEntryRLock(const SHashObj *pHashObj, SHashEntry *pe) {
H
Haojun Liao 已提交
122 123 124 125 126
  if (pHashObj->type == HASH_NO_LOCK) {
    return;
  }

  taosRLockLatch(&pe->latch);
127 128
}

L
Liu Jicong 已提交
129
static FORCE_INLINE void taosHashEntryRUnlock(const SHashObj *pHashObj, SHashEntry *pe) {
H
Haojun Liao 已提交
130
  if (pHashObj->type == HASH_NO_LOCK) {
H
hjxilinx 已提交
131 132
    return;
  }
H
Haojun Liao 已提交
133 134

  taosRUnLockLatch(&pe->latch);
135 136 137
}

static FORCE_INLINE int32_t taosHashCapacity(int32_t length) {
wafwerar's avatar
wafwerar 已提交
138
  int32_t len = (length < HASH_MAX_CAPACITY ? length : HASH_MAX_CAPACITY);
139

S
Shengliang Guan 已提交
140
  int32_t i = 4;
141
  while (i < len) i = (i << 1u);
142 143 144
  return i;
}

L
Liu Jicong 已提交
145 146
static FORCE_INLINE SHashNode *doSearchInEntryList(SHashObj *pHashObj, SHashEntry *pe, const void *key, size_t keyLen,
                                                   uint32_t hashVal) {
H
Haojun Liao 已提交
147
  SHashNode *pNode = pe->next;
H
Haojun Liao 已提交
148
  while (pNode) {
L
Liu Jicong 已提交
149
    if ((pNode->keyLen == keyLen) && ((*(pHashObj->equalFp))(GET_HASH_NODE_KEY(pNode), key, keyLen) == 0) &&
S
hash  
Shengliang Guan 已提交
150
        pNode->removed == 0) {
H
Haojun Liao 已提交
151 152 153 154 155 156 157 158 159 160
      assert(pNode->hashVal == hashVal);
      break;
    }

    pNode = pNode->next;
  }

  return pNode;
}

161
/**
H
Haojun Liao 已提交
162
 * resize the hash list if the threshold is reached
163
 *
H
hjxilinx 已提交
164
 * @param pHashObj
165
 */
H
hjLiao 已提交
166
static void taosHashTableResize(SHashObj *pHashObj);
167

H
hjLiao 已提交
168
/**
H
Haojun Liao 已提交
169 170
 * allocate and initialize a hash node
 *
H
hjLiao 已提交
171 172
 * @param key      key of object for hash, usually a null-terminated string
 * @param keyLen   length of key
H
Haojun Liao 已提交
173
 * @param pData    data to be stored in hash node
H
hjLiao 已提交
174 175 176 177
 * @param dsize    size of data
 * @return         SHashNode
 */
static SHashNode *doCreateHashNode(const void *key, size_t keyLen, const void *pData, size_t dsize, uint32_t hashVal);
178

H
hjLiao 已提交
179
/**
H
Haojun Liao 已提交
180
 * update the hash node
H
hjLiao 已提交
181
 *
H
Haojun Liao 已提交
182 183 184 185 186
 * @param pHashObj   hash table object
 * @param pe         hash table entry to operate on
 * @param prev       previous node
 * @param pNode      the old node with requested key
 * @param pNewNode   the new node with requested key
H
hjLiao 已提交
187
 */
L
Liu Jicong 已提交
188 189
static FORCE_INLINE void doUpdateHashNode(SHashObj *pHashObj, SHashEntry *pe, SHashNode *prev, SHashNode *pNode,
                                          SHashNode *pNewNode) {
H
Haojun Liao 已提交
190
  assert(pNode->keyLen == pNewNode->keyLen);
陶建辉(Jeff)'s avatar
陶建辉(Jeff) 已提交
191

wafwerar's avatar
wafwerar 已提交
192
  atomic_sub_fetch_16(&pNode->refCount, 1);
H
Haojun Liao 已提交
193 194
  if (prev != NULL) {
    prev->next = pNewNode;
195
    ASSERT(prev->next != prev);
196 197
  } else {
    pe->next = pNewNode;
H
Haojun Liao 已提交
198
  }
H
Haojun Liao 已提交
199

H
Haojun Liao 已提交
200
  if (pNode->refCount <= 0) {
陶建辉(Jeff)'s avatar
陶建辉(Jeff) 已提交
201
    pNewNode->next = pNode->next;
202 203
    ASSERT(pNewNode->next != pNewNode);

204
    FREE_HASH_NODE(pHashObj->freeFp, pNode);
陶建辉(Jeff)'s avatar
陶建辉(Jeff) 已提交
205
  } else {
S
hash  
Shengliang Guan 已提交
206
    pNewNode->next = pNode;
陶建辉(Jeff)'s avatar
陶建辉(Jeff) 已提交
207
    pe->num++;
H
Haojun Liao 已提交
208
    atomic_add_fetch_64(&pHashObj->size, 1);
陶建辉(Jeff)'s avatar
陶建辉(Jeff) 已提交
209
  }
H
Haojun Liao 已提交
210
}
211

H
hjLiao 已提交
212 213 214
/**
 * insert the hash node at the front of the linked list
 *
H
Haojun Liao 已提交
215 216
 * @param pHashObj   hash table object
 * @param pNode      the old node with requested key
H
hjLiao 已提交
217
 */
H
Haojun Liao 已提交
218
static void pushfrontNodeInEntryList(SHashEntry *pEntry, SHashNode *pNode);
219

220 221 222 223 224 225 226 227
/**
 * Check whether the hash table is empty or not.
 *
 * @param pHashObj the hash table object
 * @return if the hash table is empty or not
 */
static FORCE_INLINE bool taosHashTableEmpty(const SHashObj *pHashObj);

228
/**
H
Haojun Liao 已提交
229
 *
230 231
 * @param pHashObj
 * @return
232
 */
L
Liu Jicong 已提交
233
static FORCE_INLINE bool taosHashTableEmpty(const SHashObj *pHashObj) { return taosHashGetSize(pHashObj) == 0; }
234

H
Haojun Liao 已提交
235
SHashObj *taosHashInit(size_t capacity, _hash_fn_t fn, bool update, SHashLockTypeE type) {
H
Haojun Liao 已提交
236 237 238 239 240
  if (fn == NULL) {
    assert(0);
    return NULL;
  }

241 242
  if (capacity == 0) {
    capacity = 4;
243 244
  }

wafwerar's avatar
wafwerar 已提交
245
  SHashObj *pHashObj = (SHashObj *)taosMemoryCalloc(1, sizeof(SHashObj));
H
hjxilinx 已提交
246
  if (pHashObj == NULL) {
H
Haojun Liao 已提交
247
    terrno = TSDB_CODE_OUT_OF_MEMORY;
248 249 250 251
    return NULL;
  }

  // the max slots is not defined by user
S
Shengliang Guan 已提交
252
  pHashObj->capacity = taosHashCapacity((int32_t)capacity);
H
Haojun Liao 已提交
253

254
  pHashObj->equalFp = memcmp;
L
Liu Jicong 已提交
255
  pHashObj->hashFp = fn;
H
Haojun Liao 已提交
256
  pHashObj->type = type;
H
Haojun Liao 已提交
257
  pHashObj->enableUpdate = update;
258

H
Haojun Liao 已提交
259 260
  ASSERT((pHashObj->capacity & (pHashObj->capacity - 1)) == 0);

wafwerar's avatar
wafwerar 已提交
261
  pHashObj->hashList = (SHashEntry **)taosMemoryCalloc(pHashObj->capacity, sizeof(void *));
H
hjxilinx 已提交
262
  if (pHashObj->hashList == NULL) {
wafwerar's avatar
wafwerar 已提交
263
    taosMemoryFree(pHashObj);
H
Haojun Liao 已提交
264
    terrno = TSDB_CODE_OUT_OF_MEMORY;
265
    return NULL;
H
Haojun Liao 已提交
266
  }
H
Haojun Liao 已提交
267

H
Haojun Liao 已提交
268 269
  pHashObj->pMemBlock = taosArrayInit(8, sizeof(void *));
  if (pHashObj->pMemBlock == NULL) {
wafwerar's avatar
wafwerar 已提交
270 271
    taosMemoryFree(pHashObj->hashList);
    taosMemoryFree(pHashObj);
H
Haojun Liao 已提交
272 273 274
    terrno = TSDB_CODE_OUT_OF_MEMORY;
    return NULL;
  }
H
Haojun Liao 已提交
275

wafwerar's avatar
wafwerar 已提交
276
  void *p = taosMemoryCalloc(pHashObj->capacity, sizeof(SHashEntry));
H
Haojun Liao 已提交
277 278
  if (p == NULL) {
    taosArrayDestroy(pHashObj->pMemBlock);
wafwerar's avatar
wafwerar 已提交
279 280
    taosMemoryFree(pHashObj->hashList);
    taosMemoryFree(pHashObj);
H
Haojun Liao 已提交
281 282
    terrno = TSDB_CODE_OUT_OF_MEMORY;
    return NULL;
283
  }
H
hjxilinx 已提交
284

H
Haojun Liao 已提交
285 286 287 288 289
  for (int32_t i = 0; i < pHashObj->capacity; ++i) {
    pHashObj->hashList[i] = (void *)((char *)p + i * sizeof(SHashEntry));
  }

  taosArrayPush(pHashObj->pMemBlock, &p);
H
hjxilinx 已提交
290
  return pHashObj;
291 292
}

293 294 295
void taosHashSetEqualFp(SHashObj *pHashObj, _equal_fn_t fp) {
  if (pHashObj != NULL && fp != NULL) {
    pHashObj->equalFp = fp;
S
hash  
Shengliang Guan 已提交
296 297
  }
}
298

H
Haojun Liao 已提交
299 300 301 302 303 304
void taosHashSetFreeFp(SHashObj *pHashObj, _hash_free_fn_t fp) {
  if (pHashObj != NULL && fp != NULL) {
    pHashObj->freeFp = fp;
  }
}

305
int32_t taosHashGetSize(const SHashObj *pHashObj) {
H
Haojun Liao 已提交
306
  if (pHashObj == NULL) {
307 308
    return 0;
  }
L
Liu Jicong 已提交
309
  return (int32_t)atomic_load_64((int64_t *)&pHashObj->size);
310 311
}

X
Xiaoyu Wang 已提交
312
int32_t taosHashPut(SHashObj *pHashObj, const void *key, size_t keyLen, const void *data, size_t size) {
H
Haojun Liao 已提交
313
  if (pHashObj == NULL || key == NULL || keyLen == 0) {
314
    terrno = TSDB_CODE_INVALID_PTR;
H
Haojun Liao 已提交
315 316
    return -1;
  }
317

318
  uint32_t hashVal = (*pHashObj->hashFp)(key, (uint32_t)keyLen);
319

H
Haojun Liao 已提交
320 321
  // need the resize process, write lock applied
  if (HASH_NEED_RESIZE(pHashObj)) {
H
Haojun Liao 已提交
322
    taosHashWLock(pHashObj);
H
Haojun Liao 已提交
323
    taosHashTableResize(pHashObj);
H
Haojun Liao 已提交
324
    taosHashWUnlock(pHashObj);
H
Haojun Liao 已提交
325 326
  }

327
  // disable resize
H
Haojun Liao 已提交
328
  taosHashRLock(pHashObj);
H
Haojun Liao 已提交
329

H
Haojun Liao 已提交
330
  int32_t     slot = HASH_INDEX(hashVal, pHashObj->capacity);
H
Haojun Liao 已提交
331
  SHashEntry *pe = pHashObj->hashList[slot];
332

H
Haojun Liao 已提交
333
  taosHashEntryWLock(pHashObj, pe);
334

H
Haojun Liao 已提交
335
  SHashNode *pNode = pe->next;
336
#if 0
H
Haojun Liao 已提交
337 338 339 340 341
  if (pe->num > 0) {
    assert(pNode != NULL);
  } else {
    assert(pNode == NULL);
  }
342
#endif
H
Haojun Liao 已提交
343

L
Liu Jicong 已提交
344
  SHashNode *prev = NULL;
H
Haojun Liao 已提交
345
  while (pNode) {
L
Liu Jicong 已提交
346
    if ((pNode->keyLen == keyLen) && (*(pHashObj->equalFp))(GET_HASH_NODE_KEY(pNode), key, keyLen) == 0 &&
S
hash  
Shengliang Guan 已提交
347
        pNode->removed == 0) {
H
Haojun Liao 已提交
348 349
      assert(pNode->hashVal == hashVal);
      break;
350 351
    }

H
Haojun Liao 已提交
352
    prev = pNode;
H
Haojun Liao 已提交
353 354 355 356 357
    pNode = pNode->next;
  }

  if (pNode == NULL) {
    // no data in hash table with the specified key, add it into hash table
358 359 360 361 362
    SHashNode *pNewNode = doCreateHashNode(key, keyLen, data, size, hashVal);
    if (pNewNode == NULL) {
      return -1;
    }

H
Haojun Liao 已提交
363
    pushfrontNodeInEntryList(pe, pNewNode);
H
Haojun Liao 已提交
364
    assert(pe->next != NULL);
H
Haojun Liao 已提交
365

H
Haojun Liao 已提交
366
    taosHashEntryWUnlock(pHashObj, pe);
H
Haojun Liao 已提交
367 368

    // enable resize
H
Haojun Liao 已提交
369 370
    taosHashRUnlock(pHashObj);
    atomic_add_fetch_64(&pHashObj->size, 1);
S
hash  
Shengliang Guan 已提交
371

H
Haojun Liao 已提交
372
    return 0;
373
  } else {
H
Haojun Liao 已提交
374 375
    // not support the update operation, return error
    if (pHashObj->enableUpdate) {
376 377 378 379 380
      SHashNode *pNewNode = doCreateHashNode(key, keyLen, data, size, hashVal);
      if (pNewNode == NULL) {
        return -1;
      }

陶建辉(Jeff)'s avatar
陶建辉(Jeff) 已提交
381
      doUpdateHashNode(pHashObj, pe, prev, pNode, pNewNode);
382 383
    } else {
      terrno = TSDB_CODE_DUP_KEY;
H
Haojun Liao 已提交
384 385
    }

H
Haojun Liao 已提交
386
    taosHashEntryWUnlock(pHashObj, pe);
H
Haojun Liao 已提交
387 388

    // enable resize
H
Haojun Liao 已提交
389
    taosHashRUnlock(pHashObj);
H
Haojun Liao 已提交
390
    return pHashObj->enableUpdate ? 0 : -2;
H
Haojun Liao 已提交
391
  }
392 393
}

L
Liu Jicong 已提交
394
static void *taosHashGetImpl(SHashObj *pHashObj, const void *key, size_t keyLen, void **d, int32_t *size, bool addRef);
D
dapan1121 已提交
395

H
hjLiao 已提交
396
void *taosHashGet(SHashObj *pHashObj, const void *key, size_t keyLen) {
L
Liu Jicong 已提交
397
  void *p = NULL;
H
Haojun Liao 已提交
398
  return taosHashGetImpl(pHashObj, key, keyLen, &p, 0, false);
H
Haojun Liao 已提交
399
}
H
Haojun Liao 已提交
400

H
Haojun Liao 已提交
401 402
int32_t taosHashGetDup(SHashObj *pHashObj, const void *key, size_t keyLen, void *destBuf) {
  terrno = 0;
L
Liu Jicong 已提交
403
  /*char* p = */ taosHashGetImpl(pHashObj, key, keyLen, &destBuf, 0, false);
H
Haojun Liao 已提交
404 405
  return terrno;
}
406

L
Liu Jicong 已提交
407
int32_t taosHashGetDup_m(SHashObj *pHashObj, const void *key, size_t keyLen, void **destBuf, int32_t *size) {
H
Haojun Liao 已提交
408
  terrno = 0;
409

L
Liu Jicong 已提交
410
  /*char* p = */ taosHashGetImpl(pHashObj, key, keyLen, destBuf, size, false);
H
Haojun Liao 已提交
411
  return terrno;
412
}
H
Haojun Liao 已提交
413

L
Liu Jicong 已提交
414
void *taosHashGetImpl(SHashObj *pHashObj, const void *key, size_t keyLen, void **d, int32_t *size, bool addRef) {
H
Haojun Liao 已提交
415
  if (pHashObj == NULL || taosHashTableEmpty(pHashObj) || keyLen == 0 || key == NULL) {
H
Haojun Liao 已提交
416 417 418
    return NULL;
  }

S
Shengliang Guan 已提交
419
  uint32_t hashVal = (*pHashObj->hashFp)(key, (uint32_t)keyLen);
420

H
Haojun Liao 已提交
421
  // only add the read lock to disable the resize process
H
Haojun Liao 已提交
422
  taosHashRLock(pHashObj);
H
Haojun Liao 已提交
423

H
Haojun Liao 已提交
424 425
  int32_t     slot = HASH_INDEX(hashVal, pHashObj->capacity);
  SHashEntry *pe = pHashObj->hashList[slot];
426

H
Haojun Liao 已提交
427 428
  // no data, return directly
  if (atomic_load_32(&pe->num) == 0) {
H
Haojun Liao 已提交
429
    taosHashRUnlock(pHashObj);
430 431
    return NULL;
  }
H
Haojun Liao 已提交
432 433

  char *data = NULL;
H
Haojun Liao 已提交
434
  taosHashEntryRLock(pHashObj, pe);
H
Haojun Liao 已提交
435

H
Haojun Liao 已提交
436
#if 0
H
Haojun Liao 已提交
437 438 439 440 441
  if (pe->num > 0) {
    assert(pe->next != NULL);
  } else {
    assert(pe->next == NULL);
  }
H
Haojun Liao 已提交
442
#endif
H
Haojun Liao 已提交
443

444
  SHashNode *pNode = doSearchInEntryList(pHashObj, pe, key, keyLen, hashVal);
H
Haojun Liao 已提交
445
  if (pNode != NULL) {
H
Haojun Liao 已提交
446 447
    if (pHashObj->callbackFp != NULL) {
      pHashObj->callbackFp(GET_HASH_NODE_DATA(pNode));
H
Haojun Liao 已提交
448
    }
H
Haojun Liao 已提交
449

H
Haojun Liao 已提交
450 451
    if (size != NULL) {
      if (*d == NULL) {
L
Liu Jicong 已提交
452
        *size = pNode->dataLen;
wafwerar's avatar
wafwerar 已提交
453
        *d = taosMemoryCalloc(1, *size);
H
Haojun Liao 已提交
454 455 456 457 458
        if (*d == NULL) {
          terrno = TSDB_CODE_OUT_OF_MEMORY;
          return NULL;
        }
      } else if (*size < pNode->dataLen) {
L
Liu Jicong 已提交
459 460
        *size = pNode->dataLen;
        char *tmp = taosMemoryRealloc(*d, *size);
H
Haojun Liao 已提交
461 462 463 464 465 466 467 468 469 470 471
        if (tmp == NULL) {
          terrno = TSDB_CODE_OUT_OF_MEMORY;
          return NULL;
        }

        *d = tmp;
      }
    }

    if (addRef) {
      atomic_add_fetch_16(&pNode->refCount, 1);
H
Haojun Liao 已提交
472
    }
473

H
Haojun Liao 已提交
474 475
    if (*d != NULL) {
      memcpy(*d, GET_HASH_NODE_DATA(pNode), pNode->dataLen);
D
dapan1121 已提交
476 477
    }

478
    data = GET_HASH_NODE_DATA(pNode);
H
Haojun Liao 已提交
479 480
  }

H
Haojun Liao 已提交
481 482
  taosHashEntryRUnlock(pHashObj, pe);
  taosHashRUnlock(pHashObj);
H
Haojun Liao 已提交
483 484

  return data;
485 486
}

H
Haojun Liao 已提交
487
int32_t taosHashRemove(SHashObj *pHashObj, const void *key, size_t keyLen) {
H
Haojun Liao 已提交
488
  if (pHashObj == NULL || taosHashTableEmpty(pHashObj) || key == NULL || keyLen == 0) {
H
Haojun Liao 已提交
489 490 491
    return -1;
  }

S
Shengliang Guan 已提交
492
  uint32_t hashVal = (*pHashObj->hashFp)(key, (uint32_t)keyLen);
H
Haojun Liao 已提交
493

H
Haojun Liao 已提交
494
  // disable the resize process
H
Haojun Liao 已提交
495
  taosHashRLock(pHashObj);
H
Haojun Liao 已提交
496

H
Haojun Liao 已提交
497
  int32_t     slot = HASH_INDEX(hashVal, pHashObj->capacity);
H
Haojun Liao 已提交
498 499
  SHashEntry *pe = pHashObj->hashList[slot];

H
Haojun Liao 已提交
500
  taosHashEntryWLock(pHashObj, pe);
501 502

  // double check after locked
H
Haojun Liao 已提交
503
  if (pe->num == 0) {
H
Haojun Liao 已提交
504 505
    assert(pe->next == NULL);

H
Haojun Liao 已提交
506 507
    taosHashEntryWUnlock(pHashObj, pe);
    taosHashRUnlock(pHashObj);
H
Haojun Liao 已提交
508
    return -1;
H
Haojun Liao 已提交
509 510
  }

L
Liu Jicong 已提交
511
  int        code = -1;
H
Haojun Liao 已提交
512
  SHashNode *pNode = pe->next;
陶建辉(Jeff)'s avatar
陶建辉(Jeff) 已提交
513
  SHashNode *prevNode = NULL;
H
Haojun Liao 已提交
514

陶建辉(Jeff)'s avatar
陶建辉(Jeff) 已提交
515
  while (pNode) {
L
Liu Jicong 已提交
516
    if ((pNode->keyLen == keyLen) && ((*(pHashObj->equalFp))(GET_HASH_NODE_KEY(pNode), key, keyLen) == 0) &&
H
Haojun Liao 已提交
517 518
        pNode->removed == 0) {
      code = 0;  // it is found
H
Haojun Liao 已提交
519

wafwerar's avatar
wafwerar 已提交
520
      atomic_sub_fetch_16(&pNode->refCount, 1);
H
Haojun Liao 已提交
521 522 523 524 525 526
      pNode->removed = 1;
      if (pNode->refCount <= 0) {
        if (prevNode == NULL) {
          pe->next = pNode->next;
        } else {
          prevNode->next = pNode->next;
527
          ASSERT(prevNode->next != prevNode);
H
Haojun Liao 已提交
528
        }
H
Haojun Liao 已提交
529

H
Haojun Liao 已提交
530 531
        pe->num--;
        atomic_sub_fetch_64(&pHashObj->size, 1);
532
        FREE_HASH_NODE(pHashObj->freeFp, pNode);
陶建辉(Jeff)'s avatar
陶建辉(Jeff) 已提交
533
      }
H
Haojun Liao 已提交
534 535 536
    } else {
      prevNode = pNode;
      pNode = pNode->next;
陶建辉(Jeff)'s avatar
陶建辉(Jeff) 已提交
537
    }
H
Haojun Liao 已提交
538
  }
539

H
Haojun Liao 已提交
540 541
  taosHashEntryWUnlock(pHashObj, pe);
  taosHashRUnlock(pHashObj);
H
Haojun Liao 已提交
542

陶建辉(Jeff)'s avatar
陶建辉(Jeff) 已提交
543
  return code;
H
Haojun Liao 已提交
544 545
}

546
void taosHashClear(SHashObj *pHashObj) {
H
Haojun Liao 已提交
547 548 549
  if (pHashObj == NULL) {
    return;
  }
550 551 552

  SHashNode *pNode, *pNext;

H
Haojun Liao 已提交
553
  taosHashWLock(pHashObj);
554

555 556 557
  for (int32_t i = 0; i < pHashObj->capacity; ++i) {
    SHashEntry *pEntry = pHashObj->hashList[i];
    if (pEntry->num == 0) {
H
Haojun Liao 已提交
558
      assert(pEntry->next == NULL);
559 560
      continue;
    }
561

562 563
    pNode = pEntry->next;
    assert(pNode != NULL);
H
Haojun Liao 已提交
564

565 566
    while (pNode) {
      pNext = pNode->next;
567
      FREE_HASH_NODE(pHashObj->freeFp, pNode);
H
hjxilinx 已提交
568

569
      pNode = pNext;
570 571
    }

572 573
    pEntry->num = 0;
    pEntry->next = NULL;
574 575
  }

H
Haojun Liao 已提交
576 577
  pHashObj->size = 0;
  taosHashWUnlock(pHashObj);
578 579
}

wafwerar's avatar
wafwerar 已提交
580
// the input paras should be SHashObj **, so the origin input will be set by taosMemoryFreeClear(*pHashObj)
581 582 583 584 585
void taosHashCleanup(SHashObj *pHashObj) {
  if (pHashObj == NULL) {
    return;
  }

586
  taosHashClear(pHashObj);
wafwerar's avatar
wafwerar 已提交
587
  taosMemoryFreeClear(pHashObj->hashList);
H
Haojun Liao 已提交
588 589 590

  // destroy mem block
  size_t memBlock = taosArrayGetSize(pHashObj->pMemBlock);
H
Haojun Liao 已提交
591 592
  for (int32_t i = 0; i < memBlock; ++i) {
    void *p = taosArrayGetP(pHashObj->pMemBlock, i);
wafwerar's avatar
wafwerar 已提交
593
    taosMemoryFreeClear(p);
H
Haojun Liao 已提交
594 595 596
  }

  taosArrayDestroy(pHashObj->pMemBlock);
wafwerar's avatar
wafwerar 已提交
597
  taosMemoryFree(pHashObj);
598 599 600
}

// for profile only
L
Liu Jicong 已提交
601
int32_t taosHashGetMaxOverflowLinkLength(const SHashObj *pHashObj) {
602
  if (pHashObj == NULL || taosHashTableEmpty(pHashObj)) {
603 604
    return 0;
  }
H
hjxilinx 已提交
605

606
  int32_t num = 0;
H
hjxilinx 已提交
607

L
Liu Jicong 已提交
608
  taosHashRLock((SHashObj *)pHashObj);
H
hjxilinx 已提交
609
  for (int32_t i = 0; i < pHashObj->size; ++i) {
H
Haojun Liao 已提交
610
    SHashEntry *pEntry = pHashObj->hashList[i];
H
Haojun Liao 已提交
611 612 613

    // fine grain per entry lock is not held since this is used
    // for profiling only and doesn't need an accurate count.
H
Haojun Liao 已提交
614 615
    if (num < pEntry->num) {
      num = pEntry->num;
616 617
    }
  }
H
hjxilinx 已提交
618

L
Liu Jicong 已提交
619
  taosHashRUnlock((SHashObj *)pHashObj);
620 621
  return num;
}
H
hjLiao 已提交
622 623

void taosHashTableResize(SHashObj *pHashObj) {
H
Haojun Liao 已提交
624
  if (!HASH_NEED_RESIZE(pHashObj)) {
H
hjLiao 已提交
625 626
    return;
  }
H
Haojun Liao 已提交
627

H
Haojun Liao 已提交
628 629
  int32_t newCapacity = (int32_t)(pHashObj->capacity << 1u);
  if (newCapacity > HASH_MAX_CAPACITY) {
L
Liu Jicong 已提交
630 631
    //    uDebug("current capacity:%zu, maximum capacity:%d, no resize applied due to limitation is reached",
    //           pHashObj->capacity, HASH_MAX_CAPACITY);
H
hjLiao 已提交
632 633 634
    return;
  }

H
Haojun Liao 已提交
635
  int64_t st = taosGetTimestampUs();
L
Liu Jicong 已提交
636
  void   *pNewEntryList = taosMemoryRealloc(pHashObj->hashList, sizeof(void *) * newCapacity);
H
Haojun Liao 已提交
637
  if (pNewEntryList == NULL) {
L
Liu Jicong 已提交
638
    //    uDebug("cache resize failed due to out of memory, capacity remain:%zu", pHashObj->capacity);
H
hjLiao 已提交
639 640
    return;
  }
H
Haojun Liao 已提交
641

H
Haojun Liao 已提交
642 643
  pHashObj->hashList = pNewEntryList;

H
Haojun Liao 已提交
644
  size_t inc = newCapacity - pHashObj->capacity;
L
Liu Jicong 已提交
645
  void  *p = taosMemoryCalloc(inc, sizeof(SHashEntry));
H
Haojun Liao 已提交
646

H
Haojun Liao 已提交
647
  for (int32_t i = 0; i < inc; ++i) {
S
Shengliang Guan 已提交
648
    pHashObj->hashList[i + pHashObj->capacity] = (void *)((char *)p + i * sizeof(SHashEntry));
H
Haojun Liao 已提交
649 650 651 652
  }

  taosArrayPush(pHashObj->pMemBlock, &p);

H
Haojun Liao 已提交
653 654 655
  pHashObj->capacity = newCapacity;
  for (int32_t idx = 0; idx < pHashObj->capacity; ++idx) {
    SHashEntry *pe = pHashObj->hashList[idx];
L
Liu Jicong 已提交
656 657 658
    SHashNode  *pNode;
    SHashNode  *pNext;
    SHashNode  *pPrev = NULL;
H
Haojun Liao 已提交
659

H
Haojun Liao 已提交
660
    if (pe->num == 0) {
H
Haojun Liao 已提交
661
      assert(pe->next == NULL);
H
Haojun Liao 已提交
662
      continue;
H
hjLiao 已提交
663
    }
H
Haojun Liao 已提交
664

H
Haojun Liao 已提交
665
    pNode = pe->next;
H
Haojun Liao 已提交
666

H
Haojun Liao 已提交
667
    assert(pNode != NULL);
H
Haojun Liao 已提交
668

H
Haojun Liao 已提交
669 670 671 672 673 674 675
    while (pNode != NULL) {
      int32_t newIdx = HASH_INDEX(pNode->hashVal, pHashObj->capacity);
      pNext = pNode->next;
      if (newIdx != idx) {
        pe->num -= 1;
        if (pPrev == NULL) {
          pe->next = pNext;
H
Haojun Liao 已提交
676
        } else {
H
Haojun Liao 已提交
677
          pPrev->next = pNext;
H
Haojun Liao 已提交
678
        }
H
Haojun Liao 已提交
679

H
Haojun Liao 已提交
680 681
        SHashEntry *pNewEntry = pHashObj->hashList[newIdx];
        pushfrontNodeInEntryList(pNewEntry, pNode);
H
Haojun Liao 已提交
682
      } else {
H
Haojun Liao 已提交
683
        pPrev = pNode;
H
Haojun Liao 已提交
684
      }
H
Haojun Liao 已提交
685
      pNode = pNext;
H
hjLiao 已提交
686 687 688
    }
  }

H
Haojun Liao 已提交
689 690
  int64_t et = taosGetTimestampUs();

L
Liu Jicong 已提交
691 692 693
  //  uDebug("hash table resize completed, new capacity:%d, load factor:%f, elapsed time:%fms",
  //  (int32_t)pHashObj->capacity,
  //         ((double)pHashObj->size) / pHashObj->capacity, (et - st) / 1000.0);
H
hjLiao 已提交
694 695 696
}

SHashNode *doCreateHashNode(const void *key, size_t keyLen, const void *pData, size_t dsize, uint32_t hashVal) {
L
Liu Jicong 已提交
697
  SHashNode *pNewNode = taosMemoryMalloc(sizeof(SHashNode) + keyLen + dsize + 1);
H
Haojun Liao 已提交
698

H
hjLiao 已提交
699
  if (pNewNode == NULL) {
H
Haojun Liao 已提交
700
    terrno = TSDB_CODE_OUT_OF_MEMORY;
H
hjLiao 已提交
701 702
    return NULL;
  }
H
Haojun Liao 已提交
703

L
Liu Jicong 已提交
704
  pNewNode->keyLen = (uint32_t)keyLen;
H
hjLiao 已提交
705
  pNewNode->hashVal = hashVal;
S
hash  
Shengliang Guan 已提交
706
  pNewNode->dataLen = (uint32_t)dsize;
L
Liu Jicong 已提交
707
  pNewNode->refCount = 1;
708
  pNewNode->removed = 0;
L
Liu Jicong 已提交
709
  pNewNode->next = NULL;
H
Haojun Liao 已提交
710 711 712 713

  memcpy(GET_HASH_NODE_DATA(pNewNode), pData, dsize);
  memcpy(GET_HASH_NODE_KEY(pNewNode), key, keyLen);

H
hjLiao 已提交
714 715 716
  return pNewNode;
}

H
Haojun Liao 已提交
717
void pushfrontNodeInEntryList(SHashEntry *pEntry, SHashNode *pNode) {
H
Haojun Liao 已提交
718
  assert(pNode != NULL && pEntry != NULL);
H
Haojun Liao 已提交
719

H
Haojun Liao 已提交
720 721
  pNode->next = pEntry->next;
  pEntry->next = pNode;
H
Haojun Liao 已提交
722

723
  ASSERT(pNode->next != pNode);
H
Haojun Liao 已提交
724
  pEntry->num += 1;
H
hjLiao 已提交
725 726
}

陶建辉(Jeff)'s avatar
陶建辉(Jeff) 已提交
727 728 729 730
size_t taosHashGetMemSize(const SHashObj *pHashObj) {
  if (pHashObj == NULL) {
    return 0;
  }
H
Haojun Liao 已提交
731

L
Liu Jicong 已提交
732 733
  return (pHashObj->capacity * (sizeof(SHashEntry) + sizeof(void *))) + sizeof(SHashNode) * taosHashGetSize(pHashObj) +
         sizeof(SHashObj);
陶建辉(Jeff)'s avatar
陶建辉(Jeff) 已提交
734
}
H
Haojun Liao 已提交
735

L
Liu Jicong 已提交
736 737
void *taosHashGetKey(void *data, size_t *keyLen) {
  SHashNode *node = GET_HASH_PNODE(data);
H
Haojun Liao 已提交
738
  if (keyLen != NULL) {
L
Liu Jicong 已提交
739 740
    *keyLen = node->keyLen;
  }
D
dapan1121 已提交
741

H
Haojun Liao 已提交
742
  return GET_HASH_NODE_KEY(node);
W
wpan 已提交
743 744
}

陶建辉(Jeff)'s avatar
陶建辉(Jeff) 已提交
745
// release the pNode, return next pNode, and lock the current entry
H
Haojun Liao 已提交
746
static void *taosHashReleaseNode(SHashObj *pHashObj, void *p, int *slot) {
陶建辉(Jeff)'s avatar
陶建辉(Jeff) 已提交
747 748 749 750 751 752
  SHashNode *pOld = (SHashNode *)GET_HASH_PNODE(p);
  SHashNode *prevNode = NULL;

  *slot = HASH_INDEX(pOld->hashVal, pHashObj->capacity);
  SHashEntry *pe = pHashObj->hashList[*slot];

H
Haojun Liao 已提交
753
  taosHashEntryWLock(pHashObj, pe);
陶建辉(Jeff)'s avatar
陶建辉(Jeff) 已提交
754 755 756

  SHashNode *pNode = pe->next;
  while (pNode) {
L
Liu Jicong 已提交
757
    if (pNode == pOld) break;
陶建辉(Jeff)'s avatar
陶建辉(Jeff) 已提交
758 759 760 761 762

    prevNode = pNode;
    pNode = pNode->next;
  }

S
hash  
Shengliang Guan 已提交
763
  if (pNode) {
陶建辉(Jeff)'s avatar
陶建辉(Jeff) 已提交
764
    pNode = pNode->next;
陶建辉(Jeff)'s avatar
陶建辉(Jeff) 已提交
765 766 767 768 769
    while (pNode) {
      if (pNode->removed == 0) break;
      pNode = pNode->next;
    }

wafwerar's avatar
wafwerar 已提交
770
    atomic_sub_fetch_16(&pOld->refCount, 1);
L
Liu Jicong 已提交
771
    if (pOld->refCount <= 0) {
陶建辉(Jeff)'s avatar
陶建辉(Jeff) 已提交
772 773
      if (prevNode) {
        prevNode->next = pOld->next;
H
Haojun Liao 已提交
774
        ASSERT(prevNode->next != prevNode);
陶建辉(Jeff)'s avatar
陶建辉(Jeff) 已提交
775 776
      } else {
        pe->next = pOld->next;
H
Haojun Liao 已提交
777
        SHashNode* x = pe->next;
H
Haojun Liao 已提交
778 779 780
        if (x != NULL) {
          ASSERT(x->next != x);
        }
陶建辉(Jeff)'s avatar
陶建辉(Jeff) 已提交
781
      }
S
hash  
Shengliang Guan 已提交
782

陶建辉(Jeff)'s avatar
陶建辉(Jeff) 已提交
783
      pe->num--;
H
Haojun Liao 已提交
784
      atomic_sub_fetch_64(&pHashObj->size, 1);
785
      FREE_HASH_NODE(pHashObj->freeFp, pOld);
S
hash  
Shengliang Guan 已提交
786
    }
陶建辉(Jeff)'s avatar
陶建辉(Jeff) 已提交
787
  } else {
L
Liu Jicong 已提交
788
    //    uError("pNode:%p data:%p is not there!!!", pNode, p);
陶建辉(Jeff)'s avatar
陶建辉(Jeff) 已提交
789 790 791 792 793 794
  }

  return pNode;
}

void *taosHashIterate(SHashObj *pHashObj, void *p) {
S
hash  
Shengliang Guan 已提交
795
  if (pHashObj == NULL) return NULL;
陶建辉(Jeff)'s avatar
陶建辉(Jeff) 已提交
796

L
Liu Jicong 已提交
797
  int   slot = 0;
陶建辉(Jeff)'s avatar
陶建辉(Jeff) 已提交
798 799 800
  char *data = NULL;

  // only add the read lock to disable the resize process
H
Haojun Liao 已提交
801
  taosHashRLock(pHashObj);
陶建辉(Jeff)'s avatar
陶建辉(Jeff) 已提交
802 803 804 805 806 807

  SHashNode *pNode = NULL;
  if (p) {
    pNode = taosHashReleaseNode(pHashObj, p, &slot);
    if (pNode == NULL) {
      SHashEntry *pe = pHashObj->hashList[slot];
H
Haojun Liao 已提交
808
      taosHashEntryWUnlock(pHashObj, pe);
陶建辉(Jeff)'s avatar
陶建辉(Jeff) 已提交
809 810

      slot = slot + 1;
H
Haojun Liao 已提交
811
    }
陶建辉(Jeff)'s avatar
陶建辉(Jeff) 已提交
812
  }
H
Haojun Liao 已提交
813

陶建辉(Jeff)'s avatar
陶建辉(Jeff) 已提交
814 815 816
  if (pNode == NULL) {
    for (; slot < pHashObj->capacity; ++slot) {
      SHashEntry *pe = pHashObj->hashList[slot];
H
Haojun Liao 已提交
817

H
Haojun Liao 已提交
818
      taosHashEntryWLock(pHashObj, pe);
陶建辉(Jeff)'s avatar
陶建辉(Jeff) 已提交
819 820

      pNode = pe->next;
陶建辉(Jeff)'s avatar
陶建辉(Jeff) 已提交
821 822 823 824 825
      while (pNode) {
        if (pNode->removed == 0) break;
        pNode = pNode->next;
      }

陶建辉(Jeff)'s avatar
陶建辉(Jeff) 已提交
826 827
      if (pNode) break;

H
Haojun Liao 已提交
828
      taosHashEntryWUnlock(pHashObj, pe);
H
Haojun Liao 已提交
829
    }
陶建辉(Jeff)'s avatar
陶建辉(Jeff) 已提交
830
  }
H
Haojun Liao 已提交
831

陶建辉(Jeff)'s avatar
陶建辉(Jeff) 已提交
832 833
  if (pNode) {
    SHashEntry *pe = pHashObj->hashList[slot];
834

H
Haojun Liao 已提交
835 836 837
    uint16_t prevRef = atomic_load_16(&pNode->refCount);
    uint16_t afterRef = atomic_add_fetch_16(&pNode->refCount, 1);
    ASSERT(prevRef < afterRef);
838 839 840 841 842

    // the reference count value is overflow, which will cause the delete node operation immediately.
    if (prevRef > afterRef) {
      uError("hash entry ref count overflow, prev ref:%d, current ref:%d", prevRef, afterRef);
      // restore the value
H
Haojun Liao 已提交
843
      atomic_sub_fetch_16(&pNode->refCount, 1);
844 845 846 847 848 849 850 851 852
      data = NULL;
    } else {
      data = GET_HASH_NODE_DATA(pNode);
    }

    if (afterRef >= MAX_WARNING_REF_COUNT) {
      uWarn("hash entry ref count is abnormally high: %d", afterRef);
    }

H
Haojun Liao 已提交
853
    taosHashEntryWUnlock(pHashObj, pe);
H
hjLiao 已提交
854
  }
H
Haojun Liao 已提交
855

H
Haojun Liao 已提交
856
  taosHashRUnlock(pHashObj);
陶建辉(Jeff)'s avatar
陶建辉(Jeff) 已提交
857
  return data;
H
hjLiao 已提交
858
}
H
Haojun Liao 已提交
859

陶建辉(Jeff)'s avatar
陶建辉(Jeff) 已提交
860 861
void taosHashCancelIterate(SHashObj *pHashObj, void *p) {
  if (pHashObj == NULL || p == NULL) return;
H
Haojun Liao 已提交
862

陶建辉(Jeff)'s avatar
陶建辉(Jeff) 已提交
863
  // only add the read lock to disable the resize process
H
Haojun Liao 已提交
864
  taosHashRLock(pHashObj);
陶建辉(Jeff)'s avatar
陶建辉(Jeff) 已提交
865

H
Haojun Liao 已提交
866
  int slot;
陶建辉(Jeff)'s avatar
陶建辉(Jeff) 已提交
867 868 869
  taosHashReleaseNode(pHashObj, p, &slot);

  SHashEntry *pe = pHashObj->hashList[slot];
D
dapan1121 已提交
870

H
Haojun Liao 已提交
871 872 873 874
  taosHashEntryWUnlock(pHashObj, pe);
  taosHashRUnlock(pHashObj);
}

L
Liu Jicong 已提交
875
// TODO remove it
H
Haojun Liao 已提交
876
void *taosHashAcquire(SHashObj *pHashObj, const void *key, size_t keyLen) {
L
Liu Jicong 已提交
877
  void *p = NULL;
H
Haojun Liao 已提交
878
  return taosHashGetImpl(pHashObj, key, keyLen, &p, 0, true);
D
dapan1121 已提交
879 880
}

S
hash  
Shengliang Guan 已提交
881
void taosHashRelease(SHashObj *pHashObj, void *p) { taosHashCancelIterate(pHashObj, p); }