art

package
v1.34.28 Latest Latest
Warning

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

 Go to latest Published: Jan 12, 2026 License: BSD-3-Clause Imports: 22 Imported by: 0

Documentation

Index

Constants

View Source 
const (
	XTypBytes int = 0
)

Variables

View Source 
var ArtTreeSaverMagic string = "art.ArtTreeSaverMagic:"

Functions

func Ascend 

func Ascend(t *Tree, beg, endx Key) iter.Seq2[Key, *Leaf]

Ascend wraps a tree.Iter() iteration in ascending lexicographic (shortlex) order. See the Tree.Iter description for details.

func Descend 

func Descend(t *Tree, endx, start Key) iter.Seq2[Key, *Leaf]

Descend iterates from highest to lowest key in lexicographic (shortlex) order. Perhaps counter-intuitively, the smaller (endx) key is always the first argument. "Smallest-first" is an easy way to remember this, as it applies to both directions. Descend is a simple wrapper around the RevIter method. In reverse iteration, the range covered is (endx, start], so the endx key itself will not be seen. Use Descend(nil, nil) to see all keys in the tree.

Types

type ByteSlice 

type ByteSlice []byte

ByteSlice is an alias for []byte. It can be ignored in the uart Unserserialized ART project, as it is only used for serialization purposes elsewhere.

ByteSlice is a simple wrapper header on all msgpack messages; has the length and the bytes. Allows us length delimited messages; with length knowledge up front.

func (*ByteSlice) DecodeMsg 

func (z *ByteSlice) DecodeMsg(dc *msgp.Reader) (err error)

DecodeMsg implements msgp.Decodable We treat empty fields as if we read a Nil from the wire.

func (ByteSlice) EncodeMsg 

func (z ByteSlice) EncodeMsg(en *msgp.Writer) (err error)

EncodeMsg implements msgp.Encodable

func (ByteSlice) MarshalMsg 

func (z ByteSlice) MarshalMsg(b []byte) (o []byte, err error)

MarshalMsg implements msgp.Marshaler

func (ByteSlice) Msgsize 

func (z ByteSlice) Msgsize() (s int)

Msgsize returns an upper bound estimate of the number of bytes occupied by the serialized message

func (*ByteSlice) UnmarshalMsg 

func (z *ByteSlice) UnmarshalMsg(bts []byte) (o []byte, err error)

UnmarshalMsg implements msgp.Unmarshaler

func (*ByteSlice) UnmarshalMsgWithCfg 

func (z *ByteSlice) UnmarshalMsgWithCfg(bts []byte, cfg *msgp.RuntimeConfig) (o []byte, err error)

type ByteSliceValue 

type ByteSliceValue []byte

used by tests; kind of a default value type.

func (*ByteSliceValue) DecodeMsg 

func (z *ByteSliceValue) DecodeMsg(dc *msgp.Reader) (err error)

DecodeMsg implements msgp.Decodable We treat empty fields as if we read a Nil from the wire.

func (ByteSliceValue) EncodeMsg 

func (z ByteSliceValue) EncodeMsg(en *msgp.Writer) (err error)

EncodeMsg implements msgp.Encodable

func (ByteSliceValue) MarshalMsg 

func (z ByteSliceValue) MarshalMsg(b []byte) (o []byte, err error)

MarshalMsg implements msgp.Marshaler

func (ByteSliceValue) Msgsize 

func (z ByteSliceValue) Msgsize() (s int)

Msgsize returns an upper bound estimate of the number of bytes occupied by the serialized message

func (*ByteSliceValue) UnmarshalMsg 

func (z *ByteSliceValue) UnmarshalMsg(bts []byte) (o []byte, err error)

UnmarshalMsg implements msgp.Unmarshaler

func (*ByteSliceValue) UnmarshalMsgWithCfg 

func (z *ByteSliceValue) UnmarshalMsgWithCfg(bts []byte, cfg *msgp.RuntimeConfig) (o []byte, err error)

type Green 

type Green interface {
	//msgp.Encodable // maybe comment out later.
	msgp.Encodable
	msgp.Decodable
	msgp.Marshaler
	msgp.Unmarshaler
}

type Iterator 

type Iterator interface {

	// Next() must be called to start the iteration before
	// Key(), Value(), or Leaf() will be meaningful.
	//
	// Next will iterate over all leaf nodes in
	// the specified range in the chosen direction.
	//
	// When the iteration is done, Next returns false.
	//
	// If the tree is modified between calls to Next,
	// a version change will be recognized, and
	// Next will transparently resume iteration
	// from the successor to the last returned key.
	Next() (ok bool)

	// Leaf returns the current leaf in
	// the iterator after the first successful
	// Next() call.
	Leaf() *Leaf

	// Value returns the current value of
	// the iterator after the first successful
	// Next() call. This is the same as Leaf().Value
	Value() []byte

	// Index returns the current integer index of
	// the iterator after the first successful
	// Next() call.
	Index() int

	// Key returns the current key of
	// the iterator after the first successful
	// Next() call.
	//
	// Warning: the user must not modify
	// this returned key! The tree depends on
	// its value for correctness. Make a copy
	// before modifying the copy. To change
	// a key in the tree, call tree.Remove(old)
	// and then tree.Insert(new) with the new key.
	Key() Key
}

An Iterator will scan the tree in lexicographic (shortlex) order. See the Iter() and RevIter() methods on Tree.

type Key 

type Key []byte

Key is the []byte which the tree sorts in lexicographic (shortlex) order, which means that shorter keys sort before longer keys with the same prefix.

Key is an arbitrary string of bytes, and in particular can contain the 0 byte anywhere in the slice.

func (Key) At 

func (key Key) At(pos int) byte

At() returns the char at key[pos], or a 0 if out of bounds.

func (*Key) DecodeMsg 

func (z *Key) DecodeMsg(dc *msgp.Reader) (err error)

DecodeMsg implements msgp.Decodable We treat empty fields as if we read a Nil from the wire.

func (Key) EncodeMsg 

func (z Key) EncodeMsg(en *msgp.Writer) (err error)

EncodeMsg implements msgp.Encodable

func (Key) MarshalMsg 

func (z Key) MarshalMsg(b []byte) (o []byte, err error)

MarshalMsg implements msgp.Marshaler

func (Key) Msgsize 

func (z Key) Msgsize() (s int)

Msgsize returns an upper bound estimate of the number of bytes occupied by the serialized message

func (*Key) UnmarshalMsg 

func (z *Key) UnmarshalMsg(bts []byte) (o []byte, err error)

UnmarshalMsg implements msgp.Unmarshaler

func (*Key) UnmarshalMsgWithCfg 

func (z *Key) UnmarshalMsgWithCfg(bts []byte, cfg *msgp.RuntimeConfig) (o []byte, err error)

type Leaf 

type Leaf struct {
	Key   Key    `zid:"0"`
	Value []byte `zid:"1"`

	// version for CAS on version support
	Version int64 `zid:"2"`

	// optional type/description of the type of Value.
	Vtype string `zid:"3"`

	// optional metadata
	Leasor            string    `zid:"4"`
	LeaseUntilTm      time.Time `zid:"5"`
	WriteRaftLogIndex int64     `zid:"6"`
	LeaseEpoch        int64     `zid:"7"`

	// if lease goes stale then move this to the /dead table.
	AutoDelete bool `zid:"8"`
	// contains filtered or unexported fields
}

Leaf holds a Key and a Value together, and is stored in the Tree.

Users must take care not to modify the Key on any leaf still in the tree (for example, the leaf returned from a Find() call), since it is used internally in the sorted order that the Tree maintains. The leaf must "own" its Key bytes, and the the user must copy them if they want to make changes.

The leaf returned from Remove can be modified in any way desired, as it is no longer in the tree.

In contrast, users should feel free to update the leaf.Value on any leaf. This can be much more efficient than doing an insert to update a Key's value if the leaf is already in hand.

func NewLeaf 

func NewLeaf(key Key, v []byte, vtype string) *Leaf

func (*Leaf) Clone added in v1.32.23 

func (s *Leaf) Clone() (r *Leaf)

func (*Leaf) DecodeMsg 

func (z *Leaf) DecodeMsg(dc *msgp.Reader) (err error)

DecodeMsg implements msgp.Decodable We treat empty fields as if we read a Nil from the wire.

func (*Leaf) EncodeMsg 

func (z *Leaf) EncodeMsg(en *msgp.Writer) (err error)

EncodeMsg implements msgp.Encodable

func (*Leaf) FlatString 

func (n *Leaf) FlatString(depth int, recurse int) (s string)

func (*Leaf) Gstring 

func (z *Leaf) Gstring() (r string)

func (*Leaf) MarshalMsg 

func (z *Leaf) MarshalMsg(b []byte) (o []byte, err error)

MarshalMsg implements msgp.Marshaler

func (*Leaf) Msgsize 

func (z *Leaf) Msgsize() (s int)

Msgsize returns an upper bound estimate of the number of bytes occupied by the serialized message

func (*Leaf) String 

func (lf *Leaf) String() string

func (*Leaf) UnmarshalMsg 

func (z *Leaf) UnmarshalMsg(bts []byte) (o []byte, err error)

UnmarshalMsg implements msgp.Unmarshaler

func (*Leaf) UnmarshalMsgWithCfg 

func (z *Leaf) UnmarshalMsgWithCfg(bts []byte, cfg *msgp.RuntimeConfig) (o []byte, err error)

type SearchModifier 

type SearchModifier int
const (
	// Exact is the default.
	Exact SearchModifier = 0 // exact matches only; like a hash table
	GTE   SearchModifier = 1 // greater than or equal to this key.
	LTE   SearchModifier = 2 // less than or equal to this key.
	GT    SearchModifier = 3 // strictly greater than this key.
	LT    SearchModifier = 4 // strictly less than this key.
)

func (*SearchModifier) DecodeMsg 

func (z *SearchModifier) DecodeMsg(dc *msgp.Reader) (err error)

DecodeMsg implements msgp.Decodable We treat empty fields as if we read a Nil from the wire.

func (SearchModifier) EncodeMsg 

func (z SearchModifier) EncodeMsg(en *msgp.Writer) (err error)

EncodeMsg implements msgp.Encodable

func (SearchModifier) MarshalMsg 

func (z SearchModifier) MarshalMsg(b []byte) (o []byte, err error)

MarshalMsg implements msgp.Marshaler

func (SearchModifier) Msgsize 

func (z SearchModifier) Msgsize() (s int)

Msgsize returns an upper bound estimate of the number of bytes occupied by the serialized message

func (SearchModifier) String 

func (smod SearchModifier) String() string

func (*SearchModifier) UnmarshalMsg 

func (z *SearchModifier) UnmarshalMsg(bts []byte) (o []byte, err error)

UnmarshalMsg implements msgp.Unmarshaler

func (*SearchModifier) UnmarshalMsgWithCfg 

func (z *SearchModifier) UnmarshalMsgWithCfg(bts []byte, cfg *msgp.RuntimeConfig) (o []byte, err error)

type TestBytes 

type TestBytes struct {
	Slc []byte `zid:"0"`
}

func (*TestBytes) DecodeMsg 

func (z *TestBytes) DecodeMsg(dc *msgp.Reader) (err error)

DecodeMsg implements msgp.Decodable We treat empty fields as if we read a Nil from the wire.

func (*TestBytes) EncodeMsg 

func (z *TestBytes) EncodeMsg(en *msgp.Writer) (err error)

EncodeMsg implements msgp.Encodable

func (*TestBytes) Gstring 

func (z *TestBytes) Gstring() (r string)

func (*TestBytes) MarshalMsg 

func (z *TestBytes) MarshalMsg(b []byte) (o []byte, err error)

MarshalMsg implements msgp.Marshaler

func (*TestBytes) Msgsize 

func (z *TestBytes) Msgsize() (s int)

Msgsize returns an upper bound estimate of the number of bytes occupied by the serialized message

func (*TestBytes) UnmarshalMsg 

func (z *TestBytes) UnmarshalMsg(bts []byte) (o []byte, err error)

UnmarshalMsg implements msgp.Unmarshaler

func (*TestBytes) UnmarshalMsgWithCfg 

func (z *TestBytes) UnmarshalMsgWithCfg(bts []byte, cfg *msgp.RuntimeConfig) (o []byte, err error)

type Tree 

type Tree struct {
	RWmut sync.RWMutex `msg:"-"`

	// SkipLocking means do no internal
	// synchronization, because a higher
	// component is doing so.
	//
	// Warning: when using SkipLocking
	// the user's code _must_ synchronize (prevent
	// overlap) of readers and writers from
	// different goroutines who access the Tree
	// simultaneously. Under this setting,
	// the Tree will not do locking itself
	// (it does by default, with SkipLocking false).
	// Without synchronization, multiple goroutines
	// will create data races, lost data, and
	// segfaults from torn reads.
	//
	// The easiest way to do this is with a sync.RWMutex.
	// One such, the RWmut on this Tree, will be
	// employed if SkipLocking is allowed to
	// default to false.
	SkipLocking bool `msg:"-"`

	Leafz []*Leaf `zid:"0"`
	// contains filtered or unexported fields
}

Tree is a trie that implements the Adaptive Radix Tree (ART) algorithm to provide a sorted, key-value, in-memory dictionary[1]. The ART tree provides both path compression (vertical compression) and variable sized inner nodes (horizontal compression) for space-efficient fanout.

Path compression is particularly attractive in situations where many keys have redudant prefixes. This is the common case for many ordered-key-value-map use cases, such as database indexes and file-system hierarchies. The Google File System paper, for example, mentions the efficiencies obtained by exploiting prefix compression in their distributed file system[2]. FoundationDB's new Redwood backend provides it as a feature[3], and users wish the API could be improved by offering it[4] in query result APIs.

As an alternative to red-black trees, AVL trees, and other kinds of balanced binary trees, ART is particularly attractive. Like those trees, ART offers an ordered index of sorted keys allowing efficient O(log N) access for each unique key.

Efficient key-range lookup and iteration, as well as the ability to treat the tree as array using integer indexes (based on the counted B-tree idea[5]), make this ART tree implementation particularly easy to use in practice.

ART supports just a single value for each key -- it is not a "multi-map" in the C++ sense.

Concurrency: this ART implementation is goroutine safe, as it uses a the Tree.RWmut sync.RWMutex for synchronization. Thus it allows only a single writer at a time, and any number of readers. Readers will block until the writer is done, and thus they see a fully consistent view of the tree. The RWMutex approach was the fastest and easiest to reason about in our applications without overly complicating the code base. The SkipLocking flag can be set to omit all locking if goroutine coordination is provided by other means, or unneeded (in the case of single goroutine only access).

[1] "The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases" by Viktor Leis, Alfons Kemper, Thomas Neumann.

[2] "The Google File System" SOSP’03, October 19–22, 2003, Bolton Landing, New York, USA. by Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung. https://pdos.csail.mit.edu/6.824/papers/gfs.pdf

[3] "How does FoundationDB store keys with duplicate prefixes?" https://forums.foundationdb.org/t/how-does-foundationdb-store-keys-with-duplicate-prefixes/1234

[4] "Issue #2189: Prefix compress read range results" https://github.com/apple/foundationdb/issues/2189

[5] "Counted B-Trees" https://www.chiark.greenend.org.uk/~sgtatham/algorithms/cbtree.html

func NewArtTree 

func NewArtTree() *Tree

NewArtTree creates and returns a new ART Tree, ready for use.

func (*Tree) At 

func (t *Tree) At(i int) (lf *Leaf, ok bool)

At(i) lets us think of the tree as a array, returning the i-th leaf from the sorted leaf nodes, using an efficient O(log N) time algorithm. Here N is the size or count of elements stored in the tree.

At() uses the counted B-tree approach described by Simon Tatham[1]. This is also known as an Order-Statistic tree in the literature[2].

Optimization: for the common case of sequential calls going forward, At(i) will transparently use an iterator to cache the tree traversal point so that the next At(i+1) call can pick up where the previous tree search left off. Since we don't have to repeat the mostly-the-same traversal down the tree again, the speed-up in benchmark (see Test620) for this common case is a dramatic 6x, from 240 nsec to 40 nsec per call. The trade-off is that we must do a small amount of allocation to maintain a stack during the calls. We will try to add a small pool of iterator checkpoint frames in the future to minimize it, but complete zero-alloc is almost impossible if we want this optimization. My call is that this a trade-off well worth making.

If you will be doing alot of random (un-sequential/non-linear) access to the tree, use Atfar() instead of At(). They are the same, except that Atfar will not spend any time trying to cache the tree traversal paths to your random access points.

[1] https://www.chiark.greenend.org.uk/~sgtatham/algorithms/cbtree.html

[2] https://en.wikipedia.org/wiki/Order_statistic_tree

func (*Tree) Atfar 

func (t *Tree) Atfar(i int) (lf *Leaf, ok bool)

Atfar is more suitable that At for random (non-linear sequential) access to the tree.

Atfar() is the same as At() except that it does not attempt to do any caching of the tree traversal point to speed up sequential calls such as At(i), At(i+1), At(i+2), ... like At() does.

Hence Atfar() saves the (relatively small) time that At() spends filling the iterator checkpoint cache.

If you will be doing alot of random (un-sequential) access to the tree, use Atfar() instead of At(). The name tries to suggest that this access is "far" away from any others.

func (*Tree) Atv 

func (t *Tree) Atv(i int) (val []byte, ok bool)

Atv(i) is like At(i) but returns the value from the Leaf instead of the actual *Leaf itself, simply for convenience.

func (*Tree) Clone added in v1.34.20 

func (t *Tree) Clone() (r *Tree)

func (*Tree) CompressedStats 

func (t *Tree) CompressedStats() (cs map[int]int, bytesSaved int)

CompressedStats returns the count of inner nodes with a given compressed prefix length.

func (*Tree) DecodeMsg 

func (z *Tree) DecodeMsg(dc *msgp.Reader) (err error)

DecodeMsg implements msgp.Decodable We treat empty fields as if we read a Nil from the wire.

func (*Tree) EncodeMsg 

func (z *Tree) EncodeMsg(en *msgp.Writer) (err error)

EncodeMsg implements msgp.Encodable

func (*Tree) Find 

func (t *Tree) Find(smod SearchModifier, key Key) (lf *Leaf, idx int, found bool)

Find allows GTE, GT, LTE, LT, and Exact searches.

GTE: find a leaf greater-than-or-equal to key; the smallest such key.

GT: find a leaf strictly greater-than key; the smallest such key.

LTE: find a leaf less-than-or-equal to key; the largest such key.

LT: find a leaf less-than key; the largest such key.

Exact: find leaf whose key matches the supplied key exactly. This is the default. It acts like a hash table. A key can only be stored once in the tree. (It is not a multi-map in the C++ STL sense).

If key is nil, then GTE and GT return the first leaf in the tree, while LTE and LT return the last leaf in the tree.

Clients must take care not to modify the returned Leaf.Key, as it is not copied to keep memory use low. Doing so will result in undefined behavior.

The FindGTE, FindGT, FindLTE, and FindLT methods provide a more convenient interface to obtain the stored Leaf.Value if the full generality of Leaf access is not required.

By default, Find obtains a read-lock on the Tree.RWmut. This can be omitted by setting the Tree.SkipLocking option to true.

func (*Tree) FindExact 

func (t *Tree) FindExact(key Key) (val []byte, idx int, found bool, vtype string)

FindExact returns the element whose key matches the supplied key.

func (*Tree) FindGT 

func (t *Tree) FindGT(key Key) (val []byte, idx int, found bool, lf *Leaf)

FindGT returns the first element whose key is greater than the supplied key.

func (*Tree) FindGTE 

func (t *Tree) FindGTE(key Key) (val []byte, idx int, found bool, lf *Leaf)

FindGTE returns the first element whose key is greater than, or equal to, the supplied key.

func (*Tree) FindLT 

func (t *Tree) FindLT(key Key) (val []byte, idx int, found bool, lf *Leaf)

FindGT returns the first element whose key is less than the supplied key.

func (*Tree) FindLTE 

func (t *Tree) FindLTE(key Key) (val []byte, idx int, found bool, lf *Leaf)

FindLTE returns the first element whose key is less-than-or-equal to the supplied key.

func (*Tree) FirstLeaf 

func (t *Tree) FirstLeaf() (lf *Leaf, idx int, found bool)

FirstLeaf returns the first leaf in the Tree.

func (*Tree) Gstring 

func (z *Tree) Gstring() (r string)

func (*Tree) Insert 

func (t *Tree) Insert(key Key, value []byte, vtype string) (updated bool)

Insert makes a copy of key to avoid sharing bugs. The value is only stored and not copied. The return value updated is true if the size of the tree did not change because an existing key was given the new value.

func (*Tree) InsertLeaf 

func (t *Tree) InsertLeaf(lf *Leaf) (updated bool)

InsertLeaf: the *Leaf lf *must* own the lf.Key it holds. It cannot be shared. Callers must guarantee this, copying the slice if necessary before submitting the Leaf.

func (*Tree) IsEmpty 

func (t *Tree) IsEmpty() (empty bool)

IsEmpty returns true iff the Tree is empty.

func (*Tree) Iter 

func (t *Tree) Iter(start, end []byte) (iter *iterator)

Iter starts a traversal over the range [start, end) in ascending order.

iter.Next() must be called to start the iteration before iter.Key(), iter.Value(), or iter.Leaf() will be meaningful.

When iter.Next() returns false, the iteration has completed.

We begin with the first key that is >= start and < end.

The end key must be > the start key, or no values will be returned. Either start or end can be nil to indicate the furthest possible range in that direction.

For example, note that [x, x) will return the empty set, unless x is nil. If x _is_ nil, this will return the entire tree in ascending order.

For another example, suppose the keys {0, 1, 2} are in the tree, and tree.Iter(0, 2) is called. Forward iteration will return 0, then 1.

The returned iterator is not concurrent/multiple goroutine safe. Iteration does no synchronization. This allows for single goroutine code that deletes from (or inserts into) the tree during the iteration, which is not an uncommon need.

func (*Tree) LastLeaf 

func (t *Tree) LastLeaf() (lf *Leaf, idx int, found bool)

FirstLeaf returns the last leaf in the Tree.

func (*Tree) LeafIndex 

func (t *Tree) LeafIndex(leaf *Leaf) (idx int, ok bool)

LeafIndex returns the integer index of the leaf in the tree using exact key matching. The index represents the position in the lexicographic (shortlex) sorted order of keys, and so can be used to compute quantile and other statistics efficiently. The time complexity is O(log N).

func (*Tree) MarshalMsg 

func (z *Tree) MarshalMsg(b []byte) (o []byte, err error)

MarshalMsg implements msgp.Marshaler

func (*Tree) Msgsize 

func (z *Tree) Msgsize() (s int)

Msgsize returns an upper bound estimate of the number of bytes occupied by the serialized message

func (*Tree) NewTreeSaver 

func (tree *Tree) NewTreeSaver(w io.Writer) (*TreeSaver, error)

func (*Tree) PostLoadHook 

func (tree *Tree) PostLoadHook()

func (*Tree) PreSaveHook 

func (tree *Tree) PreSaveHook()

func (*Tree) Remove 

func (t *Tree) Remove(key Key) (deleted bool, deletedLeaf *Leaf)

Remove deletes the key from the Tree. If the key is not present deleted will return false. If the key was present, deletedLeaf will supply its associated Leaf from which value, in the deletedLeaf.Value field, can be obtained.

func (*Tree) RevIter 

func (t *Tree) RevIter(end, start []byte) (iter *iterator)

RevIter starts a traversal over the range (end, start] in descending order.

Note that the first argument to RevIter() is the smaller (if the two differ), assuming you don't want the empty set. This is true for Iter() as well.

iter.Next() must be called to start the iteration before iter.Key(), iter.Value(), or iter.Leaf() will be meaningful.

When iter.Next() returns false, the iteration has completed.

We begin with the first key that is <= start and > end.

The end key must be < the start key, or no values will be returned. Either start or end can be nil to indicate the furthest possible range in that direction.

For example, note that (x, x] will return the empty set, unless x is nil. If x _is_ nil, this will return the entire tree in descending order.

For another example, suppose the keys {0, 1, 2} are in the tree, and tree.RevIter(0, 2) is called. Reverse iteration will return 2, then 1. The same holds true if start (2 here) is replaced by by any integer > 2.

tree.RevIter(nil, 2) will yield 2, then 1, then 0; as will tree.RevIter(nil, nil).

The returned iterator is not concurrent/multiple goroutine safe. Iteration does no synchronization. This allows for single goroutine code that deletes from (or inserts into) the tree during the iteration, which is not an uncommon need.

func (*Tree) Size 

func (t *Tree) Size() (sz int)

Size returns the number of keys (leaf nodes) stored in the tree.

func (*Tree) String 

func (t *Tree) String() string

String does no locking. It returns a string representation of the tree. This is mostly for debugging, and can be quite slow for large trees.

func (*Tree) UnmarshalMsg 

func (z *Tree) UnmarshalMsg(bts []byte) (o []byte, err error)

UnmarshalMsg implements msgp.Unmarshaler

func (*Tree) UnmarshalMsgWithCfg 

func (z *Tree) UnmarshalMsgWithCfg(bts []byte, cfg *msgp.RuntimeConfig) (o []byte, err error)

type TreeLoader 

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

func NewTreeLoader 

func NewTreeLoader(r io.Reader) (*TreeLoader, error)

func (*TreeLoader) Load 

func (s *TreeLoader) Load() (tree *Tree, err error)

type TreeSaver 

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

func (*TreeSaver) Flush 

func (s *TreeSaver) Flush() (err error)

func (*TreeSaver) NumLeafWrit 

func (s *TreeSaver) NumLeafWrit() (r int)

func (*TreeSaver) Save 

func (s *TreeSaver) Save() error

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.