NetSurf
Data Structures | Functions
bloom.c File Reference

Trivial bloom filter. More...

#include <stdlib.h>
#include "utils/bloom.h"
#include "utils/utils.h"
Include dependency graph for bloom.c:

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_filterbloom_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...
 

Detailed Description

Trivial bloom filter.

Definition in file bloom.c.

Function Documentation

◆ bloom_create()

struct bloom_filter * bloom_create ( size_t  size)

Create a new bloom filter.

Parameters
sizeSize of bloom filter in bytes
Returns
Handle for newly-created bloom filter, or NULL

Definition at line 59 of file bloom.c.

References bloom_filter::size.

Referenced by urldb_add_url(), and urldb_load().

Here is the caller graph for this function:

◆ bloom_destroy()

void bloom_destroy ( struct bloom_filter b)

Destroy a previously-created bloom filter.

Parameters
bBloom filter to destroy

Definition at line 71 of file bloom.c.

Referenced by urldb_destroy().

Here is the caller graph for this function:

◆ bloom_insert_hash()

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.

Parameters
bBloom filter to add to
hashValue 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().

Here is the caller graph for this function:

◆ bloom_insert_str()

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.

Parameters
bBloom filter to add to
sPointer to data
zLength of data

Definition at line 76 of file bloom.c.

References bloom_insert_hash(), and fnv().

Here is the call graph for this function:

◆ bloom_items()

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.

Parameters
bBloom filter to examine
Returns
Number of items that have been added

Definition at line 107 of file bloom.c.

References bloom_filter::items.

◆ bloom_search_hash()

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.

Parameters
bBloom filter to search
hashHash value to search for
Returns
False if never added, True if it might have been.

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

Here is the caller graph for this function:

◆ bloom_search_str()

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.

Parameters
bBloom filter to search
sPointer to data to search for
zLength of data
Returns
False if never added, True if it might have been.

Definition at line 92 of file bloom.c.

References bloom_search_hash(), and fnv().

Here is the call graph for this function:

◆ fnv()

static uint32_t fnv ( const char *  datum,
size_t  len 
)
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.

Parameters
datumThe string to hash.
lensize_t of data length.
Returns
The calculated hash value for the datum.

Definition at line 38 of file bloom.c.

Referenced by bloom_insert_str(), and bloom_search_str().

Here is the caller graph for this function: