Documentation
¶
Index ¶
- Variables
- 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) Hibernated() bool
- 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 ¶
var ( // ErrAllocatorNotHibernated is returned by Serialize() and Deserialize() when the // allocator still holds its in-memory storage. Hibernate() intentionally no-ops for // small or empty allocators, so callers must be able to match this instead of // crashing the whole run. ErrAllocatorNotHibernated = errors.New("(de)serialization requires the hibernated state") )
Functions ¶
func CompressUInt32Slice ¶
CompressUInt32Slice compresses a slice of uint32-s with LZ4.
func DecompressUInt32Slice ¶
DecompressUInt32Slice decompresses a slice of uint32-s previously compressed with CompressUInt32Slice. 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) Deserialize ¶
Deserialize reads a hibernated allocator from disk.
func (*Allocator) Hibernate ¶
func (allocator *Allocator) Hibernate()
Hibernate compresses the allocated memory.
func (*Allocator) Hibernated ¶
Hibernated reports whether the allocator is currently hibernated, i.e. its storage was compressed away. Hibernate() deliberately does nothing for allocators below the hibernation threshold or without any nodes, so callers which need to distinguish those cases (Serialize() requires the hibernated state) have to ask.
func (*Allocator) Serialize ¶
Serialize writes the hibernated allocator on disk. The format is private to Hercules' run-local hibernation files, but still carries a version and per-buffer checksum so truncated or corrupted temporary state is rejected deterministically.
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) 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) NegativeLimit ¶
NegativeLimit checks if the iterator points before the minimum element in the tree.
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 (*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) 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().
func (*RBTree) NegativeLimit ¶
NegativeLimit creates an iterator that points before the minimum item in the tree.
Source Files