//
// Created by Eugeny Grishul
//
// See license at http://bamelg.com/license.txt
//
using System.Runtime;
namespace System.Collections {
// Designed for huge amounts of small structs
// O(1) allocation and removal
// Object addresses not changed after resize
public class PagedPool<T> {
private int _version;
private PageInfo* _firstPage;
private int _pageCount;
private const int _elementsPerPage1 = ( int )( ( Memory.DefaultPageReserveSize - typeof( PageInfo ).ContentStride ) / ( typeof( T ).ContentStride + sizeof( byte ) ) );
private const int _elementsPerPage2 = ( int )( ( Memory.DefaultPageReserveSize - typeof( PageInfo ).ContentStride ) / ( typeof( T ).ContentStride + sizeof( ushort ) ) );
private const bool _useIndices1 = _elementsPerPage1 < 256;
public const int BlockSize = _useIndices1 ? _elementsPerPage1 : _elementsPerPage2;
public int Count { get; private set; }
public int Capacity { get { return _pageCount * BlockSize; } }
public Functors.Action<T*> OnInitialize, OnFinalize = bitcast<Functors.Action<T*>>( typeof( T ).Destructor );
public PagedPool() {
Assert.IsTrue( typeof( T ).IsStruct | typeof( T ).IsFixedArray ); // PagedPool<T> designed to be used with structs
Assert.IsTrue( BlockSize > 2 ); // Dont use big structures
}
~PagedPool() {
if( OnFinalize != null )
foreach( var value in this )
OnFinalize( value );
for( var page = _firstPage; page != null; ) {
var next = page->Next;
Memory.FreePages( page->Elements, Memory.DefaultPageReserveCount );
page = next;
}
}
private PageInfo* AllocatePage() {
var memory = ( byte* ) Memory.AllocatePages( Memory.DefaultPageReserveCount );
var page = ( PageInfo* )( memory + Memory.DefaultPageReserveSize - typeof( PageInfo ).ContentStride );
// page->Parent = this; ReleaseReference();
*( void** ) &page->Parent = bitcast<void*>( this ); // dont touch refcount
page->Next = _firstPage;
_firstPage = page;
[DisableWarningUnreachable]
if( _useIndices1 ) {
var pageIndices = page->Indices1;
page->FreeIndexPtr = pageIndices;
for( var i = 0; i < BlockSize; ++i )
pageIndices[i] = ( byte ) i;
}
else {
var pageIndices = page->Indices2;
page->FreeIndexPtr = pageIndices;
for( var i = 0; i < BlockSize; ++i )
pageIndices[i] = ( ushort ) i;
}
return page;
}
// unfortunately we must return ptrs to prevent possible usage errors
public T* TryAllocate() {
CommonCollectionOperations.UpdateVersion( &_version );
for( var page = _firstPage; page != null; page = page->Next ) {
if( page->FreeCount <= 0 ) continue;
return Allocate( page );
}
// Allocate new page
{
var page = AllocatePage();
return Allocate( page );
}
}
public T* Allocate() {
var result = TryAllocate();
if( result == null ) Assert.Fail( "Not enought room for new elements!" );
return result;
}
public void Free( T* value ) {
if( value == null ) return;
CommonCollectionOperations.UpdateVersion( &_version );
var page = GetPageInfo( value );
if( page != null ) {
Free( page, value );
return;
}
Assert.Fail( "'value' not owned!" );
}
public yield<T*> GetEnumerator() {
var version = _version;
var freeMap = new BitArray( BlockSize );
for( var page = _firstPage; page != null; page = page->Next ) {
freeMap.Clear();
var count = page->Count;
if( count <= 0 ) continue;
var indices1 = page->Indices1;
var indices2 = page->Indices2;
var elements = page->Elements;
for( var j = count; j < BlockSize; ++j ) {
freeMap[_useIndices1 ? indices1[j] : indices2[j]] = true;
}
for( var j = 0; j < BlockSize; ++j ) {
if( freeMap[j] ) continue;
CommonCollectionOperations.VersionCheck( version == _version );
yield return elements + j;
}
}
}
/// For debug-only purposes
public int IndexOf( T* value ) {
var page = GetPageInfo( value );
if( page != null ) {
var valueIndex = IndexOf( page, value );
if( valueIndex == -1 ) return -1;
var pageIndex = _pageCount - 1;
for( var existingPage = _firstPage; existingPage != null; existingPage = existingPage->Next, --pageIndex ) {
if( page == existingPage )
return valueIndex + pageIndex * BlockSize;
}
return -1;
}
return -1;
}
/// @{ page operations
private struct PageInfo {
public declaringtype Parent;
public void* FreeIndexPtr;
public PageInfo* Next;
public byte* Indices1 { get { return bitcast<byte*>( &this ) - BlockSize; } }
public ushort* Indices2 { get { return bitcast<ushort*>( &this ) - BlockSize; } }
public T* Elements { get { return bitcast<T*>( bitcast<uintptr>( &this ) & ~( Memory.DefaultPageReserveSize - 1 ) ); } }
public int Count { get { return _useIndices1 ? ( int )( ( byte* ) FreeIndexPtr - Indices1 ) : ( int )( ( ushort* ) FreeIndexPtr - Indices2 ); } }
public int FreeCount { get { return ( int )( BlockSize - Count ); } }
}
private static PageInfo* GetPageInfo( T* element ) { return ( bitcast<PageInfo*>( bitcast<byte*>( bitcast<uintptr>( element ) | ( Memory.DefaultPageReserveSize - 1 ) ) - typeof( PageInfo ).ContentStride + 1 ) ); }
private int IndexOf( PageInfo* page, T* value ) {
if( page->Parent != this ) return -1;
var elements = page->Elements;
return ( value >= elements && value < elements + BlockSize ) ? ( int )( value - elements ) : -1;
}
private T* Allocate( PageInfo* page ) {
++Count;
ushort index;
[DisableWarningUnreachable]
if( _useIndices1 ) {
index = *( byte* ) page->FreeIndexPtr;
page->FreeIndexPtr = ( byte* ) page->FreeIndexPtr + 1;
}
else {
index = *( ushort* ) page->FreeIndexPtr;
page->FreeIndexPtr = ( ushort* ) page->FreeIndexPtr + 1;
}
var result = page->Elements + index;
Memory.Clear( result, sizeof( T ) );
if( OnInitialize != null ) OnInitialize( result );
return result;
}
[Conditional( ConditionString = "DEBUG" )]
private void VerifyOwning( PageInfo* page, T* value ) {
Assert.IsTrue( IsOwned( page, value ) );
}
[Conditional( ConditionString = "DEBUG" )]
private void VerifyFree( PageInfo* page, intptr value ) {
var freeCount = page->FreeCount;
[DisableWarningUnreachable]
if( _useIndices1 ) {
var freePtr = ( byte* ) page->FreeIndexPtr;
for( var i = 0; i < freeCount; ++i ) {
if( freePtr[i] == value ) {
Assert.Fail( "Object already freed!" );
return;
}
}
}
else {
var freePtr = ( ushort* ) page->FreeIndexPtr;
for( var i = 0; i < freeCount; ++i ) {
if( freePtr[i] == value ) {
Assert.Fail( "Object already freed!" );
return;
}
}
}
}
private void Free( PageInfo* page, T* value ) {
--Count;
VerifyOwning( page, value );
var index = value - page->Elements;
VerifyFree( page, index );
if( OnFinalize != null ) OnFinalize( value );
[DisableWarningUnreachable]
if( _useIndices1 ) {
page->FreeIndexPtr = ( byte* ) page->FreeIndexPtr - 1;
*( byte* ) page->FreeIndexPtr = ( byte ) index;
}
else {
page->FreeIndexPtr = ( ushort* ) page->FreeIndexPtr - 1;
*( ushort* ) page->FreeIndexPtr = ( ushort ) index;
}
}
private bool IsOwned( PageInfo* page, T* value ) {
var elements = page->Elements;
return value >= elements && value < elements + BlockSize;
}
/// @}
}
}