cuckoo

Documentation

Index

• Constants
• type Item
  • func (i Item) Copy() *Item
  • func (i *Item) Equals(other *Item) bool
• type ItemLocation
• type Table
  • func NewTable(name string, numBuckets uint64, bucketDepth uint64, itemSize uint64, ...) *Table
  • func (t *Table) Bucket(item *Item) (uint64, error)
  • func (t *Table) Contains(item *Item) bool
  • func (t *Table) GetCapacity() uint64
  • func (t *Table) GetNumElements() uint64
  • func (t *Table) Insert(item *Item) (bool, *Item)
  • func (t *Table) Remove(item *Item) bool

Constants

const MaxEvictions int = 500

MaxEvictions represents the number of chained evictions before an insert attempt fails.

Types

type Item

type Item struct {
	ID      uint64
	Data    []byte
	Bucket1 uint64
	Bucket2 uint64
}

Item holds a full item data for cuckoo table placement.

func (Item) Copy

func (i Item) Copy() *Item

Copy duplicates an Item.

func (*Item) Equals

func (i *Item) Equals(other *Item) bool

Equals compares item equality.

type ItemLocation

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

ItemLocation holds metadata for item placement in a cuckoo table.

type Table

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

Table is a cuckoo table managing placement of Items, where the data is a byte array.

func NewTable

func NewTable(name string, numBuckets uint64, bucketDepth uint64, itemSize uint64,
	data []byte, randSeed int64) *Table

NewTable creates a new cuckoo table optionaly backed by a pre-allocated memory area. Two cuckoo tables will have identical state iff, 1. the same randSeed is used 2. the same operations are applied in the same order numBuckets = number of buckets depth = the number of entries per bucket randSeed = seed for PRNG

func (*Table) Bucket

func (t *Table) Bucket(item *Item) (uint64, error)

Bucket returns the bucket in a table that the Item is in, if it is in the table. an invalid bucket number and an error, otherwise

func (*Table) Contains

func (t *Table) Contains(item *Item) bool

Contains checks if value exists in specified buckets the value must have been inserted with the same bucket1 and bucket2 values Returns: - true if the item is in either bucket - false if either bucket is out of range - false if value not in either bucket

func (*Table) GetCapacity

func (t *Table) GetCapacity() uint64

GetCapacity returns the total capacity of the table (numBuckets * depth)

func (*Table) GetNumElements

func (t *Table) GetNumElements() uint64

GetNumElements returns the number of elements stored in the table Load factor = GetNumElements() / GetCapacity()

func (*Table) Insert

func (t *Table) Insert(item *Item) (bool, *Item)

Insert adds item into the cuckoo table, even if a duplicate value already exists in table. Returns: - true on success, false on failure - false if item.Data is not equal to t.itemSize - false if either bucket is out of range - false if insertion cannot complete because reached MAX_EVICTIONS

func (*Table) Remove

func (t *Table) Remove(item *Item) bool

Remove deletes item from the cuckoo table, looking in only 2 specified buckets Only matches if the value was previously inserted with the same {bucket1, bucket2} values If the incorrect buckets were specified, it won't go searching for you If the value exists in the table multiple times, it will only remove one Returns: - true if a value was removed from either bucket, false if not - fails if either bucket is out of range