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:
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.
maximum_concurrent_capacitymethod 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 thefragmentscollection. 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_reservemethod is implemented. This method naturally requires a&mut selfreference. 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.can_concurrently_add_fragmentmethod is implemented to make sure that concurrent safety guarantees are satisfied.concurrently_grow_tomethod 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_statemethod is implemented. This method may be considered as the detailed version of thecapacitymethod. The additional information is useful for concurrent safety guarantees.with_linear_growth_and_fragments_capacitywith_doubling_growth_and_fragments_capacity*with_recursive_growth_and_fragments_capacityGrowth::required_fragments_lentrait method is defined with an auto implementation. Efficient implementations are provided for the growth strategies defined in this crate.clonemethod now preserves equality ofmaximum_capacity.preludemodule is brought back.SplitVecandFragmentconstructors are revised and simplified.