diff options
-rw-r--r-- | lib/arena/Cargo.toml | 6 | ||||
-rw-r--r-- | lib/arena/src/lib.rs | 80 | ||||
-rw-r--r-- | lib/arena/src/map.rs | 6 |
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" | |||
3 | version = "0.1.0" | 3 | version = "0.1.0" |
4 | description = "Thy rope of sands..." | 4 | description = "Thy rope of sands..." |
5 | license = "MIT OR Apache-2.0" | 5 | license = "MIT OR Apache-2.0" |
6 | repository = "https://github.com/rust-analyzer/rust-analyzer" | ||
7 | documentation = "https://docs.rs/la-arena" | ||
8 | categories = ["data-structures", "memory-management", "rust-patterns"] | ||
6 | authors = ["rust-analyzer developers"] | 9 | authors = ["rust-analyzer developers"] |
7 | edition = "2018" | 10 | edition = "2018" |
8 | |||
9 | [lib] | ||
10 | doctest = 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 | ||
3 | use std::{ | 5 | use std::{ |
4 | fmt, | 6 | fmt, |
@@ -10,6 +12,7 @@ use std::{ | |||
10 | 12 | ||
11 | pub mod map; | 13 | pub 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)] |
14 | pub struct RawId(u32); | 17 | pub 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. | ||
40 | pub struct Idx<T> { | 44 | pub 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 | ||
75 | impl<T> Idx<T> { | 79 | impl<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)] |
85 | pub struct Arena<T> { | 93 | pub 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 | ||
95 | impl<T> Arena<T> { | 103 | impl<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 | ||
14 | impl<T, V> ArenaMap<Idx<T>, V> { | 14 | impl<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 | } |