1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96
//! # ev_slotmap //! A lock-free, concurrent slot map. //! Most of this library is a rip off of [Jon Gjengset's evmap](https://docs.rs/evmap/10.0.2/evmap/) //! but with a few notable simplifications //! //! - The value-bag map is replaced with a [one-way slotmap](https://docs.rs/one_way_slot_map/0.2.0/one_way_slot_map/) //! - No batched edits (required because slot map keys need to be returned on insert) //! - No associated metadata //! //! The core synchronization component's of evmap are still present. Out of //! simplicity, we also use the [ShallowCopy](https://docs.rs/evmap/10.0.2/evmap/shallow_copy/trait.ShallowCopy.html) //! straight out of evmap instead of copy-pasting it in. Also the following //! blurb is almost straight from evmap. //! //! This map implementation allows reads and writes to execute entirely in parallel, with no //! implicit synchronization overhead. Reads never take locks on their critical path, and neither //! do writes assuming there is a single writer (multi-writer is possible using a `Mutex`), which //! significantly improves performance under contention. //! //! Unlike evmap which provides eventual consistency following explicit `refresh` //! calls, synchronization between reads and writers happens before write methods //! return. For read-heavy workloads, the scheme used by this module is particularly //! useful. Writers can afford to refresh after every write, which provides up-to-date //! reads, and readers remain fast as they do not need to ever take locks. #![warn( missing_docs, rust_2018_idioms, missing_debug_implementations, intra_doc_link_resolution_failure )] #![allow(clippy::type_complexity)] use one_way_slot_map::{SlotMap, SlotMapKey as Key, SlotMapKeyData}; use std::sync::{atomic, Arc, Mutex}; mod inner; use crate::inner::Inner; use evmap::ShallowCopy; use slab::Slab; pub(crate) type Epochs = Arc<Mutex<Slab<Arc<atomic::AtomicUsize>>>>; /// A pending map operation. #[non_exhaustive] #[derive(PartialEq, Eq, Debug)] pub(crate) enum Operation<V> { /// Just do a refresh without altering the data NoOp, /// Replace the value for this key with this value. Replace(SlotMapKeyData, V), /// Add this value to the map. Add(V), /// Remove the value with this key from the map. Remove(SlotMapKeyData), /// Clear the map. Clear, } mod write; pub use crate::write::WriteHandle; mod read; pub use crate::read::{MapReadRef, ReadGuard, ReadHandle, ReadHandleFactory}; /// Create an empty ev slotmap. pub fn new<K, P, V>() -> (ReadHandle<K, P, V>, WriteHandle<K, P, V>) where K: Key<P>, V: ShallowCopy, { let epochs = Default::default(); let inner = Inner::new(); let mut w_handle = Inner::new(); w_handle.mark_ready(); let r = read::new(inner, Arc::clone(&epochs)); let w = write::new(w_handle, epochs, r.clone()); (r, w) } /// Create a new evmap with the given data pub fn new_with_data<K, P, V>( data: SlotMap<K, P, V>, ) -> (ReadHandle<K, P, V>, WriteHandle<K, P, V>) where K: Key<P>, V: ShallowCopy, { let epochs = Default::default(); let (inner_r, inner_w) = Inner::new_with_data(data); let r = read::new(inner_r, Arc::clone(&epochs)); let w = write::new(inner_w, epochs, r.clone()); (r, w) }