diff options
author | Christian Grothoff <christian@grothoff.org> | 2014-11-27 14:10:47 +0000 |
---|---|---|
committer | Christian Grothoff <christian@grothoff.org> | 2014-11-27 14:10:47 +0000 |
commit | 0d3932d5151f61cf4838123dd7edc66f27c08dfc (patch) | |
tree | 7804fca56796e33c77cd46738e296dc2d61a1973 /src/set/gnunet-service-set_union_strata_estimator.c | |
parent | 6062da84163355a854b8213538ad82127552adc0 (diff) | |
download | gnunet-0d3932d5151f61cf4838123dd7edc66f27c08dfc.tar.gz gnunet-0d3932d5151f61cf4838123dd7edc66f27c08dfc.zip |
-renaming
Diffstat (limited to 'src/set/gnunet-service-set_union_strata_estimator.c')
-rw-r--r-- | src/set/gnunet-service-set_union_strata_estimator.c | 221 |
1 files changed, 221 insertions, 0 deletions
diff --git a/src/set/gnunet-service-set_union_strata_estimator.c b/src/set/gnunet-service-set_union_strata_estimator.c new file mode 100644 index 000000000..2288e25f5 --- /dev/null +++ b/src/set/gnunet-service-set_union_strata_estimator.c | |||
@@ -0,0 +1,221 @@ | |||
1 | /* | ||
2 | This file is part of GNUnet | ||
3 | (C) 2012 Christian Grothoff (and other contributing authors) | ||
4 | |||
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. | ||
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 | General Public License for more details. | ||
14 | |||
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. | ||
19 | */ | ||
20 | /** | ||
21 | * @file set/gnunet-service-set_union_strata_estimator.c | ||
22 | * @brief invertible bloom filter | ||
23 | * @author Florian Dold | ||
24 | */ | ||
25 | |||
26 | #include "platform.h" | ||
27 | #include "gnunet_util_lib.h" | ||
28 | #include "ibf.h" | ||
29 | #include "gnunet-service-set_union_strata_estimator.h" | ||
30 | |||
31 | |||
32 | /** | ||
33 | * Write the given strata estimator to the buffer. | ||
34 | * | ||
35 | * @param se strata estimator to serialize | ||
36 | * @param buf buffer to write to, must be of appropriate size | ||
37 | */ | ||
38 | void | ||
39 | strata_estimator_write (const struct StrataEstimator *se, void *buf) | ||
40 | { | ||
41 | int i; | ||
42 | |||
43 | GNUNET_assert (NULL != se); | ||
44 | for (i = 0; i < se->strata_count; i++) | ||
45 | { | ||
46 | ibf_write_slice (se->strata[i], 0, se->ibf_size, buf); | ||
47 | buf += se->ibf_size * IBF_BUCKET_SIZE; | ||
48 | } | ||
49 | } | ||
50 | |||
51 | |||
52 | /** | ||
53 | * Read strata from the buffer into the given strata | ||
54 | * estimator. The strata estimator must already be allocated. | ||
55 | * | ||
56 | * @param buf buffer to read from | ||
57 | * @param se strata estimator to write to | ||
58 | */ | ||
59 | void | ||
60 | strata_estimator_read (const void *buf, struct StrataEstimator *se) | ||
61 | { | ||
62 | int i; | ||
63 | for (i = 0; i < se->strata_count; i++) | ||
64 | { | ||
65 | ibf_read_slice (buf, 0, se->ibf_size, se->strata[i]); | ||
66 | buf += se->ibf_size * IBF_BUCKET_SIZE; | ||
67 | } | ||
68 | } | ||
69 | |||
70 | |||
71 | /** | ||
72 | * Add a key to the strata estimator. | ||
73 | * | ||
74 | * @param se strata estimator to add the key to | ||
75 | * @param key key to add | ||
76 | */ | ||
77 | void | ||
78 | strata_estimator_insert (struct StrataEstimator *se, struct IBF_Key key) | ||
79 | { | ||
80 | uint64_t v; | ||
81 | int i; | ||
82 | v = key.key_val; | ||
83 | /* count trailing '1'-bits of v */ | ||
84 | for (i = 0; v & 1; v>>=1, i++) | ||
85 | /* empty */; | ||
86 | ibf_insert (se->strata[i], key); | ||
87 | } | ||
88 | |||
89 | |||
90 | /** | ||
91 | * Remove a key from the strata estimator. | ||
92 | * | ||
93 | * @param se strata estimator to remove the key from | ||
94 | * @param key key to remove | ||
95 | */ | ||
96 | void | ||
97 | strata_estimator_remove (struct StrataEstimator *se, struct IBF_Key key) | ||
98 | { | ||
99 | uint64_t v; | ||
100 | int i; | ||
101 | v = key.key_val; | ||
102 | /* count trailing '1'-bits of v */ | ||
103 | for (i = 0; v & 1; v>>=1, i++) | ||
104 | /* empty */; | ||
105 | ibf_remove (se->strata[i], key); | ||
106 | } | ||
107 | |||
108 | |||
109 | /** | ||
110 | * Create a new strata estimator with the given parameters. | ||
111 | * | ||
112 | * @param strata_count number of stratas, that is, number of ibfs in the estimator | ||
113 | * @param ibf_size size of each ibf stratum | ||
114 | * @param ibf_hashnum hashnum parameter of each ibf | ||
115 | * @return a freshly allocated, empty strata estimator | ||
116 | */ | ||
117 | struct StrataEstimator * | ||
118 | strata_estimator_create (unsigned int strata_count, uint32_t ibf_size, uint8_t ibf_hashnum) | ||
119 | { | ||
120 | struct StrataEstimator *se; | ||
121 | int i; | ||
122 | |||
123 | /* fixme: allocate everything in one chunk */ | ||
124 | |||
125 | se = GNUNET_new (struct StrataEstimator); | ||
126 | se->strata_count = strata_count; | ||
127 | se->ibf_size = ibf_size; | ||
128 | se->strata = GNUNET_malloc (sizeof (struct InvertibleBloomFilter *) * strata_count); | ||
129 | for (i = 0; i < strata_count; i++) | ||
130 | se->strata[i] = ibf_create (ibf_size, ibf_hashnum); | ||
131 | return se; | ||
132 | } | ||
133 | |||
134 | |||
135 | /** | ||
136 | * Estimate set difference with two strata estimators, | ||
137 | * i.e. arrays of IBFs. | ||
138 | * Does not not modify its arguments. | ||
139 | * | ||
140 | * @param se1 first strata estimator | ||
141 | * @param se2 second strata estimator | ||
142 | * @return the estimated difference | ||
143 | */ | ||
144 | unsigned int | ||
145 | strata_estimator_difference (const struct StrataEstimator *se1, | ||
146 | const struct StrataEstimator *se2) | ||
147 | { | ||
148 | int i; | ||
149 | int count; | ||
150 | |||
151 | GNUNET_assert (se1->strata_count == se2->strata_count); | ||
152 | count = 0; | ||
153 | for (i = se1->strata_count - 1; i >= 0; i--) | ||
154 | { | ||
155 | struct InvertibleBloomFilter *diff; | ||
156 | /* number of keys decoded from the ibf */ | ||
157 | int ibf_count; | ||
158 | /* FIXME: implement this without always allocating new IBFs */ | ||
159 | diff = ibf_dup (se1->strata[i]); | ||
160 | ibf_subtract (diff, se2->strata[i]); | ||
161 | for (ibf_count = 0; GNUNET_YES; ibf_count++) | ||
162 | { | ||
163 | int more; | ||
164 | |||
165 | more = ibf_decode (diff, NULL, NULL); | ||
166 | if (GNUNET_NO == more) | ||
167 | { | ||
168 | count += ibf_count; | ||
169 | break; | ||
170 | } | ||
171 | /* Estimate if decoding fails or would not terminate */ | ||
172 | if ((GNUNET_SYSERR == more) || (ibf_count > diff->size)) | ||
173 | { | ||
174 | ibf_destroy (diff); | ||
175 | return count * (1 << (i + 1)); | ||
176 | } | ||
177 | } | ||
178 | ibf_destroy (diff); | ||
179 | } | ||
180 | return count; | ||
181 | } | ||
182 | |||
183 | |||
184 | /** | ||
185 | * Make a copy of a strata estimator. | ||
186 | * | ||
187 | * @param se the strata estimator to copy | ||
188 | * @return the copy | ||
189 | */ | ||
190 | struct StrataEstimator * | ||
191 | strata_estimator_dup (struct StrataEstimator *se) | ||
192 | { | ||
193 | struct StrataEstimator *c; | ||
194 | int i; | ||
195 | |||
196 | c = GNUNET_new (struct StrataEstimator); | ||
197 | c->strata_count = se->strata_count; | ||
198 | c->ibf_size = se->ibf_size; | ||
199 | c->strata = GNUNET_malloc (sizeof (struct InvertibleBloomFilter *) * se->strata_count); | ||
200 | for (i = 0; i < se->strata_count; i++) | ||
201 | c->strata[i] = ibf_dup (se->strata[i]); | ||
202 | return c; | ||
203 | } | ||
204 | |||
205 | |||
206 | /** | ||
207 | * Destroy a strata estimator, free all of its resources. | ||
208 | * | ||
209 | * @param se strata estimator to destroy. | ||
210 | */ | ||
211 | void | ||
212 | strata_estimator_destroy (struct StrataEstimator *se) | ||
213 | { | ||
214 | int i; | ||
215 | |||
216 | for (i = 0; i < se->strata_count; i++) | ||
217 | ibf_destroy (se->strata[i]); | ||
218 | GNUNET_free (se->strata); | ||
219 | GNUNET_free (se); | ||
220 | } | ||
221 | |||