aboutsummaryrefslogtreecommitdiff
path: root/src/consensus/ibf.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/consensus/ibf.c')
-rw-r--r--src/consensus/ibf.c87
1 files changed, 15 insertions, 72 deletions
diff --git a/src/consensus/ibf.c b/src/consensus/ibf.c
index 87dbdd696..739b97339 100644
--- a/src/consensus/ibf.c
+++ b/src/consensus/ibf.c
@@ -63,12 +63,10 @@ ibf_hashcode_from_key (struct IBF_Key key, struct GNUNET_HashCode *dst)
63 * 63 *
64 * @param size number of IBF buckets 64 * @param size number of IBF buckets
65 * @param hash_num number of buckets one element is hashed in 65 * @param hash_num number of buckets one element is hashed in
66 * @param salt salt for mingling hashes, different salt may
67 * result in less (or more) collisions
68 * @return the newly created invertible bloom filter 66 * @return the newly created invertible bloom filter
69 */ 67 */
70struct InvertibleBloomFilter * 68struct InvertibleBloomFilter *
71ibf_create (uint32_t size, uint8_t hash_num, uint32_t salt) 69ibf_create (uint32_t size, uint8_t hash_num)
72{ 70{
73 struct InvertibleBloomFilter *ibf; 71 struct InvertibleBloomFilter *ibf;
74 72
@@ -235,32 +233,25 @@ ibf_decode (struct InvertibleBloomFilter *ibf,
235 233
236 234
237/** 235/**
238 * Write an ibf. 236 * Write buckets from an ibf to a buffer.
237 * Exactly (IBF_BUCKET_SIZE*ibf->size) bytes are written to buf.
239 * 238 *
240 * @param ibf the ibf to write 239 * @param ibf the ibf to write
241 * @param start with which bucket to start 240 * @param start with which bucket to start
242 * @param count how many buckets to write 241 * @param count how many buckets to write
243 * @param buf buffer to write the data to, will be updated to point to the 242 * @param buf buffer to write the data to
244 * first byte after the written data
245 * @param size pointer to the size of the buffer, will be updated, can be NULL
246 */ 243 */
247void 244void
248ibf_write_slice (const struct InvertibleBloomFilter *ibf, uint32_t start, uint32_t count, void **buf, size_t *size) 245ibf_write_slice (const struct InvertibleBloomFilter *ibf, uint32_t start, uint32_t count, void *buf)
249{ 246{
250 struct IBF_Key *key_dst; 247 struct IBF_Key *key_dst;
251 struct IBF_KeyHash *key_hash_dst; 248 struct IBF_KeyHash *key_hash_dst;
252 struct IBF_Count *count_dst; 249 struct IBF_Count *count_dst;
253 250
254 /* update size and check for overflow */ 251 GNUNET_assert (start + count <= ibf->size);
255 if (NULL != size) 252
256 {
257 size_t old_size;
258 old_size = *size;
259 *size = *size - count * IBF_BUCKET_SIZE;
260 GNUNET_assert (*size < old_size);
261 }
262 /* copy keys */ 253 /* copy keys */
263 key_dst = (struct IBF_Key *) *buf; 254 key_dst = (struct IBF_Key *) buf;
264 memcpy (key_dst, ibf->key_sum + start, count * sizeof *key_dst); 255 memcpy (key_dst, ibf->key_sum + start, count * sizeof *key_dst);
265 key_dst += count; 256 key_dst += count;
266 /* copy key hashes */ 257 /* copy key hashes */
@@ -271,40 +262,28 @@ ibf_write_slice (const struct InvertibleBloomFilter *ibf, uint32_t start, uint32
271 count_dst = (struct IBF_Count *) key_hash_dst; 262 count_dst = (struct IBF_Count *) key_hash_dst;
272 memcpy (count_dst, ibf->count + start, count * sizeof *count_dst); 263 memcpy (count_dst, ibf->count + start, count * sizeof *count_dst);
273 count_dst += count; 264 count_dst += count;
274 /* returned buffer is at the end of written data*/
275 *buf = (void *) count_dst;
276} 265}
277 266
278 267
279/** 268/**
280 * Read an ibf. 269 * Read buckets from a buffer into an ibf.
281 * 270 *
282 * @param buf pointer to the buffer to write to, will point to first 271 * @param buf pointer to the buffer to read from
283 * byte after the written data // FIXME: take 'const void *buf' for input, return number of bytes READ
284 * @param size size of the buffer, will be updated
285 * @param start which bucket to start at 272 * @param start which bucket to start at
286 * @param count how many buckets to read 273 * @param count how many buckets to read
287 * @param ibf the ibf to read from 274 * @param ibf the ibf to read from
288 * @return GNUNET_OK on success // FIXME: return 0 on error (or -1/ssize_t), number of bytes read otherwise
289 */ 275 */
290int 276void
291ibf_read_slice (void **buf, size_t *size, uint32_t start, uint32_t count, struct InvertibleBloomFilter *ibf) 277ibf_read_slice (const void *buf, uint32_t start, uint32_t count, struct InvertibleBloomFilter *ibf)
292{ 278{
293 struct IBF_Key *key_src; 279 struct IBF_Key *key_src;
294 struct IBF_KeyHash *key_hash_src; 280 struct IBF_KeyHash *key_hash_src;
295 struct IBF_Count *count_src; 281 struct IBF_Count *count_src;
296 282
297 /* update size and check for overflow */ 283 GNUNET_assert (start + count <= ibf->size);
298 if (NULL != size) 284
299 {
300 size_t old_size;
301 old_size = *size;
302 *size = *size - count * IBF_BUCKET_SIZE;
303 if (*size > old_size)
304 return GNUNET_SYSERR;
305 }
306 /* copy keys */ 285 /* copy keys */
307 key_src = (struct IBF_Key *) *buf; 286 key_src = (struct IBF_Key *) buf;
308 memcpy (ibf->key_sum + start, key_src, count * sizeof *key_src); 287 memcpy (ibf->key_sum + start, key_src, count * sizeof *key_src);
309 key_src += count; 288 key_src += count;
310 /* copy key hashes */ 289 /* copy key hashes */
@@ -315,40 +294,6 @@ ibf_read_slice (void **buf, size_t *size, uint32_t start, uint32_t count, struct
315 count_src = (struct IBF_Count *) key_hash_src; 294 count_src = (struct IBF_Count *) key_hash_src;
316 memcpy (ibf->count + start, count_src, count * sizeof *count_src); 295 memcpy (ibf->count + start, count_src, count * sizeof *count_src);
317 count_src += count; 296 count_src += count;
318 /* returned buffer is at the end of written data*/
319 *buf = (void *) count_src;
320 return GNUNET_OK;
321}
322
323
324/**
325 * Write an ibf.
326 *
327 * @param ibf the ibf to write
328 * @param buf buffer to write the data to, will be updated to point to the
329 * first byte after the written data
330 * @param size pointer to the size of the buffer, will be updated, can be NULL
331 */
332void
333ibf_write (const struct InvertibleBloomFilter *ibf, void **buf, size_t *size)
334{
335 ibf_write_slice (ibf, 0, ibf->size, buf, size);
336}
337
338
339/**
340 * Read an ibf.
341 *
342 * @param buf pointer to the buffer to write to, will point to first
343 * byte after the written data
344 * @param size size of the buffer, will be updated
345 * @param dst ibf to write buckets to
346 * @return GNUNET_OK on success
347 */
348int
349ibf_read (void **buf, size_t *size, struct InvertibleBloomFilter *dst)
350{
351 return ibf_read_slice (buf, size, 0, dst->size, dst);
352} 297}
353 298
354 299
@@ -366,7 +311,6 @@ ibf_subtract (struct InvertibleBloomFilter *ibf1, const struct InvertibleBloomFi
366 311
367 GNUNET_assert (ibf1->size == ibf2->size); 312 GNUNET_assert (ibf1->size == ibf2->size);
368 GNUNET_assert (ibf1->hash_num == ibf2->hash_num); 313 GNUNET_assert (ibf1->hash_num == ibf2->hash_num);
369 GNUNET_assert (ibf1->salt == ibf2->salt);
370 314
371 for (i = 0; i < ibf1->size; i++) 315 for (i = 0; i < ibf1->size; i++)
372 { 316 {
@@ -388,7 +332,6 @@ ibf_dup (const struct InvertibleBloomFilter *ibf)
388 struct InvertibleBloomFilter *copy; 332 struct InvertibleBloomFilter *copy;
389 copy = GNUNET_malloc (sizeof *copy); 333 copy = GNUNET_malloc (sizeof *copy);
390 copy->hash_num = ibf->hash_num; 334 copy->hash_num = ibf->hash_num;
391 copy->salt = ibf->salt;
392 copy->size = ibf->size; 335 copy->size = ibf->size;
393 copy->key_hash_sum = GNUNET_memdup (ibf->key_hash_sum, ibf->size * sizeof (struct IBF_KeyHash)); 336 copy->key_hash_sum = GNUNET_memdup (ibf->key_hash_sum, ibf->size * sizeof (struct IBF_KeyHash));
394 copy->key_sum = GNUNET_memdup (ibf->key_sum, ibf->size * sizeof (struct IBF_Key)); 337 copy->key_sum = GNUNET_memdup (ibf->key_sum, ibf->size * sizeof (struct IBF_Key));