context: //
  // System.Web.Caching.Cache
  //
  // Author(s):
  //  Lluis Sanchez (lluis@ximian.com)
  //  Marek Habersack <mhabersack@novell.com>
  //
  // (C) 2005-2009 Novell, Inc (http://novell.com)
  //
  //
  // Permission is hereby granted, free of charge, to any person obtaining
  // a copy of this software and associated documentation files (the
  // "Software"), to deal in the Software without restriction, including
  // without limitation the rights to use, copy, modify, merge, publish,
  // distribute, sublicense, and/or sell copies of the Software, and to
  // permit persons to whom the Software is furnished to do so, subject to
  // the following conditions:
  //
  // The above copyright notice and this permission notice shall be
  // included in all copies or substantial portions of the Software.
  //
  // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  //
  
  using System.Threading;
  using System.Collections;
  using System.Collections.Generic;
  using System.Linq;
  using System.Security.Permissions;
  using System.Web.Configuration;
  
  namespace System.Web.Caching
  {
  	// CAS - no InheritanceDemand here as the class is sealed
  	[AspNetHostingPermission (SecurityAction.LinkDemand, Level = AspNetHostingPermissionLevel.Minimal)]
  	public sealed class Cache: IEnumerable
  	{
  		const int LOW_WATER_MARK = 10000; // Target number of items if high water mark is reached
  		const int HIGH_WATER_MARK = 15000; // We start collection after exceeding this count
  		
  		public static readonly DateTime NoAbsoluteExpiration = DateTime.MaxValue;
  		public static readonly TimeSpan NoSlidingExpiration = TimeSpan.Zero;
  
  		// cacheLock will be released in the code below without checking whether it was
  		// actually acquired. The API doesn't offer a reliable way to check whether the lock
  		// is being held by the current thread and since Mono does't implement CER
  		// (Constrained Execution Regions -
  		// http://msdn.microsoft.com/en-us/library/ms228973.aspx) currently, we have no
  		// reliable way of recording the information that the lock has been successfully
  		// acquired.
  		// It can happen that a Thread.Abort occurs while acquiring the lock and the lock
  		// isn't  actually held. In this case the attempt to release a lock will throw an
  		// exception. It's better than a race of setting a boolean flag  after acquiring the
  		// lock and then relying upon it here to release it - that may cause a deadlock
  		// should we fail to release the lock  which was successfully acquired but
  		// Thread.Abort happened right after that during the stloc instruction to set the
  		// boolean flag. Once CERs are supported we can use the boolean flag reliably.
  		ReaderWriterLockSlim cacheLock;
  		CacheItemLRU cache;
  		CacheItemPriorityQueue timedItems;
  		Timer expirationTimer;
  		long expirationTimerPeriod = 0;
  		Cache dependencyCache;
  		bool? disableExpiration;
  		long privateBytesLimit = -1;
  		long percentagePhysicalMemoryLimit = -1;
  		
  		bool DisableExpiration {
  			get {
  				if (disableExpiration == null) {
  					var cs = WebConfigurationManager.GetWebApplicationSection ("system.web/caching/cache") as CacheSection;
  					if (cs == null)
  						disableExpiration = false;
  					else
  						disableExpiration = (bool)cs.DisableExpiration;
  				}
  
  				return (bool)disableExpiration;
  			}
  		}
  
  		public long EffectivePrivateBytesLimit {
  			get {
  				if (privateBytesLimit == -1) {
  					var cs = WebConfigurationManager.GetWebApplicationSection ("system.web/caching/cache") as CacheSection;
  					if (cs == null)
  						privateBytesLimit = 0;
  					else
  						privateBytesLimit = cs.PrivateBytesLimit;
  
  					if (privateBytesLimit == 0) {
  						// http://blogs.msdn.com/tmarq/archive/2007/06/25/some-history-on-the-asp-net-cache-memory-limits.aspx
  						// TODO: calculate
  						privateBytesLimit = 734003200;
  					}
  				}
  
  				return privateBytesLimit;
  			}
  		}
  
  		public long EffectivePercentagePhysicalMemoryLimit {
  			get {
  				if (percentagePhysicalMemoryLimit == -1) {
  					var cs = WebConfigurationManager.GetWebApplicationSection ("system.web/caching/cache") as CacheSection;
  					if (cs == null)
  						percentagePhysicalMemoryLimit = 0;
  					else
  						percentagePhysicalMemoryLimit = cs.PercentagePhysicalMemoryUsedLimit;
  
  					if (percentagePhysicalMemoryLimit == 0) {
  						// http://blogs.msdn.com/tmarq/archive/2007/06/25/some-history-on-the-asp-net-cache-memory-limits.aspx
  						// TODO: calculate
  						percentagePhysicalMemoryLimit = 97;
  					}
  				}
  
  				return percentagePhysicalMemoryLimit;
  			}
  		}
  		
  		public Cache ()
  		{
  			cacheLock = new ReaderWriterLockSlim ();
  			cache = new CacheItemLRU (this, HIGH_WATER_MARK, LOW_WATER_MARK);
  		}
  
  		public int Count {
  			get { return cache.Count; }
  		}
  		
  		public object this [string key] {
  			get { return Get (key); }
  			set { Insert (key, value); }
  		}
  
  		// Must ALWAYS be called with the cache write lock held
  		CacheItem RemoveCacheItem (string key)
  		{
  			if (key == null)
  				return null;
  
  			CacheItem ret = cache [key];
  			if (ret == null)
  				return null;
  			
  			if (timedItems != null)
  				timedItems.OnItemDisable (ret);
  			
  			ret.Disabled = true;
  			cache.Remove (key);
  			
  			return ret;
  		}
  		
  		public object Add (string key, object value, CacheDependency dependencies, DateTime absoluteExpiration, TimeSpan slidingExpiration, CacheItemPriority priority, CacheItemRemovedCallback onRemoveCallback)
  		{
  			if (key == null)
  				throw new ArgumentNullException ("key");
  			
  			try {
  				cacheLock.EnterWriteLock ();
  				CacheItem it = cache [key];
  
  				if (it != null)
  					return it.Value;
  				Insert (key, value, dependencies, absoluteExpiration, slidingExpiration, priority, onRemoveCallback, null, false);
  			} finally {
  				// See comment at the top of the file, above cacheLock declaration
  				cacheLock.ExitWriteLock ();
  			}
  				
  			return null;
  		}
  		
  		public object Get (string key)
  		{
  			try {
  				cacheLock.EnterUpgradeableReadLock ();
  				CacheItem it = cache [key];
  				if (it == null)
  					return null;
  				
  				if (it.Dependency != null && it.Dependency.HasChanged) {
  					try {
  						cacheLock.EnterWriteLock ();
  						if (!NeedsUpdate (it, CacheItemUpdateReason.DependencyChanged, false))
  							Remove (it.Key, CacheItemRemovedReason.DependencyChanged, false, true);
  					} finally {
  						// See comment at the top of the file, above cacheLock declaration
  						cacheLock.ExitWriteLock ();
  					}
  					
  					return null;
  				}
  
  				if (!DisableExpiration) {
  					if (it.SlidingExpiration != NoSlidingExpiration) {
  						it.AbsoluteExpiration = DateTime.Now + it.SlidingExpiration;
  						// Cast to long is ok since we know that sliding expiration
  						// is less than 365 days (31536000000ms)
  						long remaining = (long)it.SlidingExpiration.TotalMilliseconds;
  						it.ExpiresAt = it.AbsoluteExpiration.Ticks;
  						
  						if (expirationTimer != null && (expirationTimerPeriod == 0 || expirationTimerPeriod > remaining)) {
  							expirationTimerPeriod = remaining;
  							expirationTimer.Change (expirationTimerPeriod, expirationTimerPeriod);
  						}
  					
  					} else if (DateTime.Now >= it.AbsoluteExpiration) {
  						try {
  							cacheLock.EnterWriteLock ();
  							if (!NeedsUpdate (it, CacheItemUpdateReason.Expired, false))
  								Remove (key, CacheItemRemovedReason.Expired, false, true);
  						} finally {
  							// See comment at the top of the file, above cacheLock declaration
  							cacheLock.ExitWriteLock ();
  						}
  
  						return null;
  					}
  				}
  				
  				return it.Value;
  			} finally {
  				// See comment at the top of the file, above cacheLock declaration
  				cacheLock.ExitUpgradeableReadLock ();
  			}
  		}
  		
  		public void Insert (string key, object value)
  		{
  			Insert (key, value, null, NoAbsoluteExpiration, NoSlidingExpiration, CacheItemPriority.Normal, null, null, true);
  		}
  		
  		public void Insert (string key, object value, CacheDependency dependencies)
  		{
  			Insert (key, value, dependencies, NoAbsoluteExpiration, NoSlidingExpiration, CacheItemPriority.Normal, null, null, true);
  		}
  		
  		public void Insert (string key, object value, CacheDependency dependencies, DateTime absoluteExpiration, TimeSpan slidingExpiration)
  		{
  			Insert (key, value, dependencies, absoluteExpiration, slidingExpiration, CacheItemPriority.Normal, null, null, true);
  		}
  
  		public void Insert (string key, object value, CacheDependency dependencies, DateTime absoluteExpiration, TimeSpan slidingExpiration,
  				    CacheItemUpdateCallback onUpdateCallback)
  		{
  			Insert (key, value, dependencies, absoluteExpiration, slidingExpiration, CacheItemPriority.Normal, null, onUpdateCallback, true);
  		}
  		
  		public void Insert (string key, object value, CacheDependency dependencies, DateTime absoluteExpiration, TimeSpan slidingExpiration,
  				    CacheItemPriority priority, CacheItemRemovedCallback onRemoveCallback)
  		{
  			Insert (key, value, dependencies, absoluteExpiration, slidingExpiration, priority, onRemoveCallback, null, true);
  		}
  
  		void Insert (string key, object value, CacheDependency dependencies, DateTime absoluteExpiration, TimeSpan slidingExpiration,
  			     CacheItemPriority priority, CacheItemRemovedCallback onRemoveCallback, CacheItemUpdateCallback onUpdateCallback, bool doLock)
  		{
  			if (key == null)
  				throw new ArgumentNullException ("key");
  			if (value == null)
  				throw new ArgumentNullException ("value");
  			if (slidingExpiration < TimeSpan.Zero || slidingExpiration > TimeSpan.FromDays (365))
  				throw new ArgumentNullException ("slidingExpiration");
  			if (absoluteExpiration != NoAbsoluteExpiration && slidingExpiration != NoSlidingExpiration)
  				throw new ArgumentException ("Both absoluteExpiration and slidingExpiration are specified");
  				
  			CacheItem ci = new CacheItem ();
  			ci.Value = value;
  			ci.Key = key;
  			
  			if (dependencies != null) {
  				ci.Dependency = dependencies;
  				dependencies.DependencyChanged += new EventHandler (OnDependencyChanged);
  				dependencies.SetCache (DependencyCache);
  			}
  
  			ci.Priority = priority;
  			SetItemTimeout (ci, absoluteExpiration, slidingExpiration, onRemoveCallback, onUpdateCallback, key, doLock);
  		}
  		
  		internal void SetItemTimeout (string key, DateTime absoluteExpiration, TimeSpan slidingExpiration, bool doLock)
  		{
  			CacheItem ci = null;			
  			try {
  				if (doLock)
  					cacheLock.EnterWriteLock ();
  				
  				ci = cache [key];
  				if (ci != null)
  					SetItemTimeout (ci, absoluteExpiration, slidingExpiration, ci.OnRemoveCallback, null, key, false);
  			} finally {
  				if (doLock) {
  					// See comment at the top of the file, above cacheLock declaration
  					cacheLock.ExitWriteLock ();
  				}
  			}
  		}
  
  		void SetItemTimeout (CacheItem ci, DateTime absoluteExpiration, TimeSpan slidingExpiration, CacheItemRemovedCallback onRemoveCallback,
  				     CacheItemUpdateCallback onUpdateCallback, string key, bool doLock)
  		{
  			bool disableExpiration = DisableExpiration;
  
  			if (!disableExpiration) {
  				ci.SlidingExpiration = slidingExpiration;
  				if (slidingExpiration != NoSlidingExpiration)
  					ci.AbsoluteExpiration = DateTime.Now + slidingExpiration;
  				else
  					ci.AbsoluteExpiration = absoluteExpiration;			
  			}
  			
  			ci.OnRemoveCallback = onRemoveCallback;
  			ci.OnUpdateCallback = onUpdateCallback;
  			
  			try {
  				if (doLock)
  					cacheLock.EnterWriteLock ();
  
  				if (key != null) {
  					cache [key] = ci;
  					cache.EvictIfNecessary ();
  				}
  				
  				ci.LastChange = DateTime.Now;
  				if (!disableExpiration && ci.AbsoluteExpiration != NoAbsoluteExpiration) {
  					bool enqueue;
  					if (ci.IsTimedItem) {
  						enqueue = UpdateTimedItem (ci);
  						if (!enqueue)
  							UpdateTimerPeriod (ci);
  					} else
  						enqueue = true;
  
  					if (enqueue) {
  						ci.IsTimedItem = true;
  						EnqueueTimedItem (ci);
  					}
  					
  				}
  			} finally {
  				if (doLock) {
  					// See comment at the top of the file, above cacheLock declaration
  					cacheLock.ExitWriteLock ();
  				}
  			}
  		}
  
  		// MUST be called with cache lock held
  		bool UpdateTimedItem (CacheItem item)
  		{
  			if (timedItems == null)
  				return true;
  
  			item.ExpiresAt = item.AbsoluteExpiration.Ticks;
  			return !timedItems.Update (item);
  		}
  
  		// MUST be called with cache lock held
  		void UpdateTimerPeriod (CacheItem item)
  		{
  			if (timedItems == null)
  				timedItems = new CacheItemPriorityQueue ();
  
  			long remaining = Math.Max (0, (long)(item.AbsoluteExpiration - DateTime.Now).TotalMilliseconds);
  			item.ExpiresAt = item.AbsoluteExpiration.Ticks;
  			
  			if (remaining > 4294967294)
  				// Maximum due time for timer
  				// Item will expire properly anyway, as the timer will be
  				// rescheduled for the item's expiration time once that item is
  				// bubbled to the top of the priority queue.
  				remaining = 4294967294;
  
  			if (expirationTimer != null && expirationTimerPeriod <= remaining)
  				return;
  			expirationTimerPeriod = remaining;
  
  			if (expirationTimer == null)
  				expirationTimer = new Timer (new TimerCallback (ExpireItems), null, expirationTimerPeriod, expirationTimerPeriod);
  			else
  				expirationTimer.Change (expirationTimerPeriod, expirationTimerPeriod);
  		}
  		
  		// MUST be called with cache lock held
  		void EnqueueTimedItem (CacheItem item)
  		{
  			UpdateTimerPeriod (item);
  			timedItems.Enqueue (item);
  		}
  
  		public object Remove (string key)
  		{
  			return Remove (key, CacheItemRemovedReason.Removed, true, true);
  		}
  		
  		internal object Remove (string key, CacheItemRemovedReason reason, bool doLock, bool invokeCallback)
  		{
  			CacheItem it = null;
  			try {
  				if (doLock)
  					cacheLock.EnterWriteLock ();
  				
  				it = RemoveCacheItem (key);
  			} finally {
  				if (doLock) {
  					// See comment at the top of the file, above cacheLock declaration
  					cacheLock.ExitWriteLock ();
  				}
  			}
  
  			object ret = null;
  
gt: 			if (it != null) {