ibf

Documentation

Index

• Variables
• type Cell
  • func NewCell() *Cell
  • func (c *Cell) Clone() *Cell
  • func (c *Cell) GetCount() int64
  • func (c *Cell) GetDigest() uint64
  • func (c *Cell) GetKey() []byte
  • func (c *Cell) Insert(key []byte, digest uint64)
  • func (c *Cell) Invert()
  • func (c *Cell) IsEmpty() bool
  • func (c *Cell) IsPure(h *Hash) bool
  • func (c *Cell) Remove(key []byte, digest uint64)
  • func (c *Cell) Subtract(cell *Cell)
  • func (c *Cell) Union(cell *Cell)
• type Hash
  • func NewHash(key0, key1 uint64) *Hash
  • func (h *Hash) Hash(value []byte) (digest uint64)
• type IBF
  • func NewIBF(size uint64, seed int64) *IBF
  • func NewIBFWithHash(size uint64, positioners []*Hash, hasher *Hash) *IBF
  • func (i *IBF) Clone() (clone *IBF)
  • func (i *IBF) GetCardinality() int64
  • func (i *IBF) GetCells() []*Cell
  • func (i *IBF) GetSize() uint64
  • func (i *IBF) Insert(key []byte)
  • func (i *IBF) Invert()
  • func (i *IBF) IsEmpty() bool
  • func (i *IBF) Pop() ([]byte, error)
  • func (i *IBF) Remove(key []byte)
  • func (i *IBF) Subtract(other *IBF)
  • func (i *IBF) Union(other *IBF)

Variables

var (
	Error = errs.Class("ibf")

	ErrNoPureCell = Error.New("no pure cell")
	ErrEmptySet   = Error.New("empty set")
)

Errors for this package.

Types

type Cell

type Cell struct {
	Key    *block `json:"key"`
	Digest uint64 `json:"digest"`
	Count  int64  `json:"count"`
}

Cell contains the state of an individual position in an IBF.

func NewCell

func NewCell() *Cell

NewCell returns a new empty cell.

func (*Cell) Clone

func (c *Cell) Clone() *Cell

Clone returns a deep copy of this cell.

func (*Cell) GetCount

func (c *Cell) GetCount() int64

GetCount returns the cell's count.

func (*Cell) GetDigest

func (c *Cell) GetDigest() uint64

GetDigest returns the cell's digest.

func (*Cell) GetKey

func (c *Cell) GetKey() []byte

GetKey returns a copy of the key.

func (*Cell) Insert

func (c *Cell) Insert(key []byte, digest uint64)

Insert adds the key with the given digest to this cell.

NOTE: This assumes the key does not already exist in the cell. If it does this effectively removes it and the count will be incorrect.

func (*Cell) Invert

func (c *Cell) Invert()

Invert negates the count.

func (*Cell) IsEmpty

func (c *Cell) IsEmpty() bool

IsEmpty returns true if the cell's count is zero, key is empty, and digest is zero.

func (*Cell) IsPure

func (c *Cell) IsPure(h *Hash) bool

IsPure returns true if the cell contains exactly one value and the hash is valid.

func (*Cell) Remove

func (c *Cell) Remove(key []byte, digest uint64)

Remove deletes the key with the given digest from this cell.

NOTE: This assumes the key already exists in the cell. If it does not this effectively adds it and the count will be incorrect.

func (*Cell) Subtract

func (c *Cell) Subtract(cell *Cell)

Subtract removes all keys in the given cell from this one.

NOTE: This assumes given cell is a subset of this one. If it wasn't this effectly performs a symmetric difference and the count will be incorrect.

func (*Cell) Union

func (c *Cell) Union(cell *Cell)

Union adds all keys from the given cell to this one.

NOTE: This assumes cells were disjoint sets. If there weren't this effectly performs a symmetric difference and the count will be incorrect.

type Hash

type Hash struct {
	Key [2]uint64 `json:"key"`
}

Hash maintains the state for a siphash hasher.

func NewHash

func NewHash(key0, key1 uint64) *Hash

NewHash returns a new siphash hasher.

func (*Hash) Hash

func (h *Hash) Hash(value []byte) (digest uint64)

Hash retuns the digest of the value.

type IBF

type IBF struct {
	Positioners []*Hash `json:"positioners"`
	Hasher      *Hash   `json:"hasher"`

	Size  uint64  `json:"size"`
	Cells []*Cell `json:"cells"`

	Cardinality int64 `json:"cardinality"`
}

IBF holds the state of an invertable bloom filter.

func NewIBF

func NewIBF(size uint64, seed int64) *IBF

NewIBF creates a new IBF of the given size. An IBF can accurately handle differences of approximately 2/3rds the configured size (e.g. a size of 100 would allow for ~66 differences to be accurately retrieved). 3 positioners and a hasher are created using the output from a random number generator initialized with the seed.

func NewIBFWithHash

func NewIBFWithHash(size uint64, positioners []*Hash, hasher *Hash) *IBF

NewIBFWithHash creates a new IBF with the provided positioners and hasher. It will use the given hashers for positioning and computing the key hashes. The positioners must all be initialized with different seeds to ensure they do not produce the same positions for the same key.

func (*IBF) Clone

func (i *IBF) Clone() (clone *IBF)

Clone returns a copy of this set.

func (*IBF) GetCardinality

func (i *IBF) GetCardinality() int64

GetCardinality returns the IBF's cardinality.

func (*IBF) GetCells

func (i *IBF) GetCells() []*Cell

GetCells returns the IBF's cells.

func (*IBF) GetSize

func (i *IBF) GetSize() uint64

GetSize returns the IBF's size.

func (*IBF) Insert

func (i *IBF) Insert(key []byte)

Insert adds the key to the set.

NOTE: This does not know if the key already exists and will add it unconditionally. If the key did already exist in the set, then that effectively would remove it!

func (*IBF) Invert

func (i *IBF) Invert()

Invert flips the cardinality of the set and the cells. As if all elements has instead been removed from the set instead of added.

func (*IBF) IsEmpty

func (i *IBF) IsEmpty() bool

IsEmpty returns true if all the cells are empty and the cardinality is zero.

func (*IBF) Pop

func (i *IBF) Pop() ([]byte, error)

Pop finds a key in a pure cell, removes it from the set, and returns it. If no pure cell can be found it returns ErrNoPureCell indicating that there are more elements in the set, but they cannot be popped. If the set is empty it returns ErrEmptySet.

func (*IBF) Remove

func (i *IBF) Remove(key []byte)

Remove deletes the key from the set.

NOTE: This does not know if the key already exists and will add it unconditionally. If the key did already exist in the set, then that effectively would add it!

func (*IBF) Subtract

func (i *IBF) Subtract(other *IBF)

Subtract removes all the elements from the provided set from this set.

NOTE: This assumes the other set is a subset of this one. If that isn't true then this will actually perform a symmetric difference and the cardinality will be incorrect! If the two sets are not configured the same then the behavior is undefined and could potentially panic.

func (*IBF) Union

func (i *IBF) Union(other *IBF)

Union inserts all the elements from the provided set to this set.

NOTE: This assumes the two sets are disjoint and configured the same. If the two sets are not disjoint this will actually perform a symmetric difference and the cardinality will be incorrect! If the two sets are not configured the same then the behavior is undefined and could potentially panic.