2 This file is part of GNUnet
3 Copyright (C) 2012 Christian Grothoff (and other contributing authors)
5 GNUnet is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published
7 by the Free Software Foundation; either version 3, or (at your
8 option) any later version.
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 General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with GNUnet; see the file COPYING. If not, write to the
17 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
18 Boston, MA 02110-1301, USA.
21 * @file set/gnunet-service-set_union_strata_estimator.c
22 * @brief invertible bloom filter
23 * @author Florian Dold
26 #include "gnunet_util_lib.h"
28 #include "gnunet-service-set_union_strata_estimator.h"
32 * Write the given strata estimator to the buffer.
34 * @param se strata estimator to serialize
35 * @param buf buffer to write to, must be of appropriate size
38 strata_estimator_write (const struct StrataEstimator *se,
43 GNUNET_assert (NULL != se);
44 for (i = 0; i < se->strata_count; i++)
46 ibf_write_slice (se->strata[i], 0, se->ibf_size, buf);
47 buf += se->ibf_size * IBF_BUCKET_SIZE;
53 * Read strata from the buffer into the given strata
54 * estimator. The strata estimator must already be allocated.
56 * @param buf buffer to read from
57 * @param se strata estimator to write to
60 strata_estimator_read (const void *buf,
61 struct StrataEstimator *se)
65 for (i = 0; i < se->strata_count; i++)
67 ibf_read_slice (buf, 0, se->ibf_size, se->strata[i]);
68 buf += se->ibf_size * IBF_BUCKET_SIZE;
74 * Add a key to the strata estimator.
76 * @param se strata estimator to add the key to
77 * @param key key to add
80 strata_estimator_insert (struct StrataEstimator *se,
87 /* count trailing '1'-bits of v */
88 for (i = 0; v & 1; v>>=1, i++)
90 ibf_insert (se->strata[i], key);
95 * Remove a key from the strata estimator.
97 * @param se strata estimator to remove the key from
98 * @param key key to remove
101 strata_estimator_remove (struct StrataEstimator *se,
108 /* count trailing '1'-bits of v */
109 for (i = 0; v & 1; v>>=1, i++)
111 ibf_remove (se->strata[i], key);
116 * Create a new strata estimator with the given parameters.
118 * @param strata_count number of stratas, that is, number of ibfs in the estimator
119 * @param ibf_size size of each ibf stratum
120 * @param ibf_hashnum hashnum parameter of each ibf
121 * @return a freshly allocated, empty strata estimator
123 struct StrataEstimator *
124 strata_estimator_create (unsigned int strata_count,
128 struct StrataEstimator *se;
131 /* fixme: allocate everything in one chunk */
132 se = GNUNET_new (struct StrataEstimator);
133 se->strata_count = strata_count;
134 se->ibf_size = ibf_size;
135 se->strata = GNUNET_malloc (sizeof (struct InvertibleBloomFilter *) * strata_count);
136 for (i = 0; i < strata_count; i++)
137 se->strata[i] = ibf_create (ibf_size, ibf_hashnum);
143 * Estimate set difference with two strata estimators,
144 * i.e. arrays of IBFs.
145 * Does not not modify its arguments.
147 * @param se1 first strata estimator
148 * @param se2 second strata estimator
149 * @return the estimated difference
152 strata_estimator_difference (const struct StrataEstimator *se1,
153 const struct StrataEstimator *se2)
158 GNUNET_assert (se1->strata_count == se2->strata_count);
160 for (i = se1->strata_count - 1; i >= 0; i--)
162 struct InvertibleBloomFilter *diff;
163 /* number of keys decoded from the ibf */
166 /* FIXME: implement this without always allocating new IBFs */
167 diff = ibf_dup (se1->strata[i]);
168 ibf_subtract (diff, se2->strata[i]);
169 for (ibf_count = 0; GNUNET_YES; ibf_count++)
173 more = ibf_decode (diff, NULL, NULL);
174 if (GNUNET_NO == more)
179 /* Estimate if decoding fails or would not terminate */
180 if ((GNUNET_SYSERR == more) || (ibf_count > diff->size))
183 return count * (1 << (i + 1));
193 * Make a copy of a strata estimator.
195 * @param se the strata estimator to copy
198 struct StrataEstimator *
199 strata_estimator_dup (struct StrataEstimator *se)
201 struct StrataEstimator *c;
204 c = GNUNET_new (struct StrataEstimator);
205 c->strata_count = se->strata_count;
206 c->ibf_size = se->ibf_size;
207 c->strata = GNUNET_malloc (sizeof (struct InvertibleBloomFilter *) * se->strata_count);
208 for (i = 0; i < se->strata_count; i++)
209 c->strata[i] = ibf_dup (se->strata[i]);
215 * Destroy a strata estimator, free all of its resources.
217 * @param se strata estimator to destroy.
220 strata_estimator_destroy (struct StrataEstimator *se)
224 for (i = 0; i < se->strata_count; i++)
225 ibf_destroy (se->strata[i]);
226 GNUNET_free (se->strata);