vendor/elsa/src/map.rs

   1 use std::borrow::Borrow;
   2 use std::cell::{Cell, UnsafeCell};
   3 use std::collections::hash_map::RandomState;
   4 use std::collections::BTreeMap;
   5 use std::collections::HashMap;
   6 use std::hash::{BuildHasher, Hash};
   7 use std::iter::FromIterator;
   8 use std::ops::Index;
   9
  10 use stable_deref_trait::StableDeref;
  11
  12 /// Append-only version of `std::collections::HashMap` where
  13 /// insertion does not require mutable access
  14 pub struct FrozenMap<K, V, S = RandomState> {
  15     map: UnsafeCell<HashMap<K, V, S>>,
  16     /// Eq/Hash implementations can have side-effects, and using Rc it is possible
  17     /// for FrozenMap::insert to be called on a key that itself contains the same
  18     /// `FrozenMap`, whose `eq` implementation also calls FrozenMap::insert
  19     ///
  20     /// We use this `in_use` flag to guard against any reentrancy.
  21     in_use: Cell<bool>,
  22 }
  23
  24 // safety: UnsafeCell implies !Sync
  25
  26 impl<K: Eq + Hash, V> FrozenMap<K, V> {
  27     pub fn new() -> Self {
  28         Self {
  29             map: UnsafeCell::new(Default::default()),
  30             in_use: Cell::new(false),
  31         }
  32     }
  33
  34     /// # Examples
  35     ///
  36     /// ```
  37     /// use elsa::FrozenMap;
  38     ///
  39     /// let map = FrozenMap::new();
  40     /// assert_eq!(map.len(), 0);
  41     /// map.insert(1, Box::new("a"));
  42     /// assert_eq!(map.len(), 1);
  43     /// ```
  44     pub fn len(&self) -> usize {
  45         assert!(!self.in_use.get());
  46         self.in_use.set(true);
  47         let len = unsafe {
  48             let map = self.map.get();
  49             (*map).len()
  50         };
  51         self.in_use.set(false);
  52         len
  53     }
  54
  55     /// # Examples
  56     ///
  57     /// ```
  58     /// use elsa::FrozenMap;
  59     ///
  60     /// let map = FrozenMap::new();
  61     /// assert_eq!(map.is_empty(), true);
  62     /// map.insert(1, Box::new("a"));
  63     /// assert_eq!(map.is_empty(), false);
  64     /// ```
  65     pub fn is_empty(&self) -> bool {
  66         self.len() == 0
  67     }
  68 }
  69
  70 impl<K: Eq + Hash, V: StableDeref, S: BuildHasher> FrozenMap<K, V, S> {
  71     // these should never return &K or &V
  72     // these should never delete any entries
  73     pub fn insert(&self, k: K, v: V) -> &V::Target {
  74         assert!(!self.in_use.get());
  75         self.in_use.set(true);
  76         let ret = unsafe {
  77             let map = self.map.get();
  78             &*(*map).entry(k).or_insert(v)
  79         };
  80         self.in_use.set(false);
  81         ret
  82     }
  83
  84     /// Returns a reference to the value corresponding to the key.
  85     ///
  86     /// The key may be any borrowed form of the map's key type, but
  87     /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
  88     /// the key type.
  89     ///
  90     /// # Examples
  91     ///
  92     /// ```
  93     /// use elsa::FrozenMap;
  94     ///
  95     /// let map = FrozenMap::new();
  96     /// map.insert(1, Box::new("a"));
  97     /// assert_eq!(map.get(&1), Some(&"a"));
  98     /// assert_eq!(map.get(&2), None);
  99     /// ```
 100     pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V::Target>
 101     where
 102         K: Borrow<Q>,
 103         Q: Hash + Eq,
 104     {
 105         assert!(!self.in_use.get());
 106         self.in_use.set(true);
 107         let ret = unsafe {
 108             let map = self.map.get();
 109             (*map).get(k).map(|x| &**x)
 110         };
 111         self.in_use.set(false);
 112         ret
 113     }
 114
 115     /// Applies a function to the owner of the value corresponding to the key (if any).
 116     ///
 117     /// The key may be any borrowed form of the map's key type, but
 118     /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
 119     /// the key type.
 120     ///
 121     /// # Examples
 122     ///
 123     /// ```
 124     /// use elsa::FrozenMap;
 125     ///
 126     /// let map = FrozenMap::new();
 127     /// map.insert(1, Box::new("a"));
 128     /// assert_eq!(map.map_get(&1, Clone::clone), Some(Box::new("a")));
 129     /// assert_eq!(map.map_get(&2, Clone::clone), None);
 130     /// ```
 131     pub fn map_get<Q: ?Sized, T, F>(&self, k: &Q, f: F) -> Option<T>
 132     where
 133         K: Borrow<Q>,
 134         Q: Hash + Eq,
 135         F: FnOnce(&V) -> T,
 136     {
 137         assert!(!self.in_use.get());
 138         self.in_use.set(true);
 139         let ret = unsafe {
 140             let map = self.map.get();
 141             (*map).get(k).map(f)
 142         };
 143         self.in_use.set(false);
 144         ret
 145     }
 146
 147     pub fn into_map(self) -> HashMap<K, V, S> {
 148         self.map.into_inner()
 149     }
 150
 151     // TODO add more
 152 }
 153
 154 impl<K: Eq + Hash + StableDeref, V: StableDeref, S: BuildHasher> FrozenMap<K, V, S> {
 155     /// Returns a reference to the key and value matching a borrowed
 156     /// key.
 157     ///
 158     /// The key argument may be any borrowed form of the map's key type,
 159     /// but [`Hash`] and [`Eq`] on the borrowed form *must* match those
 160     /// for the key type.
 161     ///
 162     /// # Examples
 163     ///
 164     /// ```
 165     /// use elsa::FrozenMap;
 166     ///
 167     /// let map = FrozenMap::new();
 168     /// map.insert(Box::new("1"), Box::new("a"));
 169     /// assert_eq!(map.get_key_value(&"1"), Some((&"1", &"a")));
 170     /// assert_eq!(map.get_key_value(&"2"), None);
 171     /// ```
 172     pub fn get_key_value<Q: ?Sized>(&self, k: &Q) -> Option<(&K::Target, &V::Target)>
 173     where
 174         K: Borrow<Q>,
 175         Q: Hash + Eq,
 176     {
 177         assert!(!self.in_use.get());
 178         self.in_use.set(true);
 179         let ret = unsafe {
 180             let map = self.map.get();
 181             (*map).get_key_value(k).map(|(k, v)| (&**k, &**v))
 182         };
 183         self.in_use.set(false);
 184         ret
 185     }
 186 }
 187
 188 impl<K, V, S> std::convert::AsMut<HashMap<K, V, S>> for FrozenMap<K, V, S> {
 189     /// Get mutable access to the underlying [`HashMap`].
 190     ///
 191     /// This is safe, as it requires a `&mut self`, ensuring nothing is using
 192     /// the 'frozen' contents.
 193     fn as_mut(&mut self) -> &mut HashMap<K, V, S> {
 194         unsafe { &mut *self.map.get() }
 195     }
 196 }
 197
 198 impl<K, V, S> From<HashMap<K, V, S>> for FrozenMap<K, V, S> {
 199     fn from(map: HashMap<K, V, S>) -> Self {
 200         Self {
 201             map: UnsafeCell::new(map),
 202             in_use: Cell::new(false),
 203         }
 204     }
 205 }
 206
 207 impl<Q: ?Sized, K, V, S> Index<&Q> for FrozenMap<K, V, S>
 208 where
 209     Q: Eq + Hash,
 210     K: Eq + Hash + Borrow<Q>,
 211     V: StableDeref,
 212     S: BuildHasher,
 213 {
 214     type Output = V::Target;
 215
 216     /// # Examples
 217     ///
 218     /// ```
 219     /// use elsa::FrozenMap;
 220     ///
 221     /// let map = FrozenMap::new();
 222     /// map.insert(1, Box::new("a"));
 223     /// assert_eq!(map[&1], "a");
 224     /// ```
 225     fn index(&self, idx: &Q) -> &V::Target {
 226         self.get(idx)
 227             .expect("attempted to index FrozenMap with unknown key")
 228     }
 229 }
 230
 231 impl<K: Eq + Hash, V, S: BuildHasher + Default> FromIterator<(K, V)> for FrozenMap<K, V, S> {
 232     fn from_iter<T>(iter: T) -> Self
 233     where
 234         T: IntoIterator<Item = (K, V)>,
 235     {
 236         let map: HashMap<_, _, _> = iter.into_iter().collect();
 237         map.into()
 238     }
 239 }
 240
 241 impl<K: Eq + Hash, V, S: Default> Default for FrozenMap<K, V, S> {
 242     fn default() -> Self {
 243         Self {
 244             map: UnsafeCell::new(Default::default()),
 245             in_use: Cell::new(false),
 246         }
 247     }
 248 }
 249
 250 /// Append-only version of `std::collections::BTreeMap` where
 251 /// insertion does not require mutable access
 252 pub struct FrozenBTreeMap<K, V> {
 253     map: UnsafeCell<BTreeMap<K, V>>,
 254     /// Eq/Hash implementations can have side-effects, and using Rc it is possible
 255     /// for FrozenBTreeMap::insert to be called on a key that itself contains the same
 256     /// `FrozenBTreeMap`, whose `eq` implementation also calls FrozenBTreeMap::insert
 257     ///
 258     /// We use this `in_use` flag to guard against any reentrancy.
 259     in_use: Cell<bool>,
 260 }
 261
 262 // safety: UnsafeCell implies !Sync
 263
 264 impl<K: Clone + Ord, V: StableDeref> FrozenBTreeMap<K, V> {
 265     pub fn new() -> Self {
 266         Self {
 267             map: UnsafeCell::new(Default::default()),
 268             in_use: Cell::new(false),
 269         }
 270     }
 271
 272     /// # Examples
 273     ///
 274     /// ```
 275     /// use elsa::FrozenBTreeMap;
 276     ///
 277     /// let map = FrozenBTreeMap::new();
 278     /// assert_eq!(map.len(), 0);
 279     /// map.insert(1, Box::new("a"));
 280     /// assert_eq!(map.len(), 1);
 281     /// ```
 282     pub fn len(&self) -> usize {
 283         assert!(!self.in_use.get());
 284         self.in_use.set(true);
 285         let len = unsafe {
 286             let map = self.map.get();
 287             (*map).len()
 288         };
 289         self.in_use.set(false);
 290         len
 291     }
 292
 293     /// # Examples
 294     ///
 295     /// ```
 296     /// use elsa::FrozenBTreeMap;
 297     ///
 298     /// let map = FrozenBTreeMap::new();
 299     /// assert_eq!(map.is_empty(), true);
 300     /// map.insert(1, Box::new("a"));
 301     /// assert_eq!(map.is_empty(), false);
 302     /// ```
 303     pub fn is_empty(&self) -> bool {
 304         self.len() == 0
 305     }
 306 }
 307
 308 impl<K: Clone + Ord, V: StableDeref> FrozenBTreeMap<K, V> {
 309     // these should never return &K or &V
 310     // these should never delete any entries
 311     pub fn insert(&self, k: K, v: V) -> &V::Target {
 312         assert!(!self.in_use.get());
 313         self.in_use.set(true);
 314         let ret = unsafe {
 315             let map = self.map.get();
 316             &*(*map).entry(k).or_insert(v)
 317         };
 318         self.in_use.set(false);
 319         ret
 320     }
 321
 322     /// Returns a reference to the value corresponding to the key.
 323     ///
 324     /// The key may be any borrowed form of the map's key type, but
 325     /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
 326     /// the key type.
 327     ///
 328     /// # Examples
 329     ///
 330     /// ```
 331     /// use elsa::FrozenBTreeMap;
 332     ///
 333     /// let map = FrozenBTreeMap::new();
 334     /// map.insert(1, Box::new("a"));
 335     /// assert_eq!(map.get(&1), Some(&"a"));
 336     /// assert_eq!(map.get(&2), None);
 337     /// ```
 338     pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V::Target>
 339     where
 340         K: Borrow<Q>,
 341         Q: Ord,
 342     {
 343         assert!(!self.in_use.get());
 344         self.in_use.set(true);
 345         let ret = unsafe {
 346             let map = self.map.get();
 347             (*map).get(k).map(|x| &**x)
 348         };
 349         self.in_use.set(false);
 350         ret
 351     }
 352
 353     /// Applies a function to the owner of the value corresponding to the key (if any).
 354     ///
 355     /// The key may be any borrowed form of the map's key type, but
 356     /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
 357     /// the key type.
 358     ///
 359     /// # Examples
 360     ///
 361     /// ```
 362     /// use elsa::FrozenBTreeMap;
 363     ///
 364     /// let map = FrozenBTreeMap::new();
 365     /// map.insert(1, Box::new("a"));
 366     /// assert_eq!(map.map_get(&1, Clone::clone), Some(Box::new("a")));
 367     /// assert_eq!(map.map_get(&2, Clone::clone), None);
 368     /// ```
 369     pub fn map_get<Q: ?Sized, T, F>(&self, k: &Q, f: F) -> Option<T>
 370     where
 371         K: Borrow<Q>,
 372         Q: Ord,
 373         F: FnOnce(&V) -> T,
 374     {
 375         assert!(!self.in_use.get());
 376         self.in_use.set(true);
 377         let ret = unsafe {
 378             let map = self.map.get();
 379             (*map).get(k).map(f)
 380         };
 381         self.in_use.set(false);
 382         ret
 383     }
 384
 385     pub fn into_map(self) -> BTreeMap<K, V> {
 386         self.map.into_inner()
 387     }
 388
 389     // TODO add more
 390 }
 391
 392 impl<K, V> std::convert::AsMut<BTreeMap<K, V>> for FrozenBTreeMap<K, V> {
 393     /// Get mutable access to the underlying [`HashMap`].
 394     ///
 395     /// This is safe, as it requires a `&mut self`, ensuring nothing is using
 396     /// the 'frozen' contents.
 397     fn as_mut(&mut self) -> &mut BTreeMap<K, V> {
 398         unsafe { &mut *self.map.get() }
 399     }
 400 }
 401
 402 impl<K: Clone + Ord, V: StableDeref> From<BTreeMap<K, V>> for FrozenBTreeMap<K, V> {
 403     fn from(map: BTreeMap<K, V>) -> Self {
 404         Self {
 405             map: UnsafeCell::new(map),
 406             in_use: Cell::new(false),
 407         }
 408     }
 409 }
 410
 411 impl<Q: ?Sized, K, V> Index<&Q> for FrozenBTreeMap<K, V>
 412 where
 413     Q: Ord,
 414     K: Clone + Ord + Borrow<Q>,
 415     V: StableDeref,
 416 {
 417     type Output = V::Target;
 418
 419     /// # Examples
 420     ///
 421     /// ```
 422     /// use elsa::FrozenBTreeMap;
 423     ///
 424     /// let map = FrozenBTreeMap::new();
 425     /// map.insert(1, Box::new("a"));
 426     /// assert_eq!(map[&1], "a");
 427     /// ```
 428     fn index(&self, idx: &Q) -> &V::Target {
 429         self.get(idx)
 430             .expect("attempted to index FrozenBTreeMap with unknown key")
 431     }
 432 }
 433
 434 impl<K: Clone + Ord, V: StableDeref> FromIterator<(K, V)> for FrozenBTreeMap<K, V> {
 435     fn from_iter<T>(iter: T) -> Self
 436     where
 437         T: IntoIterator<Item = (K, V)>,
 438     {
 439         let map: BTreeMap<_, _> = iter.into_iter().collect();
 440         map.into()
 441     }
 442 }
 443
 444 impl<K: Clone + Ord, V: StableDeref> Default for FrozenBTreeMap<K, V> {
 445     fn default() -> Self {
 446         Self {
 447             map: UnsafeCell::new(Default::default()),
 448             in_use: Cell::new(false),
 449         }
 450     }
 451 }