crossbeam-skiplist/src/map.rs
Line | Count | Source |
1 | | //! TODO: docs |
2 | | |
3 | | use std::borrow::Borrow; |
4 | | use std::fmt; |
5 | | use std::iter::FromIterator; |
6 | | use std::mem::ManuallyDrop; |
7 | | use std::ops::{Bound, RangeBounds}; |
8 | | use std::ptr; |
9 | | |
10 | | use crate::base::{self, try_pin_loop}; |
11 | | use crate::epoch; |
12 | | |
13 | | /// A map based on a lock-free skip list. |
14 | | pub struct SkipMap<K, V> { |
15 | | inner: base::SkipList<K, V>, |
16 | | } |
17 | | |
18 | | impl<K, V> SkipMap<K, V> { |
19 | | /// Returns a new, empty map. |
20 | 4 | pub fn new() -> SkipMap<K, V> { |
21 | 4 | SkipMap { |
22 | 4 | inner: base::SkipList::new(epoch::default_collector().clone()), |
23 | 4 | } |
24 | 4 | } <crossbeam_skiplist::map::SkipMap<i32, i32>>::new Line | Count | Source | 20 | 3 | pub fn new() -> SkipMap<K, V> { | 21 | 3 | SkipMap { | 22 | 3 | inner: base::SkipList::new(epoch::default_collector().clone()), | 23 | 3 | } | 24 | 3 | } |
<crossbeam_skiplist::map::SkipMap<i32, ()>>::new Line | Count | Source | 20 | 1 | pub fn new() -> SkipMap<K, V> { | 21 | 1 | SkipMap { | 22 | 1 | inner: base::SkipList::new(epoch::default_collector().clone()), | 23 | 1 | } | 24 | 1 | } |
|
25 | | |
26 | | /// Returns `true` if the map is empty. |
27 | | pub fn is_empty(&self) -> bool { |
28 | | self.inner.is_empty() |
29 | | } |
30 | | |
31 | | /// Returns the number of entries in the map. |
32 | | /// |
33 | | /// If the map is being concurrently modified, consider the returned number just an |
34 | | /// approximation without any guarantees. |
35 | | pub fn len(&self) -> usize { |
36 | | self.inner.len() |
37 | | } |
38 | | } |
39 | | |
40 | | impl<K, V> SkipMap<K, V> |
41 | | where |
42 | | K: Ord, |
43 | | { |
44 | | /// Returns the entry with the smallest key. |
45 | | pub fn front(&self) -> Option<Entry<'_, K, V>> { |
46 | | let guard = &epoch::pin(); |
47 | | try_pin_loop(|| self.inner.front(guard)).map(Entry::new) |
48 | | } |
49 | | |
50 | | /// Returns the entry with the largest key. |
51 | | pub fn back(&self) -> Option<Entry<'_, K, V>> { |
52 | | let guard = &epoch::pin(); |
53 | | try_pin_loop(|| self.inner.back(guard)).map(Entry::new) |
54 | | } |
55 | | |
56 | | /// Returns `true` if the map contains a value for the specified key. |
57 | | pub fn contains_key<Q>(&self, key: &Q) -> bool |
58 | | where |
59 | | K: Borrow<Q>, |
60 | | Q: Ord + ?Sized, |
61 | | { |
62 | | let guard = &epoch::pin(); |
63 | | self.inner.contains_key(key, guard) |
64 | | } |
65 | | |
66 | | /// Returns an entry with the specified `key`. |
67 | | pub fn get<Q>(&self, key: &Q) -> Option<Entry<'_, K, V>> |
68 | | where |
69 | | K: Borrow<Q>, |
70 | | Q: Ord + ?Sized, |
71 | | { |
72 | | let guard = &epoch::pin(); |
73 | | try_pin_loop(|| self.inner.get(key, guard)).map(Entry::new) |
74 | | } |
75 | | |
76 | | /// Returns an `Entry` pointing to the lowest element whose key is above |
77 | | /// the given bound. If no such element is found then `None` is |
78 | | /// returned. |
79 | | pub fn lower_bound<'a, Q>(&'a self, bound: Bound<&Q>) -> Option<Entry<'a, K, V>> |
80 | | where |
81 | | K: Borrow<Q>, |
82 | | Q: Ord + ?Sized, |
83 | | { |
84 | | let guard = &epoch::pin(); |
85 | | try_pin_loop(|| self.inner.lower_bound(bound, guard)).map(Entry::new) |
86 | | } |
87 | | |
88 | | /// Returns an `Entry` pointing to the highest element whose key is below |
89 | | /// the given bound. If no such element is found then `None` is |
90 | | /// returned. |
91 | | pub fn upper_bound<'a, Q>(&'a self, bound: Bound<&Q>) -> Option<Entry<'a, K, V>> |
92 | | where |
93 | | K: Borrow<Q>, |
94 | | Q: Ord + ?Sized, |
95 | | { |
96 | | let guard = &epoch::pin(); |
97 | | try_pin_loop(|| self.inner.upper_bound(bound, guard)).map(Entry::new) |
98 | | } |
99 | | |
100 | | /// Finds an entry with the specified key, or inserts a new `key`-`value` pair if none exist. |
101 | | pub fn get_or_insert(&self, key: K, value: V) -> Entry<'_, K, V> { |
102 | | let guard = &epoch::pin(); |
103 | | Entry::new(self.inner.get_or_insert(key, value, guard)) |
104 | | } |
105 | | |
106 | | /// Returns an iterator over all entries in the map. |
107 | 4 | pub fn iter(&self) -> Iter<'_, K, V> { |
108 | 4 | Iter { |
109 | 4 | inner: self.inner.ref_iter(), |
110 | 4 | } |
111 | 4 | } |
112 | | |
113 | | /// Returns an iterator over a subset of entries in the skip list. |
114 | 33 | pub fn range<Q, R>(&self, range: R) -> Range<'_, Q, R, K, V> |
115 | 33 | where |
116 | 33 | K: Borrow<Q>, |
117 | 33 | R: RangeBounds<Q>, |
118 | 33 | Q: Ord + ?Sized, |
119 | 33 | { |
120 | 33 | Range { |
121 | 33 | inner: self.inner.ref_range(range), |
122 | 33 | } |
123 | 33 | } <crossbeam_skiplist::map::SkipMap<i32, i32>>::range::<i32, core::ops::range::RangeFull> Line | Count | Source | 114 | 1 | pub fn range<Q, R>(&self, range: R) -> Range<'_, Q, R, K, V> | 115 | 1 | where | 116 | 1 | K: Borrow<Q>, | 117 | 1 | R: RangeBounds<Q>, | 118 | 1 | Q: Ord + ?Sized, | 119 | 1 | { | 120 | 1 | Range { | 121 | 1 | inner: self.inner.ref_range(range), | 122 | 1 | } | 123 | 1 | } |
<crossbeam_skiplist::map::SkipMap<i32, i32>>::range::<i32, (core::ops::range::Bound<&i32>, core::ops::range::Bound<&i32>)> Line | Count | Source | 114 | 32 | pub fn range<Q, R>(&self, range: R) -> Range<'_, Q, R, K, V> | 115 | 32 | where | 116 | 32 | K: Borrow<Q>, | 117 | 32 | R: RangeBounds<Q>, | 118 | 32 | Q: Ord + ?Sized, | 119 | 32 | { | 120 | 32 | Range { | 121 | 32 | inner: self.inner.ref_range(range), | 122 | 32 | } | 123 | 32 | } |
|
124 | | } |
125 | | |
126 | | impl<K, V> SkipMap<K, V> |
127 | | where |
128 | | K: Ord + Send + 'static, |
129 | | V: Send + 'static, |
130 | | { |
131 | | /// Inserts a `key`-`value` pair into the map and returns the new entry. |
132 | | /// |
133 | | /// If there is an existing entry with this key, it will be removed before inserting the new |
134 | | /// one. |
135 | 23 | pub fn insert(&self, key: K, value: V) -> Entry<'_, K, V> { |
136 | 23 | let guard = &epoch::pin(); |
137 | 23 | Entry::new(self.inner.insert(key, value, guard)) |
138 | 23 | } <crossbeam_skiplist::map::SkipMap<i32, i32>>::insert Line | Count | Source | 135 | 20 | pub fn insert(&self, key: K, value: V) -> Entry<'_, K, V> { | 136 | 20 | let guard = &epoch::pin(); | 137 | 20 | Entry::new(self.inner.insert(key, value, guard)) | 138 | 20 | } |
<crossbeam_skiplist::map::SkipMap<i32, ()>>::insert Line | Count | Source | 135 | 3 | pub fn insert(&self, key: K, value: V) -> Entry<'_, K, V> { | 136 | 3 | let guard = &epoch::pin(); | 137 | 3 | Entry::new(self.inner.insert(key, value, guard)) | 138 | 3 | } |
|
139 | | |
140 | | /// Removes an entry with the specified `key` from the map and returns it. |
141 | 4 | pub fn remove<Q>(&self, key: &Q) -> Option<Entry<'_, K, V>> |
142 | 4 | where |
143 | 4 | K: Borrow<Q>, |
144 | 4 | Q: Ord + ?Sized, |
145 | 4 | { |
146 | 4 | let guard = &epoch::pin(); |
147 | 4 | self.inner.remove(key, guard).map(Entry::new) |
148 | 4 | } |
149 | | |
150 | | /// Removes an entry from the front of the map. |
151 | | pub fn pop_front(&self) -> Option<Entry<'_, K, V>> { |
152 | | let guard = &epoch::pin(); |
153 | | self.inner.pop_front(guard).map(Entry::new) |
154 | | } |
155 | | |
156 | | /// Removes an entry from the back of the map. |
157 | | pub fn pop_back(&self) -> Option<Entry<'_, K, V>> { |
158 | | let guard = &epoch::pin(); |
159 | | self.inner.pop_back(guard).map(Entry::new) |
160 | | } |
161 | | |
162 | | /// Iterates over the map and removes every entry. |
163 | | pub fn clear(&self) { |
164 | | let guard = &mut epoch::pin(); |
165 | | self.inner.clear(guard); |
166 | | } |
167 | | } |
168 | | |
169 | | impl<K, V> Default for SkipMap<K, V> { |
170 | | fn default() -> SkipMap<K, V> { |
171 | | SkipMap::new() |
172 | | } |
173 | | } |
174 | | |
175 | | impl<K, V> fmt::Debug for SkipMap<K, V> |
176 | | where |
177 | | K: Ord + fmt::Debug, |
178 | | V: fmt::Debug, |
179 | | { |
180 | | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
181 | | f.pad("SkipMap { .. }") |
182 | | } |
183 | | } |
184 | | |
185 | | impl<K, V> IntoIterator for SkipMap<K, V> { |
186 | | type Item = (K, V); |
187 | | type IntoIter = IntoIter<K, V>; |
188 | | |
189 | | fn into_iter(self) -> IntoIter<K, V> { |
190 | | IntoIter { |
191 | | inner: self.inner.into_iter(), |
192 | | } |
193 | | } |
194 | | } |
195 | | |
196 | | impl<'a, K, V> IntoIterator for &'a SkipMap<K, V> |
197 | | where |
198 | | K: Ord, |
199 | | { |
200 | | type Item = Entry<'a, K, V>; |
201 | | type IntoIter = Iter<'a, K, V>; |
202 | | |
203 | | fn into_iter(self) -> Iter<'a, K, V> { |
204 | | self.iter() |
205 | | } |
206 | | } |
207 | | |
208 | | impl<K, V> FromIterator<(K, V)> for SkipMap<K, V> |
209 | | where |
210 | | K: Ord, |
211 | | { |
212 | | fn from_iter<I>(iter: I) -> SkipMap<K, V> |
213 | | where |
214 | | I: IntoIterator<Item = (K, V)>, |
215 | | { |
216 | | let s = SkipMap::new(); |
217 | | for (k, v) in iter { |
218 | | s.get_or_insert(k, v); |
219 | | } |
220 | | s |
221 | | } |
222 | | } |
223 | | |
224 | | /// A reference-counted entry in a map. |
225 | | pub struct Entry<'a, K, V> { |
226 | | inner: ManuallyDrop<base::RefEntry<'a, K, V>>, |
227 | | } |
228 | | |
229 | | impl<'a, K, V> Entry<'a, K, V> { |
230 | 169 | fn new(inner: base::RefEntry<'a, K, V>) -> Entry<'a, K, V> { |
231 | 169 | Entry { |
232 | 169 | inner: ManuallyDrop::new(inner), |
233 | 169 | } |
234 | 169 | } <crossbeam_skiplist::map::Entry<i32, i32>>::new Line | Count | Source | 230 | 166 | fn new(inner: base::RefEntry<'a, K, V>) -> Entry<'a, K, V> { | 231 | 166 | Entry { | 232 | 166 | inner: ManuallyDrop::new(inner), | 233 | 166 | } | 234 | 166 | } |
<crossbeam_skiplist::map::Entry<i32, ()>>::new Line | Count | Source | 230 | 3 | fn new(inner: base::RefEntry<'a, K, V>) -> Entry<'a, K, V> { | 231 | 3 | Entry { | 232 | 3 | inner: ManuallyDrop::new(inner), | 233 | 3 | } | 234 | 3 | } |
|
235 | | |
236 | | /// Returns a reference to the key. |
237 | 11 | pub fn key(&self) -> &K { |
238 | 11 | self.inner.key() |
239 | 11 | } |
240 | | |
241 | | /// Returns a reference to the value. |
242 | 131 | pub fn value(&self) -> &V { |
243 | 131 | self.inner.value() |
244 | 131 | } |
245 | | |
246 | | /// Returns `true` if the entry is removed from the map. |
247 | | pub fn is_removed(&self) -> bool { |
248 | | self.inner.is_removed() |
249 | | } |
250 | | } |
251 | | |
252 | | impl<K, V> Drop for Entry<'_, K, V> { |
253 | 169 | fn drop(&mut self) { |
254 | 169 | unsafe { |
255 | 169 | ManuallyDrop::into_inner(ptr::read(&self.inner)).release_with_pin(epoch::pin); |
256 | 169 | } |
257 | 169 | } <crossbeam_skiplist::map::Entry<i32, i32> as core::ops::drop::Drop>::drop Line | Count | Source | 253 | 166 | fn drop(&mut self) { | 254 | 166 | unsafe { | 255 | 166 | ManuallyDrop::into_inner(ptr::read(&self.inner)).release_with_pin(epoch::pin); | 256 | 166 | } | 257 | 166 | } |
<crossbeam_skiplist::map::Entry<i32, ()> as core::ops::drop::Drop>::drop Line | Count | Source | 253 | 3 | fn drop(&mut self) { | 254 | 3 | unsafe { | 255 | 3 | ManuallyDrop::into_inner(ptr::read(&self.inner)).release_with_pin(epoch::pin); | 256 | 3 | } | 257 | 3 | } |
|
258 | | } |
259 | | |
260 | | impl<'a, K, V> Entry<'a, K, V> |
261 | | where |
262 | | K: Ord, |
263 | | { |
264 | | /// Moves to the next entry in the map. |
265 | | pub fn move_next(&mut self) -> bool { |
266 | | let guard = &epoch::pin(); |
267 | | self.inner.move_next(guard) |
268 | | } |
269 | | |
270 | | /// Moves to the previous entry in the map. |
271 | | pub fn move_prev(&mut self) -> bool { |
272 | | let guard = &epoch::pin(); |
273 | | self.inner.move_prev(guard) |
274 | | } |
275 | | |
276 | | /// Returns the next entry in the map. |
277 | | pub fn next(&self) -> Option<Entry<'a, K, V>> { |
278 | | let guard = &epoch::pin(); |
279 | | self.inner.next(guard).map(Entry::new) |
280 | | } |
281 | | |
282 | | /// Returns the previous entry in the map. |
283 | | pub fn prev(&self) -> Option<Entry<'a, K, V>> { |
284 | | let guard = &epoch::pin(); |
285 | | self.inner.prev(guard).map(Entry::new) |
286 | | } |
287 | | } |
288 | | |
289 | | impl<K, V> Entry<'_, K, V> |
290 | | where |
291 | | K: Ord + Send + 'static, |
292 | | V: Send + 'static, |
293 | | { |
294 | | /// Removes the entry from the map. |
295 | | /// |
296 | | /// Returns `true` if this call removed the entry and `false` if it was already removed. |
297 | | pub fn remove(&self) -> bool { |
298 | | let guard = &epoch::pin(); |
299 | | self.inner.remove(guard) |
300 | | } |
301 | | } |
302 | | |
303 | | impl<'a, K, V> Clone for Entry<'a, K, V> { |
304 | | fn clone(&self) -> Entry<'a, K, V> { |
305 | | Entry { |
306 | | inner: self.inner.clone(), |
307 | | } |
308 | | } |
309 | | } |
310 | | |
311 | | impl<K, V> fmt::Debug for Entry<'_, K, V> |
312 | | where |
313 | | K: fmt::Debug, |
314 | | V: fmt::Debug, |
315 | | { |
316 | | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
317 | | f.debug_tuple("Entry") |
318 | | .field(self.key()) |
319 | | .field(self.value()) |
320 | | .finish() |
321 | | } |
322 | | } |
323 | | |
324 | | /// An owning iterator over the entries of a `SkipMap`. |
325 | | pub struct IntoIter<K, V> { |
326 | | inner: base::IntoIter<K, V>, |
327 | | } |
328 | | |
329 | | impl<K, V> Iterator for IntoIter<K, V> { |
330 | | type Item = (K, V); |
331 | | |
332 | | fn next(&mut self) -> Option<(K, V)> { |
333 | | self.inner.next() |
334 | | } |
335 | | } |
336 | | |
337 | | impl<K, V> fmt::Debug for IntoIter<K, V> { |
338 | | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
339 | | f.pad("IntoIter { .. }") |
340 | | } |
341 | | } |
342 | | |
343 | | /// An iterator over the entries of a `SkipMap`. |
344 | | pub struct Iter<'a, K, V> { |
345 | | inner: base::RefIter<'a, K, V>, |
346 | | } |
347 | | |
348 | | impl<'a, K, V> Iterator for Iter<'a, K, V> |
349 | | where |
350 | | K: Ord, |
351 | | { |
352 | | type Item = Entry<'a, K, V>; |
353 | | |
354 | 24 | fn next(&mut self) -> Option<Entry<'a, K, V>> { |
355 | 24 | let guard = &epoch::pin(); |
356 | 24 | self.inner.next(guard).map(Entry::new) |
357 | 24 | } |
358 | | } |
359 | | |
360 | | impl<'a, K, V> DoubleEndedIterator for Iter<'a, K, V> |
361 | | where |
362 | | K: Ord, |
363 | | { |
364 | 11 | fn next_back(&mut self) -> Option<Entry<'a, K, V>> { |
365 | 11 | let guard = &epoch::pin(); |
366 | 11 | self.inner.next_back(guard).map(Entry::new) |
367 | 11 | } |
368 | | } |
369 | | |
370 | | impl<K, V> fmt::Debug for Iter<'_, K, V> { |
371 | | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
372 | | f.pad("Iter { .. }") |
373 | | } |
374 | | } |
375 | | |
376 | | /// An iterator over the entries of a `SkipMap`. |
377 | | pub struct Range<'a, Q, R, K, V> |
378 | | where |
379 | | K: Ord + Borrow<Q>, |
380 | | R: RangeBounds<Q>, |
381 | | Q: Ord + ?Sized, |
382 | | { |
383 | | pub(crate) inner: base::RefRange<'a, Q, R, K, V>, |
384 | | } |
385 | | |
386 | | impl<'a, Q, R, K, V> Iterator for Range<'a, Q, R, K, V> |
387 | | where |
388 | | K: Ord + Borrow<Q>, |
389 | | R: RangeBounds<Q>, |
390 | | Q: Ord + ?Sized, |
391 | | { |
392 | | type Item = Entry<'a, K, V>; |
393 | | |
394 | 144 | fn next(&mut self) -> Option<Entry<'a, K, V>> { |
395 | 144 | let guard = &epoch::pin(); |
396 | 144 | self.inner.next(guard).map(Entry::new) |
397 | 144 | } <crossbeam_skiplist::map::Range<i32, (core::ops::range::Bound<&i32>, core::ops::range::Bound<&i32>), i32, i32> as core::iter::traits::iterator::Iterator>::next Line | Count | Source | 394 | 133 | fn next(&mut self) -> Option<Entry<'a, K, V>> { | 395 | 133 | let guard = &epoch::pin(); | 396 | 133 | self.inner.next(guard).map(Entry::new) | 397 | 133 | } |
<crossbeam_skiplist::map::Range<i32, core::ops::range::RangeFull, i32, i32> as core::iter::traits::iterator::Iterator>::next Line | Count | Source | 394 | 11 | fn next(&mut self) -> Option<Entry<'a, K, V>> { | 395 | 11 | let guard = &epoch::pin(); | 396 | 11 | self.inner.next(guard).map(Entry::new) | 397 | 11 | } |
|
398 | | } |
399 | | |
400 | | impl<'a, Q, R, K, V> DoubleEndedIterator for Range<'a, Q, R, K, V> |
401 | | where |
402 | | K: Ord + Borrow<Q>, |
403 | | R: RangeBounds<Q>, |
404 | | Q: Ord + ?Sized, |
405 | | { |
406 | | fn next_back(&mut self) -> Option<Entry<'a, K, V>> { |
407 | | let guard = &epoch::pin(); |
408 | | self.inner.next_back(guard).map(Entry::new) |
409 | | } |
410 | | } |
411 | | |
412 | | impl<Q, R, K, V> fmt::Debug for Range<'_, Q, R, K, V> |
413 | | where |
414 | | K: Ord + Borrow<Q> + fmt::Debug, |
415 | | V: fmt::Debug, |
416 | | R: RangeBounds<Q> + fmt::Debug, |
417 | | Q: Ord + ?Sized, |
418 | | { |
419 | | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
420 | | f.debug_struct("Range") |
421 | | .field("range", &self.inner.range) |
422 | | .field("head", &self.inner.head) |
423 | | .field("tail", &self.inner.tail) |
424 | | .finish() |
425 | | } |
426 | | } |