yfast

Documentation

Overview

Package yfast implements a y-fast trie. Instead of a red-black BBST for the leaves, this implementation uses a simple ordered list. This package should have searches that are as performant as the x-fast trie while having faster inserts/deletes and linear space consumption.

Performance characteristics: Space: O(n) Get: O(log log M) Search: O(log log M) Insert: O(log log M) Delete: O(log log M)

where n is the number of items in the trie and M is the size of the universe, ie, 2^m where m is the number of bits in the specified key size.

This particular implementation also uses fixed bucket sizes as this should aid in multithreading these functions for performance optimization.

Index

• type Entries
• type Entry
• type Iterator
  • func (iter *Iterator) Next() bool
  • func (iter *Iterator) Value() Entry
• type YFastTrie
  • func New(ifc interface{}) *YFastTrie
  • func (yfast *YFastTrie) Delete(keys ...uint64) Entries
  • func (yfast *YFastTrie) Get(key uint64) Entry
  • func (yfast *YFastTrie) Insert(entries ...Entry) Entries
  • func (yfast *YFastTrie) Iter(key uint64) *Iterator
  • func (yfast *YFastTrie) Len() uint64
  • func (yfast *YFastTrie) Predecessor(key uint64) Entry
  • func (yfast *YFastTrie) Successor(key uint64) Entry

Types

type Entries

type Entries []Entry

Entries is a typed list of Entry. The size of entries will be limited to 1/2log M to 2log M where M is the size of the universe.

type Entry

type Entry interface {
	// Key is the key for this entry.  If the trie has been
	// given bit size n, only the last n bits of this key
	// will matter.  Use a bit size of 64 to enable all
	// 2^64-1 keys.
	Key() uint64
}

Entry defines items that can be inserted into the y-fast trie.

type Iterator

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

Iterator will iterate of the results of a query.

func (*Iterator) Next

func (iter *Iterator) Next() bool

Next will return a bool indicating if another value exists in the iterator.

func (*Iterator) Value

func (iter *Iterator) Value() Entry

Value will return the Entry representing the iterator's current position. If no Entry exists at the present condition, the iterator is exhausted and this method will return nil.

type YFastTrie

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

YFastTrie implements all the methods available to the y-fast trie datastructure. The top half is composed of an x-fast trie while the leaves are composed of ordered lists of type Entry, an interface found in this package.

func New

func New(ifc interface{}) *YFastTrie

New constructs, initializes, and returns a new y-fast trie. Provided should be a uint type that specifies the number of bits in the desired universe. This will affect the time complexity of all lookup and mutate operations.

func (*YFastTrie) Delete

func (yfast *YFastTrie) Delete(keys ...uint64) Entries

Delete will delete the provided keys from the y-fast trie and return a list of entries that were deleted.

func (*YFastTrie) Get

func (yfast *YFastTrie) Get(key uint64) Entry

Get will look for the provided key in the y-fast trie and return the associated value if it is found. If it is not found, this method returns nil.

func (*YFastTrie) Insert

func (yfast *YFastTrie) Insert(entries ...Entry) Entries

Insert will insert the provided entries into the y-fast trie and return a list of entries that were overwritten.

func (*YFastTrie) Iter

func (yfast *YFastTrie) Iter(key uint64) *Iterator

Iter will return an iterator that will iterate across all values that start or immediately proceed the provided key. Iteration happens in ascending order.

func (*YFastTrie) Len

func (yfast *YFastTrie) Len() uint64

Len returns the number of items in the y-fast trie.

func (*YFastTrie) Predecessor

func (yfast *YFastTrie) Predecessor(key uint64) Entry

Predecessor returns an Entry with a key equal to or immediately preceeding than the provided key. If such an Entry does not exist this returns nil.

func (*YFastTrie) Successor

func (yfast *YFastTrie) Successor(key uint64) Entry

Successor returns an Entry with a key equal to or immediately greater than the provided key. If such an Entry does not exist this returns nil.