Thanks for using Compiler Explorer
Sponsors
Jakt
C++
Ada
Analysis
Android Java
Android Kotlin
Assembly
C
C3
Carbon
C++ (Circle)
CIRCT
Clean
CMake
CMakeScript
COBOL
C++ for OpenCL
MLIR
Cppx
Cppx-Blue
Cppx-Gold
Cpp2-cppfront
Crystal
C#
CUDA C++
D
Dart
Elixir
Erlang
Fortran
F#
Go
Haskell
HLSL
Hook
Hylo
ispc
Java
Julia
Kotlin
LLVM IR
LLVM MIR
Modula-2
Nim
Objective-C
Objective-C++
OCaml
OpenCL C
Pascal
Pony
Python
Racket
Ruby
Rust
Snowball
Scala
Solidity
Spice
Swift
LLVM TableGen
Toit
TypeScript Native
V
Vala
Visual Basic
Zig
Javascript
GIMPLE
rust source #1
Output
Compile to binary object
Link to binary
Execute the code
Intel asm syntax
Demangle identifiers
Verbose demangling
Filters
Unused labels
Library functions
Directives
Comments
Horizontal whitespace
Debug intrinsics
Compiler
BPF gcc (trunk)
mrustc (master)
rustc 1.0.0
rustc 1.1.0
rustc 1.10.0
rustc 1.11.0
rustc 1.12.0
rustc 1.13.0
rustc 1.14.0
rustc 1.15.1
rustc 1.16.0
rustc 1.17.0
rustc 1.18.0
rustc 1.19.0
rustc 1.2.0
rustc 1.20.0
rustc 1.21.0
rustc 1.22.0
rustc 1.23.0
rustc 1.24.0
rustc 1.25.0
rustc 1.26.0
rustc 1.27.0
rustc 1.27.1
rustc 1.28.0
rustc 1.29.0
rustc 1.3.0
rustc 1.30.0
rustc 1.31.0
rustc 1.32.0
rustc 1.33.0
rustc 1.34.0
rustc 1.35.0
rustc 1.36.0
rustc 1.37.0
rustc 1.38.0
rustc 1.39.0
rustc 1.4.0
rustc 1.40.0
rustc 1.41.0
rustc 1.42.0
rustc 1.43.0
rustc 1.44.0
rustc 1.45.0
rustc 1.45.2
rustc 1.46.0
rustc 1.47.0
rustc 1.48.0
rustc 1.49.0
rustc 1.5.0
rustc 1.50.0
rustc 1.51.0
rustc 1.52.0
rustc 1.53.0
rustc 1.54.0
rustc 1.55.0
rustc 1.56.0
rustc 1.57.0
rustc 1.58.0
rustc 1.59.0
rustc 1.6.0
rustc 1.60.0
rustc 1.61.0
rustc 1.62.0
rustc 1.63.0
rustc 1.64.0
rustc 1.65.0
rustc 1.66.0
rustc 1.67.0
rustc 1.68.0
rustc 1.69.0
rustc 1.7.0
rustc 1.70.0
rustc 1.71.0
rustc 1.72.0
rustc 1.73.0
rustc 1.74.0
rustc 1.75.0
rustc 1.76.0
rustc 1.77.0
rustc 1.8.0
rustc 1.9.0
rustc beta
rustc nightly
rustc-cg-gcc (master)
x86-64 GCCRS (GCC master)
x86-64 GCCRS (GCCRS master)
Options
Source code
use std::hash::Hash; pub trait BloomFilter { fn contains<T: Hash>(&self, input: &T) -> bool; fn insert<T: Hash>(&mut self, input: &T); } pub mod bitvec { pub fn bitvec_at(position: usize, buf: &[u8]) -> bool { let index = position / 8; let shift = position % 8; (buf[index] >> shift) & 1u8 == 1u8 } pub fn bitvec_set(position: usize, buf: &mut [u8]) { let index = position / 8; let shift = position % 8; buf[index] |= 1u8 << shift; } #[cfg(test)] mod tests { use super::*; #[test] fn test_bitvec_at() { let mut buf = [0u8; 10]; buf[0] = 255u8; // The entirety of the first byte should be true. for i in 0..8 { assert_eq!(bitvec_at(i, &buf), true); } // The rest of the bitvector should be false. for i in 8..80 { assert_eq!(bitvec_at(i, &buf), false); } } #[test] fn test_bitvec_set() { let mut buf = [0u8; 10]; bitvec_set(0, &mut buf); assert_eq!(bitvec_at(0, &buf), true); // The rest of the bitvector should be unchanged. for i in 1..80 { assert_eq!(bitvec_at(i, &buf), false); } bitvec_set(7, &mut buf); assert_eq!(bitvec_at(7, &buf), true); bitvec_set(8, &mut buf); assert_eq!(bitvec_at(8, &buf), true); bitvec_set(9, &mut buf); assert_eq!(bitvec_at(9, &buf), true); bitvec_set(79, &mut buf); assert_eq!(bitvec_at(79, &buf), true); } } } use std::collections::hash_map::DefaultHasher; use std::hash::Hasher; use std::usize; /// A bloom filter that resides entirely on the stack. 'M' is the number /// of bytes allotted to the filter and 'N' is the number of items within /// the set. This filter will minimize the false positive rate. #[derive(Debug)] pub struct MinBFStack<const M: usize, const N: usize> { m: [u8; M], } impl<const M: usize, const N: usize> Default for MinBFStack<M, N> { fn default() -> Self { MinBFStack { m: [0u8; M] } } } impl<const M: usize, const N: usize> MinBFStack<M, N> { pub fn k() -> usize { // https://en.wikipedia.org/wiki/Bloom_filter#Optimal_number_of_hash_functions // TODO: There are situations where when we minimize the hash function number, // we choose k such that p is (1 / the number of atoms in the universe). Rather // than do this attempt to hit some upper bound. f32::ceil((8 * M / N) as f32 * f32::ln(2.0f32)) as usize } } impl<const M: usize, const N: usize> MinBFStack<M, N> { fn compute_hash<T: Hash>(input: &T, salt: usize) -> u64 { let mut state = DefaultHasher::new(); input.hash(&mut state); salt.hash(&mut state); state.finish() } } impl<const M: usize, const N: usize> BloomFilter for MinBFStack<M, N> { fn contains<T: Hash>(&self, input: &T) -> bool { for salt in 0..MinBFStack::<M, N>::k() { let position: usize = MinBFStack::<M, N>::compute_hash(input, salt) as usize % M; if bitvec::bitvec_at(position, &self.m) { return true; } } false } fn insert<T: Hash>(&mut self, input: &T) { for salt in 0..MinBFStack::<M, N>::k() { let position: usize = MinBFStack::<M, N>::compute_hash(input, salt) as usize % M; bitvec::bitvec_set(position, &mut self.m); } } } pub fn main() { let mut bf = MinBFStack::<8, 5>::default(); println!("k: {}", MinBFStack::<8, 5>::k()); bf.insert(&"ok"); println!("{}", bf.contains(&"ok")); }
Become a Patron
Sponsor on GitHub
Donate via PayPal
Source on GitHub
Mailing list
Installed libraries
Wiki
Report an issue
How it works
Contact the author
CE on Mastodon
About the author
Statistics
Changelog
Version tree