Documentation
¶
Index ¶
- func CompressUInt32Slice(data []uint32) []byte
- func DecompressUInt32Slice(data []byte, result []uint32)
- type Allocator
- func (allocator *Allocator) Boot()
- func (allocator Allocator) Clone() *Allocator
- func (allocator *Allocator) Deserialize(path string) error
- func (allocator *Allocator) Hibernate()
- func (allocator *Allocator) Serialize(path string) error
- func (allocator Allocator) Size() int
- func (allocator Allocator) Used() int
- type Item
- type Iterator
- type RBTree
- func (tree RBTree) Allocator() *Allocator
- func (tree RBTree) CloneDeep(allocator *Allocator) *RBTree
- func (tree RBTree) CloneShallow(allocator *Allocator) *RBTree
- func (tree *RBTree) DeleteWithIterator(iter Iterator)
- func (tree *RBTree) DeleteWithKey(key uint32) bool
- func (tree *RBTree) Erase()
- func (tree *RBTree) FindGE(key uint32) Iterator
- func (tree *RBTree) FindLE(key uint32) Iterator
- func (tree RBTree) Get(key uint32) *uint32
- func (tree *RBTree) Insert(item Item) (bool, Iterator)
- func (tree RBTree) Len() int
- func (tree *RBTree) Limit() Iterator
- func (tree *RBTree) Max() Iterator
- func (tree *RBTree) Min() Iterator
- func (tree *RBTree) NegativeLimit() Iterator
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func CompressUInt32Slice ¶
CompressUInt32Slice compresses a slice of uint32-s with LZ4.
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 ¶
Clone copies an existing RBTree allocator.
func (*Allocator) Deserialize ¶
Deserialize reads a hibernated allocator from disk.
func (*Allocator) Hibernate ¶
func (allocator *Allocator) Hibernate()
Hibernate compresses the allocated memory.
func (*Allocator) Serialize ¶
Serialize writes the hibernated allocator on disk.
func (Allocator) Size ¶
Size returns the currently allocated size.
type Item ¶
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 ¶
Equal checks for the underlying nodes equality.
func (Iterator) 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 ¶
Limit checks if the iterator points beyond the max element in the tree.
func (Iterator) Max ¶
Max checks if the iterator points to the maximum element in the tree.
func (Iterator) Min ¶
Min checks if the iterator points to the minimum element in the tree.
func (Iterator) NegativeLimit ¶
NegativeLimit checks if the iterator points before the minimum element in the tree.
func (Iterator) Next ¶
Next creates a new iterator that points to the successor of the current element.
REQUIRES: !iter.Limit()
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 ¶
NewRBTree creates a new red-black binary tree.
func (RBTree) Allocator ¶
Allocator returns the bound nodes allocator.
func (RBTree) CloneDeep ¶
CloneDeep performs a deep copy of the tree - the nodes are created from scratch.
func (RBTree) CloneShallow ¶
CloneShallow performs a shallow copy of the tree - the nodes are assumed to already exist in the allocator.
func (*RBTree) DeleteWithIterator ¶
DeleteWithIterator deletes the current item.
REQUIRES: !iter.Limit() && !iter.NegativeLimit()
func (*RBTree) DeleteWithKey ¶
DeleteWithKey deletes an item with the given Key. Returns true iff the item was found.
func (*RBTree) FindGE ¶
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 ¶
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 ¶
Get is a convenience function for finding an element equal to Key. Returns nil if not found.
func (*RBTree) Insert ¶
Insert an item. If the item is already in the tree, do nothing and return false. Else return true.
func (*RBTree) Limit ¶
Limit creates an iterator that points beyond the maximum item in the tree.
func (*RBTree) Max ¶
Max creates an iterator that points at the maximum item in the tree.
If the tree is empty, returns NegativeLimit().
func (*RBTree) Min ¶
Min creates an iterator that points to the minimum item in the tree. If the tree is empty, returns Limit()
Source Files