//
// Created by Eugeny Grishul
//
// See license at http://bamelg.com/license.txt
//
using System.Diagnostics;
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 PagedQueue<T> {
private int _version;
private PageInfo* _firstPage;
private PageInfo* _lastPage;
// at most 1 free page is cached
private PageInfo* _freePage;
private int _pageCount;
public const int BlockSize = ( int )( ( Memory.DefaultPageReserveSize - typeof( PageInfo ).ContentStride ) / typeof( T ).ContentStride );
public int Count { get; private set; }
public int Capacity { get { return _pageCount * BlockSize; } }
public int PageCount { get { return _pageCount; } }
public Functors.Action<T*> OnInitialize, OnFinalize = bitcast<Functors.Action<T*>>( typeof( T ).Destructor );
public PagedQueue() {
Assert.IsTrue( typeof( T ).IsStruct | typeof( T ).IsFixedArray ); // PagedQueue<T> designed to be use with structs
Assert.IsTrue( BlockSize > 2 ); // Dont use big structures
AllocatePage();
}
~PagedQueue() {
if( OnFinalize != null )
foreach( var value in this )
OnFinalize( value );
for( var page = _firstPage; page != null; ) {
var next = page->Next;
FreePage( page );
page = next;
}
if( _freePage != null )
FreePage( _freePage );
}
public T* First() {
if( !Assert.IsTrue( _firstPage->Count > 0 ) ) return null;
return _firstPage->Elements + _firstPage->Head;
}
public T* Last() {
if( !Assert.IsTrue( _lastPage->Count > 0 ) ) return null;
return _lastPage->Elements + ( _lastPage->Tail > 0 ? _lastPage->Tail - 1 : BlockSize - 1 );
}
private PageInfo* AllocatePage() {
byte* memory;
if( _freePage != null ) {
memory = ( byte* ) _freePage->Elements;
_freePage = null;
}
else {
memory = ( byte* ) Memory.AllocatePages( Memory.DefaultPageReserveCount );
++_pageCount;
}
var page = ( PageInfo* )( memory + Memory.DefaultPageReserveSize - typeof( PageInfo ).ContentStride );
*( void** ) &page->Parent = bitcast<void*>( this ); // dont touch refcount
if( _firstPage == null ) _firstPage = page;
if( _lastPage != null ) _lastPage->Next = page;
_lastPage = page;
return page;
}
private void FreePage( PageInfo* page ) {
--_pageCount;
Memory.FreePages( page->Elements, Memory.DefaultPageReserveCount );
}
// unfortunately we must return ptrs to prevent possible usage errors
public T* TryEnqueue() {
CommonCollectionOperations.UpdateVersion( &_version );
if( _lastPage != null && _lastPage->FreeCount > 0 )
return Enqueue( _lastPage );
// Enqueue new page
{
var page = AllocatePage();
return Enqueue( page );
}
}
public T* Enqueue() {
var result = TryEnqueue();
if( result == null ) Assert.Fail( "Not enought room for new elements!" );
return result;
}
private static PageInfo* GetPageInfo( T* element ) { return ( bitcast<PageInfo*>( bitcast<byte*>( bitcast<uintptr>( element ) | ( Memory.DefaultPageReserveSize - 1 ) ) - typeof( PageInfo ).ContentStride + 1 ) ); }
public void* Dequeue() {
CommonCollectionOperations.UpdateVersion( &_version );
var result = Dequeue( _firstPage );
if( result == null ) return null;
if( _firstPage->Count == 0 ) {
var next = _firstPage->Next;
if( _freePage == null )
_freePage = _firstPage;
else {
FreePage( _freePage ); // delete cold page
_freePage = _firstPage; // _freePage = hot page
}
_firstPage = next;
}
return result;
}
public yield<T*> GetEnumerator( T* startingValue ) {
var version = _version;
var startingPage = GetPageInfo( startingValue );
Debug.Assert( startingPage->Parent == this );
Debug.Assert( startingPage->Count > 0 );
var startingIndex = startingValue - startingPage->Elements;
Debug.Assert( startingIndex >= 0 );
Debug.Assert( startingIndex < BlockSize );
// iterate startingPage
{
Debug.Assert( startingPage->Count > 0 );
var elements = startingPage->Elements;
if( startingIndex < startingPage->Tail ) {
for( var j = startingIndex; j < startingPage->Tail; ++j ) {
CommonCollectionOperations.VersionCheck( version == _version );
yield return elements + j;
}
}
else {
for( var j = startingIndex; j < BlockSize; ++j ) {
CommonCollectionOperations.VersionCheck( version == _version );
yield return elements + j;
}
for( var j = 0; j < startingPage->Tail; ++j ) {
CommonCollectionOperations.VersionCheck( version == _version );
yield return elements + j;
}
}
}
// iterate following pages
for( var page = startingPage->Next; page != null; page = page->Next ) {
Debug.Assert( page->Count > 0 );
var elements = page->Elements;
if( page->Head < page->Tail ) {
for( var j = page->Head; j < page->Tail; ++j ) {
CommonCollectionOperations.VersionCheck( version == _version );
yield return elements + j;
}
}
else {
for( var j = page->Head; j < BlockSize; ++j ) {
CommonCollectionOperations.VersionCheck( version == _version );
yield return elements + j;
}
for( var j = 0; j < page->Tail; ++j ) {
CommonCollectionOperations.VersionCheck( version == _version );
yield return elements + j;
}
}
}
}
public yield<T*> GetEnumerator() {
var version = _version;
for( var page = _firstPage; page != null; page = page->Next ) {
var count = page->Count;
if( count <= 0 ) continue;
var elements = page->Elements;
if( page->Head < page->Tail ) {
for( var j = page->Head; j < page->Tail; ++j ) {
CommonCollectionOperations.VersionCheck( version == _version );
yield return elements + j;
}
}
else {
for( var j = page->Head; j < BlockSize; ++j ) {
CommonCollectionOperations.VersionCheck( version == _version );
yield return elements + j;
}
for( var j = 0; j < page->Tail; ++j ) {
CommonCollectionOperations.VersionCheck( version == _version );
yield return elements + j;
}
}
}
}
#region page operations
private struct PageInfo {
public declaringtype Parent;
public PageInfo* Next;
public T* Elements { get { return bitcast<T*>( bitcast<uintptr>( &this ) & ~( Memory.DefaultPageReserveSize - 1 ) ); } }
public int Tail, Head, Count;
public int FreeCount { get { return ( int )( BlockSize - Count ); } }
}
private T* Enqueue( PageInfo* page ) {
var result = page->Elements + page->Tail;
++page->Tail;
if( page->Tail >= BlockSize ) page->Tail = 0;
++page->Count;
++Count;
CommonCollectionOperations.UpdateVersion( &_version );
Memory.Clear( result, sizeof( T ) );
if( OnInitialize != null ) OnInitialize( result );
return result;
}
// Remove first element from queue, returns deleted ptr
private void* Dequeue( PageInfo* page ) {
if( !Assert.IsTrue( page->Count > 0 ) ) return null;
var result = page->Elements + page->Head;
*result = default( T );
++page->Head;
if( page->Head >= BlockSize ) page->Head = 0;
--page->Count;
--Count;
CommonCollectionOperations.UpdateVersion( &_version );
return result;
}
#endregion
}
}