4
\$\begingroup\$

A Bloom filter question once again. I have this:

BloomFilter.h

#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 */

BloomFilter.c

#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);
}

main.c

#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;
}

Critique request

My primary concern is handling errors: should I just abort or do something else?

\$\endgroup\$

1 Answer 1

Reset to default
3
\$\begingroup\$

Bug

In this function:

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);
}

you are using an array of 64 bit integers to hold the bits. Therefore, you should be using BITS_PER_UINT64_T which is 64, rather that BITS_PER_UINT8_T which is 8. The same thing happens in read_bit().

Unnecessary loop

The loop inside write_bit_impl() and read_bit_impl() can be replaced by a single shift. In other words, this:

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;
}

can be rewritten as this:

static void write_bit_impl(uint64_t* word, size_t bit_index)
{
    *word |= ((uint64_t) 1) << bit_index;
}
\$\endgroup\$
1
  • \$\begingroup\$ Do you have any opinions on "exception" handling? \$\endgroup\$
    – coderodde
    Commented Oct 30, 2017 at 19:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.