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(size int, listSetSize int) *Pool
  • func (p *Pool) Borrow() ListSet
  • func (p *Pool) Destroy()
  • 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 memrory 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 implemtation 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(size int, listSetSize int) *Pool

NewPool creates a new pool with specified size. listSetSize specifies the size of a list at creation time point

func (*Pool) Borrow

func (p *Pool) Borrow() ListSet

Borrow return a free list

func (*Pool) Destroy

func (p *Pool) Destroy()

Destroy and empty 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