insert.go

func (c *CuckooFilter) getCuckooParams(data []byte) (uint, uint, []byte) {
	hash := c.computeHash(data)
	f := hash[0:c.fpSize]
	i1 := uint(binary.BigEndian.Uint32(hash2(hash))) % c.numbuckets
	i2 := (i1 ^ uint(binary.BigEndian.Uint32(hash1(f)))) % c.numbuckets

	return i1, i2, f
}


func (c *CuckooFilter) Insert(data []byte) error {
	i1, i2, f := c.getCuckooParams(data)
	return c.insert(i1, i2, f)
}

func (c *CuckooFilter) insert(i1 uint, i2 uint, f []byte) error {
	// insert into bucket1
	b1 := c.buckets[i1]
	if idx, err := b1.getEmptyEntry(); err == nil {
		b1[idx] = f
		return nil
	}

	// insert into bucket2
	b2 := c.buckets[i2]
	if idx, err := b2.getEmptyEntry(); err == nil {
		b2[idx] = f
		return nil
	}

	// must relocate existing items

	// i = randomly pick i1 or i2;
	// 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]

	i := i1
	for n := 0; n < maxCuckooKicks; n++ {
		// randomly select an entry e from bucket[i];
		rIdx := rand.Intn(len(c.buckets[i]) - 1)
		f, c.buckets[i][rIdx] = c.buckets[i][rIdx], f
		i = (i ^ uint(binary.BigEndian.Uint32(hash2(f)))) % c.numbuckets
		b := c.buckets[i]
		if idx, err := b.getEmptyEntry(); err == nil {
			b[idx] = f
			return nil
		}
	}

	return ERR_FILTER_FULL

}