Crate ppar[−][src]
Expand description
Package implement persistent array using a variant of rope data structure.
Fundamentally, it can be viewed as a binary-tree of array-blocks, where
each leaf-node is a block of contiguous item of type T
, while intermediate
nodes only hold references to the child nodes, left and right.
To be more precise, intermediate nodes in the tree are organised similar
to rope structure, as a tuple of (weight, left, right) where weight
is the sum of all items present in the leaf-nodes under the left-branch.
Here is a quick list of situation that might require using ppar
.
- When array size is too large with repeated insert and remove operation.
- When shared ownership is required.
- When shared ownership across concurrent threads.
- To support undo/redo operation for array modifications.
- When splitting up of array and/or joining arrays are frequently done.
- Lazy clone of array using copy-on-write.
Ownership and Cloning
Cloning arc::Vector
and rc::Vector
is cheap, it creates a shared ownership
of the underlying tree. This is great for applications requiring
shared-ownership, but at the cost of copy-on-write for every mutation in
the Vector, like insert, remove, delete. For applications requiring only
single-ownership insert_mut, remove_mut, delete_mut gives better
performance because the underlying tree is mutated in-place. To help decide
what method to use when, methods that perform in-place mutation are
suffixed with _mut
.
Thread Safety
arc::Vector<T>
is thread safe through Arc
. To trade-off
thread-safety for performance use rc::Vector
type, which is same as
arc::Vector
type except for using std::rc::Rc
instead of
std::sync::Arc
for shared ownership. That is, Send
and Sync
traits are not available for rc::Vector
type while it is available
for arc::Vector
type.
Alternate libraries:
Modules
Module implement thread-safe persistent array.
Module implement persistent array, faster but not thread safe.
Enums
Error variants that can be returned by this package’s API.
Constants
Leaf node shall not exceed this default size.
Threshold on tree depth, beyond which auto-rebalance will kick in.
Type Definitions
Type alias for Result return type, used by this package.