lib/bloom.h

   1 /*
   2  *  Copyright (c) 2012-2017, Jyri J. Virkki
   3  *  All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions are
   7  * met:
   8  *
   9  * 1. Redistributions of source code must retain the above copyright
  10  * notice, this list of conditions and the following disclaimer.
  11  *
  12  * 2. Redistributions in binary form must reproduce the above copyright
  13  * notice, this list of conditions and the following disclaimer in the
  14  * documentation and/or other materials provided with the distribution.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  20  * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  */
  28
  29 /* Obtained from https://github.com/jvirkki/libbloom */
  30
  31 #ifndef _BLOOM_H
  32 #define _BLOOM_H
  33
  34 #ifdef __cplusplus
  35 extern "C" {
  36 #endif
  37
  38
  39 /** ***************************************************************************
  40  * Structure to keep track of one bloom filter.  Caller needs to
  41  * allocate this and pass it to the functions below. First call for
  42  * every struct must be to bloom_init().
  43  *
  44  */
  45 struct bloom
  46 {
  47   // These fields are part of the public interface of this structure.
  48   // Client code may read these values if desired. Client code MUST NOT
  49   // modify any of these.
  50   int entries;
  51   double error;
  52   int bits;
  53   int bytes;
  54   int hashes;
  55   uint32_t seed;
  56
  57   // Fields below are private to the implementation. These may go away or
  58   // change incompatibly at any moment. Client code MUST NOT access or rely
  59   // on these.
  60   double bpe;
  61   unsigned char * bf;
  62   int ready;
  63 };
  64
  65
  66 /** ***************************************************************************
  67  * Initialize the bloom filter for use.
  68  *
  69  * The filter is initialized with a bit field and number of hash functions
  70  * according to the computations from the wikipedia entry:
  71  *     http://en.wikipedia.org/wiki/Bloom_filter
  72  *
  73  * Optimal number of bits is:
  74  *     bits = (entries * ln(error)) / ln(2)^2
  75  *
  76  * Optimal number of hash functions is:
  77  *     hashes = bpe * ln(2)
  78  *
  79  * Parameters:
  80  * -----------
  81  *     bloom   - Pointer to an allocated struct bloom (see above).
  82  *     entries - The expected number of entries which will be inserted.
  83  *               Must be at least 1000 (in practice, likely much larger).
  84  *     error   - Probability of collision (as long as entries are not
  85  *               exceeded).
  86  *
  87  * Return:
  88  * -------
  89  *     0 - on success
  90  *     1 - on failure
  91  *
  92  */
  93 int bloom_init(struct bloom * bloom, int entries, double error);
  94
  95
  96 /** ***************************************************************************
  97  * Deprecated, use bloom_init()
  98  *
  99  */
 100 int bloom_init_size(struct bloom * bloom, int entries, double error,
 101                     unsigned int cache_size);
 102
 103
 104 /** ***************************************************************************
 105  * Check if the given element is in the bloom filter. Remember this may
 106  * return false positive if a collision occurred.
 107  *
 108  * Parameters:
 109  * -----------
 110  *     bloom  - Pointer to an allocated struct bloom (see above).
 111  *     buffer - Pointer to buffer containing element to check.
 112  *     len    - Size of 'buffer'.
 113  *
 114  * Return:
 115  * -------
 116  *     0 - element is not present
 117  *     1 - element is present (or false positive due to collision)
 118  *    -1 - bloom not initialized
 119  *
 120  */
 121 int bloom_check(struct bloom * bloom, const void * buffer, int len);
 122
 123
 124 /** ***************************************************************************
 125  * Add the given element to the bloom filter.
 126  * The return code indicates if the element (or a collision) was already in,
 127  * so for the common check+add use case, no need to call check separately.
 128  *
 129  * Parameters:
 130  * -----------
 131  *     bloom  - Pointer to an allocated struct bloom (see above).
 132  *     buffer - Pointer to buffer containing element to add.
 133  *     len    - Size of 'buffer'.
 134  *
 135  * Return:
 136  * -------
 137  *     0 - element was not present and was added
 138  *     1 - element (or a collision) had already been added previously
 139  *    -1 - bloom not initialized
 140  *
 141  */
 142 int bloom_add(struct bloom * bloom, const void * buffer, int len);
 143
 144
 145 /** ***************************************************************************
 146  * Print (to stdout) info about this bloom filter. Debugging aid.
 147  *
 148  */
 149 void bloom_print(struct bloom * bloom);
 150
 151
 152 /** ***************************************************************************
 153  * Deallocate internal storage.
 154  *
 155  * Upon return, the bloom struct is no longer usable. You may call bloom_init
 156  * again on the same struct to reinitialize it again.
 157  *
 158  * Parameters:
 159  * -----------
 160  *     bloom  - Pointer to an allocated struct bloom (see above).
 161  *
 162  * Return: none
 163  *
 164  */
 165 void bloom_free(struct bloom * bloom);
 166
 167 /** ***************************************************************************
 168  * Erase internal storage.
 169  *
 170  * Erases all elements. Upon return, the bloom struct returns to its initial
 171  * (initialized) state.
 172  *
 173  * Parameters:
 174  * -----------
 175  *     bloom  - Pointer to an allocated struct bloom (see above).
 176  *
 177  * Return:
 178  *     0 - on success
 179  *     1 - on failure
 180  *
 181  */
 182 int bloom_reset(struct bloom * bloom);
 183
 184 #ifdef __cplusplus
 185 }
 186 #endif
 187
 188 #endif