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.





The Error type.


A Guard on a CAS operation


The result of running an operation


A hierarchical version tree.



The kind of an error.


Values included in successful replies to Operations


A write operation that is part of a multi-cas



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

Type Definitions


Convenient wrapper around std::Result.