bloom.gno

  1// Package bloom implements a Bloom filter, a space-efficient probabilistic
  2// 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 of
  8// a false positive grows as more elements are added and can be traded against
  9// memory usage when the filter is created.
 10package bloom
 11
 12import (
 13	"math"
 14
 15	"gno.land/p/g17khqpukees4237dtn3astzapmp462vjhsz6st4/bitset"
 16	"gno.land/p/g17khqpukees4237dtn3astzapmp462vjhsz6st4/murmur3"
 17)
 18
 19// Bloom is a probabilistic set-membership filter.
 20type Bloom struct {
 21	bits bitset.BitSet
 22	m    uint64 // Number of bits in the filter
 23	k    uint64 // Number of hash positions set per element
 24}
 25
 26// 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 = 1
 32	}
 33
 34	if k < 1 {
 35		k = 1
 36	}
 37
 38	return &Bloom{
 39		bits: bitset.New(m),
 40		m:    m,
 41		k:    k,
 42	}
 43}
 44
 45// New creates a filter sized to hold up to maxItems elements while keeping the
 46// false-positive probability around falsePositiveRate (for example 0.01 for 1%).
 47// It computes the optimal number of bits and hash functions and delegates to
 48// NewWithMK. Invalid inputs (maxItems == 0, or a rate outside the open interval
 49// (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	}
 54
 55	n := float64(maxItems)
 56	ln2 := math.Ln2
 57
 58	// m = ceil( -(n * ln(p)) / (ln2)^2 )
 59	m := uint64(math.Ceil(-(n * math.Log(falsePositiveRate)) / (ln2 * ln2)))
 60
 61	// k = round( (m/n) * ln2 )
 62	k := uint64(math.Round((float64(m) / n) * ln2))
 63
 64	return NewWithMK(m, k)
 65}
 66
 67// Capacity returns the capacity "m" of the filter.
 68func (b *Bloom) Capacity() uint64 {
 69	return b.m
 70}
 71
 72// HashFunctions returns the number of hash functions "k" of the filter.
 73func (b *Bloom) HashFunctions() uint64 {
 74	return b.k
 75}
 76
 77// Reset clears all values from the filter, keeping its capacity and hash count.
 78func (b *Bloom) Reset() *Bloom {
 79	b.bits.ClearAll()
 80	return b
 81}
 82
 83// 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 b
 90}
 91
 92// AddString inserts string data into the filter.
 93func (b *Bloom) AddString(data string) *Bloom {
 94	return b.Add([]byte(data))
 95}
 96
 97// 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 false
105		}
106	}
107	return true
108}
109
110// 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}
116
117// 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.m
120}
121
122// hashes splits a single 64-bit MurmurHash3 hash of data into two 32-bit halves
123// 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}