thash.h 6.5 KB
Newer Older
H
Haojun Liao 已提交
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
/*
 * 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/>.
 */

#ifndef TDENGINE_HASH_H
#define TDENGINE_HASH_H

#ifdef __cplusplus
extern "C" {
#endif

#include "tarray.h"
#include "tlockfree.h"

typedef uint32_t (*_hash_fn_t)(const char *, uint32_t);
H
Haojun Liao 已提交
27
typedef int32_t  (*_equal_fn_t)(const void*, const void*, size_t len);
H
Haojun Liao 已提交
28 29 30 31 32 33 34 35
typedef void (*_hash_before_fn_t)(void *);
typedef void (*_hash_free_fn_t)(void *);

#define HASH_MAX_CAPACITY (1024 * 1024 * 16)
#define HASH_DEFAULT_LOAD_FACTOR (0.75)

#define HASH_INDEX(v, c) ((v) & ((c)-1))

D
dapan1121 已提交
36 37
#define HASH_NODE_EXIST(code) (code == -2)

H
Haojun Liao 已提交
38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126
/**
 * murmur hash algorithm
 * @key  usually string
 * @len  key length
 * @seed hash seed
 * @out  an int32 value
 */
uint32_t MurmurHash3_32(const char *key, uint32_t len);

/**
 *
 * @param key
 * @param len
 * @return
 */
uint32_t taosIntHash_32(const char *key, uint32_t len);
uint32_t taosIntHash_64(const char *key, uint32_t len);

_hash_fn_t taosGetDefaultHashFunction(int32_t type);

typedef struct SHashNode {
  struct 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          count;       // reference count
  int8_t            removed;     // flag to indicate removed
  char              data[];
} SHashNode;

#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)))

typedef enum SHashLockTypeE {
  HASH_NO_LOCK     = 0,
  HASH_ENTRY_LOCK  = 1,
} SHashLockTypeE;

typedef struct SHashEntry {
  int32_t    num;      // number of elements in current entry
  SRWLatch   latch;    // entry latch
  SHashNode *next;
} SHashEntry;

typedef struct SHashObj {
  SHashEntry    **hashList;
  uint32_t        capacity;     // number of slots
  uint32_t        size;         // number of elements in hash table

  _hash_fn_t      hashFp;       // hash function
  _hash_free_fn_t freeFp;       // hash node free callback function
  _equal_fn_t     equalFp;      // equal function
  _hash_before_fn_t callbackFp; // function invoked before return the value to caller

  SRWLatch        lock;         // read-write spin lock
  SHashLockTypeE  type;         // lock type
  bool            enableUpdate; // enable update
  SArray         *pMemBlock;    // memory block allocated for SHashEntry
} SHashObj;

/**
 * init the hash table
 *
 * @param capacity    initial capacity of the hash table
 * @param fn          hash function to generate the hash value
 * @param threadsafe  thread safe or not
 * @return
 */
SHashObj *taosHashInit(size_t capacity, _hash_fn_t fn, bool update, SHashLockTypeE type);

/**
 * return the size of hash table
 * @param pHashObj
 * @return
 */
int32_t taosHashGetSize(const SHashObj *pHashObj);

/**
 * put element into hash table, if the element with the same key exists, update it
 * @param pHashObj
 * @param key
 * @param keyLen
 * @param data
 * @param size
 * @return
 */
int32_t taosHashPut(SHashObj *pHashObj, const void *key, size_t keyLen, void *data, size_t size);

D
dapan1121 已提交
127 128 129
int32_t taosHashPutExt(SHashObj *pHashObj, const void *key, size_t keyLen, void *data, size_t size, bool *newAdded);


H
Haojun Liao 已提交
130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149
/**
 * return the payload data with the specified key
 *
 * @param pHashObj
 * @param key
 * @param keyLen
 * @return
 */
void *taosHashGet(SHashObj *pHashObj, const void *key, size_t keyLen);

/**
 * Clone the result to destination buffer
 * @param pHashObj
 * @param key
 * @param keyLen
 * @param destBuf
 * @return
 */
void *taosHashGetClone(SHashObj *pHashObj, const void *key, size_t keyLen, void* destBuf);

D
dapan1121 已提交
150 151 152 153 154 155 156 157 158 159
/**
 * Clone the result to interval allocated buffer
 * @param pHashObj
 * @param key
 * @param keyLen
 * @param destBuf
 * @return
 */
void* taosHashGetCloneExt(SHashObj *pHashObj, const void *key, size_t keyLen, void (*fp)(void *), void** d, size_t *sz);

H
Haojun Liao 已提交
160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213
/**
 * remove item with the specified key
 * @param pHashObj
 * @param key
 * @param keyLen
 */
int32_t taosHashRemove(SHashObj *pHashObj, const void *key, size_t keyLen);

/**
 * Clear the hash table.
 * @param pHashObj
 */
void taosHashClear(SHashObj *pHashObj);

/**
 * Clean up hash table and release all allocated resources.
 * @param handle
 */
void taosHashCleanup(SHashObj *pHashObj);

/**
 * Get the max overflow link list length
 * @param pHashObj
 * @return
 */
int32_t taosHashGetMaxOverflowLinkLength(const SHashObj *pHashObj);

/**
 * Get the hash table size
 * @param pHashObj
 * @return
 */
size_t taosHashGetMemSize(const SHashObj *pHashObj);

/**
 * Create the hash table iterator
 * @param pHashObj
 * @param p
 * @return
 */
void *taosHashIterate(SHashObj *pHashObj, void *p);

/**
 * Cancel the hash table iterator
 * @param pHashObj
 * @param p
 */
void  taosHashCancelIterate(SHashObj *pHashObj, void *p);

/**
 * Get the corresponding key information for a given data in hash table
 * @param data
 * @return
 */
D
dapan1121 已提交
214
int32_t taosHashGetKey(void *data, void** key, size_t* keyLen);
H
Haojun Liao 已提交
215

L
Liu Jicong 已提交
216

L
Liu Jicong 已提交
217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234
/**
 * Get the corresponding key information for a given data in hash table, using memcpy
 * @param data
 * @param dst
 * @return
 */
static FORCE_INLINE int32_t taosHashCopyKey(void *data, void* dst) {
  if (NULL == data || NULL == dst) {
    return -1;
  }
  
  SHashNode * node = GET_HASH_PNODE(data);
  void* key = GET_HASH_NODE_KEY(node);
  memcpy(dst, key, node->keyLen);

  return 0;
}

L
Liu Jicong 已提交
235 236 237 238 239 240 241
/**
 * Get the corresponding data length for a given data in hash table
 * @param data
 * @return
 */
int32_t taosHashGetDataLen(void *data);

D
dapan1121 已提交
242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261
/**
 * return the payload data with the specified key(reference number added)
 *
 * @param pHashObj
 * @param key
 * @param keyLen
 * @return
 */
void* taosHashAcquire(SHashObj *pHashObj, const void *key, size_t keyLen);

/**
 * release the prevous acquired obj
 *
 * @param pHashObj
 * @param data
 * @return
 */
void taosHashRelease(SHashObj *pHashObj, void *p);


H
Haojun Liao 已提交
262 263 264 265 266
#ifdef __cplusplus
}
#endif

#endif  // TDENGINE_HASH_H