[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[GNUnet-SVN] r25613 - gnunet/src/consensus
From: |
gnunet |
Subject: |
[GNUnet-SVN] r25613 - gnunet/src/consensus |
Date: |
Fri, 21 Dec 2012 11:06:41 +0100 |
Author: dold
Date: 2012-12-21 11:06:41 +0100 (Fri, 21 Dec 2012)
New Revision: 25613
Modified:
gnunet/src/consensus/gnunet-consensus-ibf.c
gnunet/src/consensus/ibf.c
gnunet/src/consensus/ibf.h
Log:
collision detection for IBF, timing for test tool
Modified: gnunet/src/consensus/gnunet-consensus-ibf.c
===================================================================
--- gnunet/src/consensus/gnunet-consensus-ibf.c 2012-12-21 02:32:55 UTC (rev
25612)
+++ gnunet/src/consensus/gnunet-consensus-ibf.c 2012-12-21 10:06:41 UTC (rev
25613)
@@ -68,6 +68,8 @@
int i;
int side;
int res;
+ struct GNUNET_TIME_Absolute start_time;
+ struct GNUNET_TIME_Relative delta_time;
set_a = GNUNET_CONTAINER_multihashmap_create (((asize == 0) ? 1 : (asize +
csize)),
GNUNET_NO);
@@ -85,7 +87,6 @@
GNUNET_CRYPTO_hash_create_random (GNUNET_CRYPTO_QUALITY_WEAK, &id);
if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains (set_a, &id))
continue;
- printf("A: %s\n", GNUNET_h2s (&id));
GNUNET_CONTAINER_multihashmap_put (
set_a, &id, NULL, GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY);
i++;
@@ -98,7 +99,6 @@
continue;
if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains (set_b, &id))
continue;
- printf("B: %s\n", GNUNET_h2s (&id));
GNUNET_CONTAINER_multihashmap_put (
set_b, &id, NULL, GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY);
i++;
@@ -111,25 +111,30 @@
continue;
if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains (set_b, &id))
continue;
- printf("C: %s\n", GNUNET_h2s (&id));
GNUNET_CONTAINER_multihashmap_put (
set_c, &id, NULL, GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY);
i++;
}
-
ibf_a = ibf_create (ibf_size, hash_num, 0);
ibf_b = ibf_create (ibf_size, hash_num, 0);
+ start_time = GNUNET_TIME_absolute_get ();
+
GNUNET_CONTAINER_multihashmap_iterate (set_a, &insert_iterator, ibf_a);
GNUNET_CONTAINER_multihashmap_iterate (set_b, &insert_iterator, ibf_b);
GNUNET_CONTAINER_multihashmap_iterate (set_c, &insert_iterator, ibf_a);
GNUNET_CONTAINER_multihashmap_iterate (set_c, &insert_iterator, ibf_b);
+ delta_time = GNUNET_TIME_absolute_get_duration (start_time);
- printf ("-----------------\n");
+ printf ("encoded in: %s\n", GNUNET_STRINGS_relative_time_to_string
(delta_time, GNUNET_NO));
+
ibf_subtract (ibf_a, ibf_b);
+
+ start_time = GNUNET_TIME_absolute_get ();
+
for (;;)
{
res = ibf_decode (ibf_a, &side, &id);
@@ -142,15 +147,15 @@
{
if ((0 == GNUNET_CONTAINER_multihashmap_size (set_b)) &&
(0 == GNUNET_CONTAINER_multihashmap_size (set_a)))
- printf ("decode succeeded\n");
+ {
+ delta_time = GNUNET_TIME_absolute_get_duration (start_time);
+ printf ("decoded successfully in: %s\n",
GNUNET_STRINGS_relative_time_to_string (delta_time, GNUNET_NO));
+ }
else
printf ("decode missed elements\n");
return;
}
- printf("R: %s\n", GNUNET_h2s (&id));
- printf("s: %d\n", side);
-
if (side == 1)
res = GNUNET_CONTAINER_multihashmap_remove (set_a, &id, NULL);
if (side == -1)
Modified: gnunet/src/consensus/ibf.c
===================================================================
--- gnunet/src/consensus/ibf.c 2012-12-21 02:32:55 UTC (rev 25612)
+++ gnunet/src/consensus/ibf.c 2012-12-21 10:06:41 UTC (rev 25613)
@@ -27,6 +27,13 @@
#include "ibf.h"
+
+/**
+ * Opaque handle to an invertible bloom filter (IBF).
+ *
+ * An IBF is a counting bloom filter that has the ability to restore
+ * the hashes of its stored elements with high probability.
+ */
struct InvertibleBloomFilter
{
/**
@@ -66,6 +73,12 @@
/**
* Create an invertible bloom filter.
+ *
+ * @param size number of IBF buckets
+ * @param hash_num number of buckets one element is hashed in
+ * @param salt salt for mingling hashes, different salt may
+ * result in less (or more) collisions
+ * @return the newly created invertible bloom filter
*/
struct InvertibleBloomFilter *
ibf_create (unsigned int size, unsigned int hash_num, uint32_t salt)
@@ -85,7 +98,12 @@
/**
- * Insert an element into an IBF.
+ * Insert an element into an IBF, with either positive or negative sign.
+ *
+ * @param ibf the IBF
+ * @param id the element's hash code
+ * @param side the sign of side determines the sign of the
+ * inserted element.
*/
void
ibf_insert_on_side (struct InvertibleBloomFilter *ibf,
@@ -93,33 +111,48 @@
int side)
{
struct GNUNET_HashCode bucket_indices;
- struct GNUNET_HashCode remove_key;
+ struct GNUNET_HashCode key_copy;
struct GNUNET_HashCode key_hash;
- int i;
+ int *used_buckets;
+ unsigned int i;
- /* copy the key, if key and an entry in the IBF alias */
- remove_key = *key;
GNUNET_assert ((1 == side) || (-1 == side));
+ GNUNET_assert (NULL != ibf);
- bucket_indices = remove_key;
+ used_buckets = alloca (ibf->hash_num * sizeof (int));
+
+ /* copy the key, if key and an entry in the IBF alias */
+ key_copy = *key;
+
+ bucket_indices = key_copy;
GNUNET_CRYPTO_hash (key, sizeof (struct GNUNET_HashCode), &key_hash);
for (i = 0; i < ibf->hash_num; i++)
{
unsigned int bucket;
+ unsigned int j;
+ int collided;
+
if ((i % 16) == 0)
GNUNET_CRYPTO_hash (&bucket_indices, sizeof (struct GNUNET_HashCode),
&bucket_indices);
bucket = bucket_indices.bits[i%16] % ibf->size;
+ collided = GNUNET_NO;
+ for (j = 0; j < i; j++)
+ if (used_buckets[j] == bucket)
+ collided = GNUNET_YES;
+ if (GNUNET_YES == collided)
+ {
+ used_buckets[i] = -1;
+ continue;
+ }
+ used_buckets[i] = bucket;
- printf ("inserting %s in bucket %u side %d\n",
- GNUNET_h2s (&remove_key), bucket, side);
-
ibf->count[bucket] += side;
- GNUNET_CRYPTO_hash_xor (&remove_key, &ibf->id_sum[bucket],
+ GNUNET_CRYPTO_hash_xor (&key_copy, &ibf->id_sum[bucket],
&ibf->id_sum[bucket]);
GNUNET_CRYPTO_hash_xor (&key_hash, &ibf->hash_sum[bucket],
&ibf->hash_sum[bucket]);
@@ -128,6 +161,9 @@
/**
* Insert an element into an IBF.
+ *
+ * @param ibf the IBF
+ * @param id the element's hash code
*/
void
ibf_insert (struct InvertibleBloomFilter *ibf, const struct GNUNET_HashCode
*key)
@@ -160,10 +196,10 @@
* Decode and remove an element from the IBF, if possible.
*
* @param ibf the invertible bloom filter to decode
- * @param ret_id the hash code of the decoded element, if successful
* @param side sign of the cell's count where the decoded element came from.
* A negative sign indicates that the element was recovered
* resides in an IBF that was previously subtracted from.
+ * @param ret_id the hash code of the decoded element, if successful
* @return GNUNET_YES if decoding an element was successful,
* GNUNET_NO if the IBF is empty,
* GNUNET_SYSERR if the decoding has failed
@@ -189,9 +225,6 @@
if (0 != memcmp (&hash, &ibf->hash_sum[i], sizeof (struct
GNUNET_HashCode)))
continue;
- printf ("%d pure\n", i);
- printf ("%d count\n", ibf->count[i]);
-
*ret_side = ibf->count[i];
*ret_id = ibf->id_sum[i];
@@ -212,7 +245,8 @@
* Subtract ibf2 from ibf1, storing the result in ibf1.
* The two IBF's must have the same parameters size and hash_num.
*
- * @return a newly allocated invertible bloom filter
+ * @param ibf1 IBF that is subtracted from
+ * @param ibf2 IBF that will be subtracted from ibf1
*/
void
ibf_subtract (struct InvertibleBloomFilter *ibf1, struct InvertibleBloomFilter
*ibf2)
@@ -225,10 +259,7 @@
for (i = 0; i < ibf1->size; i++)
{
- printf ("ibf1->count[%d]=%d, ibf2->count[%d]=%d\n", i, ibf1->count[i], i,
- ibf2->count[i]);
ibf1->count[i] -= ibf2->count[i];
- printf("diff: %d\n", ibf1->count[i]);
GNUNET_CRYPTO_hash_xor (&ibf1->id_sum[i], &ibf2->id_sum[i],
&ibf1->id_sum[i]);
GNUNET_CRYPTO_hash_xor (&ibf1->hash_sum[i], &ibf2->hash_sum[i],
Modified: gnunet/src/consensus/ibf.h
===================================================================
--- gnunet/src/consensus/ibf.h 2012-12-21 02:32:55 UTC (rev 25612)
+++ gnunet/src/consensus/ibf.h 2012-12-21 10:06:41 UTC (rev 25613)
@@ -75,6 +75,9 @@
/**
* Subtract ibf2 from ibf1, storing the result in ibf1.
* The two IBF's must have the same parameters size and hash_num.
+ *
+ * @param ibf1 IBF that is subtracted from
+ * @param ibf2 IBF that will be subtracted from ibf1
*/
void
ibf_subtract (struct InvertibleBloomFilter *ibf1, struct InvertibleBloomFilter
*ibf2);
@@ -84,10 +87,10 @@
* Decode and remove an element from the IBF, if possible.
*
* @param ibf the invertible bloom filter to decode
- * @param ret_id the hash code of the decoded element, if successful
* @param side sign of the cell's count where the decoded element came from.
* A negative sign indicates that the element was recovered
resides in an IBF
* that was previously subtracted from.
+ * @param ret_id the hash code of the decoded element, if successful
* @return GNUNET_YES if decoding an element was successful, GNUNET_NO if the
IBF is empty,
* GNUNET_SYSERR if the decoding has faile
*/
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [GNUnet-SVN] r25613 - gnunet/src/consensus,
gnunet <=