bloomfilter.c File Reference (original) (raw)

#include "[postgres.h](postgres%5F8h%5Fsource.html)"
#include <math.h>
#include "[common/hashfn.h](hashfn%5F8h%5Fsource.html)"
#include "[lib/bloomfilter.h](bloomfilter%5F8h%5Fsource.html)"
#include "[port/pg_bitutils.h](pg%5F%5Fbitutils%5F8h%5Fsource.html)"

Go to the source code of this file.

Functions
static int	my_bloom_power (uint64 target_bitset_bits)

static int	optimal_k (uint64 bitset_bits, int64 total_elems)

static void	k_hashes (bloom_filter filter, uint32 hashes, unsigned char *elem, size_t len)

static uint32	mod_m (uint32 val, uint64 m)

bloom_filter *	bloom_create (int64 total_elems, int bloom_work_mem, uint64 seed)

void	bloom_free (bloom_filter *filter)

void	bloom_add_element (bloom_filter filter, unsigned char elem, size_t len)

bool	bloom_lacks_element (bloom_filter filter, unsigned char elem, size_t len)

double	bloom_prop_bits_set (bloom_filter *filter)

◆ MAX_HASH_FUNCS

#define MAX_HASH_FUNCS 10

◆ bloom_add_element()

void bloom_add_element	(	bloom_filter *	filter,
unsigned char *	elem,
size_t	len
)

Definition at line 135 of file bloomfilter.c.

136{

138 int i;

139

141

142

144 {

145 filter->bitset[hashes[i] >> 3] |= 1 << (hashes[i] & 7);

146 }

147}

static void k_hashes(bloom_filter *filter, uint32 *hashes, unsigned char *elem, size_t len)

unsigned char bitset[FLEXIBLE_ARRAY_MEMBER]

References bloom_filter::bitset, i, bloom_filter::k_hash_funcs, k_hashes(), len, and MAX_HASH_FUNCS.

Referenced by bt_target_page_check(), populate_with_dummy_strings(), and roles_list_append().

◆ bloom_create()

Definition at line 87 of file bloomfilter.c.

88{

90 int bloom_power;

100

101 bitset_bytes = Min(bloom_work_mem * UINT64CONST(1024), total_elems * 2);

102 bitset_bytes = Max(1024 * 1024, bitset_bytes);

103

104

105

106

107

109 bitset_bits = UINT64CONST(1) << bloom_power;

111

112

114 sizeof(unsigned char) * bitset_bytes);

116 filter->seed = seed;

117 filter->m = bitset_bits;

118

119 return filter;

120}

static int optimal_k(uint64 bitset_bits, int64 total_elems)

static int my_bloom_power(uint64 target_bitset_bits)

void * palloc0(Size size)

References BITS_PER_BYTE, bloom_filter::k_hash_funcs, bloom_filter::m, Max, Min, my_bloom_power(), optimal_k(), palloc0(), bloom_filter::seed, and UINT64CONST.

Referenced by bt_check_every_level(), create_and_test_bloom(), and roles_list_append().

◆ bloom_free()

◆ bloom_lacks_element()

bool bloom_lacks_element	(	bloom_filter *	filter,
unsigned char *	elem,
size_t	len
)

◆ bloom_prop_bits_set()

◆ k_hashes()

static void k_hashes ( bloom_filter * filter, uint32 * hashes, unsigned char * elem, size_t len )	static

Definition at line 250 of file bloomfilter.c.

251{

254 y;

256 int i;

257

258

262 m = filter->m;

263

266

267

268 hashes[0] = x;

270 {

273

274 hashes[i] = x;

275 }

276}

static uint32 mod_m(uint32 val, uint64 m)

static Datum hash_any_extended(const unsigned char *k, int keylen, uint64 seed)

static uint64 DatumGetUInt64(Datum X)

static unsigned hash(unsigned *uv, int n)

References DatumGetUInt64(), hash(), hash_any_extended(), i, bloom_filter::k_hash_funcs, len, bloom_filter::m, mod_m(), bloom_filter::seed, x, and y.

Referenced by bloom_add_element(), and bloom_lacks_element().

◆ mod_m()

◆ my_bloom_power()

static int my_bloom_power ( uint64 target_bitset_bits)	static

Definition at line 210 of file bloomfilter.c.

211{

212 int bloom_power = -1;

213

214 while (target_bitset_bits > 0 && bloom_power < 32)

215 {

216 bloom_power++;

217 target_bitset_bits >>= 1;

218 }

219

220 return bloom_power;

221}

Referenced by bloom_create().

◆ optimal_k()

static int optimal_k ( uint64 bitset_bits, int64 total_elems )	static