numtree

Documentation

Overview

Package numtree implements radix tree data structure for 32 and 64-bit unsigned integets. Copy-on-write is used for any tree modification so old root doesn't see any change happens with tree.

Index

• Constants
• type Node32
  • func (n *Node32) Children() (*Node32, *Node32)
  • func (n *Node32) Delete(key uint32, bits int) (*Node32, bool)
  • func (n *Node32) Dot() string
  • func (n *Node32) Enumerate() chan *Node32
  • func (n *Node32) ExactMatch(key uint32, bits int) (interface{}, bool)
  • func (n *Node32) FindNode(key uint32, bits int) *Node32
  • func (n *Node32) InplaceInsert(key uint32, bits int, value interface{}) *Node32
  • func (n *Node32) Insert(key uint32, bits int, value interface{}) *Node32
  • func (n *Node32) Match(key uint32, bits int) (interface{}, bool)
• type Node64
  • func (n *Node64) Children() (*Node64, *Node64)
  • func (n *Node64) Delete(key uint64, bits int) (*Node64, bool)
  • func (n *Node64) Dot() string
  • func (n *Node64) Enumerate() chan *Node64
  • func (n *Node64) ExactMatch(key uint64, bits int) (interface{}, bool)
  • func (n *Node64) FindNode(key uint64, bits int) *Node64
  • func (n *Node64) InplaceInsert(key uint64, bits int, value interface{}) *Node64
  • func (n *Node64) Insert(key uint64, bits int, value interface{}) *Node64
  • func (n *Node64) Match(key uint64, bits int) (interface{}, bool)

Constants

const Key32BitSize = 32

Key32BitSize is an alias for bitsize of 32-bit radix tree's key.

const Key64BitSize = 64

Key64BitSize is an alias for bitsize of 64-bit radix tree's key.

Types

type Node32

type Node32 struct {
	// Key stores key for current node.
	Key uint32
	// Bits is a number of significant bits in Key.
	Bits uint8
	// Leaf indicates if the node is leaf node and contains any data in Value.
	Leaf bool
	// Value contains data associated with key.
	Value interface{}
	// contains filtered or unexported fields
}

Node32 is an element of radix tree with 32-bit unsigned integer as a key.

func (*Node32) Children

func (n *Node32) Children() (*Node32, *Node32)

func (*Node32) Delete

func (n *Node32) Delete(key uint32, bits int) (*Node32, bool)

Delete removes subtree which is contained by given key. The method uses copy on write strategy.

func (*Node32) Dot

func (n *Node32) Dot() string

Dot dumps tree to Graphviz .dot format

func (*Node32) Enumerate

func (n *Node32) Enumerate() chan *Node32

Enumerate returns channel which is populated by nodes with data in order of their keys.

func (*Node32) ExactMatch

func (n *Node32) ExactMatch(key uint32, bits int) (interface{}, bool)

ExactMatch locates node which exactly matches given key.

func (*Node32) FindNode

func (n *Node32) FindNode(key uint32, bits int) *Node32

func (*Node32) InplaceInsert

func (n *Node32) InplaceInsert(key uint32, bits int, value interface{}) *Node32

InplaceInsert puts new leaf to radix tree (or replaces value in existing one). The method inserts data directly to current tree so make sure you have exclusive access to it.

func (*Node32) Insert

func (n *Node32) Insert(key uint32, bits int, value interface{}) *Node32

Insert puts new leaf to radix tree and returns pointer to new root. The method uses copy on write strategy so old root doesn't see the change.

func (*Node32) Match

func (n *Node32) Match(key uint32, bits int) (interface{}, bool)

Match locates node which key is equal to or "contains" the key passed as argument.

type Node64

type Node64 struct {
	// Key stores key for current node.
	Key uint64
	// Bits is a number of significant bits in Key.
	Bits uint8
	// Leaf indicates if the node is leaf node and contains any data in Value.
	Leaf bool
	// Value contains data associated with key.
	Value interface{}
	// contains filtered or unexported fields
}

Node64 is an element of radix tree with 64-bit unsigned integer as a key.

func (*Node64) Children

func (n *Node64) Children() (*Node64, *Node64)

func (*Node64) Delete

func (n *Node64) Delete(key uint64, bits int) (*Node64, bool)

Delete removes subtree which is contained by given key. The method uses copy on write strategy.

func (*Node64) Dot

func (n *Node64) Dot() string

Dot dumps tree to Graphviz .dot format

func (*Node64) Enumerate

func (n *Node64) Enumerate() chan *Node64

Enumerate returns channel which is populated by nodes in order of their keys.

func (*Node64) ExactMatch

func (n *Node64) ExactMatch(key uint64, bits int) (interface{}, bool)

ExactMatch locates node which exactly matches given key.

func (*Node64) FindNode

func (n *Node64) FindNode(key uint64, bits int) *Node64

func (*Node64) InplaceInsert

func (n *Node64) InplaceInsert(key uint64, bits int, value interface{}) *Node64

InplaceInsert puts new leaf to radix tree (or replaces value in existing one). The method inserts data directly to current tree so make sure you have exclusive access to it.

func (*Node64) Insert

func (n *Node64) Insert(key uint64, bits int, value interface{}) *Node64

Insert puts new leaf to radix tree and returns pointer to new root. The method uses copy on write strategy so old root doesn't see the change.

func (*Node64) Match

func (n *Node64) Match(key uint64, bits int) (interface{}, bool)

Match locates node which key is equal to or "contains" the key passed as argument.