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  * Size of one ibf bucket in bytes
  44  */
  45 #define IBF_BUCKET_SIZE (8+4+1)
  46
  47
  48 /**
  49  * Invertible bloom filter (IBF).
  50  *
  51  * An IBF is a counting bloom filter that has the ability to restore
  52  * the hashes of its stored elements with high probability.
  53  */
  54 struct InvertibleBloomFilter
  55 {
  56   /**
  57    * How many cells does this IBF have?
  58    */
  59   uint32_t size;
  60
  61   /**
  62    * In how many cells do we hash one element?
  63    * Usually 4 or 3.
  64    */
  65   unsigned int hash_num;
  66
  67   /**
  68    * Salt for mingling hashes
  69    */
  70   uint32_t salt;
  71
  72   /**
  73    * xor sums of the elements' hash codes, used to identify the elements.
  74    */
  75   uint64_t *id_sum;
  76
  77   /**
  78    * xor sums of the "hash of the hash".
  79    */
  80   uint32_t *hash_sum;
  81
  82   /**
  83    * How many times has a bucket been hit?
  84    * Can be negative, as a result of IBF subtraction.
  85    */
  86   int8_t *count;
  87 };
  88
  89
  90 /**
  91  * Create a key from a hashcode.
  92  *
  93  * @param hash the hashcode
  94  * @return a key
  95  */
  96 uint64_t
  97 ibf_key_from_hashcode (const struct GNUNET_HashCode *hash);
  98
  99
 100 /**
 101  * Create a hashcode from a key, by replicating the key
 102  * until the hascode is filled
 103  *
 104  * @param key the key
 105  * @param dst hashcode to store the result in
 106  */
 107 void
 108 ibf_hashcode_from_key (uint64_t key, struct GNUNET_HashCode *dst);
 109
 110
 111 /**
 112  * Create an invertible bloom filter.
 113  *
 114  * @param size number of IBF buckets
 115  * @param hash_num number of buckets one element is hashed in, usually 3 or 4
 116  * @param salt salt for mingling hashes, different salt may
 117  *        result in less (or more) collisions
 118  * @return the newly created invertible bloom filter
 119  */
 120 struct InvertibleBloomFilter *
 121 ibf_create(uint32_t size, unsigned int hash_num, uint32_t salt);
 122
 123
 124 /**
 125  * Insert an element into an IBF.
 126  *
 127  * @param ibf the IBF
 128  * @param id the element's hash code
 129  */
 130 void
 131 ibf_insert (struct InvertibleBloomFilter *ibf, uint64_t id);
 132
 133
 134 /**
 135  * Subtract ibf2 from ibf1, storing the result in ibf1.
 136  * The two IBF's must have the same parameters size and hash_num.
 137  *
 138  * @param ibf1 IBF that is subtracted from
 139  * @param ibf2 IBF that will be subtracted from ibf1
 140  */
 141 void
 142 ibf_subtract (struct InvertibleBloomFilter *ibf1, const struct InvertibleBloomFilter *ibf2);
 143
 144
 145 /**
 146  * Decode and remove an element from the IBF, if possible.
 147  *
 148  * @param ibf the invertible bloom filter to decode
 149  * @param side sign of the cell's count where the decoded element came from.
 150  *             A negative sign indicates that the element was recovered resides in an IBF
 151  *             that was previously subtracted from.
 152  * @param ret_id the hash code of the decoded element, if successful
 153  * @return GNUNET_YES if decoding an element was successful, GNUNET_NO if the IBF is empty,
 154  *         GNUNET_SYSERR if the decoding has faile
 155  */
 156 int
 157 ibf_decode (struct InvertibleBloomFilter *ibf, int *side, uint64_t *ret_id);
 158
 159
 160 /**
 161  * Create a copy of an IBF, the copy has to be destroyed properly.
 162  *
 163  * @param ibf the IBF to copy
 164  */
 165 struct InvertibleBloomFilter *
 166 ibf_dup (struct InvertibleBloomFilter *ibf);
 167
 168 /**
 169  * Destroy all resources associated with the invertible bloom filter.
 170  * No more ibf_*-functions may be called on ibf after calling destroy.
 171  *
 172  * @param ibf the intertible bloom filter to destroy
 173  */
 174 void
 175 ibf_destroy (struct InvertibleBloomFilter *ibf);
 176
 177
 178 #if 0                           /* keep Emacsens' auto-indent happy */
 179 {
 180 #endif
 181 #ifdef __cplusplus
 182 }
 183 #endif
 184
 185 #endif
 186