summaryrefslogtreecommitdiff
path: root/src/set/gnunet-service-set_union_strata_estimator.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/set/gnunet-service-set_union_strata_estimator.c')
-rw-r--r--src/set/gnunet-service-set_union_strata_estimator.c210
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 */
46size_t 46size_t
47strata_estimator_write (const struct StrataEstimator *se, 47strata_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 */
94int 94int
95strata_estimator_read (const void *buf, 95strata_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 */
143void 143void
144strata_estimator_insert (struct StrataEstimator *se, 144strata_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 */
164void 164void
165strata_estimator_remove (struct StrataEstimator *se, 165strata_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 */
187struct StrataEstimator * 187struct StrataEstimator *
188strata_estimator_create (unsigned int strata_count, 188strata_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 */
227unsigned int 227unsigned int
228strata_estimator_difference (const struct StrataEstimator *se1, 228strata_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 */
272struct StrataEstimator * 272struct StrataEstimator *
273strata_estimator_dup (struct StrataEstimator *se) 273strata_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 */
294void 294void
295strata_estimator_destroy (struct StrataEstimator *se) 295strata_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}