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 
58  key = ibf_key_from_hashcode(hash);
59  ibf_hashcode_from_key(key, &replicated);
61  key_to_hashcode,
62  &replicated,
63  GNUNET_memdup(hash, sizeof *hash),
65 }
66 
67 
68 static void
71  void *cls)
72 {
73  struct GNUNET_HashCode replicated;
74 
75  ibf_hashcode_from_key(key, &replicated);
77  &replicated,
78  iter,
79  cls);
80 }
81 
82 
83 static int
84 insert_iterator(void *cls, const struct GNUNET_HashCode *key, void *value)
85 {
86  struct InvertibleBloomFilter *ibf = cls;
87 
89  return GNUNET_YES;
90 }
91 
92 
93 static int
94 remove_iterator(void *cls, const struct GNUNET_HashCode *key, void *value)
95 {
96  struct GNUNET_CONTAINER_MultiHashMap *hashmap = cls;
97 
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 =
120  GNUNET_NO);
121  set_b =
123  GNUNET_NO);
124  set_c = GNUNET_CONTAINER_multihashmap_create(((csize == 0) ? 1 : csize),
125  GNUNET_NO);
126 
127  key_to_hashcode =
129  ? 1
130  : (asize + bsize + csize)),
131  GNUNET_NO);
132 
133  printf("hash-num=%u, size=%u, #(A-B)=%u, #(B-A)=%u, #(A&B)=%u\n",
134  hash_num,
135  ibf_size,
136  asize,
137  bsize,
138  csize);
139 
140  i = 0;
141  while (i < asize)
142  {
145  continue;
148  set_a,
149  &id,
150  NULL,
152  register_hashcode(&id);
153  i++;
154  }
155  i = 0;
156  while (i < bsize)
157  {
160  continue;
162  continue;
165  set_b,
166  &id,
167  NULL,
169  register_hashcode(&id);
170  i++;
171  }
172  i = 0;
173  while (i < csize)
174  {
177  continue;
179  continue;
181  continue;
184  set_c,
185  &id,
186  NULL,
188  register_hashcode(&id);
189  i++;
190  }
191 
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))
195  {
196  /* insufficient memory */
197  GNUNET_break(0);
199  return;
200  }
201 
202 
203  printf("generated sets\n");
204 
205  start_time = GNUNET_TIME_absolute_get();
206 
211 
212  delta_time = GNUNET_TIME_absolute_get_duration(start_time);
213 
214  printf("encoded in: %s\n",
216 
217  ibf_subtract(ibf_a, ibf_b);
218 
219 
220  start_time = GNUNET_TIME_absolute_get();
221 
222  for (i = 0; i <= asize + bsize; i++)
223  {
224  res = ibf_decode(ibf_a, &side, &ibf_key);
225  if (GNUNET_SYSERR == res)
226  {
227  printf("decode failed, %u/%u elements left\n",
230  asize + bsize);
231  return;
232  }
233  if (GNUNET_NO == res)
234  {
235  if ((0 == GNUNET_CONTAINER_multihashmap_size(set_b)) &&
237  {
238  delta_time = GNUNET_TIME_absolute_get_duration(start_time);
239  printf("decoded successfully in: %s\n",
241  }
242  else
243  {
244  printf("decode missed elements (should never happen)\n");
245  }
246  return;
247  }
248 
249  if (side == 1)
250  iter_hashcodes(ibf_key, remove_iterator, set_a);
251  if (side == -1)
252  iter_hashcodes(ibf_key, remove_iterator, set_b);
253  }
254  printf("cyclic IBF, %u/%u elements left\n",
257  asize + bsize);
258 }
259 
260 
261 int
262 main(int argc, char **argv)
263 {
264  struct GNUNET_GETOPT_CommandLineOption options[] = {
266  "asize",
267  NULL,
268  gettext_noop("number of element in set A-B"),
269  &asize),
270 
272  "bsize",
273  NULL,
274  gettext_noop("number of element in set B-A"),
275  &bsize),
276 
278  "csize",
279  NULL,
280  gettext_noop(
281  "number of common elements in A and B"),
282  &csize),
283 
285  "hash-num",
286  NULL,
287  gettext_noop("hash num"),
288  &hash_num),
289 
291  "ibf-size",
292  NULL,
293  gettext_noop("ibf size"),
294  &ibf_size),
295 
297  };
298 
299  GNUNET_PROGRAM_run2(argc,
300  argv,
301  "gnunet-consensus-ibf",
302  "help",
303  options,
304  &run,
305  NULL,
306  GNUNET_YES);
307  return 0;
308 }
int(* GNUNET_CONTAINER_MulitHashMapIteratorCallback)(void *cls, const struct GNUNET_HashCode *key, void *value)
Iterator over hash map entries.
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:140
static void iter_hashcodes(struct IBF_Key key, GNUNET_CONTAINER_MulitHashMapIteratorCallback iter, void *cls)
static enum GNUNET_CRYPTO_Quality random_quality
Invertible bloom filter (IBF).
Definition: ibf.h:79
static struct GNUNET_CONTAINER_MultiHashMap * key_to_hashcode
#define GNUNET_NO
Definition: gnunet_common.h:78
#define GNUNET_memdup(buf, size)
Allocate and initialize a block of memory.
#define GNUNET_OK
Named constants for return values.
Definition: gnunet_common.h:75
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:517
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:225
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:686
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:349
static unsigned int bsize
A 512-bit hashcode.
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:76
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
int GNUNET_CONTAINER_multihashmap_get_multiple(struct GNUNET_CONTAINER_MultiHashMap *map, const struct GNUNET_HashCode *key, GNUNET_CONTAINER_MulitHashMapIteratorCallback it, void *it_cls)
Iterate over all entries in the map that match a particular key.
configuration data
Definition: configuration.c:83
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
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:77
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
int GNUNET_CONTAINER_multihashmap_iterate(struct GNUNET_CONTAINER_MultiHashMap *map, GNUNET_CONTAINER_MulitHashMapIteratorCallback it, void *it_cls)
Iterate over all entries in the map.
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