GNUnet  0.10.x
gnunet-set-ibf-profiler.c
Go to the documentation of this file.
1 /*
2  This file is part of GNUnet.
3  Copyright (C) 2012 GNUnet e.V.
4 
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.
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  Affero General Public License for more details.
14 
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/>.
17 
18  SPDX-License-Identifier: AGPL3.0-or-later
19 */
20 
27 #include "platform.h"
28 #include "gnunet_util_lib.h"
29 
30 #include "ibf.h"
31 
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;
37 
38 /* FIXME: add parameter for this */
40 
43 /* common elements in a and b */
45 
47 
50 
51 
52 static void
54 {
55  struct GNUNET_HashCode replicated;
56  struct IBF_Key key;
57  key = ibf_key_from_hashcode (hash);
58  ibf_hashcode_from_key (key, &replicated);
59  (void) GNUNET_CONTAINER_multihashmap_put (key_to_hashcode,
60  &replicated,
61  GNUNET_memdup (hash, sizeof *hash),
63 }
64 
65 
66 static void
69  void *cls)
70 {
71  struct GNUNET_HashCode replicated;
72 
73  ibf_hashcode_from_key (key, &replicated);
75  &replicated,
76  iter, cls);
77 }
78 
79 
80 static int
81 insert_iterator (void *cls,
82  const struct GNUNET_HashCode *key,
83  void *value)
84 {
85  struct InvertibleBloomFilter *ibf = cls;
86 
87  ibf_insert (ibf, ibf_key_from_hashcode (key));
88  return GNUNET_YES;
89 }
90 
91 
92 static int
93 remove_iterator (void *cls,
94  const struct GNUNET_HashCode *key,
95  void *value)
96 {
97  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);
100  return GNUNET_YES;
101 }
102 
103 
104 static void
105 run (void *cls,
106  char *const *args,
107  const char *cfgfile,
108  const struct GNUNET_CONFIGURATION_Handle *cfg)
109 {
110  struct GNUNET_HashCode id;
111  struct IBF_Key ibf_key;
112  int i;
113  int side;
114  int res;
115  struct GNUNET_TIME_Absolute start_time;
116  struct GNUNET_TIME_Relative delta_time;
117 
118  set_a = GNUNET_CONTAINER_multihashmap_create (((asize == 0) ? 1 : (asize + csize)),
119  GNUNET_NO);
120  set_b = GNUNET_CONTAINER_multihashmap_create (((bsize == 0) ? 1 : (bsize + csize)),
121  GNUNET_NO);
122  set_c = GNUNET_CONTAINER_multihashmap_create (((csize == 0) ? 1 : csize),
123  GNUNET_NO);
124 
125  key_to_hashcode = GNUNET_CONTAINER_multihashmap_create (((asize+bsize+csize == 0) ? 1 : (asize+bsize+csize)),
126  GNUNET_NO);
127 
128  printf ("hash-num=%u, size=%u, #(A-B)=%u, #(B-A)=%u, #(A&B)=%u\n",
130 
131  i = 0;
132  while (i < asize)
133  {
136  continue;
138  GNUNET_CONTAINER_multihashmap_put (set_a, &id, NULL,
140  register_hashcode (&id);
141  i++;
142  }
143  i = 0;
144  while (i < bsize)
145  {
148  continue;
150  continue;
152  GNUNET_CONTAINER_multihashmap_put (set_b, &id, NULL,
154  register_hashcode (&id);
155  i++;
156  }
157  i = 0;
158  while (i < csize)
159  {
162  continue;
164  continue;
166  continue;
168  GNUNET_CONTAINER_multihashmap_put (set_c, &id, NULL,
170  register_hashcode (&id);
171  i++;
172  }
173 
174  ibf_a = ibf_create (ibf_size, hash_num);
175  ibf_b = ibf_create (ibf_size, hash_num);
176  if ( (NULL == ibf_a) ||
177  (NULL == ibf_b) )
178  {
179  /* insufficient memory */
180  GNUNET_break (0);
182  return;
183  }
184 
185 
186  printf ("generated sets\n");
187 
188  start_time = GNUNET_TIME_absolute_get ();
189 
194 
195  delta_time = GNUNET_TIME_absolute_get_duration (start_time);
196 
197  printf ("encoded in: %s\n",
199  GNUNET_NO));
200 
201  ibf_subtract (ibf_a, ibf_b);
202 
203 
204  start_time = GNUNET_TIME_absolute_get ();
205 
206  for (i = 0; i <= asize + bsize; i++)
207  {
208  res = ibf_decode (ibf_a, &side, &ibf_key);
209  if (GNUNET_SYSERR == res)
210  {
211  printf ("decode failed, %u/%u elements left\n",
213  asize + bsize);
214  return;
215  }
216  if (GNUNET_NO == res)
217  {
218  if ((0 == GNUNET_CONTAINER_multihashmap_size (set_b)) &&
219  (0 == GNUNET_CONTAINER_multihashmap_size (set_a)))
220  {
221  delta_time = GNUNET_TIME_absolute_get_duration (start_time);
222  printf ("decoded successfully in: %s\n",
224  GNUNET_NO));
225  }
226  else
227  {
228  printf ("decode missed elements (should never happen)\n");
229  }
230  return;
231  }
232 
233  if (side == 1)
234  iter_hashcodes (ibf_key, remove_iterator, set_a);
235  if (side == -1)
236  iter_hashcodes (ibf_key, remove_iterator, set_b);
237  }
238  printf("cyclic IBF, %u/%u elements left\n",
240  asize + bsize);
241 }
242 
243 
244 int
245 main (int argc, char **argv)
246 {
247  struct GNUNET_GETOPT_CommandLineOption options[] = {
248 
250  "asize",
251  NULL,
252  gettext_noop ("number of element in set A-B"),
253  &asize),
254 
256  "bsize",
257  NULL,
258  gettext_noop ("number of element in set B-A"),
259  &bsize),
260 
262  "csize",
263  NULL,
264  gettext_noop ("number of common elements in A and B"),
265  &csize),
266 
268  "hash-num",
269  NULL,
270  gettext_noop ("hash num"),
271  &hash_num),
272 
274  "ibf-size",
275  NULL,
276  gettext_noop ("ibf size"),
277  &ibf_size),
278 
280  };
281 
282  GNUNET_PROGRAM_run2 (argc, argv, "gnunet-consensus-ibf",
283  "help",
284  options, &run, NULL, GNUNET_YES);
285  return 0;
286 }
static struct GNUNET_CONTAINER_MultiHashMap * set_b
unsigned int GNUNET_CONTAINER_multihashmap_size(const struct GNUNET_CONTAINER_MultiHashMap *map)
Get the number of key-value pairs in the map.
int GNUNET_PROGRAM_run2(int argc, char *const *argv, const char *binaryName, const char *binaryHelp, const struct GNUNET_GETOPT_CommandLineOption *options, GNUNET_PROGRAM_Main task, void *task_cls, int run_without_scheduler)
Run a standard GNUnet command startup sequence (initialize loggers and configuration, parse options).
Definition: program.c:141
static enum GNUNET_CRYPTO_Quality random_quality
Invertible bloom filter (IBF).
Definition: ibf.h:82
static struct GNUNET_CONTAINER_MultiHashMap * key_to_hashcode
int(* GNUNET_CONTAINER_HashMapIterator)(void *cls, const struct GNUNET_HashCode *key, void *value)
Iterator over hash map entries.
int GNUNET_CONTAINER_multihashmap_iterate(struct GNUNET_CONTAINER_MultiHashMap *map, GNUNET_CONTAINER_HashMapIterator it, void *it_cls)
Iterate over all entries in the map.
#define GNUNET_NO
Definition: gnunet_common.h:81
#define GNUNET_memdup(buf, size)
Allocate and initialize a block of memory.
#define GNUNET_OK
Named constants for return values.
Definition: gnunet_common.h:78
GNUNET_CRYPTO_Quality
Desired quality level for random numbers.
Definition of a command line option.
int GNUNET_CONTAINER_multihashmap_contains(const struct GNUNET_CONTAINER_MultiHashMap *map, const struct GNUNET_HashCode *key)
Check if the map contains any value under the given key (including values that are NULL)...
void GNUNET_SCHEDULER_shutdown(void)
Request the shutdown of a scheduler.
Definition: scheduler.c:524
static void run(void *cls, char *const *args, const char *cfgfile, const struct GNUNET_CONFIGURATION_Handle *cfg)
Internal representation of the hash map.
#define GNUNET_break(cond)
Use this for internal assertion violations that are not fatal (can be handled) but should not occur...
struct GNUNET_GETOPT_CommandLineOption GNUNET_GETOPT_OPTION_END
Definition: 002.c:13
static unsigned int ibf_size
static struct InvertibleBloomFilter * ibf_a
static unsigned int csize
void GNUNET_CRYPTO_hash_create_random(enum GNUNET_CRYPTO_Quality mode, struct GNUNET_HashCode *result)
Create a random hash code.
Definition: crypto_hash.c:138
static char * value
Value of the record to add/remove.
static int remove_iterator(void *cls, const struct GNUNET_HashCode *key, void *value)
int ibf_decode(struct InvertibleBloomFilter *ibf, int *ret_side, struct IBF_Key *ret_id)
Decode and remove an element from the IBF, if possible.
Definition: ibf.c:222
void ibf_hashcode_from_key(struct IBF_Key key, struct GNUNET_HashCode *dst)
Create a hashcode from a key, by replicating the key until the hascode is filled. ...
Definition: ibf.c:55
const char * GNUNET_STRINGS_relative_time_to_string(struct GNUNET_TIME_Relative delta, int do_round)
Give relative time in human-readable fancy format.
Definition: strings.c:727
static int insert_iterator(void *cls, const struct GNUNET_HashCode *key, void *value)
static unsigned int asize
static struct GNUNET_CONTAINER_MultiHashMap * set_c
int GNUNET_CONTAINER_multihashmap_remove(struct GNUNET_CONTAINER_MultiHashMap *map, const struct GNUNET_HashCode *key, const void *value)
Remove the given key-value pair from the map.
static void register_hashcode(struct GNUNET_HashCode *hash)
void ibf_subtract(struct InvertibleBloomFilter *ibf1, const struct InvertibleBloomFilter *ibf2)
Subtract ibf2 from ibf1, storing the result in ibf1.
Definition: ibf.c:346
static unsigned int bsize
A 512-bit hashcode.
static void iter_hashcodes(struct IBF_Key key, GNUNET_CONTAINER_HashMapIterator iter, void *cls)
static int res
struct GNUNET_TIME_Absolute GNUNET_TIME_absolute_get(void)
Get the current time.
Definition: time.c:118
static struct GNUNET_CONFIGURATION_Handle * cfg
Our configuration.
Definition: gnunet-arm.c:104
There must only be one value per key; storing a value should fail if a value under the same key alrea...
struct GNUNET_HashCode key
The key used in the DHT.
#define GNUNET_SYSERR
Definition: gnunet_common.h:79
invertible bloom filter
int main(int argc, char **argv)
static unsigned int hash_num
struct InvertibleBloomFilter * ibf_create(uint32_t size, uint8_t hash_num)
Create an invertible bloom filter.
Definition: ibf.c:76
int GNUNET_CONTAINER_multihashmap_put(struct GNUNET_CONTAINER_MultiHashMap *map, const struct GNUNET_HashCode *key, void *value, enum GNUNET_CONTAINER_MultiHashMapOption opt)
Store a key-value pair in the map.
Allow multiple values with the same key.
void ibf_insert(struct InvertibleBloomFilter *ibf, struct IBF_Key key)
Insert a key into an IBF.
Definition: ibf.c:164
configuration data
Definition: configuration.c:85
struct GNUNET_TIME_Relative GNUNET_TIME_absolute_get_duration(struct GNUNET_TIME_Absolute whence)
Get the duration of an operation as the difference of the current time and the given start time "henc...
Definition: time.c:373
int GNUNET_CONTAINER_multihashmap_get_multiple(struct GNUNET_CONTAINER_MultiHashMap *map, const struct GNUNET_HashCode *key, GNUNET_CONTAINER_HashMapIterator it, void *it_cls)
Iterate over all entries in the map that match a particular key.
struct GNUNET_CONTAINER_MultiHashMap * GNUNET_CONTAINER_multihashmap_create(unsigned int len, int do_not_copy_keys)
Create a multi hash map.
Time for absolute times used by GNUnet, in microseconds.
#define GNUNET_YES
Definition: gnunet_common.h:80
struct GNUNET_GETOPT_CommandLineOption GNUNET_GETOPT_option_uint(char shortName, const char *name, const char *argumentHelp, const char *description, unsigned int *val)
Allow user to specify an unsigned int.
struct IBF_Key ibf_key_from_hashcode(const struct GNUNET_HashCode *hash)
Create a key from a hashcode.
Definition: ibf.c:42
static struct GNUNET_CONTAINER_MultiHashMap * set_a
Keys that can be inserted into and removed from an IBF.
Definition: ibf.h:45
static struct InvertibleBloomFilter * ibf_b
No good quality of the operation is needed (i.e., random numbers can be pseudo-random).
Time for relative time used by GNUnet, in microseconds.
#define gettext_noop(String)
Definition: gettext.h:69