Implements an Array-like interface for paged data that is object pool friendly. The internal data is stored in small "pages", each of which are obtained from an object pool and later returned to the object pool when finished. This allows the PooledArray class to obtain as much space as needed on demand from the object pool rather than have to de…

PooledArray.CS

// Copyright (c) 2017 StagPoint Software

namespace StagPoint.Collections
{
	using System;
	using System.Collections;
	using System.Collections.Generic;

	/// <summary>
	/// Implements an Array-like interface for paged data that is object pool friendly.
	/// The internal data is stored in small "pages", each of which are obtained from an object pool and 
	/// later returned to the object pool when finished. This allows the PooledArray class to obtain as 
	/// much space as needed on demand from the object pool rather than have to determine a scheme for 
	/// tracking and pooling various arrays of different sizes.
	/// For instance: with fixed size arrays an object pool could have one 10K array, one 20K array, 
	/// one 1K array, one 512 byte array, etc. By contrast, a PooledArray instance claims as many smaller
	/// pages from the object pool as it needs, which it then presents to the calling code as if they are 
	/// a single array of the required size, and then returns those pages to the object pool when they 
	/// are no longer needed.
	/// </summary>
	/// <typeparam name="T">The data type of the elements that will be stored in the array</typeparam>
	public class PooledArray<T> : IDisposable, IEnumerable, IEnumerable<T>
	{
		#region Constants

		private const int PAGE_SIZE = 1024;
		private const int PAGE_INDEX_SHIFT = 10;

		#endregion Constants

		#region Object pooling

		#region Static variables

		// NOTE: Switched to Stack<object> in an attempt to work around
		// a bug in the version of Mono used by Unity on iOS - http://stackoverflow.com/q/16542915
		private static Stack<object> s_objectPool = new Stack<object>( 128 );

		private static volatile object s_staticLockTarget = new object();

		#endregion Static variables

		/// <summary>
		/// Releases all instances in the object pool.
		/// </summary>
		public static void ClearPool()
		{
			lock( s_staticLockTarget )
			{
				s_objectPool.Clear();
				s_objectPool.TrimExcess();
			}
		}

		/// <summary>
		/// Returns a reference to a <see cref="PooledArray"/> instance. If there are
		/// available instances in the object pool, the first available instance will
		/// be returned. If there are no instances available, then a new instance
		/// will be created. Use the <see cref="Release"/> function to return the instance
		/// to the object pool.
		/// </summary>
		private static PooledArray<T> ClaimFromPool()
		{
			lock( s_staticLockTarget )
			{
				if( s_objectPool.Count > 0 )
				{
					return (PooledArray<T>)s_objectPool.Pop();
				}
			}

			return new PooledArray<T>( PAGE_SIZE );
		}

		/// <summary>
		/// Returns a reference to a <see cref="PooledArray"/> instance. If there are
		/// available instances in the object pool, the first available instance will
		/// be returned. If there are no instances available, then a new instance
		/// will be created. Use the <see cref="ReturnToPool"/> function to return the instance
		/// to the object pool.
		/// </summary>
		public static PooledArray<T> ClaimFromPool( int capacity )
		{
			var array = ClaimFromPool();

			array.ensureCapacity( capacity );

			return array;
		}

		/// <summary>
		/// Releases the <see cref="PooledArray"/> back to the object pool
		/// </summary>
		public void ReturnToPool()
		{
			for( int i = 0; i < m_pages.Count; i++ )
			{
				m_pages[ i ].ReturnToPool();
			}

			m_pages.Clear();

			lock( s_staticLockTarget )
			{
				s_objectPool.Push( this );
			}
		}

		#endregion Object pooling

		#region Private instance variables

		private List<Page> m_pages = null;
		private int m_capacity = 0;
		private int m_length = 0;
		private bool m_isElementTypeValueType = false;

		#endregion Private instance variables

		#region Public properties

		public int Length
		{
#if NET_VERSION_4_5
		[MethodImpl(MethodImplOptions.AggressiveInlining)]
#endif
			get { return m_length; }
			set
			{
				while( m_length > value )
				{
					var page = m_pages[ m_pages.Count - 1 ];
					page.ReturnToPool();

					m_pages.RemoveAt( m_pages.Count - 1 );

					m_capacity -= PAGE_SIZE;
					m_length = ( m_pages.Count + 1 ) * PAGE_SIZE;
				}

				ensureCapacity( value );
			}
		}

		public T this[ int index ]
		{
			get
			{
				if( index < 0 || index > m_length - 1 )
					throw new IndexOutOfRangeException();

				return m_pages[ index >> PAGE_INDEX_SHIFT ][ index ];
			}
			set
			{
				if( index < 0 )
					throw new IndexOutOfRangeException();

				m_pages[ index >> PAGE_INDEX_SHIFT ][ index ] = value;
			}
		}

		#endregion Public properties

		#region Constructor - Note: Calling code must use PooledArray<T>.ClaimFromPool() rather than the [new] operator

		// Disallow parameterless constructor 
		private PooledArray() { throw new NotImplementedException(); }

		private PooledArray( int length )
		{
#if !UNITY_EDITOR && UNITY_METRO
			isElementTypeValueType = typeof( T ).GetTypeInfo().IsValueType;
#else
			m_isElementTypeValueType = typeof( T ).IsValueType;
#endif
			m_pages = new List<Page>( PAGE_SIZE >> PAGE_INDEX_SHIFT );
			ensureCapacity( length );
		}

		#endregion Constructor

		#region Public functions

		public void Sort()
		{
			if( m_length <= 0 || m_pages.Count == 0 )
				return;

			if( m_pages.Count == 1 )
			{
				m_pages[ 0 ].Sort( m_length - 1 );
				return;
			}

			quickSort( 0, m_length - 1, Comparer<T>.Default );
		}

		/// <summary>
		/// Copies the elements of the collection to a <see cref="System.Array"/> instance
		/// </summary>
		/// <param name="array"></param>
		public void CopyTo( T[] array )
		{
			CopyTo( array, 0 );
		}

		/// <summary>
		/// Copies the elements of the collection to an <see cref="System.Array"/> starting at the specified destination array index
		/// </summary>
		public void CopyTo( T[] destination, int destinationIndex )
		{
			for( int i = 0; i < m_length; i++ )
			{
				destination[ destinationIndex++ ] = this[ i ];
			}
		}

		/// <summary>
		/// Copies the elements of the array to an <see cref="System.Array"/>
		/// </summary>
		/// <param name="sourceIndex">The position in the source array to start copying from</param>
		/// <param name="destination">The destination array</param>
		/// <param name="destinationIndex">The position in the destination array to start copying to</param>
		/// <param name="length">The total number of elements to copy</param>
		public void CopyTo( int sourceIndex, T[] destination, int destinationIndex, int length )
		{
			if( length == 0 )
				return;

			if( length < 0 )
				throw new IndexOutOfRangeException();

			if( sourceIndex + length > m_length )
				throw new IndexOutOfRangeException( "sourceIndex" );

			if( destination == null )
				throw new ArgumentNullException( "dest" );

			if( destinationIndex + length > destination.Length )
				throw new IndexOutOfRangeException( "destIndex" );

			for( int i = 0; i < length; i++ )
			{
				destination[ destinationIndex++ ] = this[ sourceIndex++ ];
			}
		}

		/// <summary>
		/// Returns a List&lt;T&gt; collection containing all elements of this array
		/// </summary>
		/// <returns></returns>
		public List<T> ToList()
		{
			var list = new List<T>( m_length );

			for( int i = 0; i < m_length; i++ )
			{
				list.Add( this[ i ] );
			}

			return list;
		}

		/// <summary>
		/// Returns an array containing all elements of this collection
		/// </summary>
		public T[] ToArray()
		{
			var array = new T[ m_length ];

			for( int i = 0; i < m_length; i++ )
			{
				array[ i ] = this[ i ];
			}

			return array;
		}

		/// <summary>
		/// Searches for the specified value by reference, which can be faster than using the DefaultEqualityComparer or
		/// calling the Equals function on the value, but only works with reference types.
		/// Returns the index of the specified value, if it is contained in the array. Returns -1 if the value is
		/// not contained in the array.
		/// </summary>
		/// <param name="value">The value to search for</param>
		public int IndexOfReference( T value )
		{
			if( m_isElementTypeValueType )
			{
				throw new InvalidOperationException( string.Format( "Type {0} is a value type. Use Contains() instead", typeof( T ) ) );
			}

			for( int i = 0; i < m_pages.Count; i++ )
			{
				var index = m_pages[ i ].IndexOfReference( value, m_length - 1 );
				if( index != -1 )
				{
					return index;
				}
			}

			return -1;
		}

		/// <summary>
		/// Returns the index of the specified value, if it is contained in the array. Returns -1 if the value is
		/// not contained in the array.
		/// </summary>
		/// <param name="value">The value to search for</param>
		public int IndexOf( T value )
		{
			for( int i = 0; i < m_pages.Count; i++ )
			{
				var index = m_pages[ i ].IndexOf( value, m_length - 1 );
				if( index != -1 )
				{
					return index;
				}
			}

			return -1;
		}

		/// <summary>
		/// Returns TRUE if the value is contained in the array, and returns FALSE otherwise.
		/// </summary>
		/// <param name="value">The value to search for</param>
#if NET_VERSION_4_5
		[MethodImpl(MethodImplOptions.AggressiveInlining)]
#endif
		public bool Contains( T value )
		{
			return IndexOf( value ) != -1;
		}

		/// <summary>
		/// Searches for the specified value by reference, which can be faster than using the DefaultEqualityComparer or
		/// calling the Equals function on the value, but only works with reference types.
		/// Returns TRUE if the value is contained in the array, and returns FALSE otherwise.
		/// </summary>
		/// <param name="value">The value to search for</param>
#if NET_VERSION_4_5
		[MethodImpl(MethodImplOptions.AggressiveInlining)]
#endif
		public bool ContainsReference( T value )
		{
			return IndexOfReference( value ) != -1;
		}

		/// <summary>
		/// Removes all elements from the array
		/// </summary>
		public void Clear()
		{
			for( int i = 0; i < m_pages.Count; i++ )
			{
				m_pages[ i ].Clear();
			}
		}

		#endregion Public functions

		#region Private utility functions

		/// <summary>
		/// Will ensure that the array's capacity is sufficient to hold the indicated number of elements
		/// </summary>
		/// <param name="totalCount">The total number of elements that the array must hold</param>
		private void ensureCapacity( int totalCount )
		{
			if( m_pages == null )
			{
				m_pages = new List<Page>();
			}

			while( totalCount > m_capacity )
			{
				m_pages.Add( Page.ClaimFromPool( m_capacity ) );
				m_capacity += PAGE_SIZE;
			}

			m_length = totalCount;
		}

		private void quickSort( int start, int end, IComparer<T> comparer )
		{
			if( start < end )
			{
				int pivot = partition( start, end, comparer );
				quickSort( start, pivot - 1, comparer );
				quickSort( pivot + 1, end, comparer );
			}
		}

		private int partition( int start, int end, IComparer<T> comparer )
		{
			var pivot = this[ end ];
			int pivotIndex = start;

			var itemTemp = default( T );

			for( int i = start; i < end; i++ )
			{
				if( comparer.Compare( this[ i ], pivot ) <= 0 )
				{
					itemTemp = this[ i ];
					this[ i ] = this[ pivotIndex ];
					this[ pivotIndex ] = itemTemp;

					pivotIndex++;
				}
			}

			itemTemp = this[ pivotIndex ];
			this[ pivotIndex ] = this[ end ];
			this[ end ] = itemTemp;

			return pivotIndex;
		}

		#endregion Private utility functions

		#region IDisposable Members

		public void Dispose()
		{
			this.ReturnToPool();
		}

		#endregion IDisposable Members

		#region IEnumerable Members

		public PooledArrayEnumerator Enumerator()
		{
			return new PooledArray<T>.PooledArrayEnumerator( this );
		}

		public IEnumerator<T> GetEnumerator()
		{
			return new PooledArray<T>.PooledArrayEnumerator( this );
		}

		IEnumerator IEnumerable.GetEnumerator()
		{
			return new PooledArray<T>.PooledArrayEnumerator( this );
		}

		#endregion IEnumerable Members

		#region Nested types

		private class Page
		{
			#region Object pooling

			private static Stack<object> s_objectPool = new Stack<object>();
			private static volatile object s_staticLockTarget = new object();

			public static Page ClaimFromPool( int baseIndex )
			{
				lock( s_staticLockTarget )
				{
					if( s_objectPool.Count > 0 )
					{
						var recycled = (Page)s_objectPool.Pop();
						recycled.m_baseIndex = baseIndex;

						return recycled;
					}
				}

				var newPage = new Page( baseIndex );
				return newPage;
			}

			#endregion Object pooling

			#region Private data members

			private T[] m_data;
			private int m_baseIndex;

			#endregion Private data members

			#region Constructor

			private Page()
			{
				throw new NotImplementedException();
			}

			private Page( int baseIndex )
			{
				m_baseIndex = baseIndex;
				m_data = new T[ PAGE_SIZE ];
			}

			#endregion Constructor

			#region Public properties

			public T this[ int index ]
			{
#if NET_VERSION_4_5
		[MethodImpl(MethodImplOptions.AggressiveInlining)]
#endif
				get { return m_data[ index - m_baseIndex ]; }
#if NET_VERSION_4_5
		[MethodImpl(MethodImplOptions.AggressiveInlining)]
#endif
				set { m_data[ index - m_baseIndex ] = value; }
			}

			#endregion Public properties

			#region Public functions

			public void Sort( int maxIndex )
			{
				var count = Math.Min( m_data.Length, maxIndex - m_baseIndex + 1 );
				Array.Sort( m_data, 0, count );
			}

			public int IndexOf( T value, int maxIndex )
			{
				var count = Math.Min( m_data.Length, maxIndex - m_baseIndex + 1 );
				return Array.IndexOf<T>( m_data, value, 0, count );
			}

			public int IndexOfReference( T value, int maxIndex )
			{
				var count = Math.Min( m_data.Length, maxIndex - m_baseIndex + 1 );
				for( int i = 0; i < count; i++ )
				{
					if( object.ReferenceEquals( m_data[ i ], value ) )
					{
						return m_baseIndex + i;
					}
				}

				return -1;
			}

			public void Clear()
			{
				Array.Clear( m_data, 0, m_data.Length );
			}

			public void ReturnToPool()
			{
				Array.Clear( m_data, 0, m_data.Length );

				lock( s_staticLockTarget )
				{
					s_objectPool.Push( this );
				}
			}

			#endregion Public functions
		}

		/// <summary>
		/// Enumerates the elements of a <see cref="T:System.Collections.Generic.List`1"/>.
		/// </summary>
		[Serializable]
		public struct PooledArrayEnumerator : IEnumerator, IDisposable, IEnumerator<T>
		{
			private PooledArray<T> array;
			private int next;
			private T current;

			public PooledArrayEnumerator GetEnumerator()
			{
				return this;
			}

			object IEnumerator.Current
			{
				get
				{
					if( this.next <= 0 )
						throw new InvalidOperationException();
					else
						return (object)this.current;
				}
			}

			public T Current
			{
				get
				{
					return this.current;
				}
			}

			internal PooledArrayEnumerator( PooledArray<T> array )
			{
				this.array = array;
				this.next = 0;
				this.current = default( T );
			}

			void IEnumerator.Reset()
			{
				this.next = 0;
			}

			public void Dispose()
			{
				this.array = null;
			}

			public bool MoveNext()
			{
				if( this.next < 0 )
					return false;
				if( this.next < this.array.Length )
				{
					this.current = this.array[ this.next++ ];
					return true;
				}
				else
				{
					this.next = -1;
					return false;
				}
			}
		}

		#endregion Nested types
	}
}