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

fyrox_core/pool/
mod.rs
