PostgreSQL Source Code git master
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
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:485
int i
Definition: isn.c:72
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:958
#define Max(x, y)
Definition: c.h:952
uint64_t uint64
Definition: c.h:486
#define UINT64CONST(x)
Definition: c.h:500
void * palloc0(Size size)
Definition: mcxt.c:1347
#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:1521

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:339

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

Referenced by bt_check_every_level(), and create_and_test_bloom().