src/consensus/ibf.h

   1 /*
   2       This file is part of GNUnet
   3       (C) 2012 Christian Grothoff (and other contributing authors)
   4
   5       GNUnet is free software; you can redistribute it and/or modify
   6       it under the terms of the GNU General Public License as published
   7       by the Free Software Foundation; either version 2, or (at your
   8       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       General Public License for more details.
  14
  15       You should have received a copy of the GNU General Public License
  16       along with GNUnet; see the file COPYING.  If not, write to the
  17       Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  18       Boston, MA 02111-1307, USA.
  19 */
  20
  21 /**
  22  * @file consensus/ibf.h
  23  * @brief invertible bloom filter
  24  * @author Florian Dold
  25  */
  26
  27 #ifndef GNUNET_CONSENSUS_IBF_H
  28 #define GNUNET_CONSENSUS_IBF_H
  29
  30 #include "platform.h"
  31 #include "gnunet_common.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
  43 struct IBF_Key
  44 {
  45   uint64_t key_val;
  46 };
  47
  48 struct IBF_KeyHash
  49 {
  50   uint32_t key_hash_val;
  51 };
  52
  53 struct IBF_Count
  54 {
  55   int8_t count_val;
  56 };
  57
  58 /**
  59  * Size of one ibf bucket in bytes
  60  */
  61 #define IBF_BUCKET_SIZE (sizeof (struct IBF_Count) + sizeof (struct IBF_Key) + \
  62     sizeof (struct IBF_KeyHash))
  63
  64 /**
  65  * Invertible bloom filter (IBF).
  66  *
  67  * An IBF is a counting bloom filter that has the ability to restore
  68  * the hashes of its stored elements with high probability.
  69  */
  70 struct InvertibleBloomFilter
  71 {
  72   /**
  73    * How many cells does this IBF have?
  74    */
  75   uint32_t size;
  76
  77   /**
  78    * In how many cells do we hash one element?
  79    * Usually 4 or 3.
  80    */
  81   uint8_t hash_num;
  82
  83   /**
  84    * Salt for mingling hashes
  85    */
  86   uint32_t salt;
  87
  88   /**
  89    * Xor sums of the elements' keys, used to identify the elements.
  90    * Array of 'size' elements.
  91    */
  92   struct IBF_Key *key_sum;
  93
  94   /**
  95    * Xor sums of the hashes of the keys of inserted elements.
  96    * Array of 'size' elements.
  97    */
  98   struct IBF_KeyHash *key_hash_sum;
  99
 100   /**
 101    * How many times has a bucket been hit?
 102    * Can be negative, as a result of IBF subtraction.
 103    * Array of 'size' elements.
 104    */
 105   struct IBF_Count *count;
 106 };
 107
 108
 109 /**
 110  * Write an ibf.
 111  *
 112  * @param ibf the ibf to write
 113  * @param start with which bucket to start
 114  * @param count how many buckets to write
 115  * @param buf buffer to write the data to, will be updated to point to the
 116  *            first byte after the written data
 117  * @param size pointer to the size of the buffer, will be updated, can be NULL
 118  */
 119 void
 120 ibf_write_slice (const struct InvertibleBloomFilter *ibf, uint32_t start, uint32_t count, void **buf, size_t *size);
 121
 122
 123 /**
 124  * Read an ibf.
 125  *
 126  * @param buf pointer to the buffer to write to, will point to first
 127  *            byte after the written data
 128  * @param size size of the buffer, will be updated
 129  * @param start which bucket to start at
 130  * @param count how many buckets to read
 131  * @param dst ibf to write buckets to
 132  * @return GNUNET_OK on success
 133  */
 134 int
 135 ibf_read_slice (void **buf, size_t *size, uint32_t start, uint32_t count, struct InvertibleBloomFilter *dst);
 136
 137
 138 /**
 139  * Write an ibf.
 140  *
 141  * @param ibf the ibf to write
 142  * @param start with which bucket to start
 143  * @param count how many buckets to write
 144  * @param buf buffer to write the data to, will be updated to point to the
 145  *            first byte after the written data
 146  * @param size pointer to the size of the buffer, will be updated, can be NULL
 147  */
 148 void
 149 ibf_write (const struct InvertibleBloomFilter *ibf, void **buf, size_t *size);
 150
 151
 152 /**
 153  * Read an ibf.
 154  *
 155  * @param buf pointer to the buffer to write to, will point to first
 156  *            byte after the written data
 157  * @param size size of the buffer, will be updated
 158  * @param start which bucket to start at
 159  * @param count how many buckets to read
 160  * @param dst ibf to write buckets to
 161  * @return GNUNET_OK on success
 162  */
 163 int
 164 ibf_read (void **buf, size_t *size, struct InvertibleBloomFilter *dst);
 165
 166
 167 /**
 168  * Create a key from a hashcode.
 169  *
 170  * @param hash the hashcode
 171  * @return a key
 172  */
 173 struct IBF_Key
 174 ibf_key_from_hashcode (const struct GNUNET_HashCode *hash);
 175
 176
 177 /**
 178  * Create a hashcode from a key, by replicating the key
 179  * until the hascode is filled
 180  *
 181  * @param key the key
 182  * @param dst hashcode to store the result in
 183  */
 184 void
 185 ibf_hashcode_from_key (struct IBF_Key key, struct GNUNET_HashCode *dst);
 186
 187
 188 /**
 189  * Create an invertible bloom filter.
 190  *
 191  * @param size number of IBF buckets
 192  * @param hash_num number of buckets one element is hashed in, usually 3 or 4
 193  * @param salt salt for mingling hashes, different salt may
 194  *        result in less (or more) collisions
 195  * @return the newly created invertible bloom filter
 196  */
 197 struct InvertibleBloomFilter *
 198 ibf_create (uint32_t size, uint8_t hash_num, uint32_t salt);
 199
 200
 201 /**
 202  * Insert an element into an IBF.
 203  *
 204  * @param ibf the IBF
 205  * @param key the element's hash code
 206  */
 207 void
 208 ibf_insert (struct InvertibleBloomFilter *ibf, struct IBF_Key key);
 209
 210
 211 /**
 212  * Subtract ibf2 from ibf1, storing the result in ibf1.
 213  * The two IBF's must have the same parameters size and hash_num.
 214  *
 215  * @param ibf1 IBF that is subtracted from
 216  * @param ibf2 IBF that will be subtracted from ibf1
 217  */
 218 void
 219 ibf_subtract (struct InvertibleBloomFilter *ibf1, const struct InvertibleBloomFilter *ibf2);
 220
 221
 222 /**
 223  * Decode and remove an element from the IBF, if possible.
 224  *
 225  * @param ibf the invertible bloom filter to decode
 226  * @param side sign of the cell's count where the decoded element came from.
 227  *             A negative sign indicates that the element was recovered resides in an IBF
 228  *             that was previously subtracted from.
 229  * @param ret_id the hash code of the decoded element, if successful
 230  * @return GNUNET_YES if decoding an element was successful, GNUNET_NO if the IBF is empty,
 231  *         GNUNET_SYSERR if the decoding has faile
 232  */
 233 int
 234 ibf_decode (struct InvertibleBloomFilter *ibf, int *side, struct IBF_Key *ret_key);
 235
 236
 237 /**
 238  * Create a copy of an IBF, the copy has to be destroyed properly.
 239  *
 240  * @param ibf the IBF to copy
 241  */
 242 struct InvertibleBloomFilter *
 243 ibf_dup (const struct InvertibleBloomFilter *ibf);
 244
 245 /**
 246  * Destroy all resources associated with the invertible bloom filter.
 247  * No more ibf_*-functions may be called on ibf after calling destroy.
 248  *
 249  * @param ibf the intertible bloom filter to destroy
 250  */
 251 void
 252 ibf_destroy (struct InvertibleBloomFilter *ibf);
 253
 254
 255 #if 0                           /* keep Emacsens' auto-indent happy */
 256 {
 257 #endif
 258 #ifdef __cplusplus
 259 }
 260 #endif
 261
 262 #endif
 263