Upgrade PinnedVec dependencies

• PinnedVec dependencies are upgraded to the latest.
• New clippy warnings are fixed.

Towards lock-free safe concurrent mutation

A major revision towards enabling safe concurrent grow & read & udpate methods.

Following are the notable changes.

ConcurrentElement

ConcurrentElement struct is defined. A concurrent element is sort of an element which does not directly provide &T or &mut T references.

• Instead, it provides thread-safe methods such as map, cloned, copied to read the data.
• And it provides thread-safe update, set and replace methods to mutate the data.

Changes in the ConcurrentVec

Defining concurrent element api lead the changes in the entire crate:

• vec.get(i) or vec[i] now returns &ConcurrentElement. All thread safe access to the value is then provided by the concurrent element.
• Similarly vec.iter() yields references to concurrent elements.
• Since concurrent elements can both be read and mutated, methods such as get_mut or iter_mut are not necessary.

ConcurrentSlice

ConcurrentSlice is defined. This struct is analogous to a slice of a vec or slice.

• Slices provide safe and limited access to a certain region of the data. This feature is useful and convenient when we want to split the data to different threads.
• Slices have all read & update methods, and as expected, lack the grow methods.

Safety and Partially Unsafe Methods

Safety guarantees are re-evaluated. With the safe api of the concurrent vec, we must not have a race condition. At least, this is the claim and expectation reflecting the design decisions. Tests are in line with the claim so far.

Methods that provide direct &T, &mut T, *const T or *mut T accesses are kept; however, marked as unsafe.

• Unsafe methods are now better defined.
• These methods are still partially safe due to the following:
  • We cannot end up with a dangling pointer when using these methods.
  • We cannot access out-of-bounds memory.
  • We cannot access uninitialized or freed memory.
• The only undefined behavior we can experience is due to race conditions:
  • The references returned by these methods leak out of the vector. Although they will remain valid, concurrent vector now has no means of preventing race conditions. Even when the user only reads through &T, we can still have race conditions since the concurrent vec itselfs allow thread-safe update methods.
• Possible scenarios where the unsafe methods can be safely used are documented, demonstrated with examples and tested.

Crate is converted to no_std

Merge pull request #26 from orxfun/crate-turned-into-no_std

crated turned into no_std

Clone, Index and IndexMut traits implemented

• Thread safe Clone method is implemented.
• Index and IndexMut traits are implemented for usize indices.
  • Due to possibly fragmented nature of the underlying pinned vec, and since we cannot return a reference to a temporarily created collection, currently index over a range is not possible. This would be possible with IndexMove (see rust-lang/rfcs#997).
• Debug trait implementation is made mode convenient, revealing the current len and capacity in addition to the elements.
• Upgraded dependencies to pinned-vec (3.7) and pinned-concurrent-col (2.6) versions.
• Tests are extended:
  • concurrent clone is tested.
  • in addition to concurrent push & read, safety of concurrent extend & read is also tested.
• boxcar::Vec is added to the benchmarks.

32-bit support

Due to fix in the SplitVec https://github.com/orxfun/orx-split-vec/releases/tag/3.4.0

ConcurrentOption version is upgraded (1.1)

• raw-get methods are renamed as get-raw

Concurrency model is revised to use `ConcurrentOption`

• Instead of Option, a ConcurrentOption is used as the wrapper of elements. ConcurrentOption provides guarantees in accessing the inner value without a data race. For the concurrent vector, its most important feature is to enable lock free initialize_if_none since write-only-once guarantee is already provided by the vector. Then, we can use efficient as_ref_with_order methods to get a reference to the data without a concern about data race.
• Changes in the State definition by the concurrent pinned collections are reflected to enable the vector to always have an initialized and valid state.
• raw_get and raw_get_mut methods are implemented. These methods provide out the raw pointers; however, only to initialized elements. Note that the memory locations will never change, and hence, these pointers will always point to valid and initialized data throughout the lifetime of the vector.
• Documentation and tests are revised accordingly.

Concurrency Model Revision

Concurrency Model Revision

With this major refactoring, safety issues are fixed to achieve a miri safe version for all the tests defined in this crate.

The refactoring consists of two main parts: downstream changes in pinned vector's concurrency support and replacing Option with T and AtomicBool vector.

PinnedVec Support for Concurrency

In version 2, PinnedVec grew with new methods to support concurrent data structures. However, this caused problems since these exposed methods were often unsafe, and further, they were not directly useful for the pinned vector consumers except for concurrent data structures wrapping a pinned vector. Furthermore, they are alien to a regular vector interface that we are used to using.

In version 3, a second trait called ConcurrentPinnedVec is defined. All useful methods related with concurrent programming are moved to this trait. This trait has an associated type defining the underlying pinned vector type. It can be turned into the pinned vector.

Finally, IntoConcurrentPinnedVec trait is defined. A pinned vector implementing this trait can be turned into a ConcurrentPinnedVec. As explained above, it can be converted back to the pinned vector.

In this release ConcurrentVec wraps a ConcurrentPinnedVec rather than a PinnedVec.

Concurrency State

The main goal of ConcurrentVec is to enable safe reading while allowing it to efficiently grow. In version 1, it was attempted to achieve this through wrapping the elements by an Option. Although this turned out to pass exhaustive tests, it had two problems. Firstly, it is not best to have a vector of Option rather than that of T's, since the concurrent collection allows to transform into_inner. In version 2, underlying concurrent pinned vector stores elements as T, and hence, we can directly get the vector of T's. Secondly, version 1 failed miri tests for the tests where we read & grow concurrently. Having a parallel concurrent vector of atomic bools, the race condition is eliminated in version 2.

n_items_buffer_as_mut_slices is implemented

This unsafe method provides the mutable slices allowing the consumer to write into the reserved buffer efficiently.

concurrent-col safe drop

• Upgraded to new version of PinnedConcurrentCol and ConcurrentBag with additional drop safety.
• Benchmarks are revised.
• Documentation is revised.