deepmesa_collections/lhmap/
entry.rs

1/*
2   LinkedHashMap: A fast and flexible linked HashMap that allows for
3   O(1) inserts and removes with a predictable iteration order.
4
5   Copyright 2021 "Rahul Singh <rsingh@arrsingh.com>"
6
7   Licensed under the Apache License, Version 2.0 (the "License");
8   you may not use this file except in compliance with the License.
9   You may obtain a copy of the License at
10
11       http://www.apache.org/licenses/LICENSE-2.0
12
13   Unless required by applicable law or agreed to in writing, software
14   distributed under the License is distributed on an "AS IS" BASIS,
15   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16   See the License for the specific language governing permissions and
17   limitations under the License.
18*/
19
20use crate::linkedlist::node::NodeHandle;
21use core::hash::Hash;
22use core::hash::Hasher;
23
24pub(crate) struct PtrKey<T: Hash + Eq>(*const T);
25
26impl<T: Hash + Eq> PtrKey<T> {
27    pub(crate) fn new(t: &T) -> PtrKey<T> {
28        return PtrKey(t as *const T);
29    }
30
31    pub(crate) fn from_ptr(ptr: *const T) -> PtrKey<T> {
32        return PtrKey(ptr);
33    }
34}
35
36impl<T> Hash for PtrKey<T>
37where
38    T: Hash + Eq,
39{
40    fn hash<H>(&self, h: &mut H)
41    where
42        H: Hasher,
43    {
44        unsafe {
45            (*self.0).hash(h);
46        }
47    }
48}
49
50impl<T> PartialEq for PtrKey<T>
51where
52    T: Hash + Eq,
53{
54    fn eq(&self, other: &Self) -> bool {
55        unsafe {
56            return (*(self.0)).eq(&(*other.0));
57        }
58    }
59}
60
61impl<T> Eq for PtrKey<T> where T: Hash + Eq {}
62
63/// A view into a single entry in a map. The entry is used in the
64/// evict_eldest function if one if provided. See
65/// [`eviction`](crate::map::lhmap::LinkedHashMap#evicting-elements) in the
66/// module level documentation.
67#[derive(Debug)]
68pub struct Entry<K, V> {
69    pub(crate) key: K,
70    pub(crate) val: V,
71}
72
73impl<K, V> Entry<K, V> {
74    pub(crate) fn new(k: K, v: V) -> Entry<K, V> {
75        return Entry { key: k, val: v };
76    }
77
78    pub(crate) unsafe fn key_ptr(&self) -> *const K {
79        return &self.key as *const K;
80    }
81}
82
83impl<K, V> PartialEq for Entry<K, V>
84where
85    K: PartialEq,
86    V: PartialEq,
87{
88    fn eq(&self, other: &Self) -> bool {
89        self.key == other.key && self.val == other.val
90    }
91}
92
93impl<K, V> Eq for Entry<K, V>
94where
95    K: Eq,
96    V: Eq,
97{}
98
99/// An enum used to specify the iteration order for the LinkedHashMap.
100///
101/// [`InsertionOrder`](#variant.InsertionOrder) is the order in which the
102/// keys were inserted into the map from least recently inserted
103/// (oldest) to most recently inserted (newest).
104///
105/// [`AccessOrder`](#variant.AccessOrder) is the order in which the
106/// keys in the map were last accessed from least-recently accessed
107/// (oldest) to most recently accessed (newest).
108#[derive(Debug, PartialEq, Eq)]
109pub enum Order {
110    /// LinkedHashMap iteration order from least-recently accessed to
111    /// most-recently accessed.
112    AccessOrder,
113
114    /// LinkedHashMap iteration order from least-recently inserted to
115    /// most-recently inserted.
116    InsertionOrder,
117}
118
119/// A handle to an entry in a [`LinkedHashMap`](crate::LinkedHashMap).
120///
121/// This handle wraps a [`NodeHandle`] from the underlying linked list and
122/// provides methods to manipulate the position of entries within the map's
123/// iteration order. Handles can be copied and passed around by value
124/// regardless of the lifetime of the map.
125///
126/// Once an entry is removed from the map, its handle becomes invalid.
127/// Using an invalid handle is safe - methods will return `false` or `None`
128/// to indicate the handle is no longer valid.
129///
130/// # Examples
131/// ```
132/// use deepmesa_collections::LinkedHashMap;
133/// use deepmesa_collections::lhmap::Order;
134///
135/// let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::InsertionOrder, None);
136/// lhm.put(1, "a");
137/// lhm.put(2, "b");
138///
139/// if let Some(handle) = lhm.entry_handle(&1) {
140///     // Move entry with key 1 to the end of iteration order
141///     lhm.make_tail(handle);
142/// }
143/// ```
144#[derive(Debug, Clone)]
145pub struct EntryHandle<K, V> {
146    pub(crate) node_handle: NodeHandle<Entry<K, V>>,
147}
148
149unsafe impl<K, V> Send for EntryHandle<K, V> where K: Hash + Eq {}
150unsafe impl<K, V> Sync for EntryHandle<K, V> where K: Hash + Eq {}
151
152impl<K, V> PartialEq for EntryHandle<K, V>
153where
154    K: PartialEq,
155    V: PartialEq,
156{
157    fn eq(&self, other: &Self) -> bool {
158        self.node_handle == other.node_handle
159    }
160}
161
162impl<K, V> Eq for EntryHandle<K, V>
163where
164    K: Eq,
165    V: Eq,
166{}
167
168impl<K, V> Default for EntryHandle<K, V> {
169    /// Creates a default (invalid) entry handle.
170    fn default() -> Self {
171        Self {
172            node_handle: NodeHandle::default(),
173        }
174    }
175}
176
177impl<K, V> EntryHandle<K, V>
178where
179    K: Hash + Eq,
180{
181    /// Creates a new EntryHandle wrapping the given NodeHandle.
182    pub(crate) fn new(node_handle: NodeHandle<Entry<K, V>>) -> Self {
183        Self { node_handle }
184    }
185
186}
deepmesa_collections/lhmap/entry.rs

deepmesa_collections/lhmap/
entry.rs
