mono/mcs/class/System.Web/System.Web.Caching/CacheItemPriorityQueue.cs

//
// System.Web.Caching.CacheItem
//
// Author(s):
//  Marek Habersack <[email protected]>
//
// (C) 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;
using System.Text;
using System.Threading;

namespace System.Web.Caching
{
	sealed class CacheItemPriorityQueue
	{
		sealed class Node
		{
			public CacheItem Data;
		
			public Node Left;
			public Node Right;
			public Node Parent;
			public Node Next;
			public Node Prev;

			public CacheItem SwapData (CacheItem newData)
			{
				CacheItem ret = Data;
				Data = newData;
				
				return ret;
			}

			public Node (CacheItem data)
			{
				Data = data;
			}
		}
		
		Node root;
		Node lastAdded;
		Node firstParent;
		Node lastParent;

#if SYSTEMCORE_DEP
		ReaderWriterLockSlim queueLock;
#endif

		public CacheItemPriorityQueue ()
		{
#if SYSTEMCORE_DEP
			queueLock = new ReaderWriterLockSlim ();
#endif
		}
		
		public void Enqueue (CacheItem item)
		{
			if (item == null)
				return;

#if SYSTEMCORE_DEP
			bool locked = false;
			try {
				queueLock.EnterWriteLock ();
				locked = true;
#endif
				Node node = new Node (item);
				if (root == null) {
					root = lastAdded = lastParent = firstParent = node;
					return;
				}

				if (lastParent.Left != null && lastParent.Right != null) {
					lastParent = lastParent.Next;
					if (lastParent == null) {
						lastParent = firstParent = firstParent.Left;
						lastAdded = null;
					}
				}

				node.Parent = lastParent;			
				if (lastParent.Left == null)
					lastParent.Left = node;
				else
					lastParent.Right = node;

				if (lastAdded != null) {
					lastAdded.Next = node;
					node.Prev = lastAdded;
				}
			
				lastAdded = node;
				BubbleUp (node);
#if SYSTEMCORE_DEP
			} finally {
				if (locked)
					queueLock.ExitWriteLock ();
			}
#endif
		}

		public CacheItem Dequeue ()
		{
			CacheItem ret = null;
#if SYSTEMCORE_DEP
			bool locked = false;
			try {
				queueLock.EnterWriteLock ();
				locked = true;
#endif
				if (root == null)
					return null;

			
				if (root.Left == null && root.Right == null) {
					ret = root.Data;
					root = null;
					if (ret.Disabled)
						return null;
				
					return ret;
				}

				ret = root.Data;
				do {
					Node last = lastAdded;
					if (last == null)
						return null;
				
					if (last.Prev == null) {
						Node parent = last.Parent;
						while (true) {
							if (parent.Next == null)
								break;
							parent = parent.Next;
						}
						lastAdded = parent;
					} else {
						lastAdded = last.Prev;
						lastAdded.Next = null;
					}

					if (last.Parent.Left == last)
						last.Parent.Left = null;
					else
						last.Parent.Right = null;
			
					root.Data = last.Data;
					BubbleDown (root);
				} while (ret.Disabled);
#if SYSTEMCORE_DEP
			} finally {
				if (locked)
					queueLock.ExitWriteLock ();
			}
#endif
			return ret;
		}

		public CacheItem Peek ()
		{
#if SYSTEMCORE_DEP
			bool locked = false;
			try {
				queueLock.EnterReadLock ();
				locked = true;
#endif
				if (root == null)
					return null;
#if SYSTEMCORE_DEP
			} finally {
				if (locked)
					queueLock.ExitReadLock ();
			}
#endif
			return root.Data;
		}
		
		void BubbleDown (Node item)
		{
			if (item == null || (item.Left == null && item.Right == null))
				return;

			if (item.Left == null)
				SwapBubbleDown (item, item.Right);
			else if (item.Right == null)
				SwapBubbleDown (item, item.Left);
			else {
				if (item.Left.Data.ExpiresAt < item.Right.Data.ExpiresAt)
					SwapBubbleDown (item, item.Left);
				else
					SwapBubbleDown (item, item.Right);
			}
		}

		void SwapBubbleDown (Node item, Node otherItem)
		{
			if (otherItem.Data.ExpiresAt < item.Data.ExpiresAt) {
				item.Data = otherItem.SwapData (item.Data);
				BubbleDown (otherItem);
			}
		}
		
		void BubbleUp (Node item)
		{
			if (item == null || item.Data == null)
				return;
			
			Node parent = item.Parent;
			if (parent == null)
				return;
			
			if (item.Data.ExpiresAt > parent.Data.ExpiresAt)
				return;

			item.Data = parent.SwapData (item.Data);
			
			BubbleUp (parent);
		}
		
		public string GetDotScript ()
		{
			StringBuilder sb = new StringBuilder ();

			sb.Append ("graph CacheItemPriorityQueue {\n");
			sb.Append ("\tnode [color=lightblue, style=filled];\n");
			if (root != null) {
				if (root.Left == null && root.Right == null)
					sb.AppendFormat ("\t{0};", root.Data.ExpiresAt);
				else
					TraverseTree (sb, root);
			}
			sb.Append ("}\n");

			return sb.ToString ();
		}

		void TraverseTree (StringBuilder sb, Node root)
		{
			if (root.Left != null) {
				sb.AppendFormat ("\t{0} -- {1};\n", root.Data.ExpiresAt, root.Left.Data.ExpiresAt);
				TraverseTree (sb, root.Left);
			}

			if (root.Right != null) {
				sb.AppendFormat ("\t{0} -- {1};\n", root.Data.ExpiresAt, root.Right.Data.ExpiresAt);
				TraverseTree (sb, root.Right);
			}
		}
	}
}