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

   1 //
   2 // Author(s):
   3 //  Marek Habersack <mhabersack@novell.com>
   4 //
   5 // (C) 2009-2010 Novell, Inc (http://novell.com)
   6 //
   7 //
   8 // Permission is hereby granted, free of charge, to any person obtaining
   9 // a copy of this software and associated documentation files (the
  10 // "Software"), to deal in the Software without restriction, including
  11 // without limitation the rights to use, copy, modify, merge, publish,
  12 // distribute, sublicense, and/or sell copies of the Software, and to
  13 // permit persons to whom the Software is furnished to do so, subject to
  14 // the following conditions:
  15 //
  16 // The above copyright notice and this permission notice shall be
  17 // included in all copies or substantial portions of the Software.
  18 //
  19 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  20 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  21 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  22 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  23 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  24 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  25 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  26 //
  27 using System;
  28 using System.Collections.Generic;
  29 using System.IO;
  30 using System.Text;
  31 using System.Threading;
  32 using System.Xml;
  33
  34 namespace System.Web.Caching
  35 {
  36         sealed partial class CacheItemPriorityQueue
  37         {
  38                 const int INITIAL_HEAP_SIZE = 32;
  39                 const int HEAP_RESIZE_THRESHOLD = 8192;
  40
  41                 CacheItem[] heap;
  42                 int heapSize = 0;
  43                 int heapCount = 0;
  44
  45                 // See comment for the cacheLock field at top of System.Web.Caching/Cache.cs
  46                 ReaderWriterLockSlim queueLock;
  47
  48                 public int Count {
  49                         get { return heapCount; }
  50                 }
  51
  52                 public int Size {
  53                         get { return heapSize; }
  54                 }
  55
  56                 public CacheItemPriorityQueue ()
  57                 {
  58                         queueLock = new ReaderWriterLockSlim ();
  59                         InitDebugMode ();
  60                 }
  61
  62                 CacheItem[] GetHeapWithGrow ()
  63                 {
  64                         if (heap == null) {
  65                                 heap = new CacheItem [INITIAL_HEAP_SIZE];
  66                                 heapSize = INITIAL_HEAP_SIZE;
  67                                 heapCount = 0;
  68                                 return heap;
  69                         }
  70
  71                         if (heapCount >= heapSize) {
  72                                 heapSize <<= 1;
  73                                 Array.Resize <CacheItem> (ref heap, heapSize);
  74                         }
  75
  76                         return heap;
  77                 }
  78
  79                 CacheItem[] GetHeapWithShrink ()
  80                 {
  81                         if (heap == null)
  82                                 return null;
  83
  84                         if (heapSize > HEAP_RESIZE_THRESHOLD) {
  85                                 int halfTheSize = heapSize >> 1;
  86
  87                                 if (heapCount < halfTheSize)
  88                                         Array.Resize <CacheItem> (ref heap, halfTheSize + (heapCount / 3));
  89                         }
  90
  91                         return heap;
  92                 }
  93
  94                 public void Enqueue (CacheItem item)
  95                 {
  96                         if (item == null)
  97                                 return;
  98
  99                         CacheItem[] heap;
 100
 101                         try {
 102                                 queueLock.EnterWriteLock ();
 103                                 heap = GetHeapWithGrow ();
 104                                 heap [heapCount++] = item;
 105                                 BubbleUp (heap);
 106
 107                                 AddSequenceEntry (item, EDSequenceEntryType.Enqueue);
 108                         } finally {
 109                                 // See comment at the top of the file, above queueLock declaration
 110                                 queueLock.ExitWriteLock ();
 111                         }
 112                 }
 113
 114                 public CacheItem Dequeue ()
 115                 {
 116                         CacheItem ret = null;
 117                         CacheItem[] heap;
 118                         int index;
 119
 120                         try {
 121                                 queueLock.EnterWriteLock ();
 122                                 heap = GetHeapWithShrink ();
 123                                 if (heap == null || heapCount == 0)
 124                                         return null;
 125
 126                                 ret = heap [0];
 127                                 index = --heapCount;
 128                                 heap [0] = heap [index];
 129                                 heap [index] = null;
 130
 131                                 if (heapCount > 0)
 132                                         BubbleDown (heap);
 133
 134                                 AddSequenceEntry (ret, EDSequenceEntryType.Dequeue);
 135                                 return ret;
 136                         } finally {
 137                                 // See comment at the top of the file, above queueLock declaration
 138                                 queueLock.ExitWriteLock ();
 139                         }
 140                 }
 141
 142                 public CacheItem Peek ()
 143                 {
 144                         CacheItem ret;
 145
 146                         try {
 147                                 queueLock.EnterReadLock ();
 148                                 if (heap == null || heapCount == 0)
 149                                         return null;
 150
 151                                 ret = heap [0];
 152                                 AddSequenceEntry (ret, EDSequenceEntryType.Peek);
 153
 154                                 return ret;
 155                         } finally {
 156                                 // See comment at the top of the file, above queueLock declaration
 157                                 queueLock.ExitReadLock ();
 158                         }
 159                 }
 160
 161                 void BubbleDown (CacheItem[] heap)
 162                 {
 163                         int index = 0;
 164                         int left = 1;
 165                         int right = 2;
 166                         CacheItem item = heap [0];
 167                         int selected = (right < heapCount && heap [right].ExpiresAt < heap [left].ExpiresAt) ? 2 : 1;
 168
 169                         while (selected < heapCount && heap [selected].ExpiresAt < item.ExpiresAt) {
 170                                 heap [index] = heap [selected];
 171                                 index = selected;
 172                                 left = (index << 1) + 1;
 173                                 right = left + 1;
 174                                 selected = right < heapCount && heap [right].ExpiresAt < heap [left].ExpiresAt ? right : left;
 175                         }
 176                         heap [index] = item;
 177                 }
 178
 179                 void BubbleUp (CacheItem[] heap)
 180                 {
 181                         int index, parentIndex;
 182                         CacheItem parent, item;
 183
 184                         if (heapCount <= 1)
 185                                 return;
 186
 187                         index = heapCount - 1;
 188                         parentIndex = (index - 1) >> 1;
 189
 190                         item = heap [index];
 191                         while (index > 0) {
 192                                 parent = heap [parentIndex];
 193                                 if (heap [index].ExpiresAt >= parent.ExpiresAt)
 194                                         break;
 195
 196                                 heap [index] = parent;
 197                                 index = parentIndex;
 198                                 parentIndex = (index - 1) >> 1;
 199                         }
 200
 201                         heap [index] = item;
 202                 }
 203         }
 204 }