PostgreSQL Source Code git master
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
test_bloomfilter.c File Reference
#include "postgres.h"
#include "common/pg_prng.h"
#include "fmgr.h"
#include "lib/bloomfilter.h"
#include "miscadmin.h"
Include dependency graph for test_bloomfilter.c:

Go to the source code of this file.

Macros

#define MAX_ELEMENT_BYTES   21
 
#define FPOSITIVE_THRESHOLD   0.01
 

Functions

static void populate_with_dummy_strings (bloom_filter *filter, int64 nelements)
 
static int64 nfalsepos_for_missing_strings (bloom_filter *filter, int64 nelements)
 
static void create_and_test_bloom (int power, int64 nelements, int callerseed)
 
 PG_FUNCTION_INFO_V1 (test_bloomfilter)
 
Datum test_bloomfilter (PG_FUNCTION_ARGS)
 

Variables

 PG_MODULE_MAGIC
 

Macro Definition Documentation

◆ FPOSITIVE_THRESHOLD

#define FPOSITIVE_THRESHOLD   0.01

Definition at line 25 of file test_bloomfilter.c.

◆ MAX_ELEMENT_BYTES

#define MAX_ELEMENT_BYTES   21

Definition at line 23 of file test_bloomfilter.c.

Function Documentation

◆ create_and_test_bloom()

static void create_and_test_bloom ( int  power,
int64  nelements,
int  callerseed 
)
static

Definition at line 72 of file test_bloomfilter.c.

73{
74 int bloom_work_mem;
75 uint64 seed;
76 int64 nfalsepos;
77 bloom_filter *filter;
78
79 bloom_work_mem = (1L << power) / 8L / 1024L;
80
81 elog(DEBUG1, "bloom_work_mem (KB): %d", bloom_work_mem);
82
83 /*
84 * Generate random seed, or use caller's. Seed should always be a
85 * positive value less than or equal to PG_INT32_MAX, to ensure that any
86 * random seed can be recreated through callerseed if the need arises.
87 */
88 seed = callerseed < 0 ? pg_prng_int32p(&pg_global_prng_state) : callerseed;
89
90 /* Create Bloom filter, populate it, and report on false positive rate */
91 filter = bloom_create(nelements, bloom_work_mem, seed);
92 populate_with_dummy_strings(filter, nelements);
93 nfalsepos = nfalsepos_for_missing_strings(filter, nelements);
94
95 ereport((nfalsepos > nelements * FPOSITIVE_THRESHOLD) ? WARNING : DEBUG1,
96 (errmsg_internal("seed: " UINT64_FORMAT " false positives: " INT64_FORMAT " (%.6f%%) bitset %.2f%% set",
97 seed, nfalsepos, (double) nfalsepos / nelements,
98 100.0 * bloom_prop_bits_set(filter))));
99
100 bloom_free(filter);
101}
void bloom_free(bloom_filter *filter)
Definition: bloomfilter.c:126
bloom_filter * bloom_create(int64 total_elems, int bloom_work_mem, uint64 seed)
Definition: bloomfilter.c:87
double bloom_prop_bits_set(bloom_filter *filter)
Definition: bloomfilter.c:187
#define INT64_FORMAT
Definition: c.h:506
int64_t int64
Definition: c.h:485
#define UINT64_FORMAT
Definition: c.h:507
uint64_t uint64
Definition: c.h:489
int errmsg_internal(const char *fmt,...)
Definition: elog.c:1157
#define WARNING
Definition: elog.h:36
#define DEBUG1
Definition: elog.h:30
#define elog(elevel,...)
Definition: elog.h:225
#define ereport(elevel,...)
Definition: elog.h:149
int32 pg_prng_int32p(pg_prng_state *state)
Definition: pg_prng.c:254
pg_prng_state pg_global_prng_state
Definition: pg_prng.c:34
static void populate_with_dummy_strings(bloom_filter *filter, int64 nelements)
static int64 nfalsepos_for_missing_strings(bloom_filter *filter, int64 nelements)
#define FPOSITIVE_THRESHOLD

References bloom_create(), bloom_free(), bloom_prop_bits_set(), DEBUG1, elog, ereport, errmsg_internal(), FPOSITIVE_THRESHOLD, INT64_FORMAT, nfalsepos_for_missing_strings(), pg_global_prng_state, pg_prng_int32p(), populate_with_dummy_strings(), UINT64_FORMAT, and WARNING.

Referenced by test_bloomfilter().

◆ nfalsepos_for_missing_strings()

static int64 nfalsepos_for_missing_strings ( bloom_filter filter,
int64  nelements 
)
static

Definition at line 52 of file test_bloomfilter.c.

53{
55 int64 nfalsepos = 0;
56 int64 i;
57
58 for (i = 0; i < nelements; i++)
59 {
61
62 snprintf(element, sizeof(element), "M" INT64_FORMAT, i);
63 if (!bloom_lacks_element(filter, (unsigned char *) element,
64 strlen(element)))
65 nfalsepos++;
66 }
67
68 return nfalsepos;
69}
bool bloom_lacks_element(bloom_filter *filter, unsigned char *elem, size_t len)
Definition: bloomfilter.c:157
int i
Definition: isn.c:72
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:122
#define snprintf
Definition: port.h:238
static chr element(struct vars *v, const chr *startp, const chr *endp)
Definition: regc_locale.c:376
#define MAX_ELEMENT_BYTES

References bloom_lacks_element(), CHECK_FOR_INTERRUPTS, element(), i, INT64_FORMAT, MAX_ELEMENT_BYTES, and snprintf.

Referenced by create_and_test_bloom().

◆ PG_FUNCTION_INFO_V1()

PG_FUNCTION_INFO_V1 ( test_bloomfilter  )

◆ populate_with_dummy_strings()

static void populate_with_dummy_strings ( bloom_filter filter,
int64  nelements 
)
static

Definition at line 32 of file test_bloomfilter.c.

33{
35 int64 i;
36
37 for (i = 0; i < nelements; i++)
38 {
40
41 snprintf(element, sizeof(element), "i" INT64_FORMAT, i);
42 bloom_add_element(filter, (unsigned char *) element, strlen(element));
43 }
44}
void bloom_add_element(bloom_filter *filter, unsigned char *elem, size_t len)
Definition: bloomfilter.c:135

References bloom_add_element(), CHECK_FOR_INTERRUPTS, element(), i, INT64_FORMAT, MAX_ELEMENT_BYTES, and snprintf.

Referenced by create_and_test_bloom().

◆ test_bloomfilter()

Datum test_bloomfilter ( PG_FUNCTION_ARGS  )

Definition at line 113 of file test_bloomfilter.c.

114{
115 int power = PG_GETARG_INT32(0);
116 int64 nelements = PG_GETARG_INT64(1);
117 int seed = PG_GETARG_INT32(2);
118 int tests = PG_GETARG_INT32(3);
119 int i;
120
121 if (power < 23 || power > 32)
122 elog(ERROR, "power argument must be between 23 and 32 inclusive");
123
124 if (tests <= 0)
125 elog(ERROR, "invalid number of tests: %d", tests);
126
127 if (nelements < 0)
128 elog(ERROR, "invalid number of elements: %d", tests);
129
130 for (i = 0; i < tests; i++)
131 {
132 elog(DEBUG1, "beginning test #%d...", i + 1);
133
134 create_and_test_bloom(power, nelements, seed);
135 }
136
138}
#define ERROR
Definition: elog.h:39
#define PG_RETURN_VOID()
Definition: fmgr.h:349
#define PG_GETARG_INT64(n)
Definition: fmgr.h:283
#define PG_GETARG_INT32(n)
Definition: fmgr.h:269
static void create_and_test_bloom(int power, int64 nelements, int callerseed)

References create_and_test_bloom(), DEBUG1, elog, ERROR, i, PG_GETARG_INT32, PG_GETARG_INT64, and PG_RETURN_VOID.

Variable Documentation

◆ PG_MODULE_MAGIC

PG_MODULE_MAGIC

Definition at line 20 of file test_bloomfilter.c.