From 4c4e54ac8a9782439744fe15aa31a3bedab92b74 Mon Sep 17 00:00:00 2001 From: Aleksey Kladov Date: Thu, 14 Jan 2021 18:47:42 +0300 Subject: prepare to publish el libro de arena --- lib/README.md | 2 + lib/arena/Cargo.toml | 10 ++++ lib/arena/src/lib.rs | 152 +++++++++++++++++++++++++++++++++++++++++++++++++++ lib/arena/src/map.rs | 62 +++++++++++++++++++++ 4 files changed, 226 insertions(+) create mode 100644 lib/README.md create mode 100644 lib/arena/Cargo.toml create mode 100644 lib/arena/src/lib.rs create mode 100644 lib/arena/src/map.rs (limited to 'lib') diff --git a/lib/README.md b/lib/README.md new file mode 100644 index 000000000..6b2eeac2c --- /dev/null +++ b/lib/README.md @@ -0,0 +1,2 @@ +Crates in this directory are published to crates.io and obey semver. +They *could* live in a separate repo, but we want to experiment with a monorepo setup. diff --git a/lib/arena/Cargo.toml b/lib/arena/Cargo.toml new file mode 100644 index 000000000..183a5bb6a --- /dev/null +++ b/lib/arena/Cargo.toml @@ -0,0 +1,10 @@ +[package] +name = "la-arena" +version = "0.1.0" +description = "Thy rope of sands..." +license = "MIT OR Apache-2.0" +authors = ["rust-analyzer developers"] +edition = "2018" + +[lib] +doctest = false diff --git a/lib/arena/src/lib.rs b/lib/arena/src/lib.rs new file mode 100644 index 000000000..3169aa5b8 --- /dev/null +++ b/lib/arena/src/lib.rs @@ -0,0 +1,152 @@ +//! Yet another index-based arena. + +use std::{ + fmt, + hash::{Hash, Hasher}, + iter::FromIterator, + marker::PhantomData, + ops::{Index, IndexMut}, +}; + +pub mod map; + +#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)] +pub struct RawId(u32); + +impl From for u32 { + fn from(raw: RawId) -> u32 { + raw.0 + } +} + +impl From for RawId { + fn from(id: u32) -> RawId { + RawId(id) + } +} + +impl fmt::Debug for RawId { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + self.0.fmt(f) + } +} + +impl fmt::Display for RawId { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + self.0.fmt(f) + } +} + +pub struct Idx { + raw: RawId, + _ty: PhantomData T>, +} + +impl Clone for Idx { + fn clone(&self) -> Self { + *self + } +} +impl Copy for Idx {} + +impl PartialEq for Idx { + fn eq(&self, other: &Idx) -> bool { + self.raw == other.raw + } +} +impl Eq for Idx {} + +impl Hash for Idx { + fn hash(&self, state: &mut H) { + self.raw.hash(state) + } +} + +impl fmt::Debug for Idx { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let mut type_name = std::any::type_name::(); + if let Some(idx) = type_name.rfind(':') { + type_name = &type_name[idx + 1..] + } + write!(f, "Idx::<{}>({})", type_name, self.raw) + } +} + +impl Idx { + pub fn from_raw(raw: RawId) -> Self { + Idx { raw, _ty: PhantomData } + } + pub fn into_raw(self) -> RawId { + self.raw + } +} + +#[derive(Clone, PartialEq, Eq)] +pub struct Arena { + data: Vec, +} + +impl fmt::Debug for Arena { + fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { + fmt.debug_struct("Arena").field("len", &self.len()).field("data", &self.data).finish() + } +} + +impl Arena { + pub const fn new() -> Arena { + Arena { data: Vec::new() } + } + pub fn clear(&mut self) { + self.data.clear(); + } + + pub fn len(&self) -> usize { + self.data.len() + } + pub fn is_empty(&self) -> bool { + self.data.is_empty() + } + pub fn alloc(&mut self, value: T) -> Idx { + let id = RawId(self.data.len() as u32); + self.data.push(value); + Idx::from_raw(id) + } + pub fn iter( + &self, + ) -> impl Iterator, &T)> + ExactSizeIterator + DoubleEndedIterator { + self.data.iter().enumerate().map(|(idx, value)| (Idx::from_raw(RawId(idx as u32)), value)) + } + pub fn shrink_to_fit(&mut self) { + self.data.shrink_to_fit(); + } +} + +impl Default for Arena { + fn default() -> Arena { + Arena { data: Vec::new() } + } +} + +impl Index> for Arena { + type Output = T; + fn index(&self, idx: Idx) -> &T { + let idx = idx.into_raw().0 as usize; + &self.data[idx] + } +} + +impl IndexMut> for Arena { + fn index_mut(&mut self, idx: Idx) -> &mut T { + let idx = idx.into_raw().0 as usize; + &mut self.data[idx] + } +} + +impl FromIterator for Arena { + fn from_iter(iter: I) -> Self + where + I: IntoIterator, + { + Arena { data: Vec::from_iter(iter) } + } +} diff --git a/lib/arena/src/map.rs b/lib/arena/src/map.rs new file mode 100644 index 000000000..0f33907c0 --- /dev/null +++ b/lib/arena/src/map.rs @@ -0,0 +1,62 @@ +//! A map from arena IDs to some other type. Space requirement is O(highest ID). + +use std::marker::PhantomData; + +use crate::Idx; + +/// A map from arena IDs to some other type. Space requirement is O(highest ID). +#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] +pub struct ArenaMap { + v: Vec>, + _ty: PhantomData, +} + +impl ArenaMap, V> { + pub fn insert(&mut self, id: Idx, t: V) { + let idx = Self::to_idx(id); + + self.v.resize_with((idx + 1).max(self.v.len()), || None); + self.v[idx] = Some(t); + } + + pub fn get(&self, id: Idx) -> Option<&V> { + self.v.get(Self::to_idx(id)).and_then(|it| it.as_ref()) + } + + pub fn get_mut(&mut self, id: Idx) -> Option<&mut V> { + self.v.get_mut(Self::to_idx(id)).and_then(|it| it.as_mut()) + } + + pub fn values(&self) -> impl Iterator { + self.v.iter().filter_map(|o| o.as_ref()) + } + + pub fn values_mut(&mut self) -> impl Iterator { + self.v.iter_mut().filter_map(|o| o.as_mut()) + } + + pub fn iter(&self) -> impl Iterator, &V)> { + self.v.iter().enumerate().filter_map(|(idx, o)| Some((Self::from_idx(idx), o.as_ref()?))) + } + + fn to_idx(id: Idx) -> usize { + u32::from(id.into_raw()) as usize + } + + fn from_idx(idx: usize) -> Idx { + Idx::from_raw((idx as u32).into()) + } +} + +impl std::ops::Index> for ArenaMap, T> { + type Output = T; + fn index(&self, id: Idx) -> &T { + self.v[Self::to_idx(id)].as_ref().unwrap() + } +} + +impl Default for ArenaMap, T> { + fn default() -> Self { + ArenaMap { v: Vec::new(), _ty: PhantomData } + } +} -- cgit v1.2.3