csc_7b_fc/
hmap.rs

1//! This module contains the implementation of a closed hashmap from scratch.
2//! Because the interior of the implementation is exposed, one can use it to
3//! implement a biject hashmap without resorting to Copy, Clone, Rc or anything
4//! unsafe.
5
6#![allow(dead_code, unused_imports, unused_variables)]
7
8use std::collections::hash_map::RandomState;
9use std::hash::{BuildHasher, Hash,Hasher};
10use std::ops::{Index,IndexMut};
11
12/// Structure of a HashMap, built from scratch, but which uses
13/// Rust's built-in implmenetations of the Hash trait.
14/// This is a closed hash table with a linear probing rehash function.
15/// The table is a vector of Option<key-value-pair>.  The vector
16/// maxhashes tracks the maximum number of hashes and rehashes required
17/// for a given hash slot.  keylocs tracks locations of possible keys
18/// in the vector, which is important for quick iteration over the structure.
19/// The size/capacity of the vector is always set to a power of 2: this
20/// means instead of % capacity we can calculate & mask, where mask is always
21/// capacity-1;  The hashstate is necessary for writing the hash function.
22pub struct Hmap<KT,VT> {
23  pub table : Vec<Option<(KT,VT)>>,
24  pub count : usize,
25  pub maxhashes: Vec<usize>,
26  pub keylocs : Vec<usize>, // records where keys are located.
27  pub mask : usize,  // always = capacity-1 (power of 2 - 1)
28  pub hashstate : RandomState,
29}
30
31impl<KT:Hash+Eq,VT> Hmap<KT,VT> {
32  fn make(cap : usize) -> Self {  // internal function
33    let mut tab = Vec::new();
34    tab.resize_with(cap,||None);
35    let mut mh = Vec::new();
36    mh.resize(cap,0);
37    Hmap {
38      table : tab,
39      count : 0,
40      maxhashes : mh,
41      keylocs: Vec::with_capacity(cap),
42      mask : cap-1,
43      hashstate: RandomState::new(),
44    }
45  }// with_capacity
46
47  /// Creates new Hmap with default capacity 16
48  pub fn new() -> Self {
49    Self::make(16)
50  }
51
52  /// Creates new Hmap with requested capacity.  The
53  /// actual capacity will be the nearest power of two that's
54  /// greater than or equal to the requested capacity.
55  pub fn with_capacity(requested_cap:usize) -> Self {
56    let mut cap = 1;
57    while cap < requested_cap { cap *= 2; }
58    Self::make(cap)
59  }
60
61  /// returns the number of key-value pairs inside the map
62  pub fn len(&self) -> usize { self.count }
63  /// returns the current capacity of the map
64  pub fn current_capacity(&self) -> usize { self.mask+1 }
65
66  /// retrieves a borrow of the value associated with the given key,
67  /// if it exists.  Look at the source code to understand how it's defined.
68  /// Given an opt:Option<T>, opt.as_ref() will return an Option<&T>.
69  pub fn get(&self, key:&KT) -> Option<&VT> {
70    match self.find_slot(key) {
71      Some(h) => self.table[h].as_ref().map(|(k,v)|v),
72      None => None,
73    }
74  }
75
76  /// retrieves a mutable borrow of the value associated with the given key,
77  /// if it exists.  Look at the source code.  Given a mutable opt:Option<T>,
78  /// opt.as_mut() will return an Option<&mut T>.
79  pub fn get_mut(&mut self, key:&KT) -> Option<&mut VT> {
80    match self.find_slot(key) {
81      Some(h) => self.table[h].as_mut().map(|(k,v)|v),
82      None => None,
83    }
84  }
85
86  /// add or change the value associated with the key, returns the
87  /// previous key and value, if it existed.  Look at the source code.
88  /// Note that core::mem::swap is used to assign to the vector while
89  /// taking the previous value out of the vector.
90  pub fn set(&mut self, key:KT, val:VT) -> Option<(KT,VT)> {
91    if self.count*100 >= (self.mask+1)*75 { self.resize(true); }
92    match self.find_new_slot(&key) {
93      (h,true) => {
94          let mut pair = Some((key,val));
95          core::mem::swap(&mut pair, &mut self.table[h]);
96          pair
97        },
98      (h,false) => {
99          self.count += 1;
100          let pair = Some((key,val));
101          self.table[h] = pair;
102          None
103        },
104    }//match
105  }
106
107  /// removes the key-value pair given the key, returns the pair if it
108  /// exists.  Note that core::mem::swap is used to take the pair out
109  /// of the vector.
110  pub fn remove(&mut self, key:&KT) -> Option<(KT,VT)> {
111    match self.find_slot(key) {
112      Some(h) => {
113        let mut temp = None;
114        core::mem::swap(&mut temp, &mut self.table[h]);
115        self.count -= 1;
116        temp
117      },
118      None => { None },
119    }
120  }
121
122  /// Internal function called by resize, assumes that key-value pair
123  /// is new and that table has enough capacity.
124  pub fn add(&mut self, key:KT, val:VT) {  // called internally
125    let h0 = self.hash(&key);
126    let mut h = h0;
127    let mut hashes = 1;
128    while let Some(_) = &self.table[h] {
129      h = (h+1)&self.mask;
130      hashes += 1;
131    }
132    if hashes > self.maxhashes[h0] { self.maxhashes[h0] = hashes; }
133    self.keylocs.push(h);
134    self.count += 1;
135    self.table[h] = Some((key,val));
136  }
137
138  /// Resizes the hashmap by doubling or halfing the capacity.
139  pub fn resize(&mut self, upsize:bool) -> bool {
140    let newcap = if upsize {(self.mask+1)*2} else {(self.mask+1)/2};
141    if self.count > newcap { return false; }
142    let mut newmap = Self::make(newcap);
143    for i in &self.keylocs {
144      if let Some(_) = &self.table[*i] {
145        let mut temp = None;
146        core::mem::swap(&mut temp, &mut self.table[*i]);
147        temp.map(|(k,v)|{newmap.add(k,v)});
148      }
149    }
150    core::mem::swap(self, &mut newmap);
151    true
152  }
153
154  /// hash function steals the Hash trait implementations of Rust
155  pub fn hash(&self, key:&KT) -> usize {
156    let mut bs = self.hashstate.build_hasher();
157    key.hash(&mut bs);
158    (bs.finish() as usize) & self.mask
159  }
160
161  /// This function finds the location where a key is found, or
162  /// where a new key-value pair can be inserted.  It returns
163  /// an index, paired with a boolean indicating whether the key
164  /// was found at that index.
165  pub fn find_new_slot(&mut self, key:&KT) -> (usize,bool) {
166    let h0 = self.hash(key);
167    let mut h = h0;
168    let mut hashes = 1;
169    let mut reuse = None;
170    loop {
171      match &self.table[h] {
172        Some((k,_)) if key==k => { return (h,true); },
173        Some(_) => {
174          h = (h+1)&self.mask;
175          hashes += 1;
176        },
177        None if hashes <= self.maxhashes[h0] => {
178          if let None = reuse { reuse = Some(h); }
179          h = (h+1)&self.mask;
180          hashes +=1;
181        },
182        _ => { break; }  // end loop
183      }
184    }//loop
185    if hashes > self.maxhashes[h0] { self.maxhashes[h0] = hashes; }
186    if let Some(r) = reuse { (r,false) }
187    else {
188      self.keylocs.push(h);
189      (h,false)
190    }
191  }// find_new_slot
192
193  /// This function finds the index of the internal vector where a
194  /// key is located, if it exists.
195  pub fn find_slot(&self, key:&KT) -> Option<usize> {
196    let h0 = self.hash(key);
197    let mut h = h0;
198    let mut hashes = 1;
199    loop {
200      match &self.table[h] {
201        Some((k,_)) if key==k => { return Some(h); },
202        _ if hashes < self.maxhashes[h0] => {
203          h = (h+1)&self.mask;
204          hashes += 1;
205        },
206        _ => { break; }
207      }
208    }//loop
209    None
210  }// find_slot
211
212  /// Creates iterator over all key-value pairs
213  pub fn iter<'t>(&'t self) -> HmapIter<'t,KT,VT> {
214    HmapIter {
215      hmap : self,
216      i : 0,
217    }
218  }
219} // main impl
220
221
222/// Structure for implementing Iterator trait
223pub struct HmapIter<'t,KT,VT> {
224  hmap : &'t Hmap<KT,VT>,
225  i : usize,
226}
227impl<'t,KT,VT> Iterator for HmapIter<'t,KT,VT> {
228  type Item = (&'t KT,&'t VT);
229  fn next(&mut self) -> Option<Self::Item> {
230    while self.i < self.hmap.keylocs.len() {
231      let ai = self.hmap.keylocs[self.i];
232      self.i += 1;
233      if let None = &self.hmap.table[ai] { continue; }
234      else { return self.hmap.table[ai].as_ref().map(|p|(&p.0, &p.1)); }
235    }
236    None
237  }
238}
239
240impl<KT:Hash+Eq,VT> Index<&KT> for Hmap<KT,VT> {
241  type Output = VT;
242  /// Provides ability to use syntax such as `map[&key]`.  Operation
243  /// will panic if key does not exist
244  fn index(&self, key:&KT) -> &Self::Output {
245    self.get(key).unwrap()
246  }
247}
248
249impl<KT:Hash+Eq,VT> Index<KT> for Hmap<KT,VT> {
250  type Output = VT;
251  /// Provides ability to use syntax such as `map[key]`. Operation will
252  /// panic if key does not exist.
253  fn index(&self, key:KT) -> &Self::Output {
254    self.get(&key).unwrap()
255  }
256}
257
258impl<KT:Hash+Eq,VT:Default> IndexMut<KT> for Hmap<KT,VT> {
259  /// Provides ability to use syntax such as `map[key] = val`.
260  /// This function will insert a new value into the table if necessary
261  /// and assumes that the value type VT implements the Default trait.
262  fn index_mut(&mut self, key:KT) -> &mut Self::Output {
263    if self.count*100 >= (self.mask+1)*75 { self.resize(true); }  
264    let (h,found) = self.find_new_slot(&key);
265    if !found {
266      self.table[h] = Some((key,VT::default()));
267      self.count += 1;
268    }
269    self.table[h].as_mut().map(|(_,v)|v).unwrap()    
270  }
271}
272
csc_7b_fc/hmap.rs

csc_7b_fc/
hmap.rs
