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§
- arc
- Module implement thread-safe persistent array.
- rc
- Module implement persistent array, faster but not thread safe.
Enums§
- Error
- Error variants that can be returned by this package’s API.
Constants§
- LEAF_
CAP - Leaf node shall not exceed this default size.
- REBALANCE_
THRESHOLD - Threshold on tree depth, beyond which auto-rebalance will kick in.
Type Aliases§
- Result
- Type alias for Result return type, used by this package.