Line data    Source code

       1              : //! Equivalent of [`std::collections::hash_map::Entry`] for this hashmap.
       2              : 
       3              : use crate::hash::core::{CoreHashMap, FullError, INVALID_POS};
       4              : use crate::sync::{RwLockWriteGuard, ValueWriteGuard};
       5              : 
       6              : use std::hash::Hash;
       7              : use std::mem;
       8              : 
       9              : pub enum Entry<'a, 'b, K, V> {
      10              :     Occupied(OccupiedEntry<'a, 'b, K, V>),
      11              :     Vacant(VacantEntry<'a, 'b, K, V>),
      12              : }
      13              : 
      14              : /// Enum representing the previous position within a chain.
      15              : #[derive(Clone, Copy)]
      16              : pub(crate) enum PrevPos {
      17              :     /// Starting index within the dictionary.  
      18              :     First(u32),
      19              :     /// Regular index within the buckets.
      20              :     Chained(u32),
      21              :     /// Unknown - e.g. the associated entry was retrieved by index instead of chain.
      22              :     Unknown(u64),
      23              : }
      24              : 
      25              : pub struct OccupiedEntry<'a, 'b, K, V> {
      26              :     /// Mutable reference to the map containing this entry.
      27              :     pub(crate) map: RwLockWriteGuard<'b, CoreHashMap<'a, K, V>>,
      28              :     /// The key of the occupied entry
      29              :     pub(crate) _key: K,
      30              :     /// The index of the previous entry in the chain.
      31              :     pub(crate) prev_pos: PrevPos,
      32              :     /// The position of the bucket in the [`CoreHashMap`] bucket array.
      33              :     pub(crate) bucket_pos: u32,
      34              : }
      35              : 
      36              : impl<K, V> OccupiedEntry<'_, '_, K, V> {
      37            0 :     pub fn get(&self) -> &V {
      38            0 :         &self.map.buckets[self.bucket_pos as usize]
      39            0 :             .inner
      40            0 :             .as_ref()
      41            0 :             .unwrap()
      42            0 :             .1
      43            0 :     }
      44              : 
      45            0 :     pub fn get_mut(&mut self) -> &mut V {
      46            0 :         &mut self.map.buckets[self.bucket_pos as usize]
      47            0 :             .inner
      48            0 :             .as_mut()
      49            0 :             .unwrap()
      50            0 :             .1
      51            0 :     }
      52              : 
      53              :     /// Inserts a value into the entry, replacing (and returning) the existing value.
      54        64716 :     pub fn insert(&mut self, value: V) -> V {
      55        64716 :         let bucket = &mut self.map.buckets[self.bucket_pos as usize];
      56              :         // This assumes inner is Some, which it must be for an OccupiedEntry
      57        64716 :         mem::replace(&mut bucket.inner.as_mut().unwrap().1, value)
      58        64716 :     }
      59              : 
      60              :     /// Removes the entry from the hash map, returning the value originally stored within it.
      61              :     ///
      62              :     /// This may result in multiple bucket accesses if the entry was obtained by index as the
      63              :     /// previous chain entry needs to be discovered in this case.
      64        23501 :     pub fn remove(mut self) -> V {
      65              :         // If this bucket was queried by index, go ahead and follow its chain from the start.
      66        23501 :         let prev = if let PrevPos::Unknown(hash) = self.prev_pos {
      67          247 :             let dict_idx = hash as usize % self.map.dictionary.len();
      68          247 :             let mut prev = PrevPos::First(dict_idx as u32);
      69          247 :             let mut curr = self.map.dictionary[dict_idx];
      70          268 :             while curr != self.bucket_pos {
      71           21 :                 assert!(curr != INVALID_POS);
      72           21 :                 prev = PrevPos::Chained(curr);
      73           21 :                 curr = self.map.buckets[curr as usize].next;
      74              :             }
      75          247 :             prev
      76              :         } else {
      77        23254 :             self.prev_pos
      78              :         };
      79              : 
      80              :         // CoreHashMap::remove returns Option<(K, V)>. We know it's Some for an OccupiedEntry.
      81        23501 :         let bucket = &mut self.map.buckets[self.bucket_pos as usize];
      82              : 
      83              :         // unlink it from the chain
      84        23501 :         match prev {
      85        21586 :             PrevPos::First(dict_pos) => {
      86        21586 :                 self.map.dictionary[dict_pos as usize] = bucket.next;
      87        21586 :             }
      88         1915 :             PrevPos::Chained(bucket_pos) => {
      89         1915 :                 self.map.buckets[bucket_pos as usize].next = bucket.next;
      90         1915 :             }
      91            0 :             _ => unreachable!(),
      92              :         }
      93              : 
      94              :         // and add it to the freelist
      95        23501 :         let free = self.map.free_head;
      96        23501 :         let bucket = &mut self.map.buckets[self.bucket_pos as usize];
      97        23501 :         let old_value = bucket.inner.take();
      98        23501 :         bucket.next = free;
      99        23501 :         self.map.free_head = self.bucket_pos;
     100        23501 :         self.map.buckets_in_use -= 1;
     101              : 
     102        23501 :         old_value.unwrap().1
     103        23501 :     }
     104              : }
     105              : 
     106              : /// An abstract view into a vacant entry within the map.
     107              : pub struct VacantEntry<'a, 'b, K, V> {
     108              :     /// Mutable reference to the map containing this entry.
     109              :     pub(crate) map: RwLockWriteGuard<'b, CoreHashMap<'a, K, V>>,
     110              :     /// The key to be inserted into this entry.
     111              :     pub(crate) key: K,
     112              :     /// The position within the dictionary corresponding to the key's hash.
     113              :     pub(crate) dict_pos: u32,
     114              : }
     115              : 
     116              : impl<'b, K: Clone + Hash + Eq, V> VacantEntry<'_, 'b, K, V> {
     117              :     /// Insert a value into the vacant entry, finding and populating an empty bucket in the process.
     118              :     ///
     119              :     /// # Errors
     120              :     /// Will return [`FullError`] if there are no unoccupied buckets in the map.
     121       172328 :     pub fn insert(mut self, value: V) -> Result<ValueWriteGuard<'b, V>, FullError> {
     122       172328 :         let pos = self.map.alloc_bucket(self.key, value)?;
     123       172326 :         self.map.buckets[pos as usize].next = self.map.dictionary[self.dict_pos as usize];
     124       172326 :         self.map.dictionary[self.dict_pos as usize] = pos;
     125              : 
     126       172326 :         Ok(RwLockWriteGuard::map(self.map, |m| {
     127       172326 :             &mut m.buckets[pos as usize].inner.as_mut().unwrap().1
     128       172326 :         }))
     129       172328 :     }
     130              : }