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