linked_hash_map_rs/
lib.rs

1//! #LinkedHashMap
2//!
3//! More: [LinkedHashMap] or [src/tests.rs](https://docs.rs/crate/linked-hash-map-rs/latest/source/src/tests.rs)
4//!
5//! ```rust
6//!
7//! use linked_hash_map_rs::LinkedHashMap;
8//!
9//! let mut map = LinkedHashMap::new();
10//! map.insert(1, "a");
11//! map.insert(2, "b");
12//! map.insert(3, "c");
13//! map.get_mut(&1).map(|v| *v = "A");
14//!
15//! assert_eq!(map.get(&1), Some(&"A"));
16//! assert_eq!(map.remove(&2), Some((2, "b")));
17//! assert_eq!(map.get(&2), None);
18//! assert_eq!(map.get(&3), Some(&"c"));
19//!
20//! ```
21
22#![allow(clippy::not_unsafe_ptr_arg_deref)]
23
24use std::borrow::Borrow;
25use std::collections::HashMap;
26use std::fmt::{Debug, Formatter};
27use std::hash::{Hash, Hasher};
28use std::marker::PhantomData;
29use std::ptr::replace;
30
31#[cfg(feature = "serde")]
32mod serde;
33#[cfg(test)]
34mod tests;
35
36struct KeyPtr<K> {
37    k: *const K,
38}
39
40#[derive(Hash, PartialEq, Eq)]
41#[repr(transparent)]
42struct Qey<Q: ?Sized>(Q);
43
44impl<Q: ?Sized> Qey<Q> {
45    fn from_ref(q: &Q) -> &Self {
46        unsafe { std::mem::transmute(q) }
47    }
48}
49
50impl<K, Q: ?Sized> Borrow<Qey<Q>> for KeyPtr<K>
51    where
52        K: Borrow<Q>,
53{
54    fn borrow(&self) -> &Qey<Q> {
55        Qey::from_ref(unsafe { (*self.k).borrow() })
56    }
57}
58
59impl<K: Hash> Hash for KeyPtr<K> {
60    fn hash<H: Hasher>(&self, state: &mut H) {
61        unsafe { (*self.k).hash(state) }
62    }
63}
64
65impl<K: PartialEq> PartialEq for KeyPtr<K> {
66    fn eq(&self, other: &Self) -> bool {
67        unsafe { (*self.k).eq(&*other.k) }
68    }
69}
70
71impl<K: Eq> Eq for KeyPtr<K> {}
72
73pub struct LinkedHashMap<K, V, S = std::collections::hash_map::RandomState> {
74    hash_map: HashMap<KeyPtr<K>, *mut Node<K, V>, S>,
75    head: Option<*mut Node<K, V>>,
76    tail: Option<*mut Node<K, V>>,
77    marker: PhantomData<Node<K, V>>,
78}
79
80pub struct Node<K, V> {
81    key: K,
82    value: V,
83    prev: Option<*mut Node<K, V>>,
84    next: Option<*mut Node<K, V>>,
85}
86
87impl<K, V> Node<K, V> {
88    pub fn into_ptr(_self: Self) -> *mut Self {
89        Box::into_raw(Box::new(_self))
90    }
91}
92
93impl<K, V, S> LinkedHashMap<K, V, S> {
94    pub fn with_hasher(hasher: S) -> LinkedHashMap<K, V, S> {
95        LinkedHashMap {
96            hash_map: HashMap::with_hasher(hasher),
97            head: None,
98            tail: None,
99            marker: Default::default(),
100        }
101    }
102
103    pub fn with_capacity_and_hasher(capacity: usize, hasher: S) -> Self {
104        LinkedHashMap {
105            hash_map: HashMap::with_capacity_and_hasher(capacity, hasher),
106            head: None,
107            tail: None,
108            marker: Default::default(),
109        }
110    }
111}
112
113impl<K, V> LinkedHashMap<K, V, std::collections::hash_map::RandomState>
114    where
115        K: Hash + Eq,
116{
117    pub fn new() -> Self {
118        LinkedHashMap {
119            hash_map: HashMap::new(),
120            ..Default::default()
121        }
122    }
123
124    pub fn with_capacity(capacity: usize) -> Self {
125        LinkedHashMap {
126            hash_map: HashMap::with_capacity(capacity),
127            ..Default::default()
128        }
129    }
130
131    #[inline]
132    pub fn push_front(&mut self, key: K, value: V) -> Option<(&K, V)> {
133        unsafe {
134            if let Some(node) = self.hash_map.get(&KeyPtr { k: &key }) {
135                let old = replace(&mut (**node).value, value);
136                Some((&(**node).key, old))
137            } else {
138                let node = Node::into_ptr(Node {
139                    key,
140                    value,
141                    prev: None,
142                    next: None,
143                });
144
145                self.hash_map.insert(KeyPtr { k: &(*node).key }, node);
146                self.push_front_node(node);
147                None
148            }
149        }
150    }
151
152    /// like [push_front], but return the put element instead of the replaced element
153    #[inline]
154    pub fn push_front_and_return(&mut self, key: K, value: V) -> (&K, &V) {
155        unsafe {
156            if let Some(node) = self.hash_map.get(&KeyPtr { k: &key }) {
157                replace(&mut (**node).value, value);
158                (&(**node).key, &(**node).value)
159            } else {
160                let node = Node::into_ptr(Node {
161                    key,
162                    value,
163                    prev: None,
164                    next: None,
165                });
166
167                self.hash_map.insert(KeyPtr { k: &(*node).key }, node);
168                self.push_front_node(node);
169                (&(*node).key, &(*node).value)
170            }
171        }
172    }
173
174    #[inline]
175    unsafe fn push_front_node(&mut self, node: *mut Node<K, V>) {
176        (*node).prev = None;
177        (*node).next = self.head;
178        let node = Some(node);
179        match self.head {
180            None => self.tail = node,
181            Some(head) => (*head).prev = node,
182        }
183
184        self.head = node;
185    }
186
187    #[inline]
188    pub fn pop_front_node(&mut self) -> Option<Box<Node<K, V>>> {
189        self.head
190            .map(|node| unsafe {
191                self.head = (*node).next;
192
193                match self.head {
194                    None => self.tail = None,
195                    Some(head) => (*head).prev = None,
196                }
197
198                self.hash_map
199                    .remove(&KeyPtr { k: &(*node).key })
200                    .map(|node| Box::from_raw(node))
201            })
202            .flatten()
203    }
204
205    #[inline]
206    pub fn pop_front(&mut self) -> Option<(K, V)> {
207        self.pop_front_node().map(|node| (node.key, node.value))
208    }
209
210    #[inline]
211    pub fn front(&self) -> Option<(&K, &V)> {
212        self.head
213            .map(|node| unsafe { (&(*node).key, &(*node).value) })
214    }
215
216    #[inline]
217    pub fn push_back(&mut self, key: K, value: V) -> Option<(&K, V)> {
218        unsafe {
219            if let Some(node) = self.hash_map.get(&KeyPtr { k: &key }) {
220                let old = replace(&mut (**node).value, value);
221                Some((&(**node).key, old))
222            } else {
223                let node = Node::into_ptr(Node {
224                    key,
225                    value,
226                    prev: None,
227                    next: None,
228                });
229                self.hash_map.insert(KeyPtr { k: &(*node).key }, node);
230                self.push_back_node(node);
231                None
232            }
233        }
234    }
235
236    /// like [push_back], but return the put element instead of the replaced element
237    #[inline]
238    pub fn push_back_and_return(&mut self, key: K, value: V) -> (&K, &V) {
239        unsafe {
240            if let Some(node) = self.hash_map.get(&KeyPtr { k: &key }) {
241                replace(&mut (**node).value, value);
242                (&(**node).key, &(**node).value)
243            } else {
244                let node = Node::into_ptr(Node {
245                    key,
246                    value,
247                    prev: None,
248                    next: None,
249                });
250                self.hash_map.insert(KeyPtr { k: &(*node).key }, node);
251                self.push_back_node(node);
252                (&(*node).key, &(*node).value)
253            }
254        }
255    }
256
257    #[inline]
258    unsafe fn push_back_node(&mut self, node: *mut Node<K, V>) {
259        (*node).prev = self.tail;
260        (*node).next = None;
261        let node = Some(node);
262        if let Some(tail) = self.tail {
263            (*tail).next = node
264        } else {
265            self.head = node;
266        }
267        self.tail = node;
268    }
269
270    #[inline]
271    pub fn pop_back_node(&mut self) -> Option<Box<Node<K, V>>> {
272        self.tail
273            .map(|node| unsafe {
274                self.tail = (*node).prev;
275
276                match self.tail {
277                    None => self.head = None,
278                    Some(tail) => (*tail).next = None,
279                }
280
281                self.hash_map
282                    .remove(&KeyPtr { k: &(*node).key })
283                    .map(|node| Box::from_raw(node))
284            })
285            .flatten()
286    }
287
288    #[inline]
289    pub fn pop_back(&mut self) -> Option<(K, V)> {
290        self.pop_back_node().map(|node| (node.key, node.value))
291    }
292
293    #[inline]
294    pub fn back(&self) -> Option<(&K, &V)> {
295        self.tail
296            .map(|node| unsafe { (&(*node).key, &(*node).value) })
297    }
298
299    #[inline]
300    pub fn len(&self) -> usize {
301        self.hash_map.len()
302    }
303
304    #[inline]
305    pub fn capacity(&self) -> usize {
306        self.hash_map.capacity()
307    }
308
309    #[inline]
310    pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V>
311        where
312            K: Borrow<Q>,
313            Q: Hash + Eq,
314    {
315        self.hash_map
316            .get(Qey::from_ref(key))
317            .map(|node| unsafe { &(**node).value })
318    }
319
320    #[inline]
321    pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>
322        where
323            K: Borrow<Q>,
324            Q: Hash + Eq,
325    {
326        self.hash_map
327            .get_mut(Qey::from_ref(key))
328            .map(|node| unsafe { &mut (**node).value })
329    }
330
331    #[inline]
332    pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)>
333        where
334            K: Borrow<Q>,
335            Q: Hash + Eq,
336    {
337        self.hash_map.remove(Qey::from_ref(key)).map(|node| unsafe {
338            self.remove_node(node);
339            let node = Box::from_raw(node);
340            (node.key, node.value)
341        })
342    }
343
344    #[inline]
345    fn remove_node(&mut self, node: *mut Node<K, V>) {
346        unsafe {
347            if let Some(head) = self.head {
348                if head == node {
349                    self.head = (*head).next
350                }
351            }
352            if let Some(tail) = self.tail {
353                if tail == node {
354                    self.tail = (*tail).prev
355                }
356            }
357            if let Some(next) = (*node).next {
358                (*next).prev = (*node).prev
359            }
360            if let Some(prev) = (*node).prev {
361                (*prev).next = (*node).next
362            }
363        }
364    }
365
366    #[inline]
367    pub fn move_to_front<Q: ?Sized>(&mut self, key: &Q) -> Option<(&K, &V)>
368        where
369            K: Borrow<Q>,
370            Q: Hash + Eq,
371    {
372        self.hash_map
373            .get(Qey::from_ref(key))
374            .map(|node| *node)
375            .map(|node| unsafe {
376                self.remove_node(node);
377                self.push_front_node(node);
378                (&(*node).key, &(*node).value)
379            })
380    }
381
382    #[inline]
383    pub fn move_to_back<Q: ?Sized>(&mut self, key: &Q) -> Option<(&K, &V)>
384        where
385            K: Borrow<Q>,
386            Q: Hash + Eq,
387    {
388        self.hash_map
389            .get(Qey::from_ref(key))
390            .map(|node| *node)
391            .map(|node| unsafe {
392                self.remove_node(node);
393                self.push_back_node(node);
394                (&(*node).key, &(*node).value)
395            })
396    }
397
398    #[inline]
399    pub fn take<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)>
400        where
401            K: Borrow<Q>,
402            Q: Hash + Eq,
403    {
404        self.remove(key)
405    }
406
407    #[inline]
408    pub fn insert(&mut self, key: K, value: V) -> Option<(&K, V)> {
409        self.push_back(key, value)
410    }
411
412    #[inline]
413    pub fn insert_and_return(&mut self, key: K, value: V) -> (&K, &V) {
414        self.push_back_and_return(key, value)
415    }
416
417    #[inline]
418    pub fn contains<Q: ?Sized>(&self, key: &Q) -> bool
419        where
420            K: Borrow<Q>,
421            Q: Hash + Eq,
422    {
423        self.hash_map.contains_key(Qey::from_ref(key))
424    }
425
426    #[inline]
427    pub fn is_empty(&self) -> bool {
428        self.hash_map.is_empty() && self.head.is_none() && self.tail.is_none()
429    }
430
431    #[inline]
432    pub fn position(&self, pos: usize) -> Option<(&K, &V)> {
433        let mut next = self.head;
434        for _ in 0..pos {
435            next = next.map(|node| unsafe { (*node).next }).flatten();
436        }
437        next.map(|ptr| unsafe { (&(*ptr).key, &(*ptr).value) })
438    }
439
440    #[inline]
441    pub fn position_mut(&mut self, pos: usize) -> Option<(&mut K, &mut V)> {
442        let mut next = self.head;
443        for _ in 0..pos {
444            next = next.map(|node| unsafe { (*node).next }).flatten();
445        }
446        next.map(|ptr| unsafe { (&mut (*ptr).key, &mut (*ptr).value) })
447    }
448
449    #[inline]
450    pub fn clear(&mut self) {
451        while self.pop_back().is_some() {}
452    }
453
454    #[inline]
455    pub fn iter(&self) -> Iter<K, V> {
456        Iter {
457            head: self.head.map(|ptr| ptr as *const _),
458            marker: PhantomData,
459        }
460    }
461
462    #[inline]
463    pub fn _into_iter(mut self) -> IntoIter<K, V> {
464        let head = self.head;
465        self.head = None;
466        IntoIter {
467            head,
468            marker: PhantomData,
469        }
470    }
471}
472
473impl<K, V, S> Default for LinkedHashMap<K, V, S>
474    where
475        S: Default,
476{
477    fn default() -> Self {
478        LinkedHashMap {
479            hash_map: HashMap::default(),
480            head: None,
481            tail: None,
482            marker: PhantomData,
483        }
484    }
485}
486
487impl<K, V, S> Drop for LinkedHashMap<K, V, S> {
488    fn drop(&mut self) {
489        unsafe fn drop_node<K, V>(node: *mut Node<K, V>) {
490            let node = Box::from_raw(node);
491            if let Some(node) = node.next {
492                drop_node(node)
493            }
494        }
495        if let Some(node) = self.head {
496            unsafe { drop_node(node) }
497        }
498    }
499}
500
501pub struct Iter<'a, K: 'a, V: 'a> {
502    head: Option<*const Node<K, V>>,
503    marker: PhantomData<(&'a K, &'a V)>,
504}
505
506pub struct IntoIter<K, V> {
507    head: Option<*mut Node<K, V>>,
508    marker: PhantomData<(K, V)>,
509}
510
511impl<'a, K, V> Iterator for Iter<'a, K, V> {
512    type Item = (&'a K, &'a V);
513
514    fn next(&mut self) -> Option<Self::Item> {
515        self.head.map(|node| unsafe {
516            let kv = (&(*node).key, &(*node).value);
517            self.head = (*node).next.map(|ptr| ptr as *const _);
518            kv
519        })
520    }
521}
522
523impl<K, V> Iterator for IntoIter<K, V> {
524    type Item = (K, V);
525
526    fn next(&mut self) -> Option<Self::Item> {
527        self.head.map(|node| unsafe {
528            self.head = (*node).next;
529            let node = Box::from_raw(node);
530            (node.key, node.value)
531        })
532    }
533}
534
535impl<K, V> IntoIterator for LinkedHashMap<K, V>
536    where
537        K: Hash + Eq,
538{
539    type Item = (K, V);
540    type IntoIter = IntoIter<K, V>;
541
542    fn into_iter(self) -> Self::IntoIter {
543        self._into_iter()
544    }
545}
546
547impl<'a, K, V> IntoIterator for &'a LinkedHashMap<K, V>
548    where
549        K: Hash + Eq,
550{
551    type Item = (&'a K, &'a V);
552    type IntoIter = Iter<'a, K, V>;
553
554    fn into_iter(self) -> Iter<'a, K, V> {
555        self.iter()
556    }
557}
558
559impl<K, V> Extend<(K, V)> for LinkedHashMap<K, V>
560    where
561        K: Hash + Eq,
562{
563    fn extend<T: IntoIterator<Item=(K, V)>>(&mut self, iter: T) {
564        for (k, v) in iter {
565            self.insert(k, v);
566        }
567    }
568}
569
570impl<K, V> Clone for LinkedHashMap<K, V>
571    where
572        K: Clone + Hash + Eq,
573        V: Clone,
574{
575    fn clone(&self) -> Self {
576        let mut map =
577            LinkedHashMap::with_capacity_and_hasher(self.len(), self.hash_map.hasher().clone());
578        map.extend(self.iter().map(|(k, v)| (k.clone(), v.clone())));
579        map
580    }
581}
582
583impl<K, V> Debug for LinkedHashMap<K, V>
584    where
585        K: Debug + Hash + Eq,
586        V: Debug,
587{
588    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
589        f.debug_map().entries(self).finish()
590    }
591}
592
593impl<K, V> PartialEq for LinkedHashMap<K, V>
594    where
595        K: Hash + Eq,
596        V: PartialEq,
597{
598    fn eq(&self, other: &Self) -> bool {
599        self.len() == other.len() && self.iter().eq(other.iter())
600    }
601}
602
603impl<K, V> Eq for LinkedHashMap<K, V>
604    where
605        K: Hash + Eq,
606        V: Eq,
607{}
608
609impl<K, V> Hash for LinkedHashMap<K, V>
610    where
611        K: Hash + Eq,
612        V: Hash,
613{
614    fn hash<H: Hasher>(&self, state: &mut H) {
615        self.iter().for_each(|t| t.hash(state))
616    }
617}
618
619unsafe impl<K, V> Sync for LinkedHashMap<K, V>
620    where
621        K: Sync,
622        V: Sync,
623{}
624
625unsafe impl<K, V> Send for LinkedHashMap<K, V>
626    where
627        K: Send,
628        V: Send,
629{}
linked_hash_map_rs/lib.rs

linked_hash_map_rs/
lib.rs
