rbtree

package
v10.7.2 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Jan 14, 2020 License: Apache-2.0 Imports: 8 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func CompressUInt32Slice

func CompressUInt32Slice(data []uint32) []byte

CompressUInt32Slice compresses a slice of uint32-s with LZ4.

func DecompressUInt32Slice

func DecompressUInt32Slice(data []byte, result []uint32)

DecompressUInt32Slice decompresses a slice of uint32-s previously compressed with LZ4. `result` must be preallocated.

Types

type Allocator

type Allocator struct {
	HibernationThreshold int
	// contains filtered or unexported fields
}

Allocator is the allocator for nodes in a RBTree.

func NewAllocator

func NewAllocator() *Allocator

NewAllocator creates a new allocator for RBTree's nodes.

func (*Allocator) Boot

func (allocator *Allocator) Boot()

Boot performs the opposite of Hibernate() - decompresses and restores the allocated memory.

func (Allocator) Clone

func (allocator Allocator) Clone() *Allocator

Clone copies an existing RBTree allocator.

func (*Allocator) Deserialize

func (allocator *Allocator) Deserialize(path string) error

Deserialize reads a hibernated allocator from disk.

func (*Allocator) Hibernate

func (allocator *Allocator) Hibernate()

Hibernate compresses the allocated memory.

func (*Allocator) Serialize

func (allocator *Allocator) Serialize(path string) error

Serialize writes the hibernated allocator on disk.

func (Allocator) Size

func (allocator Allocator) Size() int

Size returns the currently allocated size.

func (Allocator) Used

func (allocator Allocator) Used() int

Used returns the number of nodes contained in the allocator.

type Item

type Item struct {
	Key   uint32
	Value uint32
}

Item is the object stored in each tree node.

type Iterator

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

Iterator allows scanning tree elements in sort order.

Iterator invalidation rule is the same as C++ std::map<>'s. That is, if you delete the element that an iterator points to, the iterator becomes invalid. For other operation types, the iterator remains valid.

func (Iterator) Equal

func (iter Iterator) Equal(other Iterator) bool

Equal checks for the underlying nodes equality.

func (Iterator) Item

func (iter Iterator) Item() *Item

Item returns the current element. Allows mutating the node (key to be changed with care!).

The result is nil if iter.Limit() || iter.NegativeLimit().

func (Iterator) Limit

func (iter Iterator) Limit() bool

Limit checks if the iterator points beyond the max element in the tree.

func (Iterator) Max

func (iter Iterator) Max() bool

Max checks if the iterator points to the maximum element in the tree.

func (Iterator) Min

func (iter Iterator) Min() bool

Min checks if the iterator points to the minimum element in the tree.

func (Iterator) NegativeLimit

func (iter Iterator) NegativeLimit() bool

NegativeLimit checks if the iterator points before the minimum element in the tree.

func (Iterator) Next

func (iter Iterator) Next() Iterator

Next creates a new iterator that points to the successor of the current element.

REQUIRES: !iter.Limit()

func (Iterator) Prev

func (iter Iterator) Prev() Iterator

Prev creates a new iterator that points to the predecessor of the current node.

REQUIRES: !iter.NegativeLimit()

type RBTree

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

RBTree is a red-black tree with an API similar to C++ STL's.

The implementation is inspired (read: stolen) from: http://en.literateprograms.org/Red-black_tree_(C)#chunk use:private function prototypes.

The code was optimized for the simple integer types of Key and Value. The code was further optimized for using allocators. Credits: Yaz Saito.

func NewRBTree

func NewRBTree(allocator *Allocator) *RBTree

NewRBTree creates a new red-black binary tree.

func (RBTree) Allocator

func (tree RBTree) Allocator() *Allocator

Allocator returns the bound nodes allocator.

func (RBTree) CloneDeep

func (tree RBTree) CloneDeep(allocator *Allocator) *RBTree

CloneDeep performs a deep copy of the tree - the nodes are created from scratch.

func (RBTree) CloneShallow

func (tree RBTree) CloneShallow(allocator *Allocator) *RBTree

CloneShallow performs a shallow copy of the tree - the nodes are assumed to already exist in the allocator.

func (*RBTree) DeleteWithIterator

func (tree *RBTree) DeleteWithIterator(iter Iterator)

DeleteWithIterator deletes the current item.

REQUIRES: !iter.Limit() && !iter.NegativeLimit()

func (*RBTree) DeleteWithKey

func (tree *RBTree) DeleteWithKey(key uint32) bool

DeleteWithKey deletes an item with the given Key. Returns true iff the item was found.

func (*RBTree) Erase

func (tree *RBTree) Erase()

Erase removes all the nodes from the tree.

func (*RBTree) FindGE

func (tree *RBTree) FindGE(key uint32) Iterator

FindGE finds the smallest element N such that N >= Key, and returns the iterator pointing to the element. If no such element is found, returns tree.Limit().

func (*RBTree) FindLE

func (tree *RBTree) FindLE(key uint32) Iterator

FindLE finds the largest element N such that N <= Key, and returns the iterator pointing to the element. If no such element is found, returns iter.NegativeLimit().

func (RBTree) Get

func (tree RBTree) Get(key uint32) *uint32

Get is a convenience function for finding an element equal to Key. Returns nil if not found.

func (*RBTree) Insert

func (tree *RBTree) Insert(item Item) (bool, Iterator)

Insert an item. If the item is already in the tree, do nothing and return false. Else return true.

func (RBTree) Len

func (tree RBTree) Len() int

Len returns the number of elements in the tree.

func (*RBTree) Limit

func (tree *RBTree) Limit() Iterator

Limit creates an iterator that points beyond the maximum item in the tree.

func (*RBTree) Max

func (tree *RBTree) Max() Iterator

Max creates an iterator that points at the maximum item in the tree.

If the tree is empty, returns NegativeLimit().

func (*RBTree) Min

func (tree *RBTree) Min() Iterator

Min creates an iterator that points to the minimum item in the tree. If the tree is empty, returns Limit()

func (*RBTree) NegativeLimit

func (tree *RBTree) NegativeLimit() Iterator

NegativeLimit creates an iterator that points before the minimum item in the tree.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL