dashmap/set.rs
1use crate::iter_set::{Iter, OwningIter};
2#[cfg(feature = "raw-api")]
3use crate::lock::RwLock;
4use crate::setref::one::Ref;
5use crate::DashMap;
6#[cfg(feature = "raw-api")]
7use crate::HashMap;
8use cfg_if::cfg_if;
9use core::borrow::Borrow;
10use core::fmt;
11use core::hash::{BuildHasher, Hash};
12use core::iter::FromIterator;
13#[cfg(feature = "raw-api")]
14use crossbeam_utils::CachePadded;
15use std::collections::hash_map::RandomState;
16
17/// DashSet is a thin wrapper around [`DashMap`] using `()` as the value type. It uses
18/// methods and types which are more convenient to work with on a set.
19///
20/// [`DashMap`]: struct.DashMap.html
21pub struct DashSet<K, S = RandomState> {
22 pub(crate) inner: DashMap<K, (), S>,
23}
24
25impl<K: Eq + Hash + fmt::Debug, S: BuildHasher + Clone> fmt::Debug for DashSet<K, S> {
26 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
27 fmt::Debug::fmt(&self.inner, f)
28 }
29}
30
31impl<K: Eq + Hash + Clone, S: Clone> Clone for DashSet<K, S> {
32 fn clone(&self) -> Self {
33 Self {
34 inner: self.inner.clone(),
35 }
36 }
37
38 fn clone_from(&mut self, source: &Self) {
39 self.inner.clone_from(&source.inner)
40 }
41}
42
43impl<K, S> Default for DashSet<K, S>
44where
45 K: Eq + Hash,
46 S: Default + BuildHasher + Clone,
47{
48 fn default() -> Self {
49 Self::with_hasher(Default::default())
50 }
51}
52
53impl<'a, K: 'a + Eq + Hash> DashSet<K, RandomState> {
54 /// Creates a new DashSet with a capacity of 0.
55 ///
56 /// # Examples
57 ///
58 /// ```
59 /// use dashmap::DashSet;
60 ///
61 /// let games = DashSet::new();
62 /// games.insert("Veloren");
63 /// ```
64 pub fn new() -> Self {
65 Self::with_hasher(RandomState::default())
66 }
67
68 /// Creates a new DashMap with a specified starting capacity.
69 ///
70 /// # Examples
71 ///
72 /// ```
73 /// use dashmap::DashSet;
74 ///
75 /// let numbers = DashSet::with_capacity(2);
76 /// numbers.insert(2);
77 /// numbers.insert(8);
78 /// ```
79 pub fn with_capacity(capacity: usize) -> Self {
80 Self::with_capacity_and_hasher(capacity, RandomState::default())
81 }
82}
83
84impl<'a, K: 'a + Eq + Hash, S: BuildHasher + Clone> DashSet<K, S> {
85 /// Creates a new DashMap with a capacity of 0 and the provided hasher.
86 ///
87 /// # Examples
88 ///
89 /// ```
90 /// use dashmap::DashSet;
91 /// use std::collections::hash_map::RandomState;
92 ///
93 /// let s = RandomState::new();
94 /// let games = DashSet::with_hasher(s);
95 /// games.insert("Veloren");
96 /// ```
97 pub fn with_hasher(hasher: S) -> Self {
98 Self::with_capacity_and_hasher(0, hasher)
99 }
100
101 /// Creates a new DashMap with a specified starting capacity and hasher.
102 ///
103 /// # Examples
104 ///
105 /// ```
106 /// use dashmap::DashSet;
107 /// use std::collections::hash_map::RandomState;
108 ///
109 /// let s = RandomState::new();
110 /// let numbers = DashSet::with_capacity_and_hasher(2, s);
111 /// numbers.insert(2);
112 /// numbers.insert(8);
113 /// ```
114 pub fn with_capacity_and_hasher(capacity: usize, hasher: S) -> Self {
115 Self {
116 inner: DashMap::with_capacity_and_hasher(capacity, hasher),
117 }
118 }
119
120 /// Hash a given item to produce a usize.
121 /// Uses the provided or default HashBuilder.
122 pub fn hash_usize<T: Hash>(&self, item: &T) -> usize {
123 self.inner.hash_usize(item)
124 }
125
126 cfg_if! {
127 if #[cfg(feature = "raw-api")] {
128 /// Allows you to peek at the inner shards that store your data.
129 /// You should probably not use this unless you know what you are doing.
130 ///
131 /// Requires the `raw-api` feature to be enabled.
132 ///
133 /// # Examples
134 ///
135 /// ```
136 /// use dashmap::DashSet;
137 ///
138 /// let set = DashSet::<()>::new();
139 /// println!("Amount of shards: {}", set.shards().len());
140 /// ```
141 pub fn shards(&self) -> &[CachePadded<RwLock<HashMap<K, ()>>>] {
142 self.inner.shards()
143 }
144 }
145 }
146
147 cfg_if! {
148 if #[cfg(feature = "raw-api")] {
149 /// Finds which shard a certain key is stored in.
150 /// You should probably not use this unless you know what you are doing.
151 /// Note that shard selection is dependent on the default or provided HashBuilder.
152 ///
153 /// Requires the `raw-api` feature to be enabled.
154 ///
155 /// # Examples
156 ///
157 /// ```
158 /// use dashmap::DashSet;
159 ///
160 /// let set = DashSet::new();
161 /// set.insert("coca-cola");
162 /// println!("coca-cola is stored in shard: {}", set.determine_map("coca-cola"));
163 /// ```
164 pub fn determine_map<Q>(&self, key: &Q) -> usize
165 where
166 K: Borrow<Q>,
167 Q: Hash + Eq + ?Sized,
168 {
169 self.inner.determine_map(key)
170 }
171 }
172 }
173
174 cfg_if! {
175 if #[cfg(feature = "raw-api")] {
176 /// Finds which shard a certain hash is stored in.
177 ///
178 /// Requires the `raw-api` feature to be enabled.
179 ///
180 /// # Examples
181 ///
182 /// ```
183 /// use dashmap::DashSet;
184 ///
185 /// let set: DashSet<i32> = DashSet::new();
186 /// let key = "key";
187 /// let hash = set.hash_usize(&key);
188 /// println!("hash is stored in shard: {}", set.determine_shard(hash));
189 /// ```
190 pub fn determine_shard(&self, hash: usize) -> usize {
191 self.inner.determine_shard(hash)
192 }
193 }
194 }
195
196 /// Inserts a key into the set. Returns true if the key was not already in the set.
197 ///
198 /// # Examples
199 ///
200 /// ```
201 /// use dashmap::DashSet;
202 ///
203 /// let set = DashSet::new();
204 /// set.insert("I am the key!");
205 /// ```
206 pub fn insert(&self, key: K) -> bool {
207 self.inner.insert(key, ()).is_none()
208 }
209
210 /// Removes an entry from the map, returning the key if it existed in the map.
211 ///
212 /// # Examples
213 ///
214 /// ```
215 /// use dashmap::DashSet;
216 ///
217 /// let soccer_team = DashSet::new();
218 /// soccer_team.insert("Jack");
219 /// assert_eq!(soccer_team.remove("Jack").unwrap(), "Jack");
220 /// ```
221 pub fn remove<Q>(&self, key: &Q) -> Option<K>
222 where
223 K: Borrow<Q>,
224 Q: Hash + Eq + ?Sized,
225 {
226 self.inner.remove(key).map(|(k, _)| k)
227 }
228
229 /// Removes an entry from the set, returning the key
230 /// if the entry existed and the provided conditional function returned true.
231 ///
232 /// ```
233 /// use dashmap::DashSet;
234 ///
235 /// let soccer_team = DashSet::new();
236 /// soccer_team.insert("Sam");
237 /// soccer_team.remove_if("Sam", |player| player.starts_with("Ja"));
238 /// assert!(soccer_team.contains("Sam"));
239 /// ```
240 /// ```
241 /// use dashmap::DashSet;
242 ///
243 /// let soccer_team = DashSet::new();
244 /// soccer_team.insert("Sam");
245 /// soccer_team.remove_if("Jacob", |player| player.starts_with("Ja"));
246 /// assert!(!soccer_team.contains("Jacob"));
247 /// ```
248 pub fn remove_if<Q>(&self, key: &Q, f: impl FnOnce(&K) -> bool) -> Option<K>
249 where
250 K: Borrow<Q>,
251 Q: Hash + Eq + ?Sized,
252 {
253 // TODO: Don't create another closure around f
254 self.inner.remove_if(key, |k, _| f(k)).map(|(k, _)| k)
255 }
256
257 /// Creates an iterator over a DashMap yielding immutable references.
258 ///
259 /// # Examples
260 ///
261 /// ```
262 /// use dashmap::DashSet;
263 ///
264 /// let words = DashSet::new();
265 /// words.insert("hello");
266 /// assert_eq!(words.iter().count(), 1);
267 /// ```
268 pub fn iter(&'a self) -> Iter<'a, K, S, DashMap<K, (), S>> {
269 let iter = self.inner.iter();
270
271 Iter::new(iter)
272 }
273
274 /// Get a reference to an entry in the set
275 ///
276 /// # Examples
277 ///
278 /// ```
279 /// use dashmap::DashSet;
280 ///
281 /// let youtubers = DashSet::new();
282 /// youtubers.insert("Bosnian Bill");
283 /// assert_eq!(*youtubers.get("Bosnian Bill").unwrap(), "Bosnian Bill");
284 /// ```
285 pub fn get<Q>(&'a self, key: &Q) -> Option<Ref<'a, K>>
286 where
287 K: Borrow<Q>,
288 Q: Hash + Eq + ?Sized,
289 {
290 self.inner.get(key).map(Ref::new)
291 }
292
293 /// Remove excess capacity to reduce memory usage.
294 pub fn shrink_to_fit(&self) {
295 self.inner.shrink_to_fit()
296 }
297
298 /// Retain elements that whose predicates return true
299 /// and discard elements whose predicates return false.
300 ///
301 /// # Examples
302 ///
303 /// ```
304 /// use dashmap::DashSet;
305 ///
306 /// let people = DashSet::new();
307 /// people.insert("Albin");
308 /// people.insert("Jones");
309 /// people.insert("Charlie");
310 /// people.retain(|name| name.contains('i'));
311 /// assert_eq!(people.len(), 2);
312 /// ```
313 pub fn retain(&self, mut f: impl FnMut(&K) -> bool) {
314 self.inner.retain(|k, _| f(k))
315 }
316
317 /// Fetches the total number of keys stored in the set.
318 ///
319 /// # Examples
320 ///
321 /// ```
322 /// use dashmap::DashSet;
323 ///
324 /// let people = DashSet::new();
325 /// people.insert("Albin");
326 /// people.insert("Jones");
327 /// people.insert("Charlie");
328 /// assert_eq!(people.len(), 3);
329 /// ```
330 pub fn len(&self) -> usize {
331 self.inner.len()
332 }
333
334 /// Checks if the set is empty or not.
335 ///
336 /// # Examples
337 ///
338 /// ```
339 /// use dashmap::DashSet;
340 ///
341 /// let map = DashSet::<()>::new();
342 /// assert!(map.is_empty());
343 /// ```
344 pub fn is_empty(&self) -> bool {
345 self.inner.is_empty()
346 }
347
348 /// Removes all keys in the set.
349 ///
350 /// # Examples
351 ///
352 /// ```
353 /// use dashmap::DashSet;
354 ///
355 /// let people = DashSet::new();
356 /// people.insert("Albin");
357 /// assert!(!people.is_empty());
358 /// people.clear();
359 /// assert!(people.is_empty());
360 /// ```
361 pub fn clear(&self) {
362 self.inner.clear()
363 }
364
365 /// Returns how many keys the set can store without reallocating.
366 pub fn capacity(&self) -> usize {
367 self.inner.capacity()
368 }
369
370 /// Checks if the set contains a specific key.
371 ///
372 /// # Examples
373 ///
374 /// ```
375 /// use dashmap::DashSet;
376 ///
377 /// let people = DashSet::new();
378 /// people.insert("Dakota Cherries");
379 /// assert!(people.contains("Dakota Cherries"));
380 /// ```
381 pub fn contains<Q>(&self, key: &Q) -> bool
382 where
383 K: Borrow<Q>,
384 Q: Hash + Eq + ?Sized,
385 {
386 self.inner.contains_key(key)
387 }
388}
389
390impl<K: Eq + Hash, S: BuildHasher + Clone> IntoIterator for DashSet<K, S> {
391 type Item = K;
392
393 type IntoIter = OwningIter<K, S>;
394
395 fn into_iter(self) -> Self::IntoIter {
396 OwningIter::new(self.inner.into_iter())
397 }
398}
399
400impl<K: Eq + Hash, S: BuildHasher + Clone> Extend<K> for DashSet<K, S> {
401 fn extend<T: IntoIterator<Item = K>>(&mut self, iter: T) {
402 let iter = iter.into_iter().map(|k| (k, ()));
403
404 self.inner.extend(iter)
405 }
406}
407
408impl<K: Eq + Hash, S: BuildHasher + Clone + Default> FromIterator<K> for DashSet<K, S> {
409 fn from_iter<I: IntoIterator<Item = K>>(iter: I) -> Self {
410 let mut set = DashSet::default();
411
412 set.extend(iter);
413
414 set
415 }
416}
417
418#[cfg(feature = "typesize")]
419impl<K, S> typesize::TypeSize for DashSet<K, S>
420where
421 K: typesize::TypeSize + Eq + Hash,
422 S: typesize::TypeSize + Clone + BuildHasher,
423{
424 fn extra_size(&self) -> usize {
425 self.inner.extra_size()
426 }
427
428 typesize::if_typesize_details! {
429 fn get_collection_item_count(&self) -> Option<usize> {
430 Some(self.len())
431 }
432 }
433}
434
435#[cfg(test)]
436mod tests {
437 use crate::DashSet;
438
439 #[test]
440 fn test_basic() {
441 let set = DashSet::new();
442
443 set.insert(0);
444
445 assert_eq!(set.get(&0).as_deref(), Some(&0));
446 }
447
448 #[test]
449 fn test_default() {
450 let set: DashSet<u32> = DashSet::default();
451
452 set.insert(0);
453
454 assert_eq!(set.get(&0).as_deref(), Some(&0));
455 }
456
457 #[test]
458 fn test_multiple_hashes() {
459 let set = DashSet::<u32>::default();
460
461 for i in 0..100 {
462 assert!(set.insert(i));
463 }
464
465 for i in 0..100 {
466 assert!(!set.insert(i));
467 }
468
469 for i in 0..100 {
470 assert_eq!(Some(i), set.remove(&i));
471 }
472
473 for i in 0..100 {
474 assert_eq!(None, set.remove(&i));
475 }
476 }
477}