aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--src/setu/ibf.c68
1 files changed, 42 insertions, 26 deletions
diff --git a/src/setu/ibf.c b/src/setu/ibf.c
index 79b4f28db..1beba9065 100644
--- a/src/setu/ibf.c
+++ b/src/setu/ibf.c
@@ -20,7 +20,7 @@
20 20
21/** 21/**
22 * @file set/ibf.c 22 * @file set/ibf.c
23 * @brief implementation of the invertible bloom filter 23 * @brief implementation of the invertible Bloom filter
24 * @author Florian Dold 24 * @author Florian Dold
25 */ 25 */
26 26
@@ -58,12 +58,11 @@ ibf_hashcode_from_key (struct IBF_Key key,
58 struct GNUNET_HashCode *dst) 58 struct GNUNET_HashCode *dst)
59{ 59{
60 struct IBF_Key *p; 60 struct IBF_Key *p;
61 unsigned int i;
62 const unsigned int keys_per_hashcode = sizeof(struct GNUNET_HashCode) 61 const unsigned int keys_per_hashcode = sizeof(struct GNUNET_HashCode)
63 / sizeof(struct IBF_Key); 62 / sizeof(struct IBF_Key);
64 63
65 p = (struct IBF_Key *) dst; 64 p = (struct IBF_Key *) dst;
66 for (i = 0; i < keys_per_hashcode; i++) 65 for (unsigned int i = 0; i < keys_per_hashcode; i++)
67 *p++ = key; 66 *p++ = key;
68} 67}
69 68
@@ -76,12 +75,12 @@ ibf_hashcode_from_key (struct IBF_Key key,
76 * @return the newly created invertible bloom filter, NULL on error 75 * @return the newly created invertible bloom filter, NULL on error
77 */ 76 */
78struct InvertibleBloomFilter * 77struct InvertibleBloomFilter *
79ibf_create (uint32_t size, uint8_t hash_num) 78ibf_create (uint32_t size,
79 uint8_t hash_num)
80{ 80{
81 struct InvertibleBloomFilter *ibf; 81 struct InvertibleBloomFilter *ibf;
82 82
83 GNUNET_assert (0 != size); 83 GNUNET_assert (0 != size);
84
85 ibf = GNUNET_new (struct InvertibleBloomFilter); 84 ibf = GNUNET_new (struct InvertibleBloomFilter);
86 ibf->count = GNUNET_malloc_large (size * sizeof(uint8_t)); 85 ibf->count = GNUNET_malloc_large (size * sizeof(uint8_t));
87 if (NULL == ibf->count) 86 if (NULL == ibf->count)
@@ -106,7 +105,6 @@ ibf_create (uint32_t size, uint8_t hash_num)
106 } 105 }
107 ibf->size = size; 106 ibf->size = size;
108 ibf->hash_num = hash_num; 107 ibf->hash_num = hash_num;
109
110 return ibf; 108 return ibf;
111} 109}
112 110
@@ -123,7 +121,8 @@ ibf_get_indices (const struct InvertibleBloomFilter *ibf,
123 uint32_t i; 121 uint32_t i;
124 uint32_t bucket; 122 uint32_t bucket;
125 123
126 bucket = GNUNET_CRYPTO_crc32_n (&key, sizeof key); 124 bucket = GNUNET_CRYPTO_crc32_n (&key,
125 sizeof (key));
127 for (i = 0, filled = 0; filled < ibf->hash_num; i++) 126 for (i = 0, filled = 0; filled < ibf->hash_num; i++)
128 { 127 {
129 uint64_t x; 128 uint64_t x;
@@ -134,7 +133,8 @@ ibf_get_indices (const struct InvertibleBloomFilter *ibf,
134 dst[filled++] = bucket % ibf->size; 133 dst[filled++] = bucket % ibf->size;
135try_next: 134try_next:
136 x = ((uint64_t) bucket << 32) | i; 135 x = ((uint64_t) bucket << 32) | i;
137 bucket = GNUNET_CRYPTO_crc32_n (&x, sizeof x); 136 bucket = GNUNET_CRYPTO_crc32_n (&x,
137 sizeof (x));
138 } 138 }
139} 139}
140 140
@@ -170,8 +170,13 @@ ibf_insert (struct InvertibleBloomFilter *ibf,
170 int buckets[ibf->hash_num]; 170 int buckets[ibf->hash_num];
171 171
172 GNUNET_assert (ibf->hash_num <= ibf->size); 172 GNUNET_assert (ibf->hash_num <= ibf->size);
173 ibf_get_indices (ibf, key, buckets); 173 ibf_get_indices (ibf,
174 ibf_insert_into (ibf, key, buckets, 1); 174 key,
175 buckets);
176 ibf_insert_into (ibf,
177 key,
178 buckets,
179 1);
175} 180}
176 181
177 182
@@ -188,8 +193,13 @@ ibf_remove (struct InvertibleBloomFilter *ibf,
188 int buckets[ibf->hash_num]; 193 int buckets[ibf->hash_num];
189 194
190 GNUNET_assert (ibf->hash_num <= ibf->size); 195 GNUNET_assert (ibf->hash_num <= ibf->size);
191 ibf_get_indices (ibf, key, buckets); 196 ibf_get_indices (ibf,
192 ibf_insert_into (ibf, key, buckets, -1); 197 key,
198 buckets);
199 ibf_insert_into (ibf,
200 key,
201 buckets,
202 -1);
193} 203}
194 204
195 205
@@ -234,8 +244,6 @@ ibf_decode (struct InvertibleBloomFilter *ibf,
234 244
235 for (uint32_t i = 0; i < ibf->size; i++) 245 for (uint32_t i = 0; i < ibf->size; i++)
236 { 246 {
237 int hit;
238
239 /* we can only decode from pure buckets */ 247 /* we can only decode from pure buckets */
240 if ( (1 != ibf->count[i].count_val) && 248 if ( (1 != ibf->count[i].count_val) &&
241 (-1 != ibf->count[i].count_val) ) 249 (-1 != ibf->count[i].count_val) )
@@ -249,23 +257,30 @@ ibf_decode (struct InvertibleBloomFilter *ibf,
249 257
250 /* test if key in bucket hits its own location, 258 /* test if key in bucket hits its own location,
251 * if not, the key hash was subject to collision */ 259 * if not, the key hash was subject to collision */
252 hit = GNUNET_NO; 260 {
253 ibf_get_indices (ibf, ibf->key_sum[i], buckets); 261 bool hit = false;
254 for (int j = 0; j < ibf->hash_num; j++) 262
255 if (buckets[j] == i) 263 ibf_get_indices (ibf,
256 hit = GNUNET_YES; 264 ibf->key_sum[i],
257 265 buckets);
258 if (GNUNET_NO == hit) 266 for (int j = 0; j < ibf->hash_num; j++)
259 continue; 267 if (buckets[j] == i)
260 268 {
269 hit = true;
270 break;
271 }
272 if (! hit)
273 continue;
274 }
261 if (NULL != ret_side) 275 if (NULL != ret_side)
262 *ret_side = ibf->count[i].count_val; 276 *ret_side = ibf->count[i].count_val;
263 if (NULL != ret_id) 277 if (NULL != ret_id)
264 *ret_id = ibf->key_sum[i]; 278 *ret_id = ibf->key_sum[i];
265 279
266 /* insert on the opposite side, effectively removing the element */ 280 /* insert on the opposite side, effectively removing the element */
267 ibf_insert_into (ibf, ibf->key_sum[i], buckets, -ibf->count[i].count_val); 281 ibf_insert_into (ibf,
268 282 ibf->key_sum[i], buckets,
283 -ibf->count[i].count_val);
269 return GNUNET_YES; 284 return GNUNET_YES;
270 } 285 }
271 286
@@ -287,7 +302,8 @@ ibf_decode (struct InvertibleBloomFilter *ibf,
287void 302void
288ibf_write_slice (const struct InvertibleBloomFilter *ibf, 303ibf_write_slice (const struct InvertibleBloomFilter *ibf,
289 uint32_t start, 304 uint32_t start,
290 uint32_t count, void *buf) 305 uint32_t count,
306 void *buf)
291{ 307{
292 struct IBF_Key *key_dst; 308 struct IBF_Key *key_dst;
293 struct IBF_KeyHash *key_hash_dst; 309 struct IBF_KeyHash *key_hash_dst;