diff options
-rw-r--r-- | src/setu/ibf.c | 68 |
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 | */ |
78 | struct InvertibleBloomFilter * | 77 | struct InvertibleBloomFilter * |
79 | ibf_create (uint32_t size, uint8_t hash_num) | 78 | ibf_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; |
135 | try_next: | 134 | try_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, | |||
287 | void | 302 | void |
288 | ibf_write_slice (const struct InvertibleBloomFilter *ibf, | 303 | ibf_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; |