src/set/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    * Xor sums of the elements' keys, used to identify the elements.
  85    * Array of 'size' elements.
  86    */
  87   struct IBF_Key *key_sum;
  88
  89   /**
  90    * Xor sums of the hashes of the keys of inserted elements.
  91    * Array of 'size' elements.
  92    */
  93   struct IBF_KeyHash *key_hash_sum;
  94
  95   /**
  96    * How many times has a bucket been hit?
  97    * Can be negative, as a result of IBF subtraction.
  98    * Array of 'size' elements.
  99    */
 100   struct IBF_Count *count;
 101 };
 102
 103
 104 /**
 105  * Write buckets from an ibf to a buffer.
 106  * Exactly (IBF_BUCKET_SIZE*ibf->size) bytes are written to buf.
 107  *
 108  * @param ibf the ibf to write
 109  * @param start with which bucket to start
 110  * @param count how many buckets to write
 111  * @param buf buffer to write the data to
 112  */
 113 void
 114 ibf_write_slice (const struct InvertibleBloomFilter *ibf, uint32_t start, uint32_t count, void *buf);
 115
 116
 117 /**
 118  * Read buckets from a buffer into an ibf.
 119  *
 120  * @param buf pointer to the buffer to read from
 121  * @param start which bucket to start at
 122  * @param count how many buckets to read
 123  * @param ibf the ibf to read from
 124  */
 125 void
 126 ibf_read_slice (const void *buf, uint32_t start, uint32_t count, struct InvertibleBloomFilter *ibf);
 127
 128
 129 /**
 130  * Create a key from a hashcode.
 131  *
 132  * @param hash the hashcode
 133  * @return a key
 134  */
 135 struct IBF_Key
 136 ibf_key_from_hashcode (const struct GNUNET_HashCode *hash);
 137
 138
 139 /**
 140  * Create a hashcode from a key, by replicating the key
 141  * until the hascode is filled
 142  *
 143  * @param key the key
 144  * @param dst hashcode to store the result in
 145  */
 146 void
 147 ibf_hashcode_from_key (struct IBF_Key key, struct GNUNET_HashCode *dst);
 148
 149
 150 /**
 151  * Create an invertible bloom filter.
 152  *
 153  * @param size number of IBF buckets
 154  * @param hash_num number of buckets one element is hashed in, usually 3 or 4
 155  * @return the newly created invertible bloom filter
 156  */
 157 struct InvertibleBloomFilter *
 158 ibf_create (uint32_t size, uint8_t hash_num);
 159
 160
 161 /**
 162  * Insert an element into an IBF.
 163  *
 164  * @param ibf the IBF
 165  * @param key the element's hash code
 166  */
 167 void
 168 ibf_insert (struct InvertibleBloomFilter *ibf, struct IBF_Key key);
 169
 170
 171 /**
 172  * Subtract ibf2 from ibf1, storing the result in ibf1.
 173  * The two IBF's must have the same parameters size and hash_num.
 174  *
 175  * @param ibf1 IBF that is subtracted from
 176  * @param ibf2 IBF that will be subtracted from ibf1
 177  */
 178 void
 179 ibf_subtract (struct InvertibleBloomFilter *ibf1, const struct InvertibleBloomFilter *ibf2);
 180
 181
 182 /**
 183  * Decode and remove an element from the IBF, if possible.
 184  *
 185  * @param ibf the invertible bloom filter to decode
 186  * @param ret_side sign of the cell's count where the decoded element came from.
 187  *                 A negative sign indicates that the element was recovered
 188  *                 resides in an IBF that was previously subtracted from.
 189  * @param ret_id receives the hash code of the decoded element, if successful
 190  * @return GNUNET_YES if decoding an element was successful,
 191  *         GNUNET_NO if the IBF is empty,
 192  *         GNUNET_SYSERR if the decoding has failed
 193  */
 194 int
 195 ibf_decode (struct InvertibleBloomFilter *ibf, int *ret_side, struct IBF_Key *ret_id);
 196
 197
 198 /**
 199  * Create a copy of an IBF, the copy has to be destroyed properly.
 200  *
 201  * @param ibf the IBF to copy
 202  */
 203 struct InvertibleBloomFilter *
 204 ibf_dup (const struct InvertibleBloomFilter *ibf);
 205
 206 /**
 207  * Destroy all resources associated with the invertible bloom filter.
 208  * No more ibf_*-functions may be called on ibf after calling destroy.
 209  *
 210  * @param ibf the intertible bloom filter to destroy
 211  */
 212 void
 213 ibf_destroy (struct InvertibleBloomFilter *ibf);
 214
 215
 216 #if 0                           /* keep Emacsens' auto-indent happy */
 217 {
 218 #endif
 219 #ifdef __cplusplus
 220 }
 221 #endif
 222
 223 #endif
 224