fyrox_core/pool/
mod.rs

1// Copyright (c) 2019-present Dmitry Stepanov and Fyrox Engine contributors.
2//
3// Permission is hereby granted, free of charge, to any person obtaining a copy
4// of this software and associated documentation files (the "Software"), to deal
5// in the Software without restriction, including without limitation the rights
6// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
7// copies of the Software, and to permit persons to whom the Software is
8// furnished to do so, subject to the following conditions:
9//
10// The above copyright notice and this permission notice shall be included in all
11// copies or substantial portions of the Software.
12//
13// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
14// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
15// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
16// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
17// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
18// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
19// SOFTWARE.
20
21//! A generational arena - a contiguous growable array type which allows removing
22//! from the middle without shifting and therefore without invalidating other indices.
23//!
24//! Pool is a contiguous block of memory with fixed-size entries, each entry can be
25//! either vacant or occupied. When you put an object into the pool you get a handle to
26//! that object. You can use that handle later on to borrow a reference to an object.
27//! A handle can point to some object or be invalid, this may look similar to raw
28//! pointers, but there is two major differences:
29//!
30//! 1) We can check if a handle is valid before accessing the object it might point to.
31//! 2) We can ensure the handle we're using is still valid for the object it points to
32//! to make sure it hasn't been replaced with a different object on the same position.
33//! Each handle stores a special field called generation which is shared across the entry
34//! and the handle, so the handle is valid if these fields are the same on both the entry
35//! and the handle. This protects from situations where you have a handle that has
36//! a valid index of a record, but the payload in this record has been replaced.
37//!
38//! Contiguous memory block increases efficiency of memory operations - the CPU will
39//! load portions of data into its cache piece by piece, it will be free from any
40//! indirections that might cause cache invalidation. This is the so called cache
41//! friendliness.
42
43use crate::{reflect::prelude::*, visitor::prelude::*, ComponentProvider};
44use std::cell::UnsafeCell;
45use std::fmt::{Display, Formatter};
46use std::{
47    any::{Any, TypeId},
48    fmt::Debug,
49    future::Future,
50    marker::PhantomData,
51    ops::{Index, IndexMut},
52};
53
54pub mod handle;
55pub mod multiborrow;
56pub mod payload;
57
58pub use handle::*;
59pub use multiborrow::*;
60pub use payload::*;
61
62const INVALID_GENERATION: u32 = 0;
63
64/// Pool allows to create as many objects as you want in contiguous memory
65/// block. It allows to create and delete objects much faster than if they'll
66/// be allocated on heap. Also since objects stored in contiguous memory block
67/// they can be effectively accessed because such memory layout is cache-friendly.
68pub struct Pool<T, P = Option<T>>
69where
70    T: Sized,
71    P: PayloadContainer<Element = T>,
72{
73    records: Vec<PoolRecord<T, P>>,
74    free_stack: Vec<u32>,
75}
76
77impl<T: Sized + Debug, P: PayloadContainer<Element = T> + 'static> Debug for Pool<T, P> {
78    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
79        let mut s = f.debug_struct("Pool");
80        for (handle, value) in self.pair_iter() {
81            s.field(&handle.to_string(), value);
82        }
83        s.finish()
84    }
85}
86
87/// This trait unifies pool objects and their variants.
88///
89/// If T is the pool object type, [`ObjectOrVariant::convert_to_dest_type`] returns the pool object itself.
90///
91/// If T is a variant of the pool object type, [`ObjectOrVariant::convert_to_dest_type`] returns the variant of the pool object.
92///
93/// The [`Pool`] struct uses this trait to unify the logic of retrieving both pool objects and their variants.
94pub trait ObjectOrVariant<T> {
95    fn convert_to_dest_type(object: &T) -> Option<&Self>;
96    fn convert_to_dest_type_mut(object: &mut T) -> Option<&mut Self>;
97}
98
99/// This trait is a helper trait for implementing [`ObjectOrVariant`] indirectly in child crates.
100///
101/// To implement [`ObjectOrVariant`] for type `U` in a child crate, you need to implement [`ObjectOrVariantHelper`] for [`PhantomData<U>`].
102///
103/// This is necessary because Rust does not support `impl<T> ForeignTrait<LocalType> for T`
104///
105/// But Rust does support `impl<T> ForeignTrait<LocalType> for ForeignType<T>`
106///
107/// Details can be found in [here](https://rust-lang.github.io/rfcs/2451-re-rebalancing-coherence.html#concrete-orphan-rules).
108///
109/// Therefore, we cannot implement [`ObjectOrVariant`] directly using `impl<U: TraitBound> ObjectOrVariant<LocalType> for U`
110///
111/// but we can do `impl<U: TraitBound> ObjectOrVariantHelper<LocalType, U> for PhantomData<U>`
112///
113/// There is an indirection to get rid of [`PhantomData<U>`] because we want to have a clean API for pool methods
114/// where you can pass in `U` directly instead of [`PhantomData<U>`].
115pub trait ObjectOrVariantHelper<T, U> {
116    fn convert_to_dest_type_helper(object: &T) -> Option<&U>;
117    fn convert_to_dest_type_helper_mut(object: &mut T) -> Option<&mut U>;
118}
119
120// This is the default implementation for pool object types.
121// For pool object variant types, they need to be implemented case by case, since Rust does not support multiple blanket implementations.
122impl<T> ObjectOrVariantHelper<T, T> for PhantomData<T> {
123    fn convert_to_dest_type_helper(object: &T) -> Option<&T> {
124        Some(object)
125    }
126    fn convert_to_dest_type_helper_mut(object: &mut T) -> Option<&mut T> {
127        Some(object)
128    }
129}
130
131// This blanket implementation wraps types that implement ObjectOrVariantHelper with the ObjectOrVariant trait.
132impl<T, U> ObjectOrVariant<T> for U
133where
134    PhantomData<U>: ObjectOrVariantHelper<T, U>,
135{
136    fn convert_to_dest_type(object: &T) -> Option<&Self> {
137        PhantomData::<U>::convert_to_dest_type_helper(object)
138    }
139    fn convert_to_dest_type_mut(object: &mut T) -> Option<&mut Self> {
140        PhantomData::<U>::convert_to_dest_type_helper_mut(object)
141    }
142}
143
144impl<T, P> Reflect for Pool<T, P>
145where
146    T: Reflect,
147    P: PayloadContainer<Element = T> + Reflect,
148    Pool<T, P>: Clone,
149{
150    #[inline]
151    fn source_path() -> &'static str {
152        file!()
153    }
154
155    fn derived_types() -> &'static [TypeId]
156    where
157        Self: Sized,
158    {
159        &[]
160    }
161
162    fn try_clone_box(&self) -> Option<Box<dyn Reflect>> {
163        Some(Box::new(self.clone()))
164    }
165
166    fn query_derived_types(&self) -> &'static [TypeId] {
167        Self::derived_types()
168    }
169
170    #[inline]
171    fn type_name(&self) -> &'static str {
172        std::any::type_name::<Self>()
173    }
174
175    #[inline]
176    fn doc(&self) -> &'static str {
177        ""
178    }
179
180    #[inline]
181    fn fields_ref(&self, func: &mut dyn FnMut(&[FieldRef])) {
182        func(&[])
183    }
184
185    #[inline]
186    fn fields_mut(&mut self, func: &mut dyn FnMut(&mut [FieldMut])) {
187        func(&mut [])
188    }
189
190    #[inline]
191    fn into_any(self: Box<Self>) -> Box<dyn Any> {
192        self
193    }
194
195    #[inline]
196    fn as_any(&self, func: &mut dyn FnMut(&dyn Any)) {
197        func(self)
198    }
199
200    #[inline]
201    fn as_any_mut(&mut self, func: &mut dyn FnMut(&mut dyn Any)) {
202        func(self)
203    }
204
205    #[inline]
206    fn as_reflect(&self, func: &mut dyn FnMut(&dyn Reflect)) {
207        func(self)
208    }
209
210    #[inline]
211    fn as_reflect_mut(&mut self, func: &mut dyn FnMut(&mut dyn Reflect)) {
212        func(self)
213    }
214
215    #[inline]
216    fn set(&mut self, value: Box<dyn Reflect>) -> Result<Box<dyn Reflect>, Box<dyn Reflect>> {
217        let this = std::mem::replace(self, value.take()?);
218        Ok(Box::new(this))
219    }
220
221    fn assembly_name(&self) -> &'static str {
222        env!("CARGO_PKG_NAME")
223    }
224
225    fn type_assembly_name() -> &'static str {
226        env!("CARGO_PKG_NAME")
227    }
228
229    #[inline]
230    fn as_array(&self, func: &mut dyn FnMut(Option<&dyn ReflectArray>)) {
231        func(Some(self))
232    }
233
234    #[inline]
235    fn as_array_mut(&mut self, func: &mut dyn FnMut(Option<&mut dyn ReflectArray>)) {
236        func(Some(self))
237    }
238}
239
240impl<T, P> ReflectArray for Pool<T, P>
241where
242    T: Reflect,
243    P: PayloadContainer<Element = T> + Reflect,
244    Pool<T, P>: Clone,
245{
246    #[inline]
247    fn reflect_index(&self, index: usize) -> Option<&dyn Reflect> {
248        self.at(index as u32).ok().map(|p| p as &dyn Reflect)
249    }
250
251    #[inline]
252    fn reflect_index_mut(&mut self, index: usize) -> Option<&mut dyn Reflect> {
253        self.at_mut(index as u32)
254            .ok()
255            .map(|p| p as &mut dyn Reflect)
256    }
257
258    #[inline]
259    fn reflect_len(&self) -> usize {
260        self.get_capacity() as usize
261    }
262}
263
264impl<T, P> PartialEq for Pool<T, P>
265where
266    T: PartialEq,
267    P: PayloadContainer<Element = T> + PartialEq,
268{
269    #[inline]
270    fn eq(&self, other: &Self) -> bool {
271        self.records == other.records
272    }
273}
274
275// Zero - non-borrowed.
276// Negative values - amount of mutable borrows, positive - amount of immutable borrows.
277#[derive(Default, Debug)]
278struct RefCounter(pub UnsafeCell<isize>);
279
280unsafe impl Sync for RefCounter {}
281unsafe impl Send for RefCounter {}
282
283impl RefCounter {
284    unsafe fn get(&self) -> isize {
285        *self.0.get()
286    }
287
288    unsafe fn increment(&self) {
289        *self.0.get() += 1;
290    }
291
292    unsafe fn decrement(&self) {
293        *self.0.get() -= 1;
294    }
295}
296
297#[derive(Debug)]
298struct PoolRecord<T, P = Option<T>>
299where
300    T: Sized,
301    P: PayloadContainer<Element = T>,
302{
303    ref_counter: RefCounter,
304    // Generation number, used to keep info about lifetime. The handle is valid
305    // only if record it points to is of the same generation as the pool record.
306    // Notes: Zero is unknown generation used for None handles.
307    generation: u32,
308    // Actual payload.
309    payload: Payload<P>,
310}
311
312impl<T, P> PartialEq for PoolRecord<T, P>
313where
314    T: PartialEq,
315    P: PayloadContainer<Element = T> + PartialEq,
316{
317    #[inline]
318    fn eq(&self, other: &Self) -> bool {
319        self.generation == other.generation && self.payload.get() == other.payload.get()
320    }
321}
322
323impl<T, P> Default for PoolRecord<T, P>
324where
325    P: PayloadContainer<Element = T> + 'static,
326{
327    #[inline]
328    fn default() -> Self {
329        Self {
330            ref_counter: Default::default(),
331            generation: INVALID_GENERATION,
332            payload: Payload::new_empty(),
333        }
334    }
335}
336
337impl<T, P> Visit for PoolRecord<T, P>
338where
339    T: Visit + 'static,
340    P: PayloadContainer<Element = T> + Visit,
341{
342    #[inline]
343    fn visit(&mut self, name: &str, visitor: &mut Visitor) -> VisitResult {
344        let mut region = visitor.enter_region(name)?;
345
346        self.generation.visit("Generation", &mut region)?;
347        self.payload.get_mut().visit("Payload", &mut region)?;
348
349        Ok(())
350    }
351}
352
353impl<T> Clone for Handle<T> {
354    #[inline]
355    fn clone(&self) -> Handle<T> {
356        *self
357    }
358}
359
360impl<T, P> Visit for Pool<T, P>
361where
362    T: Visit + 'static,
363    P: PayloadContainer<Element = T> + Default + Visit + 'static,
364{
365    #[inline]
366    fn visit(&mut self, name: &str, visitor: &mut Visitor) -> VisitResult {
367        let mut region = visitor.enter_region(name)?;
368        self.records.visit("Records", &mut region)?;
369        self.free_stack.visit("FreeStack", &mut region)?;
370        Ok(())
371    }
372}
373
374impl<T, P> Default for Pool<T, P>
375where
376    T: 'static,
377    P: PayloadContainer<Element = T> + 'static,
378{
379    #[inline]
380    fn default() -> Self {
381        Self::new()
382    }
383}
384
385#[derive(Debug)]
386pub struct Ticket<T> {
387    index: u32,
388    marker: PhantomData<T>,
389}
390
391impl<T> Drop for Ticket<T> {
392    fn drop(&mut self) {
393        panic!(
394            "An object at index {} must be returned to a pool it was taken from! \
395            Call Pool::forget_ticket if you don't need the object anymore.",
396            self.index
397        )
398    }
399}
400
401impl<T, P> Clone for PoolRecord<T, P>
402where
403    T: Clone,
404    P: PayloadContainer<Element = T> + Clone + 'static,
405{
406    #[inline]
407    fn clone(&self) -> Self {
408        Self {
409            ref_counter: Default::default(),
410            generation: self.generation,
411            payload: self.payload.clone(),
412        }
413    }
414}
415
416impl<T, P> Clone for Pool<T, P>
417where
418    P: PayloadContainer<Element = T> + Clone + 'static,
419    T: Clone,
420{
421    #[inline]
422    fn clone(&self) -> Self {
423        Self {
424            records: self.records.clone(),
425            free_stack: self.free_stack.clone(),
426        }
427    }
428}
429
430#[derive(PartialEq, Copy, Clone)]
431pub enum PoolError {
432    InvalidIndex(u32),
433    InvalidGeneration(u32),
434    InvalidType(ErasedHandle),
435    Empty(ErasedHandle),
436    NoSuchComponent(ErasedHandle),
437    MutablyBorrowed(ErasedHandle),
438    ImmutablyBorrowed(ErasedHandle),
439    UnknownDependentObject(ErasedHandle),
440}
441
442impl std::error::Error for PoolError {}
443
444impl Display for PoolError {
445    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
446        match self {
447            Self::InvalidIndex(index) => {
448                write!(
449                    f,
450                    "The index {index} of the handle is invalid and does not point to any object!"
451                )
452            }
453            Self::InvalidGeneration(generation) => {
454                write!(
455                    f,
456                    "The generation {generation} of the handle is invalid! It means that the object \
457                    at the handle was freed and it position was taken by some other object."
458                )
459            }
460            Self::InvalidType(handle) => {
461                write!(
462                    f,
463                    "The type of the object at the handle {handle} is different from what was requested!"
464                )
465            }
466            Self::Empty(handle) => {
467                write!(f, "There's no object at {handle} handle.")
468            }
469            Self::UnknownDependentObject(handle) => {
470                write!(
471                    f,
472                    "Unable to fetch the dependent object by handle {handle}, because the handle \
473                is invalid!"
474                )
475            }
476            Self::NoSuchComponent(handle) => write!(
477                f,
478                "An object at {handle} handle does not have such component.",
479            ),
480            Self::MutablyBorrowed(handle) => {
481                write!(
482                    f,
483                    "An object at {handle} handle cannot be borrowed immutably, because it is \
484                    already borrowed mutably."
485                )
486            }
487            Self::ImmutablyBorrowed(handle) => {
488                write!(
489                    f,
490                    "An object at {handle} handle cannot be borrowed mutably, because it is \
491                    already borrowed immutably."
492                )
493            }
494        }
495    }
496}
497
498impl Debug for PoolError {
499    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
500        write!(f, "{}", self)
501    }
502}
503
504impl<T, P> Pool<T, P>
505where
506    P: PayloadContainer<Element = T> + 'static,
507{
508    #[inline]
509    pub fn new() -> Self {
510        Pool {
511            records: Vec::new(),
512            free_stack: Vec::new(),
513        }
514    }
515
516    #[inline]
517    pub fn with_capacity(capacity: u32) -> Self {
518        let capacity = usize::try_from(capacity).expect("capacity overflowed usize");
519        Pool {
520            records: Vec::with_capacity(capacity),
521            free_stack: Vec::new(),
522        }
523    }
524
525    fn records_len(&self) -> u32 {
526        u32::try_from(self.records.len()).expect("Number of records overflowed u32")
527    }
528
529    fn records_get(&self, index: u32) -> Result<&PoolRecord<T, P>, PoolError> {
530        self.records
531            .get(usize::try_from(index).expect("Index overflowed usize"))
532            .ok_or(PoolError::InvalidIndex(index))
533    }
534
535    fn records_get_mut(&mut self, index: u32) -> Result<&mut PoolRecord<T, P>, PoolError> {
536        self.records
537            .get_mut(usize::try_from(index).expect("Index overflowed usize"))
538            .ok_or(PoolError::InvalidIndex(index))
539    }
540
541    #[inline]
542    pub fn try_get<U: ObjectOrVariant<T>>(&self, handle: Handle<U>) -> Result<&U, PoolError> {
543        let handle = handle.transmute();
544        let pool_object = self.try_borrow(handle)?;
545        U::convert_to_dest_type(pool_object).ok_or(PoolError::InvalidType(handle.into()))
546    }
547
548    #[inline]
549    pub fn try_get_mut<U: ObjectOrVariant<T>>(
550        &mut self,
551        handle: Handle<U>,
552    ) -> Result<&mut U, PoolError> {
553        let handle = handle.transmute();
554        let pool_object = self.try_borrow_mut(handle)?;
555        U::convert_to_dest_type_mut(pool_object).ok_or(PoolError::InvalidType(handle.into()))
556    }
557
558    #[inline]
559    #[must_use]
560    pub fn spawn(&mut self, payload: T) -> Handle<T> {
561        self.spawn_with(|_| payload)
562    }
563
564    /// Tries to put an object in the pool at given position. Returns `Err(payload)` if a corresponding
565    /// entry is occupied.
566    ///
567    /// # Performance
568    ///
569    /// The method has O(n) complexity in worst case, where `n` - amount of free records in the pool.
570    /// In typical uses cases `n` is very low. It should be noted that if a pool is filled entirely
571    /// and you trying to put an object at the end of pool, the method will have O(1) complexity.
572    ///
573    /// # Panics
574    ///
575    /// Panics if the index is occupied or reserved (e.g. by [`take_reserve`]).
576    ///
577    /// [`take_reserve`]: Pool::take_reserve
578    #[inline]
579    pub fn spawn_at(&mut self, index: u32, payload: T) -> Result<Handle<T>, T> {
580        self.spawn_at_internal(index, INVALID_GENERATION, payload)
581    }
582
583    /// Tries to put an object in the pool at given handle. Returns `Err(payload)` if a corresponding
584    /// entry is occupied.
585    ///
586    /// # Performance
587    ///
588    /// The method has O(n) complexity in worst case, where `n` - amount of free records in the pool.
589    /// In typical uses cases `n` is very low. It should be noted that if a pool is filled entirely
590    /// and you trying to put an object at the end of pool, the method will have O(1) complexity.
591    ///
592    /// # Panics
593    ///
594    /// Panics if the index is occupied or reserved (e.g. by [`take_reserve`]).
595    ///
596    /// [`take_reserve`]: Pool::take_reserve
597    #[inline]
598    pub fn spawn_at_handle(&mut self, handle: Handle<T>, payload: T) -> Result<Handle<T>, T> {
599        self.spawn_at_internal(handle.index, handle.generation, payload)
600    }
601
602    fn spawn_at_internal(
603        &mut self,
604        index: u32,
605        desired_generation: u32,
606        payload: T,
607    ) -> Result<Handle<T>, T> {
608        let index_usize = usize::try_from(index).expect("index overflowed usize");
609        match self.records.get_mut(index_usize) {
610            Some(record) => match record.payload.as_ref() {
611                Some(_) => Err(payload),
612                None => {
613                    let position = self
614                        .free_stack
615                        .iter()
616                        .rposition(|i| *i == index)
617                        .expect("free_stack must contain the index of the empty record (most likely attempting to spawn at a reserved index)!");
618
619                    self.free_stack.remove(position);
620
621                    let generation = if desired_generation == INVALID_GENERATION {
622                        record.generation + 1
623                    } else {
624                        desired_generation
625                    };
626
627                    record.generation = generation;
628                    record.payload = Payload::new(payload);
629
630                    Ok(Handle::new(index, generation))
631                }
632            },
633            None => {
634                // Spawn missing records to fill gaps.
635                for i in self.records_len()..index {
636                    self.records.push(PoolRecord {
637                        ref_counter: Default::default(),
638                        generation: 1,
639                        payload: Payload::new_empty(),
640                    });
641                    self.free_stack.push(i);
642                }
643
644                let generation = if desired_generation == INVALID_GENERATION {
645                    1
646                } else {
647                    desired_generation
648                };
649
650                self.records.push(PoolRecord {
651                    ref_counter: Default::default(),
652                    generation,
653                    payload: Payload::new(payload),
654                });
655
656                Ok(Handle::new(index, generation))
657            }
658        }
659    }
660
661    #[inline]
662    #[must_use]
663    /// Construct a value with the handle it would be given.
664    /// Note: Handle is _not_ valid until function has finished executing.
665    pub fn spawn_with<F: FnOnce(Handle<T>) -> T>(&mut self, callback: F) -> Handle<T> {
666        if let Some(free_index) = self.free_stack.pop() {
667            let record = self
668                .records_get_mut(free_index)
669                .expect("free stack contained invalid index");
670
671            if record.payload.is_some() {
672                panic!(
673                    "Attempt to spawn an object at pool record with payload! Record index is {free_index}"
674                );
675            }
676
677            let generation = record.generation + 1;
678            let handle = Handle {
679                index: free_index,
680                generation,
681                type_marker: PhantomData,
682            };
683
684            let payload = callback(handle);
685
686            record.generation = generation;
687            record.payload.replace(payload);
688            handle
689        } else {
690            // No free records, create new one
691            let generation = 1;
692
693            let handle = Handle {
694                index: self.records.len() as u32,
695                generation,
696                type_marker: PhantomData,
697            };
698
699            let payload = callback(handle);
700
701            let record = PoolRecord {
702                ref_counter: Default::default(),
703                generation,
704                payload: Payload::new(payload),
705            };
706
707            self.records.push(record);
708
709            handle
710        }
711    }
712
713    #[inline]
714    /// Asynchronously construct a value with the handle it would be given.
715    /// Note: Handle is _not_ valid until function has finished executing.
716    pub async fn spawn_with_async<F, Fut>(&mut self, callback: F) -> Handle<T>
717    where
718        F: FnOnce(Handle<T>) -> Fut,
719        Fut: Future<Output = T>,
720    {
721        if let Some(free_index) = self.free_stack.pop() {
722            let record = self
723                .records_get_mut(free_index)
724                .expect("free stack contained invalid index");
725
726            if record.payload.is_some() {
727                panic!(
728                    "Attempt to spawn an object at pool record with payload! Record index is {free_index}"
729                );
730            }
731
732            let generation = record.generation + 1;
733            let handle = Handle {
734                index: free_index,
735                generation,
736                type_marker: PhantomData,
737            };
738
739            let payload = callback(handle).await;
740
741            record.generation = generation;
742            record.payload.replace(payload);
743            handle
744        } else {
745            // No free records, create new one
746            let generation = 1;
747
748            let handle = Handle {
749                index: self.records.len() as u32,
750                generation,
751                type_marker: PhantomData,
752            };
753
754            let payload = callback(handle).await;
755
756            let record = PoolRecord {
757                generation,
758                ref_counter: Default::default(),
759                payload: Payload::new(payload),
760            };
761
762            self.records.push(record);
763
764            handle
765        }
766    }
767
768    /// Generates a set of handles that could be used to spawn a set of objects. This method does not
769    /// modify the pool and the generated handles could be used together with [`Self::spawn_at_handle`]
770    /// method.
771    #[inline]
772    pub fn generate_free_handles(&self, amount: usize) -> Vec<Handle<T>> {
773        let mut free_handles = Vec::with_capacity(amount);
774        free_handles.extend(
775            self.free_stack
776                .iter()
777                .rev()
778                .take(amount)
779                .map(|i| Handle::new(*i, self.records[*i as usize].generation + 1)),
780        );
781        if free_handles.len() < amount {
782            let remainder = amount - free_handles.len();
783            free_handles.extend(
784                (self.records.len()..self.records.len() + remainder)
785                    .map(|i| Handle::new(i as u32, 1)),
786            );
787        }
788        free_handles
789    }
790
791    /// Returns a handle that may be used to spawn an object in the pool. This handle is guaranteed
792    /// to point at the vacant place in the pool. [`Self::spawn_at_handle`] call with this handle
793    /// will always succeed if called right after this method.
794    #[inline]
795    pub fn next_free_handle(&self) -> Handle<T> {
796        if let Some(index) = self.free_stack.last().cloned() {
797            let generation = self.records[index as usize].generation + 1;
798            Handle {
799                index,
800                generation,
801                type_marker: PhantomData,
802            }
803        } else {
804            Handle {
805                index: self.records.len() as u32,
806                generation: 1,
807                type_marker: PhantomData,
808            }
809        }
810    }
811
812    /// Borrows shared reference to an object by its handle.
813    ///
814    /// # Panics
815    ///
816    /// Panics if handle is out of bounds or generation of handle does not match with
817    /// generation of pool record at handle index (in other words it means that object
818    /// at handle's index is different than the object was there before).
819    #[inline]
820    #[must_use]
821    pub fn borrow(&self, handle: Handle<T>) -> &T {
822        self.try_borrow(handle).unwrap()
823    }
824
825    /// Borrows mutable reference to an object by its handle.
826    ///
827    /// # Panics
828    ///
829    /// Panics if handle is out of bounds or generation of handle does not match with
830    /// generation of pool record at handle index (in other words it means that object
831    /// at handle's index is different than the object was there before).
832    ///
833    /// # Example
834    ///
835    /// ```
836    /// use fyrox_core::pool::Pool;
837    /// let mut pool = Pool::<u32>::new();
838    /// let a = pool.spawn(1);
839    /// let a = pool.borrow_mut(a);
840    /// *a = 11;
841    /// ```
842    #[inline]
843    #[must_use]
844    pub fn borrow_mut(&mut self, handle: Handle<T>) -> &mut T {
845        self.try_borrow_mut(handle).unwrap()
846    }
847
848    /// Borrows shared reference to an object by its handle.
849    ///
850    /// Returns None if handle is out of bounds or generation of handle does not match with
851    /// generation of pool record at handle index (in other words it means that object
852    /// at handle's index is different than the object was there before).
853    #[inline]
854    pub fn try_borrow(&self, handle: Handle<T>) -> Result<&T, PoolError> {
855        self.records_get(handle.index).and_then(|r| {
856            if r.generation == handle.generation {
857                r.payload.as_ref().ok_or(PoolError::Empty(handle.into()))
858            } else {
859                Err(PoolError::InvalidGeneration(handle.generation))
860            }
861        })
862    }
863
864    /// Borrows mutable reference to an object by its handle.
865    ///
866    /// Returns None if handle is out of bounds or generation of handle does not match with
867    /// generation of pool record at handle index (in other words it means that object
868    /// at handle's index is different than the object was there before).
869    #[inline]
870    pub fn try_borrow_mut(&mut self, handle: Handle<T>) -> Result<&mut T, PoolError> {
871        self.records_get_mut(handle.index).and_then(|r| {
872            if r.generation == handle.generation {
873                r.payload.as_mut().ok_or(PoolError::Empty(handle.into()))
874            } else {
875                Err(PoolError::InvalidGeneration(handle.generation))
876            }
877        })
878    }
879
880    /// Borrows mutable references of objects at the same time. This method will succeed only
881    /// if handles are unique (not equal). Borrowing multiple mutable references at the same
882    /// time is useful in case if you need to mutate some objects at the same time.
883    ///
884    /// # Panics
885    ///
886    /// See [`borrow_mut`](Self::borrow_mut).
887    ///
888    /// # Example
889    ///
890    /// ```
891    /// use fyrox_core::pool::Pool;
892    /// let mut pool = Pool::<u32>::new();
893    /// let a = pool.spawn(1);
894    /// let b = pool.spawn(2);
895    /// let (a, b) = pool.borrow_two_mut((a, b));
896    /// *a = 11;
897    /// *b = 22;
898    /// ```
899    #[inline]
900    #[must_use = "Handle set must not be ignored"]
901    pub fn borrow_two_mut(&mut self, handles: (Handle<T>, Handle<T>)) -> (&mut T, &mut T) {
902        // Prevent giving two mutable references to same record.
903        assert_ne!(handles.0.index, handles.1.index);
904        unsafe {
905            let this = self as *mut Self;
906            ((*this).borrow_mut(handles.0), (*this).borrow_mut(handles.1))
907        }
908    }
909
910    /// Borrows mutable references of objects at the same time. This method will succeed only
911    /// if handles are unique (not equal). Borrowing multiple mutable references at the same
912    /// time is useful in case if you need to mutate some objects at the same time.
913    ///
914    /// # Panics
915    ///
916    /// See [`borrow_mut`](Self::borrow_mut).
917    ///
918    /// # Example
919    ///
920    /// ```
921    /// use fyrox_core::pool::Pool;
922    /// let mut pool = Pool::<u32>::new();
923    /// let a = pool.spawn(1);
924    /// let b = pool.spawn(2);
925    /// let c = pool.spawn(3);
926    /// let (a, b, c) = pool.borrow_three_mut((a, b, c));
927    /// *a = 11;
928    /// *b = 22;
929    /// *c = 33;
930    /// ```
931    #[inline]
932    #[must_use = "Handle set must not be ignored"]
933    pub fn borrow_three_mut(
934        &mut self,
935        handles: (Handle<T>, Handle<T>, Handle<T>),
936    ) -> (&mut T, &mut T, &mut T) {
937        // Prevent giving mutable references to same record.
938        assert_ne!(handles.0.index, handles.1.index);
939        assert_ne!(handles.0.index, handles.2.index);
940        assert_ne!(handles.1.index, handles.2.index);
941        unsafe {
942            let this = self as *mut Self;
943            (
944                (*this).borrow_mut(handles.0),
945                (*this).borrow_mut(handles.1),
946                (*this).borrow_mut(handles.2),
947            )
948        }
949    }
950
951    /// Borrows mutable references of objects at the same time. This method will succeed only
952    /// if handles are unique (not equal). Borrowing multiple mutable references at the same
953    /// time is useful in case if you need to mutate some objects at the same time.
954    ///
955    /// # Panics
956    ///
957    /// See [`borrow_mut`](Self::borrow_mut).
958    ///
959    /// # Example
960    ///
961    /// ```
962    /// use fyrox_core::pool::Pool;
963    /// let mut pool = Pool::<u32>::new();
964    /// let a = pool.spawn(1);
965    /// let b = pool.spawn(2);
966    /// let c = pool.spawn(3);
967    /// let d = pool.spawn(4);
968    /// let (a, b, c, d) = pool.borrow_four_mut((a, b, c, d));
969    /// *a = 11;
970    /// *b = 22;
971    /// *c = 33;
972    /// *d = 44;
973    /// ```
974    #[inline]
975    #[must_use = "Handle set must not be ignored"]
976    pub fn borrow_four_mut(
977        &mut self,
978        handles: (Handle<T>, Handle<T>, Handle<T>, Handle<T>),
979    ) -> (&mut T, &mut T, &mut T, &mut T) {
980        // Prevent giving mutable references to same record.
981        // This is kinda clunky since const generics are not stabilized yet.
982        assert_ne!(handles.0.index, handles.1.index);
983        assert_ne!(handles.0.index, handles.2.index);
984        assert_ne!(handles.0.index, handles.3.index);
985        assert_ne!(handles.1.index, handles.2.index);
986        assert_ne!(handles.1.index, handles.3.index);
987        assert_ne!(handles.2.index, handles.3.index);
988        unsafe {
989            let this = self as *mut Self;
990            (
991                (*this).borrow_mut(handles.0),
992                (*this).borrow_mut(handles.1),
993                (*this).borrow_mut(handles.2),
994                (*this).borrow_mut(handles.3),
995            )
996        }
997    }
998
999    /// Tries to borrow two objects when a handle to the second object stored in the first object.
1000    #[inline]
1001    pub fn try_borrow_dependant_mut<F>(
1002        &mut self,
1003        handle: Handle<T>,
1004        func: F,
1005    ) -> (Result<&mut T, PoolError>, Result<&mut T, PoolError>)
1006    where
1007        F: FnOnce(&T) -> Handle<T>,
1008    {
1009        let this = unsafe { &mut *(self as *mut Pool<T, P>) };
1010        let first = self.try_borrow_mut(handle);
1011        if let Ok(first_object) = first.as_ref() {
1012            let second_handle = func(first_object);
1013            if second_handle != handle {
1014                return (first, this.try_borrow_mut(second_handle));
1015            } else {
1016                return (first, Err(PoolError::MutablyBorrowed(second_handle.into())));
1017            }
1018        }
1019
1020        (first, Err(PoolError::UnknownDependentObject(handle.into())))
1021    }
1022
1023    /// Moves object out of the pool using the given handle. All handles to the object will become invalid.
1024    ///
1025    /// # Panics
1026    ///
1027    /// Panics if the given handle is invalid.
1028    #[inline]
1029    pub fn free(&mut self, handle: Handle<T>) -> T {
1030        self.try_free(handle).unwrap()
1031    }
1032
1033    /// Tries to move object out of the pool using the given handle. Returns None if given handle
1034    /// is invalid. After object is moved out if the pool, all handles to the object will become
1035    /// invalid.
1036    #[inline]
1037    pub fn try_free(&mut self, handle: Handle<T>) -> Result<T, PoolError> {
1038        let index = usize::try_from(handle.index).expect("index overflowed usize");
1039        self.records
1040            .get_mut(index)
1041            .ok_or(PoolError::InvalidIndex(handle.index))
1042            .and_then(|record| {
1043                if record.generation == handle.generation {
1044                    if let Some(payload) = record.payload.take() {
1045                        self.free_stack.push(handle.index);
1046                        Ok(payload)
1047                    } else {
1048                        Err(PoolError::Empty(handle.into()))
1049                    }
1050                } else {
1051                    Err(PoolError::InvalidGeneration(handle.generation))
1052                }
1053            })
1054    }
1055
1056    /// Moves an object out of the pool using the given handle with a promise that the object will be returned back.
1057    /// Returns pair (ticket, value). The ticket must be used to put the value back!
1058    ///
1059    /// # Motivation
1060    ///
1061    /// This method is useful when you need to take temporary ownership of an object, do something
1062    /// with it and then put it back while preserving all handles to it and being able to put new objects into
1063    /// the pool without overriding the payload at its handle.
1064    ///
1065    /// # Notes
1066    ///
1067    /// All handles to the object will be temporarily invalid until the object is returned to the pool! The pool record will
1068    /// be reserved for a further [`put_back`] call, which means if you lose the ticket you will have an empty
1069    /// "unusable" pool record forever.
1070    ///
1071    /// # Panics
1072    ///
1073    /// Panics if the given handle is invalid.
1074    ///
1075    /// [`put_back`]: Pool::put_back
1076    #[inline]
1077    pub fn take_reserve(&mut self, handle: Handle<T>) -> (Ticket<T>, T) {
1078        self.try_take_reserve(handle).unwrap()
1079    }
1080
1081    /// Does the same as [`take_reserve`] but returns an option, instead of panicking.
1082    ///
1083    /// [`take_reserve`]: Pool::take_reserve
1084    #[inline]
1085    pub fn try_take_reserve(&mut self, handle: Handle<T>) -> Result<(Ticket<T>, T), PoolError> {
1086        let record = self.records_get_mut(handle.index)?;
1087        if record.generation == handle.generation {
1088            if let Some(payload) = record.payload.take() {
1089                let ticket = Ticket {
1090                    index: handle.index,
1091                    marker: PhantomData,
1092                };
1093                Ok((ticket, payload))
1094            } else {
1095                Err(PoolError::Empty(handle.into()))
1096            }
1097        } else {
1098            Err(PoolError::InvalidGeneration(handle.generation))
1099        }
1100    }
1101
1102    /// Returns the value back into the pool using the given ticket. See [`take_reserve`] for more
1103    /// information.
1104    ///
1105    /// [`take_reserve`]: Pool::take_reserve
1106    #[inline]
1107    pub fn put_back(&mut self, ticket: Ticket<T>, value: T) -> Handle<T> {
1108        let record = self
1109            .records_get_mut(ticket.index)
1110            .expect("Ticket index was invalid");
1111        let old = record.payload.replace(value);
1112        assert!(old.is_none());
1113        let handle = Handle::new(ticket.index, record.generation);
1114        std::mem::forget(ticket);
1115        handle
1116    }
1117
1118    /// Forgets that value at ticket was reserved and makes it usable again.
1119    /// Useful when you don't need to put value back by ticket, but just make
1120    /// pool record usable again.
1121    #[inline]
1122    pub fn forget_ticket(&mut self, ticket: Ticket<T>) {
1123        self.free_stack.push(ticket.index);
1124        std::mem::forget(ticket);
1125    }
1126
1127    /// Returns total capacity of pool. Capacity has nothing about real amount of objects in pool!
1128    #[inline]
1129    #[must_use]
1130    pub fn get_capacity(&self) -> u32 {
1131        u32::try_from(self.records.len()).expect("records.len() overflowed u32")
1132    }
1133
1134    /// Destroys all objects in pool. All handles to objects will become invalid.
1135    ///
1136    /// # Remarks
1137    ///
1138    /// Use this method cautiously if objects in pool have cross "references" (handles)
1139    /// to each other. This method will make all produced handles invalid and any further
1140    /// calls for [`borrow`](Self::borrow) or [`borrow_mut`](Self::borrow_mut) will raise panic.
1141    #[inline]
1142    pub fn clear(&mut self) {
1143        self.records.clear();
1144        self.free_stack.clear();
1145    }
1146
1147    #[inline]
1148    pub fn at_mut(&mut self, n: u32) -> Result<&mut T, PoolError> {
1149        self.records_get_mut(n).and_then(|rec| {
1150            rec.payload
1151                .as_mut()
1152                .ok_or(PoolError::Empty(ErasedHandle::new(n, 0)))
1153        })
1154    }
1155
1156    #[inline]
1157    pub fn at(&self, n: u32) -> Result<&T, PoolError> {
1158        self.records_get(n).and_then(|rec| {
1159            rec.payload
1160                .get()
1161                .as_ref()
1162                .ok_or(PoolError::Empty(ErasedHandle::new(n, 0)))
1163        })
1164    }
1165
1166    #[inline]
1167    #[must_use]
1168    pub fn handle_from_index(&self, n: u32) -> Handle<T> {
1169        if let Ok(record) = self.records_get(n) {
1170            if record.generation != INVALID_GENERATION {
1171                return Handle::new(n, record.generation);
1172            }
1173        }
1174        Handle::NONE
1175    }
1176
1177    /// Returns the exact number of "alive" objects in the pool.
1178    ///
1179    /// Records that have been reserved (e.g. by [`take_reserve`]) are *not* counted.
1180    ///
1181    /// It iterates through the entire pool to count the live objects so the complexity is `O(n)`.
1182    ///
1183    /// See also [`total_count`].
1184    ///
1185    /// # Example
1186    ///
1187    /// ```
1188    /// use fyrox_core::pool::Pool;
1189    /// let mut pool = Pool::<u32>::new();
1190    /// pool.spawn(123);
1191    /// pool.spawn(321);
1192    /// assert_eq!(pool.alive_count(), 2);
1193    /// ```
1194    ///
1195    /// [`take_reserve`]: Pool::take_reserve
1196    /// [`total_count`]: Pool::total_count
1197    #[inline]
1198    #[must_use]
1199    pub fn alive_count(&self) -> u32 {
1200        let cnt = self.iter().count();
1201        u32::try_from(cnt).expect("alive_count overflowed u32")
1202    }
1203
1204    /// Returns the number of allocated objects in the pool.
1205    ///
1206    /// It also counts records that have been reserved (e.g. by [`take_reserve`]).
1207    ///
1208    /// This method is `O(1)`.
1209    ///
1210    /// See also [`alive_count`].
1211    ///
1212    /// [`take_reserve`]: Pool::take_reserve
1213    /// [`alive_count`]: Pool::alive_count
1214    #[inline]
1215    pub fn total_count(&self) -> u32 {
1216        let free = u32::try_from(self.free_stack.len()).expect("free stack length overflowed u32");
1217        self.records_len() - free
1218    }
1219
1220    #[inline]
1221    pub fn replace(&mut self, handle: Handle<T>, payload: T) -> Option<T> {
1222        let index_usize = usize::try_from(handle.index).expect("index overflowed usize");
1223        if let Some(record) = self.records.get_mut(index_usize) {
1224            if record.generation == handle.generation {
1225                self.free_stack.retain(|i| *i != handle.index);
1226
1227                record.payload.replace(payload)
1228            } else {
1229                panic!("Attempt to replace object in pool using dangling handle! Handle is {:?}, but pool record has {} generation", handle, record.generation);
1230            }
1231        } else {
1232            None
1233        }
1234    }
1235
1236    /// Returns a reference to the first element in the pool (if any).
1237    pub fn first_ref(&self) -> Option<&T> {
1238        self.iter().next()
1239    }
1240
1241    /// Returns a reference to the first element in the pool (if any).
1242    pub fn first_mut(&mut self) -> Option<&mut T> {
1243        self.iter_mut().next()
1244    }
1245
1246    /// Checks if given handle "points" to some object.
1247    ///
1248    /// # Example
1249    ///
1250    /// ```
1251    /// use fyrox_core::pool::Pool;
1252    /// let mut pool = Pool::<u32>::new();
1253    /// let handle = pool.spawn(123);
1254    /// assert_eq!(pool.is_valid_handle(handle), true)
1255    /// ```
1256    #[inline]
1257    pub fn is_valid_handle(&self, handle: Handle<impl ObjectOrVariant<T>>) -> bool {
1258        if let Ok(record) = self.records_get(handle.index) {
1259            record.payload.is_some() && record.generation == handle.generation
1260        } else {
1261            false
1262        }
1263    }
1264
1265    /// Creates new pool iterator that iterates over filled records in pool.
1266    ///
1267    /// # Example
1268    ///
1269    /// ```
1270    /// use fyrox_core::pool::Pool;
1271    /// let mut pool = Pool::<u32>::new();
1272    /// pool.spawn(123);
1273    /// pool.spawn(321);
1274    /// let mut iter = pool.iter();
1275    /// assert_eq!(*iter.next().unwrap(), 123);
1276    /// assert_eq!(*iter.next().unwrap(), 321);
1277    /// ```
1278    #[must_use]
1279    #[inline]
1280    pub fn iter(&self) -> PoolIterator<T, P> {
1281        unsafe {
1282            PoolIterator {
1283                ptr: self.records.as_ptr(),
1284                end: self.records.as_ptr().add(self.records.len()),
1285                marker: PhantomData,
1286            }
1287        }
1288    }
1289
1290    /// Creates new pair iterator that iterates over filled records using pair (handle, payload)
1291    /// Can be useful when there is a need to iterate over pool records and know a handle of
1292    /// that record.
1293    #[inline]
1294    pub fn pair_iter(&self) -> PoolPairIterator<T, P> {
1295        PoolPairIterator {
1296            pool: self,
1297            current: 0,
1298        }
1299    }
1300
1301    /// Creates new pool iterator that iterates over filled records in pool allowing
1302    /// to modify record payload.
1303    ///
1304    /// # Example
1305    ///
1306    /// ```
1307    /// use fyrox_core::pool::Pool;
1308    /// let mut pool = Pool::<u32>::new();
1309    /// pool.spawn(123);
1310    /// pool.spawn(321);
1311    /// let mut iter = pool.iter_mut();
1312    /// assert_eq!(*iter.next().unwrap(), 123);
1313    /// assert_eq!(*iter.next().unwrap(), 321);
1314    /// ```
1315    #[must_use]
1316    #[inline]
1317    pub fn iter_mut(&mut self) -> PoolIteratorMut<T, P> {
1318        unsafe {
1319            PoolIteratorMut {
1320                ptr: self.records.as_mut_ptr(),
1321                end: self.records.as_mut_ptr().add(self.records.len()),
1322                marker: PhantomData,
1323            }
1324        }
1325    }
1326
1327    /// Creates new pair iterator that iterates over filled records using pair (handle, payload)
1328    /// Can be useful when there is a need to iterate over pool records and know a handle of
1329    /// that record.
1330    #[inline]
1331    pub fn pair_iter_mut(&mut self) -> PoolPairIteratorMut<T, P> {
1332        unsafe {
1333            PoolPairIteratorMut {
1334                current: 0,
1335                ptr: self.records.as_mut_ptr(),
1336                end: self.records.as_mut_ptr().add(self.records.len()),
1337                marker: PhantomData,
1338            }
1339        }
1340    }
1341
1342    /// Retains pool records selected by `pred`. Useful when you need to remove all pool records
1343    /// by some criteria.
1344    #[inline]
1345    pub fn retain<F>(&mut self, mut pred: F)
1346    where
1347        F: FnMut(&T) -> bool,
1348    {
1349        for (i, record) in self.records.iter_mut().enumerate() {
1350            if record.generation == INVALID_GENERATION {
1351                continue;
1352            }
1353
1354            let retain = if let Some(payload) = record.payload.as_ref() {
1355                pred(payload)
1356            } else {
1357                continue;
1358            };
1359
1360            if !retain {
1361                self.free_stack.push(i as u32);
1362                record.payload.take(); // and Drop
1363            }
1364        }
1365    }
1366
1367    /// Begins multi-borrow that allows you to borrow as many (`N`) **unique** references to the pool
1368    /// elements as you need. See [`MultiBorrowContext::try_get`] for more info.
1369    #[inline]
1370    pub fn begin_multi_borrow(&mut self) -> MultiBorrowContext<T, P> {
1371        MultiBorrowContext::new(self)
1372    }
1373
1374    /// Removes all elements from the pool.
1375    #[inline]
1376    pub fn drain(&mut self) -> impl Iterator<Item = T> + '_ {
1377        self.free_stack.clear();
1378        self.records.drain(..).filter_map(|mut r| r.payload.take())
1379    }
1380
1381    fn end(&self) -> *const PoolRecord<T, P> {
1382        unsafe { self.records.as_ptr().add(self.records.len()) }
1383    }
1384
1385    fn begin(&self) -> *const PoolRecord<T, P> {
1386        self.records.as_ptr()
1387    }
1388
1389    #[inline]
1390    pub fn handle_of(&self, ptr: &T) -> Handle<T> {
1391        let begin = self.begin() as usize;
1392        let end = self.end() as usize;
1393        let val = ptr as *const T as usize;
1394        if val >= begin && val < end {
1395            let record_size = std::mem::size_of::<PoolRecord<T>>();
1396            let record_location = (val - offset_of!(PoolRecord<T>, payload)) - begin;
1397            if record_location.is_multiple_of(record_size) {
1398                let index = record_location / record_size;
1399                let index = u32::try_from(index).expect("Index overflowed u32");
1400                return self.handle_from_index(index);
1401            }
1402        }
1403        Handle::NONE
1404    }
1405}
1406
1407impl<T, P> Pool<T, P>
1408where
1409    T: ComponentProvider,
1410    P: PayloadContainer<Element = T> + 'static,
1411{
1412    /// Tries to mutably borrow an object and fetch its component of specified type.
1413    #[inline]
1414    pub fn try_get_component_of_type<C>(&self, handle: Handle<T>) -> Result<&C, PoolError>
1415    where
1416        C: 'static,
1417    {
1418        self.try_borrow(handle)
1419            .and_then(|n| {
1420                n.query_component_ref(TypeId::of::<C>())
1421                    .ok_or(PoolError::NoSuchComponent(handle.into()))
1422            })
1423            .and_then(|c| {
1424                c.downcast_ref()
1425                    .ok_or(PoolError::InvalidType(handle.into()))
1426            })
1427    }
1428
1429    /// Tries to mutably borrow an object and fetch its component of specified type.
1430    #[inline]
1431    pub fn try_get_component_of_type_mut<C>(
1432        &mut self,
1433        handle: Handle<T>,
1434    ) -> Result<&mut C, PoolError>
1435    where
1436        C: 'static,
1437    {
1438        self.try_borrow_mut(handle)
1439            .and_then(|n| {
1440                n.query_component_mut(TypeId::of::<C>())
1441                    .ok_or(PoolError::NoSuchComponent(handle.into()))
1442            })
1443            .and_then(|c| {
1444                c.downcast_mut()
1445                    .ok_or(PoolError::InvalidType(handle.into()))
1446            })
1447    }
1448}
1449
1450impl<T> FromIterator<T> for Pool<T>
1451where
1452    T: 'static,
1453{
1454    #[inline]
1455    fn from_iter<C: IntoIterator<Item = T>>(iter: C) -> Self {
1456        let iter = iter.into_iter();
1457        let (lower_bound, upper_bound) = iter.size_hint();
1458        let lower_bound = u32::try_from(lower_bound).expect("lower_bound overflowed u32");
1459        let upper_bound =
1460            upper_bound.map(|b| u32::try_from(b).expect("upper_bound overflowed u32"));
1461        let mut pool = Self::with_capacity(upper_bound.unwrap_or(lower_bound));
1462        for v in iter {
1463            let _ = pool.spawn(v);
1464        }
1465        pool
1466    }
1467}
1468
1469impl<T, U, Container> Index<Handle<U>> for Pool<T, Container>
1470where
1471    T: 'static,
1472    U: ObjectOrVariant<T>,
1473    Container: PayloadContainer<Element = T> + 'static,
1474{
1475    type Output = U;
1476    #[inline]
1477    fn index(&self, index: Handle<U>) -> &Self::Output {
1478        self.try_get(index).expect("The handle must be valid!")
1479    }
1480}
1481
1482impl<T, U, Container> IndexMut<Handle<U>> for Pool<T, Container>
1483where
1484    T: 'static,
1485    U: ObjectOrVariant<T>,
1486    Container: PayloadContainer<Element = T> + 'static,
1487{
1488    #[inline]
1489    fn index_mut(&mut self, index: Handle<U>) -> &mut Self::Output {
1490        self.try_get_mut(index).expect("The handle must be valid!")
1491    }
1492}
1493
1494impl<'a, T, P> IntoIterator for &'a Pool<T, P>
1495where
1496    P: PayloadContainer<Element = T> + 'static,
1497{
1498    type Item = &'a T;
1499    type IntoIter = PoolIterator<'a, T, P>;
1500
1501    #[inline]
1502    fn into_iter(self) -> Self::IntoIter {
1503        self.iter()
1504    }
1505}
1506
1507impl<'a, T, P> IntoIterator for &'a mut Pool<T, P>
1508where
1509    P: PayloadContainer<Element = T> + 'static,
1510{
1511    type Item = &'a mut T;
1512    type IntoIter = PoolIteratorMut<'a, T, P>;
1513
1514    #[inline]
1515    fn into_iter(self) -> Self::IntoIter {
1516        self.iter_mut()
1517    }
1518}
1519
1520pub struct PoolIterator<'a, T, P>
1521where
1522    P: PayloadContainer<Element = T>,
1523{
1524    ptr: *const PoolRecord<T, P>,
1525    end: *const PoolRecord<T, P>,
1526    marker: PhantomData<&'a T>,
1527}
1528
1529impl<'a, T, P> Iterator for PoolIterator<'a, T, P>
1530where
1531    P: PayloadContainer<Element = T> + 'static,
1532{
1533    type Item = &'a T;
1534
1535    #[inline]
1536    fn next(&mut self) -> Option<Self::Item> {
1537        unsafe {
1538            while self.ptr != self.end {
1539                let current = &*self.ptr;
1540                if let Some(payload) = current.payload.as_ref() {
1541                    self.ptr = self.ptr.offset(1);
1542                    return Some(payload);
1543                }
1544                self.ptr = self.ptr.offset(1);
1545            }
1546
1547            None
1548        }
1549    }
1550}
1551
1552pub struct PoolPairIterator<'a, T, P: PayloadContainer<Element = T>> {
1553    pool: &'a Pool<T, P>,
1554    current: usize,
1555}
1556
1557impl<'a, T, P> Iterator for PoolPairIterator<'a, T, P>
1558where
1559    P: PayloadContainer<Element = T>,
1560{
1561    type Item = (Handle<T>, &'a T);
1562
1563    #[inline]
1564    fn next(&mut self) -> Option<Self::Item> {
1565        loop {
1566            match self.pool.records.get(self.current) {
1567                Some(record) => {
1568                    if let Some(payload) = record.payload.as_ref() {
1569                        let handle = Handle::new(self.current as u32, record.generation);
1570                        self.current += 1;
1571                        return Some((handle, payload));
1572                    }
1573                    self.current += 1;
1574                }
1575                None => return None,
1576            }
1577        }
1578    }
1579}
1580
1581pub struct PoolIteratorMut<'a, T, P>
1582where
1583    P: PayloadContainer<Element = T>,
1584{
1585    ptr: *mut PoolRecord<T, P>,
1586    end: *mut PoolRecord<T, P>,
1587    marker: PhantomData<&'a mut T>,
1588}
1589
1590impl<'a, T, P> Iterator for PoolIteratorMut<'a, T, P>
1591where
1592    P: PayloadContainer<Element = T> + 'static,
1593{
1594    type Item = &'a mut T;
1595
1596    #[inline]
1597    fn next(&mut self) -> Option<Self::Item> {
1598        unsafe {
1599            while self.ptr != self.end {
1600                let current = &mut *self.ptr;
1601                if let Some(payload) = current.payload.as_mut() {
1602                    self.ptr = self.ptr.offset(1);
1603                    return Some(payload);
1604                }
1605                self.ptr = self.ptr.offset(1);
1606            }
1607
1608            None
1609        }
1610    }
1611}
1612
1613pub struct PoolPairIteratorMut<'a, T, P>
1614where
1615    P: PayloadContainer<Element = T>,
1616{
1617    ptr: *mut PoolRecord<T, P>,
1618    end: *mut PoolRecord<T, P>,
1619    marker: PhantomData<&'a mut T>,
1620    current: usize,
1621}
1622
1623impl<'a, T, P> Iterator for PoolPairIteratorMut<'a, T, P>
1624where
1625    P: PayloadContainer<Element = T> + 'static,
1626{
1627    type Item = (Handle<T>, &'a mut T);
1628
1629    #[inline]
1630    fn next(&mut self) -> Option<Self::Item> {
1631        unsafe {
1632            while self.ptr != self.end {
1633                let current = &mut *self.ptr;
1634                if let Some(payload) = current.payload.as_mut() {
1635                    let handle = Handle::new(self.current as u32, current.generation);
1636                    self.ptr = self.ptr.offset(1);
1637                    self.current += 1;
1638                    return Some((handle, payload));
1639                }
1640                self.ptr = self.ptr.offset(1);
1641                self.current += 1;
1642            }
1643
1644            None
1645        }
1646    }
1647}
1648
1649#[cfg(test)]
1650mod test {
1651    use crate::pool::PoolError;
1652    use crate::{
1653        pool::{AtomicHandle, Handle, Pool, PoolRecord, INVALID_GENERATION},
1654        visitor::{Visit, Visitor},
1655    };
1656
1657    #[test]
1658    fn pool_sanity_tests() {
1659        let mut pool: Pool<String> = Pool::new();
1660        let foobar_handle = pool.spawn(String::from("Foobar"));
1661        assert_eq!(foobar_handle.index, 0);
1662        assert_ne!(foobar_handle.generation, INVALID_GENERATION);
1663        let foobar_handle_copy = foobar_handle;
1664        assert_eq!(foobar_handle.index, foobar_handle_copy.index);
1665        assert_eq!(foobar_handle.generation, foobar_handle_copy.generation);
1666        let baz_handle = pool.spawn(String::from("Baz"));
1667        assert_eq!(pool.borrow(foobar_handle), "Foobar");
1668        assert_eq!(pool.borrow(baz_handle), "Baz");
1669        pool.free(foobar_handle);
1670        assert!(!pool.is_valid_handle(foobar_handle_copy));
1671        assert!(pool.is_valid_handle(baz_handle));
1672        let at_foobar_index = pool.spawn(String::from("AtFoobarIndex"));
1673        assert_eq!(at_foobar_index.index, 0);
1674        assert_ne!(at_foobar_index.generation, INVALID_GENERATION);
1675        assert_eq!(pool.borrow(at_foobar_index), "AtFoobarIndex");
1676        let bar_handle = pool.spawn_with(|_handle| String::from("Bar"));
1677        assert_ne!(bar_handle.index, 0);
1678        assert_ne!(bar_handle.generation, INVALID_GENERATION);
1679        assert_eq!(pool.borrow(bar_handle), "Bar");
1680    }
1681
1682    #[test]
1683    fn pool_iterator_mut_test() {
1684        let mut pool: Pool<String> = Pool::new();
1685        let foobar = pool.spawn("Foobar".to_string());
1686        let d = pool.spawn("Foo".to_string());
1687        pool.free(d);
1688        let baz = pool.spawn("Baz".to_string());
1689        for s in pool.iter() {
1690            println!("{s}");
1691        }
1692        for s in pool.iter_mut() {
1693            println!("{s}");
1694        }
1695        for s in &pool {
1696            println!("{s}");
1697        }
1698        for s in &mut pool {
1699            println!("{s}");
1700        }
1701        pool.free(foobar);
1702        pool.free(baz);
1703    }
1704
1705    #[test]
1706    fn handle_of() {
1707        #[allow(dead_code)]
1708        struct Value {
1709            data: String,
1710        }
1711
1712        let mut pool = Pool::<Value>::new();
1713        let foobar = pool.spawn(Value {
1714            data: "Foobar".to_string(),
1715        });
1716        let bar = pool.spawn(Value {
1717            data: "Bar".to_string(),
1718        });
1719        let baz = pool.spawn(Value {
1720            data: "Baz".to_string(),
1721        });
1722        assert_eq!(pool.handle_of(pool.borrow(foobar)), foobar);
1723        assert_eq!(pool.handle_of(pool.borrow(bar)), bar);
1724        assert_eq!(pool.handle_of(pool.borrow(baz)), baz);
1725    }
1726
1727    #[derive(Debug, Eq, PartialEq)]
1728    struct Payload;
1729
1730    #[test]
1731    fn pool_test_spawn_at() {
1732        let mut pool = Pool::<Payload>::new();
1733
1734        assert_eq!(pool.spawn_at(2, Payload), Ok(Handle::new(2, 1)));
1735        assert_eq!(pool.spawn_at(2, Payload), Err(Payload));
1736        assert_eq!(pool.records[0].payload.as_ref(), None);
1737        assert_eq!(pool.records[1].payload.as_ref(), None);
1738        assert_ne!(pool.records[2].payload.as_ref(), None);
1739
1740        assert_eq!(pool.spawn_at(2, Payload), Err(Payload));
1741
1742        pool.free(Handle::new(2, 1));
1743
1744        assert_eq!(pool.spawn_at(2, Payload), Ok(Handle::new(2, 2)));
1745
1746        assert_eq!(pool.spawn(Payload), Handle::<Payload>::new(1, 2));
1747        assert_eq!(pool.spawn(Payload), Handle::<Payload>::new(0, 2));
1748    }
1749
1750    #[test]
1751    fn pool_test_try_free() {
1752        let mut pool = Pool::<Payload>::new();
1753
1754        assert_eq!(
1755            pool.try_free(Handle::NONE),
1756            Err(PoolError::InvalidIndex(Handle::<Payload>::NONE.index))
1757        );
1758        assert_eq!(pool.free_stack.len(), 0);
1759
1760        let handle = pool.spawn(Payload);
1761        assert_eq!(pool.try_free(handle), Ok(Payload));
1762        assert_eq!(pool.free_stack.len(), 1);
1763        assert_eq!(pool.try_free(handle), Err(PoolError::Empty(handle.into())));
1764        assert_eq!(pool.free_stack.len(), 1);
1765    }
1766
1767    #[test]
1768    fn visit_for_pool_record() {
1769        let mut p = PoolRecord::<u32>::default();
1770        let mut visitor = Visitor::default();
1771
1772        assert!(p.visit("name", &mut visitor).is_ok());
1773    }
1774
1775    #[test]
1776    fn visit_for_pool() {
1777        let mut p = Pool::<u32>::default();
1778        let mut visitor = Visitor::default();
1779
1780        assert!(p.visit("name", &mut visitor).is_ok());
1781    }
1782
1783    #[test]
1784    fn default_for_pool() {
1785        assert_eq!(Pool::default(), Pool::<u32>::new());
1786    }
1787
1788    #[test]
1789    fn pool_with_capacity() {
1790        let p = Pool::<u32>::with_capacity(1);
1791        assert_eq!(p.records, Vec::with_capacity(1));
1792        assert_eq!(p.free_stack, Vec::new())
1793    }
1794
1795    #[test]
1796    fn pool_try_borrow() {
1797        let mut pool = Pool::<Payload>::new();
1798        let a = pool.spawn(Payload);
1799        let b = Handle::<Payload>::default();
1800
1801        assert_eq!(pool.try_borrow(a), Ok(&Payload));
1802        assert_eq!(
1803            pool.try_borrow(b),
1804            Err(PoolError::InvalidGeneration(b.generation))
1805        );
1806    }
1807
1808    #[test]
1809    fn pool_borrow_two_mut() {
1810        let mut pool = Pool::<u32>::new();
1811        let a = pool.spawn(1);
1812        let b = pool.spawn(2);
1813        let (a, b) = pool.borrow_two_mut((a, b));
1814
1815        assert_eq!(a, &mut 1);
1816        assert_eq!(b, &mut 2);
1817    }
1818
1819    #[test]
1820    fn pool_borrow_three_mut() {
1821        let mut pool = Pool::<u32>::new();
1822        let a = pool.spawn(1);
1823        let b = pool.spawn(2);
1824        let c = pool.spawn(3);
1825        let (a, b, c) = pool.borrow_three_mut((a, b, c));
1826
1827        assert_eq!(a, &mut 1);
1828        assert_eq!(b, &mut 2);
1829        assert_eq!(c, &mut 3);
1830    }
1831
1832    #[test]
1833    fn pool_borrow_four_mut() {
1834        let mut pool = Pool::<u32>::new();
1835        let a = pool.spawn(1);
1836        let b = pool.spawn(2);
1837        let c = pool.spawn(3);
1838        let d = pool.spawn(4);
1839        let (a, b, c, d) = pool.borrow_four_mut((a, b, c, d));
1840
1841        assert_eq!(a, &mut 1);
1842        assert_eq!(b, &mut 2);
1843        assert_eq!(c, &mut 3);
1844        assert_eq!(d, &mut 4);
1845    }
1846
1847    #[test]
1848    fn pool_try_borrow_dependant_mut() {
1849        let mut pool = Pool::<u32>::new();
1850        let a = pool.spawn(42);
1851        let b = pool.spawn(5);
1852
1853        assert_eq!(
1854            pool.try_borrow_dependant_mut(a, |_| b),
1855            (Ok(&mut 42), Ok(&mut 5))
1856        );
1857
1858        assert_eq!(
1859            pool.try_borrow_dependant_mut(a, |_| a),
1860            (Ok(&mut 42), Err(PoolError::MutablyBorrowed(a.into())))
1861        );
1862    }
1863
1864    #[test]
1865    fn pool_try_take_reserve() {
1866        let mut pool = Pool::<u32>::new();
1867
1868        let a = Handle::<u32>::default();
1869        assert!(pool.try_take_reserve(a).is_err());
1870
1871        let b = pool.spawn(42);
1872
1873        let (ticket, payload) = pool.try_take_reserve(b).unwrap();
1874        assert_eq!(ticket.index, 0);
1875        assert_eq!(payload, 42);
1876
1877        assert!(pool.try_take_reserve(a).is_err());
1878        assert!(pool.try_take_reserve(b).is_err());
1879
1880        pool.forget_ticket(ticket);
1881    }
1882
1883    #[test]
1884    fn pool_put_back() {
1885        let mut pool = Pool::<u32>::new();
1886        let a = pool.spawn(42);
1887        let (ticket, value) = pool.take_reserve(a);
1888        let b = pool.put_back(ticket, value);
1889
1890        assert_eq!(a, b);
1891    }
1892
1893    #[test]
1894    fn pool_forget_ticket() {
1895        let mut pool = Pool::<u32>::new();
1896        let a = pool.spawn(42);
1897        let (ticket, _) = pool.take_reserve(a);
1898
1899        pool.forget_ticket(ticket);
1900
1901        let b = pool.spawn(42);
1902
1903        assert_eq!(a.index, b.index);
1904        assert_ne!(a.generation, b.generation);
1905    }
1906
1907    #[test]
1908    fn pool_get_capacity() {
1909        let mut pool = Pool::<u32>::new();
1910        let _ = pool.spawn(42);
1911        let _ = pool.spawn(5);
1912
1913        assert_eq!(pool.get_capacity(), 2);
1914    }
1915
1916    #[test]
1917    fn pool_clear() {
1918        let mut pool = Pool::<u32>::new();
1919        let _ = pool.spawn(42);
1920
1921        assert!(!pool.records.is_empty());
1922
1923        pool.clear();
1924
1925        assert!(pool.records.is_empty());
1926        assert!(pool.free_stack.is_empty());
1927    }
1928
1929    #[test]
1930    fn pool_at_mut() {
1931        let mut pool = Pool::<u32>::new();
1932        let _ = pool.spawn(42);
1933
1934        assert_eq!(pool.at_mut(0), Ok(&mut 42));
1935        assert_eq!(pool.at_mut(1), Err(PoolError::InvalidIndex(1)));
1936    }
1937
1938    #[test]
1939    fn pool_at() {
1940        let mut pool = Pool::<u32>::new();
1941        let _ = pool.spawn(42);
1942
1943        assert_eq!(pool.at(0), Ok(&42));
1944        assert_eq!(pool.at(1), Err(PoolError::InvalidIndex(1)));
1945    }
1946
1947    #[test]
1948    fn pool_handle_from_index() {
1949        let mut pool = Pool::<u32>::new();
1950        let a = pool.spawn(42);
1951
1952        assert_eq!(pool.handle_from_index(0), a);
1953        assert_eq!(pool.handle_from_index(1), Handle::<u32>::NONE);
1954    }
1955
1956    #[test]
1957    fn pool_alive_count() {
1958        let mut pool = Pool::<u32>::new();
1959        let a = pool.spawn(42);
1960        let _ = pool.spawn(5);
1961        let (ticket, _) = pool.take_reserve(a);
1962        pool.forget_ticket(ticket);
1963
1964        assert_eq!(pool.alive_count(), 1);
1965    }
1966
1967    #[test]
1968    fn pool_total_count() {
1969        let mut pool = Pool::<u32>::new();
1970        let a = pool.spawn(42);
1971        let _ = pool.spawn(5);
1972        let (ticket, _) = pool.take_reserve(a);
1973
1974        assert_eq!(pool.total_count(), 2);
1975
1976        pool.forget_ticket(ticket);
1977    }
1978
1979    #[test]
1980    fn pool_replace() {
1981        let mut pool = Pool::<u32>::new();
1982        let a = pool.spawn(42);
1983        let b = Handle::<u32>::new(1, 1);
1984
1985        assert_eq!(pool.replace(a, 5), Some(42));
1986        assert_eq!(pool.replace(b, 5), None);
1987    }
1988
1989    #[test]
1990    fn pool_pair_iter() {
1991        let pool = Pool::<u32>::new();
1992
1993        let iter = pool.pair_iter();
1994
1995        assert_eq!(iter.pool, &pool);
1996        assert_eq!(iter.current, 0);
1997    }
1998
1999    #[test]
2000    fn pool_pair_iter_mut() {
2001        let mut pool = Pool::<u32>::new();
2002        let _ = pool.spawn(42);
2003
2004        let iter = pool.pair_iter_mut();
2005
2006        assert_eq!(iter.current, 0);
2007        assert_eq!(iter.ptr, pool.records.as_mut_ptr());
2008    }
2009
2010    #[test]
2011    fn index_for_pool() {
2012        let mut pool = Pool::<u32>::new();
2013        let a = pool.spawn(42);
2014        let b = pool.spawn(5);
2015
2016        assert_eq!(pool[a], 42);
2017        assert_eq!(pool[b], 5);
2018    }
2019
2020    #[test]
2021    fn index_mut_for_pool() {
2022        let mut pool = Pool::<u32>::new();
2023        let a = pool.spawn(42);
2024        let b = pool.spawn(5);
2025
2026        pool[a] = 15;
2027
2028        assert_eq!(pool[a], 15);
2029        assert_eq!(pool[b], 5);
2030    }
2031
2032    #[test]
2033    fn test_atomic_handle() {
2034        let handle = AtomicHandle::new(123, 321);
2035        assert!(handle.is_some());
2036        assert_eq!(handle.index(), 123);
2037        assert_eq!(handle.generation(), 321);
2038
2039        let handle = AtomicHandle::default();
2040        assert!(handle.is_none());
2041    }
2042
2043    #[test]
2044    fn test_generate_free_handles() {
2045        let mut pool = Pool::<u32>::new();
2046
2047        let _ = pool.spawn(42);
2048        let b = pool.spawn(5);
2049        let _ = pool.spawn(228);
2050
2051        pool.free(b);
2052
2053        let h0 = Handle::<u32>::new(1, 2);
2054        let h1 = Handle::<u32>::new(3, 1);
2055        let h2 = Handle::<u32>::new(4, 1);
2056        let h3 = Handle::<u32>::new(5, 1);
2057        let h4 = Handle::<u32>::new(6, 1);
2058
2059        let free_handles = pool.generate_free_handles(5);
2060        assert_eq!(free_handles, [h0, h1, h2, h3, h4]);
2061
2062        // Spawn something on the generated handles.
2063        for (i, handle) in free_handles.into_iter().enumerate() {
2064            let instance_handle = pool.spawn_at_handle(handle, i as u32);
2065            assert_eq!(instance_handle, Ok(handle));
2066        }
2067
2068        assert_eq!(pool[h0], 0);
2069        assert_eq!(pool[h1], 1);
2070        assert_eq!(pool[h2], 2);
2071        assert_eq!(pool[h3], 3);
2072        assert_eq!(pool[h4], 4);
2073    }
2074
2075    #[test]
2076    fn test_spawn_consistent_with_generate_free_handles() {
2077        let mut pool = Pool::<u32>::new();
2078
2079        let _ = pool.spawn(42);
2080        let b0 = pool.spawn(5);
2081        let b1 = pool.spawn(6);
2082        let b2 = pool.spawn(7);
2083        let _ = pool.spawn(228);
2084
2085        pool.free(b0);
2086        pool.free(b1);
2087        pool.free(b2);
2088
2089        let free_handles = pool.generate_free_handles(5);
2090
2091        let mut spawn_handles = Vec::new();
2092        for i in 0..5 {
2093            spawn_handles.push(pool.spawn(i));
2094        }
2095
2096        assert_eq!(free_handles, spawn_handles);
2097    }
2098}
fyrox_core/pool/mod.rs

fyrox_core/pool/
mod.rs
