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.c202
1 files changed, 101 insertions, 101 deletions
diff --git a/src/set/gnunet-service-set_union_strata_estimator.c b/src/set/gnunet-service-set_union_strata_estimator.c
index dcc00a680..eee0ec8d3 100644
--- a/src/set/gnunet-service-set_union_strata_estimator.c
+++ b/src/set/gnunet-service-set_union_strata_estimator.c
@@ -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)
106 { 112 {
107 osize = se->ibf_size * IBF_BUCKET_SIZE * se->strata_count; 113 GNUNET_break_op (0); /* bad compressed input data */
108 dbuf = GNUNET_decompress(buf, 114 return GNUNET_SYSERR;
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 } 115 }
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,8 +141,8 @@ 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;
@@ -151,7 +151,7 @@ strata_estimator_insert(struct StrataEstimator *se,
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,8 +162,8 @@ 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;
@@ -172,7 +172,7 @@ strata_estimator_remove(struct StrataEstimator *se,
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])
202 { 205 {
203 se->strata[i] = ibf_create(ibf_size, ibf_hashnum); 206 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
204 if (NULL == se->strata[i]) 207 "Failed to allocate memory for strata estimator\n");
205 { 208 for (j = 0; j < i; j++)
206 GNUNET_log(GNUNET_ERROR_TYPE_ERROR, 209 ibf_destroy (se->strata[i]);
207 "Failed to allocate memory for strata estimator\n"); 210 GNUNET_free (se);
208 for (j = 0; j < i; j++) 211 return NULL;
209 ibf_destroy(se->strata[i]);
210 GNUNET_free(se);
211 return NULL;
212 }
213 } 212 }
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++)
236 { 244 {
237 struct InvertibleBloomFilter *diff; 245 int more;
238 /* number of keys decoded from the ibf */ 246
239 247 more = ibf_decode (diff, NULL, NULL);
240 /* FIXME: implement this without always allocating new IBFs */ 248 if (GNUNET_NO == more)
241 diff = ibf_dup(se1->strata[i]); 249 {
242 ibf_subtract(diff, se2->strata[i]); 250 count += ibf_count;
243 for (int ibf_count = 0; GNUNET_YES; ibf_count++) 251 break;
244 { 252 }
245 int more; 253 /* Estimate if decoding fails or would not terminate */
246 254 if ((GNUNET_SYSERR == more) || (ibf_count > diff->size))
247 more = ibf_decode(diff, NULL, NULL); 255 {
248 if (GNUNET_NO == more) 256 ibf_destroy (diff);
249 { 257 return count * (1 << (i + 1));
250 count += ibf_count; 258 }
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 } 259 }
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}