#3798

Committed 31 Mar 2025 10:39AM UTC coverage: 9.424% (-20.9%) from 30.372%

Build # #3798

Build Type

push

travis-ci

Committed by

happyguoxy

Commit Message

test:add test cases

Coverage Stats

21549 of 307601 branches covered (7.01%)

Branch coverage included in aggregate %.

36084 of 303967 relevant lines covered (11.87%)

58620.7 hits per line

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

52.26

/source/util/src/thashutil.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/>.
 */

#define _DEFAULT_SOURCE
#include "tcompare.h"
#include "tutil.h"
#include "thash.h"
#include "types.h"
#include "xxhash.h"

#define ROTL32(x, r) ((x) << (r) | (x) >> (32u - (r)))

#define DLT  (FLT_COMPAR_TOL_FACTOR * FLT_EPSILON)
#define BASE 1000

#define FMIX32(h)      \
  do {                 \
    (h) ^= (h) >> 16;  \
    (h) *= 0x85ebca6b; \
    (h) ^= (h) >> 13;  \
    (h) *= 0xc2b2ae35; \
    (h) ^= (h) >> 16;  \
  } while (0)

uint32_t taosFastHash(const char *key, uint32_t len) {
  uint32_t result = 0x55555555;
  for (uint32_t i = 0; i < len; i++) {
    result ^= (uint8_t)key[i];
    result = ROTL32(result, 5);
  }
  return result;
}

uint32_t taosDJB2Hash(const char *key, uint32_t len) {
  uint32_t hash = 5381;
  for (uint32_t i = 0; i < len; i++) {
    hash = ((hash << 5) + hash) + (uint8_t)key[i]; /* hash * 33 + c */
  }
  return hash;
}

uint32_t MurmurHash3_32(const char *key, uint32_t len) {
  const uint8_t *data = (const uint8_t *)key;
  const int32_t  nblocks = len >> 2u;

  uint32_t h1 = 0x12345678;

  const uint32_t c1 = 0xcc9e2d51;
  const uint32_t c2 = 0x1b873593;

  const uint32_t *blocks = (const uint32_t *)(data + nblocks * 4);

  for (int32_t i = -nblocks; i; i++) {
    uint32_t k1 = blocks[i];

    k1 *= c1;
    k1 = ROTL32(k1, 15u);
    k1 *= c2;

    h1 ^= k1;
    h1 = ROTL32(h1, 13u);
    h1 = h1 * 5 + 0xe6546b64;
  }

  const uint8_t *tail = (data + nblocks * 4);

  uint32_t k1 = 0;

  switch (len & 3u) {
    case 3:
      k1 ^= tail[2] << 16;
    case 2:
      k1 ^= tail[1] << 8;
    case 1:
      k1 ^= tail[0];
      k1 *= c1;
      k1 = ROTL32(k1, 15u);
      k1 *= c2;
      h1 ^= k1;
  };

  h1 ^= len;

  FMIX32(h1);

  return h1;
}

uint64_t MurmurHash3_64(const char *key, uint32_t len) {
  const uint64_t m = 0x87c37b91114253d5;
  const int      r = 47;
  uint32_t       seed = 0x12345678;
  uint64_t       h = seed ^ (len * m);
  const uint8_t *data = (const uint8_t *)key;
  const uint8_t *end = data + (len - (len & 7));

  while (data != end) {
#ifndef NO_UNALIGNED_ACCESS
    uint64_t k = *((uint64_t *)data);
#else
    uint64_t k = 0;
    memcpy(&k, data, sizeof(uint64_t));
#endif
    k *= m;
    k ^= k >> r;
    k *= m;
    h ^= k;
    h *= m;
    data += 8;
  }

  switch (len & 7) {
    case 7:
      h ^= (uint64_t)data[6] << 48; /* fall-thru */
    case 6:
      h ^= (uint64_t)data[5] << 40; /* fall-thru */
    case 5:
      h ^= (uint64_t)data[4] << 32; /* fall-thru */
    case 4:
      h ^= (uint64_t)data[3] << 24; /* fall-thru */
    case 3:
      h ^= (uint64_t)data[2] << 16; /* fall-thru */
    case 2:
      h ^= (uint64_t)data[1] << 8; /* fall-thru */
    case 1:
      h ^= (uint64_t)data[0];
      h *= m; /* fall-thru */
  };

  h ^= h >> r;
  h *= m;
  h ^= h >> r;
  return h;
}

uint32_t taosIntHash_32(const char *key, uint32_t UNUSED_PARAM(len)) { return *(uint32_t *)key; }
uint32_t taosIntHash_16(const char *key, uint32_t UNUSED_PARAM(len)) { return *(uint16_t *)key; }
uint32_t taosIntHash_8(const char *key, uint32_t UNUSED_PARAM(len)) { return *(uint8_t *)key; }
uint32_t taosFloatHash(const char *key, uint32_t UNUSED_PARAM(len)) {
  float f = GET_FLOAT_VAL(key);
  if (isnan(f)) {
    return 0x7fc00000;
  }

  if (FLT_EQUAL(f, 0.0)) {
    return 0;
  }
  if (fabs(f) < FLT_MAX / BASE - DLT) {
    int32_t t = (int32_t)(round(BASE * (f + DLT)));
    return (uint32_t)t;
  } else {
    return 0x7fc00000;
  }
}
uint32_t taosDoubleHash(const char *key, uint32_t UNUSED_PARAM(len)) {
  double f = GET_DOUBLE_VAL(key);
  if (isnan(f)) {
    return 0x7fc00000;
  }

  if (DBL_EQUAL(f, 0.0)) {
    return 0;
  }
  if (fabs(f) < DBL_MAX / BASE - DLT) {
    uint64_t bits;
    memcpy(&bits, &f, sizeof(double));
    return (uint32_t)(bits ^ (bits >> 32));
  } else {
    return 0x7fc00000;
  }
}
uint32_t taosIntHash_64(const char *key, uint32_t UNUSED_PARAM(len)) {
  uint64_t val = taosGetUInt64Aligned((uint64_t *)key);

  uint64_t hash = val >> 16U;
  hash += (val & 0xFFFFU);

  return (uint32_t)hash;
}

_hash_fn_t taosGetDefaultHashFunction(int32_t type) {
  _hash_fn_t fn = NULL;
  switch (type) {
    case TSDB_DATA_TYPE_TIMESTAMP:
    case TSDB_DATA_TYPE_UBIGINT:
    case TSDB_DATA_TYPE_BIGINT:
      fn = taosIntHash_64;
      break;
    case TSDB_DATA_TYPE_BINARY:
    case TSDB_DATA_TYPE_VARBINARY:
    case TSDB_DATA_TYPE_NCHAR:
    case TSDB_DATA_TYPE_GEOMETRY:
      fn = MurmurHash3_32;
      break;
    case TSDB_DATA_TYPE_UINT:
    case TSDB_DATA_TYPE_INT:
      fn = taosIntHash_32;
      break;
    case TSDB_DATA_TYPE_SMALLINT:
    case TSDB_DATA_TYPE_USMALLINT:
      fn = taosIntHash_16;
      break;
    case TSDB_DATA_TYPE_BOOL:
    case TSDB_DATA_TYPE_UTINYINT:
    case TSDB_DATA_TYPE_TINYINT:
      fn = taosIntHash_8;
      break;
    case TSDB_DATA_TYPE_FLOAT:
      fn = taosFloatHash;
      break;
    case TSDB_DATA_TYPE_DOUBLE:
      fn = taosDoubleHash;
      break;
    default:
      fn = taosIntHash_32;
      break;
  }

  return fn;
}

int32_t taosFloatEqual(const void *a, const void *b, size_t UNUSED_PARAM(sz)) {
  // getComparFunc(TSDB_DATA_TYPE_FLOAT, -1) will always get function compareFloatVal, which will never be NULL.
  return getComparFunc(TSDB_DATA_TYPE_FLOAT, -1)(a, b);
}

int32_t taosDoubleEqual(const void *a, const void *b, size_t UNUSED_PARAM(sz)) {
  // getComparFunc(TSDB_DATA_TYPE_DOUBLE, -1) will always get function compareDoubleVal, which will never be NULL.
  return getComparFunc(TSDB_DATA_TYPE_DOUBLE, -1)(a, b);
}

int32_t taosDecimalEqual(const void* a, const void* b, size_t UNUSED_PARAM(sz)) {
  return 0;
}

_equal_fn_t taosGetDefaultEqualFunction(int32_t type) {
  _equal_fn_t fn = NULL;
  switch (type) {
    case TSDB_DATA_TYPE_FLOAT:
      fn = taosFloatEqual;
      break;
    case TSDB_DATA_TYPE_DOUBLE:
      fn = taosDoubleEqual;
      break;
    case TSDB_DATA_TYPE_DECIMAL64:
    case TSDB_DATA_TYPE_DECIMAL:
      fn = memcmp;
      break;
    default:
      fn = memcmp;
      break;
  }
  return fn;
}

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	#define _DEFAULT_SOURCE
17	#include "tcompare.h"
18	#include "tutil.h"
19	#include "thash.h"
20	#include "types.h"
21	#include "xxhash.h"
22
23	#define ROTL32(x, r) ((x) << (r) \| (x) >> (32u - (r)))
24
25	#define DLT (FLT_COMPAR_TOL_FACTOR * FLT_EPSILON)
26	#define BASE 1000
27
28	#define FMIX32(h) \
29	do { \
30	(h) ^= (h) >> 16; \
31	(h) *= 0x85ebca6b; \
32	(h) ^= (h) >> 13; \
33	(h) *= 0xc2b2ae35; \
34	(h) ^= (h) >> 16; \
35	} while (0)
36
37	uint32_t taosFastHash(const char *key, uint32_t len) {	×
38	uint32_t result = 0x55555555;	×
39	for (uint32_t i = 0; i < len; i++) {	×
40	result ^= (uint8_t)key[i];	×
41	result = ROTL32(result, 5);	×
42	}
43	return result;	×
44	}
45
46	uint32_t taosDJB2Hash(const char *key, uint32_t len) {	×
47	uint32_t hash = 5381;	×
48	for (uint32_t i = 0; i < len; i++) {	×
49	hash = ((hash << 5) + hash) + (uint8_t)key[i]; /* hash * 33 + c */	×
50	}
51	return hash;	×
52	}
53
54	uint32_t MurmurHash3_32(const char *key, uint32_t len) {	316,680✔
55	const uint8_t data = (const uint8_t )key;	316,680✔
56	const int32_t nblocks = len >> 2u;	316,680✔
57
58	uint32_t h1 = 0x12345678;	316,680✔
59
60	const uint32_t c1 = 0xcc9e2d51;	316,680✔
61	const uint32_t c2 = 0x1b873593;	316,680✔
62
63	const uint32_t blocks = (const uint32_t )(data + nblocks * 4);	316,680✔
64
65	for (int32_t i = -nblocks; i; i++) {	1,780,212✔
66	uint32_t k1 = blocks[i];	1,463,532✔
67
68	k1 *= c1;	1,463,532✔
69	k1 = ROTL32(k1, 15u);	1,463,532✔
70	k1 *= c2;	1,463,532✔
71
72	h1 ^= k1;	1,463,532✔
73	h1 = ROTL32(h1, 13u);	1,463,532✔
74	h1 = h1 * 5 + 0xe6546b64;	1,463,532✔
75	}
76
77	const uint8_t tail = (data + nblocks 4);	316,680✔
78
79	uint32_t k1 = 0;	316,680✔
80
81	switch (len & 3u) {	316,680✔
82	case 3:	53,540✔
83	k1 ^= tail[2] << 16;	53,540✔
84	case 2:	155,130✔
85	k1 ^= tail[1] << 8;	155,130✔
86	case 1:	226,761✔
87	k1 ^= tail[0];	226,761✔
88	k1 *= c1;	226,761✔
89	k1 = ROTL32(k1, 15u);	226,761✔
90	k1 *= c2;	226,761✔
91	h1 ^= k1;	226,761✔
92	};
93
94	h1 ^= len;	316,680✔
95
96	FMIX32(h1);	316,680✔
97
98	return h1;	316,680✔
99	}
100
101	uint64_t MurmurHash3_64(const char *key, uint32_t len) {	22,440✔
102	const uint64_t m = 0x87c37b91114253d5;	22,440✔
103	const int r = 47;	22,440✔
104	uint32_t seed = 0x12345678;	22,440✔
105	uint64_t h = seed ^ (len * m);	22,440✔
106	const uint8_t data = (const uint8_t )key;	22,440✔
107	const uint8_t *end = data + (len - (len & 7));	22,440✔
108
109	while (data != end) {	93,246✔
110	#ifndef NO_UNALIGNED_ACCESS
111	uint64_t k = ((uint64_t )data);	70,806✔
112	#else
113	uint64_t k = 0;
114	memcpy(&k, data, sizeof(uint64_t));
115	#endif
116	k *= m;	70,806✔
117	k ^= k >> r;	70,806✔
118	k *= m;	70,806✔
119	h ^= k;	70,806✔
120	h *= m;	70,806✔
121	data += 8;	70,806✔
122	}
123
124	switch (len & 7) {	22,440✔
125	case 7:	2,460✔
126	h ^= (uint64_t)data[6] << 48; /* fall-thru */	2,460✔
127	case 6:	4,557✔
128	h ^= (uint64_t)data[5] << 40; /* fall-thru */	4,557✔
129	case 5:	9,650✔
130	h ^= (uint64_t)data[4] << 32; /* fall-thru */	9,650✔
131	case 4:	13,728✔
132	h ^= (uint64_t)data[3] << 24; /* fall-thru */	13,728✔
133	case 3:	15,662✔
134	h ^= (uint64_t)data[2] << 16; /* fall-thru */	15,662✔
135	case 2:	18,715✔
136	h ^= (uint64_t)data[1] << 8; /* fall-thru */	18,715✔
137	case 1:	20,716✔
138	h ^= (uint64_t)data[0];	20,716✔
139	h = m; / fall-thru */	20,716✔
140	};
141
142	h ^= h >> r;	22,440✔
143	h *= m;	22,440✔
144	h ^= h >> r;	22,440✔
145	return h;	22,440✔
146	}
147
148	uint32_t taosIntHash_32(const char key, uint32_t UNUSED_PARAM(len)) { return (uint32_t *)key; }	16,809✔
149	uint32_t taosIntHash_16(const char key, uint32_t UNUSED_PARAM(len)) { return (uint16_t *)key; }	×
150	uint32_t taosIntHash_8(const char key, uint32_t UNUSED_PARAM(len)) { return (uint8_t *)key; }	×
151	uint32_t taosFloatHash(const char *key, uint32_t UNUSED_PARAM(len)) {	×
152	float f = GET_FLOAT_VAL(key);	×
153	if (isnan(f)) {	×
154	return 0x7fc00000;	×
155	}
156
157	if (FLT_EQUAL(f, 0.0)) {	×
158	return 0;	×
159	}
160	if (fabs(f) < FLT_MAX / BASE - DLT) {	×
161	int32_t t = (int32_t)(round(BASE * (f + DLT)));	×
162	return (uint32_t)t;	×
163	} else {
164	return 0x7fc00000;	×
165	}
166	}
167	uint32_t taosDoubleHash(const char *key, uint32_t UNUSED_PARAM(len)) {	×
168	double f = GET_DOUBLE_VAL(key);	×
169	if (isnan(f)) {	×
170	return 0x7fc00000;	×
171	}
172
173	if (DBL_EQUAL(f, 0.0)) {	×
174	return 0;	×
175	}
176	if (fabs(f) < DBL_MAX / BASE - DLT) {	×
177	uint64_t bits;
178	memcpy(&bits, &f, sizeof(double));	×
179	return (uint32_t)(bits ^ (bits >> 32));	×
180	} else {
181	return 0x7fc00000;	×
182	}
183	}
184	uint32_t taosIntHash_64(const char *key, uint32_t UNUSED_PARAM(len)) {	65,418✔
185	uint64_t val = taosGetUInt64Aligned((uint64_t *)key);	65,418✔
186
187	uint64_t hash = val >> 16U;	65,418✔
188	hash += (val & 0xFFFFU);	65,418✔
189
190	return (uint32_t)hash;	65,418✔
191	}
192
193	_hash_fn_t taosGetDefaultHashFunction(int32_t type) {	81,789✔
194	_hash_fn_t fn = NULL;	81,789✔
195	switch (type) {	81,789!
196	case TSDB_DATA_TYPE_TIMESTAMP:	20,128✔
197	case TSDB_DATA_TYPE_UBIGINT:
198	case TSDB_DATA_TYPE_BIGINT:
199	fn = taosIntHash_64;	20,128✔
200	break;	20,128✔
201	case TSDB_DATA_TYPE_BINARY:	44,268✔
202	case TSDB_DATA_TYPE_VARBINARY:
203	case TSDB_DATA_TYPE_NCHAR:
204	case TSDB_DATA_TYPE_GEOMETRY:
205	fn = MurmurHash3_32;	44,268✔
206	break;	44,268✔
207	case TSDB_DATA_TYPE_UINT:	17,395✔
208	case TSDB_DATA_TYPE_INT:
209	fn = taosIntHash_32;	17,395✔
210	break;	17,395✔
211	case TSDB_DATA_TYPE_SMALLINT:	×
212	case TSDB_DATA_TYPE_USMALLINT:
213	fn = taosIntHash_16;	×
214	break;	×
215	case TSDB_DATA_TYPE_BOOL:	×
216	case TSDB_DATA_TYPE_UTINYINT:
217	case TSDB_DATA_TYPE_TINYINT:
218	fn = taosIntHash_8;	×
219	break;	×
220	case TSDB_DATA_TYPE_FLOAT:	×
221	fn = taosFloatHash;	×
222	break;	×
223	case TSDB_DATA_TYPE_DOUBLE:	×
224	fn = taosDoubleHash;	×
225	break;	×
226	default:	×
227	fn = taosIntHash_32;	×
228	break;	×
229	}
230
231	return fn;	81,789✔
232	}
233
234	int32_t taosFloatEqual(const void a, const void b, size_t UNUSED_PARAM(sz)) {	×
235	// getComparFunc(TSDB_DATA_TYPE_FLOAT, -1) will always get function compareFloatVal, which will never be NULL.
236	return getComparFunc(TSDB_DATA_TYPE_FLOAT, -1)(a, b);	×
237	}
238
239	int32_t taosDoubleEqual(const void a, const void b, size_t UNUSED_PARAM(sz)) {	×
240	// getComparFunc(TSDB_DATA_TYPE_DOUBLE, -1) will always get function compareDoubleVal, which will never be NULL.
241	return getComparFunc(TSDB_DATA_TYPE_DOUBLE, -1)(a, b);	×
242	}
243
244	int32_t taosDecimalEqual(const void* a, const void* b, size_t UNUSED_PARAM(sz)) {	×
245	return 0;	×
246	}
247
248	_equal_fn_t taosGetDefaultEqualFunction(int32_t type) {	×
249	_equal_fn_t fn = NULL;	×
250	switch (type) {	×
251	case TSDB_DATA_TYPE_FLOAT:	×
252	fn = taosFloatEqual;	×
253	break;	×
254	case TSDB_DATA_TYPE_DOUBLE:	×
255	fn = taosDoubleEqual;	×
256	break;	×
257	case TSDB_DATA_TYPE_DECIMAL64:	×
258	case TSDB_DATA_TYPE_DECIMAL:
259	fn = memcmp;	×
260	break;	×
261	default:	×
262	fn = memcmp;	×
263	break;	×
264	}
265	return fn;	×
266	}

taosdata / TDengine / #3798

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