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.
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;
57 key = ibf_key_from_hashcode (hash);
58 ibf_hashcode_from_key (key, &replicated);
59 GNUNET_CONTAINER_multihashmap_put (key_to_hashcode, &replicated, GNUNET_memdup (hash, sizeof *hash),
60 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
64 iter_hashcodes (struct IBF_Key key, GNUNET_CONTAINER_HashMapIterator iter, void *cls)
66 struct GNUNET_HashCode replicated;
67 ibf_hashcode_from_key (key, &replicated);
68 GNUNET_CONTAINER_multihashmap_get_multiple (key_to_hashcode, &replicated, iter, cls);
73 insert_iterator (void *cls,
74 const struct GNUNET_HashCode *key,
77 struct InvertibleBloomFilter *ibf = (struct InvertibleBloomFilter *) cls;
78 ibf_insert (ibf, ibf_key_from_hashcode (key));
84 remove_iterator (void *cls,
85 const struct GNUNET_HashCode *key,
88 struct GNUNET_CONTAINER_MultiHashMap *hashmap = cls;
89 /* if remove fails, there just was a collision with another key */
90 (void) GNUNET_CONTAINER_multihashmap_remove (hashmap, value, NULL);
96 run (void *cls, char *const *args, const char *cfgfile,
97 const struct GNUNET_CONFIGURATION_Handle *cfg)
99 struct GNUNET_HashCode id;
100 struct IBF_Key ibf_key;
104 struct GNUNET_TIME_Absolute start_time;
105 struct GNUNET_TIME_Relative delta_time;
107 set_a = GNUNET_CONTAINER_multihashmap_create (((asize == 0) ? 1 : (asize + csize)),
109 set_b = GNUNET_CONTAINER_multihashmap_create (((bsize == 0) ? 1 : (bsize + csize)),
111 set_c = GNUNET_CONTAINER_multihashmap_create (((csize == 0) ? 1 : csize),
114 key_to_hashcode = GNUNET_CONTAINER_multihashmap_create (((asize+bsize+csize == 0) ? 1 : (asize+bsize+csize)),
117 printf ("hash-num=%u, size=%u, #(A-B)=%u, #(B-A)=%u, #(A&B)=%u\n",
118 hash_num, ibf_size, asize, bsize, csize);
123 GNUNET_CRYPTO_hash_create_random (random_quality, &id);
124 if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains (set_a, &id))
126 GNUNET_CONTAINER_multihashmap_put (
127 set_a, &id, NULL, GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY);
128 register_hashcode (&id);
134 GNUNET_CRYPTO_hash_create_random (random_quality, &id);
135 if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains (set_a, &id))
137 if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains (set_b, &id))
139 GNUNET_CONTAINER_multihashmap_put (
140 set_b, &id, NULL, GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY);
141 register_hashcode (&id);
147 GNUNET_CRYPTO_hash_create_random (random_quality, &id);
148 if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains (set_a, &id))
150 if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains (set_b, &id))
152 if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains (set_c, &id))
154 GNUNET_CONTAINER_multihashmap_put (
155 set_c, &id, NULL, GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY);
156 register_hashcode (&id);
160 ibf_a = ibf_create (ibf_size, hash_num);
161 ibf_b = ibf_create (ibf_size, hash_num);
163 printf ("generated sets\n");
165 start_time = GNUNET_TIME_absolute_get ();
167 GNUNET_CONTAINER_multihashmap_iterate (set_a, &insert_iterator, ibf_a);
168 GNUNET_CONTAINER_multihashmap_iterate (set_b, &insert_iterator, ibf_b);
169 GNUNET_CONTAINER_multihashmap_iterate (set_c, &insert_iterator, ibf_a);
170 GNUNET_CONTAINER_multihashmap_iterate (set_c, &insert_iterator, ibf_b);
172 delta_time = GNUNET_TIME_absolute_get_duration (start_time);
174 printf ("encoded in: %s\n", GNUNET_STRINGS_relative_time_to_string (delta_time, GNUNET_NO));
176 ibf_subtract (ibf_a, ibf_b);
179 start_time = GNUNET_TIME_absolute_get ();
181 for (i = 0; i <= asize + bsize; i++)
183 res = ibf_decode (ibf_a, &side, &ibf_key);
184 if (GNUNET_SYSERR == res)
186 printf ("decode failed, %u/%u elements left\n",
187 GNUNET_CONTAINER_multihashmap_size (set_a) + GNUNET_CONTAINER_multihashmap_size (set_b),
191 if (GNUNET_NO == res)
193 if ((0 == GNUNET_CONTAINER_multihashmap_size (set_b)) &&
194 (0 == GNUNET_CONTAINER_multihashmap_size (set_a)))
196 delta_time = GNUNET_TIME_absolute_get_duration (start_time);
197 printf ("decoded successfully in: %s\n", GNUNET_STRINGS_relative_time_to_string (delta_time, GNUNET_NO));
201 printf ("decode missed elements (should never happen)\n");
207 iter_hashcodes (ibf_key, remove_iterator, set_a);
209 iter_hashcodes (ibf_key, remove_iterator, set_b);
211 printf("cyclic IBF, %u/%u elements left\n",
212 GNUNET_CONTAINER_multihashmap_size (set_a) + GNUNET_CONTAINER_multihashmap_size (set_b),
217 main (int argc, char **argv)
219 static const struct GNUNET_GETOPT_CommandLineOption options[] = {
221 gettext_noop ("number of element in set A-B"), 1,
222 &GNUNET_GETOPT_set_uint, &asize},
224 gettext_noop ("number of element in set B-A"), 1,
225 &GNUNET_GETOPT_set_uint, &bsize},
227 gettext_noop ("number of common elements in A and B"), 1,
228 &GNUNET_GETOPT_set_uint, &csize},
229 {'k', "hash-num", NULL,
230 gettext_noop ("hash num"), 1,
231 &GNUNET_GETOPT_set_uint, &hash_num},
232 {'s', "ibf-size", NULL,
233 gettext_noop ("ibf size"), 1,
234 &GNUNET_GETOPT_set_uint, &ibf_size},
235 GNUNET_GETOPT_OPTION_END
237 GNUNET_PROGRAM_run2 (argc, argv, "gnunet-consensus-ibf",
239 options, &run, NULL, GNUNET_YES);