bendns' repos / rust-analyzer
Unnamed repository; edit this file 'description' to name the repository.
Auto merge of #12931 - oxalica:feat/la-arena-apis, r=lnicola
Add more constructors and entry-APIs for la-arena `la-arena` on crates.io is quite helpful when just a thin wrapper for Vec with u32 indices is needed. But the current API is not ergonomic enough. This PR - Adds `ArenaMap::new`. Not sure why only `Arena` has it now. - Adds `Arena{,Map}::with_capacity` for known-size storage. - Adds entry-API for `ArenaMap` for easier `.entry(idx).or_default().push(value)` or `.entry(idx).or_insert(...)` operations.
Browse Source
bors 2022-08-06
parent 3792720 · parent 10f870e · commit 5170569
Diffstat
-rw-r--r--lib/la-arena/src/lib.rs12
-rw-r--r--lib/la-arena/src/map.rs119
2 files changed, 129 insertions, 2 deletions
diff --git a/lib/la-arena/src/lib.rs b/lib/la-arena/src/lib.rs
index dadee43b10..a3fe59e946 100644
--- a/lib/la-arena/src/lib.rs
+++ b/lib/la-arena/src/lib.rs
@@ -12,7 +12,7 @@ use std::{
};
mod map;
-pub use map::ArenaMap;
+pub use map::{ArenaMap, Entry, OccupiedEntry, VacantEntry};
/// The raw index of a value in an arena.
#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
@@ -208,6 +208,16 @@ impl<T> Arena<T> {
Arena { data: Vec::new() }
}
+ /// Create a new empty arena with specific capacity.
+ ///
+ /// ```
+ /// let arena: la_arena::Arena<i32> = la_arena::Arena::with_capacity(42);
+ /// assert!(arena.is_empty());
+ /// ```
+ pub fn with_capacity(capacity: usize) -> Arena<T> {
+ Arena { data: Vec::with_capacity(capacity) }
+ }
+
/// Empties the arena, removing all contained values.
///
/// ```
diff --git a/lib/la-arena/src/map.rs b/lib/la-arena/src/map.rs
index d27f086d37..f74ec5d97c 100644
--- a/lib/la-arena/src/map.rs
+++ b/lib/la-arena/src/map.rs
@@ -11,6 +11,16 @@ pub struct ArenaMap<IDX, V> {
}
impl<T, V> ArenaMap<Idx<T>, V> {
+ /// Creates a new empty map.
+ pub const fn new() -> Self {
+ Self { v: Vec::new(), _ty: PhantomData }
+ }
+
+ /// Create a new empty map with specific capacity.
+ pub fn with_capacity(capacity: usize) -> Self {
+ Self { v: Vec::with_capacity(capacity), _ty: PhantomData }
+ }
+
/// Inserts a value associated with a given arena index into the map.
pub fn insert(&mut self, idx: Idx<T>, t: V) {
let idx = Self::to_idx(idx);
@@ -46,6 +56,16 @@ impl<T, V> ArenaMap<Idx<T>, V> {
self.v.iter().enumerate().filter_map(|(idx, o)| Some((Self::from_idx(idx), o.as_ref()?)))
}
+ /// Gets the given key's corresponding entry in the map for in-place manipulation.
+ pub fn entry(&mut self, idx: Idx<T>) -> Entry<'_, Idx<T>, V> {
+ let idx = Self::to_idx(idx);
+ self.v.resize_with((idx + 1).max(self.v.len()), || None);
+ match &mut self.v[idx] {
+ slot @ Some(_) => Entry::Occupied(OccupiedEntry { slot, _ty: PhantomData }),
+ slot @ None => Entry::Vacant(VacantEntry { slot, _ty: PhantomData }),
+ }
+ }
+
fn to_idx(idx: Idx<T>) -> usize {
u32::from(idx.into_raw()) as usize
}
@@ -70,6 +90,103 @@ impl<T, V> std::ops::IndexMut<Idx<V>> for ArenaMap<Idx<V>, T> {
impl<T, V> Default for ArenaMap<Idx<V>, T> {
fn default() -> Self {
- ArenaMap { v: Vec::new(), _ty: PhantomData }
+ Self::new()
+ }
+}
+
+/// A view into a single entry in a map, which may either be vacant or occupied.
+///
+/// This `enum` is constructed from the [`entry`] method on [`ArenaMap`].
+///
+/// [`entry`]: ArenaMap::entry
+pub enum Entry<'a, IDX, V> {
+ /// A vacant entry.
+ Vacant(VacantEntry<'a, IDX, V>),
+ /// An occupied entry.
+ Occupied(OccupiedEntry<'a, IDX, V>),
+}
+
+impl<'a, IDX, V> Entry<'a, IDX, V> {
+ /// Ensures a value is in the entry by inserting the default if empty, and returns a mutable reference to
+ /// the value in the entry.
+ pub fn or_insert(self, default: V) -> &'a mut V {
+ match self {
+ Self::Vacant(ent) => ent.insert(default),
+ Self::Occupied(ent) => ent.into_mut(),
+ }
+ }
+
+ /// Ensures a value is in the entry by inserting the result of the default function if empty, and returns
+ /// a mutable reference to the value in the entry.
+ pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
+ match self {
+ Self::Vacant(ent) => ent.insert(default()),
+ Self::Occupied(ent) => ent.into_mut(),
+ }
+ }
+
+ /// Provides in-place mutable access to an occupied entry before any potential inserts into the map.
+ pub fn and_modify<F: FnOnce(&mut V)>(mut self, f: F) -> Self {
+ if let Self::Occupied(ent) = &mut self {
+ f(ent.get_mut());
+ }
+ self
+ }
+}
+
+impl<'a, IDX, V> Entry<'a, IDX, V>
+where
+ V: Default,
+{
+ /// Ensures a value is in the entry by inserting the default value if empty, and returns a mutable reference
+ /// to the value in the entry.
+ pub fn or_default(self) -> &'a mut V {
+ self.or_insert_with(Default::default)
+ }
+}
+
+/// A view into an vacant entry in a [`ArenaMap`]. It is part of the [`Entry`] enum.
+pub struct VacantEntry<'a, IDX, V> {
+ slot: &'a mut Option<V>,
+ _ty: PhantomData<IDX>,
+}
+
+impl<'a, IDX, V> VacantEntry<'a, IDX, V> {
+ /// Sets the value of the entry with the `VacantEntry`’s key, and returns a mutable reference to it.
+ pub fn insert(self, value: V) -> &'a mut V {
+ self.slot.insert(value)
+ }
+}
+
+/// A view into an occupied entry in a [`ArenaMap`]. It is part of the [`Entry`] enum.
+pub struct OccupiedEntry<'a, IDX, V> {
+ slot: &'a mut Option<V>,
+ _ty: PhantomData<IDX>,
+}
+
+impl<'a, IDX, V> OccupiedEntry<'a, IDX, V> {
+ /// Gets a reference to the value in the entry.
+ pub fn get(&self) -> &V {
+ self.slot.as_ref().expect("Occupied")
+ }
+
+ /// Gets a mutable reference to the value in the entry.
+ pub fn get_mut(&mut self) -> &mut V {
+ self.slot.as_mut().expect("Occupied")
+ }
+
+ /// Converts the entry into a mutable reference to its value.
+ pub fn into_mut(self) -> &'a mut V {
+ self.slot.as_mut().expect("Occupied")
+ }
+
+ /// Sets the value of the entry with the `OccupiedEntry`’s key, and returns the entry’s old value.
+ pub fn insert(&mut self, value: V) -> V {
+ self.slot.replace(value).expect("Occupied")
+ }
+
+ /// Takes the value of the entry out of the map, and returns it.
+ pub fn remove(self) -> V {
+ self.slot.take().expect("Occupied")
}
}