gno.land/p/g17khqpukees4237dtn3astzapmp462vjhsz6st4/bloom⧉

1// Package bloom implements a Bloom filter, a space-efficient probabilistic2// data structure used to test whether an element is a member of a set.3//4// A Bloom filter never reports a false negative; If Contains returns false,5// the element was definitely never added. It may report a false positive.6//7// Contains can return true for an element that was never added. The chance of8// a false positive grows as more elements are added and can be traded against9// memory usage when the filter is created.10package bloom1112import (13	"math"1415	"gno.land/p/g17khqpukees4237dtn3astzapmp462vjhsz6st4/bitset"16	"gno.land/p/g17khqpukees4237dtn3astzapmp462vjhsz6st4/murmur3"17)1819// Bloom is a probabilistic set-membership filter.20type Bloom struct {21	bits bitset.BitSet22	m    uint64 // Number of bits in the filter23	k    uint64 // Number of hash positions set per element24}2526// NewWithMK creates a filter with an explicit bit-array size m and hash count k.27// It is the low-level constructor for callers who already know the parameters;28// Most users should prefer New. Both m and k are clamped to a minimum of 1.29func NewWithMK(m, k uint64) *Bloom {30	if m < 1 {31		m = 132	}3334	if k < 1 {35		k = 136	}3738	return &Bloom{39		bits: bitset.New(m),40		m:    m,41		k:    k,42	}43}4445// New creates a filter sized to hold up to maxItems elements while keeping the46// false-positive probability around falsePositiveRate (for example 0.01 for 1%).47// It computes the optimal number of bits and hash functions and delegates to48// NewWithMK. Invalid inputs (maxItems == 0, or a rate outside the open interval49// (0, 1)) fall back to a minimal usable filter.50func New(maxItems uint64, falsePositiveRate float64) *Bloom {51	if maxItems == 0 || falsePositiveRate <= 0 || falsePositiveRate >= 1 {52		return NewWithMK(1, 1)53	}5455	n := float64(maxItems)56	ln2 := math.Ln25758	// m = ceil( -(n * ln(p)) / (ln2)^2 )59	m := uint64(math.Ceil(-(n * math.Log(falsePositiveRate)) / (ln2 * ln2)))6061	// k = round( (m/n) * ln2 )62	k := uint64(math.Round((float64(m) / n) * ln2))6364	return NewWithMK(m, k)65}6667// Capacity returns the capacity "m" of the filter.68func (b *Bloom) Capacity() uint64 {69	return b.m70}7172// HashFunctions returns the number of hash functions "k" of the filter.73func (b *Bloom) HashFunctions() uint64 {74	return b.k75}7677// Reset clears all values from the filter, keeping its capacity and hash count.78func (b *Bloom) Reset() *Bloom {79	b.bits.ClearAll()80	return b81}8283// Add inserts data into the filter.84func (b *Bloom) Add(data []byte) *Bloom {85	h1, h2 := hashes(data)86	for i := uint64(0); i < b.k; i++ {87		b.bits.Set(b.index(h1, h2, i))88	}89	return b90}9192// AddString inserts string data into the filter.93func (b *Bloom) AddString(data string) *Bloom {94	return b.Add([]byte(data))95}9697// Contains checks whether data is possibly in the set.98// A false result means data was definitely never added.99// A true result means data was probably added but may be a false positive.100func (b *Bloom) Contains(data []byte) bool {101	h1, h2 := hashes(data)102	for i := uint64(0); i < b.k; i++ {103		if !b.bits.IsSet(b.index(h1, h2, i)) {104			return false105		}106	}107	return true108}109110// ContainsString checks whether string data is possibly in the set.111// A false result means data was definitely never added.112// A true result means data was probably added but may be a false positive.113func (b *Bloom) ContainsString(data string) bool {114	return b.Contains([]byte(data))115}116117// index returns the i-th bit position for an element using double hashing.118func (b *Bloom) index(h1, h2 uint32, i uint64) uint64 {119	return (uint64(h1) + i*uint64(h2)) % b.m120}121122// hashes splits a single 64-bit MurmurHash3 hash of data into two 32-bit halves123// used as the seeds for double hashing.124func hashes(data []byte) (h1, h2 uint32) {125	sum := murmur3.Sum64(data)126	return uint32(sum >> 32), uint32(sum)127}128