fast_able/
map_btree.rs

1use parking_lot::{ReentrantMutex, ReentrantMutexGuard};
2use serde::{Deserializer, Serialize, Serializer};
3use std::borrow::Borrow;
4use std::cell::UnsafeCell;
5use std::collections::{btree_map::IntoIter as MapIntoIter, btree_map::Iter as MapIter, BTreeMap};
6use std::fmt::{Debug, Formatter};
7use std::hash::Hash;
8use std::ops::{Deref, DerefMut};
9use std::sync::Arc;
10
11/// this sync map used to many reader,writer less.space-for-time strategy
12pub struct SyncBtreeMap<K: Eq + Hash, V> {
13    dirty: UnsafeCell<BTreeMap<K, V>>,
14    lock: ReentrantMutex<()>,
15}
16
17/// this is safety, dirty mutex ensure
18unsafe impl<K: Eq + Hash, V> Send for SyncBtreeMap<K, V> {}
19
20/// this is safety, dirty mutex ensure
21unsafe impl<K: Eq + Hash, V> Sync for SyncBtreeMap<K, V> {}
22
23impl<K: Eq + Hash, V> SyncBtreeMap<K, V>
24    where
25        K: Eq + Hash,
26{
27    pub fn new_arc() -> Arc<Self> {
28        Arc::new(Self::new())
29    }
30
31    pub fn new() -> Self {
32        Self {
33            dirty: UnsafeCell::new(BTreeMap::new()),
34            lock: Default::default(),
35        }
36    }
37
38    pub fn with_capacity(_capacity: usize) -> Self {
39        Self::new()
40    }
41
42    pub fn with_map(map: BTreeMap<K, V>) -> Self {
43        Self {
44            dirty: UnsafeCell::new(map),
45            lock: Default::default(),
46        }
47    }
48
49    pub fn insert(&self, k: K, v: V) -> Option<V>
50        where
51            K: Ord,
52    {
53        let g = self.lock.lock();
54        let m = unsafe { &mut *self.dirty.get() };
55        let r = m.insert(k, v);
56        drop(g);
57        r
58    }
59
60    pub fn insert_mut(&mut self, k: K, v: V) -> Option<V>
61        where
62            K: Ord,
63    {
64        let m = unsafe { &mut *self.dirty.get() };
65        m.insert(k, v)
66    }
67
68    pub fn remove(&self, k: &K) -> Option<V>
69        where
70            K: Ord,
71    {
72        let g = self.lock.lock();
73        let m = unsafe { &mut *self.dirty.get() };
74        let r = m.remove(k);
75        drop(g);
76        r
77    }
78
79    pub fn remove_mut(&mut self, k: &K) -> Option<V>
80        where
81            K: Ord,
82    {
83        let m = unsafe { &mut *self.dirty.get() };
84        m.remove(k)
85    }
86
87    pub fn len(&self) -> usize {
88        unsafe { (&*self.dirty.get()).len() }
89    }
90
91    pub fn is_empty(&self) -> bool {
92        unsafe { (&*self.dirty.get()).is_empty() }
93    }
94
95    pub fn clear(&self)
96        where
97            K: Eq + Hash,
98    {
99        let g = self.lock.lock();
100        let m = unsafe { &mut *self.dirty.get() };
101        m.clear();
102        drop(g);
103    }
104
105    pub fn clear_mut(&mut self)
106        where
107            K: Eq + Hash,
108    {
109        let m = unsafe { &mut *self.dirty.get() };
110        m.clear();
111    }
112
113    pub fn shrink_to_fit(&self) {}
114
115    pub fn shrink_to_fit_mut(&mut self) {}
116
117    pub fn from(map: BTreeMap<K, V>) -> Self
118        where
119            K: Eq + Hash,
120    {
121        let s = Self::with_map(map);
122        s
123    }
124
125    /// Returns a reference to the value corresponding to the key.
126    ///
127    /// The key may be any borrowed form of the map's key type, but
128    /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
129    /// the key type.
130    ///
131    /// Since reading a map is unlocked, it is very fast
132    ///
133    /// test bench_sync_hash_map_read   ... bench:           8 ns/iter (+/- 0)
134    /// # Examples
135    ///
136    /// ```
137    /// use dark_std::sync::{SyncBtreeMap};
138    ///
139    /// let mut map = SyncBtreeMap::new();
140    /// map.insert_mut(1, "a");
141    /// assert_eq!(*map.get(&1).unwrap(), "a");
142    /// assert_eq!(map.get(&2).is_none(), true);
143    /// ```
144    #[inline]
145    pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>
146        where
147            K: Borrow<Q> + Ord,
148            Q: Hash + Eq + Ord,
149    {
150        unsafe { (&*self.dirty.get()).get(k) }
151    }
152
153    #[inline]
154    pub fn get_mut<Q: ?Sized>(&self, k: &Q) -> Option<SyncMapRefMut<'_, V>>
155        where
156            K: Borrow<Q> + Ord,
157            Q: Hash + Eq + Ord,
158    {
159        let m = unsafe { &mut *self.dirty.get() };
160        Some(SyncMapRefMut {
161            _g: self.lock.lock(),
162            value: m.get_mut(k)?,
163        })
164    }
165
166    #[inline]
167    pub fn contains_key(&self, x: &K) -> bool
168        where
169            K: PartialEq + Ord,
170    {
171        let m = unsafe { &mut *self.dirty.get() };
172        m.contains_key(x)
173    }
174
175    pub fn iter(&self) -> MapIter<'_, K, V> {
176        unsafe { (&*self.dirty.get()).iter() }
177    }
178
179    pub fn iter_mut(&self) -> IterMut<'_, K, V> {
180        let m = unsafe { &mut *self.dirty.get() };
181        return IterMut {
182            _g: self.lock.lock(),
183            inner: m.iter_mut(),
184        };
185    }
186
187    pub fn into_iter(self) -> MapIntoIter<K, V> {
188        self.dirty.into_inner().into_iter()
189    }
190
191    pub fn dirty_ref(&self) -> &BTreeMap<K, V> {
192        unsafe { &*self.dirty.get() }
193    }
194
195    pub fn into_inner(self) -> BTreeMap<K, V> {
196        self.dirty.into_inner()
197    }
198}
199
200pub struct SyncMapRefMut<'a, V> {
201    _g: ReentrantMutexGuard<'a, ()>,
202    value: &'a mut V,
203}
204
205impl<'a, V> Deref for SyncMapRefMut<'_, V> {
206    type Target = V;
207
208    fn deref(&self) -> &Self::Target {
209        self.value
210    }
211}
212
213impl<'a, V> DerefMut for SyncMapRefMut<'_, V> {
214    fn deref_mut(&mut self) -> &mut Self::Target {
215        self.value
216    }
217}
218
219impl<'a, V> Debug for SyncMapRefMut<'_, V>
220    where
221        V: Debug,
222{
223    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
224        self.value.fmt(f)
225    }
226}
227
228impl<'a, V> PartialEq<Self> for SyncMapRefMut<'_, V>
229    where
230        V: Eq,
231{
232    fn eq(&self, other: &Self) -> bool {
233        self.value.eq(&other.value)
234    }
235}
236
237impl<'a, V> Eq for SyncMapRefMut<'_, V> where V: Eq {}
238
239pub struct IterMut<'a, K, V> {
240    _g: ReentrantMutexGuard<'a, ()>,
241    inner: std::collections::btree_map::IterMut<'a, K, V>,
242}
243
244impl<'a, K, V> Deref for IterMut<'a, K, V> {
245    type Target = std::collections::btree_map::IterMut<'a, K, V>;
246
247    fn deref(&self) -> &Self::Target {
248        &self.inner
249    }
250}
251
252impl<'a, K, V> DerefMut for IterMut<'a, K, V> {
253    fn deref_mut(&mut self) -> &mut Self::Target {
254        &mut self.inner
255    }
256}
257
258impl<'a, K, V> Iterator for IterMut<'a, K, V> {
259    type Item = (&'a K, &'a mut V);
260
261    fn next(&mut self) -> Option<Self::Item> {
262        self.inner.next()
263    }
264}
265
266impl<'a, K: Eq + Hash, V> IntoIterator for &'a SyncBtreeMap<K, V> {
267    type Item = (&'a K, &'a V);
268    type IntoIter = MapIter<'a, K, V>;
269
270    fn into_iter(self) -> Self::IntoIter {
271        self.iter()
272    }
273}
274
275impl<K: Eq + Hash, V> IntoIterator for SyncBtreeMap<K, V> {
276    type Item = (K, V);
277    type IntoIter = MapIntoIter<K, V>;
278
279    fn into_iter(self) -> Self::IntoIter {
280        self.into_iter()
281    }
282}
283
284impl<K: Eq + Hash, V> From<BTreeMap<K, V>> for SyncBtreeMap<K, V> {
285    fn from(arg: BTreeMap<K, V>) -> Self {
286        Self::from(arg)
287    }
288}
289
290impl<K: Eq + Hash, V> serde::Serialize for SyncBtreeMap<K, V>
291    where
292        K: Eq + Hash + Serialize + Ord,
293        V: Serialize,
294{
295    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
296        where
297            S: Serializer,
298    {
299        self.dirty_ref().serialize(serializer)
300    }
301}
302
303impl<'de, K, V> serde::Deserialize<'de> for SyncBtreeMap<K, V>
304    where
305        K: Eq + Hash + Ord + serde::Deserialize<'de>,
306        V: serde::Deserialize<'de>,
307{
308    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
309        where
310            D: Deserializer<'de>,
311    {
312        let m = BTreeMap::deserialize(deserializer)?;
313        Ok(Self::from(m))
314    }
315}
316
317impl<K: Eq + Hash, V> Debug for SyncBtreeMap<K, V>
318    where
319        K: Eq + Hash + Debug,
320        V: Debug,
321{
322    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
323        self.dirty_ref().fmt(f)
324    }
325}
326
327pub struct BtreeIter<'a, K, V> {
328    inner: MapIter<'a, K, *const V>,
329}
330
331impl<'a, K, V> Iterator for BtreeIter<'a, K, V> {
332    type Item = (&'a K, &'a V);
333
334    fn next(&mut self) -> Option<Self::Item> {
335        match self.inner.next() {
336            None => None,
337            Some((k, v)) => Some((k, unsafe { v.as_ref().unwrap() })),
338        }
339    }
340}
341
342impl<K: Clone + Eq + Hash, V: Clone> Clone for SyncBtreeMap<K, V> {
343    fn clone(&self) -> Self {
344        let c = (*self.dirty_ref()).clone();
345        SyncBtreeMap::from(c)
346    }
347}
fast_able/map_btree.rs

fast_able/
map_btree.rs
