// 
// System.Web.Caching
//
// Author:
//   Patrik Torstensson (Patrik.Torstensson@labs2.com)
// Changes:
//   Daniel Cazzulino [DHC] (dcazzulino@users.sf.net)
//
// (C) Copyright Patrik Torstensson, 2001
//
namespace System.Web.Caching
{
	/// <summary>
	/// Responsible for holding a cache entry in the linked list bucket.
	/// </summary>
	internal struct ExpiresEntry
	{
		internal CacheEntry _objEntry;
		internal long _ticksExpires;
		internal int _intNext;
	}

	/// <summary>
	/// Holds cache entries that has a expiration in a bucket list.
	/// </summary>
	internal class ExpiresBucket
	{
		private static int MIN_ENTRIES = 16;
		
		private byte	_byteID;
		private int		_intSize;
		private int		_intCount;
		private	int		_intNext;

		private Cache	_objManager;

		private ExpiresEntry [] _arrEntries;

		/// <summary>
		/// A lock to use for syncronized operations. [DHC]
		/// </summary>
		private System.Threading.ReaderWriterLock _lock = new System.Threading.ReaderWriterLock();

		/// <summary>
		/// Keeps a list of indexes in the list which are available to place new items. [DHC]
		/// </summary>
		Int32Collection _freeidx = new Int32Collection();

		/// <summary>
		/// Constructs a new bucket.
		/// </summary>
		/// <param name="bucket">Current bucket ID.</param>
		/// <param name="objManager">Cache manager reponsible for the item(s) in the expires bucket.</param>
		internal ExpiresBucket(byte bucket, Cache objManager) 
		{
			_objManager = objManager;
			Initialize(bucket);
		}

		/// <summary>
		/// Initializes the expires bucket, creates a linked list of MIN_ENTRIES.
		/// </summary>
		/// <param name="bucket">Bucket ID.</param>
		private void Initialize(byte bucket)
		{
			_byteID = bucket;
			_intNext = 0;
			_intCount = 0;

			_arrEntries = new ExpiresEntry[MIN_ENTRIES];
			_intSize = MIN_ENTRIES;

			int intPos = 0;
			do 
			{
				_arrEntries[intPos]._intNext = intPos + 1;
				//HACK: [DHC] Use constant defined in Cache.
				//_arrEntries[intPos]._ticksExpires = System.DateTime.MaxValue.Ticks;
				_arrEntries[intPos]._ticksExpires = Cache.NoAbsoluteExpiration.Ticks;
				
				intPos++;
			} while (intPos < _intSize);

			_arrEntries[_intSize - 1]._intNext = -1;
		}

		/// <summary>
		/// Expands the bucket linked array list.
		/// </summary>
		private void Expand() 
		{
			//HACK: [DHC] MAJOR performance improvement by using Array.CopyTo method. Better locking added.
			_lock.AcquireReaderLock(0);
			try
			{
				int oldsize = _intSize;
				_intSize *= 2;

				// Copy items to the new list.
				ExpiresEntry[] newlist = new ExpiresEntry[_intSize];
				_arrEntries.CopyTo(newlist, 0);

				// Set last element to point to the next new empty element
				newlist[oldsize - 1]._intNext = oldsize;

				// Initialize positions for the rest of new elements.
				for (int i = oldsize; i < _intSize; i++)
				{
					newlist[i]._intNext = i + 1;
					newlist[i]._ticksExpires = Cache.NoAbsoluteExpiration.Ticks;
				}

				// Last item signals the expansion of the list.
				newlist[_intSize - 1]._intNext = -1;

				// Replace the existing list.
				_lock.UpgradeToWriterLock(0);
				_arrEntries = newlist;
			}
			finally
			{
				//Releases both reader & writer locks.
				_lock.ReleaseReaderLock();
			}

			/* ORIGINAL CODE *
			ExpiresEntry [] arrData;
			int intPos = 0;
			int intOldSize;

			lock(this)	
			{
				intOldSize = _intSize;
				_intSize *= 2;

				// Create a new array and copy the old data into the new array
				arrData = new ExpiresEntry[_intSize];

				do 
				{
					arrData[intPos] = _arrEntries[intPos];
					intPos++;
				} while (intPos < intOldSize);

				_intNext = intPos;

				// Initialize the "new" positions.
				do 
				{
					arrData[intPos]._intNext = intPos + 1;
					intPos++;
				} while (intPos < _intSize);

				arrData[_intSize - 1]._intNext = -1;

				_arrEntries = arrData;
			}
			*/
		}

		/// <summary>
		/// Adds a cache entry into the expires bucket.
		/// </summary>
		/// <param name="objEntry">Cache Entry object to be added.</param>
		internal void Add(CacheEntry objEntry)
		{
			bool dogrow = false;

			// Check the need for expansion or reuse free index.
			if (_intNext == -1)
			{
				if (_freeidx.Count == 0)
				{
					dogrow = true;
				}
				else
				{
					_lock.AcquireReaderLock(0);
					try
					{
						// Elements may have been removed before the lock statement.
						if (_freeidx.Count == 0)
						{
							dogrow = true;
						}
						else
						{
							_intNext = _freeidx[0];
							_freeidx.Remove(_intNext);
						}
					}
					finally
					{
						_lock.ReleaseReaderLock();
					}
				}
			}

			if (dogrow) Expand();
			
			_lock.AcquireWriterLock(0);
			try
			{
				_arrEntries[_intNext]._ticksExpires = objEntry.Expires;
				_arrEntries[_intNext]._objEntry = objEntry;
				// If there are free indexes in the list, reuse them for the _next value.
				if (_freeidx.Count != 0)
				{
					_intNext = _freeidx[0];
					_freeidx.Remove(_intNext);
				}
				else
				{
					_intNext = _arrEntries[_intNext]._intNext;
				}

				_intCount++;
			}
			finally
			{
				_lock.ReleaseWriterLock();
			}

			/* ORIGINAL CODE *
			if (_intNext == -1) 
			{
				Expand();
			}
			
			lock(this)	
			{
				_arrEntries[_intNext]._ticksExpires =  objEntry.Expires;
				_arrEntries[_intNext]._objEntry = objEntry;

				_intNext = _arrEntries[_intNext]._intNext;
			
				_intCount++;
			}
			*/
		}

		/// <summary>
		/// Removes a cache entry from the expires bucket.
		/// </summary>
		/// <param name="objEntry">Cache entry to be removed.</param>
		internal void Remove(CacheEntry objEntry)
		{
			//HACK: optimized locks. [DHC]
			_lock.AcquireReaderLock(0);
			try
			{
				// Check if this is our bucket
				if (objEntry.ExpiresIndex != _byteID) return;
				if (objEntry.ExpiresIndex == CacheEntry.NoIndexInBucket) return;
				if (_arrEntries.Length < objEntry.ExpiresIndex) return;

				// Proceed to removal.
				_lock.UpgradeToWriterLock(0);
				_intCount--;

				// Push the index as a free one.
				_freeidx.Add(objEntry.ExpiresIndex);

				_arrEntries[objEntry.ExpiresIndex]._objEntry = null;
				// Clear bucket-related values from the item.
				objEntry.ExpiresBucket = CacheEntry.NoBucketHash;
				objEntry.ExpiresIndex = CacheEntry.NoIndexInBucket;
			}
			finally
			{
				//Releases both reader & writer locks
				_lock.ReleaseReaderLock();
			}
		}

		/// <summary>
		/// Updates a cache entry in the expires bucket, this is called during a hit of an item if the 
		/// cache item has a sliding expiration. The function is responsible for updating the cache
		/// entry.
		/// </summary>
		/// <param name="objEntry">Cache entry to update.</param>
		/// <param name="ticksExpires">New expiration value for the cache entry.</param>
		internal void Update(CacheEntry objEntry, long ticksExpires)
		{
			//HACK: optimized locks. [DHC]
			_lock.AcquireReaderLock(0);
			try
			{
				// Check if this is our bucket
				if (objEntry.ExpiresIndex != _byteID) return;
				if (objEntry.ExpiresIndex == CacheEntry.NoIndexInBucket) return;
				if (_arrEntries.Length < objEntry.ExpiresIndex) return;

				_arrEntries[objEntry.ExpiresIndex]._ticksExpires = ticksExpires;
				_arrEntries[objEntry.ExpiresIndex]._objEntry.Expires = ticksExpires;

				// Proceed to update.
				_lock.UpgradeToWriterLock(0);
				_arrEntries[objEntry.ExpiresIndex]._ticksExpires = ticksExpires;
				_arrEntries[objEntry.ExpiresIndex]._objEntry.Expires = ticksExpires;
			}
			finally
			{
				//Releases both read & write locks
				_lock.ReleaseReaderLock();
			}
		}

		/// <summary>
		/// Flushes all cache entries that has expired and removes them from the cache manager.
		/// </summary>
		internal void FlushExpiredItems()
		{
			ExpiresEntry objEntry;
			CacheEntry [] arrCacheEntries;
			
			int		intCachePos;
			int		intPos;
			long	ticksNow;
	
			ticksNow = System.DateTime.Now.Ticks;

			intCachePos = 0;

			// Lookup all items that needs to be removed, this is done in a two part
			// operation to minimize the locking time.
			_lock.AcquireReaderLock(0);
			try
			{
				arrCacheEntries = new CacheEntry[_intSize];

				intPos = 0;
				do 
				{
					objEntry = _arrEntries[intPos];
					if (objEntry._objEntry != null)
					{
						if (objEntry._ticksExpires < ticksNow)
						{
							System.Threading.LockCookie ck = _lock.UpgradeToWriterLock(0);
							try
							{
								//push the index for reuse
								_freeidx.Add(intPos);
								arrCacheEntries[intCachePos++] = objEntry._objEntry;

								objEntry._objEntry.ExpiresBucket = CacheEntry.NoBucketHash;
								objEntry._objEntry.ExpiresIndex = CacheEntry.NoIndexInBucket;
								objEntry._objEntry = null;
							}
							finally
							{
								_lock.DowngradeFromWriterLock(ref ck);
							}
						}
					}
					
					intPos++;
				} while (intPos < _intSize);
			}
			finally
			{
				_lock.ReleaseReaderLock();
			}

			// If we have any entries to remove, go ahead and call the cache manager remove.
			if (intCachePos > 0)
			{
				intPos = 0;
				do 
				{
					_objManager.Remove(arrCacheEntries[intPos].Key, CacheItemRemovedReason.Expired);

					intPos++;
				} while (intPos < intCachePos);
			}
		}

		/// <summary>
		/// Returns the current size of the expires bucket.
		/// </summary>
		internal int Size
		{
			get 
			{ 
				//HACK: reuse the _intSize field!!! [DHC]
				return _intSize;
			}
		}

		/// <summary>
		/// Returns number of items in the bucket.
		/// </summary>
		internal int Count
		{
			get 
			{
				return  _intCount;
			}
		}

		#region Private Int32Collection
		/* This file has been automatically generated by TextBox -- DO NOT EDIT! */
		/*
		Int32Collection
		Int32Collection.Enumerator

		These C# classes implement a strongly-typed collection of 
		Int32 objects.

		The internal representation is an array of Int32, so the performance 
		characteristics will be more like a vector than a list, to use STL terminology.

		The implementation is optimized for value-types, as it goes to great length to 
		avoid the overhead of boxing and unboxing.  But it should also work well for 
		reference types.

		Mad props to Nick Wienholt <sheyenne@bigpond.com> for assisting me in 
		this research, and the testing, the benchmarking, and of course, the 
		implementation!

		Last but not least, a quick shout out to Kit George, for his generous 
		contribution to the dotnet mailing list -- a code-generator for 
		CollectionBase-derived classes:
			http://discuss.develop.com/archives/wa.exe?A2=ind0107C&L=DOTNET&P=R35911
		This was the original inspiration for the fine code you are now enjoying.

		- Shawn Van Ness

		Other folks who've contributed:
			Ethan Smith <ethan.smith@pobox.com> (minor perf. improvements)
			Joel Mueller <jmueller@swiftk.com> (major perf. improvements)
			Chris Sells <csells@sellsbrothers.com> (generative programming guru)
			Patrice Lafond <plafond@hemisphere.bm> (a bug fix -- yikes!)
		*/

		/// <summary>
		/// An optimized collection for holding <see cref="Int32"/> values.
		/// </summary>
		[System.Serializable]
		private class Int32Collection : System.Collections.ICollection, System.Collections.IList, System.Collections.IEnumerable
		{
		#region Private vars & ctors
			private const int DefaultMinimumCapacity = 16;

			private System.Int32[] m_array = new System.Int32[DefaultMinimumCapacity];
			private int m_count = 0;
			private int m_version = 0;

			/// <summary />
			public Int32Collection()
			{ }

			/// <summary />
			public Int32Collection(Int32Collection collection)
			{ AddRange(collection); }

			/// <summary />
			public Int32Collection(System.Int32[] array)
			{ AddRange(array); }
		#endregion

		#region Public members

			/// <summary />
			public int Count
			{
				get
				{ return m_count; }
			}

			/// <summary />
			public void CopyTo(System.Int32[] array)
			{
				this.CopyTo(array, 0);
			}

			/// <summary />
			public void CopyTo(System.Int32[] array, int start)
			{
				if (m_count > array.GetUpperBound(0)+1-start)
					throw new System.ArgumentException("Destination array was not long enough.");

				// for (int i=0; i < m_count; ++i) array[start+i] = m_array[i];
				System.Array.Copy(m_array, 0, array, start, m_count); 
			}

			/// <summary />
			public System.Int32 this[int index]
			{
				get
				{
					ValidateIndex(index); // throws
					return m_array[index]; 
				}
				set
				{
					ValidateIndex(index); // throws
				
					++m_version; 
					m_array[index] = value; 
				}
			}

			/// <summary />
			public int Add(System.Int32 item)
			{			
				if (NeedsGrowth())
					Grow();

				++m_version;
				m_array[m_count] = item;
			
				return m_count++;
			}
		
			/// <summary />
			public void Clear()
			{
				++m_version;
				m_array = new System.Int32[DefaultMinimumCapacity];
				m_count = 0;
			}

			/// <summary />
			public bool Contains(System.Int32 item)
			{
				return ((IndexOf(item) == -1)?false:true);
			}

			/// <summary />
			public int IndexOf(System.Int32 item)
			{
				for (int i=0; i < m_count; ++i)
					if (m_array[i].Equals(item))
						return i;
				return -1;
			}

			/// <summary />
			public void Insert(int position, System.Int32 item)
			{
				ValidateIndex(position,true); // throws
			
				if (NeedsGrowth())
					Grow();

				++m_version;
				System.Array.Copy(m_array, position, m_array, position+1, m_count-position);

				m_array[position] = item;
				m_count++;
			}

			/// <summary />
			public void Remove(System.Int32 item)
			{			
				int index = IndexOf(item);
				if (index < 0)
					throw new System.ArgumentException("Cannot remove the specified item because it was not found in the specified Collection.");
			
				RemoveAt(index);
			}

			/// <summary />
			public void RemoveAt(int index)
			{
				ValidateIndex(index); // throws
			
				++m_version;
				m_count--;
				System.Array.Copy(m_array, index+1, m_array, index, m_count-index);

				if (NeedsTrimming())
					Trim();
			}

			// Public helpers (just to mimic some nice features of ArrayList)

			/// <summary />
			public int Capacity
			{
				get
				{ return m_array.Length; }
				set
				{
					if (value < m_count) value = m_count;
					if (value < DefaultMinimumCapacity) value = DefaultMinimumCapacity;

					if (m_array.Length == value) return;

					++m_version;

					System.Int32[] temp = new System.Int32[value];
					System.Array.Copy(m_array, 0, temp, 0, m_count); 
					m_array = temp;
				}
			}

			/// <summary />
			public void AddRange(Int32Collection collection)
			{
				++m_version;

				Capacity += collection.Count;
				System.Array.Copy(collection.m_array, 0, this.m_array, m_count, collection.m_count);
				m_count += collection.Count;
			}

			/// <summary />
			public void AddRange(System.Int32[] array)
			{
				++m_version;

				Capacity += array.Length;
				System.Array.Copy(array, 0, this.m_array, m_count, array.Length);
				m_count += array.Length;
			}
		#endregion

		#region Private helper methods
			private void ValidateIndex(int index)
			{
				ValidateIndex(index,false);
			}

			private void ValidateIndex(int index, bool allowEqualEnd)
			{
				int max = (allowEqualEnd)?(m_count):(m_count-1);
				if (index < 0 || index > max)
					throw new System.ArgumentOutOfRangeException("Index was out of range.  Must be non-negative and less than the size of the collection.", (object)index, "Specified argument was out of the range of valid values.");
			}

			private bool NeedsGrowth()
			{
				return (m_count >= Capacity);
			}

			private void Grow()
			{
				if (NeedsGrowth())
					Capacity = m_count*2;
			}

			private bool NeedsTrimming()
			{
				return (m_count <= Capacity/2);
			}

			private void Trim()
			{
				if (NeedsTrimming())
					Capacity = m_count;
			}
		#endregion

		#region System.Collections.ICollection implementation
			bool System.Collections.ICollection.IsSynchronized
			{
				get
				{ return m_array.IsSynchronized; }
			}

			object System.Collections.ICollection.SyncRoot
			{
				get
				{ return m_array.SyncRoot; }
			}

			void System.Collections.ICollection.CopyTo(System.Array array, int start)
			{
				this.CopyTo((System.Int32[])array, start);
			}
		#endregion

		#region System.Collections.IList implementation
			bool System.Collections.IList.IsFixedSize
			{
				get
				{ return false; }
			}

			bool System.Collections.IList.IsReadOnly
			{
				get
				{ return false; }
			}

			object System.Collections.IList.this[int index]
			{
				get { return (object)this[index]; }
				set { this[index] = (System.Int32)value; }
			}

			int System.Collections.IList.Add(object item)
			{
				return this.Add((System.Int32)item);
			}

			bool System.Collections.IList.Contains(object item)
			{
				return this.Contains((System.Int32)item);
			}

			int System.Collections.IList.IndexOf(object item)
			{
				return this.IndexOf((System.Int32)item);
			}

			void System.Collections.IList.Insert(int position, object item)
			{
				this.Insert(position, (System.Int32)item);
			}

			void System.Collections.IList.Remove(object item)
			{
				this.Remove((System.Int32)item);
			}
		#endregion

		#region System.Collections.IEnumerable and enumerator implementation
			/// <summary />
			public Enumerator GetEnumerator()
			{
				return new Enumerator(this);
			}

			System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
			{
				return GetEnumerator();
			}

			// Nested enumerator class
			/// <summary />
			public class Enumerator : System.Collections.IEnumerator
			{
				private Int32Collection m_collection;
				private int m_index;
				private int m_version;

				// Construction
	
				/// <summary />
				public Enumerator(Int32Collection tc)
				{
					m_collection = tc;
					m_index = -1;
					m_version = tc.m_version;
				}
	
				/// <summary />
				public System.Int32 Current
				{
					get
					{ return m_collection[m_index]; }
				}
	
				/// <summary />
				public bool MoveNext()
				{
					if (m_version != m_collection.m_version)
						throw new System.InvalidOperationException("Collection was modified; enumeration operation may not execute.");

					++m_index;
					return (m_index < m_collection.Count)?true:false;
				}
	
				/// <summary />
				public void Reset()
				{
					if (m_version != m_collection.m_version)
						throw new System.InvalidOperationException("Collection was modified; enumeration operation may not execute.");

					m_index = -1;
				}

				object System.Collections.IEnumerator.Current
				{
					get
					{ return (object)(this.Current); }
				}
			}
		#endregion
		}
		#endregion
	}
}