2 This file is part of GNUnet.
3 Copyright (C) 2012 GNUnet e.V.
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.
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.
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/>.
18 SPDX-License-Identifier: AGPL3.0-or-later
22 * @file set/gnunet-set-ibf-profiler.c
23 * @brief tool for profiling the invertible bloom filter implementation
24 * @author Florian Dold
28 #include "gnunet_util_lib.h"
32 static unsigned int asize = 10;
33 static unsigned int bsize = 10;
34 static unsigned int csize = 10;
35 static unsigned int hash_num = 4;
36 static unsigned int ibf_size = 80;
38 /* FIXME: add parameter for this */
39 static enum GNUNET_CRYPTO_Quality random_quality = GNUNET_CRYPTO_QUALITY_WEAK;
41 static struct GNUNET_CONTAINER_MultiHashMap *set_a;
42 static struct GNUNET_CONTAINER_MultiHashMap *set_b;
43 /* common elements in a and b */
44 static struct GNUNET_CONTAINER_MultiHashMap *set_c;
46 static struct GNUNET_CONTAINER_MultiHashMap *key_to_hashcode;
48 static struct InvertibleBloomFilter *ibf_a;
49 static struct InvertibleBloomFilter *ibf_b;
53 register_hashcode(struct GNUNET_HashCode *hash)
55 struct GNUNET_HashCode replicated;
58 key = ibf_key_from_hashcode(hash);
59 ibf_hashcode_from_key(key, &replicated);
60 (void)GNUNET_CONTAINER_multihashmap_put(
63 GNUNET_memdup(hash, sizeof *hash),
64 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
69 iter_hashcodes(struct IBF_Key key,
70 GNUNET_CONTAINER_MulitHashMapIteratorCallback iter,
73 struct GNUNET_HashCode replicated;
75 ibf_hashcode_from_key(key, &replicated);
76 GNUNET_CONTAINER_multihashmap_get_multiple(key_to_hashcode,
84 insert_iterator(void *cls, const struct GNUNET_HashCode *key, void *value)
86 struct InvertibleBloomFilter *ibf = cls;
88 ibf_insert(ibf, ibf_key_from_hashcode(key));
94 remove_iterator(void *cls, const struct GNUNET_HashCode *key, void *value)
96 struct GNUNET_CONTAINER_MultiHashMap *hashmap = cls;
98 /* if remove fails, there just was a collision with another key */
99 (void)GNUNET_CONTAINER_multihashmap_remove(hashmap, value, NULL);
108 const struct GNUNET_CONFIGURATION_Handle *cfg)
110 struct GNUNET_HashCode id;
111 struct IBF_Key ibf_key;
115 struct GNUNET_TIME_Absolute start_time;
116 struct GNUNET_TIME_Relative delta_time;
119 GNUNET_CONTAINER_multihashmap_create(((asize == 0) ? 1 : (asize + csize)),
122 GNUNET_CONTAINER_multihashmap_create(((bsize == 0) ? 1 : (bsize + csize)),
124 set_c = GNUNET_CONTAINER_multihashmap_create(((csize == 0) ? 1 : csize),
128 GNUNET_CONTAINER_multihashmap_create(((asize + bsize + csize == 0)
130 : (asize + bsize + csize)),
133 printf("hash-num=%u, size=%u, #(A-B)=%u, #(B-A)=%u, #(A&B)=%u\n",
143 GNUNET_CRYPTO_hash_create_random(random_quality, &id);
144 if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains(set_a, &id))
146 GNUNET_break(GNUNET_OK ==
147 GNUNET_CONTAINER_multihashmap_put(
151 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
152 register_hashcode(&id);
158 GNUNET_CRYPTO_hash_create_random(random_quality, &id);
159 if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains(set_a, &id))
161 if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains(set_b, &id))
163 GNUNET_break(GNUNET_OK ==
164 GNUNET_CONTAINER_multihashmap_put(
168 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
169 register_hashcode(&id);
175 GNUNET_CRYPTO_hash_create_random(random_quality, &id);
176 if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains(set_a, &id))
178 if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains(set_b, &id))
180 if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains(set_c, &id))
182 GNUNET_break(GNUNET_OK ==
183 GNUNET_CONTAINER_multihashmap_put(
187 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
188 register_hashcode(&id);
192 ibf_a = ibf_create(ibf_size, hash_num);
193 ibf_b = ibf_create(ibf_size, hash_num);
194 if ((NULL == ibf_a) || (NULL == ibf_b))
196 /* insufficient memory */
198 GNUNET_SCHEDULER_shutdown();
203 printf("generated sets\n");
205 start_time = GNUNET_TIME_absolute_get();
207 GNUNET_CONTAINER_multihashmap_iterate(set_a, &insert_iterator, ibf_a);
208 GNUNET_CONTAINER_multihashmap_iterate(set_b, &insert_iterator, ibf_b);
209 GNUNET_CONTAINER_multihashmap_iterate(set_c, &insert_iterator, ibf_a);
210 GNUNET_CONTAINER_multihashmap_iterate(set_c, &insert_iterator, ibf_b);
212 delta_time = GNUNET_TIME_absolute_get_duration(start_time);
214 printf("encoded in: %s\n",
215 GNUNET_STRINGS_relative_time_to_string(delta_time, GNUNET_NO));
217 ibf_subtract(ibf_a, ibf_b);
220 start_time = GNUNET_TIME_absolute_get();
222 for (i = 0; i <= asize + bsize; i++)
224 res = ibf_decode(ibf_a, &side, &ibf_key);
225 if (GNUNET_SYSERR == res)
227 printf("decode failed, %u/%u elements left\n",
228 GNUNET_CONTAINER_multihashmap_size(set_a) +
229 GNUNET_CONTAINER_multihashmap_size(set_b),
233 if (GNUNET_NO == res)
235 if ((0 == GNUNET_CONTAINER_multihashmap_size(set_b)) &&
236 (0 == GNUNET_CONTAINER_multihashmap_size(set_a)))
238 delta_time = GNUNET_TIME_absolute_get_duration(start_time);
239 printf("decoded successfully in: %s\n",
240 GNUNET_STRINGS_relative_time_to_string(delta_time, GNUNET_NO));
244 printf("decode missed elements (should never happen)\n");
250 iter_hashcodes(ibf_key, remove_iterator, set_a);
252 iter_hashcodes(ibf_key, remove_iterator, set_b);
254 printf("cyclic IBF, %u/%u elements left\n",
255 GNUNET_CONTAINER_multihashmap_size(set_a) +
256 GNUNET_CONTAINER_multihashmap_size(set_b),
262 main(int argc, char **argv)
264 struct GNUNET_GETOPT_CommandLineOption options[] = {
265 GNUNET_GETOPT_option_uint('A',
268 gettext_noop("number of element in set A-B"),
271 GNUNET_GETOPT_option_uint('B',
274 gettext_noop("number of element in set B-A"),
277 GNUNET_GETOPT_option_uint('C',
281 "number of common elements in A and B"),
284 GNUNET_GETOPT_option_uint('k',
287 gettext_noop("hash num"),
290 GNUNET_GETOPT_option_uint('s',
293 gettext_noop("ibf size"),
296 GNUNET_GETOPT_OPTION_END
299 GNUNET_PROGRAM_run2(argc,
301 "gnunet-consensus-ibf",