NetSurf
|
Trivial bloom filter. More...
Go to the source code of this file.
Data Structures | |
struct | bloom_filter |
Functions | |
static uint32_t | fnv (const char *datum, size_t len) |
Hash a string, returning a 32bit value. More... | |
struct bloom_filter * | bloom_create (size_t size) |
Create a new bloom filter. More... | |
void | bloom_destroy (struct bloom_filter *b) |
Destroy a previously-created bloom filter. More... | |
void | bloom_insert_str (struct bloom_filter *b, const char *s, size_t z) |
Insert a string of given length (may include NULs) into the filter, using an internal hash function. More... | |
void | bloom_insert_hash (struct bloom_filter *b, uint32_t hash) |
Insert a given hash value into the filter, should you already have one to hand. More... | |
bool | bloom_search_str (struct bloom_filter *b, const char *s, size_t z) |
Search the filter for the given string, assuming it was added by bloom_insert_str(). More... | |
bool | bloom_search_hash (struct bloom_filter *b, uint32_t hash) |
Search the filter for the given hash value, assuming it was added by bloom_insert_hash(). More... | |
uint32_t | bloom_items (struct bloom_filter *b) |
Find out how many items have been added to this bloom filter. More... | |
Trivial bloom filter.
Definition in file bloom.c.
struct bloom_filter * bloom_create | ( | size_t | size | ) |
Create a new bloom filter.
size | Size of bloom filter in bytes |
Definition at line 59 of file bloom.c.
References bloom_filter::size.
Referenced by urldb_add_url(), and urldb_load().
void bloom_destroy | ( | struct bloom_filter * | b | ) |
Destroy a previously-created bloom filter.
b | Bloom filter to destroy |
Definition at line 71 of file bloom.c.
Referenced by urldb_destroy().
void bloom_insert_hash | ( | struct bloom_filter * | b, |
uint32_t | hash | ||
) |
Insert a given hash value into the filter, should you already have one to hand.
b | Bloom filter to add to |
hash | Value to add |
Definition at line 82 of file bloom.c.
References bloom_filter::filter, bloom_filter::items, and bloom_filter::size.
Referenced by bloom_insert_str(), urldb_add_url(), and urldb_load().
void bloom_insert_str | ( | struct bloom_filter * | b, |
const char * | s, | ||
size_t | z | ||
) |
Insert a string of given length (may include NULs) into the filter, using an internal hash function.
b | Bloom filter to add to |
s | Pointer to data |
z | Length of data |
Definition at line 76 of file bloom.c.
References bloom_insert_hash(), and fnv().
uint32_t bloom_items | ( | struct bloom_filter * | b | ) |
Find out how many items have been added to this bloom filter.
This is useful for deciding the size of a new bloom filter should you need to rehash it.
b | Bloom filter to examine |
Definition at line 107 of file bloom.c.
References bloom_filter::items.
bool bloom_search_hash | ( | struct bloom_filter * | b, |
uint32_t | hash | ||
) |
Search the filter for the given hash value, assuming it was added by bloom_insert_hash().
May return false-positives.
b | Bloom filter to search |
hash | Hash value to search for |
Definition at line 98 of file bloom.c.
References bloom_filter::filter, and bloom_filter::size.
Referenced by bloom_search_str(), and urldb_find_url().
bool bloom_search_str | ( | struct bloom_filter * | b, |
const char * | s, | ||
size_t | z | ||
) |
Search the filter for the given string, assuming it was added by bloom_insert_str().
May return false-positives.
b | Bloom filter to search |
s | Pointer to data to search for |
z | Length of data |
Definition at line 92 of file bloom.c.
References bloom_search_hash(), and fnv().
|
inlinestatic |
Hash a string, returning a 32bit value.
The hash algorithm used is Fowler Noll Vo - a very fast and simple hash, ideal for short strings. See http://en.wikipedia.org/wiki/Fowler_Noll_Vo_hash for more details.
datum | The string to hash. |
len | size_t of data length. |
Definition at line 38 of file bloom.c.
Referenced by bloom_insert_str(), and bloom_search_str().