Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_hash/src/map.rs

9.5 KiB, 26 runs

created by r1870400018:357, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! A `ShardMap` is a shared array of generic sub-maps that can be independently locked for read
2//! and write operations. Access is via a key hash using the supplied hasher. The capacity is
3//! fixed at compile time and is limited to `u32::MAX`, since `u32` is the smallest common hash
4//! format for `HashForm`. A given key, value pair is assigned to a shard by taking the modulus of
5//! the `HashForm::to_u32`. Keys are provided as a byte slice but the hash bytes are stored as a
6//! `HashForm` allowing more efficient primitive representations when possible. Remapping to a
7//! different number of shards is performed via cloning. A `ShardMap` can be safely given to
8//! threads simply by wrapping it in an `Arc`.
9
10use oxedyne_fe2o3_core::{
11 prelude::*,
12 map::{
13 Map,
14 MapMut,
15 },
16};
17use oxedyne_fe2o3_iop_hash::api::{
18 Hasher,
19 HashForm,
20};
21
22use std::{
23 clone::Clone,
24 collections::BTreeMap,
25 fmt::Debug,
26 sync::{
27 RwLock,
28 RwLockReadGuard,
29 },
30};
31
32#[derive(Clone, Debug)]
33pub struct ExistingValue<K, V> {
34 pub shard: usize,
35 pub key: K,
36 pub val: V,
37 pub val_old: V,
38}
39
40impl<K, V> ExistingValue<K, V> {
41 pub fn new(
42 shard: usize,
43 key: K,
44 val: V,
45 val_old: V,
46 )
47 -> Self
48 {
49 Self {
50 shard,
51 key,
52 val,
53 val_old,
54 }
55 }
56}
57
58#[derive(Debug)]
59pub struct ShardMap<
60 const C: usize, // Capacity (maximum number of shards).
61 const S: usize, // Key hasher salt length.
62 V: Clone + Debug, // Mapped value.
63 M: MapMut<HashForm, V> + Clone + Debug,
64 H: Hasher + Send + Sync + 'static, // Key hasher.
65>{
66 pub n: usize,
67 pub shards: [Option<RwLock<M>>; C],
68 pub hasher: H,
69 pub salt: [u8; S],
70 phantom: std::marker::PhantomData<V>,
71}
72
73impl<
74 const C: usize,
75 const S: usize,
76 M: MapMut<HashForm, V> + Clone + Debug,
77 V: Clone + Debug,
78 H: Hasher + Send + Sync + 'static,
79>
80 ShardMap<C, S, V, M, H>
81{
82 const INIT: Option<RwLock<M>> = None;
83 const MAX_CAPACITY: usize = u32::MAX as usize;
84
85 pub fn new(
86 n: u32,
87 salt: [u8; S],
88 init_map: M,
89 hasher: H,
90 )
91 -> Outcome<Self>
92 {
93 if C > Self::MAX_CAPACITY {
94 return Err(err!(
95 "The specified capacity {} exceeds the (arbitrary) capacity limit of {}.",
96 C, Self::MAX_CAPACITY;
97 TooBig, Configuration));
98 }
99 let n = n as usize;
100 if n > C {
101 return Err(err!(
102 "The specified number of maps {} exceeds the capacity of {}.",
103 n, C;
104 TooBig, Input));
105 }
106 let mut result = Self {
107 n,
108 shards: [Self::INIT; C],
109 hasher,
110 salt,
111 phantom: std::marker::PhantomData,
112 };
113 for i in 0..(n as usize) {
114 result.shards[i] = Some(RwLock::new(init_map.clone()));
115 }
116 Ok(result)
117 }
118
119 pub fn key(&self, pristine: &[u8]) -> HashForm {
120 self.hasher.clone().hash(&[pristine], self.salt).as_hashform()
121 }
122
123 pub fn modulus(&self, hashform: &HashForm) -> Outcome<usize> {
124 Ok((res!(hashform.to_u32()) as usize) % self.n)
125 }
126
127 pub fn insert(&self, key: &[u8], value: V) -> Outcome<Option<ExistingValue<HashForm, V>>> {
128 let hashform = self.key(&key);
129 self.insert_using_hash(hashform, value)
130 }
131
132 //pub fn insert_using_hash(&self, key: HashForm, value: V) -> Outcome<Option<V>> {
133 // let modulus = res!(self.modulus(&key));
134 // match &self.shards[modulus] {
135 // Some(locked_map) => {
136 // let mut unlocked_map = lock_write!(locked_map);
137 // Ok((*unlocked_map).insert(key, value))
138 // },
139 // None => return Err(err!(
140 // "Shard {} has not been initialised in a \
141 // ShardMap with size {} and capacity {}.",
142 // modulus, self.n, C,
143 // ), Bug, Configuration)),
144 // }
145 //}
146
147 pub fn insert_using_hash(&self, key: HashForm, value: V) -> Outcome<Option<ExistingValue<HashForm, V>>> {
148 let modulus = res!(self.modulus(&key));
149 match &self.shards[modulus] {
150 Some(locked_map) => {
151 let mut unlocked_map = lock_write!(locked_map);
152 let existing_opt = match (*unlocked_map).get(&key) {
153 Some(value_old) => Some(ExistingValue::new(
154 modulus,
155 key.clone(),
156 value.clone(),
157 value_old.clone(),
158 )),
159 None => None,
160 };
161 let _value_opt = (*unlocked_map).insert(key, value);
162 Ok(existing_opt)
163 },
164 None => return Err(err!(
165 "Shard {} has not been initialised in a \
166 ShardMap with size {} and capacity {}.",
167 modulus, self.n, C;
168 Bug, Configuration)),
169 }
170 }
171 /// Returns the hashed key and the lock on the map. If you want to access just a reference, get
172 /// the map and lock it locally, e.g.
173 /// ```ignore
174 /// let (key, unlocked_shard) = res!(shardmap.get_lock(&k));
175 /// let opt_ref_v = unlocked_shard.get(&key);
176 /// ```
177 pub fn get_lock(&self, key: &[u8]) -> Outcome<(HashForm, RwLockReadGuard<'_, M>)> {
178 let hashform = self.key(&key);
179 let locked_map = res!(self.get_shard_using_hash(&hashform));
180 let unlocked_map = lock_read!(locked_map);
181 Ok((hashform, unlocked_map))
182 }
183
184 /// Returns an optional clone of the map value. If you want to access just a reference, get
185 /// the map and lock it locally, e.g.
186 /// ```ignore
187 /// let locked_map = res!(maps.get_shard(&p));
188 /// let unlocked_map = lock_read!(locked_map);
189 /// let opt_ref_v = unlocked_map.get(&res!(maps.key(&p))); // Some(&v)
190 /// ```
191 pub fn get_clone(&self, key: &[u8]) -> Outcome<Option<V>> {
192 let hashform = self.key(&key);
193 let locked_map = res!(self.get_shard_using_hash(&hashform));
194 let unlocked_map = lock_read!(locked_map);
195 Ok(unlocked_map.get(&hashform).cloned())
196 }
197
198 pub fn get_shard(&self, key: &[u8]) -> Outcome<&RwLock<M>> {
199 let hashform = self.key(&key);
200 self.get_shard_using_hash(&hashform)
201 }
202
203 pub fn get_shard_using_hash(&self, key: &HashForm) -> Outcome<&RwLock<M>> {
204 let modulus = res!(self.modulus(&key));
205 match &self.shards[modulus] {
206 Some(locked_map) => Ok(locked_map),
207 None => return Err(err!(
208 "Bin {} has not been initialised in a \
209 ShardMap with size {} and capacity {}.",
210 modulus, self.n, C;
211 Bug, Configuration)),
212 }
213 }
214
215 pub fn remap(&self, n2: u32) -> Outcome<Self> {
216 let result = res!(Self::new(n2, self.salt, M::empty(), self.hasher.clone()));
217 for i in 0..self.n {
218 match &self.shards[i] {
219 Some(locked_map) => {
220 let unlocked_map = lock_read!(locked_map);
221 for (k, v) in (*unlocked_map).iter() {
222 let modulus = (res!(k.to_u32()) as usize) % result.n;
223 match &result.shards[modulus] {
224 Some(locked_map2) => {
225 let mut unlocked_map2 = lock_write!(locked_map2);
226 unlocked_map2.insert(k.clone(), v.clone());
227 },
228 None => return Err(err!(
229 "Bin {} has not been initialised in the new \
230 ShardMap with size {} and capacity {}.",
231 modulus, result.n, C;
232 Bug, Configuration)),
233 }
234 }
235 },
236 None => return Err(err!(
237 "Bin {} has not been initialised in the existing \
238 ShardMap with size {} and capacity {}.",
239 i, self.n, C;
240 Bug, Configuration)),
241 }
242 }
243 Ok(result)
244 }
245
246 pub fn save(&self) -> Outcome<(BTreeMap<HashForm, V>, Vec<ExistingValue<HashForm, V>>)> {
247 let mut collisions = Vec::new();
248 let mut result = BTreeMap::new();
249 for i in 0..self.n {
250 match &self.shards[i] {
251 Some(locked_map) => {
252 let unlocked_map = lock_read!(locked_map);
253 for (k, v) in (*unlocked_map).iter() {
254 if let Some(v_old) = result.insert(k.clone(), v.clone()) {
255 collisions.push(ExistingValue::new(
256 i,
257 k.clone(),
258 v.clone(),
259 v_old,
260 ));
261 }
262 }
263 },
264 None => (),
265 }
266 }
267 Ok((result, collisions))
268 }
269
270 pub fn load<
271 SRC: Map<Vec<u8>, V>,
272 >(
273 &self,
274 src_map: SRC,
275 )
276 -> Outcome<Vec<ExistingValue<HashForm, V>>>
277 {
278 let mut existing = Vec::new();
279 for (k, v) in src_map.iter() {
280 if let Some(existing_value) = res!(self.insert(k, v.clone())) {
281 existing.push(existing_value);
282 }
283 }
284 Ok(existing)
285 }
286}