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 | 210 |
1 files changed, 105 insertions, 105 deletions
diff --git a/src/set/gnunet-service-set_union_strata_estimator.c b/src/set/gnunet-service-set_union_strata_estimator.c index 688c32306..dcc00a680 100644 --- a/src/set/gnunet-service-set_union_strata_estimator.c +++ b/src/set/gnunet-service-set_union_strata_estimator.c | |||
@@ -11,12 +11,12 @@ | |||
11 | WITHOUT ANY WARRANTY; without even the implied warranty of | 11 | WITHOUT ANY WARRANTY; without even the implied warranty of |
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | 12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
13 | Affero General Public License for more details. | 13 | Affero General Public License for more details. |
14 | 14 | ||
15 | You should have received a copy of the GNU Affero General Public License | 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/>. | 16 | along with this program. If not, see <http://www.gnu.org/licenses/>. |
17 | 17 | ||
18 | SPDX-License-Identifier: AGPL3.0-or-later | 18 | SPDX-License-Identifier: AGPL3.0-or-later |
19 | */ | 19 | */ |
20 | /** | 20 | /** |
21 | * @file set/gnunet-service-set_union_strata_estimator.c | 21 | * @file set/gnunet-service-set_union_strata_estimator.c |
22 | * @brief invertible bloom filter | 22 | * @brief invertible bloom filter |
@@ -44,21 +44,21 @@ | |||
44 | * @return number of bytes written to @a buf | 44 | * @return number of bytes written to @a buf |
45 | */ | 45 | */ |
46 | size_t | 46 | size_t |
47 | strata_estimator_write (const struct StrataEstimator *se, | 47 | strata_estimator_write(const struct StrataEstimator *se, |
48 | void *buf) | 48 | void *buf) |
49 | { | 49 | { |
50 | char *sbuf = buf; | 50 | char *sbuf = buf; |
51 | unsigned int i; | 51 | unsigned int i; |
52 | size_t osize; | 52 | size_t osize; |
53 | 53 | ||
54 | GNUNET_assert (NULL != se); | 54 | GNUNET_assert(NULL != se); |
55 | for (i = 0; i < se->strata_count; i++) | 55 | for (i = 0; i < se->strata_count; i++) |
56 | { | 56 | { |
57 | ibf_write_slice (se->strata[i], | 57 | ibf_write_slice(se->strata[i], |
58 | 0, | 58 | 0, |
59 | se->ibf_size, | 59 | se->ibf_size, |
60 | &sbuf[se->ibf_size * IBF_BUCKET_SIZE * i]); | 60 | &sbuf[se->ibf_size * IBF_BUCKET_SIZE * i]); |
61 | } | 61 | } |
62 | osize = se->ibf_size * IBF_BUCKET_SIZE * se->strata_count; | 62 | osize = se->ibf_size * IBF_BUCKET_SIZE * se->strata_count; |
63 | #if FAIL_10_1_COMPATIBILTIY | 63 | #if FAIL_10_1_COMPATIBILTIY |
64 | { | 64 | { |
@@ -66,15 +66,15 @@ strata_estimator_write (const struct StrataEstimator *se, | |||
66 | size_t nsize; | 66 | size_t nsize; |
67 | 67 | ||
68 | if (GNUNET_YES == | 68 | if (GNUNET_YES == |
69 | GNUNET_try_compression (buf, | 69 | GNUNET_try_compression(buf, |
70 | osize, | 70 | osize, |
71 | &cbuf, | 71 | &cbuf, |
72 | &nsize)) | 72 | &nsize)) |
73 | { | 73 | { |
74 | GNUNET_memcpy (buf, cbuf, nsize); | 74 | GNUNET_memcpy(buf, cbuf, nsize); |
75 | osize = nsize; | 75 | osize = nsize; |
76 | GNUNET_free (cbuf); | 76 | GNUNET_free(cbuf); |
77 | } | 77 | } |
78 | } | 78 | } |
79 | #endif | 79 | #endif |
80 | return osize; | 80 | return osize; |
@@ -92,10 +92,10 @@ strata_estimator_write (const struct StrataEstimator *se, | |||
92 | * @return #GNUNET_OK on success | 92 | * @return #GNUNET_OK on success |
93 | */ | 93 | */ |
94 | int | 94 | int |
95 | strata_estimator_read (const void *buf, | 95 | strata_estimator_read(const void *buf, |
96 | size_t buf_len, | 96 | size_t buf_len, |
97 | int is_compressed, | 97 | int is_compressed, |
98 | struct StrataEstimator *se) | 98 | struct StrataEstimator *se) |
99 | { | 99 | { |
100 | unsigned int i; | 100 | unsigned int i; |
101 | size_t osize; | 101 | size_t osize; |
@@ -103,33 +103,33 @@ strata_estimator_read (const void *buf, | |||
103 | 103 | ||
104 | dbuf = NULL; | 104 | dbuf = NULL; |
105 | if (GNUNET_YES == is_compressed) | 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 | { | 106 | { |
113 | GNUNET_break_op (0); /* bad compressed input data */ | 107 | osize = se->ibf_size * IBF_BUCKET_SIZE * se->strata_count; |
114 | return GNUNET_SYSERR; | 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; | ||
115 | } | 118 | } |
116 | buf = dbuf; | ||
117 | buf_len = osize; | ||
118 | } | ||
119 | 119 | ||
120 | if (buf_len != se->strata_count * se->ibf_size * IBF_BUCKET_SIZE) | 120 | if (buf_len != se->strata_count * se->ibf_size * IBF_BUCKET_SIZE) |
121 | { | 121 | { |
122 | GNUNET_break (0); /* very odd error */ | 122 | GNUNET_break(0); /* very odd error */ |
123 | GNUNET_free_non_null (dbuf); | 123 | GNUNET_free_non_null(dbuf); |
124 | return GNUNET_SYSERR; | 124 | return GNUNET_SYSERR; |
125 | } | 125 | } |
126 | 126 | ||
127 | for (i = 0; i < se->strata_count; i++) | 127 | for (i = 0; i < se->strata_count; i++) |
128 | { | 128 | { |
129 | ibf_read_slice (buf, 0, se->ibf_size, se->strata[i]); | 129 | ibf_read_slice(buf, 0, se->ibf_size, se->strata[i]); |
130 | buf += se->ibf_size * IBF_BUCKET_SIZE; | 130 | buf += se->ibf_size * IBF_BUCKET_SIZE; |
131 | } | 131 | } |
132 | GNUNET_free_non_null (dbuf); | 132 | GNUNET_free_non_null(dbuf); |
133 | return GNUNET_OK; | 133 | return GNUNET_OK; |
134 | } | 134 | } |
135 | 135 | ||
@@ -141,17 +141,17 @@ strata_estimator_read (const void *buf, | |||
141 | * @param key key to add | 141 | * @param key key to add |
142 | */ | 142 | */ |
143 | void | 143 | void |
144 | strata_estimator_insert (struct StrataEstimator *se, | 144 | strata_estimator_insert(struct StrataEstimator *se, |
145 | struct IBF_Key key) | 145 | struct IBF_Key key) |
146 | { | 146 | { |
147 | uint64_t v; | 147 | uint64_t v; |
148 | unsigned int i; | 148 | unsigned int i; |
149 | 149 | ||
150 | v = key.key_val; | 150 | v = key.key_val; |
151 | /* count trailing '1'-bits of v */ | 151 | /* count trailing '1'-bits of v */ |
152 | for (i = 0; v & 1; v>>=1, i++) | 152 | for (i = 0; v & 1; v >>= 1, i++) |
153 | /* empty */; | 153 | /* empty */; |
154 | ibf_insert (se->strata[i], key); | 154 | ibf_insert(se->strata[i], key); |
155 | } | 155 | } |
156 | 156 | ||
157 | 157 | ||
@@ -162,17 +162,17 @@ strata_estimator_insert (struct StrataEstimator *se, | |||
162 | * @param key key to remove | 162 | * @param key key to remove |
163 | */ | 163 | */ |
164 | void | 164 | void |
165 | strata_estimator_remove (struct StrataEstimator *se, | 165 | strata_estimator_remove(struct StrataEstimator *se, |
166 | struct IBF_Key key) | 166 | struct IBF_Key key) |
167 | { | 167 | { |
168 | uint64_t v; | 168 | uint64_t v; |
169 | unsigned int i; | 169 | unsigned int i; |
170 | 170 | ||
171 | v = key.key_val; | 171 | v = key.key_val; |
172 | /* count trailing '1'-bits of v */ | 172 | /* count trailing '1'-bits of v */ |
173 | for (i = 0; v & 1; v>>=1, i++) | 173 | for (i = 0; v & 1; v >>= 1, i++) |
174 | /* empty */; | 174 | /* empty */; |
175 | ibf_remove (se->strata[i], key); | 175 | ibf_remove(se->strata[i], key); |
176 | } | 176 | } |
177 | 177 | ||
178 | 178 | ||
@@ -185,32 +185,32 @@ strata_estimator_remove (struct StrataEstimator *se, | |||
185 | * @return a freshly allocated, empty strata estimator, NULL on error | 185 | * @return a freshly allocated, empty strata estimator, NULL on error |
186 | */ | 186 | */ |
187 | struct StrataEstimator * | 187 | struct StrataEstimator * |
188 | strata_estimator_create (unsigned int strata_count, | 188 | strata_estimator_create(unsigned int strata_count, |
189 | uint32_t ibf_size, | 189 | uint32_t ibf_size, |
190 | uint8_t ibf_hashnum) | 190 | uint8_t ibf_hashnum) |
191 | { | 191 | { |
192 | struct StrataEstimator *se; | 192 | struct StrataEstimator *se; |
193 | unsigned int i; | 193 | unsigned int i; |
194 | unsigned int j; | 194 | unsigned int j; |
195 | 195 | ||
196 | se = GNUNET_new (struct StrataEstimator); | 196 | se = GNUNET_new(struct StrataEstimator); |
197 | se->strata_count = strata_count; | 197 | se->strata_count = strata_count; |
198 | se->ibf_size = ibf_size; | 198 | se->ibf_size = ibf_size; |
199 | se->strata = GNUNET_new_array (strata_count, | 199 | se->strata = GNUNET_new_array(strata_count, |
200 | struct InvertibleBloomFilter *); | 200 | struct InvertibleBloomFilter *); |
201 | for (i = 0; i < strata_count; i++) | 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 | { | 202 | { |
206 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, | 203 | se->strata[i] = ibf_create(ibf_size, ibf_hashnum); |
207 | "Failed to allocate memory for strata estimator\n"); | 204 | if (NULL == se->strata[i]) |
208 | for (j = 0; j < i; j++) | 205 | { |
209 | ibf_destroy (se->strata[i]); | 206 | GNUNET_log(GNUNET_ERROR_TYPE_ERROR, |
210 | GNUNET_free (se); | 207 | "Failed to allocate memory for strata estimator\n"); |
211 | return NULL; | 208 | for (j = 0; j < i; j++) |
209 | ibf_destroy(se->strata[i]); | ||
210 | GNUNET_free(se); | ||
211 | return NULL; | ||
212 | } | ||
212 | } | 213 | } |
213 | } | ||
214 | return se; | 214 | return se; |
215 | } | 215 | } |
216 | 216 | ||
@@ -225,40 +225,40 @@ strata_estimator_create (unsigned int strata_count, | |||
225 | * @return the estimated difference | 225 | * @return the estimated difference |
226 | */ | 226 | */ |
227 | unsigned int | 227 | unsigned int |
228 | strata_estimator_difference (const struct StrataEstimator *se1, | 228 | strata_estimator_difference(const struct StrataEstimator *se1, |
229 | const struct StrataEstimator *se2) | 229 | const struct StrataEstimator *se2) |
230 | { | 230 | { |
231 | unsigned int count; | 231 | unsigned int count; |
232 | 232 | ||
233 | GNUNET_assert (se1->strata_count == se2->strata_count); | 233 | GNUNET_assert(se1->strata_count == se2->strata_count); |
234 | count = 0; | 234 | count = 0; |
235 | for (int i = se1->strata_count - 1; i >= 0; i--) | 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 | { | 236 | { |
245 | int more; | 237 | struct InvertibleBloomFilter *diff; |
246 | 238 | /* number of keys decoded from the ibf */ | |
247 | more = ibf_decode (diff, NULL, NULL); | 239 | |
248 | if (GNUNET_NO == more) | 240 | /* FIXME: implement this without always allocating new IBFs */ |
249 | { | 241 | diff = ibf_dup(se1->strata[i]); |
250 | count += ibf_count; | 242 | ibf_subtract(diff, se2->strata[i]); |
251 | break; | 243 | for (int ibf_count = 0; GNUNET_YES; ibf_count++) |
252 | } | 244 | { |
253 | /* Estimate if decoding fails or would not terminate */ | 245 | int more; |
254 | if ((GNUNET_SYSERR == more) || (ibf_count > diff->size)) | 246 | |
255 | { | 247 | more = ibf_decode(diff, NULL, NULL); |
256 | ibf_destroy (diff); | 248 | if (GNUNET_NO == more) |
257 | return count * (1 << (i + 1)); | 249 | { |
258 | } | 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); | ||
259 | } | 261 | } |
260 | ibf_destroy (diff); | ||
261 | } | ||
262 | return count; | 262 | return count; |
263 | } | 263 | } |
264 | 264 | ||
@@ -270,18 +270,18 @@ strata_estimator_difference (const struct StrataEstimator *se1, | |||
270 | * @return the copy | 270 | * @return the copy |
271 | */ | 271 | */ |
272 | struct StrataEstimator * | 272 | struct StrataEstimator * |
273 | strata_estimator_dup (struct StrataEstimator *se) | 273 | strata_estimator_dup(struct StrataEstimator *se) |
274 | { | 274 | { |
275 | struct StrataEstimator *c; | 275 | struct StrataEstimator *c; |
276 | unsigned int i; | 276 | unsigned int i; |
277 | 277 | ||
278 | c = GNUNET_new (struct StrataEstimator); | 278 | c = GNUNET_new(struct StrataEstimator); |
279 | c->strata_count = se->strata_count; | 279 | c->strata_count = se->strata_count; |
280 | c->ibf_size = se->ibf_size; | 280 | c->ibf_size = se->ibf_size; |
281 | c->strata = GNUNET_new_array (se->strata_count, | 281 | c->strata = GNUNET_new_array(se->strata_count, |
282 | struct InvertibleBloomFilter *); | 282 | struct InvertibleBloomFilter *); |
283 | for (i = 0; i < se->strata_count; i++) | 283 | for (i = 0; i < se->strata_count; i++) |
284 | c->strata[i] = ibf_dup (se->strata[i]); | 284 | c->strata[i] = ibf_dup(se->strata[i]); |
285 | return c; | 285 | return c; |
286 | } | 286 | } |
287 | 287 | ||
@@ -292,12 +292,12 @@ strata_estimator_dup (struct StrataEstimator *se) | |||
292 | * @param se strata estimator to destroy. | 292 | * @param se strata estimator to destroy. |
293 | */ | 293 | */ |
294 | void | 294 | void |
295 | strata_estimator_destroy (struct StrataEstimator *se) | 295 | strata_estimator_destroy(struct StrataEstimator *se) |
296 | { | 296 | { |
297 | unsigned int i; | 297 | unsigned int i; |
298 | 298 | ||
299 | for (i = 0; i < se->strata_count; i++) | 299 | for (i = 0; i < se->strata_count; i++) |
300 | ibf_destroy (se->strata[i]); | 300 | ibf_destroy(se->strata[i]); |
301 | GNUNET_free (se->strata); | 301 | GNUNET_free(se->strata); |
302 | GNUNET_free (se); | 302 | GNUNET_free(se); |
303 | } | 303 | } |