Crate vertree [] [src]

Vertree provides a persistent trie for storing versioned, hierarchical, typed data.

By Hierarchical, we mean that the code uses a filesystem like tree structure. In contrast to a normal trie, the key in each node is not a single character but a subset of a path between slashes. This allows us to ignore language encoding while still storing all keys in UTF-8 and providing lexicographically sorted keys.

Each inner node in the tree is a directory which contains an array of pointers to it's child nodes. Each leaf node is of a specific datastructure type. Leafs can be of type set, queue, or blob. A blob stores an array of bytes. Sets and queues store blobs.

A vertree is persistent, in the functional programming sense of the term, meaning, it is copy-on-write. Each update of a vertree results in a new vertree that shares structure with unchanged nodes in the previous vertree. Furthermore, when updating a node in the tree, all the nodes that are path copied from the updated node to the root have their versions bumped. This allows performing CAS operations on entire subtrees.

The persistent functionality is provided via the use of Atomic Refcounted (Arc) pointers. Garbage collection is performed when the refcount of nodes reaches 0. Note that this does not require epoch reclamation as used in crossbeam, because all updates are performed on a single thread. This use of Arc instead of Rc pointers for nodes allows immutable trees to be shared among threads. Note that updates on different threads will create new diverging trees, rather than a single 'latest tree'. For that we would require crossbeam.

Modules

containers
iterators

Structs

Error

The Error type.

Guard

A Guard on a CAS operation

Reply

The result of running an operation

Tree

A hierarchical version tree.

Enums

ErrorKind

The kind of an error.

NodeType
Value

Values included in successful replies to Operations

WriteOp

A write operation that is part of a multi-cas

Traits

ResultExt

Additional methods for Result, for easy interaction with this crate.

Type Definitions

Result

Convenient wrapper around std::Result.