PostgreSQL Source Code git master
bloomfilter.h File Reference
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Typedefs

typedef struct bloom_filter bloom_filter
 

Functions

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

Typedef Documentation

◆ bloom_filter

typedef struct bloom_filter bloom_filter

Definition at line 16 of file bloomfilter.h.

Function Documentation

◆ 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{
137 uint32 hashes[MAX_HASH_FUNCS];
138 int i;
139
140 k_hashes(filter, hashes, elem, len);
141
142 /* Map a bit-wise address to a byte-wise address + bit offset */
143 for (i = 0; i < filter->k_hash_funcs; i++)
144 {
145 filter->bitset[hashes[i] >> 3] |= 1 << (hashes[i] & 7);
146 }
147}
#define MAX_HASH_FUNCS
Definition: bloomfilter.c:42
static void k_hashes(bloom_filter *filter, uint32 *hashes, unsigned char *elem, size_t len)
Definition: bloomfilter.c:250
uint32_t uint32
Definition: c.h:502
int i
Definition: isn.c:77
const void size_t len
unsigned char bitset[FLEXIBLE_ARRAY_MEMBER]
Definition: bloomfilter.c:51
int k_hash_funcs
Definition: bloomfilter.c:47

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

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

Definition at line 87 of file bloomfilter.c.

88{
89 bloom_filter *filter;
90 int bloom_power;
91 uint64 bitset_bytes;
92 uint64 bitset_bits;
93
94 /*
95 * Aim for two bytes per element; this is sufficient to get a false
96 * positive rate below 1%, independent of the size of the bitset or total
97 * number of elements. Also, if rounding down the size of the bitset to
98 * the next lowest power of two turns out to be a significant drop, the
99 * false positive rate still won't exceed 2% in almost all cases.
100 */
101 bitset_bytes = Min(bloom_work_mem * UINT64CONST(1024), total_elems * 2);
102 bitset_bytes = Max(1024 * 1024, bitset_bytes);
103
104 /*
105 * Size in bits should be the highest power of two <= target. bitset_bits
106 * is uint64 because PG_UINT32_MAX is 2^32 - 1, not 2^32
107 */
108 bloom_power = my_bloom_power(bitset_bytes * BITS_PER_BYTE);
109 bitset_bits = UINT64CONST(1) << bloom_power;
110 bitset_bytes = bitset_bits / BITS_PER_BYTE;
111
112 /* Allocate bloom filter with unset bitset */
113 filter = palloc0(offsetof(bloom_filter, bitset) +
114 sizeof(unsigned char) * bitset_bytes);
115 filter->k_hash_funcs = optimal_k(bitset_bits, total_elems);
116 filter->seed = seed;
117 filter->m = bitset_bits;
118
119 return filter;
120}
static int optimal_k(uint64 bitset_bits, int64 total_elems)
Definition: bloomfilter.c:229
static int my_bloom_power(uint64 target_bitset_bits)
Definition: bloomfilter.c:210
#define Min(x, y)
Definition: c.h:975
#define Max(x, y)
Definition: c.h:969
uint64_t uint64
Definition: c.h:503
#define UINT64CONST(x)
Definition: c.h:517
void * palloc0(Size size)
Definition: mcxt.c:1969
#define BITS_PER_BYTE
uint64 seed
Definition: bloomfilter.c:48

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

void bloom_free ( bloom_filter filter)

Definition at line 126 of file bloomfilter.c.

127{
128 pfree(filter);
129}
void pfree(void *pointer)
Definition: mcxt.c:2146

References pfree().

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

◆ bloom_lacks_element()

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

Definition at line 157 of file bloomfilter.c.

158{
159 uint32 hashes[MAX_HASH_FUNCS];
160 int i;
161
162 k_hashes(filter, hashes, elem, len);
163
164 /* Map a bit-wise address to a byte-wise address + bit offset */
165 for (i = 0; i < filter->k_hash_funcs; i++)
166 {
167 if (!(filter->bitset[hashes[i] >> 3] & (1 << (hashes[i] & 7))))
168 return true;
169 }
170
171 return false;
172}

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

Referenced by bt_tuple_present_callback(), nfalsepos_for_missing_strings(), and roles_list_append().

◆ bloom_prop_bits_set()

double bloom_prop_bits_set ( bloom_filter filter)

Definition at line 187 of file bloomfilter.c.

188{
189 int bitset_bytes = filter->m / BITS_PER_BYTE;
190 uint64 bits_set = pg_popcount((char *) filter->bitset, bitset_bytes);
191
192 return bits_set / (double) filter->m;
193}
static uint64 pg_popcount(const char *buf, int bytes)
Definition: pg_bitutils.h:363

References BITS_PER_BYTE, bloom_filter::bitset, bloom_filter::m, and pg_popcount().

Referenced by bt_check_every_level(), and create_and_test_bloom().