radix

Documentation

Index

• type Item
• type IterFunc
• type Key
  • func (k Key) Key() uint64
• type Tree
  • func (t *Tree) Ascend(iter IterFunc)
  • func (t *Tree) AscendGreaterOrEqual(item Item, iter IterFunc)
  • func (t *Tree) AscendGreaterOrEqualI(key uint64, iter IterFunc)
  • func (t *Tree) Clear()
  • func (t *Tree) Delete(key Item) Item
  • func (t *Tree) DeleteI(key uint64) Item
  • func (t *Tree) Descend(iter IterFunc)
  • func (t *Tree) DescendLessOrEqual(item Item, iter IterFunc)
  • func (t *Tree) DescendLessOrEqualI(key uint64, iter IterFunc)
  • func (t *Tree) Get(key Item) Item
  • func (t *Tree) GetI(key uint64) Item
  • func (t *Tree) Len() int
  • func (t *Tree) Max() Item
  • func (t *Tree) Min() Item
  • func (t *Tree) ReplaceOrInsert(item Item) Item

Types

type Item

type Item interface {
	Key() uint64
}

Item represents a single object in the tree, with a uint64 key.

type IterFunc

type IterFunc func(Item) bool

IterFunc allows callers to iterate over the tree with Ascend/Descend* functions. Iteration will stop when this function returns false.

type Key

type Key uint64

func (Key) Key

func (k Key) Key() uint64

type Tree

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

Tree implements a radix tree (https://en.wikipedia.org/wiki/Radix_tree) with uint64 keys. This implementation is intended to be cache-efficient, minimising the number of cache line accesses (and hence misses).

The API follows google.BTree, with the exception that the Item interface provides a uint64 key instead of a Less() function.

The zero-value Tree is ready to use.

NOTE: Only a subset of functions have been implemented.

func (*Tree) Ascend

func (t *Tree) Ascend(iter IterFunc)

func (*Tree) AscendGreaterOrEqual

func (t *Tree) AscendGreaterOrEqual(item Item, iter IterFunc)

func (*Tree) AscendGreaterOrEqualI

func (t *Tree) AscendGreaterOrEqualI(key uint64, iter IterFunc)

func (*Tree) Clear

func (t *Tree) Clear()

func (*Tree) Delete

func (t *Tree) Delete(key Item) Item

func (*Tree) DeleteI

func (t *Tree) DeleteI(key uint64) Item

func (*Tree) Descend

func (t *Tree) Descend(iter IterFunc)

func (*Tree) DescendLessOrEqual

func (t *Tree) DescendLessOrEqual(item Item, iter IterFunc)

func (*Tree) DescendLessOrEqualI

func (t *Tree) DescendLessOrEqualI(key uint64, iter IterFunc)

func (*Tree) Get

func (t *Tree) Get(key Item) Item

func (*Tree) GetI

func (t *Tree) GetI(key uint64) Item

func (*Tree) Len

func (t *Tree) Len() int

func (*Tree) Max

func (t *Tree) Max() Item

func (*Tree) Min

func (t *Tree) Min() Item

func (*Tree) ReplaceOrInsert

func (t *Tree) ReplaceOrInsert(item Item) Item