1 | /* |
2 | * Copyright (c) 2021 Apple Inc. All rights reserved. |
3 | * |
4 | * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ |
5 | * |
6 | * This file contains Original Code and/or Modifications of Original Code |
7 | * as defined in and that are subject to the Apple Public Source License |
8 | * Version 2.0 (the 'License'). You may not use this file except in |
9 | * compliance with the License. The rights granted to you under the License |
10 | * may not be used to create, or enable the creation or redistribution of, |
11 | * unlawful or unlicensed copies of an Apple operating system, or to |
12 | * circumvent, violate, or enable the circumvention or violation of, any |
13 | * terms of an Apple operating system software license agreement. |
14 | * |
15 | * Please obtain a copy of the License at |
16 | * http://www.opensource.apple.com/apsl/ and read it before using this file. |
17 | * |
18 | * The Original Code and all software distributed under the License are |
19 | * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER |
20 | * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, |
21 | * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, |
22 | * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. |
23 | * Please see the License for the specific language governing rights and |
24 | * limitations under the License. |
25 | * |
26 | * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ |
27 | */ |
28 | |
29 | #ifndef _NET_BLOOM_FILTER_H_ |
30 | #define _NET_BLOOM_FILTER_H_ |
31 | |
32 | #include <sys/types.h> |
33 | |
34 | #ifdef __cplusplus |
35 | extern "C" { |
36 | #endif |
37 | |
38 | // A Bloom Filter is a space-efficient probabilistic data structure |
39 | // that is used to test whether an element is a member of a set. It has a small |
40 | // rate of false positives, but it is guaranteed to have no false negatives. |
41 | // |
42 | // net_bloom_filter is a minimal implementation for use in kernel networking |
43 | // that uses three hash functions: net_flowhash_jhash, net_flowhash_mh3_x64_128, |
44 | // and net_flowhash_mh3_x86_32. This is optimal for a 10% false positive rate. |
45 | // The optimal number of bits should be calculated as: |
46 | // num_bits = ((2.3 * ELEMENT_COUNT) / 0.48) |
47 | |
48 | struct net_bloom_filter { |
49 | uint32_t b_table_num_bits; |
50 | uint32_t b_table[0]; |
51 | }; |
52 | |
53 | struct net_bloom_filter * |
54 | net_bloom_filter_create(uint32_t num_bits); |
55 | |
56 | size_t |
57 | net_bloom_filter_get_size(uint32_t num_bits); |
58 | |
59 | void |
60 | net_bloom_filter_destroy(struct net_bloom_filter *filter); |
61 | |
62 | void |
63 | net_bloom_filter_insert(struct net_bloom_filter *filter, |
64 | const void *buffer, |
65 | uint32_t length); |
66 | |
67 | bool |
68 | net_bloom_filter_contains(struct net_bloom_filter *filter, |
69 | const void *buffer, |
70 | uint32_t length); |
71 | |
72 | #ifdef __cplusplus |
73 | } |
74 | #endif |
75 | |
76 | #endif /* _NET_BLOOM_FILTER_H_ */ |
77 | |