diff options
Diffstat (limited to 'src/set/gnunet-service-set_union_strata_estimator.c')
-rw-r--r-- | src/set/gnunet-service-set_union_strata_estimator.c | 303 |
1 files changed, 0 insertions, 303 deletions
diff --git a/src/set/gnunet-service-set_union_strata_estimator.c b/src/set/gnunet-service-set_union_strata_estimator.c deleted file mode 100644 index 97b4a1f98..000000000 --- a/src/set/gnunet-service-set_union_strata_estimator.c +++ /dev/null | |||
@@ -1,303 +0,0 @@ | |||
1 | /* | ||
2 | This file is part of GNUnet | ||
3 | Copyright (C) 2012 GNUnet e.V. | ||
4 | |||
5 | GNUnet is free software: you can redistribute it and/or modify it | ||
6 | under the terms of the GNU Affero General Public License as published | ||
7 | by the Free Software Foundation, either version 3 of the License, | ||
8 | or (at your 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 | Affero General Public License for more details. | ||
14 | |||
15 | You should have received a copy of the GNU Affero General Public License | ||
16 | along with this program. If not, see <http://www.gnu.org/licenses/>. | ||
17 | |||
18 | SPDX-License-Identifier: AGPL3.0-or-later | ||
19 | */ | ||
20 | /** | ||
21 | * @file set/gnunet-service-set_union_strata_estimator.c | ||
22 | * @brief invertible bloom filter | ||
23 | * @author Florian Dold | ||
24 | * @author Christian Grothoff | ||
25 | */ | ||
26 | #include "platform.h" | ||
27 | #include "gnunet_util_lib.h" | ||
28 | #include "ibf.h" | ||
29 | #include "gnunet-service-set_union_strata_estimator.h" | ||
30 | |||
31 | |||
32 | /** | ||
33 | * Should we try compressing the strata estimator? This will | ||
34 | * break compatibility with the 0.10.1-network. | ||
35 | */ | ||
36 | #define FAIL_10_1_COMPATIBILTIY 1 | ||
37 | |||
38 | |||
39 | /** | ||
40 | * Write the given strata estimator to the buffer. | ||
41 | * | ||
42 | * @param se strata estimator to serialize | ||
43 | * @param[out] buf buffer to write to, must be of appropriate size | ||
44 | * @return number of bytes written to @a buf | ||
45 | */ | ||
46 | size_t | ||
47 | strata_estimator_write (const struct StrataEstimator *se, | ||
48 | void *buf) | ||
49 | { | ||
50 | char *sbuf = buf; | ||
51 | unsigned int i; | ||
52 | size_t osize; | ||
53 | |||
54 | GNUNET_assert (NULL != se); | ||
55 | for (i = 0; i < se->strata_count; i++) | ||
56 | { | ||
57 | ibf_write_slice (se->strata[i], | ||
58 | 0, | ||
59 | se->ibf_size, | ||
60 | &sbuf[se->ibf_size * IBF_BUCKET_SIZE * i]); | ||
61 | } | ||
62 | osize = se->ibf_size * IBF_BUCKET_SIZE * se->strata_count; | ||
63 | #if FAIL_10_1_COMPATIBILTIY | ||
64 | { | ||
65 | char *cbuf; | ||
66 | size_t nsize; | ||
67 | |||
68 | if (GNUNET_YES == | ||
69 | GNUNET_try_compression (buf, | ||
70 | osize, | ||
71 | &cbuf, | ||
72 | &nsize)) | ||
73 | { | ||
74 | GNUNET_memcpy (buf, cbuf, nsize); | ||
75 | osize = nsize; | ||
76 | GNUNET_free (cbuf); | ||
77 | } | ||
78 | } | ||
79 | #endif | ||
80 | return osize; | ||
81 | } | ||
82 | |||
83 | |||
84 | /** | ||
85 | * Read strata from the buffer into the given strata | ||
86 | * estimator. The strata estimator must already be allocated. | ||
87 | * | ||
88 | * @param buf buffer to read from | ||
89 | * @param buf_len number of bytes in @a buf | ||
90 | * @param is_compressed is the data compressed? | ||
91 | * @param[out] se strata estimator to write to | ||
92 | * @return #GNUNET_OK on success | ||
93 | */ | ||
94 | int | ||
95 | strata_estimator_read (const void *buf, | ||
96 | size_t buf_len, | ||
97 | int is_compressed, | ||
98 | struct StrataEstimator *se) | ||
99 | { | ||
100 | unsigned int i; | ||
101 | size_t osize; | ||
102 | char *dbuf; | ||
103 | |||
104 | dbuf = NULL; | ||
105 | if (GNUNET_YES == is_compressed) | ||
106 | { | ||
107 | osize = se->ibf_size * IBF_BUCKET_SIZE * se->strata_count; | ||
108 | dbuf = GNUNET_decompress (buf, | ||
109 | buf_len, | ||
110 | osize); | ||
111 | if (NULL == dbuf) | ||
112 | { | ||
113 | GNUNET_break_op (0); /* bad compressed input data */ | ||
114 | return GNUNET_SYSERR; | ||
115 | } | ||
116 | buf = dbuf; | ||
117 | buf_len = osize; | ||
118 | } | ||
119 | |||
120 | if (buf_len != se->strata_count * se->ibf_size * IBF_BUCKET_SIZE) | ||
121 | { | ||
122 | GNUNET_break (0); /* very odd error */ | ||
123 | GNUNET_free (dbuf); | ||
124 | return GNUNET_SYSERR; | ||
125 | } | ||
126 | |||
127 | for (i = 0; i < se->strata_count; i++) | ||
128 | { | ||
129 | ibf_read_slice (buf, 0, se->ibf_size, se->strata[i]); | ||
130 | buf += se->ibf_size * IBF_BUCKET_SIZE; | ||
131 | } | ||
132 | GNUNET_free (dbuf); | ||
133 | return GNUNET_OK; | ||
134 | } | ||
135 | |||
136 | |||
137 | /** | ||
138 | * Add a key to the strata estimator. | ||
139 | * | ||
140 | * @param se strata estimator to add the key to | ||
141 | * @param key key to add | ||
142 | */ | ||
143 | void | ||
144 | strata_estimator_insert (struct StrataEstimator *se, | ||
145 | struct IBF_Key key) | ||
146 | { | ||
147 | uint64_t v; | ||
148 | unsigned int i; | ||
149 | |||
150 | v = key.key_val; | ||
151 | /* count trailing '1'-bits of v */ | ||
152 | for (i = 0; v & 1; v >>= 1, i++) | ||
153 | /* empty */; | ||
154 | ibf_insert (se->strata[i], key); | ||
155 | } | ||
156 | |||
157 | |||
158 | /** | ||
159 | * Remove a key from the strata estimator. | ||
160 | * | ||
161 | * @param se strata estimator to remove the key from | ||
162 | * @param key key to remove | ||
163 | */ | ||
164 | void | ||
165 | strata_estimator_remove (struct StrataEstimator *se, | ||
166 | struct IBF_Key key) | ||
167 | { | ||
168 | uint64_t v; | ||
169 | unsigned int i; | ||
170 | |||
171 | v = key.key_val; | ||
172 | /* count trailing '1'-bits of v */ | ||
173 | for (i = 0; v & 1; v >>= 1, i++) | ||
174 | /* empty */; | ||
175 | ibf_remove (se->strata[i], key); | ||
176 | } | ||
177 | |||
178 | |||
179 | /** | ||
180 | * Create a new strata estimator with the given parameters. | ||
181 | * | ||
182 | * @param strata_count number of stratas, that is, number of ibfs in the estimator | ||
183 | * @param ibf_size size of each ibf stratum | ||
184 | * @param ibf_hashnum hashnum parameter of each ibf | ||
185 | * @return a freshly allocated, empty strata estimator, NULL on error | ||
186 | */ | ||
187 | struct StrataEstimator * | ||
188 | strata_estimator_create (unsigned int strata_count, | ||
189 | uint32_t ibf_size, | ||
190 | uint8_t ibf_hashnum) | ||
191 | { | ||
192 | struct StrataEstimator *se; | ||
193 | unsigned int i; | ||
194 | unsigned int j; | ||
195 | |||
196 | se = GNUNET_new (struct StrataEstimator); | ||
197 | se->strata_count = strata_count; | ||
198 | se->ibf_size = ibf_size; | ||
199 | se->strata = GNUNET_new_array (strata_count, | ||
200 | struct InvertibleBloomFilter *); | ||
201 | for (i = 0; i < strata_count; i++) | ||
202 | { | ||
203 | se->strata[i] = ibf_create (ibf_size, ibf_hashnum); | ||
204 | if (NULL == se->strata[i]) | ||
205 | { | ||
206 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, | ||
207 | "Failed to allocate memory for strata estimator\n"); | ||
208 | for (j = 0; j < i; j++) | ||
209 | ibf_destroy (se->strata[i]); | ||
210 | GNUNET_free (se); | ||
211 | return NULL; | ||
212 | } | ||
213 | } | ||
214 | return se; | ||
215 | } | ||
216 | |||
217 | |||
218 | /** | ||
219 | * Estimate set difference with two strata estimators, | ||
220 | * i.e. arrays of IBFs. | ||
221 | * Does not not modify its arguments. | ||
222 | * | ||
223 | * @param se1 first strata estimator | ||
224 | * @param se2 second strata estimator | ||
225 | * @return the estimated difference | ||
226 | */ | ||
227 | unsigned int | ||
228 | strata_estimator_difference (const struct StrataEstimator *se1, | ||
229 | const struct StrataEstimator *se2) | ||
230 | { | ||
231 | unsigned int count; | ||
232 | |||
233 | GNUNET_assert (se1->strata_count == se2->strata_count); | ||
234 | count = 0; | ||
235 | for (int i = se1->strata_count - 1; i >= 0; i--) | ||
236 | { | ||
237 | struct InvertibleBloomFilter *diff; | ||
238 | /* number of keys decoded from the ibf */ | ||
239 | |||
240 | /* FIXME: implement this without always allocating new IBFs */ | ||
241 | diff = ibf_dup (se1->strata[i]); | ||
242 | ibf_subtract (diff, se2->strata[i]); | ||
243 | for (int ibf_count = 0; GNUNET_YES; ibf_count++) | ||
244 | { | ||
245 | int more; | ||
246 | |||
247 | more = ibf_decode (diff, NULL, NULL); | ||
248 | if (GNUNET_NO == more) | ||
249 | { | ||
250 | count += ibf_count; | ||
251 | break; | ||
252 | } | ||
253 | /* Estimate if decoding fails or would not terminate */ | ||
254 | if ((GNUNET_SYSERR == more) || (ibf_count > diff->size)) | ||
255 | { | ||
256 | ibf_destroy (diff); | ||
257 | return count * (1 << (i + 1)); | ||
258 | } | ||
259 | } | ||
260 | ibf_destroy (diff); | ||
261 | } | ||
262 | return count; | ||
263 | } | ||
264 | |||
265 | |||
266 | /** | ||
267 | * Make a copy of a strata estimator. | ||
268 | * | ||
269 | * @param se the strata estimator to copy | ||
270 | * @return the copy | ||
271 | */ | ||
272 | struct StrataEstimator * | ||
273 | strata_estimator_dup (struct StrataEstimator *se) | ||
274 | { | ||
275 | struct StrataEstimator *c; | ||
276 | unsigned int i; | ||
277 | |||
278 | c = GNUNET_new (struct StrataEstimator); | ||
279 | c->strata_count = se->strata_count; | ||
280 | c->ibf_size = se->ibf_size; | ||
281 | c->strata = GNUNET_new_array (se->strata_count, | ||
282 | struct InvertibleBloomFilter *); | ||
283 | for (i = 0; i < se->strata_count; i++) | ||
284 | c->strata[i] = ibf_dup (se->strata[i]); | ||
285 | return c; | ||
286 | } | ||
287 | |||
288 | |||
289 | /** | ||
290 | * Destroy a strata estimator, free all of its resources. | ||
291 | * | ||
292 | * @param se strata estimator to destroy. | ||
293 | */ | ||
294 | void | ||
295 | strata_estimator_destroy (struct StrataEstimator *se) | ||
296 | { | ||
297 | unsigned int i; | ||
298 | |||
299 | for (i = 0; i < se->strata_count; i++) | ||
300 | ibf_destroy (se->strata[i]); | ||
301 | GNUNET_free (se->strata); | ||
302 | GNUNET_free (se); | ||
303 | } | ||