GNUnet  0.10.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 
27 #ifndef GNUNET_CONSENSUS_IBF_H
28 #define GNUNET_CONSENSUS_IBF_H
29 
30 #include "platform.h"
31 #include "gnunet_util_lib.h"
32 
33 #ifdef __cplusplus
34 extern "C"
35 {
36 #if 0 /* keep Emacsens' auto-indent happy */
37 }
38 #endif
39 #endif
40 
41 
45 struct IBF_Key
46 {
47  uint64_t key_val;
48 };
49 
50 
55 {
56  uint32_t key_hash_val;
57 };
58 
59 
63 struct IBF_Count
64 {
65  int8_t count_val;
66 };
67 
68 
72 #define IBF_BUCKET_SIZE (sizeof (struct IBF_Count) + sizeof (struct IBF_Key) + \
73  sizeof (struct IBF_KeyHash))
74 
75 
83 {
87  uint32_t size;
88 
93  uint8_t hash_num;
94 
99  struct IBF_Key *key_sum;
100 
106 
112  struct IBF_Count *count;
113 };
114 
115 
125 void
126 ibf_write_slice (const struct InvertibleBloomFilter *ibf,
127  uint32_t start,
128  uint32_t count,
129  void *buf);
130 
131 
140 void
141 ibf_read_slice (const void *buf,
142  uint32_t start,
143  uint32_t count,
144  struct InvertibleBloomFilter *ibf);
145 
146 
153 struct IBF_Key
154 ibf_key_from_hashcode (const struct GNUNET_HashCode *hash);
155 
156 
164 void
165 ibf_hashcode_from_key (struct IBF_Key key, struct GNUNET_HashCode *dst);
166 
167 
175 struct InvertibleBloomFilter *
176 ibf_create (uint32_t size, uint8_t hash_num);
177 
178 
185 void
186 ibf_insert (struct InvertibleBloomFilter *ibf, struct IBF_Key key);
187 
188 
195 void
196 ibf_remove (struct InvertibleBloomFilter *ibf, struct IBF_Key key);
197 
198 
206 void
207 ibf_subtract (struct InvertibleBloomFilter *ibf1,
208  const struct InvertibleBloomFilter *ibf2);
209 
210 
223 int
224 ibf_decode (struct InvertibleBloomFilter *ibf,
225  int *ret_side,
226  struct IBF_Key *ret_id);
227 
228 
234 struct InvertibleBloomFilter *
235 ibf_dup (const struct InvertibleBloomFilter *ibf);
236 
237 
244 void
245 ibf_destroy (struct InvertibleBloomFilter *ibf);
246 
247 
248 #if 0 /* keep Emacsens' auto-indent happy */
249 {
250 #endif
251 #ifdef __cplusplus
252 }
253 #endif
254 
255 #endif
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:315
void ibf_destroy(struct InvertibleBloomFilter *ibf)
Destroy all resources associated with the invertible bloom filter.
Definition: ibf.c:388
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
struct IBF_Key * key_sum
Xor sums of the elements&#39; keys, used to identify the elements.
Definition: ibf.h:99
static int start
Set if we are to start default services (including ARM).
Definition: gnunet-arm.c:39
Invertible bloom filter (IBF).
Definition: ibf.h:82
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
uint64_t key_val
Definition: ibf.h:47
uint32_t size
How many cells does this IBF have?
Definition: ibf.h:87
struct InvertibleBloomFilter * ibf_create(uint32_t size, uint8_t hash_num)
Create an invertible bloom filter.
Definition: ibf.c:76
uint32_t key_hash_val
Definition: ibf.h:56
static char buf[2048]
uint8_t hash_num
In how many cells do we hash one element? Usually 4 or 3.
Definition: ibf.h:93
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:284
A 512-bit hashcode.
Type of the count field of IBF buckets.
Definition: ibf.h:63
struct IBF_KeyHash * key_hash_sum
Xor sums of the hashes of the keys of inserted elements.
Definition: ibf.h:105
struct GNUNET_HashCode key
The key used in the DHT.
void ibf_remove(struct InvertibleBloomFilter *ibf, struct IBF_Key key)
Remove a key from an IBF.
Definition: ibf.c:180
static unsigned int size
Size of the "table".
Definition: peer.c:67
static unsigned int hash_num
Hash of an IBF key.
Definition: ibf.h:54
struct IBF_Key ibf_key_from_hashcode(const struct GNUNET_HashCode *hash)
Create a key from a hashcode.
Definition: ibf.c:42
struct InvertibleBloomFilter * ibf_dup(const struct InvertibleBloomFilter *ibf)
Create a copy of an IBF, the copy has to be destroyed properly.
Definition: ibf.c:368
int8_t count_val
Definition: ibf.h:65
Keys that can be inserted into and removed from an IBF.
Definition: ibf.h:45
void ibf_subtract(struct InvertibleBloomFilter *ibf1, const struct InvertibleBloomFilter *ibf2)
Subtract ibf2 from ibf1, storing the result in ibf1.
Definition: ibf.c:346
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
void ibf_insert(struct InvertibleBloomFilter *ibf, struct IBF_Key key)
Insert a key into an IBF.
Definition: ibf.c:164