问C语言中的Bloom滤波器

EN

#ifndef NET_CODERODDE_UTIL_BLOOM_FILTER_H
#define NET_CODERODDE_UTIL_BLOOM_FILTER_H

#include <stdlib.h>

typedef unsigned char uint8_t;

typedef struct bloom_filter_t {
    uint8_t* array;
    size_t capacity;
    size_t (**hash_functions)(const void*);
    size_t hash_function_count;
} bloom_filter_t;

/***********************************************************************
* Allocates a new Bloom filter with given capacity and hash functions. *
***********************************************************************/
bloom_filter_t* bloom_filter_t_alloc(size_t capacity,
                                     size_t (**hash_functions)(const void*),
                                     size_t hash_function_count);

/********************************************************************
* Initializes a Bloom filter with given capacity and hash function. *
********************************************************************/
void bloom_filter_t_init(bloom_filter_t* bloom_filter,
                         size_t capacity,
                         size_t (**hash_functions)(const void*),
                         size_t hash_function_count);

/*********************************************
* Adds an element to the given Bloom filter. *
*********************************************/
void bloom_filter_t_add(bloom_filter_t* bloom_filter, const void* element);

/***********************************************************
* Queries whether an element is in the given Bloom filter. *
***********************************************************/
int bloom_filter_t_contains(bloom_filter_t* bloom_filter, const void* element);

/***********************************************************
* Restores the state of the Bloom filter to the empty one. *
***********************************************************/
void bloom_filter_t_clear(bloom_filter_t* bloom_filter);

/*****************************************************************
* Releases all the internal resources of the given Bloom filter. *
*****************************************************************/
void bloom_filter_t_deinit(bloom_filter_t* bloom_filter);

/************************************
* Releases the entire Bloom filter. *
************************************/
void bloom_filter_t_free(bloom_filter_t* bloom_filter);

#endif /* NET_CODERODDE_UTIL_BLOOM_FILTER_H */

#include "net/coderodde/util/BloomFilter.h"
#include <stdlib.h>

#define BITS_PER_UINT8_T 8

bloom_filter_t* bloom_filter_t_alloc(size_t capacity,
                                     size_t (**hash_functions)(const void*),
                                     size_t hash_function_count)
{
    bloom_filter_t* bloom_filter;
    size_t i;

    if (hash_function_count == 0)
    {
        abort();
    }

    for (i = 0; i != hash_function_count; ++i)
    {
        if (!hash_functions[i])
        {
            abort();
        }
    }

    bloom_filter = malloc(sizeof *bloom_filter);

    if (!bloom_filter)
    {
        abort();
    }

    bloom_filter->array = calloc(capacity, sizeof(uint64_t));

    if (!bloom_filter->array)
    {
        free(bloom_filter);
        abort();
    }

    bloom_filter->capacity = capacity;
    bloom_filter->hash_functions = hash_functions;
    bloom_filter->hash_function_count = hash_function_count;
    return bloom_filter;
}

void bloom_filter_t_init(bloom_filter_t* bloom_filter,
                         size_t capacity,
                         size_t (**hash_functions)(const void*),
                         size_t hash_function_count)
{
    size_t i;

    if (hash_function_count == 0)
    {
        abort();
    }

    for (i = 0; i != hash_function_count; ++i)
    {
        if (!hash_functions[i])
        {
            abort();
        }
    }

    if (!bloom_filter)
    {
        abort();
    }

    bloom_filter->array = calloc(capacity, sizeof(uint64_t));

    if (!bloom_filter->array)
    {
        abort();
    }

    bloom_filter->capacity = capacity;
    bloom_filter->hash_functions = hash_functions;
    bloom_filter->hash_function_count = hash_function_count;
}

static void write_bit_impl(uint64_t* word, size_t bit_index)
{
    uint64_t integer = 1;
    size_t i;

    for (i = 0; i != bit_index; ++i)
    {
        integer <<= 1;
    }

    *word |= integer;
}

static void write_bit(uint64_t* array, size_t bit_index)
{
    size_t word_index = bit_index / BITS_PER_UINT8_T;
    uint64_t* integer = &array[word_index];
    write_bit_impl(integer, bit_index % BITS_PER_UINT8_T);
}

void bloom_filter_t_add(bloom_filter_t* bloom_filter, const void* element)
{
    size_t i;
    size_t bit_index;
    size_t total_bits;

    if (!bloom_filter)
    {
        abort();
    }

    total_bits = bloom_filter->capacity * BITS_PER_UINT8_T;

    for (i = 0; i != bloom_filter->hash_function_count; ++i)
    {
        bit_index = bloom_filter->hash_functions[i](element) % total_bits;
        write_bit(bloom_filter->array, bit_index);
    }
}

static int read_bit_impl(uint64_t* word, size_t bit_index)
{
    uint64_t integer = 1;
    size_t i;

    for (i = 0; i != bit_index; ++i)
    {
        integer <<= 1;
    }

    return ((*word & integer) != 0) ? 1 : 0;
}

static int read_bit(uint64_t* array, size_t bit_index)
{
    size_t word_index = bit_index / BITS_PER_UINT8_T;
    uint64_t* integer = &array[word_index];
    return read_bit_impl(integer, bit_index % BITS_PER_UINT8_T);
}

int bloom_filter_t_contains(bloom_filter_t* bloom_filter, const void* element)
{
    size_t i;
    size_t bit_index;
    size_t total_bits;

    if (!bloom_filter)
    {
        abort();
    }

    total_bits = bloom_filter->capacity * BITS_PER_UINT8_T;

    for (i = 0; i != bloom_filter->hash_function_count; ++i)
    {
        bit_index = bloom_filter->hash_functions[i](element) % total_bits;

        if (!read_bit(bloom_filter->array, bit_index))
        {
            return 0;
        }
    }

    return 1;
}

void bloom_filter_t_clear(bloom_filter_t* bloom_filter)
{
    size_t i;

    if (!bloom_filter)
    {
        abort();
    }

    for (i = 0; i != bloom_filter->capacity; ++i)
    {
        bloom_filter->array[i] = 0;
    }
}

void bloom_filter_t_deinit(bloom_filter_t* bloom_filter)
{
    if (!bloom_filter)
    {
        abort();
    }

    free(bloom_filter->array);
    bloom_filter->array = NULL;
    bloom_filter->capacity = 0;
    bloom_filter->hash_function_count = 0;
    bloom_filter->hash_functions = NULL;
}

void bloom_filter_t_free(bloom_filter_t* bloom_filter)
{
    if (!bloom_filter)
    {
        abort();
    }

    bloom_filter_t_deinit(bloom_filter);
    free(bloom_filter);
}

#include "net/coderodde/util/BloomFilter.h"
#include <stdio.h>

size_t hash_function_1(const void* arg)
{
    size_t hash = 0;
    size_t i = 2;
    char* c = (char*) arg;

    while (*c)
    {
        hash += *c * i;
        i++;
        c++;
    }

    return hash;
}

size_t hash_function_2(const void* arg)
{
    size_t hash = 0;
    size_t i = 1;
    char* c = (char*) arg;

    while (*c)
    {
        hash += i * *c;
        i += 2;
        c++;
    }

    return hash;
}

int main(int argc, const char * argv[]) {
    size_t i;
    bloom_filter_t* bloom_filter;

    char* names[] = {
        "Jack",
        "Alice",
        "Bob",
        "Richard",
        "Rolf",
        "Benjamin",
        "Ada",
        "Leif",
        "Funky",
        "DJ",
    };

    size_t (*hash_functions[])(const void*) = {
        hash_function_1,
        hash_function_2
    };

    bloom_filter = bloom_filter_t_alloc(1, hash_functions, 2);

    for (i = 0; i != 8; ++i)
    {
        bloom_filter_t_add(bloom_filter, names[i]);
    }

    for (i = 0; i != 10; ++i)
    {
        printf("%s: %d\n",
               names[i],
               bloom_filter_t_contains(bloom_filter, names[i]));
    }

    return 0;
}