aboutsummaryrefslogtreecommitdiff
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 @@
1/*
2 This file is part of GNUnet
3 (C) 2012 Christian Grothoff (and other contributing authors)
4
5 GNUnet is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published
7 by the Free Software Foundation; either version 2, or (at your
8 option) any later version.
9
10 GNUnet is distributed in the hope that it will be useful, but
11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with GNUnet; see the file COPYING. If not, write to the
17 Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18 Boston, MA 02111-1307, USA.
19*/
20
21/**
22 * @file consensus/ibf.h
23 * @brief invertible bloom filter
24 * @author Florian Dold
25 */
26
27#include "platform.h"
28#include "gnunet_common.h"
29#include "ibf.h"
30#include "strata_estimator.h"
31
32void
33strata_estimator_write (const struct StrataEstimator *se, void *buf)
34{
35 int i;
36 for (i = 0; i < se->strata_count; i++)
37 {
38 ibf_write_slice (se->strata[i], 0, se->ibf_size, buf);
39 buf += se->ibf_size * IBF_BUCKET_SIZE;
40 }
41}
42
43void
44strata_estimator_read (const void *buf, struct StrataEstimator *se)
45{
46 int i;
47 for (i = 0; i < se->strata_count; i++)
48 {
49 ibf_read_slice (buf, 0, se->ibf_size, se->strata[i]);
50 buf += se->ibf_size * IBF_BUCKET_SIZE;
51 }
52}
53
54
55void
56strata_estimator_insert (struct StrataEstimator *se, struct GNUNET_HashCode *key)
57{
58 uint32_t v;
59 int i;
60 v = key->bits[0];
61 /* count trailing '1'-bits of v */
62 for (i = 0; v & 1; v>>=1, i++)
63 /* empty */;
64 ibf_insert (se->strata[i], ibf_key_from_hashcode (key));
65}
66
67
68
69struct StrataEstimator *
70strata_estimator_create (unsigned int strata_count, uint32_t ibf_size, uint8_t ibf_hashnum)
71{
72 struct StrataEstimator *se;
73 int i;
74
75 /* fixme: allocate everything in one chunk */
76
77 se = GNUNET_malloc (sizeof (struct StrataEstimator));
78 se->strata_count = strata_count;
79 se->ibf_size = ibf_size;
80 se->strata = GNUNET_malloc (sizeof (struct InvertibleBloomFilter *) * strata_count);
81 for (i = 0; i < strata_count; i++)
82 se->strata[i] = ibf_create (ibf_size, ibf_hashnum);
83 return se;
84}
85
86
87/**
88 * Estimate set difference with two strata estimators,
89 * i.e. arrays of IBFs.
90 * Does not not modify its arguments.
91 *
92 * @param se1 first strata estimator
93 * @param se2 second strata estimator
94 * @return the estimated difference
95 */
96unsigned int
97strata_estimator_difference (const struct StrataEstimator *se1,
98 const struct StrataEstimator *se2)
99{
100 int i;
101 int count;
102
103 GNUNET_assert (se1->strata_count == se2->strata_count);
104 count = 0;
105 for (i = se1->strata_count - 1; i >= 0; i--)
106 {
107 struct InvertibleBloomFilter *diff;
108 /* number of keys decoded from the ibf */
109 int ibf_count;
110 int more;
111 ibf_count = 0;
112 /* FIXME: implement this without always allocating new IBFs */
113 diff = ibf_dup (se1->strata[i]);
114 ibf_subtract (diff, se2->strata[i]);
115 for (;;)
116 {
117 more = ibf_decode (diff, NULL, NULL);
118 if (GNUNET_NO == more)
119 {
120 count += ibf_count;
121 break;
122 }
123 if (GNUNET_SYSERR == more)
124 {
125 ibf_destroy (diff);
126 return count * (1 << (i + 1));
127 }
128 ibf_count++;
129 }
130 ibf_destroy (diff);
131 }
132 return count;
133}
134
135
136void
137strata_estimator_destroy (struct StrataEstimator *se)
138{
139 int i;
140 for (i = 0; i < se->strata_count; i++)
141 ibf_destroy (se->strata[i]);
142 GNUNET_free (se->strata);
143 GNUNET_free (se);
144}
145