diff options
| -rw-r--r-- | examples/misc/Cargo.toml | 9 | ||||
| -rw-r--r-- | examples/misc/src/hashmap.rs | 168 | ||||
| -rw-r--r-- | examples/misc/src/main.rs | 7 |
3 files changed, 184 insertions, 0 deletions
diff --git a/examples/misc/Cargo.toml b/examples/misc/Cargo.toml new file mode 100644 index 00000000..31ffeaf9 --- /dev/null +++ b/examples/misc/Cargo.toml @@ -0,0 +1,9 @@ +[package] +name = "misc" +version = "0.1.0" +authors = ["Son Ho <hosonmarc@gmail.com>"] +edition = "2018" + +# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html + +[dependencies] diff --git a/examples/misc/src/hashmap.rs b/examples/misc/src/hashmap.rs new file mode 100644 index 00000000..98e3f7d8 --- /dev/null +++ b/examples/misc/src/hashmap.rs @@ -0,0 +1,168 @@ +//! A hashmap implementation. +//! TODO: we will need function pointers/closures if we want to make the map +//! generic in the key type. + +use std::vec::Vec; +pub type Key = usize; // TODO: make this generic +pub type Hash = usize; + +pub enum List<T> { + Cons(Key, T, Box<List<T>>), + Nil, +} + +/// A hash function for the keys. +/// Rk.: we use shared references because we anticipate on the generic +/// hash map version. +pub fn hash_key(k: &Key) -> Hash { + // Do nothing for now, we might want to implement something smarter + // in the future + *k +} + +/// A hash map from [u64] to values +pub struct HashMap<T> { + /// The current number of values in the table + num_values: usize, + /// The max load factor, expressed as a fraction + max_load_factor: (usize, usize), + /// The table itself + slots: Vec<List<T>>, +} + +impl<T> HashMap<T> { + /// Allocate a vector of slots of a given size. + /// We would need a loop, but can't use loops for now... + fn allocate_slots(mut slots: Vec<List<T>>, n: usize) -> Vec<List<T>> { + if n == 0 { + slots + } else { + slots.push(List::Nil); + HashMap::allocate_slots(slots, n - 1) + } + } + + pub fn new() -> Self { + let slots = HashMap::allocate_slots(Vec::new(), 32); + HashMap { + num_values: 0, + max_load_factor: (4, 5), + slots, + } + } + + /// We need a loop here too... + /// Also, we start with the end, so that F* sees that the function terminates. + fn clear_slots(slots: &mut Vec<List<T>>, i: usize) { + if i > 0 { + let i = i - 1; + slots[i] = List::Nil; + HashMap::clear_slots(slots, i) + } else { + () + } + } + + pub fn clear(&mut self) { + self.num_values = 0; + let len = self.slots.len(); + HashMap::clear_slots(&mut self.slots, len); + } + + pub fn len(&self) -> usize { + self.num_values + } + + fn insert_in_list(key: Key, value: T, ls: &mut List<T>) { + match ls { + List::Nil => *ls = List::Cons(key, value, Box::new(List::Nil)), + List::Cons(ckey, cvalue, ls) => { + if *ckey == key { + *cvalue = value; + } else { + HashMap::insert_in_list(key, value, ls) + } + } + } + } + + pub fn insert(&mut self, key: Key, value: T) { + let hash = hash_key(&key); + let hash_mod = hash % self.slots.len(); + HashMap::insert_in_list(key, value, self.slots.get_mut(hash_mod).unwrap()); + } + + fn get_in_list<'l, 'k>(key: &'k Key, ls: &'l List<T>) -> Option<&'l T> { + match ls { + List::Nil => None, + List::Cons(ckey, cvalue, ls) => { + if ckey == key { + Some(cvalue) + } else { + HashMap::get_in_list(key, ls) + } + } + } + } + + /// The signature is not exactly the same as the one in + /// [https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.get_mut] + /// (the region paramaters are more precise here). + pub fn get<'l, 'k>(&'l self, key: &'k Key) -> Option<&'l T> { + let hash = hash_key(key); + let hash_mod = hash % self.slots.len(); + HashMap::get_in_list(key, self.slots.get(hash_mod).unwrap()) + } + + fn get_mut_in_list<'l, 'k>(key: &'k Key, ls: &'l mut List<T>) -> Option<&'l mut T> { + match ls { + List::Nil => None, + List::Cons(ckey, cvalue, ls) => { + if ckey == key { + Some(cvalue) + } else { + HashMap::get_mut_in_list(key, ls) + } + } + } + } + + /// Same remark as for [get]. + pub fn get_mut<'l, 'k>(&'l mut self, key: &'k Key) -> Option<&'l mut T> { + let hash = hash_key(key); + let hash_mod = hash % self.slots.len(); + HashMap::get_mut_in_list(key, self.slots.get_mut(hash_mod).unwrap()) + } + + fn remove_from_list(key: &Key, ls: &mut List<T>) -> Option<T> { + match ls { + List::Nil => None, + List::Cons(ckey, cvalue, tl) => { + if ckey == key { + // We have to move under borrows, so we need to use + // [std::mem::replace] in several steps. + // Retrieve the tail + let mv_ls = std::mem::replace(ls, List::Nil); + match mv_ls { + List::Nil => unreachable!(), + List::Cons(_, cvalue, tl) => { + // Make the list equal to its tail + *ls = *tl; + // Returned the dropped value + Some(cvalue) + } + } + } else { + HashMap::remove_from_list(key, tl) + } + } + } + } + + /// Same remark as for [get]. + pub fn remove(&mut self, key: &Key) -> Option<T> { + let hash = hash_key(key); + let hash_mod = hash % self.slots.len(); + HashMap::remove_from_list(key, self.slots.get_mut(hash_mod).unwrap()) + } +} diff --git a/examples/misc/src/main.rs b/examples/misc/src/main.rs new file mode 100644 index 00000000..4587c571 --- /dev/null +++ b/examples/misc/src/main.rs @@ -0,0 +1,7 @@ +mod hashmap; + +use hashmap::HashMap; + +fn main() { + let hm: HashMap<u64> = HashMap::new(); +} |