bloomfilter.c File Reference

#include "postgres.h"
#include <math.h>
#include "common/hashfn.h"
#include "lib/bloomfilter.h"
#include "port/pg_bitutils.h"

Include dependency graph for bloomfilter.c:

Go to the source code of this file.

Data Structures
struct	bloom_filter

Macros
#define	MAX_HASH_FUNCS   10

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)

Macro Definition Documentation

MAX_HASH_FUNCS

#define MAX_HASH_FUNCS   10

Definition at line 42 of file bloomfilter.c.

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.

{
    uint32      hashes[MAX_HASH_FUNCS];
    int         i;
 
    k_hashes(filter, hashes, elem, len);
 
    /* Map a bit-wise address to a byte-wise address + bit offset */
    for (i = 0; i < filter->k_hash_funcs; i++)
    {
        filter->bitset[hashes[i] >> 3] |= 1 << (hashes[i] & 7);
    }
}

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.

{
    bloom_filter *filter;
    int         bloom_power;
    uint64      bitset_bytes;
    uint64      bitset_bits;
 
    /*
     * Aim for two bytes per element; this is sufficient to get a false
     * positive rate below 1%, independent of the size of the bitset or total
     * number of elements.  Also, if rounding down the size of the bitset to
     * the next lowest power of two turns out to be a significant drop, the
     * false positive rate still won't exceed 2% in almost all cases.
     */
    bitset_bytes = Min(bloom_work_mem * UINT64CONST(1024), total_elems * 2);
    bitset_bytes = Max(1024 * 1024, bitset_bytes);
 
    /*
     * Size in bits should be the highest power of two <= target.  bitset_bits
     * is uint64 because PG_UINT32_MAX is 2^32 - 1, not 2^32
     */
    bloom_power = my_bloom_power(bitset_bytes * BITS_PER_BYTE);
    bitset_bits = UINT64CONST(1) << bloom_power;
    bitset_bytes = bitset_bits / BITS_PER_BYTE;
 
    /* Allocate bloom filter with unset bitset */
    filter = palloc0(offsetof(bloom_filter, bitset) +
                     sizeof(unsigned char) * bitset_bytes);
    filter->k_hash_funcs = optimal_k(bitset_bits, total_elems);
    filter->seed = seed;
    filter->m = bitset_bits;
 
    return filter;
}

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.

{
    pfree(filter);
}

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.

{
    uint32      hashes[MAX_HASH_FUNCS];
    int         i;
 
    k_hashes(filter, hashes, elem, len);
 
    /* Map a bit-wise address to a byte-wise address + bit offset */
    for (i = 0; i < filter->k_hash_funcs; i++)
    {
        if (!(filter->bitset[hashes[i] >> 3] & (1 << (hashes[i] & 7))))
            return true;
    }
 
    return false;
}

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.

{
    int         bitset_bytes = filter->m / BITS_PER_BYTE;
    uint64      bits_set = pg_popcount((char *) filter->bitset, bitset_bytes);
 
    return bits_set / (double) filter->m;
}

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

Referenced by bt_check_every_level(), and create_and_test_bloom().

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.

{
    uint64      hash;
    uint32      x,
                y;
    uint64      m;
    int         i;
 
    /* Use 64-bit hashing to get two independent 32-bit hashes */
    hash = DatumGetUInt64(hash_any_extended(elem, len, filter->seed));
    x = (uint32) hash;
    y = (uint32) (hash >> 32);
    m = filter->m;
 
    x = mod_m(x, m);
    y = mod_m(y, m);
 
    /* Accumulate hashes */
    hashes[0] = x;
    for (i = 1; i < filter->k_hash_funcs; i++)
    {
        x = mod_m(x + y, m);
        y = mod_m(y + i, m);
 
        hashes[i] = x;
    }
}

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

static uint32 mod_m ( uint32  val, uint64  m  )

inlinestatic

Definition at line 288 of file bloomfilter.c.

{
    Assert(m <= PG_UINT32_MAX + UINT64CONST(1));
    Assert(((m - 1) & m) == 0);
 
    return val & (m - 1);
}

References Assert(), PG_UINT32_MAX, UINT64CONST, and val.

Referenced by k_hashes().

my_bloom_power()

static int my_bloom_power ( uint64  target_bitset_bits )

static

Definition at line 210 of file bloomfilter.c.

{
    int         bloom_power = -1;
 
    while (target_bitset_bits > 0 && bloom_power < 32)
    {
        bloom_power++;
        target_bitset_bits >>= 1;
    }
 
    return bloom_power;
}

Referenced by bloom_create().

optimal_k()

static int optimal_k ( uint64  bitset_bits, int64  total_elems  )

static

Definition at line 229 of file bloomfilter.c.

{
    int         k = rint(log(2.0) * bitset_bits / total_elems);
 
    return Max(1, Min(k, MAX_HASH_FUNCS));
}

References Max, MAX_HASH_FUNCS, and Min.

Referenced by bloom_create().