slices iterators require Default

Merge pull request #41 from orxfun/slices-iterators-require-Default

slices iterators require Default

slices and initialized grow

Two slice returning methods are introduced. These methods are important in performant critical applications which allows to directly benefit from slice optimizations.

• fn slices(&self, range: R) returns an iterator of slices representing a given range of the vector.
• fn slices_mut(&mut self, range: R) returns a mutable iterator of slices representing a given range of the vector.

A concurrently safe growth method method grow_and_initialize is introduced. This methods performs capacity growth and length growth at the same time making sure that all elements are initialized with valid values.

Also unsafe get_ptr_mut_and_indices method is implemented.

Test methods are extended accordingly.

`binary_search_by` is implemented

• Default implementations of binary_search and binary_search_by_key are provided.
• Extended pinned vector tests are used, including binary search test methods.
• Additional fragment specific binary search tests are added.

IntoIterator is required for PinnedVec

• Upgraded the orx-pinned-vec dependency to version 2.9 which requires all pinned vectors to implement IntoIterator.
• IntoIter is introduced and IntoIterator is implemented for SplitVec.
• Further, bug in any reduction is fixed.

Efficient Reductions

More efficient versions of the following reduction methods are implemented for the iterator.

• all
• any
• fold

`try_reserve_maximum_concurrent_capacity` method

try_reserve_maximum_concurrent_capacity method is defined which is essential for concurrent wrappers such as PinnedConcurrentCol.

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.