// codesnip-guard: Allocator
#[cfg_attr(any(),rustfmt::skip)]pub use self::allocator::{Allocator,BoxAllocator,MemoryPool};#[cfg_attr(any(),rustfmt::skip)]mod allocator{use std::{fmt::{self,Debug},marker::PhantomData,mem::{replace,size_of,take},ptr::{self,NonNull,read,write}};#[doc=" # Safety"]#[doc=" Allocations must contain the supplied value and remain valid until deallocation"]#[doc=" or allocator destruction. Live nonzero-sized allocations must not overlap."]pub unsafe trait Allocator<T>{fn allocate(&mut self,value:T)->NonNull<T>;#[doc=" # Safety"]#[doc=" `ptr` must hold a live value allocated by this allocator, with no remaining"]#[doc=" references. The allocation must not be accessed after this call."]unsafe fn deallocate(&mut self,ptr:NonNull<T>)->T;}pub struct MemoryPool<T>{pool:Vec<T>,chunks:Vec<Vec<T>>,unused:Vec<NonNull<T>>}impl<T>Debug for MemoryPool<T>{fn fmt(&self,f:&mut fmt::Formatter<'_>)->fmt::Result{f.debug_struct("MemoryPool").field("pool_len",&self.pool.len()).field("chunks",&self.chunks.len()).field("unused",&self.unused.len()).finish()}}impl<T>Default for MemoryPool<T>{fn default()->Self{Self::with_capacity(CAP/1usize.max(size_of::<T>()))}}const CAP:usize=1024;impl<T>MemoryPool<T>{pub fn new()->Self{Default::default()}pub fn with_capacity(capacity:usize)->Self{let pool=Vec::with_capacity(capacity.max(1));Self{pool,chunks:Vec::new(),unused:Vec::new()}}}impl<T>Drop for MemoryPool<T>{fn drop(&mut self){if size_of::<T>()==0{let mut unused=self.unused.len();for chunk in std::iter::once(&mut self.pool).chain(&mut self.chunks){let removed=unused.min(chunk.len());unsafe{chunk.set_len(chunk.len()-removed)};unused-=removed;}return;}self.chunks.push(take(&mut self.pool));let mut removed=vec![vec![];self.chunks.len()];for p in self.unused.iter(){let p=p.as_ptr();for(chunk,removed)in self.chunks.iter().zip(&mut removed).rev(){let ptr=chunk.as_ptr()as*mut _;let len=chunk.len();if ptr<=p&&p<ptr.wrapping_add(len){removed.push(p);}}}for(chunk,removed)in self.chunks.iter_mut().zip(&mut removed){removed.sort_unstable();for&p in removed.iter().rev(){unsafe{let len=chunk.len();let base_ptr=chunk.as_mut_ptr();ptr::copy(base_ptr.add(len-1),p,1);chunk.set_len(len-1);}}}}}unsafe impl<T>Allocator<T>for MemoryPool<T>{fn allocate(&mut self,value:T)->NonNull<T>{if let Some(ptr)=self.unused.pop(){unsafe{write(ptr.as_ptr(),value)};ptr}else{let len=self.pool.len();if len>=self.pool.capacity(){let new_capacity=self.pool.capacity()*2;let new_pool=Vec::with_capacity(new_capacity);self.chunks.push(replace(&mut self.pool,new_pool));}let len=self.pool.len();debug_assert!(len<self.pool.capacity());self.pool.push(value);unsafe{NonNull::new_unchecked(self.pool.as_mut_ptr().add(len))}}}unsafe fn deallocate(&mut self,ptr:NonNull<T>)->T{self.unused.push(ptr);unsafe{read(ptr.as_ptr())}}}#[derive(Debug)]pub struct BoxAllocator<T>(PhantomData<fn()->T>);impl<T>Default for BoxAllocator<T>{fn default()->Self{Self(PhantomData)}}unsafe impl<T>Allocator<T>for BoxAllocator<T>{fn allocate(&mut self,value:T)->NonNull<T>{unsafe{NonNull::new_unchecked(Box::leak(Box::new(value)))}}unsafe fn deallocate(&mut self,ptr:NonNull<T>)->T{unsafe{*Box::from_raw(ptr.as_ptr())}}}}