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 
56   // Fields below are private to the implementation. These may go away or
57   // change incompatibly at any moment. Client code MUST NOT access or rely
58   // on these.
59   double bpe;
60   unsigned char * bf;
61   int ready;
62 };
63 
64 
65 /** ***************************************************************************
66  * Initialize the bloom filter for use.
67  *
68  * The filter is initialized with a bit field and number of hash functions
69  * according to the computations from the wikipedia entry:
70  *     http://en.wikipedia.org/wiki/Bloom_filter
71  *
72  * Optimal number of bits is:
73  *     bits = (entries * ln(error)) / ln(2)^2
74  *
75  * Optimal number of hash functions is:
76  *     hashes = bpe * ln(2)
77  *
78  * Parameters:
79  * -----------
80  *     bloom   - Pointer to an allocated struct bloom (see above).
81  *     entries - The expected number of entries which will be inserted.
82  *               Must be at least 1000 (in practice, likely much larger).
83  *     error   - Probability of collision (as long as entries are not
84  *               exceeded).
85  *
86  * Return:
87  * -------
88  *     0 - on success
89  *     1 - on failure
90  *
91  */
92 int bloom_init(struct bloom * bloom, int entries, double error);
93 
94 
95 /** ***************************************************************************
96  * Deprecated, use bloom_init()
97  *
98  */
99 int bloom_init_size(struct bloom * bloom, int entries, double error,
100                     unsigned int cache_size);
101 
102 
103 /** ***************************************************************************
104  * Check if the given element is in the bloom filter. Remember this may
105  * return false positive if a collision occurred.
106  *
107  * Parameters:
108  * -----------
109  *     bloom  - Pointer to an allocated struct bloom (see above).
110  *     buffer - Pointer to buffer containing element to check.
111  *     len    - Size of 'buffer'.
112  *
113  * Return:
114  * -------
115  *     0 - element is not present
116  *     1 - element is present (or false positive due to collision)
117  *    -1 - bloom not initialized
118  *
119  */
120 int bloom_check(struct bloom * bloom, const void * buffer, int len);
121 
122 
123 /** ***************************************************************************
124  * Add the given element to the bloom filter.
125  * The return code indicates if the element (or a collision) was already in,
126  * so for the common check+add use case, no need to call check separately.
127  *
128  * Parameters:
129  * -----------
130  *     bloom  - Pointer to an allocated struct bloom (see above).
131  *     buffer - Pointer to buffer containing element to add.
132  *     len    - Size of 'buffer'.
133  *
134  * Return:
135  * -------
136  *     0 - element was not present and was added
137  *     1 - element (or a collision) had already been added previously
138  *    -1 - bloom not initialized
139  *
140  */
141 int bloom_add(struct bloom * bloom, const void * buffer, int len);
142 
143 
144 /** ***************************************************************************
145  * Print (to stdout) info about this bloom filter. Debugging aid.
146  *
147  */
148 void bloom_print(struct bloom * bloom);
149 
150 
151 /** ***************************************************************************
152  * Deallocate internal storage.
153  *
154  * Upon return, the bloom struct is no longer usable. You may call bloom_init
155  * again on the same struct to reinitialize it again.
156  *
157  * Parameters:
158  * -----------
159  *     bloom  - Pointer to an allocated struct bloom (see above).
160  *
161  * Return: none
162  *
163  */
164 void bloom_free(struct bloom * bloom);
165 
166 /** ***************************************************************************
167  * Erase internal storage.
168  *
169  * Erases all elements. Upon return, the bloom struct returns to its initial
170  * (initialized) state.
171  *
172  * Parameters:
173  * -----------
174  *     bloom  - Pointer to an allocated struct bloom (see above).
175  *
176  * Return:
177  *     0 - on success
178  *     1 - on failure
179  *
180  */
181 int bloom_reset(struct bloom * bloom);
182 
183 #ifdef __cplusplus
184 }
185 #endif
186 
187 #endif