Support for Concurrency: `zero_memory` argument in grow_to methods

The users of the PinnedVec trait, hence SplitVec, might require to zero out allocated memory which is not yet written. This is an additional safety guarantee for specifically concurrent data types. Therefore, grow_to and concurrently_grow_to methods accept a second argument zero_memory. When true is passed in, the implementor is responsible for zeroing out the new memory, if allocated.

• Fragment::zero(&mut self) method is implemented. This method is used on new fragments when grow to methods are called with a zero_memory of true.
• growth with memory zeroing tests are added.
• Tests extended with the test-case crate.

Support for Concurrency

• Split vector is revised for supporting data structures which use it as the underlying storage in a concurrent program:
  • maximum_concurrent_capacity method is implemented to the vector. Even though the vector can grow beyond this value, it must not grow beyond it in a concurrent program. The underlying reason is due to a possible re-allocation of the fragments collection. Split vector will always keep the elements pinned to their memory locations. However, as we keep adding fragments to the fragments collection, the memory locations of the meta information (pointers to the fragments) might be changed. This is completely fine in a single threaded program since the pinned elements guarantee is not broken. However, in a concurrent program, this might lead to the corresponding UB: * a thread tries to increase the capacity of the split vector. * this might lead to re-allocation of the fragments collection to a different memory location. * concurrently, another thread might be reading from the older memory location which is UB.
  • concurrent_reserve method is implemented. This method naturally requires a &mut self reference. Therefore, it can safely grow the maximum capacity to the desired value. Note that this call is not costly as it does not lead to any immediate allocations, except for memory to store the pointers to the fragments.
  • internal can_concurrently_add_fragment method is implemented to make sure that concurrent safety guarantees are satisfied.
  • concurrently_grow_to method is implemented. This method returns a result stating whether or not it is safely possible to grow the capacity to the desired value in a concurrent setting.
  • capacity_state method is implemented. This method may be considered as the detailed version of the capacity method. The additional information is useful for concurrent safety guarantees.
  • Capacity related tests are extended.
  • New constructors with allowing guaranteed maximum capacity are implemented:
    • with_linear_growth_and_fragments_capacity
    • with_doubling_growth_and_fragments_capacity * with_recursive_growth_and_fragments_capacity
  • Growth::required_fragments_len trait method is defined with an auto implementation. Efficient implementations are provided for the growth strategies defined in this crate.
  • clone method now preserves equality of maximum_capacity.
• prelude module is brought back.
• Internal SplitVec and Fragment constructors are revised and simplified.

`grow_to` method is implemented

Increases the capacity of the vector at least up to the new_capacity:

• has no affect if new_capacity <= self.capacity(), and returns Ok(self.capacity());
• increases the capacity to x >= new_capacity otherwise if the operation succeeds.

This method is unsafe due to the internal guarantees of pinned vectors.

• A SplitVec, on the other hand, can grow to the new_capacity without any problem.
  However, it is not designed to have intermediate empty fragments, while grow_to can leave such fragments.
  Hence, the caller is responsible for handling this.

SplitVec is extended by try_grow

• try_grow is implemented. Note that all split vector variants have the capability to grow. Therefore, they will grow and return Ok of the new capacity provided that the vector has reached its capacity.
• Debug text is extended by length and capacity.
• Default is un-implemented for Linear. Note that this was an accidental and not a useful implementation.

`get_ptr_mut` and useful `From` implementations

• prelude module is removed. Instead pub use orx_pinned_vec::PinnedVec; is added for convenience.
• unsafe get_ptr_mut pinned vec method is implemented. This method has a default Growth implementation; additionally, a more efficient constant time GrowthWithConstantTimeAccess implementation.
• test coverage is improved.
• SplitVec of any Growth, as well as standard Vec, can now be converted into a split vector with Recursive growth with no cost.
• Conversion from SplitVec to Vec is now free provided that the split vector contains only one fragment.
• slice and try_get_slice methods now accept any range.

`contains_reference` & `set_len` pinned-vec methods with `ptr_mut`

• PinnedVec::contains_reference method is implemented for SplitVec.
• GrowthWithConstantTimeAccess trait is defined. Note that every type implementing this trait also implements Growth. In other words, this is a special growth case. In addition, it provides the function get_fragment_and_inner_indices_unchecked which returns fragment and within-fragment indices without requiring the current state of the vector using constant time access function.
• ptr_mut method is implemented for split vectors having a constant time access growth strategy. This method is unsafe in the sense that it allows reading from or writing to uninitialized memory. On the other hand, it is safe against access violation, it only returns a memory location owned by the split vector.
• unsafe set_len method is implemented.

major pinned-vec 2.0.0 revision

• SplitVec implements "orx_pinned_vec::PinnedVec" version 2.0.
  • pinned elements guarantee is formalized and documented,
  • unsafe methods such as clone or insert are now safe. pinned vector on its own cannot build inter-element references; hence, these methods are not unsafe. this responsibility is passed to the struct enabling these references, namely, orx_selfref_col.
  • in addition to being a marker trait, this crate now provides test_pinned_vec function which is essential in asserting that a pinned vector implementation satisfies the required guarantees.
• Clone is implemented.
• Debug is implemented.
• Index-free iterator and reverse iterator implementations.

Recursive growth strategy

• Recursive growth strategy is defined and implemented.
• Benchmarks extended by including the Recursive strategy and adding the append benchmark.
• IntoFragments trait is defined to allow overloading in append function.
• Documentation is updated accordingly.

#22

orx_pinned_vec version 1.0

orx_pinned_vec version 1.0

Updated the orx_pinned_vec dependency to version 1.0. Note that this version finalizes the orx_pinned_vec::self_referential_elements module.

Also

• FromIterator is implemented for G: Growth + Default. Growth strategies implemented in this crate (Doubling and Linear) satisfy this trait bound.
• iter performance is further optimized by allowing the first branch to be the correct one in almost all the time.
• iter_mut is implemented.

Dependency Removed orx_fixed_vec

Dependency to orx_fixed_vec::FixedVec is removed. This is due to the fact that split vector performs as well as the standard vec after the performance optimizations, currently making fixed-vec not necessary.