33 #define IBF_KEY_HASH_VAL(k) (GNUNET_CRYPTO_crc32_n (&(k), sizeof(struct \ 45 return *(
struct IBF_Key *) hash;
63 / sizeof(struct IBF_Key);
65 p = (
struct IBF_Key *) dst;
66 for (i = 0; i < keys_per_hashcode; i++)
87 if (NULL == ibf->
count)
127 for (i = 0, filled = 0; filled < ibf->
hash_num; i++)
131 for (
unsigned int j = 0; j < filled; j++)
132 if (dst[j] == bucket % ibf->
size)
134 dst[filled++] = bucket % ibf->
size;
136 x = ((uint64_t) bucket << 32) | i;
148 for (
unsigned int i = 0; i < ibf->
hash_num; i++)
150 const int bucket = buckets[i];
202 for (uint32_t i = 0; i < ibf->
size; i++)
235 for (uint32_t i = 0; i < ibf->
size; i++)
254 for (
int j = 0; j < ibf->
hash_num; j++)
261 if (NULL != ret_side)
290 uint32_t count,
void *
buf)
299 key_dst = (
struct IBF_Key *) buf;
302 count *
sizeof *key_dst);
308 count *
sizeof *key_hash_dst);
309 key_hash_dst += count;
311 count_dst = (
struct IBF_Count *) key_hash_dst;
314 count *
sizeof *count_dst);
340 key_src = (
struct IBF_Key *) buf;
343 count *
sizeof *key_src);
349 count *
sizeof *key_hash_src);
350 key_hash_src += count;
352 count_src = (
struct IBF_Count *) key_hash_src;
355 count *
sizeof *count_src);
373 for (uint32_t i = 0; i < ibf1->
size; i++)
void ibf_remove(struct InvertibleBloomFilter *ibf, struct IBF_Key key)
Remove a key from an IBF.
int32_t GNUNET_CRYPTO_crc32_n(const void *buf, size_t len)
Compute the CRC32 checksum for the first len bytes of the buffer.
static int start
Set if we are to start default services (including ARM).
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
Invertible bloom filter (IBF).
#define GNUNET_memcpy(dst, src, n)
Call memcpy() but check for n being 0 first.
struct IBF_Count * count
How many times has a bucket been hit? Can be negative, as a result of IBF subtraction.
#define GNUNET_memdup(buf, size)
Allocate and initialize a block of memory.
#define GNUNET_new(type)
Allocate a struct or union of the given type.
void ibf_write_slice(const struct InvertibleBloomFilter *ibf, uint32_t start, uint32_t count, void *buf)
Write buckets from an ibf to a buffer.
#define GNUNET_malloc_large(size)
Wrapper around malloc.
static void ibf_insert_into(struct InvertibleBloomFilter *ibf, struct IBF_Key key, const int *buckets, int side)
struct InvertibleBloomFilter * ibf_dup(const struct InvertibleBloomFilter *ibf)
Create a copy of an IBF, the copy has to be destroyed properly.
uint32_t size
How many cells does this IBF have?
static int ibf_is_empty(struct InvertibleBloomFilter *ibf)
Test is the IBF is empty, i.e.
static struct GNUNET_OS_Process * p
Helper process we started.
#define IBF_KEY_HASH_VAL(k)
Compute the key's hash from the key.
int ibf_decode(struct InvertibleBloomFilter *ibf, int *ret_side, struct IBF_Key *ret_id)
Decode and remove an element from the IBF, if possible.
void ibf_hashcode_from_key(struct IBF_Key key, struct GNUNET_HashCode *dst)
Create a hashcode from a key, by replicating the key until the hascode is filled. ...
uint8_t hash_num
In how many cells do we hash one element? Usually 4 or 3.
void ibf_subtract(struct InvertibleBloomFilter *ibf1, const struct InvertibleBloomFilter *ibf2)
Subtract ibf2 from ibf1, storing the result in ibf1.
static void ibf_get_indices(const struct InvertibleBloomFilter *ibf, struct IBF_Key key, int *dst)
Store unique bucket indices for the specified key in dst.
Type of the count field of IBF buckets.
struct IBF_Key * key_sum
Xor sums of the elements' keys, used to identify the elements.
void ibf_read_slice(const void *buf, uint32_t start, uint32_t count, struct InvertibleBloomFilter *ibf)
Read buckets from a buffer into an ibf.
struct GNUNET_HashCode key
The key used in the DHT.
static unsigned int size
Size of the "table".
void ibf_destroy(struct InvertibleBloomFilter *ibf)
Destroy all resources associated with the invertible bloom filter.
static unsigned int hash_num
struct InvertibleBloomFilter * ibf_create(uint32_t size, uint8_t hash_num)
Create an invertible bloom filter.
void ibf_insert(struct InvertibleBloomFilter *ibf, struct IBF_Key key)
Insert a key into an IBF.
struct IBF_KeyHash * key_hash_sum
Xor sums of the hashes of the keys of inserted elements.
struct IBF_Key ibf_key_from_hashcode(const struct GNUNET_HashCode *hash)
Create a key from a hashcode.
Keys that can be inserted into and removed from an IBF.
#define GNUNET_malloc(size)
Wrapper around malloc.
#define GNUNET_free(ptr)
Wrapper around free.