cuckoofilter

Documentation

Index

• func Bytes2String(buf []byte) string
• func GetAnotherIndex(i uint, fp Fingerprint, bucketPow uint) uint
• func GetOneIndex(x string, bucketPow uint) uint
• func RandomlySelect(i1, i2 uint) uint
• func Serialize(cf *CuckooFilter) []byte
• type Bucket
  • func (bk *Bucket) Delete(fp Fingerprint) bool
  • func (bk *Bucket) GetFingerprintIndex(fp Fingerprint) int
  • func (bk *Bucket) Insert(fp Fingerprint) bool
  • func (bk *Bucket) Reset()
• type CuckooFilter
  • func Deserialize(bytes []byte) (*CuckooFilter, error)
  • func NewCuckooFilter(cap uint) *CuckooFilter
  • func (cf *CuckooFilter) Count() uint
  • func (cf *CuckooFilter) Delete(x string) bool
  • func (cf *CuckooFilter) Insert(x string) bool
  • func (cf *CuckooFilter) Lookup(x string) bool
  • func (cf *CuckooFilter) Reset()
• type Fingerprint
  • func GetFingerprint(x string) Fingerprint

Functions

func Bytes2String

func Bytes2String(buf []byte) string

Bytes2String fast type conversion from byte array to string, both share the same mem pointer.

func GetAnotherIndex

func GetAnotherIndex(i uint, fp Fingerprint, bucketPow uint) uint

func GetOneIndex

func GetOneIndex(x string, bucketPow uint) uint

func RandomlySelect

func RandomlySelect(i1, i2 uint) uint

func Serialize

func Serialize(cf *CuckooFilter) []byte

Serialize returns a byte slice representing a CuckooFilter.

Types

type Bucket

type Bucket [_BucketSize]Fingerprint

func (*Bucket) Delete

func (bk *Bucket) Delete(fp Fingerprint) bool

func (*Bucket) GetFingerprintIndex

func (bk *Bucket) GetFingerprintIndex(fp Fingerprint) int

func (*Bucket) Insert

func (bk *Bucket) Insert(fp Fingerprint) bool

func (*Bucket) Reset

func (bk *Bucket) Reset()

type CuckooFilter

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

CuckooFilter implements the Standard-Cuckoo-Filter mentioned by "Cuckoo Filter: Practically Better Than Bloom".

func Deserialize

func Deserialize(bytes []byte) (*CuckooFilter, error)

Deserialize returns a CuckooFilter from a byte slice.

func NewCuckooFilter

func NewCuckooFilter(cap uint) *CuckooFilter

func (*CuckooFilter) Count

func (cf *CuckooFilter) Count() uint

Count returns the number of items inside CuckooFilter.

func (*CuckooFilter) Delete

func (cf *CuckooFilter) Delete(x string) bool

Delete removes string item from CuckooFilter if exists and return true if deleted or not.

f = fingerprint(x);
i_1 = hash(x);
i_2 = i_1 ⊕ hash(f);
if bucket[i_1] or bucket[i_2] has f then
	remove a copy of f from this bucket;
	return True;
return False;

func (*CuckooFilter) Insert

func (cf *CuckooFilter) Insert(x string) bool

Insert inserts a string item.

f = fingerprint(x);
i_1 = hash(x);
i_2 = i_1 ⊕ hash(f);
if bucket[i_1] or bucket[i_2] has an empty entry then
	add f to that bucket;
return Done;
// must relocate existing items;
i = randomly pick i_1 or i_2;
for n = 0; n < MaxNumKicks; n++ do
	randomly select an entry e from bucket[i];
	swap f and the fingerprint stored in entry e;
	i = i ⊕ hash(f);
	if bucket[i] has an empty entry then
		add f to bucket[i];
		return Done;
// Hashtable is considered full;
return Failure;

func (*CuckooFilter) Lookup

func (cf *CuckooFilter) Lookup(x string) bool

Lookup returns true if string item is inside CuckooFilter.

f = fingerprint(x);
i_1 = hash(x);
i_2 = i_1 ⊕ hash(f);
if bucket[i_1] or bucket[i_2] has f then
	return True;
return False;

func (*CuckooFilter) Reset

func (cf *CuckooFilter) Reset()

Reset removes all items from CuckooFilter.

type Fingerprint

type Fingerprint byte

func GetFingerprint

func GetFingerprint(x string) Fingerprint