diff options
Diffstat (limited to 'src/consensus/strata_estimator.c')
-rw-r--r-- | src/consensus/strata_estimator.c | 145 |
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 | |||
32 | void | ||
33 | strata_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 | |||
43 | void | ||
44 | strata_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 | |||
55 | void | ||
56 | strata_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 | |||
69 | struct StrataEstimator * | ||
70 | strata_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 | */ | ||
96 | unsigned int | ||
97 | strata_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 | |||
136 | void | ||
137 | strata_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 | |||