#4917

Committed 07 Jan 2026 03:52PM UTC coverage: 65.42% (+0.02%) from 65.402%

Build # #4917

Build Type

push

travis-ci

Committed by

web-flow

Commit Message

merge: from main to 3.0 branch #34204

Coverage Stats

31 of 34 new or added lines in 2 files covered. (91.18%)

819 existing lines in 129 files now uncovered.

202679 of 309814 relevant lines covered (65.42%)

116724351.99 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

82.57

/source/util/src/tsimplehash.c

/*
 * 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/>.
 */

#include "tsimplehash.h"
#include "taoserror.h"
#include "tlog.h"
#include "tdef.h"

#define DEFAULT_BUF_PAGE_SIZE     1024
#define SHASH_DEFAULT_LOAD_FACTOR 0.75
#define HASH_MAX_CAPACITY         (1024 * 1024 * 16L)
#define SHASH_NEED_RESIZE(_h)     ((_h)->size >= (_h)->capacity * SHASH_DEFAULT_LOAD_FACTOR)

#define GET_SHASH_NODE_DATA(_n)     (((SHNode*)_n)->data)
#define GET_SHASH_NODE_KEY(_n, _dl) ((char*)GET_SHASH_NODE_DATA(_n) + (_dl))

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

#define FREE_HASH_NODE(_n, fp) \
  do {                         \
    if (fp) {                  \
      fp((_n)->data);          \
    }                          \
    taosMemoryFreeClear(_n);   \
  } while (0);

struct SSHashObj {
  SHNode        **hashList;
  size_t          capacity;  // number of slots
  int64_t         size;      // number of elements in hash table
  _hash_fn_t      hashFp;    // hash function
  _equal_fn_t     equalFp;   // equal function
  _hash_free_fn_t freeFp;    // free function
  SArray         *pHashNodeBuf;  // hash node allocation buffer, 1k size of each page by default
  int32_t         offset;        // allocation offset in current page
};

static FORCE_INLINE int32_t taosHashCapacity(int32_t length) {
  int32_t len = (length < HASH_MAX_CAPACITY ? length : HASH_MAX_CAPACITY);

  int32_t i = 4;
  while (i < len) i = (i << 1u);
  return i;
}

SSHashObj *tSimpleHashInit(size_t capacity, _hash_fn_t fn) {
  if (fn == NULL) {
    return NULL;
  }

  if (capacity == 0) {
    capacity = 4;
  }

  SSHashObj *pHashObj = (SSHashObj *)taosMemoryMalloc(sizeof(SSHashObj));
  if (!pHashObj) {
    return NULL;
  }

  // the max slots is not defined by user
  pHashObj->hashFp = fn;
  pHashObj->capacity = taosHashCapacity((int32_t)capacity);
  pHashObj->equalFp = memcmp;

  pHashObj->freeFp = NULL;
  pHashObj->offset = 0;
  pHashObj->size = 0;
  
  pHashObj->hashList = (SHNode **)taosMemoryCalloc(pHashObj->capacity, sizeof(void *));
  if (!pHashObj->hashList) {
    taosMemoryFree(pHashObj);
    return NULL;
  }

  return pHashObj;
}

int32_t tSimpleHashGetSize(const SSHashObj *pHashObj) {
  if (!pHashObj) {
    return 0;
  }
  return (int32_t) pHashObj->size;
}

void tSimpleHashSetFreeFp(SSHashObj* pHashObj, _hash_free_fn_t freeFp) {
  pHashObj->freeFp = freeFp;
}

static void* doInternalAlloc(SSHashObj* pHashObj, int32_t size) {
#if 0
  void** p = taosArrayGetLast(pHashObj->pHashNodeBuf);
  if (p == NULL || (pHashObj->offset + size) > DEFAULT_BUF_PAGE_SIZE) {
    // let's allocate one new page
    int32_t allocSize = TMAX(size, DEFAULT_BUF_PAGE_SIZE);
    void* pNewPage = taosMemoryMalloc(allocSize);
    if (pNewPage == NULL) {
      return NULL;
    }

    // if the allocate the buffer page is greater than the DFFAULT_BUF_PAGE_SIZE,
    // pHashObj->offset will always be greater than DEFAULT_BUF_PAGE_SIZE, which means that
    // current buffer page is full. And a new buffer page needs to be allocated.
    pHashObj->offset = size;
    taosArrayPush(pHashObj->pHashNodeBuf, &pNewPage);
    return pNewPage;
  } else {
    void* pPos = (char*)(*p) + pHashObj->offset;
    pHashObj->offset += size;
    return pPos;
  }
#else
  return taosMemoryMalloc(size);
#endif
}

static SHNode *doCreateHashNode(SSHashObj *pHashObj, const void *key, size_t keyLen, const void *data, size_t dataLen,
                                uint32_t hashVal) {
  SHNode *pNewNode = doInternalAlloc(pHashObj, sizeof(SHNode) + keyLen + dataLen);
  if (!pNewNode) {
    return NULL;
  }

  pNewNode->keyLen = keyLen;
  pNewNode->dataLen = dataLen;
  pNewNode->next = NULL;
  pNewNode->hashVal = hashVal;

  if (data) {
    memcpy(GET_SHASH_NODE_DATA(pNewNode), data, dataLen);
  }

  memcpy(GET_SHASH_NODE_KEY(pNewNode, dataLen), key, keyLen);
  return pNewNode;
}

static int32_t tSimpleHashTableResize(SSHashObj *pHashObj) {
  int32_t code = 0;
  if (!SHASH_NEED_RESIZE(pHashObj)) {
    return code;
  }

  int32_t newCapacity = (int32_t)(pHashObj->capacity << 1u);
  if (newCapacity > HASH_MAX_CAPACITY) {
    uDebug("current capacity:%" PRIzu ", maximum capacity:%" PRId32 ", no resize applied due to limitation is reached",
           pHashObj->capacity, (int32_t)HASH_MAX_CAPACITY);
    return code;
  }

//  int64_t st = taosGetTimestampUs();
  void   *pNewEntryList = taosMemoryRealloc(pHashObj->hashList, POINTER_BYTES * newCapacity);
  if (!pNewEntryList) {
    uWarn("hash resize failed due to out of memory, capacity remain:%zu", pHashObj->capacity);
    return terrno;
  }

  size_t inc = newCapacity - pHashObj->capacity;
  memset((char *)pNewEntryList + pHashObj->capacity * POINTER_BYTES, 0, inc * sizeof(void *));

  pHashObj->hashList = pNewEntryList;
  pHashObj->capacity = newCapacity;

  for (int32_t idx = 0; idx < pHashObj->capacity; ++idx) {
    SHNode *pNode = pHashObj->hashList[idx];
    if (!pNode) {
      continue;
    }

    SHNode *pNext = NULL;
    SHNode *pPrev = NULL;

    while (pNode != NULL) {
      int32_t newIdx = HASH_INDEX(pNode->hashVal, pHashObj->capacity);
      pNext = pNode->next;
      if (newIdx != idx) {
        if (!pPrev) {
          pHashObj->hashList[idx] = pNext;
        } else {
          pPrev->next = pNext;
        }

        pNode->next = pHashObj->hashList[newIdx];
        pHashObj->hashList[newIdx] = pNode;
      } else {
        pPrev = pNode;
      }

      pNode = pNext;
    }
  }

//  int64_t et = taosGetTimestampUs();
  //  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);
  return code;
}

int32_t tSimpleHashPut(SSHashObj *pHashObj, const void *key, size_t keyLen, const void *data, size_t dataLen) {
  if (!pHashObj || !key) {
    return TSDB_CODE_INVALID_PARA;
  }

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

  // need the resize process, write lock applied
  if (SHASH_NEED_RESIZE(pHashObj)) {
    int32_t code = tSimpleHashTableResize(pHashObj);
    if (TSDB_CODE_SUCCESS != code) {
      return code;
    }
  }

  int32_t slot = HASH_INDEX(hashVal, pHashObj->capacity);

  SHNode *pNode = pHashObj->hashList[slot];
  if (!pNode) {
    SHNode *pNewNode = doCreateHashNode(pHashObj, key, keyLen, data, dataLen, hashVal);
    if (!pNewNode) {
      return terrno;
    }

    pHashObj->hashList[slot] = pNewNode;
    pHashObj->size += 1;
    return 0;
  }

  while (pNode) {
    if ((keyLen == pNode->keyLen) && (*(pHashObj->equalFp))(GET_SHASH_NODE_KEY(pNode, pNode->dataLen), key, keyLen) == 0) {
      break;
    }
    pNode = pNode->next;
  }

  if (!pNode) {
    SHNode *pNewNode = doCreateHashNode(pHashObj, key, keyLen, data, dataLen, hashVal);
    if (!pNewNode) {
      return terrno;
    }
    pNewNode->next = pHashObj->hashList[slot];
    pHashObj->hashList[slot] = pNewNode;
    pHashObj->size += 1;
  } else if (data) {  // update data
    memcpy(GET_SHASH_NODE_DATA(pNode), data, dataLen);
  }

  return 0;
}

static FORCE_INLINE SHNode *doSearchInEntryList(SSHashObj *pHashObj, const void *key, size_t keyLen, int32_t index) {
  SHNode *pNode = pHashObj->hashList[index];
  while (pNode) {
    const char *p = GET_SHASH_NODE_KEY(pNode, pNode->dataLen);

    if (pNode->keyLen == keyLen && ((*(pHashObj->equalFp))(p, key, keyLen) == 0)) {
      break;
    }
    pNode = pNode->next;
  }

  return pNode;
}

static FORCE_INLINE bool taosHashTableEmpty(const SSHashObj *pHashObj) { return tSimpleHashGetSize(pHashObj) == 0; }

void *tSimpleHashGet(SSHashObj *pHashObj, const void *key, size_t keyLen) {
  if (!pHashObj || taosHashTableEmpty(pHashObj) || !key) {
    return NULL;
  }

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

  int32_t slot = HASH_INDEX(hashVal, pHashObj->capacity);
  SHNode *pNode = pHashObj->hashList[slot];
  if (!pNode) {
    return NULL;
  }

  char *data = NULL;
  pNode = doSearchInEntryList(pHashObj, key, keyLen, slot);
  if (pNode != NULL) {
    data = GET_SHASH_NODE_DATA(pNode);
  }

  return data;
}

int32_t tSimpleHashRemove(SSHashObj *pHashObj, const void *key, size_t keyLen) {
  int32_t code = TSDB_CODE_INVALID_PARA;
  if (!pHashObj || !key) {
    return code;
  }

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

  int32_t slot = HASH_INDEX(hashVal, pHashObj->capacity);

  SHNode *pNode = pHashObj->hashList[slot];
  SHNode *pPrev = NULL;
  while (pNode) {
    if ((keyLen == pNode->keyLen) && (*(pHashObj->equalFp))(GET_SHASH_NODE_KEY(pNode, pNode->dataLen), key, keyLen) == 0) {
      if (!pPrev) {
        pHashObj->hashList[slot] = pNode->next;
      } else {
        pPrev->next = pNode->next;
      }

      FREE_HASH_NODE(pNode, pHashObj->freeFp);
      pHashObj->size -= 1;
      code = TSDB_CODE_SUCCESS;
      break;
    }
    pPrev = pNode;
    pNode = pNode->next;
  }

  return code;
}

int32_t tSimpleHashIterateRemove(SSHashObj *pHashObj, const void *key, size_t keyLen, void **pIter, int32_t *iter) {
  if (!pHashObj || !key) {
    return TSDB_CODE_FAILED;
  }

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

  int32_t slot = HASH_INDEX(hashVal, pHashObj->capacity);

  SHNode *pNode = pHashObj->hashList[slot];
  SHNode *pPrev = NULL;
  while (pNode) {
    if ((*(pHashObj->equalFp))(GET_SHASH_NODE_KEY(pNode, pNode->dataLen), key, keyLen) == 0) {
      if (!pPrev) {
        pHashObj->hashList[slot] = pNode->next;
      } else {
        pPrev->next = pNode->next;
      }

      if (*pIter == (void *)GET_SHASH_NODE_DATA(pNode)) {
        *pIter = pPrev ? GET_SHASH_NODE_DATA(pPrev) : NULL;
      }

      FREE_HASH_NODE(pNode, pHashObj->freeFp);
      pHashObj->size -= 1;
      break;
    }
    pPrev = pNode;
    pNode = pNode->next;
  }

  return TSDB_CODE_SUCCESS;
}

void tSimpleHashClear(SSHashObj *pHashObj) {
  if (!pHashObj || taosHashTableEmpty(pHashObj)) {
    return;
  }

  SHNode *pNode = NULL, *pNext = NULL;
  for (int32_t i = 0; i < pHashObj->capacity; ++i) {
    pNode = pHashObj->hashList[i];
    if (!pNode) {
      continue;
    }

    while (pNode) {
      pNext = pNode->next;
      FREE_HASH_NODE(pNode, pHashObj->freeFp);
      pNode = pNext;
    }

    pHashObj->hashList[i] = NULL;
  }

  pHashObj->offset = 0;
  pHashObj->size = 0;
}

void tSimpleHashCleanup(SSHashObj *pHashObj) {
  if (!pHashObj) {
    return;
  }

  tSimpleHashClear(pHashObj);
  taosMemoryFreeClear(pHashObj->hashList);
  taosMemoryFree(pHashObj);
}

size_t tSimpleHashGetMemSize(const SSHashObj *pHashObj) {
  if (!pHashObj) {
    return 0;
  }

  return (pHashObj->capacity * sizeof(void *)) + sizeof(SHNode) * tSimpleHashGetSize(pHashObj) + sizeof(SSHashObj);
}

void *tSimpleHashIterate(const SSHashObj *pHashObj, void *data, int32_t *iter) {
  if (!pHashObj) {
    return NULL;
  }

  SHNode *pNode = NULL;

  if (!data) {
    for (int32_t i = *iter; i < pHashObj->capacity; ++i) {
      pNode = pHashObj->hashList[i];
      if (!pNode) {
        continue;
      }
      *iter = i;
      return GET_SHASH_NODE_DATA(pNode);
    }
    return NULL;
  }

  pNode = (SHNode *)((char *)data - offsetof(SHNode, data));

  if (pNode->next) {
    return GET_SHASH_NODE_DATA(pNode->next);
  }

  ++(*iter);
  for (int32_t i = *iter; i < pHashObj->capacity; ++i) {
    pNode = pHashObj->hashList[i];
    if (!pNode) {
      continue;
    }
    *iter = i;
    return GET_SHASH_NODE_DATA(pNode);
  }

  return NULL;
}

1	/*
2	* Copyright (c) 2019 TAOS Data, Inc. <jhtao@taosdata.com>
3	*
4	* This program is free software: you can use, redistribute, and/or modify
5	* it under the terms of the GNU Affero General Public License, version 3
6	* or later ("AGPL"), as published by the Free Software Foundation.
7	*
8	* This program is distributed in the hope that it will be useful, but WITHOUT
9	* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
10	* FITNESS FOR A PARTICULAR PURPOSE.
11	*
12	* You should have received a copy of the GNU Affero General Public License
13	* along with this program. If not, see <http://www.gnu.org/licenses/>.
14	*/
15
16	#include "tsimplehash.h"
17	#include "taoserror.h"
18	#include "tlog.h"
19	#include "tdef.h"
20
21	#define DEFAULT_BUF_PAGE_SIZE 1024
22	#define SHASH_DEFAULT_LOAD_FACTOR 0.75
23	#define HASH_MAX_CAPACITY (1024 * 1024 * 16L)
24	#define SHASH_NEED_RESIZE(_h) ((_h)->size >= (_h)->capacity * SHASH_DEFAULT_LOAD_FACTOR)
25
26	#define GET_SHASH_NODE_DATA(_n) (((SHNode*)_n)->data)
27	#define GET_SHASH_NODE_KEY(_n, _dl) ((char*)GET_SHASH_NODE_DATA(_n) + (_dl))
28
29	#define HASH_INDEX(v, c) ((v) & ((c)-1))
30
31	#define FREE_HASH_NODE(_n, fp) \
32	do { \
33	if (fp) { \
34	fp((_n)->data); \
35	} \
36	taosMemoryFreeClear(_n); \
37	} while (0);
38
39	struct SSHashObj {
40	SHNode **hashList;
41	size_t capacity; // number of slots
42	int64_t size; // number of elements in hash table
43	_hash_fn_t hashFp; // hash function
44	_equal_fn_t equalFp; // equal function
45	_hash_free_fn_t freeFp; // free function
46	SArray *pHashNodeBuf; // hash node allocation buffer, 1k size of each page by default
47	int32_t offset; // allocation offset in current page
48	};
49
50	static FORCE_INLINE int32_t taosHashCapacity(int32_t length) {
51	int32_t len = (length < HASH_MAX_CAPACITY ? length : HASH_MAX_CAPACITY);	1,453,488,049✔
52
53	int32_t i = 4;	1,453,488,049✔
54	while (i < len) i = (i << 1u);	2,147,483,647✔
55	return i;	1,453,488,049✔
56	}
57
58	SSHashObj *tSimpleHashInit(size_t capacity, _hash_fn_t fn) {	1,453,539,333✔
59	if (fn == NULL) {	1,453,539,333✔
60	return NULL;	×
61	}
62
63	if (capacity == 0) {	1,453,539,333✔
64	capacity = 4;	16,576,146✔
65	}
66
67	SSHashObj pHashObj = (SSHashObj )taosMemoryMalloc(sizeof(SSHashObj));	1,453,539,333✔
68	if (!pHashObj) {	1,452,219,571✔
69	return NULL;	×
70	}
71
72	// the max slots is not defined by user
73	pHashObj->hashFp = fn;	1,452,219,571✔
74	pHashObj->capacity = taosHashCapacity((int32_t)capacity);	2,147,483,647✔
75	pHashObj->equalFp = memcmp;	1,453,941,878✔
76
77	pHashObj->freeFp = NULL;	1,454,325,566✔
78	pHashObj->offset = 0;	1,454,455,236✔
79	pHashObj->size = 0;	1,454,522,848✔
80
81	pHashObj->hashList = (SHNode *)taosMemoryCalloc(pHashObj->capacity, sizeof(void ));	1,454,593,044✔
82	if (!pHashObj->hashList) {	1,452,731,366✔
83	taosMemoryFree(pHashObj);	×
84	return NULL;	×
85	}
86
87	return pHashObj;	1,453,156,266✔
88	}
89
90	int32_t tSimpleHashGetSize(const SSHashObj *pHashObj) {	2,147,483,647✔
91	if (!pHashObj) {	2,147,483,647✔
92	return 0;	9,831,652✔
93	}
94	return (int32_t) pHashObj->size;	2,147,483,647✔
95	}
96
97	void tSimpleHashSetFreeFp(SSHashObj* pHashObj, _hash_free_fn_t freeFp) {	267,976,311✔
98	pHashObj->freeFp = freeFp;	267,976,311✔
99	}	268,088,580✔
100
101	static void* doInternalAlloc(SSHashObj* pHashObj, int32_t size) {	2,147,483,647✔
102	#if 0
103	void** p = taosArrayGetLast(pHashObj->pHashNodeBuf);
104	if (p == NULL \|\| (pHashObj->offset + size) > DEFAULT_BUF_PAGE_SIZE) {
105	// let's allocate one new page
106	int32_t allocSize = TMAX(size, DEFAULT_BUF_PAGE_SIZE);
107	void* pNewPage = taosMemoryMalloc(allocSize);
108	if (pNewPage == NULL) {
109	return NULL;
110	}
111
112	// if the allocate the buffer page is greater than the DFFAULT_BUF_PAGE_SIZE,
113	// pHashObj->offset will always be greater than DEFAULT_BUF_PAGE_SIZE, which means that
114	// current buffer page is full. And a new buffer page needs to be allocated.
115	pHashObj->offset = size;
116	taosArrayPush(pHashObj->pHashNodeBuf, &pNewPage);
117	return pNewPage;
118	} else {
119	void* pPos = (char)(p) + pHashObj->offset;
120	pHashObj->offset += size;
121	return pPos;
122	}
123	#else
124	return taosMemoryMalloc(size);	2,147,483,647✔
125	#endif
126	}
127
128	static SHNode doCreateHashNode(SSHashObj pHashObj, const void key, size_t keyLen, const void data, size_t dataLen,	2,147,483,647✔
129	uint32_t hashVal) {
130	SHNode *pNewNode = doInternalAlloc(pHashObj, sizeof(SHNode) + keyLen + dataLen);	2,147,483,647✔
131	if (!pNewNode) {	2,147,483,647✔
132	return NULL;	×
133	}
134
135	pNewNode->keyLen = keyLen;	2,147,483,647✔
136	pNewNode->dataLen = dataLen;	2,147,483,647✔
137	pNewNode->next = NULL;	2,147,483,647✔
138	pNewNode->hashVal = hashVal;	2,147,483,647✔
139
140	if (data) {	2,147,483,647✔
141	memcpy(GET_SHASH_NODE_DATA(pNewNode), data, dataLen);	2,147,483,647✔
142	}
143
144	memcpy(GET_SHASH_NODE_KEY(pNewNode, dataLen), key, keyLen);	2,147,483,647✔
145	return pNewNode;	2,147,483,647✔
146	}
147
148	static int32_t tSimpleHashTableResize(SSHashObj *pHashObj) {	39,038,672✔
149	int32_t code = 0;	39,038,672✔
150	if (!SHASH_NEED_RESIZE(pHashObj)) {	39,038,672✔
151	return code;	×
152	}
153
154	int32_t newCapacity = (int32_t)(pHashObj->capacity << 1u);	39,039,154✔
155	if (newCapacity > HASH_MAX_CAPACITY) {	39,037,850✔
156	uDebug("current capacity:%" PRIzu ", maximum capacity:%" PRId32 ", no resize applied due to limitation is reached",	×
157	pHashObj->capacity, (int32_t)HASH_MAX_CAPACITY);
158	return code;	×
159	}
160
161	// int64_t st = taosGetTimestampUs();
162	void pNewEntryList = taosMemoryRealloc(pHashObj->hashList, POINTER_BYTES newCapacity);	39,037,850✔
163	if (!pNewEntryList) {	39,037,368✔
164	uWarn("hash resize failed due to out of memory, capacity remain:%zu", pHashObj->capacity);	×
165	return terrno;	×
166	}
167
168	size_t inc = newCapacity - pHashObj->capacity;	39,037,368✔
169	memset((char )pNewEntryList + pHashObj->capacity POINTER_BYTES, 0, inc * sizeof(void *));	39,039,298✔
170
171	pHashObj->hashList = pNewEntryList;	39,039,637✔
172	pHashObj->capacity = newCapacity;	39,039,298✔
173
174	for (int32_t idx = 0; idx < pHashObj->capacity; ++idx) {	2,147,483,647✔
175	SHNode *pNode = pHashObj->hashList[idx];	2,147,483,647✔
176	if (!pNode) {	2,147,483,647✔
177	continue;	2,147,483,647✔
178	}
179
180	SHNode *pNext = NULL;	2,147,483,647✔
181	SHNode *pPrev = NULL;	2,147,483,647✔
182
183	while (pNode != NULL) {	2,147,483,647✔
184	int32_t newIdx = HASH_INDEX(pNode->hashVal, pHashObj->capacity);	2,147,483,647✔
185	pNext = pNode->next;	2,147,483,647✔
186	if (newIdx != idx) {	2,147,483,647✔
187	if (!pPrev) {	2,147,483,647✔
188	pHashObj->hashList[idx] = pNext;	2,147,483,647✔
189	} else {
190	pPrev->next = pNext;	675,131,350✔
191	}
192
193	pNode->next = pHashObj->hashList[newIdx];	2,147,483,647✔
194	pHashObj->hashList[newIdx] = pNode;	2,147,483,647✔
195	} else {
196	pPrev = pNode;	2,147,483,647✔
197	}
198
199	pNode = pNext;	2,147,483,647✔
200	}
201	}
202
203	// int64_t et = taosGetTimestampUs();
204	// uDebug("hash table resize completed, new capacity:%d, load factor:%f, elapsed time:%fms",
205	// (int32_t)pHashObj->capacity,
206	// ((double)pHashObj->size) / pHashObj->capacity, (et - st) / 1000.0);
207	return code;	39,038,700✔
208	}
209
210	int32_t tSimpleHashPut(SSHashObj pHashObj, const void key, size_t keyLen, const void *data, size_t dataLen) {	2,147,483,647✔
211	if (!pHashObj \|\| !key) {	2,147,483,647✔
212	return TSDB_CODE_INVALID_PARA;	154,391,699✔
213	}
214
215	uint32_t hashVal = (*pHashObj->hashFp)(key, (uint32_t)keyLen);	2,147,483,647✔
216
217	// need the resize process, write lock applied
218	if (SHASH_NEED_RESIZE(pHashObj)) {	2,147,483,647✔
219	int32_t code = tSimpleHashTableResize(pHashObj);	39,041,036✔
220	if (TSDB_CODE_SUCCESS != code) {	39,038,700✔
221	return code;	×
222	}
223	}
224
225	int32_t slot = HASH_INDEX(hashVal, pHashObj->capacity);	2,147,483,647✔
226
227	SHNode *pNode = pHashObj->hashList[slot];	2,147,483,647✔
228	if (!pNode) {	2,147,483,647✔
229	SHNode *pNewNode = doCreateHashNode(pHashObj, key, keyLen, data, dataLen, hashVal);	2,147,483,647✔
230	if (!pNewNode) {	2,147,483,647✔
UNCOV 231	return terrno;	×
232	}
233
234	pHashObj->hashList[slot] = pNewNode;	2,147,483,647✔
235	pHashObj->size += 1;	2,147,483,647✔
236	return 0;	2,147,483,647✔
237	}
238
239	while (pNode) {	2,147,483,647✔
240	if ((keyLen == pNode->keyLen) && (*(pHashObj->equalFp))(GET_SHASH_NODE_KEY(pNode, pNode->dataLen), key, keyLen) == 0) {	2,147,483,647✔
241	break;	312,131,349✔
242	}
243	pNode = pNode->next;	2,147,483,647✔
244	}
245
246	if (!pNode) {	2,147,483,647✔
247	SHNode *pNewNode = doCreateHashNode(pHashObj, key, keyLen, data, dataLen, hashVal);	2,147,483,647✔
248	if (!pNewNode) {	2,147,483,647✔
249	return terrno;	×
250	}
251	pNewNode->next = pHashObj->hashList[slot];	2,147,483,647✔
252	pHashObj->hashList[slot] = pNewNode;	2,147,483,647✔
253	pHashObj->size += 1;	2,147,483,647✔
254	} else if (data) { // update data	306,489,062✔
255	memcpy(GET_SHASH_NODE_DATA(pNode), data, dataLen);	8,458,779✔
256	}
257
258	return 0;	2,147,483,647✔
259	}
260
261	static FORCE_INLINE SHNode doSearchInEntryList(SSHashObj pHashObj, const void *key, size_t keyLen, int32_t index) {
262	SHNode *pNode = pHashObj->hashList[index];	2,147,483,647✔
263	while (pNode) {	2,147,483,647✔
264	const char *p = GET_SHASH_NODE_KEY(pNode, pNode->dataLen);	2,147,483,647✔
265
266	if (pNode->keyLen == keyLen && ((*(pHashObj->equalFp))(p, key, keyLen) == 0)) {	2,147,483,647✔
267	break;	2,147,483,647✔
268	}
269	pNode = pNode->next;	2,147,483,647✔
270	}
271
272	return pNode;	2,147,483,647✔
273	}
274
275	static FORCE_INLINE bool taosHashTableEmpty(const SSHashObj *pHashObj) { return tSimpleHashGetSize(pHashObj) == 0; }	2,147,483,647✔
276
277	void tSimpleHashGet(SSHashObj pHashObj, const void *key, size_t keyLen) {	2,147,483,647✔
278	if (!pHashObj \|\| taosHashTableEmpty(pHashObj) \|\| !key) {	2,147,483,647✔
279	return NULL;	282,064,196✔
280	}
281
282	uint32_t hashVal = (*pHashObj->hashFp)(key, (uint32_t)keyLen);	2,147,483,647✔
283
284	int32_t slot = HASH_INDEX(hashVal, pHashObj->capacity);	2,147,483,647✔
285	SHNode *pNode = pHashObj->hashList[slot];	2,147,483,647✔
286	if (!pNode) {	2,147,483,647✔
287	return NULL;	2,147,483,647✔
288	}
289
290	char *data = NULL;	2,147,483,647✔
291	pNode = doSearchInEntryList(pHashObj, key, keyLen, slot);	2,147,483,647✔
292	if (pNode != NULL) {	2,147,483,647✔
293	data = GET_SHASH_NODE_DATA(pNode);	2,147,483,647✔
294	}
295
296	return data;	2,147,483,647✔
297	}
298
299	int32_t tSimpleHashRemove(SSHashObj pHashObj, const void key, size_t keyLen) {	827,037✔
300	int32_t code = TSDB_CODE_INVALID_PARA;	827,037✔
301	if (!pHashObj \|\| !key) {	827,037✔
302	return code;	×
303	}
304
305	uint32_t hashVal = (*pHashObj->hashFp)(key, (uint32_t)keyLen);	827,037✔
306
307	int32_t slot = HASH_INDEX(hashVal, pHashObj->capacity);	827,037✔
308
309	SHNode *pNode = pHashObj->hashList[slot];	827,037✔
310	SHNode *pPrev = NULL;	827,037✔
311	while (pNode) {	827,753✔
312	if ((keyLen == pNode->keyLen) && (*(pHashObj->equalFp))(GET_SHASH_NODE_KEY(pNode, pNode->dataLen), key, keyLen) == 0) {	827,753✔
313	if (!pPrev) {	827,037✔
314	pHashObj->hashList[slot] = pNode->next;	826,321✔
315	} else {
316	pPrev->next = pNode->next;	716✔
317	}
318
319	FREE_HASH_NODE(pNode, pHashObj->freeFp);	827,037✔
320	pHashObj->size -= 1;	827,037✔
321	code = TSDB_CODE_SUCCESS;	826,421✔
322	break;	826,421✔
323	}
324	pPrev = pNode;	716✔
325	pNode = pNode->next;	716✔
326	}
327
328	return code;	826,421✔
329	}
330
331	int32_t tSimpleHashIterateRemove(SSHashObj pHashObj, const void key, size_t keyLen, void *pIter, int32_t iter) {	×
332	if (!pHashObj \|\| !key) {	×
333	return TSDB_CODE_FAILED;	×
334	}
335
336	uint32_t hashVal = (*pHashObj->hashFp)(key, (uint32_t)keyLen);	×
337
338	int32_t slot = HASH_INDEX(hashVal, pHashObj->capacity);	×
339
340	SHNode *pNode = pHashObj->hashList[slot];	×
341	SHNode *pPrev = NULL;	×
342	while (pNode) {	×
343	if ((*(pHashObj->equalFp))(GET_SHASH_NODE_KEY(pNode, pNode->dataLen), key, keyLen) == 0) {	×
344	if (!pPrev) {	×
345	pHashObj->hashList[slot] = pNode->next;	×
346	} else {
347	pPrev->next = pNode->next;	×
348	}
349
350	if (pIter == (void )GET_SHASH_NODE_DATA(pNode)) {	×
351	*pIter = pPrev ? GET_SHASH_NODE_DATA(pPrev) : NULL;	×
352	}
353
354	FREE_HASH_NODE(pNode, pHashObj->freeFp);	×
355	pHashObj->size -= 1;	×
356	break;	×
357	}
358	pPrev = pNode;	×
359	pNode = pNode->next;	×
360	}
361
362	return TSDB_CODE_SUCCESS;	×
363	}
364
365	void tSimpleHashClear(SSHashObj *pHashObj) {	1,493,916,943✔
366	if (!pHashObj \|\| taosHashTableEmpty(pHashObj)) {	2,147,483,647✔
367	return;	477,696,278✔
368	}
369
370	SHNode pNode = NULL, pNext = NULL;	1,016,385,148✔
371	for (int32_t i = 0; i < pHashObj->capacity; ++i) {	2,147,483,647✔
372	pNode = pHashObj->hashList[i];	2,147,483,647✔
373	if (!pNode) {	2,147,483,647✔
374	continue;	2,147,483,647✔
375	}
376
377	while (pNode) {	2,147,483,647✔
378	pNext = pNode->next;	2,147,483,647✔
379	FREE_HASH_NODE(pNode, pHashObj->freeFp);	2,147,483,647✔
380	pNode = pNext;	2,147,483,647✔
381	}
382
383	pHashObj->hashList[i] = NULL;	2,147,483,647✔
384	}
385
386	pHashObj->offset = 0;	1,016,325,220✔
387	pHashObj->size = 0;	1,016,346,656✔
388	}
389
390	void tSimpleHashCleanup(SSHashObj *pHashObj) {	2,147,483,647✔
391	if (!pHashObj) {	2,147,483,647✔
392	return;	1,539,948,704✔
393	}
394
395	tSimpleHashClear(pHashObj);	1,454,874,151✔
396	taosMemoryFreeClear(pHashObj->hashList);	1,455,112,923✔
397	taosMemoryFree(pHashObj);	1,454,901,264✔
398	}
399
400	size_t tSimpleHashGetMemSize(const SSHashObj *pHashObj) {	×
401	if (!pHashObj) {	×
402	return 0;	×
403	}
404
405	return (pHashObj->capacity * sizeof(void )) + sizeof(SHNode) tSimpleHashGetSize(pHashObj) + sizeof(SSHashObj);	×
406	}
407
408	void tSimpleHashIterate(const SSHashObj pHashObj, void data, int32_t iter) {	2,147,483,647✔
409	if (!pHashObj) {	2,147,483,647✔
410	return NULL;	6,677,441✔
411	}
412
413	SHNode *pNode = NULL;	2,147,483,647✔
414
415	if (!data) {	2,147,483,647✔
416	for (int32_t i = *iter; i < pHashObj->capacity; ++i) {	2,147,483,647✔
417	pNode = pHashObj->hashList[i];	2,147,483,647✔
418	if (!pNode) {	2,147,483,647✔
419	continue;	2,147,483,647✔
420	}
421	*iter = i;	902,054,536✔
422	return GET_SHASH_NODE_DATA(pNode);	902,035,697✔
423	}
424	return NULL;	86,365,676✔
425	}
426
427	pNode = (SHNode )((char )data - offsetof(SHNode, data));	2,147,483,647✔
428
429	if (pNode->next) {	2,147,483,647✔
430	return GET_SHASH_NODE_DATA(pNode->next);	2,147,483,647✔
431	}
432
433	++(*iter);	2,147,483,647✔
434	for (int32_t i = *iter; i < pHashObj->capacity; ++i) {	2,147,483,647✔
435	pNode = pHashObj->hashList[i];	2,147,483,647✔
436	if (!pNode) {	2,147,483,647✔
437	continue;	2,147,483,647✔
438	}
439	*iter = i;	2,147,483,647✔
440	return GET_SHASH_NODE_DATA(pNode);	2,147,483,647✔
441	}
442
443	return NULL;	852,874,901✔
444	}

taosdata / TDengine / #4917

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous