crossbeam_skiplist_mvcc/
lib.rs

1#![doc = include_str!("../README.md")]
2#![forbid(unsafe_code)]
3#![cfg_attr(docsrs, feature(doc_cfg))]
4#![cfg_attr(docsrs, allow(unused_attributes))]
5#![deny(missing_docs)]
6
7macro_rules! common {
8  ($mod_name: literal) => {
9    /// Inserts a `key`-`value` pair into the map and returns the new entry.
10    ///
11    /// If there is an existing entry with this key, it will be removed before inserting the new
12    /// one.
13    ///
14    /// This function returns an [`Ok(Entry)`](Entry) which
15    /// can be used to access the inserted key's associated value.
16    ///
17    /// This function returns an [`Err(Error)`](Error) if the given version has already been discarded by [`compact`](SkipMap::compact).
18    ///
19    /// See also [`insert_unchecked`](SkipMap::insert_unchecked).
20    ///
21    /// ## Example
22    ///
23    /// ```rust
24    #[doc = concat!("use crossbeam_skiplist_mvcc::", $mod_name, "::SkipMap;")]
25    ///
26    /// let map = SkipMap::new();
27    /// map.insert(1, "key", "value").unwrap();
28    ///
29    /// assert_eq!(*map.get(1, "key").unwrap().value(), "value");
30    /// ```
31    pub fn insert(
32      &self,
33      version: u64,
34      key: K,
35      value: V,
36    ) -> Result<Entry<'_, K, V, Active, C>, Error> {
37      self
38        .check_discard(version)
39        .map(|_| self.insert_in(version, key, value))
40    }
41
42    /// Inserts a `key`-`value` pair into the map and returns the new entry.
43    ///
44    /// If there is an existing entry with this key, it will be removed before inserting the new
45    /// one.
46    ///
47    /// This function returns an [`Entry`] which
48    /// can be used to access the inserted key's associated value.
49    ///
50    /// See also [`insert`](SkipMap::insert).
51    ///
52    /// ## Panics
53    /// - If the given `version` has already been discarded by [`compact`](SkipMap::compact).
54    ///
55    /// ## Example
56    ///
57    /// ```rust
58    #[doc = concat!("use crossbeam_skiplist_mvcc::", $mod_name, "::SkipMap;")]
59    ///
60    /// let map = SkipMap::new();
61    /// map.insert_unchecked(1, "key", "value");
62    ///
63    /// assert_eq!(*map.get(1, "key").unwrap().value(), "value");
64    /// ```
65    pub fn insert_unchecked(&self, version: u64, key: K, value: V) -> Entry<'_, K, V, Active, C> {
66      self
67        .check_discard(version)
68        .expect("version has already been discarded");
69      self.insert_in(version, key, value)
70    }
71
72    /// Inserts a `key`-`value` pair into the skip list and returns the new entry.
73    ///
74    /// If there is an existing entry with this key and compare(entry.value) returns true,
75    /// it will be removed before inserting the new one.
76    /// The closure will not be called if the key is not present.
77    ///
78    /// This function returns an [`Ok(Entry)`](`Entry`) which
79    /// can be used to access the inserted key's associated value.
80    ///
81    /// This function returns an [`Err(Error)`](`Error`) if the given version has already been discarded by [`compact`](SkipMap::compact).
82    ///
83    /// See also [`compare_insert_unchecked`](SkipMap::compare_insert_unchecked).
84    ///
85    /// ## Example
86    ///
87    /// ```rust
88    #[doc = concat!("use crossbeam_skiplist_mvcc::", $mod_name, "::SkipMap;")]
89    ///
90    /// let map = SkipMap::new();
91    /// map.insert(1, "key", 1);
92    /// map.compare_insert(1, "key", 0, |x| x.unwrap() < &0).unwrap();
93    /// assert_eq!(*map.get(1, "key").unwrap().value(), 1);
94    /// map.compare_insert(1, "key", 2, |x| x.unwrap() < &2).unwrap();
95    /// assert_eq!(*map.get(1, "key").unwrap().value(), 2);
96    /// map.compare_insert(1, "absent_key", 0, |_| false).unwrap();
97    /// assert_eq!(*map.get(1, "absent_key").unwrap().value(), 0);
98    /// ```
99    pub fn compare_insert<F>(
100      &self,
101      version: u64,
102      key: K,
103      value: V,
104      compare_fn: F,
105    ) -> Result<Entry<'_, K, V, Active, C>, Error>
106    where
107      F: Fn(Option<&V>) -> bool,
108    {
109      self
110        .check_discard(version)
111        .map(|_| self.compare_insert_in(version, key, value, compare_fn))
112    }
113
114    /// Inserts a `key`-`value` pair into the skip list and returns the new entry.
115    ///
116    /// If there is an existing entry with this key and compare(entry.value) returns true,
117    /// it will be removed before inserting the new one.
118    /// The closure will not be called if the key is not present.
119    ///
120    /// This function returns an [`Entry`] which
121    /// can be used to access the inserted key's associated value.
122    ///
123    /// ## Example
124    ///
125    /// ```rust
126    #[doc = concat!("use crossbeam_skiplist_mvcc::", $mod_name, "::SkipMap;")]
127    ///
128    /// let map = SkipMap::new();
129    /// map.insert(1, "key", 1);
130    /// map.compare_insert_unchecked(1, "key", 0, |x| x.unwrap() < &0);
131    /// assert_eq!(*map.get(1, "key").unwrap().value(), 1);
132    /// map.compare_insert_unchecked(1, "key", 2, |x| x.unwrap() < &2);
133    /// assert_eq!(*map.get(1, "key").unwrap().value(), 2);
134    /// map.compare_insert_unchecked(1, "absent_key", 0, |_| false);
135    /// assert_eq!(*map.get(1, "absent_key").unwrap().value(), 0);
136    /// ```
137    pub fn compare_insert_unchecked<F>(
138      &self,
139      version: u64,
140      key: K,
141      value: V,
142      compare_fn: F,
143    ) -> Entry<'_, K, V, Active, C>
144    where
145      F: Fn(Option<&V>) -> bool,
146    {
147      self
148        .check_discard(version)
149        .expect("version has already been discarded");
150      self.compare_insert_in(version, key, value, compare_fn)
151    }
152
153    /// Insert a tombstone entry for the specified `key` from the map and returns it.
154    ///
155    /// Note that this will not actually remove the entry from the map,
156    /// but only insert a new entry and mark it as removed.
157    /// To actually remove entries with old versions, use [`compact`](SkipMap::compact).
158    ///
159    /// This function returns an [`Entry`] which
160    /// can be used to access the removed key's associated value.
161    ///
162    /// This function returns an [`Err(Error)`](`Error`) if the given version has already been discarded by [`compact`](SkipMap::compact).
163    ///
164    /// See also [`remove_unchecked`](SkipMap::remove_unchecked).
165    ///
166    /// ## Example
167    ///
168    /// ```rust
169    #[doc = concat!("use crossbeam_skiplist_mvcc::", $mod_name, "::SkipMap;")]
170    ///
171    /// let map: SkipMap<&str, &str> = SkipMap::new();
172    /// assert!(map.remove(1, "invalid key").unwrap().is_none());
173    ///
174    /// map.insert(0, "key", "value");
175    /// assert_eq!(*map.remove(1, "key").unwrap().unwrap().value(), "value");
176    /// ```
177    pub fn remove(
178      &self,
179      version: u64,
180      key: K,
181    ) -> Result<Option<Entry<'_, K, V, Active, C>>, Error> {
182      self
183        .check_discard(version)
184        .map(|_| self.remove_in(version, key))
185    }
186
187    /// Insert a tombstone entry for the specified `key` from the map and returns it.
188    ///
189    /// Note that this will not actually remove the entry from the map,
190    /// but only insert a new entry and mark it as removed.
191    /// To actually remove entries with old versions, use [`compact`](SkipMap::compact).
192    ///
193    /// This function returns an [`Entry`] which
194    /// can be used to access the removed key's associated value.
195    ///
196    /// ## Panics
197    /// - If the given `version` has already been discarded by [`compact`](SkipMap::compact).
198    ///
199    /// ## Example
200    ///
201    /// ```rust
202    #[doc = concat!("use crossbeam_skiplist_mvcc::", $mod_name, "::SkipMap;")]
203    ///
204    /// let map: SkipMap<&str, &str> = SkipMap::new();
205    /// assert!(map.remove_unchecked(1, "invalid key").is_none());
206    ///
207    /// map.insert(0, "key", "value");
208    /// assert_eq!(*map.remove_unchecked(1, "key").unwrap().value(), "value");
209    /// ```
210    pub fn remove_unchecked(&self, version: u64, key: K) -> Option<Entry<'_, K, V, Active, C>> {
211      self
212        .check_discard(version)
213        .expect("version has already been discarded");
214      self.remove_in(version, key)
215    }
216
217    #[inline]
218    fn check_discard(&self, version: u64) -> Result<(), Error> {
219      let last = self.last_discard_version.load(Ordering::Acquire);
220      if last != 0 && last >= version {
221        return Err(Error::AlreadyDiscarded(version));
222      }
223      Ok(())
224    }
225  };
226}
227
228/// A multiple version ordered map based on a lock-free skip list. See [`SkipMap`](crate::nested::SkipMap).
229pub mod nested;
230
231/// A multiple version ordered map based on a lock-free skip list. See [`SkipMap`](crate::flatten::SkipMap).
232pub mod flatten;
233
234/// Error types for this crate.
235pub mod error;
236
237pub use crossbeam_skiplist::{equivalentor, Ascend, Descend};
238
239pub use dbutils::state;
240
241/// Transfer the value from `V` to `Self::To`.
242pub trait Transfer<'a, V: 'a>: sealed::Sealed<'a, V> {}
243
244impl<'a, V: 'a, T> Transfer<'a, V> for T where T: sealed::Sealed<'a, V> {}
245
246mod sealed {
247  pub struct TombstoneValidator;
248
249  impl<V> snapshotor::Validator<Option<V>> for TombstoneValidator {
250    #[inline]
251    fn validate(&self, value: &Option<V>) -> bool {
252      value.is_some()
253    }
254  }
255
256  pub trait Sealed<'a, V: 'a>: dbutils::state::State {
257    type To: 'a;
258
259    fn output(data: Option<&'a V>) -> Self::To;
260  }
261
262  impl<'a, V: 'a> Sealed<'a, V> for dbutils::state::Active {
263    type To = &'a V;
264
265    #[inline]
266    fn output(data: Option<&'a V>) -> Self::To {
267      data.expect("entry in Active state must have a value")
268    }
269  }
270
271  impl<'a, V: 'a> Sealed<'a, V> for dbutils::state::MaybeTombstone {
272    type To = Option<&'a V>;
273
274    #[inline]
275    fn output(data: Option<&'a V>) -> Self::To {
276      data
277    }
278  }
279}
crossbeam_skiplist_mvcc/lib.rs

crossbeam_skiplist_mvcc/
lib.rs
