2 This file is part of GNUnet
3 (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., 59 Temple Place - Suite 330,
18 Boston, MA 02111-1307, USA.
23 * @brief invertible bloom filter
24 * @author Florian Dold
28 #include "gnunet_util_lib.h"
30 #include "strata_estimator.h"
33 strata_estimator_write (const struct StrataEstimator *se, void *buf)
37 GNUNET_assert (NULL != se);
38 for (i = 0; i < se->strata_count; i++)
40 ibf_write_slice (se->strata[i], 0, se->ibf_size, buf);
41 buf += se->ibf_size * IBF_BUCKET_SIZE;
46 strata_estimator_read (const void *buf, struct StrataEstimator *se)
49 for (i = 0; i < se->strata_count; i++)
51 ibf_read_slice (buf, 0, se->ibf_size, se->strata[i]);
52 buf += se->ibf_size * IBF_BUCKET_SIZE;
58 strata_estimator_insert (struct StrataEstimator *se, struct IBF_Key key)
63 /* count trailing '1'-bits of v */
64 for (i = 0; v & 1; v>>=1, i++)
66 ibf_insert (se->strata[i], key);
71 strata_estimator_remove (struct StrataEstimator *se, struct IBF_Key key)
76 /* count trailing '1'-bits of v */
77 for (i = 0; v & 1; v>>=1, i++)
79 ibf_remove (se->strata[i], key);
84 struct StrataEstimator *
85 strata_estimator_create (unsigned int strata_count, uint32_t ibf_size, uint8_t ibf_hashnum)
87 struct StrataEstimator *se;
90 /* fixme: allocate everything in one chunk */
92 se = GNUNET_new (struct StrataEstimator);
93 se->strata_count = strata_count;
94 se->ibf_size = ibf_size;
95 se->strata = GNUNET_malloc (sizeof (struct InvertibleBloomFilter *) * strata_count);
96 for (i = 0; i < strata_count; i++)
97 se->strata[i] = ibf_create (ibf_size, ibf_hashnum);
103 * Estimate set difference with two strata estimators,
104 * i.e. arrays of IBFs.
105 * Does not not modify its arguments.
107 * @param se1 first strata estimator
108 * @param se2 second strata estimator
109 * @return the estimated difference
112 strata_estimator_difference (const struct StrataEstimator *se1,
113 const struct StrataEstimator *se2)
118 GNUNET_assert (se1->strata_count == se2->strata_count);
120 for (i = se1->strata_count - 1; i >= 0; i--)
122 struct InvertibleBloomFilter *diff;
123 /* number of keys decoded from the ibf */
125 /* FIXME: implement this without always allocating new IBFs */
126 diff = ibf_dup (se1->strata[i]);
127 ibf_subtract (diff, se2->strata[i]);
128 for (ibf_count = 0; GNUNET_YES; ibf_count++)
132 more = ibf_decode (diff, NULL, NULL);
133 if (GNUNET_NO == more)
138 /* Estimate if decoding fails or would not terminate */
139 if ((GNUNET_SYSERR == more) || (ibf_count > diff->size))
142 return count * (1 << (i + 1));
151 * Make a copy of a strata estimator.
153 * @param se the strata estimator to copy
156 struct StrataEstimator *
157 strata_estimator_dup (struct StrataEstimator *se)
159 struct StrataEstimator *c;
162 c = GNUNET_new (struct StrataEstimator);
163 c->strata_count = se->strata_count;
164 c->ibf_size = se->ibf_size;
165 c->strata = GNUNET_malloc (sizeof (struct InvertibleBloomFilter *) * se->strata_count);
166 for (i = 0; i < se->strata_count; i++)
167 c->strata[i] = ibf_dup (se->strata[i]);
173 strata_estimator_destroy (struct StrataEstimator *se)
176 for (i = 0; i < se->strata_count; i++)
177 ibf_destroy (se->strata[i]);
178 GNUNET_free (se->strata);