GNUnet  0.11.x
ibf.h
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 
28 #ifndef GNUNET_CONSENSUS_IBF_H
29 #define GNUNET_CONSENSUS_IBF_H
30 
31 #include "platform.h"
32 #include "gnunet_util_lib.h"
33 
34 #ifdef __cplusplus
35 extern "C"
36 {
37 #if 0 /* keep Emacsens' auto-indent happy */
38 }
39 #endif
40 #endif
41 
42 
46 struct IBF_Key
47 {
48  uint64_t key_val;
49 };
50 
51 
55 struct IBF_KeyHash
56 {
57  uint32_t key_hash_val;
58 };
59 
60 
64 struct IBF_Count
65 {
66  int64_t count_val;
67 };
68 
69 
73 #define IBF_BUCKET_SIZE (sizeof(struct IBF_Count) + sizeof(struct IBF_Key) \
74  + sizeof(struct IBF_KeyHash))
75 
76 
84 {
88  uint32_t size;
89 
94  uint8_t hash_num;
95 
102 
109 
114  struct IBF_Key *key_sum;
115 
120  struct IBF_KeyHash *key_hash_sum;
121 
127  struct IBF_Count *count;
128 };
129 
130 
140 void
141 ibf_write_slice (const struct InvertibleBloomFilter *ibf,
142  uint32_t start,
143  uint64_t count,
144  void *buf,
145  uint8_t counter_max_length);
146 
147 
156 void
157 ibf_read_slice (const void *buf,
158  uint32_t start,
159  uint64_t count,
160  struct InvertibleBloomFilter *ibf,
161  uint8_t counter_max_length);
162 
163 
170 struct IBF_Key
171 ibf_key_from_hashcode (const struct GNUNET_HashCode *hash);
172 
173 
181 void
182 ibf_hashcode_from_key (struct IBF_Key key, struct GNUNET_HashCode *dst);
183 
184 
192 struct InvertibleBloomFilter *
193 ibf_create (uint32_t size, uint8_t hash_num);
194 
195 
202 void
203 ibf_insert (struct InvertibleBloomFilter *ibf, struct IBF_Key key);
204 
205 
212 void
213 ibf_remove (struct InvertibleBloomFilter *ibf, struct IBF_Key key);
214 
215 
223 void
224 ibf_subtract (struct InvertibleBloomFilter *ibf1,
225  const struct InvertibleBloomFilter *ibf2);
226 
227 
240 int
241 ibf_decode (struct InvertibleBloomFilter *ibf,
242  int *ret_side,
243  struct IBF_Key *ret_id);
244 
245 
251 struct InvertibleBloomFilter *
252 ibf_dup (const struct InvertibleBloomFilter *ibf);
253 
254 
261 void
262 ibf_destroy (struct InvertibleBloomFilter *ibf);
263 
264 uint8_t
266 
267 
278 void
279 pack_counter (const struct InvertibleBloomFilter *ibf,
280  uint32_t start,
281  uint64_t count,
282  uint8_t *buf,
283  uint8_t counter_max_length);
284 
295 void
296 unpack_counter (const struct InvertibleBloomFilter *ibf,
297  uint32_t start,
298  uint64_t count,
299  uint8_t *buf,
300  uint8_t counter_max_length);
301 
302 
303 #if 0 /* keep Emacsens' auto-indent happy */
304 {
305 #endif
306 #ifdef __cplusplus
307 }
308 #endif
309 
310 #endif
static int start
Set if we are to start default services (including ARM).
Definition: gnunet-arm.c:39
struct GNUNET_HashCode key
The key used in the DHT.
static char buf[2048]
static unsigned int hash_num
static unsigned int size
Size of the "table".
Definition: peer.c:67
void ibf_subtract(struct InvertibleBloomFilter *ibf1, const struct InvertibleBloomFilter *ibf2)
Subtract ibf2 from ibf1, storing the result in ibf1.
Definition: ibf.c:356
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:228
void ibf_read_slice(const void *buf, uint32_t start, uint32_t count, struct InvertibleBloomFilter *ibf)
Read buckets from a buffer into an ibf.
Definition: ibf.c:323
struct IBF_Key ibf_key_from_hashcode(const struct GNUNET_HashCode *hash)
Create a key from a hashcode.
Definition: ibf.c:43
void ibf_write_slice(const struct InvertibleBloomFilter *ibf, uint32_t start, uint32_t count, void *buf)
Write buckets from an ibf to a buffer.
Definition: ibf.c:290
struct InvertibleBloomFilter * ibf_create(uint32_t size, uint8_t hash_num)
Create an invertible bloom filter.
Definition: ibf.c:79
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:57
void ibf_insert(struct InvertibleBloomFilter *ibf, struct IBF_Key key)
Insert a key into an IBF.
Definition: ibf.c:167
struct InvertibleBloomFilter * ibf_dup(const struct InvertibleBloomFilter *ibf)
Create a copy of an IBF, the copy has to be destroyed properly.
Definition: ibf.c:379
void ibf_remove(struct InvertibleBloomFilter *ibf, struct IBF_Key key)
Remove a key from an IBF.
Definition: ibf.c:184
void ibf_destroy(struct InvertibleBloomFilter *ibf)
Destroy all resources associated with the invertible bloom filter.
Definition: ibf.c:403
uint8_t ibf_get_max_counter(struct InvertibleBloomFilter *ibf)
Returns the minimal bytes needed to store the counter of the IBF.
Definition: ibf.c:298
void unpack_counter(const struct InvertibleBloomFilter *ibf, uint32_t start, uint64_t count, uint8_t *buf, uint8_t counter_max_length)
Unpacks the counter to transmit only the smallest possible amount of bytes and preventing overflow of...
Definition: ibf.c:442
void pack_counter(const struct InvertibleBloomFilter *ibf, uint32_t start, uint64_t count, uint8_t *buf, uint8_t counter_max_length)
Packs the counter to transmit only the smallest possible amount of bytes and preventing overflow of t...
Definition: ibf.c:369
A 512-bit hashcode.
Type of the count field of IBF buckets.
Definition: ibf.h:64
int64_t count_val
Definition: ibf.h:66
Hash of an IBF key.
Definition: ibf.h:55
uint32_t key_hash_val
Definition: ibf.h:56
Keys that can be inserted into and removed from an IBF.
Definition: ibf.h:46
uint64_t key_val
Definition: ibf.h:47
Invertible bloom filter (IBF).
Definition: ibf.h:83
int remote_decoded_count
If an IBF is decoded this count stores how many elements are on the remote site.
Definition: ibf.h:108
int local_decoded_count
If an IBF is decoded this count stores how many elements are on the local site.
Definition: ibf.h:101
struct IBF_KeyHash * key_hash_sum
Xor sums of the hashes of the keys of inserted elements.
Definition: ibf.h:105
uint32_t size
How many cells does this IBF have?
Definition: ibf.h:87
struct IBF_Count * count
How many times has a bucket been hit? Can be negative, as a result of IBF subtraction.
Definition: ibf.h:112
struct IBF_Key * key_sum
Xor sums of the elements' keys, used to identify the elements.
Definition: ibf.h:99
uint8_t hash_num
In how many cells do we hash one element? Usually 4 or 3.
Definition: ibf.h:93