crossbeam-skiplist/src/set.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::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 | | } |