c_map/
lib.rs

1#![doc = include_str!("../README.md")]
2
3mod encapsulate;
4
5#[cfg(feature = "parking-lot")]
6use parking_lot::{RwLock, RwLockReadGuard, RwLockWriteGuard};
7#[cfg(not(feature = "parking-lot"))]
8use std::sync::{RwLock, RwLockReadGuard, RwLockWriteGuard};
9
10use std::{
11    collections::{hash_map::RandomState, HashMap as Map},
12    hash::{BuildHasher, Hash, Hasher},
13};
14
15pub use encapsulate::*;
16
17pub struct HashMap<K, V, S = RandomState> {
18    hasher: S,
19    shift: usize,
20    shards: Box<[RwLock<Map<K, V, S>>]>,
21}
22
23impl<K, V> HashMap<K, V> {
24    /// Creates an empty `HashMap`.
25    ///
26    /// The hash map is initially created with a capacity of 0, so it will not allocate until it
27    /// is first inserted into.
28    #[inline]
29    pub fn new() -> Self {
30        Self::with_hasher(RandomState::default())
31    }
32
33    /// Creates an empty `HashMap` with the specified capacity.
34    ///
35    /// The hash map will be able to hold at least `capacity` elements without
36    /// reallocating. If `capacity` is 0, the hash map will not allocate.
37    #[inline]
38    pub fn with_capacity(capacity: usize) -> Self {
39        Self::with_capacity_and_hasher(capacity, RandomState::default())
40    }
41}
42
43impl<K: Hash, V, S: BuildHasher> HashMap<K, V, S> {
44    #[inline]
45    pub fn read<'a>(&'a self, key: &'a K) -> Readable<'a, K, V, S> {
46        Readable {
47            #[cfg(not(feature = "parking-lot"))]
48            map: self.shard(key).read().unwrap(),
49            #[cfg(feature = "parking-lot")]
50            map: self.shard(key).read(),
51            key,
52        }
53    }
54
55    #[inline]
56    pub fn write(&self, key: K) -> Writeable<K, V, S> {
57        Writeable {
58            #[cfg(not(feature = "parking-lot"))]
59            map: self.shard(&key).write().unwrap(),
60            #[cfg(feature = "parking-lot")]
61            map: self.shard(&key).write(),
62            key,
63        }
64    }
65
66    #[inline]
67    pub fn shard(&self, key: &K) -> &RwLock<Map<K, V, S>> {
68        let idx = self.shard_idx(key);
69        unsafe { self.shards.get_unchecked(idx) }
70    }
71
72    pub fn shard_idx(&self, key: &K) -> usize {
73        let mut hasher = self.hasher.build_hasher();
74        key.hash(&mut hasher);
75        let hash = hasher.finish() as usize;
76        // Leave the high 7 bits for the HashBrown SIMD tag.
77        (hash << 7) >> self.shift
78    }
79}
80
81impl<K, V, S: Clone> HashMap<K, V, S> {
82    #[inline]
83    /// Get a reference to the map's shards.
84    pub fn shards(&self) -> &[RwLock<Map<K, V, S>>] {
85        self.shards.as_ref()
86    }
87
88    /// Creates an empty `HashMap` which will use the given hash builder to hash
89    /// keys.
90    ///
91    /// The created map has the default initial capacity.
92    ///
93    /// Warning: `hash_builder` is normally randomly generated, and
94    /// is designed to allow HashMaps to be resistant to attacks that
95    /// cause many collisions and very poor performance. Setting it
96    /// manually using this function can expose a DoS attack vector.
97    ///
98    /// The `hash_builder` passed should implement the [`BuildHasher`] trait for
99    /// the HashMap to be useful.
100    #[inline]
101    pub fn with_hasher(hasher: S) -> Self {
102        Self::with_capacity_and_hasher(0, hasher)
103    }
104
105    /// Creates an empty `HashMap` with the specified capacity, using `hash_builder`
106    /// to hash the keys.
107    ///
108    /// The hash map will be able to hold at least `capacity` elements without
109    /// reallocating. If `capacity` is 0, the hash map will not allocate.
110    ///
111    /// Warning: `hash_builder` is normally randomly generated, and
112    /// is designed to allow HashMaps to be resistant to attacks that
113    /// cause many collisions and very poor performance. Setting it
114    /// manually using this function can expose a DoS attack vector.
115    ///
116    /// The `hash_builder` passed should implement the [`BuildHasher`] trait for
117    /// the HashMap to be useful.
118    pub fn with_capacity_and_hasher(mut capacity: usize, hasher: S) -> Self {
119        let shard_amount = (num_cpus::get() * 4).next_power_of_two();
120        if capacity != 0 {
121            capacity = (capacity + (shard_amount - 1)) & !(shard_amount - 1);
122        }
123        Self {
124            shift: std::mem::size_of::<usize>() * 8 - shard_amount.trailing_zeros() as usize,
125            shards: (0..shard_amount)
126                .map(|_| {
127                    RwLock::new(Map::with_capacity_and_hasher(
128                        capacity / shard_amount,
129                        hasher.clone(),
130                    ))
131                })
132                .collect(),
133            hasher,
134        }
135    }
136}
137
138impl<K, V> Default for HashMap<K, V> {
139    fn default() -> Self {
140        Self::new()
141    }
142}
c_map/lib.rs

c_map/
lib.rs
