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  uint64_t key_val;
47 };
48 
49 
53 struct IBF_KeyHash {
54  uint32_t key_hash_val;
55 };
56 
57 
61 struct IBF_Count {
62  int8_t count_val;
63 };
64 
65 
69 #define IBF_BUCKET_SIZE (sizeof(struct IBF_Count) + sizeof(struct IBF_Key) + \
70  sizeof(struct IBF_KeyHash))
71 
72 
83  uint32_t size;
84 
89  uint8_t hash_num;
90 
95  struct IBF_Key *key_sum;
96 
102 
108  struct IBF_Count *count;
109 };
110 
111 
121 void
122 ibf_write_slice(const struct InvertibleBloomFilter *ibf,
123  uint32_t start,
124  uint32_t count,
125  void *buf);
126 
127 
136 void
137 ibf_read_slice(const void *buf,
138  uint32_t start,
139  uint32_t count,
140  struct InvertibleBloomFilter *ibf);
141 
142 
149 struct IBF_Key
150 ibf_key_from_hashcode(const struct GNUNET_HashCode *hash);
151 
152 
160 void
161 ibf_hashcode_from_key(struct IBF_Key key, struct GNUNET_HashCode *dst);
162 
163 
171 struct InvertibleBloomFilter *
172 ibf_create(uint32_t size, uint8_t hash_num);
173 
174 
181 void
182 ibf_insert(struct InvertibleBloomFilter *ibf, struct IBF_Key key);
183 
184 
191 void
192 ibf_remove(struct InvertibleBloomFilter *ibf, struct IBF_Key key);
193 
194 
202 void
204  const struct InvertibleBloomFilter *ibf2);
205 
206 
219 int
221  int *ret_side,
222  struct IBF_Key *ret_id);
223 
224 
230 struct InvertibleBloomFilter *
231 ibf_dup(const struct InvertibleBloomFilter *ibf);
232 
233 
240 void
242 
243 
244 #if 0 /* keep Emacsens' auto-indent happy */
245 {
246 #endif
247 #ifdef __cplusplus
248 }
249 #endif
250 
251 #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:318
void ibf_destroy(struct InvertibleBloomFilter *ibf)
Destroy all resources associated with the invertible bloom filter.
Definition: ibf.c:392
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:95
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:79
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
uint64_t key_val
Definition: ibf.h:46
uint32_t size
How many cells does this IBF have?
Definition: ibf.h:83
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:54
static char buf[2048]
uint8_t hash_num
In how many cells do we hash one element? Usually 4 or 3.
Definition: ibf.h:89
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:287
A 512-bit hashcode.
Type of the count field of IBF buckets.
Definition: ibf.h:61
struct IBF_KeyHash * key_hash_sum
Xor sums of the hashes of the keys of inserted elements.
Definition: ibf.h:101
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:181
static unsigned int size
Size of the "table".
Definition: peer.c:66
static unsigned int hash_num
Hash of an IBF key.
Definition: ibf.h:53
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:371
int8_t count_val
Definition: ibf.h:62
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:349
struct IBF_Count * count
How many times has a bucket been hit? Can be negative, as a result of IBF subtraction.
Definition: ibf.h:108
void ibf_insert(struct InvertibleBloomFilter *ibf, struct IBF_Key key)
Insert a key into an IBF.
Definition: ibf.c:164