[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[GNUnet-SVN] r34442 - gnunet/src/set
From: |
gnunet |
Subject: |
[GNUnet-SVN] r34442 - gnunet/src/set |
Date: |
Thu, 27 Nov 2014 15:10:47 +0100 |
Author: grothoff
Date: 2014-11-27 15:10:47 +0100 (Thu, 27 Nov 2014)
New Revision: 34442
Added:
gnunet/src/set/gnunet-service-set_union_strata_estimator.c
gnunet/src/set/gnunet-service-set_union_strata_estimator.h
Removed:
gnunet/src/set/strata_estimator.c
gnunet/src/set/strata_estimator.h
Modified:
gnunet/src/set/Makefile.am
gnunet/src/set/gnunet-service-set_union.c
Log:
-renaming
Modified: gnunet/src/set/Makefile.am
===================================================================
--- gnunet/src/set/Makefile.am 2014-11-27 14:06:12 UTC (rev 34441)
+++ gnunet/src/set/Makefile.am 2014-11-27 14:10:47 UTC (rev 34442)
@@ -45,7 +45,7 @@
gnunet-service-set_union.c \
gnunet-service-set_intersection.c \
ibf.c ibf.h \
- strata_estimator.c strata_estimator.h \
+ gnunet-service-set_union_strata_estimator.c
gnunet-service-set_union_strata_estimator.h \
set_protocol.h
gnunet_service_set_LDADD = \
$(top_builddir)/src/util/libgnunetutil.la \
Modified: gnunet/src/set/gnunet-service-set_union.c
===================================================================
--- gnunet/src/set/gnunet-service-set_union.c 2014-11-27 14:06:12 UTC (rev
34441)
+++ gnunet/src/set/gnunet-service-set_union.c 2014-11-27 14:10:47 UTC (rev
34442)
@@ -19,7 +19,7 @@
*/
/**
- * @file set/gnunet-service-set.c
+ * @file set/gnunet-service-set_union.c
* @brief two-peer set operations
* @author Florian Dold
*/
@@ -27,7 +27,7 @@
#include "gnunet_util_lib.h"
#include "gnunet-service-set.h"
#include "ibf.h"
-#include "strata_estimator.h"
+#include "gnunet-service-set_union_strata_estimator.h"
#include "set_protocol.h"
#include <gcrypt.h>
Copied: gnunet/src/set/gnunet-service-set_union_strata_estimator.c (from rev
34430, gnunet/src/set/strata_estimator.c)
===================================================================
--- gnunet/src/set/gnunet-service-set_union_strata_estimator.c
(rev 0)
+++ gnunet/src/set/gnunet-service-set_union_strata_estimator.c 2014-11-27
14:10:47 UTC (rev 34442)
@@ -0,0 +1,221 @@
+/*
+ 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 3, 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 set/gnunet-service-set_union_strata_estimator.c
+ * @brief invertible bloom filter
+ * @author Florian Dold
+ */
+
+#include "platform.h"
+#include "gnunet_util_lib.h"
+#include "ibf.h"
+#include "gnunet-service-set_union_strata_estimator.h"
+
+
+/**
+ * Write the given strata estimator to the buffer.
+ *
+ * @param se strata estimator to serialize
+ * @param buf buffer to write to, must be of appropriate size
+ */
+void
+strata_estimator_write (const struct StrataEstimator *se, void *buf)
+{
+ int i;
+
+ GNUNET_assert (NULL != se);
+ 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;
+ }
+}
+
+
+/**
+ * Read strata from the buffer into the given strata
+ * estimator. The strata estimator must already be allocated.
+ *
+ * @param buf buffer to read from
+ * @param se strata estimator to write to
+ */
+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;
+ }
+}
+
+
+/**
+ * Add a key to the strata estimator.
+ *
+ * @param se strata estimator to add the key to
+ * @param key key to add
+ */
+void
+strata_estimator_insert (struct StrataEstimator *se, struct IBF_Key key)
+{
+ uint64_t v;
+ int i;
+ v = key.key_val;
+ /* count trailing '1'-bits of v */
+ for (i = 0; v & 1; v>>=1, i++)
+ /* empty */;
+ ibf_insert (se->strata[i], key);
+}
+
+
+/**
+ * Remove a key from the strata estimator.
+ *
+ * @param se strata estimator to remove the key from
+ * @param key key to remove
+ */
+void
+strata_estimator_remove (struct StrataEstimator *se, struct IBF_Key key)
+{
+ uint64_t v;
+ int i;
+ v = key.key_val;
+ /* count trailing '1'-bits of v */
+ for (i = 0; v & 1; v>>=1, i++)
+ /* empty */;
+ ibf_remove (se->strata[i], key);
+}
+
+
+/**
+ * Create a new strata estimator with the given parameters.
+ *
+ * @param strata_count number of stratas, that is, number of ibfs in the
estimator
+ * @param ibf_size size of each ibf stratum
+ * @param ibf_hashnum hashnum parameter of each ibf
+ * @return a freshly allocated, empty strata estimator
+ */
+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_new (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;
+ /* FIXME: implement this without always allocating new IBFs */
+ diff = ibf_dup (se1->strata[i]);
+ ibf_subtract (diff, se2->strata[i]);
+ for (ibf_count = 0; GNUNET_YES; ibf_count++)
+ {
+ int more;
+
+ more = ibf_decode (diff, NULL, NULL);
+ if (GNUNET_NO == more)
+ {
+ count += ibf_count;
+ break;
+ }
+ /* Estimate if decoding fails or would not terminate */
+ if ((GNUNET_SYSERR == more) || (ibf_count > diff->size))
+ {
+ ibf_destroy (diff);
+ return count * (1 << (i + 1));
+ }
+ }
+ ibf_destroy (diff);
+ }
+ return count;
+}
+
+
+/**
+ * Make a copy of a strata estimator.
+ *
+ * @param se the strata estimator to copy
+ * @return the copy
+ */
+struct StrataEstimator *
+strata_estimator_dup (struct StrataEstimator *se)
+{
+ struct StrataEstimator *c;
+ int i;
+
+ c = GNUNET_new (struct StrataEstimator);
+ c->strata_count = se->strata_count;
+ c->ibf_size = se->ibf_size;
+ c->strata = GNUNET_malloc (sizeof (struct InvertibleBloomFilter *) *
se->strata_count);
+ for (i = 0; i < se->strata_count; i++)
+ c->strata[i] = ibf_dup (se->strata[i]);
+ return c;
+}
+
+
+/**
+ * Destroy a strata estimator, free all of its resources.
+ *
+ * @param se strata estimator to destroy.
+ */
+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);
+}
+
Copied: gnunet/src/set/gnunet-service-set_union_strata_estimator.h (from rev
34430, gnunet/src/set/strata_estimator.h)
===================================================================
--- gnunet/src/set/gnunet-service-set_union_strata_estimator.h
(rev 0)
+++ gnunet/src/set/gnunet-service-set_union_strata_estimator.h 2014-11-27
14:10:47 UTC (rev 34442)
@@ -0,0 +1,147 @@
+/*
+ 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 3, 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 set/gnunet-service-set_union_strata_estimator.h
+ * @brief estimator of set difference
+ * @author Florian Dold
+ */
+
+#ifndef GNUNET_CONSENSUS_STRATA_ESTIMATOR_H
+#define GNUNET_CONSENSUS_STRATA_ESTIMATOR_H
+
+#include "platform.h"
+#include "gnunet_common.h"
+#include "gnunet_util_lib.h"
+
+#ifdef __cplusplus
+extern "C"
+{
+#if 0 /* keep Emacsens' auto-indent happy */
+}
+#endif
+#endif
+
+
+/**
+ * A handle to a strata estimator.
+ */
+struct StrataEstimator
+{
+ struct InvertibleBloomFilter **strata;
+ unsigned int strata_count;
+ unsigned int ibf_size;
+};
+
+
+/**
+ * Write the given strata estimator to the buffer.
+ *
+ * @param se strata estimator to serialize
+ * @param buf buffer to write to, must be of appropriate size
+ */
+void
+strata_estimator_write (const struct StrataEstimator *se, void *buf);
+
+
+/**
+ * Read strata from the buffer into the given strata
+ * estimator. The strata estimator must already be allocated.
+ *
+ * @param buf buffer to read from
+ * @param se strata estimator to write to
+ */
+void
+strata_estimator_read (const void *buf, struct StrataEstimator *se);
+
+
+/**
+ * Create a new strata estimator with the given parameters.
+ *
+ * @param strata_count number of stratas, that is, number of ibfs in the
estimator
+ * @param ibf_size size of each ibf stratum
+ * @param ibf_hashnum hashnum parameter of each ibf
+ * @return a freshly allocated, empty strata estimator
+ */
+struct StrataEstimator *
+strata_estimator_create (unsigned int strata_count, uint32_t ibf_size, uint8_t
ibf_hashnum);
+
+
+/**
+ * Get an estimation of the symmetric difference of the elements
+ * contained in both strata estimators.
+ *
+ * @param se1 first strata estimator
+ * @param se2 second strata estimator
+ * @return abs(|se1| - |se2|)
+ */
+unsigned int
+strata_estimator_difference (const struct StrataEstimator *se1,
+ const struct StrataEstimator *se2);
+
+
+/**
+ * Add a key to the strata estimator.
+ *
+ * @param se strata estimator to add the key to
+ * @param key key to add
+ */
+void
+strata_estimator_insert (struct StrataEstimator *se, struct IBF_Key key);
+
+
+/**
+ * Remove a key from the strata estimator.
+ *
+ * @param se strata estimator to remove the key from
+ * @param key key to remove
+ */
+void
+strata_estimator_remove (struct StrataEstimator *se, struct IBF_Key key);
+
+
+/**
+ * Destroy a strata estimator, free all of its resources.
+ *
+ * @param se strata estimator to destroy.
+ */
+void
+strata_estimator_destroy (struct StrataEstimator *se);
+
+
+/**
+ * Make a copy of a strata estimator.
+ *
+ * @param se the strata estimator to copy
+ * @return the copy
+ */
+struct StrataEstimator *
+strata_estimator_dup (struct StrataEstimator *se);
+
+
+#if 0 /* keep Emacsens' auto-indent happy */
+{
+#endif
+#ifdef __cplusplus
+}
+#endif
+
+#endif
+
Deleted: gnunet/src/set/strata_estimator.c
===================================================================
--- gnunet/src/set/strata_estimator.c 2014-11-27 14:06:12 UTC (rev 34441)
+++ gnunet/src/set/strata_estimator.c 2014-11-27 14:10:47 UTC (rev 34442)
@@ -1,181 +0,0 @@
-/*
- 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 3, 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 set/ibf.h
- * @brief invertible bloom filter
- * @author Florian Dold
- */
-
-#include "platform.h"
-#include "gnunet_util_lib.h"
-#include "ibf.h"
-#include "strata_estimator.h"
-
-void
-strata_estimator_write (const struct StrataEstimator *se, void *buf)
-{
- int i;
-
- GNUNET_assert (NULL != se);
- 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 IBF_Key key)
-{
- uint64_t v;
- int i;
- v = key.key_val;
- /* count trailing '1'-bits of v */
- for (i = 0; v & 1; v>>=1, i++)
- /* empty */;
- ibf_insert (se->strata[i], key);
-}
-
-
-void
-strata_estimator_remove (struct StrataEstimator *se, struct IBF_Key key)
-{
- uint64_t v;
- int i;
- v = key.key_val;
- /* count trailing '1'-bits of v */
- for (i = 0; v & 1; v>>=1, i++)
- /* empty */;
- ibf_remove (se->strata[i], 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_new (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;
- /* FIXME: implement this without always allocating new IBFs */
- diff = ibf_dup (se1->strata[i]);
- ibf_subtract (diff, se2->strata[i]);
- for (ibf_count = 0; GNUNET_YES; ibf_count++)
- {
- int more;
-
- more = ibf_decode (diff, NULL, NULL);
- if (GNUNET_NO == more)
- {
- count += ibf_count;
- break;
- }
- /* Estimate if decoding fails or would not terminate */
- if ((GNUNET_SYSERR == more) || (ibf_count > diff->size))
- {
- ibf_destroy (diff);
- return count * (1 << (i + 1));
- }
- }
- ibf_destroy (diff);
- }
- return count;
-}
-
-/**
- * Make a copy of a strata estimator.
- *
- * @param se the strata estimator to copy
- * @return the copy
- */
-struct StrataEstimator *
-strata_estimator_dup (struct StrataEstimator *se)
-{
- struct StrataEstimator *c;
- int i;
-
- c = GNUNET_new (struct StrataEstimator);
- c->strata_count = se->strata_count;
- c->ibf_size = se->ibf_size;
- c->strata = GNUNET_malloc (sizeof (struct InvertibleBloomFilter *) *
se->strata_count);
- for (i = 0; i < se->strata_count; i++)
- c->strata[i] = ibf_dup (se->strata[i]);
- return c;
-}
-
-
-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);
-}
-
Deleted: gnunet/src/set/strata_estimator.h
===================================================================
--- gnunet/src/set/strata_estimator.h 2014-11-27 14:06:12 UTC (rev 34441)
+++ gnunet/src/set/strata_estimator.h 2014-11-27 14:10:47 UTC (rev 34442)
@@ -1,147 +0,0 @@
-/*
- 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 3, 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 set/strata_estimator.h
- * @brief estimator of set difference
- * @author Florian Dold
- */
-
-#ifndef GNUNET_CONSENSUS_STRATA_ESTIMATOR_H
-#define GNUNET_CONSENSUS_STRATA_ESTIMATOR_H
-
-#include "platform.h"
-#include "gnunet_common.h"
-#include "gnunet_util_lib.h"
-
-#ifdef __cplusplus
-extern "C"
-{
-#if 0 /* keep Emacsens' auto-indent happy */
-}
-#endif
-#endif
-
-
-/**
- * A handle to a strata estimator.
- */
-struct StrataEstimator
-{
- struct InvertibleBloomFilter **strata;
- unsigned int strata_count;
- unsigned int ibf_size;
-};
-
-
-/**
- * Write the given strata estimator to the buffer.
- *
- * @param se strata estimator to serialize
- * @param buf buffer to write to, must be of appropriate size
- */
-void
-strata_estimator_write (const struct StrataEstimator *se, void *buf);
-
-
-/**
- * Read strata from the buffer into the given strata
- * estimator. The strata estimator must already be allocated.
- *
- * @param buf buffer to read from
- * @param se strata estimator to write to
- */
-void
-strata_estimator_read (const void *buf, struct StrataEstimator *se);
-
-
-/**
- * Create a new strata estimator with the given parameters.
- *
- * @param strata_count number of stratas, that is, number of ibfs in the
estimator
- * @param ibf_size size of each ibf stratum
- * @param ibf_hashnum hashnum parameter of each ibf
- * @return a freshly allocated, empty strata estimator
- */
-struct StrataEstimator *
-strata_estimator_create (unsigned int strata_count, uint32_t ibf_size, uint8_t
ibf_hashnum);
-
-
-/**
- * Get an estimation of the symmetric difference of the elements
- * contained in both strata estimators.
- *
- * @param se1 first strata estimator
- * @param se2 second strata estimator
- * @return abs(|se1| - |se2|)
- */
-unsigned int
-strata_estimator_difference (const struct StrataEstimator *se1,
- const struct StrataEstimator *se2);
-
-
-/**
- * Add a key to the strata estimator.
- *
- * @param se strata estimator to add the key to
- * @param key key to add
- */
-void
-strata_estimator_insert (struct StrataEstimator *se, struct IBF_Key key);
-
-
-/**
- * Remove a key from the strata estimator.
- *
- * @param se strata estimator to remove the key from
- * @param key key to remove
- */
-void
-strata_estimator_remove (struct StrataEstimator *se, struct IBF_Key key);
-
-
-/**
- * Destroy a strata estimator, free all of its resources.
- *
- * @param se strata estimator to destroy.
- */
-void
-strata_estimator_destroy (struct StrataEstimator *se);
-
-
-/**
- * Make a copy of a strata estimator.
- *
- * @param se the strata estimator to copy
- * @return the copy
- */
-struct StrataEstimator *
-strata_estimator_dup (struct StrataEstimator *se);
-
-
-#if 0 /* keep Emacsens' auto-indent happy */
-{
-#endif
-#ifdef __cplusplus
-}
-#endif
-
-#endif
-
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [GNUnet-SVN] r34442 - gnunet/src/set,
gnunet <=