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