arena_container/
nightly.rs

1extern crate alloc as alloc_crate;
2
3use alloc_crate::alloc::Allocator;
4use alloc_crate::collections::{TryReserveError, TryReserveErrorKind};
5use alloc_crate::vec::{self, Vec};
6use composable_allocators::Global as Global;
7use const_default::ConstDefault;
8use core::fmt::Debug;
9use core::hint::unreachable_unchecked;
10use core::iter::{self, FusedIterator};
11use core::mem::{align_of, replace, size_of};
12use core::ops::{Index, IndexMut};
13use core::ptr::{self};
14use core::slice::{self};
15use either::{Either, Left, Right};
16
17pub use crate::index::*;
18
19type ArenaItem<I, T> = Either<<I as ArenaIndex>::Optional, T>;
20
21/// A (mostly read-only) inner container holding [`Arena`] items.
22/// While [`Arena`] itself is unique (i.e. non-clonable) object,
23/// arena ['items'](Arena::items) could be cloned.
24#[derive(Debug, Clone)]
25pub struct ArenaItems<I: ArenaIndex, T, A: Allocator = Global> {
26    vec: Vec<ArenaItem<I, T>, A>,
27    vacancy: I::Optional,
28}
29
30impl<I: ArenaIndex, T, A: Allocator> ArenaItems<I, T, A> {
31    /// An amount of memory required to hold one component.
32    ///
33    /// This information can be useful for memory management fine-tuning.
34    pub const fn item_size() -> usize {
35        size_of::<ArenaItem<I, T>>()
36    }
37
38    /// An alignment of a cell, holding a component with all required metadata.
39    ///
40    /// This information can be useful for memory management fine-tuning.
41    pub const fn item_align() -> usize {
42        align_of::<ArenaItem<I, T>>()
43    }
44
45    const fn new_in(alloc: A) -> Self {
46        ArenaItems {
47            vec: Vec::new_in(alloc),
48            vacancy: I::NONE
49        }
50    }
51
52    fn with_capacity_in(capacity: usize, alloc: A) -> Self {
53        ArenaItems {
54            vec: Vec::with_capacity_in(capacity, alloc),
55            vacancy: I::NONE
56        }
57    }
58
59    /// Returns a reference to the underlying allocator.
60    pub fn allocator(&self) -> &A { self.vec.allocator() }
61
62    /// Returns the number of elements the arena can hold without reallocating.
63    pub fn capacity(&self) -> usize { self.vec.capacity() }
64
65    /// Returns the number of elements in the arena.
66    ///
67    /// This function has linear worst-case complexity.
68    pub fn len(&self) -> usize {
69        let mut vacancies = 0;
70        let mut vacancy = self.vacancy;
71        while let Some(i) = I::to_option(vacancy) {
72            vacancies += 1;
73            vacancy = *self.vec[I::try_to_usize(i).unwrap()].as_ref().left().unwrap();
74        }
75        self.vec.len() - vacancies
76    }
77
78    /// Returns true iff the number of elements in the arena equals the maximum number of elements ever in the arena.
79    ///
80    /// Because the arena capacity cannot be less than `min_capacity`, the returned false means
81    /// there is space for at least one more item.
82    ///
83    /// The returned value equals to `self.len() == self.min_capacity()`, but unlike [`len`](ArenaItems::len)
84    /// this function has constant complexity.
85    pub fn len_equals_to_min_capacity(&self) -> bool {
86        I::to_option(self.vacancy).is_none()
87    }
88
89    /// Returns `true` if the arena contains no elements.
90    ///
91    /// This function has linear worst-case complexity.
92    pub fn is_empty(&self) -> bool { self.vec.iter().all(|x| x.is_left()) }
93
94    /// Returns the maximum number of elements ever in the arena.
95    /// The arena capacity cannot be less than `min_capacity`.
96    ///
97    /// Arena `min_capacity` never decreases.
98    ///
99    /// # Examples
100    ///
101    /// ```rust
102    /// # use arena_container::Arena;
103    /// #
104    /// # struct Data { /* ... */ }
105    /// #
106    /// # fn main() {
107    /// let mut arena: Arena<usize, Data> = Arena::new();
108    /// assert_eq!(arena.items().min_capacity(), 0);
109    /// let index_1 = arena.insert(|index| (Data { /* ... */ }, index));
110    /// assert_eq!(arena.items().min_capacity(), 1);
111    /// let index_2 = arena.insert(|index| (Data { /* ... */ }, index));
112    /// assert_eq!(arena.items().min_capacity(), 2);
113    /// arena.remove(index_1);
114    /// assert_eq!(arena.items().min_capacity(), 2);
115    /// let index_3 = arena.insert(|index| (Data { /* ... */ }, index));
116    /// assert_eq!(arena.items().min_capacity(), 2);
117    /// let index_4 = arena.insert(|index| (Data { /* ... */ }, index));
118    /// assert_eq!(arena.items().min_capacity(), 3);
119    /// # }
120    /// ```
121    pub fn min_capacity(&self) -> usize { self.vec.len() }
122
123    /// Reserves capacity for at least `additional` more elements.
124    /// The collection may reserve more space to avoid frequent reallocations.
125    /// After calling `reserve`, capacity will be greater than or equal to
126    /// `self.min_capacity() + additional`. Does nothing if capacity is already sufficient.
127    ///
128    /// # Panics
129    ///
130    /// Panics if the new capacity overflows usize.
131    pub fn reserve(&mut self, additional: usize) { self.vec.reserve(additional) }
132
133    /// Reserves the minimum capacity for exactly `additional` more elements.
134    /// After calling `reserve_exact`, capacity will be greater than or equal to
135    /// `self.min_capacity() + additional`. Does nothing if the capacity is already sufficient.
136    ///
137    /// Note that the allocator may give the collection more space than it requests.
138    /// Therefore, capacity can not be relied upon to be precisely minimal.
139    /// Prefer [`reserve`](ArenaItems::reserve) if future insertions are expected.
140    ///
141    /// # Panics
142    ///
143    /// Panics if the new capacity overflows usize.
144    pub fn reserve_exact(&mut self, additional: usize) { self.vec.reserve_exact(additional) }
145
146    /// Shrinks the capacity of the arena with a lower bound.
147    ///
148    /// The capacity will remain at least as large as both the [`min_capacity`](ArenaItems::min_capacity)
149    /// and the supplied value.
150    pub fn shrink_to(&mut self, min_capacity: usize) { self.vec.shrink_to(min_capacity) }
151
152    /// Shrinks the capacity of the vector as much as possible.
153    ///
154    /// It will drop down as close as possible to the [`min_capacity`](ArenaItems::min_capacity)
155    /// but the allocator may still inform the arena that there is space for a few more elements.
156    pub fn shrink_to_fit(&mut self) { self.vec.shrink_to_fit() }
157
158    /// Tries to reserve capacity for at least additional more elements.
159    /// The collection may reserve more space to avoid frequent reallocations.
160    /// After calling `try_reserve`, capacity will be greater than or equal
161    /// to `self.min_capacity() + additional`. Does nothing if capacity is already sufficient.
162    ///
163    /// # Errors
164    ///
165    /// If the capacity overflows, or the allocator reports a failure, then an error is returned.
166    pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
167        self.vec.try_reserve(additional)
168    }
169
170    /// Tries to reserve capacity for exactly `additional` more elements.
171    /// The collection may reserve more space to avoid frequent reallocations.
172    /// After calling `try_reserve_exact`, capacity will be greater than or equal
173    /// to `self.min_capacity() + additional`. Does nothing if capacity is already sufficient.
174    ///
175    /// Note that the allocator may give the collection more space than it requests.
176    /// Therefore, capacity can not be relied upon to be precisely minimal.
177    /// Prefer [`try_reserve`](ArenaItems::try_reserve) if future insertions are expected.
178    ///
179    /// # Errors
180    ///
181    /// If the capacity overflows, or the allocator reports a failure, then an error is returned.
182    pub fn try_reserve_exact(&mut self, additional: usize) -> Result<(), TryReserveError> {
183        self.vec.try_reserve_exact(additional)
184    }
185
186    /// Returns reference to the item occupying `index` place, or `None` if there is no such.
187    ///
188    /// # Panics
189    ///
190    /// Panics if `index` is greater than or equal to [`min_capacity()`](ArenaItems::min_capacity).
191    pub fn get_value(&self, index: usize) -> Option<&T> {
192        self.vec[index].as_ref().right()
193    }
194
195    /// Returns mutable reference to the item occupying `index` place, or `None` if there is no such.
196    ///
197    /// # Panics
198    ///
199    /// Panics if `index` is greater than or equal to [`min_capacity()`](ArenaItems::min_capacity).
200    pub fn get_value_mut(&mut self, index: usize) -> Option<&mut T> {
201        self.vec[index].as_mut().right()
202    }
203
204    /// Returns an iterator over all occupied indices.
205    pub fn indices(&self) -> ArenaItemsIndices<'_, I, T> {
206        ArenaItemsIndices(self.vec.iter().enumerate())
207    }
208
209    /// Returns an iterator over all items.
210    pub fn values(&self) -> ArenaItemsValues<'_, I, T> {
211        ArenaItemsValues(self.vec.iter())
212    }
213
214    /// Returns a mutable iterator over all items.
215    pub fn values_mut(&mut self) -> ArenaItemsValuesMut<'_, I, T> {
216        ArenaItemsValuesMut(self.vec.iter_mut())
217    }
218
219    /// Returns an iterator over all items combined with their indices.
220    pub fn iter(&self) -> ArenaItemsIter<'_, I, T> {
221        ArenaItemsIter(self.vec.iter().enumerate())
222    }
223
224    /// Returns a mutable iterator over all items combined with their indices.
225    pub fn iter_mut(&mut self) -> ArenaItemsIterMut<'_, I, T> {
226        ArenaItemsIterMut(self.vec.iter_mut().enumerate())
227    }
228
229    /// Transforms the container into an iterator over all occupied indices.
230    pub fn into_indices(self) -> ArenaItemsIntoIndices<I, T, A> {
231        ArenaItemsIntoIndices(self.vec.into_iter().enumerate())
232    }
233
234    /// Transforms the container into an iterator over all items.
235    pub fn into_values(self) -> ArenaItemsIntoValues<I, T, A> {
236        ArenaItemsIntoValues(self.vec.into_iter())
237    }
238}
239
240/// An iterator over all items combined with their ids.
241///
242/// Usually created by the [`ArenaItems::iter`](ArenaItems::iter) method.
243#[derive(Debug, Clone)]
244pub struct ArenaItemsIter<'a, I: ArenaIndex, T>(
245    iter::Enumerate<slice::Iter<'a, Either<I::Optional, T>>>
246);
247
248impl<'a, I: ArenaIndex, T> Iterator for ArenaItemsIter<'a, I, T> {
249    type Item = (I, &'a T);
250
251    fn next(&mut self) -> Option<Self::Item> {
252        loop {
253            match self.0.next() {
254                None => return None,
255                Some((_, Left(_))) => { },
256                Some((index, Right(item))) =>
257                    return Some((I::try_from_usize(index).unwrap(), item)),
258            }
259        }
260    }
261
262    fn size_hint(&self) -> (usize, Option<usize>) {
263        (0, self.0.size_hint().1)
264    }
265}
266
267impl<'a, I: ArenaIndex, T> DoubleEndedIterator for ArenaItemsIter<'a, I, T> {
268    fn next_back(&mut self) -> Option<Self::Item> {
269        loop {
270            match self.0.next_back() {
271                None => return None,
272                Some((_, Left(_))) => { },
273                Some((index, Right(item))) =>
274                    return Some((I::try_from_usize(index).unwrap(), item)),
275            }
276        }
277    }
278}
279
280impl<'a, I: ArenaIndex, T> FusedIterator for ArenaItemsIter<'a, I, T> { }
281
282/// A mutable iterator over all items combined with their ids.
283///
284/// Usually created by the [`ArenaItems::iter_mut`](ArenaItems::iter_mut) method.
285#[derive(Debug)]
286pub struct ArenaItemsIterMut<'a, I: ArenaIndex, T>(
287    iter::Enumerate<slice::IterMut<'a, Either<I::Optional, T>>>
288);
289
290impl<'a, I: ArenaIndex, T> Iterator for ArenaItemsIterMut<'a, I, T> {
291    type Item = (I, &'a mut T);
292
293    fn next(&mut self) -> Option<Self::Item> {
294        loop {
295            match self.0.next() {
296                None => return None,
297                Some((_, Left(_))) => { },
298                Some((index, Right(item))) =>
299                    return Some((I::try_from_usize(index).unwrap(), item)),
300            }
301        }
302    }
303
304    fn size_hint(&self) -> (usize, Option<usize>) {
305        (0, self.0.size_hint().1)
306    }
307}
308
309impl<'a, I: ArenaIndex, T> DoubleEndedIterator for ArenaItemsIterMut<'a, I, T> {
310    fn next_back(&mut self) -> Option<Self::Item> {
311        loop {
312            match self.0.next_back() {
313                None => return None,
314                Some((_, Left(_))) => { },
315                Some((index, Right(item))) =>
316                    return Some((I::try_from_usize(index).unwrap(), item)),
317            }
318        }
319    }
320}
321
322impl<'a, I: ArenaIndex, T> FusedIterator for ArenaItemsIterMut<'a, I, T> { }
323
324/// An iterator over all items ids.
325///
326/// Usually created by the [`ArenaItems::indices`](ArenaItems::indices) method.
327#[derive(Debug, Clone)]
328pub struct ArenaItemsIndices<'a, I: ArenaIndex, T>(
329    iter::Enumerate<slice::Iter<'a, Either<I::Optional, T>>>
330);
331
332impl<'a, I: ArenaIndex, T> Iterator for ArenaItemsIndices<'a, I, T> {
333    type Item = I;
334
335    fn next(&mut self) -> Option<Self::Item> {
336        loop {
337            match self.0.next() {
338                None => return None,
339                Some((_, Left(_))) => { },
340                Some((index, Right(_))) => return Some(I::try_from_usize(index).unwrap()),
341            }
342        }
343    }
344
345    fn size_hint(&self) -> (usize, Option<usize>) {
346        (0, self.0.size_hint().1)
347    }
348}
349
350impl<'a, I: ArenaIndex, T> DoubleEndedIterator for ArenaItemsIndices<'a, I, T> {
351    fn next_back(&mut self) -> Option<Self::Item> {
352        loop {
353            match self.0.next_back() {
354                None => return None,
355                Some((_, Left(_))) => { },
356                Some((index, Right(_))) => return Some(I::try_from_usize(index).unwrap()),
357            }
358        }
359    }
360}
361
362impl<'a, I: ArenaIndex, T> FusedIterator for ArenaItemsIndices<'a, I, T> { }
363
364/// An iterator over all items.
365///
366/// Usually created by the [`ArenaItems::values`](ArenaItems::values) method.
367#[derive(Debug, Clone)]
368pub struct ArenaItemsValues<'a, I: ArenaIndex, T>(
369    slice::Iter<'a, Either<I::Optional, T>>
370);
371
372impl<'a, I: ArenaIndex, T> Iterator for ArenaItemsValues<'a, I, T> {
373    type Item = &'a T;
374
375    fn next(&mut self) -> Option<Self::Item> {
376        loop {
377            match self.0.next() {
378                None => return None,
379                Some(Left(_)) => { },
380                Some(Right(item)) => return Some(item),
381            }
382        }
383    }
384
385    fn size_hint(&self) -> (usize, Option<usize>) {
386        (0, self.0.size_hint().1)
387    }
388}
389
390impl<'a, I: ArenaIndex, T> DoubleEndedIterator for ArenaItemsValues<'a, I, T> {
391    fn next_back(&mut self) -> Option<Self::Item> {
392        loop {
393            match self.0.next_back() {
394                None => return None,
395                Some(Left(_)) => { },
396                Some(Right(item)) => return Some(item),
397            }
398        }
399    }
400}
401
402impl<'a, I: ArenaIndex, T> FusedIterator for ArenaItemsValues<'a, I, T> { }
403
404/// A mutable iterator over all items.
405///
406/// Usually created by the [`ArenaItems::values_mut`](ArenaItems::values_mut) method.
407#[derive(Debug)]
408pub struct ArenaItemsValuesMut<'a, I: ArenaIndex, T>(
409    slice::IterMut<'a, Either<I::Optional, T>>
410);
411
412impl<'a, I: ArenaIndex, T> Iterator for ArenaItemsValuesMut<'a, I, T> {
413    type Item = &'a mut T;
414
415    fn next(&mut self) -> Option<Self::Item> {
416        loop {
417            match self.0.next() {
418                None => return None,
419                Some(Left(_)) => { },
420                Some(Right(item)) => return Some(item),
421            }
422        }
423    }
424
425    fn size_hint(&self) -> (usize, Option<usize>) {
426        (0, self.0.size_hint().1)
427    }
428}
429
430impl<'a, I: ArenaIndex, T> DoubleEndedIterator for ArenaItemsValuesMut<'a, I, T> {
431    fn next_back(&mut self) -> Option<Self::Item> {
432        loop {
433            match self.0.next_back() {
434                None => return None,
435                Some(Left(_)) => { },
436                Some(Right(item)) => return Some(item),
437            }
438        }
439    }
440}
441
442impl<'a, I: ArenaIndex, T> FusedIterator for ArenaItemsValuesMut<'a, I, T> { }
443
444/// An iterator over all occupied indices.
445///
446/// Usually created by the [`ArenaItems::into_indices`](ArenaItems::into_indices) method.
447#[derive(Debug)]
448pub struct ArenaItemsIntoIndices<I: ArenaIndex, T, A: Allocator = Global>(
449    iter::Enumerate<vec::IntoIter<Either<I::Optional, T>, A>>,
450);
451
452impl<I: ArenaIndex, T, A: Allocator> Iterator for ArenaItemsIntoIndices<I, T, A> {
453    type Item = I;
454
455    fn next(&mut self) -> Option<Self::Item> {
456        loop {
457            match self.0.next() {
458                None => return None,
459                Some((_, Left(_))) => { },
460                Some((index, Right(_))) => return Some(I::try_from_usize(index).unwrap()),
461            }
462        }
463    }
464
465    fn size_hint(&self) -> (usize, Option<usize>) {
466        (0, self.0.size_hint().1)
467    }
468}
469
470impl<I: ArenaIndex, T, A: Allocator> DoubleEndedIterator for ArenaItemsIntoIndices<I, T, A> {
471    fn next_back(&mut self) -> Option<Self::Item> {
472        loop {
473            match self.0.next_back() {
474                None => return None,
475                Some((_, Left(_))) => { },
476                Some((index, Right(_))) => return Some(I::try_from_usize(index).unwrap()),
477            }
478        }
479    }
480}
481
482impl<I: ArenaIndex, T, A: Allocator> FusedIterator for ArenaItemsIntoIndices<I, T, A> { }
483
484/// An iterator over all items.
485///
486/// Usually created by the [`ArenaItems::into_values`](ArenaItems::into_values) method.
487#[derive(Debug)]
488pub struct ArenaItemsIntoValues<I: ArenaIndex, T, A: Allocator = Global>(
489    vec::IntoIter<Either<I::Optional, T>, A>,
490);
491
492impl<I: ArenaIndex, T, A: Allocator> Iterator for ArenaItemsIntoValues<I, T, A> {
493    type Item = T;
494
495    fn next(&mut self) -> Option<Self::Item> {
496        loop {
497            match self.0.next() {
498                None => return None,
499                Some(Left(_)) => { },
500                Some(Right(item)) => return Some(item),
501            }
502        }
503    }
504
505    fn size_hint(&self) -> (usize, Option<usize>) {
506        (0, self.0.size_hint().1)
507    }
508}
509
510impl<I: ArenaIndex, T, A: Allocator> DoubleEndedIterator for ArenaItemsIntoValues<I, T, A> {
511    fn next_back(&mut self) -> Option<Self::Item> {
512        loop {
513            match self.0.next_back() {
514                None => return None,
515                Some(Left(_)) => { },
516                Some(Right(item)) => return Some(item),
517            }
518        }
519    }
520}
521
522impl<I: ArenaIndex, T, A: Allocator> FusedIterator for ArenaItemsIntoValues<I, T, A> { }
523
524/// An iterator over all items combined with their ids.
525///
526/// Usually created by the [`ArenaItems::into_iter`](ArenaItems::into_iter) method.
527#[derive(Debug, Clone)]
528pub struct ArenaItemsIntoIter<I: ArenaIndex, T, A: Allocator = Global>(
529    iter::Enumerate<vec::IntoIter<Either<I::Optional, T>, A>>,
530);
531
532impl<I: ArenaIndex, T, A: Allocator> Iterator for ArenaItemsIntoIter<I, T, A> {
533    type Item = (I, T);
534
535    fn next(&mut self) -> Option<Self::Item> {
536        loop {
537            match self.0.next() {
538                None => return None,
539                Some((_, Left(_))) => { },
540                Some((index, Right(item))) =>
541                    return Some((I::try_from_usize(index).unwrap(), item)),
542            }
543        }
544    }
545
546    fn size_hint(&self) -> (usize, Option<usize>) {
547        (0, self.0.size_hint().1)
548    }
549}
550
551impl<I: ArenaIndex, T, A: Allocator> DoubleEndedIterator for ArenaItemsIntoIter<I, T, A> {
552    fn next_back(&mut self) -> Option<Self::Item> {
553        loop {
554            match self.0.next_back() {
555                None => return None,
556                Some((_, Left(_))) => { },
557                Some((index, Right(item))) =>
558                    return Some((I::try_from_usize(index).unwrap(), item)),
559            }
560        }
561    }
562}
563
564impl<I: ArenaIndex, T, A: Allocator> FusedIterator for ArenaItemsIntoIter<I, T, A> { }
565
566impl<I: ArenaIndex, T, A: Allocator> IntoIterator for ArenaItems<I, T, A> {
567    type Item = (I, T);
568    type IntoIter = ArenaItemsIntoIter<I, T, A>;
569
570    fn into_iter(self) -> Self::IntoIter {
571        ArenaItemsIntoIter(self.vec.into_iter().enumerate())
572    }
573}
574
575impl<'a, I: ArenaIndex, T, A: Allocator> IntoIterator for &'a ArenaItems<I, T, A> {
576    type Item = (I, &'a T);
577    type IntoIter = ArenaItemsIter<'a, I, T>;
578
579    fn into_iter(self) -> Self::IntoIter { self.iter() }
580}
581
582mod forgettable_field {
583    use core::fmt::{self, Debug, Formatter};
584    use core::mem::{MaybeUninit, forget, replace};
585    use core::ops::{Deref, DerefMut};
586
587    pub struct ForgettableField<T>(MaybeUninit<T>);
588
589    impl<T> ForgettableField<T> {
590        pub const fn new(value: T) -> Self { ForgettableField(MaybeUninit::new(value)) }
591
592        pub fn into_inner(mut this: Self) -> T {
593            let inner = replace(&mut this.0, MaybeUninit::uninit());
594            forget(this);
595            unsafe { inner.assume_init() }
596        }
597
598        pub fn take_and_forget<Owner>(mut owner: Owner, f: impl FnOnce(&mut Owner) -> &mut Self) -> T {
599            let this = replace(f(&mut owner), ForgettableField(MaybeUninit::uninit()));
600            forget(owner);
601            Self::into_inner(this)
602        }
603    }
604
605    impl<T> Drop for ForgettableField<T> {
606        fn drop(&mut self) {
607            unsafe { self.0.assume_init_drop() }
608        }
609    }
610
611    impl<T> Deref for ForgettableField<T> {
612        type Target = T;
613
614        fn deref(&self) -> &T { unsafe { self.0.assume_init_ref() } }
615    }
616
617    impl<T> DerefMut for ForgettableField<T> {
618        fn deref_mut(&mut self) -> &mut T { unsafe { self.0.assume_init_mut() } }
619    }
620
621    impl<T: Default> Default for ForgettableField<T> {
622        fn default() -> Self { ForgettableField::new(T::default()) }
623    }
624
625    impl<T: Debug> Debug for ForgettableField<T> {
626        fn fmt(&self, f: &mut Formatter) -> fmt::Result {
627            self.deref().fmt(f)
628        }
629    }
630}
631
632use forgettable_field::*;
633
634/// Unordered container with random access.
635#[derive(Debug)]
636pub struct Arena<I: ArenaIndex, T: 'static, A: Allocator = Global> {
637    items: ForgettableField<ArenaItems<I, T, A>>,
638}
639
640impl<I: ArenaIndex, T> Arena<I, T, Global> {
641    /// Decomposes `Arena` into raw components.
642    ///
643    /// Use [`from_raw_parts`](Arena::from_raw_parts) to assemble `Arena` back.
644    pub fn into_raw_parts(self) -> (usize, usize, usize, I::Optional) {
645        let items = ForgettableField::take_and_forget(self, |x| &mut x.items);
646        let (ptr, len, capacity, _) = items.vec.into_raw_parts_with_alloc();
647        let vacancy = items.vacancy;
648        let ptr = ptr.expose_provenance();
649        (ptr, len, capacity, vacancy)
650    }
651
652    /// Creates an `Arena` from raw parts.
653    ///
654    /// # Safety
655    ///
656    /// Raw parts must be obtained using [`into_raw_parts`](Arena::into_raw_parts) method
657    /// of same type.
658    pub unsafe fn from_raw_parts(a: usize, b: usize, c: usize, d: I::Optional) -> Self {
659        Arena {
660            items: ForgettableField::new(ArenaItems {
661                vec: Vec::from_raw_parts_in(ptr::with_exposed_provenance_mut(a), b, c, Global),
662                vacancy: d,
663            })
664        }
665    }
666}
667
668impl<I: ArenaIndex, T, A: Allocator> Arena<I, T, A> {
669    /// Decomposes `Arena` into raw components including allocator.
670    ///
671    /// Use [`from_raw_parts_in`](Arena::from_raw_parts_in) to assemble `Arena` back.
672    pub fn into_raw_parts_with_alloc(self) -> (usize, usize, usize, I::Optional, A) {
673        let items = ForgettableField::take_and_forget(self, |x| &mut x.items);
674        let (ptr, len, capacity, alloc) = items.vec.into_raw_parts_with_alloc();
675        let vacancy = items.vacancy;
676        let ptr = ptr.expose_provenance();
677        (ptr, len, capacity, vacancy, alloc)
678    }
679
680    /// Creates an `Arena` from raw parts including allocator.
681    ///
682    /// # Safety
683    ///
684    /// Raw parts must be obtained using [`into_raw_parts_with_alloc`](Arena::into_raw_parts_with_alloc) method
685    /// of same type.
686    pub unsafe fn from_raw_parts_in(a: usize, b: usize, c: usize, d: I::Optional, alloc: A) -> Self {
687        Arena {
688            items: ForgettableField::new(ArenaItems {
689                vec: Vec::from_raw_parts_in(ptr::with_exposed_provenance_mut(a), b, c, alloc),
690                vacancy: d,
691            })
692        }
693    }
694
695    /// Creates an arena instance.
696    pub const fn new() -> Self where A: ConstDefault {
697        Self::new_in(ConstDefault::DEFAULT)
698    }
699
700    /// Creates an arena instance with the specified initial capacity.
701    pub fn with_capacity(capacity: usize) -> Self where A: ConstDefault {
702        Self::with_capacity_in(capacity, ConstDefault::DEFAULT)
703    }
704
705    /// Creates an arena instance.
706    pub const fn new_in(alloc: A) -> Self {
707        Arena {
708            items: ForgettableField::new(ArenaItems::new_in(alloc))
709        }
710    }
711
712    /// Creates an arena instance with the specified initial capacity.
713    pub fn with_capacity_in(capacity: usize, alloc: A) -> Self {
714        Arena {
715            items: ForgettableField::new(ArenaItems::with_capacity_in(capacity, alloc))
716        }
717    }
718
719    /// Returns contained items packed in a special container.
720    /// While arena itself is unique (i.e. non-clonable) object,
721    /// this special container could be cloned.
722    pub fn into_items(#[allow(unused_mut)] mut self) -> ArenaItems<I, T, A> {
723        ForgettableField::take_and_forget(self, |x| &mut x.items)
724    }
725
726    /// Returns reference to contained items packed in a special container.
727    /// While arena itself is unique (i.e. non-clonable) object,
728    /// this special container could be cloned.
729    pub fn items(&self) -> &ArenaItems<I, T, A> { &self.items }
730
731    /// Returns mutable reference to contained items packed in
732    /// a (mostly read-only) special container.
733    /// While arena itself is unique (i.e. non-clonable) object,
734    /// this special container could be cloned.
735    pub fn items_mut(&mut self) -> &mut ArenaItems<I, T, A> { &mut self.items }
736
737    /// Reserves capacity for at least one more element.
738    /// The collection may reserve more space to avoid frequent reallocations.
739    /// After calling `reserve`, capacity will be greater than or equal to
740    /// `self.items().len() + 1`. Does nothing if capacity is already sufficient.
741    ///
742    /// # Panics
743    ///
744    /// Panics if the required capacity overflows maximum index value + 1.
745    pub fn reserve(&mut self) {
746        if self.items().len_equals_to_min_capacity() {
747            self.items_mut().reserve(1);
748            assert!(I::try_from_usize(self.items().min_capacity()).is_some());
749        }
750    }
751
752    /// Reserves the minimum capacity for exactly one more element.
753    /// After calling `reserve_exact`, capacity will be greater than or equal to
754    /// `self.items().len() + 1`. Does nothing if the capacity is already sufficient.
755    ///
756    /// Note that the allocator may give the collection more space than it requests.
757    /// Therefore, capacity can not be relied upon to be precisely minimal.
758    /// Prefer [`reserve`](Arena::reserve) if future insertions are expected.
759    ///
760    /// # Panics
761    ///
762    /// Panics if the required capacity overflows maximum index value + 1.
763    pub fn reserve_exact(&mut self) {
764        if self.items().len_equals_to_min_capacity() {
765            self.items_mut().reserve_exact(1);
766            assert!(I::try_from_usize(self.items().min_capacity()).is_some());
767        }
768    }
769
770    /// Tries to reserve capacity for at least one more element.
771    /// The collection may reserve more space to avoid frequent reallocations.
772    /// After calling `try_reserve`, capacity will be greater than or equal
773    /// to `self.items().len() + 1`. Does nothing if capacity is already sufficient.
774    ///
775    /// # Errors
776    ///
777    /// If the capacity overflows, or the allocator reports a failure, then an error is returned.
778    pub fn try_reserve(&mut self) -> Result<(), TryReserveError> {
779        if self.items().len_equals_to_min_capacity() {
780            self.items_mut().try_reserve(1)?;
781            I::try_from_usize(self.items().min_capacity())
782                .ok_or(TryReserveError::from(TryReserveErrorKind::CapacityOverflow)).map(|_| ())
783        } else {
784            Ok(())
785        }
786    }
787
788    /// Tries to reserve capacity for exactly one more element.
789    /// The collection may reserve more space to avoid frequent reallocations.
790    /// After calling `try_reserve_exact`, capacity will be greater than or equal
791    /// to `self.items().len() + 1`. Does nothing if capacity is already sufficient.
792    ///
793    /// Note that the allocator may give the collection more space than it requests.
794    /// Therefore, capacity can not be relied upon to be precisely minimal.
795    /// Prefer [`try_reserve`](Arena::try_reserve) if future insertions are expected.
796    ///
797    /// # Errors
798    ///
799    /// If the capacity overflows, or the allocator reports a failure, then an error is returned.
800    pub fn try_reserve_exact(&mut self) -> Result<(), TryReserveError> {
801        if self.items().len_equals_to_min_capacity() {
802            self.items_mut().try_reserve_exact(1)?;
803            I::try_from_usize(self.items().min_capacity())
804                .ok_or(TryReserveError::from(TryReserveErrorKind::CapacityOverflow)).map(|_| ())
805        } else {
806            Ok(())
807        }
808    }
809
810    /// Place new item into the arena.
811    ///
812    /// # Examples
813    ///
814    /// ```rust
815    /// # use arena_container::Arena;
816    /// #
817    /// # struct Data { /* ... */ }
818    /// #
819    /// # fn main() {
820    /// let mut arena: Arena<usize, Data> = Arena::new();
821    /// let new_item_index = arena.insert(|index| (Data { /* ... */ }, index));
822    /// # }
823    /// ```
824    pub fn insert<R>(&mut self, item: impl FnOnce(I) -> (T, R)) -> R {
825        if let Some(index) = I::to_option(self.items.vacancy) {
826            let (item, result) = item(index);
827            self.items.vacancy = replace(&mut self.items.vec[I::try_to_usize(index).unwrap()], Right(item)).left()
828                .unwrap_or_else(|| unsafe { unreachable_unchecked() });
829            result
830        } else {
831            let index = I::try_from_usize(self.items.len()).expect("out of indices");
832            let (item, result) = item(index);
833            self.items.vec.push(Right(item));
834            result
835        }
836    }
837
838    /// Removes item with provided index.
839    ///
840    /// Panics if index is not occupied.
841    pub fn remove(&mut self, index: I) -> T {
842        let vacancy = self.items.vacancy;
843        match replace(&mut self.items.vec[I::try_to_usize(index).expect("invalid index")], Left(vacancy)) {
844            Left(vacancy) => {
845                self.items.vec[I::try_to_usize(index).unwrap()] = Left(vacancy);
846                panic!("invalid index");
847            },
848            Right(item) => {
849                self.items.vacancy = I::some(index);
850                item
851            }
852        }
853    }
854}
855
856impl<I: ArenaIndex, T, A: Allocator> Default for Arena<I, T, A> where A: ConstDefault {
857    fn default() -> Self { Arena::new() }
858}
859
860impl<I: ArenaIndex, T, A: Allocator> Index<I> for Arena<I, T, A> {
861    type Output = T;
862
863    fn index(&self, index: I) -> &T {
864        self.items.vec[I::try_to_usize(index).expect("invalid index")].as_ref().right().expect("invalid index")
865    }
866}
867
868impl<I: ArenaIndex, T, A: Allocator> IndexMut<I> for Arena<I, T, A> {
869    fn index_mut(&mut self, index: I) -> &mut T {
870        self.items.vec[I::try_to_usize(index).expect("invalid index")].as_mut().right().expect("invalid index")
871    }
872}
873
874#[cfg(test)]
875mod test {
876    use quickcheck_macros::quickcheck;
877
878    use core::num::NonZeroU32;
879    use core::sync::atomic::{AtomicI8, Ordering};
880    use crate::*;
881
882    struct Test {
883        this: NonZeroU32,
884        value: i8
885    }
886
887    const fn _new_test_arena() -> Arena<NonZeroU32, Test> {
888        Arena::new()
889    }
890
891    struct TestWithDrop {
892        value: i8
893    }
894
895    static TEST_DROP: AtomicI8 = AtomicI8::new(-1);
896
897    const fn _new_test_with_drop_arena() -> Arena<NonZeroU32, TestWithDrop> {
898        Arena::new()
899    }
900
901    impl Drop for TestWithDrop {
902        fn drop(&mut self) {
903            TEST_DROP.store(self.value, Ordering::SeqCst);
904        }
905    }
906
907    #[quickcheck]
908    fn new_arena_min_capacity_is_zero(capacity: Option<u8>) -> bool {
909        let capacity = capacity.map(|capacity| capacity as usize);
910        capacity.map_or_else(
911            || <Arena::<NonZeroU32, Test>>::new(),
912            |capacity| <Arena::<NonZeroU32, Test>>::with_capacity(capacity)
913        ).items().min_capacity() == 0
914    }
915
916    #[quickcheck]
917    fn arena_contains_inserted_item(capacity: Option<u8>, value: i8) -> bool {
918        let capacity = capacity.map(|capacity| capacity as usize);
919        let mut arena = capacity.map_or_else(
920            || <Arena::<NonZeroU32, Test>>::new(),
921            |capacity| <Arena::<NonZeroU32, Test>>::with_capacity(capacity)
922        );
923        let index = arena.insert(|this| (Test { this, value }, this));
924        arena[index].this == index && arena[index].value == value
925    }
926
927    #[test]
928    fn drop_components() {
929        {
930            let mut arena: Arena<NonZeroU32, TestWithDrop> = Arena::new();
931            arena.insert(|this: NonZeroU32| (TestWithDrop { value: 7 }, this));
932            TEST_DROP.store(-1, Ordering::SeqCst);
933        }
934        assert_eq!(TEST_DROP.load(Ordering::SeqCst), 7);
935    }
936
937    #[test]
938    fn try_reserve() {
939        let mut arena: Arena<i8, ()> = Arena::new();
940        while arena.try_reserve().is_ok() {
941            arena.insert(|_| ((), ()));
942        }
943    }
944}
arena_container/nightly.rs

arena_container/
nightly.rs
