cuckoo

package module

v0.0.0-...-dc1bf47 Latest Latest Go to latest Published: Nov 23, 2024 License: MIT Imports: 6 Imported by: 0

Details

Valid go.mod file
Redistributable license
Tagged version
Stable version
Learn more about best practices

Repository

github.com/duongcongtoai/vacuumfilter

Links

Open Source Insights

README ¶

Credit

Code heavily taken from https://github.com/wuwuz/Vacuum-Filter Paper Link: http://www.vldb.org/pvldb/vol13/p197-wang.pdf

Documentation ¶

Index ¶

func BallsInBinsMaxLoad(balls, bins float64) float64
func F(x, c float64) float64
func FDerivative(x, c float64) float64
func HashUtilMurmurHash64(h uint64) uint64
func HashUtilMurmurHash64Raw(data []byte) uint64
func ProperAltRange(M, i int, len []int) int
func RoundDown(a, b uint64) uint64
func RoundUp(a, b int) int
func SolveEquation(c float64) float64
func UpperPower2(x int) int
type SemiSortCuckooFilter
type VacuumFilter

Constants ¶

This section is empty.

Variables ¶

This section is empty.

Functions ¶

func BallsInBinsMaxLoad ¶

func BallsInBinsMaxLoad(balls, bins float64) float64

BallsInBinsMaxLoad calculates the maximum load based on the balls-in-bins model.

func F ¶

func F(x, c float64) float64

F is the main function used in Newton's method.

func FDerivative ¶

func FDerivative(x, c float64) float64

FDerivative is the derivative of F with respect to x.

func HashUtilMurmurHash64 ¶

func HashUtilMurmurHash64(h uint64) uint64

HashUtilMurmurHash64 is a placeholder for the MurmurHash function

func HashUtilMurmurHash64Raw ¶

func HashUtilMurmurHash64Raw(data []byte) uint64

func ProperAltRange ¶

func ProperAltRange(M, i int, len []int) int

func RoundDown ¶

func RoundDown(a, b uint64) uint64

Helper function to round down a number to the nearest multiple of b

func RoundUp ¶

func RoundUp(a, b int) int

RoundUp rounds up to the nearest multiple of b

func SolveEquation ¶

func SolveEquation(c float64) float64

SolveEquation solves the given equation using Newton's method.

func UpperPower2 ¶

func UpperPower2(x int) int

Types ¶

type SemiSortCuckooFilter ¶

type SemiSortCuckooFilter struct {
	// contains filtered or unexported fields
}

func (*SemiSortCuckooFilter) Alternate ¶

func (v *SemiSortCuckooFilter) Alternate(pos int64, fp int64) int64

func (*SemiSortCuckooFilter) Clear ¶

func (f *SemiSortCuckooFilter) Clear()

Clear resets the filter

func (*SemiSortCuckooFilter) Delete ¶

func (f *SemiSortCuckooFilter) Delete(data []byte) bool

func (*SemiSortCuckooFilter) DeleteInBucket ¶

func (f *SemiSortCuckooFilter) DeleteInBucket(pos int64, fp int64) int

func (*SemiSortCuckooFilter) Fingerprint ¶

func (f *SemiSortCuckooFilter) Fingerprint(ele uint64) uint64

Fingerprint generates a fingerprint for an element

func (*SemiSortCuckooFilter) GetBucket ¶

func (f *SemiSortCuckooFilter) GetBucket(pos int64, store []int64)

func (*SemiSortCuckooFilter) GetLoadFactor ¶

func (f *SemiSortCuckooFilter) GetLoadFactor() float64

GetLoadFactor computes the load factor

func (*SemiSortCuckooFilter) Init ¶

func (f *SemiSortCuckooFilter) Init(maxItem, m, step int)

Init initializes the SemiSortCuckooFilter

func (*SemiSortCuckooFilter) Insert ¶

func (v *SemiSortCuckooFilter) Insert(data []byte) bool

Insert overrides Insert for VacuumFilter

func (*SemiSortCuckooFilter) InsertToBucket ¶

func (f *SemiSortCuckooFilter) InsertToBucket(store []int64, fp int64) int

func (*SemiSortCuckooFilter) Lookup ¶

func (f *SemiSortCuckooFilter) Lookup(raw []byte) bool

func (*SemiSortCuckooFilter) LookupInBucket ¶

func (f *SemiSortCuckooFilter) LookupInBucket(pos int64, fp int64) int

func (*SemiSortCuckooFilter) PositionHash ¶

func (f *SemiSortCuckooFilter) PositionHash(ele int64) int64

PositionHash maps an element to a position in the filter

func (*SemiSortCuckooFilter) SetBucket ¶

func (f *SemiSortCuckooFilter) SetBucket(pos int64, store []int64)

func (*SemiSortCuckooFilter) SortPair ¶

func (f *SemiSortCuckooFilter) SortPair(a, b *int64)

Helper function to sort two values in descending order

type VacuumFilter ¶

type VacuumFilter struct {
	SemiSortCuckooFilter
}

VacuumFilter is a type of SemiSortCuckooFilter

Source Files ¶

View all Source files

?	: This menu
/	: Search site
f or F	: Jump to
y or Y	: Canonical URL