Basic bloom filter library in C

Problem

I've started learning C and as an exercise I decided to implement some basic functionality for a bloom filter. This is my first C project, so I wanted to see if I was doing things appropriately (project structure/organization wise). Also, I was wondering how to turn this into a shared/static library, since I tried initially with CMake, but I got a bit lost. The project is hosted on github here, but I have included the files below.

Questions relating to code:

Code style/clarity/quality, I just tried to follow what I'd seen in the linux kernel

Code security (No bounds/null checks in the inits)

Code performance

Any general ways to improve

bloom_filter.h

```
#ifndef BLOOM_FILTER_H
#define BLOOM_FILTER_H

#include
#include
#include
#include

#define BLOOM_INIT(bf) \
do { \
bf = malloc(sizeof(struct bloom_filter)); \
bf->nelems = 100; \
bf->mbits = 1600; \
bf->nhashes = 11; \
bf->buf = calloc(bf->nelems, sizeof(uint16_t)); \
} while(0)
#define BLOOM_INIT_NELEMS(bf, nelems) \
do { \
bf = malloc(sizeof(struct bloom_filter)); \
bf->nelems = nelems; \
bf->mbits = bf->nelems (sizeof(uint16_t) nhashes = (bf->mbits / bf->nelems) log(2); \
bf->buf = calloc(bf->nelems, sizeof(uint16_t)); \
} while(0)
#define BLOOM_FREE(bf) \
do { \
free(bf->buf); \
free(bf); \
} while(0)

struct bloom_filter {
uint8

Solution

For a C starter very well-written code!

There's not much to say about the code-style itself, though I've tried to improve it a bit.
My code is on GitHub, too.

Let's go through the relevant commits.

-
code style: add braces, move decls:

It's often frowned-upon to elide the braces even in cases like

if (P)
  Q;

better either use

if (P) Q;

or add the braces.
Eliding the braces (without putting it in one line) has often produced bugs like this:

if (P)
  Q;
  S;

which will always execute S.

The next thing I did was move the declaration of the iterating i into the for-loop.
This will not pollute the current scope and makes it clear where the variable is used and what for.

-
remove unnecessary do-while:

There's no need for the do-while(0) here -- a simple scope-block does the trick too, eg.:

#define BLOOM_FREE(bf)          \
{                               \
    free(bf->buf);              \
    free(bf);                   \
}

Also you could change BLOOM_INIT(bf) to:

#define BLOOM_INIT(bf) BLOOM_INIT_NELEMS(bf, 100)

This is a bit less optimized but makes it clear that it's just a shorthand.

-
add 'generic' insert_bytes function

Only providing functionality for int32_t and 0-terminated strings is a bit limited.
Either provide some kind of generic function (the caller must pass width of type and a void to the value) or allow passing standard bytes (ie. char ) that do not need to be 0-terminated, I chose the latter way.

Also you can reuse most of the code this way.

Other remarks:

-
sizeof(uint16_t) mbits / bf->nelems) to just PRECISION which would be far easier to understand and possibly more portable too.

-
You might want to find better types for the filter as currently there are many conversions in the code that might change the values of the variables.
Just remove the "no-" in the conversion warning flags in the CMakeLists.txt file to see what I mean.
Much of it is probably harmless on standard Linux/GCC toolchains but I wouldn't rely too much on it.
Better fix it up.

Code Snippets

if (P)
  Q;

if (P)
  Q;
  S;

#define BLOOM_FREE(bf)          \
{                               \
    free(bf->buf);              \
    free(bf);                   \
}

#define BLOOM_INIT(bf) BLOOM_INIT_NELEMS(bf, 100)

#define PPCAT_NX(A, B, C) A ## B ## C
#define PPCAT(A, B, C) PPCAT_NX(A, B, C)

#define PRECISION 16
#define BUF_TYPE PPCAT(uint, PRECISION, _t)

int main() {
  BUF_TYPE x; /* declares a uint16_t */
}

Context

StackExchange Code Review Q#139371, answer score: 2

Revisions (0)

No revisions yet.