src/set/ibf.h

   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
  19 /**
  20  * @file set/ibf.h
  21  * @brief invertible bloom filter
  22  * @author Florian Dold
  23  */
  24
  25 #ifndef GNUNET_CONSENSUS_IBF_H
  26 #define GNUNET_CONSENSUS_IBF_H
  27
  28 #include "platform.h"
  29 #include "gnunet_util_lib.h"
  30
  31 #ifdef __cplusplus
  32 extern "C"
  33 {
  34 #if 0                           /* keep Emacsens' auto-indent happy */
  35 }
  36 #endif
  37 #endif
  38
  39
  40 /**
  41  * Keys that can be inserted into and removed from an IBF.
  42  */
  43 struct IBF_Key
  44 {
  45   uint64_t key_val;
  46 };
  47
  48
  49 /**
  50  * Hash of an IBF key.
  51  */
  52 struct IBF_KeyHash
  53 {
  54   uint32_t key_hash_val;
  55 };
  56
  57
  58 /**
  59  * Type of the count field of IBF buckets.
  60  */
  61 struct IBF_Count
  62 {
  63   int8_t count_val;
  64 };
  65
  66
  67 /**
  68  * Size of one ibf bucket in bytes
  69  */
  70 #define IBF_BUCKET_SIZE (sizeof (struct IBF_Count) + sizeof (struct IBF_Key) + \
  71     sizeof (struct IBF_KeyHash))
  72
  73
  74 /**
  75  * Invertible bloom filter (IBF).
  76  *
  77  * An IBF is a counting bloom filter that has the ability to restore
  78  * the hashes of its stored elements with high probability.
  79  */
  80 struct InvertibleBloomFilter
  81 {
  82   /**
  83    * How many cells does this IBF have?
  84    */
  85   uint32_t size;
  86
  87   /**
  88    * In how many cells do we hash one element?
  89    * Usually 4 or 3.
  90    */
  91   uint8_t hash_num;
  92
  93   /**
  94    * Xor sums of the elements' keys, used to identify the elements.
  95    * Array of 'size' elements.
  96    */
  97   struct IBF_Key *key_sum;
  98
  99   /**
 100    * Xor sums of the hashes of the keys of inserted elements.
 101    * Array of 'size' elements.
 102    */
 103   struct IBF_KeyHash *key_hash_sum;
 104
 105   /**
 106    * How many times has a bucket been hit?
 107    * Can be negative, as a result of IBF subtraction.
 108    * Array of 'size' elements.
 109    */
 110   struct IBF_Count *count;
 111 };
 112
 113
 114 /**
 115  * Write buckets from an ibf to a buffer.
 116  * Exactly (IBF_BUCKET_SIZE*ibf->size) bytes are written to buf.
 117  *
 118  * @param ibf the ibf to write
 119  * @param start with which bucket to start
 120  * @param count how many buckets to write
 121  * @param buf buffer to write the data to
 122  */
 123 void
 124 ibf_write_slice (const struct InvertibleBloomFilter *ibf,
 125                  uint32_t start,
 126                  uint32_t count,
 127                  void *buf);
 128
 129
 130 /**
 131  * Read buckets from a buffer into an ibf.
 132  *
 133  * @param buf pointer to the buffer to read from
 134  * @param start which bucket to start at
 135  * @param count how many buckets to read
 136  * @param ibf the ibf to write to
 137  */
 138 void
 139 ibf_read_slice (const void *buf,
 140                 uint32_t start,
 141                 uint32_t count,
 142                 struct InvertibleBloomFilter *ibf);
 143
 144
 145 /**
 146  * Create a key from a hashcode.
 147  *
 148  * @param hash the hashcode
 149  * @return a key
 150  */
 151 struct IBF_Key
 152 ibf_key_from_hashcode (const struct GNUNET_HashCode *hash);
 153
 154
 155 /**
 156  * Create a hashcode from a key, by replicating the key
 157  * until the hascode is filled
 158  *
 159  * @param key the key
 160  * @param dst hashcode to store the result in
 161  */
 162 void
 163 ibf_hashcode_from_key (struct IBF_Key key, struct GNUNET_HashCode *dst);
 164
 165
 166 /**
 167  * Create an invertible bloom filter.
 168  *
 169  * @param size number of IBF buckets
 170  * @param hash_num number of buckets one element is hashed in, usually 3 or 4
 171  * @return the newly created invertible bloom filter, NULL on error
 172  */
 173 struct InvertibleBloomFilter *
 174 ibf_create (uint32_t size, uint8_t hash_num);
 175
 176
 177 /**
 178  * Insert a key into an IBF.
 179  *
 180  * @param ibf the IBF
 181  * @param key the element's hash code
 182  */
 183 void
 184 ibf_insert (struct InvertibleBloomFilter *ibf, struct IBF_Key key);
 185
 186
 187 /**
 188  * Remove a key from an IBF.
 189  *
 190  * @param ibf the IBF
 191  * @param key the element's hash code
 192  */
 193 void
 194 ibf_remove (struct InvertibleBloomFilter *ibf, struct IBF_Key key);
 195
 196
 197 /**
 198  * Subtract ibf2 from ibf1, storing the result in ibf1.
 199  * The two IBF's must have the same parameters size and hash_num.
 200  *
 201  * @param ibf1 IBF that is subtracted from
 202  * @param ibf2 IBF that will be subtracted from ibf1
 203  */
 204 void
 205 ibf_subtract (struct InvertibleBloomFilter *ibf1,
 206               const struct InvertibleBloomFilter *ibf2);
 207
 208
 209 /**
 210  * Decode and remove an element from the IBF, if possible.
 211  *
 212  * @param ibf the invertible bloom filter to decode
 213  * @param ret_side sign of the cell's count where the decoded element came from.
 214  *                 A negative sign indicates that the element was recovered
 215  *                 resides in an IBF that was previously subtracted from.
 216  * @param ret_id receives the hash code of the decoded element, if successful
 217  * @return #GNUNET_YES if decoding an element was successful,
 218  *         #GNUNET_NO if the IBF is empty,
 219  *         #GNUNET_SYSERR if the decoding has failed
 220  */
 221 int
 222 ibf_decode (struct InvertibleBloomFilter *ibf,
 223             int *ret_side,
 224             struct IBF_Key *ret_id);
 225
 226
 227 /**
 228  * Create a copy of an IBF, the copy has to be destroyed properly.
 229  *
 230  * @param ibf the IBF to copy
 231  */
 232 struct InvertibleBloomFilter *
 233 ibf_dup (const struct InvertibleBloomFilter *ibf);
 234
 235
 236 /**
 237  * Destroy all resources associated with the invertible bloom filter.
 238  * No more ibf_*-functions may be called on ibf after calling destroy.
 239  *
 240  * @param ibf the intertible bloom filter to destroy
 241  */
 242 void
 243 ibf_destroy (struct InvertibleBloomFilter *ibf);
 244
 245
 246 #if 0                           /* keep Emacsens' auto-indent happy */
 247 {
 248 #endif
 249 #ifdef __cplusplus
 250 }
 251 #endif
 252
 253 #endif