diff options
Diffstat (limited to 'matrix-lang/src/value/hash.rs')
| -rw-r--r-- | matrix-lang/src/value/hash.rs | 240 |
1 files changed, 240 insertions, 0 deletions
diff --git a/matrix-lang/src/value/hash.rs b/matrix-lang/src/value/hash.rs new file mode 100644 index 0000000..35c1343 --- /dev/null +++ b/matrix-lang/src/value/hash.rs @@ -0,0 +1,240 @@ +use crate::prelude::*; +use std::hash::{Hash, DefaultHasher, Hasher}; + +#[derive(Clone)] +pub struct ValueMap { + values: Vec<ValueEntry>, + size: usize, + used: usize, +} + +#[derive(Clone)] +enum ValueEntry { + Empty, + Taken((Value, Value)), + Gravestone(Value), +} + +impl Default for ValueMap { + fn default() -> Self { + ValueMap { + values: vec![ValueEntry::Empty; 8], + size: 8, + used: 0, + } + } +} + +impl ValueMap { + + fn get_index(values: &Vec<ValueEntry>, size: usize, key: &Value, hash: usize) -> usize { + let mut nearest_grave = None; + let start = hash & size; + for offset in 0..size { + let idx = (start + offset) % size; + match &values[idx] { + ValueEntry::Empty => return idx, + ValueEntry::Taken((marker, _)) => { + if marker.eq(key) { return idx }; + continue; + }, + ValueEntry::Gravestone(grave) => { + if grave.eq(key) { return idx }; + if nearest_grave.is_none() { + nearest_grave = Some(idx); + } + continue; + }, + } + } + + match nearest_grave { + Some(idx) => idx, + None => panic!("cannot get value map index: full!!!"), + } + } + + fn expand(&mut self) -> Result<()> { + let pairs = self.values.iter() + .filter_map(|e| { + match e { + ValueEntry::Taken(s) => Some(s.clone()), + _ => None + } + }) + .collect::<Vec<(Value, Value)>>(); + + let new_used = pairs.len(); + let new_size = self.size * 2 + pairs.len(); + let mut new_values = vec![ValueEntry::Empty; new_size]; + + for (key, value) in pairs.into_iter() { + let hash = self.hash(&key)?; + let idx = ValueMap::get_index(&new_values, new_size, &key, hash); + new_values[idx] = ValueEntry::Taken((key, value)); + } + + self.used = new_used; + self.size = new_size; + self.values = new_values; + + Ok(()) + } + + fn hash(&self, key: &Value) -> Result<usize> { + let mut hasher = DefaultHasher::new(); + key.try_hash(&mut hasher)?; + Ok(hasher.finish() as usize) + } + + pub fn get<'a>(&'a self, key: &Value) -> Result<Option<&'a Value>> { + let hash = self.hash(key)?; + let idx = ValueMap::get_index(&self.values, self.size, key, hash); + match &self.values[idx] { + ValueEntry::Taken((_, value)) => Ok(Some(value)), + _ => Ok(None) + } + } + + pub fn insert(&mut self, key: Value, value: Value) -> Result<()> { + if self.used * 3 >= self.size * 2 { + self.expand()?; + } + let key = key.deep_clone(); + let hash = self.hash(&key)?; + let idx = ValueMap::get_index(&self.values, self.size, &key, hash); + self.values[idx] = ValueEntry::Taken((key, value)); + self.used += 1; + Ok(()) + } + + pub fn remove(&mut self, key: &Value) -> Result<Option<Value>> { + let hash = self.hash(key)?; + let idx = ValueMap::get_index(&self.values, self.size, key, hash); + let mut value = ValueEntry::Gravestone(key.clone()); + std::mem::swap(&mut value, &mut self.values[idx]); + match value { + ValueEntry::Taken((_, v)) => { + self.used -= 1; + Ok(Some(v)) + } + _ => Ok(None), + } + } + + pub fn entries<'a>(&'a self) -> ValueMapIterator<'a> { + ValueMapIterator::new(self) + } + + pub fn new() -> Self { + Self::default() + } + + pub fn len(&self) -> usize { + self.used + } +} + +pub struct ValueMapIterator<'a> { + map: &'a ValueMap, + index: usize +} + +impl<'a> ValueMapIterator<'a> { + fn new(map: &'a ValueMap) -> Self { + Self { map, index: 0 } + } +} + +impl<'a> Iterator for ValueMapIterator<'a> { + type Item = (&'a Value, &'a Value); + + fn next(&mut self) -> Option<Self::Item> { + let mut idx = self.index; + loop { + if idx >= self.map.size { + return None + } + use ValueEntry as E; + let E::Taken((k, v)) = &self.map.values[idx] else { + idx += 1; + continue; + }; + + self.index = idx + 1; + return Some((k, v)) + } + } +} + +pub trait TryHash { + fn try_hash<H: std::hash::Hasher>(&self, state: &mut H) -> Result<()>; +} + +impl TryHash for Value { + fn try_hash<H: std::hash::Hasher>(&self, state: &mut H) -> Result<()> { + use Value::*; + match self { + Nil => 0x23845.hash(state), + Bool(b) => b.hash(state), + Int(i) => i.hash(state), + Ratio(r) => r.hash(state), + Regex(r) => r.as_str().hash(state), + String(s) => s.hash(state), + List(l) => { + for val in l.iter() { + val.try_hash(state)?; + } + } + Matrix(m) => { + m.domain.hash(state); + m.codomain.hash(state); + for val in m.values.iter() { + val.try_hash(state)?; + } + }, + _ => return Err(exception!(HASH_EXCEPTION, "cannot hash {self:?}")) + }; + Ok(()) + } +} + +impl ValueClone for ValueEntry { + fn deep_clone(&self) -> Self { + use ValueEntry as E; + match self { + E::Empty => E::Empty, + E::Taken((k, v)) => E::Taken((k.deep_clone(), v.deep_clone())), + E::Gravestone(g) => E::Gravestone(g.deep_clone()), + } + } + + fn shallow_clone(&self) -> Self { + use ValueEntry as E; + match self { + E::Empty => E::Empty, + E::Taken((k, v)) => E::Taken((k.clone(), v.clone())), + E::Gravestone(g) => E::Gravestone(g.clone()), + } + } +} + +impl ValueClone for ValueMap { + fn deep_clone(&self) -> Self { + let values = self.values.iter().map(|e| e.deep_clone()).collect(); + Self { + values, + size: self.size, + used: self.used + } + } + + fn shallow_clone(&self) -> Self { + let values = self.values.iter().map(|e| e.clone()).collect(); + Self { + values, + size: self.size, + used: self.used + } + } +} |