mcs/class/System.Runtime.Caching/System.Runtime.Caching/MemoryCacheEntryPriorityQueue.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
  33 namespace System.Runtime.Caching
  34 {
  35         sealed partial class MemoryCacheEntryPriorityQueue
  36         {
  37                 const int INITIAL_HEAP_SIZE = 32;
  38                 const int HEAP_RESIZE_THRESHOLD = 8192;
  39
  40                 MemoryCacheEntry[] heap;
  41                 int heapSize = 0;
  42                 int heapCount = 0;
  43                 ReaderWriterLockSlim queueLock;
  44
  45                 public int Count {
  46                         get { return heapCount; }
  47                 }
  48
  49                 public int Size {
  50                         get { return heapSize; }
  51                 }
  52
  53                 public MemoryCacheEntryPriorityQueue ()
  54                 {
  55                         queueLock = new ReaderWriterLockSlim ();
  56                 }
  57
  58                 MemoryCacheEntry[] GetHeapWithGrow ()
  59                 {
  60                         if (heap == null) {
  61                                 heap = new MemoryCacheEntry [INITIAL_HEAP_SIZE];
  62                                 heapSize = INITIAL_HEAP_SIZE;
  63                                 heapCount = 0;
  64                                 return heap;
  65                         }
  66
  67                         if (heapCount >= heapSize) {
  68                                 heapSize <<= 1;
  69                                 Array.Resize <MemoryCacheEntry> (ref heap, heapSize);
  70                         }
  71
  72                         return heap;
  73                 }
  74
  75                 MemoryCacheEntry[] GetHeapWithShrink ()
  76                 {
  77                         if (heap == null)
  78                                 return null;
  79
  80                         if (heapSize > HEAP_RESIZE_THRESHOLD) {
  81                                 int halfTheSize = heapSize >> 1;
  82
  83                                 if (heapCount < halfTheSize)
  84                                         Array.Resize <MemoryCacheEntry> (ref heap, halfTheSize + (heapCount / 3));
  85                         }
  86
  87                         return heap;
  88                 }
  89
  90                 public void Enqueue (MemoryCacheEntry item)
  91                 {
  92                         if (item == null)
  93                                 return;
  94
  95                         bool locked = false;
  96                         MemoryCacheEntry[] heap;
  97
  98                         try {
  99                                 queueLock.EnterWriteLock ();
 100                                 locked = true;
 101                                 heap = GetHeapWithGrow ();
 102                                 heap [heapCount++] = item;
 103                                 BubbleUp (heap);
 104                         } finally {
 105                                 if (locked)
 106                                         queueLock.ExitWriteLock ();
 107                         }
 108                 }
 109
 110                 public MemoryCacheEntry Dequeue ()
 111                 {
 112                         MemoryCacheEntry ret = null;
 113                         MemoryCacheEntry[] heap;
 114                         bool locked = false;
 115                         int index;
 116
 117                         try {
 118                                 queueLock.EnterWriteLock ();
 119                                 locked = true;
 120                                 heap = GetHeapWithShrink ();
 121                                 if (heap == null || heapCount == 0)
 122                                         return null;
 123
 124                                 ret = heap [0];
 125                                 index = --heapCount;
 126                                 heap [0] = heap [index];
 127                                 heap [index] = null;
 128
 129                                 if (heapCount > 0)
 130                                         BubbleDown (heap);
 131
 132                                 return ret;
 133                         } finally {
 134                                 if (locked)
 135                                         queueLock.ExitWriteLock ();
 136                         }
 137                 }
 138
 139                 public MemoryCacheEntry Peek ()
 140                 {
 141                         bool locked = false;
 142
 143                         try {
 144                                 queueLock.EnterReadLock ();
 145                                 locked = true;
 146                                 if (heap == null || heapCount == 0)
 147                                         return null;
 148
 149                                 return heap [0];
 150                         } finally {
 151                                 if (locked)
 152                                         queueLock.ExitReadLock ();
 153                         }
 154                 }
 155
 156                 void BubbleDown (MemoryCacheEntry[] heap)
 157                 {
 158                         int index = 0;
 159                         int left = 1;
 160                         int right = 2;
 161                         MemoryCacheEntry item = heap [0];
 162                         int selected = (right < heapCount && heap [right].ExpiresAt < heap [left].ExpiresAt) ? 2 : 1;
 163
 164                         while (selected < heapCount && heap [selected].ExpiresAt < item.ExpiresAt) {
 165                                 heap [index] = heap [selected];
 166                                 index = selected;
 167                                 left = (index << 1) + 1;
 168                                 right = left + 1;
 169                                 selected = right < heapCount && heap [right].ExpiresAt < heap [left].ExpiresAt ? right : left;
 170                         }
 171                         heap [index] = item;
 172                 }
 173
 174                 void BubbleUp (MemoryCacheEntry[] heap)
 175                 {
 176                         int index, parentIndex;
 177                         MemoryCacheEntry parent, item;
 178
 179                         if (heapCount <= 1)
 180                                 return;
 181
 182                         index = heapCount - 1;
 183                         parentIndex = (index - 1) >> 1;
 184
 185                         item = heap [index];
 186                         while (index > 0) {
 187                                 parent = heap [parentIndex];
 188                                 if (heap [index].ExpiresAt >= parent.ExpiresAt)
 189                                         break;
 190
 191                                 heap [index] = parent;
 192                                 index = parentIndex;
 193                                 parentIndex = (index - 1) >> 1;
 194                         }
 195
 196                         heap [index] = item;
 197                 }
 198         }
 199 }