visited

Documentation

Index

• type ListSet
  • func NewList(size int) ListSet
  • func (l ListSet) Len() int
  • func (l *ListSet) Reset()
  • func (l *ListSet) Visit(node uint64)
  • func (l *ListSet) Visited(node uint64) bool
• type Pool
  • func NewPool(initialSize int, listSetSize int, maxStorage int) *Pool
  • func (p *Pool) Borrow() ListSet
  • func (p *Pool) Destroy()
  • func (p *Pool) Len() int
  • func (p *Pool) Return(l ListSet)

Types

type ListSet

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

ListSet is a reusable list with very efficient resets. Inspired by the C++ implementation in hnswlib it can be reset with zero memory writes in the array by moving the match target instead of altering the list. Only after a version overflow do we need to actually reset

The new implementation uses a slice where the first element is reserved for the marker. This allow us to use ListSet as a value (i.e. no pointer is required) The marker (i.e. set[0]) allows for reusing the same list without having to zero all elements on each list reset. Resetting the list takes place once the marker (i.e. set[0]) overflows

func NewList

func NewList(size int) ListSet

NewList creates a new list. It allocates memory for elements and marker

func (ListSet) Len

func (l ListSet) Len() int

Len returns the number of elements in the list.

func (*ListSet) Reset

func (l *ListSet) Reset()

Reset list only in case of an overflow.

func (*ListSet) Visit

func (l *ListSet) Visit(node uint64)

Visit sets element at node to the marker value

func (*ListSet) Visited

func (l *ListSet) Visited(node uint64) bool

Visited checks if l contains the specified node

type Pool

type Pool struct {
	sync.Mutex
	// contains filtered or unexported fields
}

func NewPool

func NewPool(initialSize int, listSetSize int, maxStorage int) *Pool

NewPool creates a new pool with specified size. listSetSize specifies the size of a list at creation time point maxStorage specifies the maximum number of lists that can be stored in the pool, the pool can still generate infinite lists, but if more than maxStorage are returned to the pool, some lists will be thrown away.

func (*Pool) Borrow

func (p *Pool) Borrow() ListSet

Borrow a list from the pool. If the pool is empty, a new list is craeted. If an old list is used, it is guaranteed to be reset – as that was performed on return.

func (*Pool) Destroy

func (p *Pool) Destroy()

Destroy and empty pool

func (*Pool) Len

func (p *Pool) Len() int

Len returns the number of lists currently in the pool

func (*Pool) Return

func (p *Pool) Return(l ListSet)

Return list l to the pool The list l might be thrown if l.Len() > listSetSize*1.10 or if the pool is full.