Browse Source Download (without any required ccan dependencies)

Module:

invbloom

Summary:

implementation of invertible bloom lookup tables.

Dependencies:

Description:

This code implements a subset of invertible bloom lookup tables as described in[1].

[1] Goodrich, Michael T., and Michael Mitzenmacher. "Invertible bloom

    lookup tables." Communication, Control, and Computing (Allerton), 2011
    49th Annual Allerton Conference on. IEEE, 2011.
     http://arxiv.org/pdf/1101.2245

Example:

#include <ccan/invbloom/invbloom.h>
#include <stdio.h>

int main(int argc, char *argv[])
{
        unsigned int i, n;
        struct invbloom *ib = invbloom_new(NULL, char *, 16, 0);

        for (i = 1; i < argc; i++)
                invbloom_insert(ib, &argv[i]);

        n = 0;
        for (i = 1; i < argc; i++)
                n += invbloom_get(ib, &argv[i]);

        printf("%u out of %u are found\n", n, argc);

        n = 0;
        for (i = 1; i < argc; i++) {
                unsigned int j;
                char **p = invbloom_extract(NULL, ib);

                for (j = 1; j < argc; j++) {
                        if (p == &argv[j])
                                n++;
                }
                tal_free(p);
        }
        printf("%u out of %u were extracted\n", n, argc);
        return 0;
}

License:

BSD-MIT