//
-// System.Web.Caching.CacheItem
-//
// Author(s):
// Marek Habersack <mhabersack@novell.com>
//
-// (C) 2009 Novell, Inc (http://novell.com)
+// (C) 2009-2010 Novell, Inc (http://novell.com)
//
//
// Permission is hereby granted, free of charge, to any person obtaining
// WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
//
using System;
+using System.Collections.Generic;
+using System.IO;
using System.Text;
+using System.Threading;
+using System.Xml;
namespace System.Web.Caching
{
- sealed class CacheItemPriorityQueue
+ sealed partial class CacheItemPriorityQueue
{
- sealed class Node
- {
- public CacheItem Data;
+ const int INITIAL_HEAP_SIZE = 32;
+ const int HEAP_RESIZE_THRESHOLD = 8192;
- 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;
- }
+ CacheItem[] heap;
+ int heapSize = 0;
+ int heapCount = 0;
+ ReaderWriterLockSlim queueLock;
- public Node (CacheItem data)
- {
- Data = data;
- }
+ public int Count {
+ get { return heapCount; }
}
-
- Node root;
- Node lastAdded;
- Node firstParent;
- Node lastParent;
- public void Enqueue (CacheItem item)
+ public int Size {
+ get { return heapSize; }
+ }
+
+ public CacheItemPriorityQueue ()
{
- if (item == null)
- return;
+ queueLock = new ReaderWriterLockSlim ();
+ InitDebugMode ();
+ }
- Node node = new Node (item);
- if (root == null) {
- root = lastAdded = lastParent = firstParent = node;
- return;
+ CacheItem[] GetHeapWithGrow ()
+ {
+ if (heap == null) {
+ heap = new CacheItem [INITIAL_HEAP_SIZE];
+ heapSize = INITIAL_HEAP_SIZE;
+ heapCount = 0;
+ return heap;
}
- if (lastParent.Left != null && lastParent.Right != null) {
- lastParent = lastParent.Next;
- if (lastParent == null) {
- lastParent = firstParent = firstParent.Left;
- lastAdded = null;
- }
+ if (heapCount >= heapSize) {
+ heapSize <<= 1;
+ Array.Resize <CacheItem> (ref heap, heapSize);
}
- 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);
+ return heap;
}
- public CacheItem Dequeue ()
+ CacheItem[] GetHeapWithShrink ()
{
- if (root == null)
+ if (heap == null)
return null;
- CacheItem ret;
- if (root.Left == null && root.Right == null) {
- ret = root.Data;
- root = null;
- if (ret.Disabled)
- return null;
-
- return ret;
- }
+ if (heapSize > HEAP_RESIZE_THRESHOLD) {
+ int halfTheSize = heapSize >> 1;
- 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 (heapCount < halfTheSize)
+ Array.Resize <CacheItem> (ref heap, halfTheSize + (heapCount / 3));
+ }
- return ret;
- }
-
- public CacheItem Peek ()
- {
- if (root == null)
- return null;
-
- return root.Data;
+ return heap;
}
- void BubbleDown (Node item)
+ public void Enqueue (CacheItem item)
{
- if (item == null || (item.Left == null && item.Right == null))
+ if (item == 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);
+ bool locked = false;
+ CacheItem[] heap;
+
+ try {
+ queueLock.EnterWriteLock ();
+ locked = true;
+ heap = GetHeapWithGrow ();
+ heap [heapCount++] = item;
+ BubbleUp (heap);
+
+ AddSequenceEntry (item, EDSequenceEntryType.Enqueue);
+ } finally {
+ if (locked)
+ queueLock.ExitWriteLock ();
}
}
- void SwapBubbleDown (Node item, Node otherItem)
+ public CacheItem Dequeue ()
{
- if (otherItem.Data.ExpiresAt < item.Data.ExpiresAt) {
- item.Data = otherItem.SwapData (item.Data);
- BubbleDown (otherItem);
+ CacheItem ret = null;
+ CacheItem[] heap;
+ bool locked = false;
+ int index;
+
+ try {
+ queueLock.EnterWriteLock ();
+ locked = true;
+ heap = GetHeapWithShrink ();
+ if (heap == null || heapCount == 0)
+ return null;
+
+ ret = heap [0];
+ index = --heapCount;
+ heap [0] = heap [index];
+ heap [index] = null;
+
+ if (heapCount > 0)
+ BubbleDown (heap);
+
+ AddSequenceEntry (ret, EDSequenceEntryType.Dequeue);
+ return ret;
+ } finally {
+ if (locked)
+ queueLock.ExitWriteLock ();
}
}
-
- void BubbleUp (Node item)
+
+ public CacheItem Peek ()
{
- if (item == null || item.Data == null)
- return;
-
- Node parent = item.Parent;
- if (parent == null)
- return;
+ bool locked = false;
+ CacheItem ret;
- if (item.Data.ExpiresAt > parent.Data.ExpiresAt)
- return;
+ try {
+ queueLock.EnterReadLock ();
+ locked = true;
+ if (heap == null || heapCount == 0)
+ return null;
- item.Data = parent.SwapData (item.Data);
-
- BubbleUp (parent);
+ ret = heap [0];
+ AddSequenceEntry (ret, EDSequenceEntryType.Peek);
+
+ return ret;
+ } finally {
+ if (locked)
+ queueLock.ExitReadLock ();
+ }
}
- public string GetDotScript ()
+ void BubbleDown (CacheItem[] heap)
{
- 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);
+ int index = 0;
+ int left = 1;
+ int right = 2;
+ CacheItem item = heap [0];
+ int selected = (right < heapCount && heap [right].ExpiresAt < heap [left].ExpiresAt) ? 2 : 1;
+
+ while (selected < heapCount && heap [selected].ExpiresAt < item.ExpiresAt) {
+ heap [index] = heap [selected];
+ index = selected;
+ left = (index << 1) + 1;
+ right = left + 1;
+ selected = right < heapCount && heap [right].ExpiresAt < heap [left].ExpiresAt ? right : left;
}
- sb.Append ("}\n");
-
- return sb.ToString ();
+ heap [index] = item;
}
-
- void TraverseTree (StringBuilder sb, Node root)
+
+ void BubbleUp (CacheItem[] heap)
{
- if (root.Left != null) {
- sb.AppendFormat ("\t{0} -- {1};\n", root.Data.ExpiresAt, root.Left.Data.ExpiresAt);
- TraverseTree (sb, root.Left);
+ int index, parentIndex;
+ CacheItem parent, item;
+
+ if (heapCount <= 1)
+ return;
+
+ index = heapCount - 1;
+ parentIndex = (index - 1) >> 1;
+
+ item = heap [index];
+ while (index > 0) {
+ parent = heap [parentIndex];
+ if (heap [index].ExpiresAt >= parent.ExpiresAt)
+ break;
+
+ heap [index] = parent;
+ index = parentIndex;
+ parentIndex = (index - 1) >> 1;
}
- if (root.Right != null) {
- sb.AppendFormat ("\t{0} -- {1};\n", root.Data.ExpiresAt, root.Right.Data.ExpiresAt);
- TraverseTree (sb, root.Right);
- }
+ heap [index] = item;
}
}
}
projects / mono.git / blobdiff