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.
17 * @file set/gnunet-set-ibf-profiler.c
18 * @brief tool for profiling the invertible bloom filter implementation
19 * @author Florian Dold
23 #include "gnunet_util_lib.h"
27 static unsigned int asize = 10;
28 static unsigned int bsize = 10;
29 static unsigned int csize = 10;
30 static unsigned int hash_num = 4;
31 static unsigned int ibf_size = 80;
33 /* FIXME: add parameter for this */
34 static enum GNUNET_CRYPTO_Quality random_quality = GNUNET_CRYPTO_QUALITY_WEAK;
36 static struct GNUNET_CONTAINER_MultiHashMap *set_a;
37 static struct GNUNET_CONTAINER_MultiHashMap *set_b;
38 /* common elements in a and b */
39 static struct GNUNET_CONTAINER_MultiHashMap *set_c;
41 static struct GNUNET_CONTAINER_MultiHashMap *key_to_hashcode;
43 static struct InvertibleBloomFilter *ibf_a;
44 static struct InvertibleBloomFilter *ibf_b;
48 register_hashcode (struct GNUNET_HashCode *hash)
50 struct GNUNET_HashCode replicated;
52 key = ibf_key_from_hashcode (hash);
53 ibf_hashcode_from_key (key, &replicated);
54 (void) GNUNET_CONTAINER_multihashmap_put (key_to_hashcode,
56 GNUNET_memdup (hash, sizeof *hash),
57 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
62 iter_hashcodes (struct IBF_Key key,
63 GNUNET_CONTAINER_HashMapIterator iter,
66 struct GNUNET_HashCode replicated;
68 ibf_hashcode_from_key (key, &replicated);
69 GNUNET_CONTAINER_multihashmap_get_multiple (key_to_hashcode,
76 insert_iterator (void *cls,
77 const struct GNUNET_HashCode *key,
80 struct InvertibleBloomFilter *ibf = cls;
82 ibf_insert (ibf, ibf_key_from_hashcode (key));
88 remove_iterator (void *cls,
89 const struct GNUNET_HashCode *key,
92 struct GNUNET_CONTAINER_MultiHashMap *hashmap = cls;
93 /* if remove fails, there just was a collision with another key */
94 (void) GNUNET_CONTAINER_multihashmap_remove (hashmap, value, NULL);
103 const struct GNUNET_CONFIGURATION_Handle *cfg)
105 struct GNUNET_HashCode id;
106 struct IBF_Key ibf_key;
110 struct GNUNET_TIME_Absolute start_time;
111 struct GNUNET_TIME_Relative delta_time;
113 set_a = GNUNET_CONTAINER_multihashmap_create (((asize == 0) ? 1 : (asize + csize)),
115 set_b = GNUNET_CONTAINER_multihashmap_create (((bsize == 0) ? 1 : (bsize + csize)),
117 set_c = GNUNET_CONTAINER_multihashmap_create (((csize == 0) ? 1 : csize),
120 key_to_hashcode = GNUNET_CONTAINER_multihashmap_create (((asize+bsize+csize == 0) ? 1 : (asize+bsize+csize)),
123 printf ("hash-num=%u, size=%u, #(A-B)=%u, #(B-A)=%u, #(A&B)=%u\n",
124 hash_num, ibf_size, asize, bsize, csize);
129 GNUNET_CRYPTO_hash_create_random (random_quality, &id);
130 if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains (set_a, &id))
132 GNUNET_break (GNUNET_OK ==
133 GNUNET_CONTAINER_multihashmap_put (set_a, &id, NULL,
134 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
135 register_hashcode (&id);
141 GNUNET_CRYPTO_hash_create_random (random_quality, &id);
142 if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains (set_a, &id))
144 if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains (set_b, &id))
146 GNUNET_break (GNUNET_OK ==
147 GNUNET_CONTAINER_multihashmap_put (set_b, &id, NULL,
148 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
149 register_hashcode (&id);
155 GNUNET_CRYPTO_hash_create_random (random_quality, &id);
156 if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains (set_a, &id))
158 if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains (set_b, &id))
160 if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains (set_c, &id))
162 GNUNET_break (GNUNET_OK ==
163 GNUNET_CONTAINER_multihashmap_put (set_c, &id, NULL,
164 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
165 register_hashcode (&id);
169 ibf_a = ibf_create (ibf_size, hash_num);
170 ibf_b = ibf_create (ibf_size, hash_num);
171 if ( (NULL == ibf_a) ||
174 /* insufficient memory */
176 GNUNET_SCHEDULER_shutdown ();
181 printf ("generated sets\n");
183 start_time = GNUNET_TIME_absolute_get ();
185 GNUNET_CONTAINER_multihashmap_iterate (set_a, &insert_iterator, ibf_a);
186 GNUNET_CONTAINER_multihashmap_iterate (set_b, &insert_iterator, ibf_b);
187 GNUNET_CONTAINER_multihashmap_iterate (set_c, &insert_iterator, ibf_a);
188 GNUNET_CONTAINER_multihashmap_iterate (set_c, &insert_iterator, ibf_b);
190 delta_time = GNUNET_TIME_absolute_get_duration (start_time);
192 printf ("encoded in: %s\n",
193 GNUNET_STRINGS_relative_time_to_string (delta_time,
196 ibf_subtract (ibf_a, ibf_b);
199 start_time = GNUNET_TIME_absolute_get ();
201 for (i = 0; i <= asize + bsize; i++)
203 res = ibf_decode (ibf_a, &side, &ibf_key);
204 if (GNUNET_SYSERR == res)
206 printf ("decode failed, %u/%u elements left\n",
207 GNUNET_CONTAINER_multihashmap_size (set_a) + GNUNET_CONTAINER_multihashmap_size (set_b),
211 if (GNUNET_NO == res)
213 if ((0 == GNUNET_CONTAINER_multihashmap_size (set_b)) &&
214 (0 == GNUNET_CONTAINER_multihashmap_size (set_a)))
216 delta_time = GNUNET_TIME_absolute_get_duration (start_time);
217 printf ("decoded successfully in: %s\n",
218 GNUNET_STRINGS_relative_time_to_string (delta_time,
223 printf ("decode missed elements (should never happen)\n");
229 iter_hashcodes (ibf_key, remove_iterator, set_a);
231 iter_hashcodes (ibf_key, remove_iterator, set_b);
233 printf("cyclic IBF, %u/%u elements left\n",
234 GNUNET_CONTAINER_multihashmap_size (set_a) + GNUNET_CONTAINER_multihashmap_size (set_b),
240 main (int argc, char **argv)
242 struct GNUNET_GETOPT_CommandLineOption options[] = {
244 GNUNET_GETOPT_option_uint ('A',
247 gettext_noop ("number of element in set A-B"),
250 GNUNET_GETOPT_option_uint ('B',
253 gettext_noop ("number of element in set B-A"),
256 GNUNET_GETOPT_option_uint ('C',
259 gettext_noop ("number of common elements in A and B"),
262 GNUNET_GETOPT_option_uint ('k',
265 gettext_noop ("hash num"),
268 GNUNET_GETOPT_option_uint ('s',
271 gettext_noop ("ibf size"),
274 GNUNET_GETOPT_OPTION_END
277 GNUNET_PROGRAM_run2 (argc, argv, "gnunet-consensus-ibf",
279 options, &run, NULL, GNUNET_YES);