summaryrefslogtreecommitdiff
path: root/src/consensus/strata_estimator.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/consensus/strata_estimator.c')
-rw-r--r--src/consensus/strata_estimator.c145
1 files changed, 145 insertions, 0 deletions
diff --git a/src/consensus/strata_estimator.c b/src/consensus/strata_estimator.c
new file mode 100644
index 000000000..685c50f0f
--- /dev/null
+++ b/src/consensus/strata_estimator.c
@@ -0,0 +1,145 @@
+/*
+ This file is part of GNUnet
+ (C) 2012 Christian Grothoff (and other contributing authors)
+
+ GNUnet is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published
+ by the Free Software Foundation; either version 2, or (at your
+ option) any later version.
+
+ GNUnet is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with GNUnet; see the file COPYING. If not, write to the
+ Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ Boston, MA 02111-1307, USA.
+*/
+
+/**
+ * @file consensus/ibf.h
+ * @brief invertible bloom filter
+ * @author Florian Dold
+ */
+
+#include "platform.h"
+#include "gnunet_common.h"
+#include "ibf.h"
+#include "strata_estimator.h"
+
+void
+strata_estimator_write (const struct StrataEstimator *se, void *buf)
+{
+ int i;
+ for (i = 0; i < se->strata_count; i++)
+ {
+ ibf_write_slice (se->strata[i], 0, se->ibf_size, buf);
+ buf += se->ibf_size * IBF_BUCKET_SIZE;
+ }
+}
+
+void
+strata_estimator_read (const void *buf, struct StrataEstimator *se)
+{
+ int i;
+ for (i = 0; i < se->strata_count; i++)
+ {
+ ibf_read_slice (buf, 0, se->ibf_size, se->strata[i]);
+ buf += se->ibf_size * IBF_BUCKET_SIZE;
+ }
+}
+
+
+void
+strata_estimator_insert (struct StrataEstimator *se, struct GNUNET_HashCode *key)
+{
+ uint32_t v;
+ int i;
+ v = key->bits[0];
+ /* count trailing '1'-bits of v */
+ for (i = 0; v & 1; v>>=1, i++)
+ /* empty */;
+ ibf_insert (se->strata[i], ibf_key_from_hashcode (key));
+}
+
+
+
+struct StrataEstimator *
+strata_estimator_create (unsigned int strata_count, uint32_t ibf_size, uint8_t ibf_hashnum)
+{
+ struct StrataEstimator *se;
+ int i;
+
+ /* fixme: allocate everything in one chunk */
+
+ se = GNUNET_malloc (sizeof (struct StrataEstimator));
+ se->strata_count = strata_count;
+ se->ibf_size = ibf_size;
+ se->strata = GNUNET_malloc (sizeof (struct InvertibleBloomFilter *) * strata_count);
+ for (i = 0; i < strata_count; i++)
+ se->strata[i] = ibf_create (ibf_size, ibf_hashnum);
+ return se;
+}
+
+
+/**
+ * Estimate set difference with two strata estimators,
+ * i.e. arrays of IBFs.
+ * Does not not modify its arguments.
+ *
+ * @param se1 first strata estimator
+ * @param se2 second strata estimator
+ * @return the estimated difference
+ */
+unsigned int
+strata_estimator_difference (const struct StrataEstimator *se1,
+ const struct StrataEstimator *se2)
+{
+ int i;
+ int count;
+
+ GNUNET_assert (se1->strata_count == se2->strata_count);
+ count = 0;
+ for (i = se1->strata_count - 1; i >= 0; i--)
+ {
+ struct InvertibleBloomFilter *diff;
+ /* number of keys decoded from the ibf */
+ int ibf_count;
+ int more;
+ ibf_count = 0;
+ /* FIXME: implement this without always allocating new IBFs */
+ diff = ibf_dup (se1->strata[i]);
+ ibf_subtract (diff, se2->strata[i]);
+ for (;;)
+ {
+ more = ibf_decode (diff, NULL, NULL);
+ if (GNUNET_NO == more)
+ {
+ count += ibf_count;
+ break;
+ }
+ if (GNUNET_SYSERR == more)
+ {
+ ibf_destroy (diff);
+ return count * (1 << (i + 1));
+ }
+ ibf_count++;
+ }
+ ibf_destroy (diff);
+ }
+ return count;
+}
+
+
+void
+strata_estimator_destroy (struct StrataEstimator *se)
+{
+ int i;
+ for (i = 0; i < se->strata_count; i++)
+ ibf_destroy (se->strata[i]);
+ GNUNET_free (se->strata);
+ GNUNET_free (se);
+}
+