aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--lib/arena/Cargo.toml6
-rw-r--r--lib/arena/src/lib.rs80
-rw-r--r--lib/arena/src/map.rs6
3 files changed, 88 insertions, 4 deletions
diff --git a/lib/arena/Cargo.toml b/lib/arena/Cargo.toml
index 183a5bb6a..1afec9bf8 100644
--- a/lib/arena/Cargo.toml
+++ b/lib/arena/Cargo.toml
@@ -3,8 +3,8 @@ name = "la-arena"
3version = "0.1.0" 3version = "0.1.0"
4description = "Thy rope of sands..." 4description = "Thy rope of sands..."
5license = "MIT OR Apache-2.0" 5license = "MIT OR Apache-2.0"
6repository = "https://github.com/rust-analyzer/rust-analyzer"
7documentation = "https://docs.rs/la-arena"
8categories = ["data-structures", "memory-management", "rust-patterns"]
6authors = ["rust-analyzer developers"] 9authors = ["rust-analyzer developers"]
7edition = "2018" 10edition = "2018"
8
9[lib]
10doctest = false
diff --git a/lib/arena/src/lib.rs b/lib/arena/src/lib.rs
index 3169aa5b8..78a147c7d 100644
--- a/lib/arena/src/lib.rs
+++ b/lib/arena/src/lib.rs
@@ -1,4 +1,6 @@
1//! Yet another index-based arena. 1//! Yet another ID-based arena.
2
3#![warn(missing_docs)]
2 4
3use std::{ 5use std::{
4 fmt, 6 fmt,
@@ -10,6 +12,7 @@ use std::{
10 12
11pub mod map; 13pub mod map;
12 14
15/// The raw ID of a value in an arena.
13#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)] 16#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
14pub struct RawId(u32); 17pub struct RawId(u32);
15 18
@@ -37,6 +40,7 @@ impl fmt::Display for RawId {
37 } 40 }
38} 41}
39 42
43/// The ID of a value allocated in an arena that holds `T`s.
40pub struct Idx<T> { 44pub struct Idx<T> {
41 raw: RawId, 45 raw: RawId,
42 _ty: PhantomData<fn() -> T>, 46 _ty: PhantomData<fn() -> T>,
@@ -73,14 +77,18 @@ impl<T> fmt::Debug for Idx<T> {
73} 77}
74 78
75impl<T> Idx<T> { 79impl<T> Idx<T> {
80 /// Creates a new ID from a [`RawId`].
76 pub fn from_raw(raw: RawId) -> Self { 81 pub fn from_raw(raw: RawId) -> Self {
77 Idx { raw, _ty: PhantomData } 82 Idx { raw, _ty: PhantomData }
78 } 83 }
84
85 /// Converts this ID into the underlying [`RawId`].
79 pub fn into_raw(self) -> RawId { 86 pub fn into_raw(self) -> RawId {
80 self.raw 87 self.raw
81 } 88 }
82} 89}
83 90
91/// Yet another ID-based arena.
84#[derive(Clone, PartialEq, Eq)] 92#[derive(Clone, PartialEq, Eq)]
85pub struct Arena<T> { 93pub struct Arena<T> {
86 data: Vec<T>, 94 data: Vec<T>,
@@ -93,29 +101,99 @@ impl<T: fmt::Debug> fmt::Debug for Arena<T> {
93} 101}
94 102
95impl<T> Arena<T> { 103impl<T> Arena<T> {
104 /// Creates a new empty arena.
105 ///
106 /// ```
107 /// let arena: la_arena::Arena<i32> = la_arena::Arena::new();
108 /// assert!(arena.is_empty());
109 /// ```
96 pub const fn new() -> Arena<T> { 110 pub const fn new() -> Arena<T> {
97 Arena { data: Vec::new() } 111 Arena { data: Vec::new() }
98 } 112 }
113
114 /// Empties the arena, removing all contained values.
115 ///
116 /// ```
117 /// let mut arena = la_arena::Arena::new();
118 ///
119 /// arena.alloc(1);
120 /// arena.alloc(2);
121 /// arena.alloc(3);
122 /// assert_eq!(arena.len(), 3);
123 ///
124 /// arena.clear();
125 /// assert!(arena.is_empty());
126 /// ```
99 pub fn clear(&mut self) { 127 pub fn clear(&mut self) {
100 self.data.clear(); 128 self.data.clear();
101 } 129 }
102 130
131 /// Returns the length of the arena.
132 ///
133 /// ```
134 /// let mut arena = la_arena::Arena::new();
135 /// assert_eq!(arena.len(), 0);
136 ///
137 /// arena.alloc("foo");
138 /// assert_eq!(arena.len(), 1);
139 ///
140 /// arena.alloc("bar");
141 /// assert_eq!(arena.len(), 2);
142 ///
143 /// arena.alloc("baz");
144 /// assert_eq!(arena.len(), 3);
145 /// ```
103 pub fn len(&self) -> usize { 146 pub fn len(&self) -> usize {
104 self.data.len() 147 self.data.len()
105 } 148 }
149
150 /// Returns whether the arena contains no elements.
151 ///
152 /// ```
153 /// let mut arena = la_arena::Arena::new();
154 /// assert!(arena.is_empty());
155 ///
156 /// arena.alloc(0.5);
157 /// assert!(!arena.is_empty());
158 /// ```
106 pub fn is_empty(&self) -> bool { 159 pub fn is_empty(&self) -> bool {
107 self.data.is_empty() 160 self.data.is_empty()
108 } 161 }
162
163 /// Allocates a new value on the arena, returning the value’s ID.
164 ///
165 /// ```
166 /// let mut arena = la_arena::Arena::new();
167 /// let id = arena.alloc(50);
168 ///
169 /// assert_eq!(arena[id], 50);
170 /// ```
109 pub fn alloc(&mut self, value: T) -> Idx<T> { 171 pub fn alloc(&mut self, value: T) -> Idx<T> {
110 let id = RawId(self.data.len() as u32); 172 let id = RawId(self.data.len() as u32);
111 self.data.push(value); 173 self.data.push(value);
112 Idx::from_raw(id) 174 Idx::from_raw(id)
113 } 175 }
176
177 /// Returns an iterator over the arena’s elements.
178 ///
179 /// ```
180 /// let mut arena = la_arena::Arena::new();
181 /// let id1 = arena.alloc(20);
182 /// let id2 = arena.alloc(40);
183 /// let id3 = arena.alloc(60);
184 ///
185 /// let mut iterator = arena.iter();
186 /// assert_eq!(iterator.next(), Some((id1, &20)));
187 /// assert_eq!(iterator.next(), Some((id2, &40)));
188 /// assert_eq!(iterator.next(), Some((id3, &60)));
189 /// ```
114 pub fn iter( 190 pub fn iter(
115 &self, 191 &self,
116 ) -> impl Iterator<Item = (Idx<T>, &T)> + ExactSizeIterator + DoubleEndedIterator { 192 ) -> impl Iterator<Item = (Idx<T>, &T)> + ExactSizeIterator + DoubleEndedIterator {
117 self.data.iter().enumerate().map(|(idx, value)| (Idx::from_raw(RawId(idx as u32)), value)) 193 self.data.iter().enumerate().map(|(idx, value)| (Idx::from_raw(RawId(idx as u32)), value))
118 } 194 }
195
196 /// Reallocates the arena to make it take up as little space as possible.
119 pub fn shrink_to_fit(&mut self) { 197 pub fn shrink_to_fit(&mut self) {
120 self.data.shrink_to_fit(); 198 self.data.shrink_to_fit();
121 } 199 }
diff --git a/lib/arena/src/map.rs b/lib/arena/src/map.rs
index 0f33907c0..980198247 100644
--- a/lib/arena/src/map.rs
+++ b/lib/arena/src/map.rs
@@ -12,6 +12,7 @@ pub struct ArenaMap<ID, V> {
12} 12}
13 13
14impl<T, V> ArenaMap<Idx<T>, V> { 14impl<T, V> ArenaMap<Idx<T>, V> {
15 /// Inserts a value associated with a given arena ID into the map.
15 pub fn insert(&mut self, id: Idx<T>, t: V) { 16 pub fn insert(&mut self, id: Idx<T>, t: V) {
16 let idx = Self::to_idx(id); 17 let idx = Self::to_idx(id);
17 18
@@ -19,22 +20,27 @@ impl<T, V> ArenaMap<Idx<T>, V> {
19 self.v[idx] = Some(t); 20 self.v[idx] = Some(t);
20 } 21 }
21 22
23 /// Returns a reference to the value associated with the provided ID if it is present.
22 pub fn get(&self, id: Idx<T>) -> Option<&V> { 24 pub fn get(&self, id: Idx<T>) -> Option<&V> {
23 self.v.get(Self::to_idx(id)).and_then(|it| it.as_ref()) 25 self.v.get(Self::to_idx(id)).and_then(|it| it.as_ref())
24 } 26 }
25 27
28 /// Returns a mutable reference to the value associated with the provided ID if it is present.
26 pub fn get_mut(&mut self, id: Idx<T>) -> Option<&mut V> { 29 pub fn get_mut(&mut self, id: Idx<T>) -> Option<&mut V> {
27 self.v.get_mut(Self::to_idx(id)).and_then(|it| it.as_mut()) 30 self.v.get_mut(Self::to_idx(id)).and_then(|it| it.as_mut())
28 } 31 }
29 32
33 /// Returns an iterator over the values in the map.
30 pub fn values(&self) -> impl Iterator<Item = &V> { 34 pub fn values(&self) -> impl Iterator<Item = &V> {
31 self.v.iter().filter_map(|o| o.as_ref()) 35 self.v.iter().filter_map(|o| o.as_ref())
32 } 36 }
33 37
38 /// Returns an iterator over mutable references to the values in the map.
34 pub fn values_mut(&mut self) -> impl Iterator<Item = &mut V> { 39 pub fn values_mut(&mut self) -> impl Iterator<Item = &mut V> {
35 self.v.iter_mut().filter_map(|o| o.as_mut()) 40 self.v.iter_mut().filter_map(|o| o.as_mut())
36 } 41 }
37 42
43 /// Returns an iterator over the arena IDs and values in the map.
38 pub fn iter(&self) -> impl Iterator<Item = (Idx<T>, &V)> { 44 pub fn iter(&self) -> impl Iterator<Item = (Idx<T>, &V)> {
39 self.v.iter().enumerate().filter_map(|(idx, o)| Some((Self::from_idx(idx), o.as_ref()?))) 45 self.v.iter().enumerate().filter_map(|(idx, o)| Some((Self::from_idx(idx), o.as_ref()?)))
40 } 46 }