vecstorage/lib.rs
1//! # `VecStorage`
2//! Struct to re-use the storage of a vector for borrowing values with different lifetimes.
3//!
4//! ## Examples
5//! The following code does not compile:
6//! ```compile_fail
7//! let mut v = Vec::with_capacity(2);
8//! {
9//! let x = 1; let y = 2;
10//! v.push(&x);
11//! v.push(&y);
12//! v.clear(); // We stop borrowing here, but the compiler doesn't know that.
13//! }
14//! {
15//! let a = 1; let b = 2;
16//! v.push(&a);
17//! v.push(&b);
18//! v.clear(); // We stop borrowing here, but the compiler doesn't know that.
19//! }
20//! ```
21//!
22//! You can use [`VecStorage`] to solve this problem:
23//! ```
24//! use vecstorage::VecStorage;
25//! let mut v = VecStorage::<&'static u32>::with_capacity(2);
26//! {
27//! let x = 1; let y = 2;
28//! let mut guard = v.vec_guard();
29//! // `guard` behaves like a `Vec<&'_ u32>` that can be used to store `&x`.
30//! guard.push(&x); // No memory allocation here, we use the memory allocated in `v`.
31//! guard.push(&y);
32//! // If we were going to push more items on the guard, we would allocate memory.
33//! // When guard goes out of scope, it is cleared.
34//! }
35//! {
36//! let a = 1; let b = 2;
37//! let mut guard = v.vec_guard();
38//! // Now guard behaves like a vector.
39//! // The memory from the previous run has been cleared ...
40//! assert_eq!(guard.len(), 0);
41//! // ... but the memeroy has been reused.
42//! assert_eq!(guard.capacity(), 2);
43//! guard.push(&a);
44//! guard.push(&b);
45//! }
46//! ```
47//!
48//! The [`VecStorage`] re-uses the same memory each time:
49//! ```
50//! use vecstorage::VecStorage;
51//! let mut v = VecStorage::<&'static u32>::with_capacity(2);
52//! let capacity;
53//! {
54//! let x = 1; let y = 2; let z = 3;
55//! let mut guard = v.vec_guard();
56//! guard.push(&x); // No memory allocation here, we use the memory allocated in `v`.
57//! guard.push(&y);
58//! // Let's push some more items on the guard and allocate memory:
59//! guard.push(&z);
60//! capacity = guard.capacity();
61//! assert!(capacity > 2);
62//! }
63//! {
64//! let mut guard = v.vec_guard::<&u32>();
65//! // The memory from the previous run has been cleared ...
66//! assert_eq!(guard.len(), 0);
67//! // ... but the capacity is kept:
68//! assert_eq!(capacity, guard.capacity());
69//! }
70//! ```
71//!
72//!
73//! The following example illustrates the typical usage of [`VecStorage`].
74//! ```
75//! use vecstorage::VecStorage;
76//!
77//! struct WithLifetime<'a> {
78//! reference: &'a ()
79//! }
80//!
81//! struct MyStruct {
82//! storage: VecStorage<WithLifetime<'static>>
83//! }
84//!
85//! impl MyStruct {
86//! fn with_capacity(capacity: usize) -> Self {
87//! Self {
88//! storage: VecStorage::with_capacity(capacity)
89//! }
90//! }
91//!
92//! fn apply_from_iterator<'a, I, F>(&mut self, iterator: I, f: F)
93//! where I: Iterator<Item = WithLifetime<'a>>, F: Fn(&[WithLifetime<'a>]) {
94//! let mut guard = self.storage.vec_guard();
95//! for item in iterator {
96//! guard.push(item)
97//! }
98//! f(guard.as_slice());
99//! }
100//! }
101//! ```
102//!
103//!
104//! [`VecStorage<T>`] allocates memory just like [`Vec<T>`].
105//! Typically, `T` is chosen to have a `'static` lifetime, but you actually want a
106//! a `Vec<TGuard>`, where `TGuard` is another data type that does not have a `'static` lifetime.
107//! If the types `T` and `TGuard` have the same size and alignment, you can use
108//! the [`VecStorage<T>`] to create a [`VecGuard<TGuard>`] with the [`vec_guard<'_, TGuard>()`] method.
109//! The [`VecGuard`] uses the memory from the [`VecStorage`] and can temporarily
110//! be used just like a [`Vec<TGuard>`]
111//! (i.e.: it implements `Deref<Target=Vec<TGuard>>` and `DerefMut<Target=Vec<TGuard>>`).
112//!
113//! When the [`VecGuard`] is dropped, the vector is cleared, but
114//! the memory "goes back to the [`VecStorage`]" and
115//! can be re-used later on to store references with a different lifetime.
116use std::ffi::c_void;
117use std::marker::PhantomData;
118use std::mem;
119use std::ops::Deref;
120use std::ops::DerefMut;
121
122/// Re-usable memory for creating a vector of references.
123///
124/// See the [module-level documentation] for more information.
125///
126/// [module-level documentation]: ./index.html
127#[derive(Debug)]
128pub struct VecStorage<T> {
129 ptr: *mut c_void,
130 capacity: usize,
131 // The borrow system already ensures that there cannot be two `VecGuard`'s of
132 // the same `VecStorage`, but when a `VecGuard` is "mem::forgotten", it cannot
133 // cleanup, so we use this field to ensure that no new `VecGuard` can be created
134 // if the previous one is "mem::forgotten".
135 is_locked: bool,
136 phantom: PhantomData<T>,
137}
138
139unsafe impl<T> Send for VecStorage<T> where T: Send {}
140unsafe impl<T> Sync for VecStorage<T> where T: Sync {}
141
142/// This can be used as a vector of `T` ([`Vec<T>`]).
143///
144/// See the [module-level documentation] for more information.
145///
146/// [module-level documentation]: ./index.html
147pub struct VecGuard<'s, TOrig, T> {
148 storage: &'s mut VecStorage<TOrig>,
149 borrow: Vec<T>,
150}
151
152impl<'s, TOrig, T> Deref for VecGuard<'s, TOrig, T> {
153 type Target = Vec<T>;
154
155 fn deref(&self) -> &Vec<T> {
156 &self.borrow
157 }
158}
159
160impl<'s, TOrig, T> DerefMut for VecGuard<'s, TOrig, T> {
161 fn deref_mut(&mut self) -> &mut Vec<T> {
162 &mut self.borrow
163 }
164}
165
166impl<'s, TOrig, T> Drop for VecGuard<'s, TOrig, T> {
167 fn drop(&mut self) {
168 self.borrow.clear();
169 self.storage.ptr = self.borrow.as_mut_ptr() as *mut c_void;
170 debug_assert_eq!(self.borrow.len(), 0);
171 self.storage.capacity = self.borrow.capacity();
172
173 // `drop` is always called recursively,
174 // see https://doc.rust-lang.org/nomicon/destructors.html
175 // So we have to manually drop `self.borrow`.
176 // We cannot simply "move out of borrowed content",
177 // so we swap it with another vector.
178 // Note: `Vec::new()` does not allocate.
179 let mut v = Vec::new();
180 mem::swap(&mut v, &mut self.borrow);
181 mem::forget(v);
182
183 self.storage.is_locked = false;
184 }
185}
186
187impl<T> VecStorage<T> {
188 /// Create a new [`VecStorage<T>`] with the provided capacity.
189 ///
190 /// # Example
191 /// ```
192 /// use vecstorage::VecStorage;
193 ///
194 /// let storage = VecStorage::<u32>::with_capacity(5);
195 /// assert_eq!(storage.capacity(), 5);
196 /// ```
197 pub fn with_capacity(capacity: usize) -> Self {
198 let mut vector: Vec<T> = Vec::with_capacity(capacity);
199 debug_assert_eq!(vector.len(), 0);
200 let result = Self {
201 is_locked: false,
202 ptr: vector.as_mut_ptr() as *mut c_void,
203 capacity: vector.capacity(),
204 phantom: PhantomData,
205 };
206 mem::forget(vector);
207 result
208 }
209
210 /// Get the capacity of the [`VecStorage`].
211 ///
212 /// # Example
213 /// ```
214 /// use vecstorage::VecStorage;
215 ///
216 /// let storage = VecStorage::<u32>::with_capacity(5);
217 /// assert_eq!(storage.capacity(), 5);
218 /// ```
219 pub fn capacity(&self) -> usize {
220 self.capacity
221 }
222
223 /// Creates a new [`VecGuard`] using the memory allocated by `self`.
224 /// This VecGuard` will automatically clear the vector when it goes out of scope.
225 ///
226 /// # Panics
227 /// Panics if `TGuard` doesn't have the same size and alignment as `T`.
228 ///
229 /// Panics if `mem::forget()` was called on a [`VecGuard`]
230 /// that was created previously on the same [`VecStorage`].
231 ///
232 /// # Example
233 /// ```
234 /// use vecstorage::VecStorage;
235 ///
236 /// let mut storage = VecStorage::<u32>::with_capacity(2);
237 /// {
238 /// let mut guard = storage.vec_guard();
239 /// assert_eq!(guard.capacity(), 2);
240 /// assert_eq!(guard.len(), 0);
241 /// guard.push(3);
242 /// guard.push(2);
243 ///}
244 ///{
245 /// let mut guard = storage.vec_guard::<u32>();
246 /// assert_eq!(guard.capacity(), 2); // The memory of the `storage` is reused
247 /// assert_eq!(guard.len(), 0); // But its contents has been "cleared".
248 ///}
249 ///```
250 pub fn vec_guard<'s, TGuard>(&'s mut self) -> VecGuard<'s, T, TGuard> {
251 // If `mem::forget()` was called on the guard, then
252 // the `drop()` on the guard did not run and
253 // the ptr and the capacity of the underlying vector may not be
254 // correct anymore.
255 // It is then undefined behaviour to use `Vec::from_raw_parts`.
256 // Hence this check.
257 if self.is_locked {
258 panic!(
259 "`VecStorage` has been locked. \
260 Probably `mem::forget()` was called on a `VecGuard`."
261 );
262 }
263 use std::alloc::Layout;
264 if Layout::new::<TGuard>() != Layout::new::<T>() {
265 panic!(
266 "The data type of the guard must have the same size and alignment \
267 as the data type of the `VecStorage`."
268 );
269 }
270 self.is_locked = true;
271
272 let vector;
273 unsafe { vector = Vec::from_raw_parts(self.ptr as *mut TGuard, 0, self.capacity) }
274 VecGuard {
275 borrow: vector,
276 storage: self,
277 }
278 }
279}
280
281impl<T> Drop for VecStorage<T> {
282 fn drop(&mut self) {
283 if !self.is_locked {
284 unsafe {
285 mem::drop(Vec::from_raw_parts(self.ptr as *mut T, 0, self.capacity));
286 }
287 } else {
288 // If `mem::forget()` was called on a guard, then
289 // the `drop()` on the guard did not run and
290 // the ptr and the capacity of the underlying vector may not be
291 // correct anymore.
292 // It is probably not a good idea to panic inside the `drop()` function,
293 // so let's just leak some memory (`mem::forget()` was called after all.)
294 // We do nothing in this `else` branch.
295 }
296 }
297}
298
299#[test]
300#[should_panic(
301 expected = "`VecStorage` has been locked. Probably `mem::forget()` was called on a `VecGuard`"
302)]
303fn mem_forgetting_guard_leads_to_panic_with_new_guard() {
304 let mut v = VecStorage::<&u32>::with_capacity(2);
305 {
306 let x = 1;
307 let mut guard = v.vec_guard();
308 guard.push(&x);
309 // You should not do the following:
310 mem::forget(guard);
311 }
312 {
313 let _guard = v.vec_guard::<&u32>();
314 }
315}
316
317#[test]
318#[should_panic(
319 expected = "The data type of the guard must have the same size and alignment \
320 as the data type of the `VecStorage`."
321)]
322fn creating_guard_with_different_size_gives_leads_to_panic() {
323 let mut v = VecStorage::<u32>::with_capacity(2);
324 let _guard = v.vec_guard::<u64>();
325}
326
327#[test]
328fn mem_forgetting_guard_does_not_lead_to_panic() {
329 let mut v = VecStorage::<&u32>::with_capacity(2);
330 {
331 let x = 1;
332 let mut guard = v.vec_guard();
333 guard.push(&x);
334 // You should not do the following:
335 mem::forget(guard);
336 }
337 // The `VecStorage` is dropped and this should not lead to a panic.
338}
339
340#[test]
341fn vec_storage_mut_common_use_cases() {
342 let capacity;
343 let mut v = VecStorage::<&u32>::with_capacity(2);
344 {
345 let mut x = 1;
346 let mut y = 2;
347 let mut z = 3;
348 let mut guard = v.vec_guard();
349 assert_eq!(guard.capacity(), 2);
350 assert_eq!(guard.len(), 0);
351 guard.push(&mut x);
352 guard.push(&mut y);
353 guard.push(&mut z);
354 capacity = guard.capacity();
355 }
356 {
357 let mut a = 1;
358 let mut b = 2;
359 let mut guard = v.vec_guard();
360 assert_eq!(guard.len(), 0);
361 assert_eq!(capacity, guard.capacity());
362 guard.push(&mut a);
363 guard.push(&mut b);
364 }
365}
366
367#[cfg(test)]
368fn impls_send<T: Send>() {}
369
370#[test]
371fn vecstorage_implements_send() {
372 impls_send::<VecStorage<u32>>();
373}
374
375#[cfg(test)]
376fn impls_sync<T: Sync>() {}
377
378#[test]
379fn vecstorage_implements_sync() {
380 impls_sync::<VecStorage<u32>>();
381}