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