hercules.v9: gopkg.in/src-d/hercules.v9/internal/rbtree Index | Files

package rbtree

import "gopkg.in/src-d/hercules.v9/internal/rbtree"

Index

Package Files

lz4.go rbtree.go

func CompressUInt32Slice Uses

func CompressUInt32Slice(data []uint32) []byte

CompressUInt32Slice compresses a slice of uint32-s with LZ4.

func DecompressUInt32Slice Uses

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

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

type Allocator Uses

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

Allocator is the allocator for nodes in a RBTree.

func NewAllocator Uses

func NewAllocator() *Allocator

NewAllocator creates a new allocator for RBTree's nodes.

func (*Allocator) Boot Uses

func (allocator *Allocator) Boot()

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

func (Allocator) Clone Uses

func (allocator Allocator) Clone() *Allocator

Clone copies an existing RBTree allocator.

func (*Allocator) Deserialize Uses

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

Deserialize reads a hibernated allocator from disk.

func (*Allocator) Hibernate Uses

func (allocator *Allocator) Hibernate()

Hibernate compresses the allocated memory.

func (*Allocator) Serialize Uses

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

Serialize writes the hibernated allocator on disk.

func (Allocator) Size Uses

func (allocator Allocator) Size() int

Size returns the currently allocated size.

func (Allocator) Used Uses

func (allocator Allocator) Used() int

Used returns the number of nodes contained in the allocator.

type Item Uses

type Item struct {
    Key   uint32
    Value uint32
}

Item is the object stored in each tree node.

type Iterator Uses

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 Uses

func (iter Iterator) Equal(other Iterator) bool

Equal checks for the underlying nodes equality.

func (Iterator) Item Uses

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 Uses

func (iter Iterator) Limit() bool

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

func (Iterator) Max Uses

func (iter Iterator) Max() bool

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

func (Iterator) Min Uses

func (iter Iterator) Min() bool

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

func (Iterator) NegativeLimit Uses

func (iter Iterator) NegativeLimit() bool

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

func (Iterator) Next Uses

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 Uses

func (iter Iterator) Prev() Iterator

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

REQUIRES: !iter.NegativeLimit()

type RBTree Uses

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 Uses

func NewRBTree(allocator *Allocator) *RBTree

NewRBTree creates a new red-black binary tree.

func (RBTree) Allocator Uses

func (tree RBTree) Allocator() *Allocator

Allocator returns the bound nodes allocator.

func (RBTree) CloneDeep Uses

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

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

func (RBTree) CloneShallow Uses

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 Uses

func (tree *RBTree) DeleteWithIterator(iter Iterator)

DeleteWithIterator deletes the current item.

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

func (*RBTree) DeleteWithKey Uses

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 Uses

func (tree *RBTree) Erase()

Erase removes all the nodes from the tree.

func (*RBTree) FindGE Uses

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 Uses

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 Uses

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 Uses

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 Uses

func (tree RBTree) Len() int

Len returns the number of elements in the tree.

func (*RBTree) Limit Uses

func (tree *RBTree) Limit() Iterator

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

func (*RBTree) Max Uses

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 Uses

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 Uses

func (tree *RBTree) NegativeLimit() Iterator

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

Package rbtree imports 8 packages (graph) and is imported by 2 packages. Updated 2019-04-30. Refresh now. Tools for package owners.