GNUnet 0.21.0
gnunet-service-set_union_strata_estimator.c
Go to the documentation of this file.
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 */
26#include "platform.h"
27#include "gnunet_util_lib.h"
28#include "ibf.h"
30
31
36#define FAIL_10_1_COMPATIBILTIY 1
37
38
46size_t
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 ==
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
94int
95strata_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
143void
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
158void
160 struct IBF_Key key)
161{
162 uint64_t v;
163 unsigned int i;
164
165 v = key.key_val;
166 /* count trailing '1'-bits of v */
167 for (i = 0; v & 1; v >>= 1, i++)
168 /* empty */;
169 ibf_remove (se->strata[i], key);
170}
171
172
181struct StrataEstimator *
183 uint32_t ibf_size,
184 uint8_t ibf_hashnum)
185{
186 struct StrataEstimator *se;
187 unsigned int i;
188 unsigned int j;
189
190 se = GNUNET_new (struct StrataEstimator);
192 se->ibf_size = ibf_size;
194 struct InvertibleBloomFilter *);
195 for (i = 0; i < strata_count; i++)
196 {
197 se->strata[i] = ibf_create (ibf_size, ibf_hashnum);
198 if (NULL == se->strata[i])
199 {
201 "Failed to allocate memory for strata estimator\n");
202 for (j = 0; j < i; j++)
203 ibf_destroy (se->strata[i]);
204 GNUNET_free (se);
205 return NULL;
206 }
207 }
208 return se;
209}
210
211
221unsigned int
223 const struct StrataEstimator *se2)
224{
225 unsigned int count;
226
228 count = 0;
229 for (int i = se1->strata_count - 1; i >= 0; i--)
230 {
231 struct InvertibleBloomFilter *diff;
232 /* number of keys decoded from the ibf */
233
234 /* FIXME: implement this without always allocating new IBFs */
235 diff = ibf_dup (se1->strata[i]);
236 ibf_subtract (diff, se2->strata[i]);
237 for (int ibf_count = 0; GNUNET_YES; ibf_count++)
238 {
239 int more;
240
241 more = ibf_decode (diff, NULL, NULL);
242 if (GNUNET_NO == more)
243 {
244 count += ibf_count;
245 break;
246 }
247 /* Estimate if decoding fails or would not terminate */
248 if ((GNUNET_SYSERR == more) || (ibf_count > diff->size))
249 {
250 ibf_destroy (diff);
251 return count * (1 << (i + 1));
252 }
253 }
254 ibf_destroy (diff);
255 }
256 return count;
257}
258
259
266struct StrataEstimator *
268{
269 struct StrataEstimator *c;
270 unsigned int i;
271
272 c = GNUNET_new (struct StrataEstimator);
273 c->strata_count = se->strata_count;
274 c->ibf_size = se->ibf_size;
276 struct InvertibleBloomFilter *);
277 for (i = 0; i < se->strata_count; i++)
278 c->strata[i] = ibf_dup (se->strata[i]);
279 return c;
280}
281
282
288void
290{
291 unsigned int i;
292
293 for (i = 0; i < se->strata_count; i++)
294 ibf_destroy (se->strata[i]);
295 GNUNET_free (se->strata);
296 GNUNET_free (se);
297}
void ibf_subtract(struct InvertibleBloomFilter *ibf1, const struct InvertibleBloomFilter *ibf2)
Subtract ibf2 from ibf1, storing the result in ibf1.
Definition: ibf.c:357
int ibf_decode(struct InvertibleBloomFilter *ibf, int *ret_side, struct IBF_Key *ret_id)
Decode and remove an element from the IBF, if possible.
Definition: ibf.c:229
void ibf_read_slice(const void *buf, uint32_t start, uint32_t count, struct InvertibleBloomFilter *ibf)
Read buckets from a buffer into an ibf.
Definition: ibf.c:324
void ibf_write_slice(const struct InvertibleBloomFilter *ibf, uint32_t start, uint32_t count, void *buf)
Write buckets from an ibf to a buffer.
Definition: ibf.c:291
void ibf_insert(struct InvertibleBloomFilter *ibf, struct IBF_Key key)
Insert a key into an IBF.
Definition: ibf.c:168
struct InvertibleBloomFilter * ibf_dup(const struct InvertibleBloomFilter *ibf)
Create a copy of an IBF, the copy has to be destroyed properly.
Definition: ibf.c:380
struct InvertibleBloomFilter * ibf_create(uint32_t size, uint8_t hash_num)
Create an invertible bloom filter.
Definition: ibf.c:80
void ibf_remove(struct InvertibleBloomFilter *ibf, struct IBF_Key key)
Remove a key from an IBF.
Definition: ibf.c:185
void ibf_destroy(struct InvertibleBloomFilter *ibf)
Destroy all resources associated with the invertible bloom filter.
Definition: ibf.c:404
#define IBF_BUCKET_SIZE
Size of one ibf bucket in bytes.
Definition: ibf.h:72
struct GNUNET_HashCode key
The key used in the DHT.
unsigned int strata_estimator_difference(const struct StrataEstimator *se1, const struct StrataEstimator *se2)
Estimate set difference with two strata estimators, i.e.
struct StrataEstimator * strata_estimator_create(unsigned int strata_count, uint32_t ibf_size, uint8_t ibf_hashnum)
Create a new strata estimator with the given parameters.
void strata_estimator_destroy(struct StrataEstimator *se)
Destroy a strata estimator, free all of its resources.
int strata_estimator_read(const void *buf, size_t buf_len, int is_compressed, struct StrataEstimator *se)
Read strata from the buffer into the given strata estimator.
size_t strata_estimator_write(const struct StrataEstimator *se, void *buf)
Write the given strata estimator to the buffer.
void strata_estimator_insert(struct StrataEstimator *se, struct IBF_Key key)
Add a key to the strata estimator.
struct StrataEstimator * strata_estimator_dup(struct StrataEstimator *se)
Make a copy of a strata estimator.
void strata_estimator_remove(struct StrataEstimator *se, struct IBF_Key key)
Remove a key from the strata estimator.
static unsigned int ibf_size
#define GNUNET_log(kind,...)
char * GNUNET_decompress(const char *input, size_t input_size, size_t output_size)
Decompress input, return the decompressed data as output.
Definition: compress.c:70
int GNUNET_try_compression(const char *data, size_t old_size, char **result, size_t *new_size)
Try to compress the given block of data using libz.
Definition: compress.c:33
#define GNUNET_memcpy(dst, src, n)
Call memcpy() but check for n being 0 first.
@ GNUNET_OK
@ GNUNET_YES
@ GNUNET_NO
@ GNUNET_SYSERR
#define GNUNET_break_op(cond)
Use this for assertion violations caused by other peers (i.e.
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
#define GNUNET_break(cond)
Use this for internal assertion violations that are not fatal (can be handled) but should not occur.
@ GNUNET_ERROR_TYPE_ERROR
#define GNUNET_new(type)
Allocate a struct or union of the given type.
#define GNUNET_new_array(n, type)
Allocate a size n array with structs or unions of the given type.
#define GNUNET_free(ptr)
Wrapper around free.
Keys that can be inserted into and removed from an IBF.
Definition: ibf.h:46
Invertible bloom filter (IBF).
Definition: ibf.h:83
uint32_t size
How many cells does this IBF have?
Definition: ibf.h:87
struct IBF_Count * count
How many times has a bucket been hit? Can be negative, as a result of IBF subtraction.
Definition: ibf.h:112
A handle to a strata estimator.
unsigned int ibf_size
Size of each IBF stratum (in bytes)
struct InvertibleBloomFilter ** strata
The IBFs of this strata estimator.
unsigned int strata_count
Size of the IBF array in strata.