crossbeam-skiplist/src/set.rs

Source
//! TODO: docs

use std::borrow::Borrow;
use std::fmt;
use std::iter::FromIterator;
use std::ops::{Bound, RangeBounds};

use crate::map;

/// A set based on a lock-free skip list.
pub struct SkipSet<T> {
    inner: map::SkipMap<T, ()>,
}

impl<T> SkipSet<T> {
    /// Returns a new, empty set.
    pub fn new() -> SkipSet<T> {
        SkipSet {
            inner: map::SkipMap::new(),
        }
    }

    /// Returns `true` if the set is empty.
    pub fn is_empty(&self) -> bool {
        self.inner.is_empty()
    }

    /// Returns the number of entries in the set.
    ///
    /// If the set is being concurrently modified, consider the returned number just an
    /// approximation without any guarantees.
    pub fn len(&self) -> usize {
        self.inner.len()
    }
}

impl<T> SkipSet<T>
where
    T: Ord,
{
    /// Returns the entry with the smallest key.
    pub fn front(&self) -> Option<Entry<'_, T>> {
        self.inner.front().map(Entry::new)
    }

    /// Returns the entry with the largest key.
    pub fn back(&self) -> Option<Entry<'_, T>> {
        self.inner.back().map(Entry::new)
    }

    /// Returns `true` if the set contains a value for the specified key.
    pub fn contains<Q>(&self, key: &Q) -> bool
    where
        T: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        self.inner.contains_key(key)
    }

    /// Returns an entry with the specified `key`.
    pub fn get<Q>(&self, key: &Q) -> Option<Entry<'_, T>>
    where
        T: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        self.inner.get(key).map(Entry::new)
    }

    /// Returns an `Entry` pointing to the lowest element whose key is above
    /// the given bound. If no such element is found then `None` is
    /// returned.
    pub fn lower_bound<'a, Q>(&'a self, bound: Bound<&Q>) -> Option<Entry<'a, T>>
    where
        T: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        self.inner.lower_bound(bound).map(Entry::new)
    }

    /// Returns an `Entry` pointing to the highest element whose key is below
    /// the given bound. If no such element is found then `None` is
    /// returned.
    pub fn upper_bound<'a, Q>(&'a self, bound: Bound<&Q>) -> Option<Entry<'a, T>>
    where
        T: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        self.inner.upper_bound(bound).map(Entry::new)
    }

    /// Finds an entry with the specified key, or inserts a new `key`-`value` pair if none exist.
    pub fn get_or_insert(&self, key: T) -> Entry<'_, T> {
        Entry::new(self.inner.get_or_insert(key, ()))
    }

    /// Returns an iterator over all entries in the map.
    pub fn iter(&self) -> Iter<'_, T> {
        Iter {
            inner: self.inner.iter(),
        }
    }

    /// Returns an iterator over a subset of entries in the skip list.
    pub fn range<Q, R>(&self, range: R) -> Range<'_, Q, R, T>
    where
        T: Borrow<Q>,
        R: RangeBounds<Q>,
        Q: Ord + ?Sized,
    {
        Range {
            inner: self.inner.range(range),
        }
    }
}

impl<T> SkipSet<T>
where
    T: Ord + Send + 'static,
{
    /// Inserts a `key`-`value` pair into the set and returns the new entry.
    ///
    /// If there is an existing entry with this key, it will be removed before inserting the new
    /// one.
    pub fn insert(&self, key: T) -> Entry<'_, T> {
        Entry::new(self.inner.insert(key, ()))
    }

    /// Removes an entry with the specified key from the set and returns it.
    pub fn remove<Q>(&self, key: &Q) -> Option<Entry<'_, T>>
    where
        T: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        self.inner.remove(key).map(Entry::new)
    }

    /// Removes an entry from the front of the map.
    pub fn pop_front(&self) -> Option<Entry<'_, T>> {
        self.inner.pop_front().map(Entry::new)
    }

    /// Removes an entry from the back of the map.
    pub fn pop_back(&self) -> Option<Entry<'_, T>> {
        self.inner.pop_back().map(Entry::new)
    }

    /// Iterates over the set and removes every entry.
    pub fn clear(&self) {
        self.inner.clear();
    }
}

impl<T> Default for SkipSet<T> {
    fn default() -> SkipSet<T> {
        SkipSet::new()
    }
}

impl<T> fmt::Debug for SkipSet<T>
where
    T: Ord + fmt::Debug,
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.pad("SkipSet { .. }")
    }
}

impl<T> IntoIterator for SkipSet<T> {
    type Item = T;
    type IntoIter = IntoIter<T>;

    fn into_iter(self) -> IntoIter<T> {
        IntoIter {
            inner: self.inner.into_iter(),
        }
    }
}

impl<'a, T> IntoIterator for &'a SkipSet<T>
where
    T: Ord,
{
    type Item = Entry<'a, T>;
    type IntoIter = Iter<'a, T>;

    fn into_iter(self) -> Iter<'a, T> {
        self.iter()
    }
}

impl<T> FromIterator<T> for SkipSet<T>
where
    T: Ord,
{
    fn from_iter<I>(iter: I) -> SkipSet<T>
    where
        I: IntoIterator<Item = T>,
    {
        let s = SkipSet::new();
        for t in iter {
            s.get_or_insert(t);
        }
        s
    }
}

/// TODO
pub struct Entry<'a, T> {
    inner: map::Entry<'a, T, ()>,
}

impl<'a, T> Entry<'a, T> {
    fn new(inner: map::Entry<'a, T, ()>) -> Entry<'a, T> {
        Entry { inner }
    }

    /// Returns a reference to the key.
    pub fn value(&self) -> &T {
        self.inner.key()
    }

    /// Returns `true` if the entry is removed from the set.
    pub fn is_removed(&self) -> bool {
        self.inner.is_removed()
    }
}

impl<'a, T> Entry<'a, T>
where
    T: Ord,
{
    /// TODO
    pub fn move_next(&mut self) -> bool {
        self.inner.move_next()
    }

    /// TODO
    pub fn move_prev(&mut self) -> bool {
        self.inner.move_prev()
    }

    /// Returns the next entry in the set.
    pub fn next(&self) -> Option<Entry<'a, T>> {
        self.inner.next().map(Entry::new)
    }

    /// Returns the previous entry in the set.
    pub fn prev(&self) -> Option<Entry<'a, T>> {
        self.inner.prev().map(Entry::new)
    }
}

impl<T> Entry<'_, T>
where
    T: Ord + Send + 'static,
{
    /// Removes the entry from the set.
    ///
    /// Returns `true` if this call removed the entry and `false` if it was already removed.
    pub fn remove(&self) -> bool {
        self.inner.remove()
    }
}

impl<'a, T> Clone for Entry<'a, T> {
    fn clone(&self) -> Entry<'a, T> {
        Entry {
            inner: self.inner.clone(),
        }
    }
}

impl<T> fmt::Debug for Entry<'_, T>
where
    T: fmt::Debug,
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_struct("Entry")
            .field("value", self.value())
            .finish()
    }
}

/// An owning iterator over the entries of a `SkipSet`.
pub struct IntoIter<T> {
    inner: map::IntoIter<T, ()>,
}

impl<T> Iterator for IntoIter<T> {
    type Item = T;

    fn next(&mut self) -> Option<T> {
        self.inner.next().map(|(k, ())| k)
    }
}

impl<T> fmt::Debug for IntoIter<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.pad("IntoIter { .. }")
    }
}

/// An iterator over the entries of a `SkipSet`.
pub struct Iter<'a, T> {
    inner: map::Iter<'a, T, ()>,
}

impl<'a, T> Iterator for Iter<'a, T>
where
    T: Ord,
{
    type Item = Entry<'a, T>;

    fn next(&mut self) -> Option<Entry<'a, T>> {
        self.inner.next().map(Entry::new)
    }
}

impl<'a, T> DoubleEndedIterator for Iter<'a, T>
where
    T: Ord,
{
    fn next_back(&mut self) -> Option<Entry<'a, T>> {
        self.inner.next_back().map(Entry::new)
    }
}

impl<T> fmt::Debug for Iter<'_, T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.pad("Iter { .. }")
    }
}

/// An iterator over the entries of a `SkipMap`.
pub struct Range<'a, Q, R, T>
where
    T: Ord + Borrow<Q>,
    R: RangeBounds<Q>,
    Q: Ord + ?Sized,
{
    inner: map::Range<'a, Q, R, T, ()>,
}

impl<'a, Q, R, T> Iterator for Range<'a, Q, R, T>
where
    T: Ord + Borrow<Q>,
    R: RangeBounds<Q>,
    Q: Ord + ?Sized,
{
    type Item = Entry<'a, T>;

    fn next(&mut self) -> Option<Entry<'a, T>> {
        self.inner.next().map(Entry::new)
    }
}

impl<'a, Q, R, T> DoubleEndedIterator for Range<'a, Q, R, T>
where
    T: Ord + Borrow<Q>,
    R: RangeBounds<Q>,
    Q: Ord + ?Sized,
{
    fn next_back(&mut self) -> Option<Entry<'a, T>> {
        self.inner.next_back().map(Entry::new)
    }
}

impl<Q, R, T> fmt::Debug for Range<'_, Q, R, T>
where
    T: Ord + Borrow<Q> + fmt::Debug,
    R: RangeBounds<Q> + fmt::Debug,
    Q: Ord + ?Sized,
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_struct("Range")
            .field("range", &self.inner.inner.range)
            .field("head", &self.inner.inner.head.as_ref().map(|e| e.key()))
            .field("tail", &self.inner.inner.tail.as_ref().map(|e| e.key()))
            .finish()
    }
}

Coverage Report

Created: 2021-01-22 16:54

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