#3559

Committed 18 Dec 2024 12:59AM UTC coverage: 59.805% (+0.03%) from 59.778%

Build # #3559

Build Type

push

travis-ci

Committed by

web-flow

Commit Message

Merge pull request #29187 from taosdata/merge/mainto3.0

merge: main to 3.0 branch

Run Details

132705 of 287544 branches covered (46.15%)

Branch coverage included in aggregate %.

87 of 95 new or added lines in 19 files covered. (91.58%)

1132 existing lines in 133 files now uncovered.

209591 of 284807 relevant lines covered (73.59%)

8125235.78 hits per line

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

64.53

/source/util/src/tbloomfilter.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 "tbloomfilter.h"
#include "taos.h"
#include "taoserror.h"

#define UNIT_NUM_BITS      64ULL
#define UNIT_ADDR_NUM_BITS 6ULL

static FORCE_INLINE bool setBit(uint64_t* buf, uint64_t index) {
  uint64_t unitIndex = index >> UNIT_ADDR_NUM_BITS;
  uint64_t old = buf[unitIndex];
  buf[unitIndex] |= (1ULL << (index % UNIT_NUM_BITS));
  return buf[unitIndex] != old;
}

static FORCE_INLINE bool getBit(uint64_t* buf, uint64_t index) {
  uint64_t unitIndex = index >> UNIT_ADDR_NUM_BITS;
  uint64_t mask = 1ULL << (index % UNIT_NUM_BITS);
  return buf[unitIndex] & mask;
}

int32_t tBloomFilterInit(uint64_t expectedEntries, double errorRate, SBloomFilter** ppBF) {
  int32_t code = 0;
  int32_t lino = 0;
  if (expectedEntries < 1 || errorRate <= 0 || errorRate >= 1.0) {
    code = TSDB_CODE_FAILED;
    QUERY_CHECK_CODE(code, lino, _error);
  }
  SBloomFilter* pBF = taosMemoryCalloc(1, sizeof(SBloomFilter));
  if (pBF == NULL) {
    code = terrno;
    QUERY_CHECK_CODE(code, lino, _error);
  }
  pBF->expectedEntries = expectedEntries;
  pBF->errorRate = errorRate;

  double lnRate = fabs(log(errorRate));
  // ln(2)^2 = 0.480453013918201
  // m = - n * ln(P) / ( ln(2) )^2
  // m is the size of bloom filter, n is expected entries, P is false positive probability
  pBF->numUnits = (uint64_t)ceil(expectedEntries * lnRate / 0.480453013918201 / UNIT_NUM_BITS);
  pBF->numBits = pBF->numUnits * 64;
  pBF->size = 0;

  // ln(2) = 0.693147180559945
  pBF->hashFunctions = (uint32_t)ceil(lnRate / 0.693147180559945);
  pBF->hashFn1 = HASH_FUNCTION_1;
  pBF->hashFn2 = HASH_FUNCTION_2;
  pBF->buffer = taosMemoryCalloc(pBF->numUnits, sizeof(uint64_t));
  if (pBF->buffer == NULL) {
    tBloomFilterDestroy(pBF);
    code = terrno;
    QUERY_CHECK_CODE(code, lino, _error);
  }
  (*ppBF) = pBF;

_error:
  if (code != TSDB_CODE_SUCCESS) {
    uError("%s failed at line %d since %s", __func__, lino, tstrerror(code));
  }
  return code;
}

int32_t tBloomFilterPutHash(SBloomFilter* pBF, uint64_t hash1, uint64_t hash2) {
  if (tBloomFilterIsFull(pBF)) {
    uError("%s failed at line %d since %s", __func__, __LINE__, tstrerror(TSDB_CODE_INVALID_PARA));
    return TSDB_CODE_FAILED;
  }
  bool                    hasChange = false;
  const register uint64_t size = pBF->numBits;
  uint64_t                cbHash = hash1;
  for (uint32_t i = 0; i < pBF->hashFunctions; ++i) {
    hasChange |= setBit(pBF->buffer, cbHash % size);
    cbHash += hash2;
  }
  if (hasChange) {
    pBF->size++;
    return TSDB_CODE_SUCCESS;
  }
  return TSDB_CODE_FAILED;
}

int32_t tBloomFilterPut(SBloomFilter* pBF, const void* keyBuf, uint32_t len) {
  uint64_t                h1 = (uint64_t)pBF->hashFn1(keyBuf, len);
  uint64_t                h2 = (uint64_t)pBF->hashFn2(keyBuf, len);
  bool                    hasChange = false;
  const register uint64_t size = pBF->numBits;
  uint64_t                cbHash = h1;
  for (uint32_t i = 0; i < pBF->hashFunctions; ++i) {
    hasChange |= setBit(pBF->buffer, cbHash % size);
    cbHash += h2;
  }
  if (hasChange) {
    pBF->size++;
    return TSDB_CODE_SUCCESS;
  }
  return TSDB_CODE_FAILED;
}

int32_t tBloomFilterNoContain(const SBloomFilter* pBF, uint64_t hash1, uint64_t hash2) {
  const register uint64_t size = pBF->numBits;
  uint64_t                cbHash = hash1;
  for (uint32_t i = 0; i < pBF->hashFunctions; ++i) {
    if (!getBit(pBF->buffer, cbHash % size)) {
      return TSDB_CODE_SUCCESS;
    }
    cbHash += hash2;
  }
  return TSDB_CODE_FAILED;
}

void tBloomFilterDestroy(SBloomFilter* pBF) {
  if (pBF == NULL) {
    return;
  }
  taosMemoryFree(pBF->buffer);
  taosMemoryFree(pBF);
}

int32_t tBloomFilterEncode(const SBloomFilter* pBF, SEncoder* pEncoder) {
  TAOS_CHECK_RETURN(tEncodeU32(pEncoder, pBF->hashFunctions));
  TAOS_CHECK_RETURN(tEncodeU64(pEncoder, pBF->expectedEntries));
  TAOS_CHECK_RETURN(tEncodeU64(pEncoder, pBF->numUnits));
  TAOS_CHECK_RETURN(tEncodeU64(pEncoder, pBF->numBits));
  TAOS_CHECK_RETURN(tEncodeU64(pEncoder, pBF->size));
  for (uint64_t i = 0; i < pBF->numUnits; i++) {
    uint64_t* pUnits = (uint64_t*)pBF->buffer;
    TAOS_CHECK_RETURN(tEncodeU64(pEncoder, pUnits[i]));
  }
  TAOS_CHECK_RETURN(tEncodeDouble(pEncoder, pBF->errorRate));
  return 0;
}

int32_t tBloomFilterDecode(SDecoder* pDecoder, SBloomFilter** ppBF) {
  int32_t       code = 0;
  int32_t       lino = 0;
  SBloomFilter* pBF = taosMemoryCalloc(1, sizeof(SBloomFilter));
  if (!pBF) {
    code = terrno;
    QUERY_CHECK_CODE(code, lino, _error);
  }
  pBF->buffer = NULL;
  if (tDecodeU32(pDecoder, &pBF->hashFunctions) < 0) {
    code = TSDB_CODE_FAILED;
    QUERY_CHECK_CODE(code, lino, _error);
  }
  if (tDecodeU64(pDecoder, &pBF->expectedEntries) < 0) {
    code = TSDB_CODE_FAILED;
    QUERY_CHECK_CODE(code, lino, _error);
  }
  if (tDecodeU64(pDecoder, &pBF->numUnits) < 0) {
    code = TSDB_CODE_FAILED;
    QUERY_CHECK_CODE(code, lino, _error);
  }
  if (tDecodeU64(pDecoder, &pBF->numBits) < 0) {
    code = TSDB_CODE_FAILED;
    QUERY_CHECK_CODE(code, lino, _error);
  }
  if (tDecodeU64(pDecoder, &pBF->size) < 0) {
    code = TSDB_CODE_FAILED;
    QUERY_CHECK_CODE(code, lino, _error);
  }
  pBF->buffer = taosMemoryCalloc(pBF->numUnits, sizeof(uint64_t));
  QUERY_CHECK_NULL(pBF->buffer, code, lino, _error, terrno);

  for (int32_t i = 0; i < pBF->numUnits; i++) {
    uint64_t* pUnits = (uint64_t*)pBF->buffer;
    if (tDecodeU64(pDecoder, pUnits + i) < 0) {
      code = TSDB_CODE_FAILED;
      QUERY_CHECK_CODE(code, lino, _error);
    }
  }
  if (tDecodeDouble(pDecoder, &pBF->errorRate) < 0) {
    code = TSDB_CODE_FAILED;
    QUERY_CHECK_CODE(code, lino, _error);
  }
  pBF->hashFn1 = HASH_FUNCTION_1;
  pBF->hashFn2 = HASH_FUNCTION_2;
  (*ppBF) = pBF;
  return TSDB_CODE_SUCCESS;

_error:
  tBloomFilterDestroy(pBF);
  uError("%s failed at line %d since %s", __func__, lino, tstrerror(code));
  return code;
}

bool tBloomFilterIsFull(const SBloomFilter* pBF) { return pBF->size >= pBF->expectedEntries; }

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
18	#include "tbloomfilter.h"
19	#include "taos.h"
20	#include "taoserror.h"
21
22	#define UNIT_NUM_BITS 64ULL
23	#define UNIT_ADDR_NUM_BITS 6ULL
24
25	static FORCE_INLINE bool setBit(uint64_t* buf, uint64_t index) {
26	uint64_t unitIndex = index >> UNIT_ADDR_NUM_BITS;	106,496,085✔
27	uint64_t old = buf[unitIndex];	106,496,085✔
28	buf[unitIndex] \|= (1ULL << (index % UNIT_NUM_BITS));	106,496,085✔
29	return buf[unitIndex] != old;	106,496,085✔
30	}
31
32	static FORCE_INLINE bool getBit(uint64_t* buf, uint64_t index) {
33	uint64_t unitIndex = index >> UNIT_ADDR_NUM_BITS;	15,519,126✔
34	uint64_t mask = 1ULL << (index % UNIT_NUM_BITS);	15,519,126✔
35	return buf[unitIndex] & mask;	15,519,126✔
36	}
37
38	int32_t tBloomFilterInit(uint64_t expectedEntries, double errorRate, SBloomFilter** ppBF) {	125,635,258✔
39	int32_t code = 0;	125,635,258✔
40	int32_t lino = 0;	125,635,258✔
41	if (expectedEntries < 1 \|\| errorRate <= 0 \|\| errorRate >= 1.0) {	125,635,258!
UNCOV 42	code = TSDB_CODE_FAILED;	×
UNCOV 43	QUERY_CHECK_CODE(code, lino, _error);	×
44	}
45	SBloomFilter* pBF = taosMemoryCalloc(1, sizeof(SBloomFilter));	125,635,254!
46	if (pBF == NULL) {	127,069,841!
47	code = terrno;	×
48	QUERY_CHECK_CODE(code, lino, _error);	×
49	}
50	pBF->expectedEntries = expectedEntries;	127,069,841✔
51	pBF->errorRate = errorRate;	127,069,841✔
52
53	double lnRate = fabs(log(errorRate));	127,069,841✔
54	// ln(2)^2 = 0.480453013918201
55	// m = - n * ln(P) / ( ln(2) )^2
56	// m is the size of bloom filter, n is expected entries, P is false positive probability
57	pBF->numUnits = (uint64_t)ceil(expectedEntries * lnRate / 0.480453013918201 / UNIT_NUM_BITS);	127,069,841✔
58	pBF->numBits = pBF->numUnits * 64;	127,069,841✔
59	pBF->size = 0;	127,069,841✔
60
61	// ln(2) = 0.693147180559945
62	pBF->hashFunctions = (uint32_t)ceil(lnRate / 0.693147180559945);	127,069,841✔
63	pBF->hashFn1 = HASH_FUNCTION_1;	127,069,841✔
64	pBF->hashFn2 = HASH_FUNCTION_2;	127,069,841✔
65	pBF->buffer = taosMemoryCalloc(pBF->numUnits, sizeof(uint64_t));	127,069,841!
66	if (pBF->buffer == NULL) {	124,464,441!
67	tBloomFilterDestroy(pBF);	×
68	code = terrno;	×
69	QUERY_CHECK_CODE(code, lino, _error);	×
70	}
71	(*ppBF) = pBF;	124,464,441✔
72
73	_error:	124,464,445✔
74	if (code != TSDB_CODE_SUCCESS) {	124,464,445✔
75	uError("%s failed at line %d since %s", __func__, lino, tstrerror(code));	4!
76	}
77	return code;	124,159,162✔
78	}
79
80	int32_t tBloomFilterPutHash(SBloomFilter* pBF, uint64_t hash1, uint64_t hash2) {	9,172,891✔
81	if (tBloomFilterIsFull(pBF)) {	9,172,891✔
82	uError("%s failed at line %d since %s", __func__, __LINE__, tstrerror(TSDB_CODE_INVALID_PARA));	6,941!
83	return TSDB_CODE_FAILED;	×
84	}
85	bool hasChange = false;	9,154,218✔
86	const register uint64_t size = pBF->numBits;	9,154,218✔
87	uint64_t cbHash = hash1;	9,154,218✔
88	for (uint32_t i = 0; i < pBF->hashFunctions; ++i) {	86,496,854✔
89	hasChange \|= setBit(pBF->buffer, cbHash % size);	77,342,636✔
90	cbHash += hash2;	77,342,636✔
91	}
92	if (hasChange) {	9,154,218!
93	pBF->size++;	9,158,532✔
94	return TSDB_CODE_SUCCESS;	9,158,532✔
95	}
96	return TSDB_CODE_FAILED;	×
97	}
98
99	int32_t tBloomFilterPut(SBloomFilter* pBF, const void* keyBuf, uint32_t len) {	2,869,436✔
100	uint64_t h1 = (uint64_t)pBF->hashFn1(keyBuf, len);	2,869,436✔
101	uint64_t h2 = (uint64_t)pBF->hashFn2(keyBuf, len);	2,869,702✔
102	bool hasChange = false;	2,869,701✔
103	const register uint64_t size = pBF->numBits;	2,869,701✔
104	uint64_t cbHash = h1;	2,869,701✔
105	for (uint32_t i = 0; i < pBF->hashFunctions; ++i) {	32,023,150✔
106	hasChange \|= setBit(pBF->buffer, cbHash % size);	29,153,449✔
107	cbHash += h2;	29,153,449✔
108	}
109	if (hasChange) {	2,869,701✔
110	pBF->size++;	2,843,646✔
111	return TSDB_CODE_SUCCESS;	2,843,646✔
112	}
113	return TSDB_CODE_FAILED;	26,055✔
114	}
115
116	int32_t tBloomFilterNoContain(const SBloomFilter* pBF, uint64_t hash1, uint64_t hash2) {	4,989,511✔
117	const register uint64_t size = pBF->numBits;	4,989,511✔
118	uint64_t cbHash = hash1;	4,989,511✔
119	for (uint32_t i = 0; i < pBF->hashFunctions; ++i) {	15,645,958✔
120	if (!getBit(pBF->buffer, cbHash % size)) {	31,038,252✔
121	return TSDB_CODE_SUCCESS;	4,862,679✔
122	}
123	cbHash += hash2;	10,656,447✔
124	}
125	return TSDB_CODE_FAILED;	126,832✔
126	}
127
128	void tBloomFilterDestroy(SBloomFilter* pBF) {	128,047,395✔
129	if (pBF == NULL) {	128,047,395!
130	return;	×
131	}
132	taosMemoryFree(pBF->buffer);	128,047,395!
133	taosMemoryFree(pBF);	127,471,753!
134	}
135
136	int32_t tBloomFilterEncode(const SBloomFilter* pBF, SEncoder* pEncoder) {	50,934✔
137	TAOS_CHECK_RETURN(tEncodeU32(pEncoder, pBF->hashFunctions));	101,868!
138	TAOS_CHECK_RETURN(tEncodeU64(pEncoder, pBF->expectedEntries));	101,868!
139	TAOS_CHECK_RETURN(tEncodeU64(pEncoder, pBF->numUnits));	101,868!
140	TAOS_CHECK_RETURN(tEncodeU64(pEncoder, pBF->numBits));	101,868!
141	TAOS_CHECK_RETURN(tEncodeU64(pEncoder, pBF->size));	101,868!
142	for (uint64_t i = 0; i < pBF->numUnits; i++) {	79,128,693✔
143	uint64_t* pUnits = (uint64_t*)pBF->buffer;	79,077,759✔
144	TAOS_CHECK_RETURN(tEncodeU64(pEncoder, pUnits[i]));	158,155,518!
145	}
146	TAOS_CHECK_RETURN(tEncodeDouble(pEncoder, pBF->errorRate));	101,868!
147	return 0;	50,934✔
148	}
149
150	int32_t tBloomFilterDecode(SDecoder* pDecoder, SBloomFilter** ppBF) {	25,428✔
151	int32_t code = 0;	25,428✔
152	int32_t lino = 0;	25,428✔
153	SBloomFilter* pBF = taosMemoryCalloc(1, sizeof(SBloomFilter));	25,428!
154	if (!pBF) {	25,427!
155	code = terrno;	×
156	QUERY_CHECK_CODE(code, lino, _error);	×
157	}
158	pBF->buffer = NULL;	25,427✔
159	if (tDecodeU32(pDecoder, &pBF->hashFunctions) < 0) {	50,852!
160	code = TSDB_CODE_FAILED;	×
161	QUERY_CHECK_CODE(code, lino, _error);	×
162	}
163	if (tDecodeU64(pDecoder, &pBF->expectedEntries) < 0) {	50,847!
164	code = TSDB_CODE_FAILED;	×
165	QUERY_CHECK_CODE(code, lino, _error);	×
166	}
167	if (tDecodeU64(pDecoder, &pBF->numUnits) < 0) {	50,844!
168	code = TSDB_CODE_FAILED;	×
169	QUERY_CHECK_CODE(code, lino, _error);	×
170	}
171	if (tDecodeU64(pDecoder, &pBF->numBits) < 0) {	50,844!
172	code = TSDB_CODE_FAILED;	×
173	QUERY_CHECK_CODE(code, lino, _error);	×
174	}
175	if (tDecodeU64(pDecoder, &pBF->size) < 0) {	50,843!
176	code = TSDB_CODE_FAILED;	×
177	QUERY_CHECK_CODE(code, lino, _error);	×
178	}
179	pBF->buffer = taosMemoryCalloc(pBF->numUnits, sizeof(uint64_t));	25,421!
180	QUERY_CHECK_NULL(pBF->buffer, code, lino, _error, terrno);	25,418!
181
182	for (int32_t i = 0; i < pBF->numUnits; i++) {	41,658,532✔
183	uint64_t* pUnits = (uint64_t*)pBF->buffer;	41,630,308✔
184	if (tDecodeU64(pDecoder, pUnits + i) < 0) {	83,263,422!
185	code = TSDB_CODE_FAILED;	×
186	QUERY_CHECK_CODE(code, lino, _error);	×
187	}
188	}
189	if (tDecodeDouble(pDecoder, &pBF->errorRate) < 0) {	53,650!
190	code = TSDB_CODE_FAILED;	×
191	QUERY_CHECK_CODE(code, lino, _error);	×
192	}
193	pBF->hashFn1 = HASH_FUNCTION_1;	25,426✔
194	pBF->hashFn2 = HASH_FUNCTION_2;	25,426✔
195	(*ppBF) = pBF;	25,426✔
196	return TSDB_CODE_SUCCESS;	25,426✔
197
198	_error:	×
199	tBloomFilterDestroy(pBF);	×
200	uError("%s failed at line %d since %s", __func__, lino, tstrerror(code));	×
201	return code;	×
202	}
203
204	bool tBloomFilterIsFull(const SBloomFilter* pBF) { return pBF->size >= pBF->expectedEntries; }	21,065,456✔

taosdata / TDengine / #3559

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