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