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

   1 //
   2 // System.Web.Caching.CacheItem
   3 //
   4 // Author(s):
   5 //  Marek Habersack <mhabersack@novell.com>
   6 //
   7 // (C) 2009 Novell, Inc (http://novell.com)
   8 //
   9 //
  10 // Permission is hereby granted, free of charge, to any person obtaining
  11 // a copy of this software and associated documentation files (the
  12 // "Software"), to deal in the Software without restriction, including
  13 // without limitation the rights to use, copy, modify, merge, publish,
  14 // distribute, sublicense, and/or sell copies of the Software, and to
  15 // permit persons to whom the Software is furnished to do so, subject to
  16 // the following conditions:
  17 //
  18 // The above copyright notice and this permission notice shall be
  19 // included in all copies or substantial portions of the Software.
  20 //
  21 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  22 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  23 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  24 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  25 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  26 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  27 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  28 //
  29 using System;
  30 using System.Text;
  31
  32 namespace System.Web.Caching
  33 {
  34         sealed class CacheItemPriorityQueue
  35         {
  36                 sealed class Node
  37                 {
  38                         public CacheItem Data;
  39
  40                         public Node Left;
  41                         public Node Right;
  42                         public Node Parent;
  43                         public Node Next;
  44                         public Node Prev;
  45
  46                         public CacheItem SwapData (CacheItem newData)
  47                         {
  48                                 CacheItem ret = Data;
  49                                 Data = newData;
  50
  51                                 return ret;
  52                         }
  53
  54                         public Node (CacheItem data)
  55                         {
  56                                 Data = data;
  57                         }
  58                 }
  59
  60                 Node root;
  61                 Node lastAdded;
  62                 Node firstParent;
  63                 Node lastParent;
  64
  65                 public void Enqueue (CacheItem item)
  66                 {
  67                         if (item == null)
  68                                 return;
  69
  70                         Node node = new Node (item);
  71                         if (root == null) {
  72                                 root = lastAdded = lastParent = firstParent = node;
  73                                 return;
  74                         }
  75
  76                         if (lastParent.Left != null && lastParent.Right != null) {
  77                                 lastParent = lastParent.Next;
  78                                 if (lastParent == null) {
  79                                         lastParent = firstParent = firstParent.Left;
  80                                         lastAdded = null;
  81                                 }
  82                         }
  83
  84                         node.Parent = lastParent;
  85                         if (lastParent.Left == null)
  86                                 lastParent.Left = node;
  87                         else
  88                                 lastParent.Right = node;
  89
  90                         if (lastAdded != null) {
  91                                 lastAdded.Next = node;
  92                                 node.Prev = lastAdded;
  93                         }
  94
  95                         lastAdded = node;
  96                         BubbleUp (node);
  97                 }
  98
  99                 public CacheItem Dequeue ()
 100                 {
 101                         Console.WriteLine ("{0}.Dequeue ()", this);
 102                         if (root == null)
 103                                 return null;
 104
 105                         CacheItem ret;
 106                         if (root.Left == null && root.Right == null) {
 107                                 ret = root.Data;
 108                                 root = null;
 109                                 if (ret.Disabled) {
 110                                         Console.WriteLine ("\troot disabled, returning null");
 111                                         return null;
 112                                 }
 113
 114                                 return ret;
 115                         }
 116
 117                         ret = root.Data;
 118                         do {
 119                                 Node last = lastAdded;
 120                                 if (last == null)
 121                                         return null;
 122
 123                                 if (last.Prev == null) {
 124                                         Node parent = last.Parent;
 125                                         while (true) {
 126                                                 if (parent.Next == null)
 127                                                         break;
 128                                                 parent = parent.Next;
 129                                         }
 130                                         lastAdded = parent;
 131                                 } else {
 132                                         lastAdded = last.Prev;
 133                                         lastAdded.Next = null;
 134                                 }
 135
 136                                 if (last.Parent.Left == last)
 137                                         last.Parent.Left = null;
 138                                 else
 139                                         last.Parent.Right = null;
 140
 141                                 root.Data = last.Data;
 142                                 BubbleDown (root);
 143
 144                                 if (ret.Disabled)
 145                                         Console.WriteLine ("\titem {0} disabled, ignoring", ret.ExpiresAt);
 146                         } while (ret.Disabled);
 147
 148                         return ret;
 149                 }
 150
 151                 public CacheItem Peek ()
 152                 {
 153                         if (root == null)
 154                                 return null;
 155
 156                         return root.Data;
 157                 }
 158
 159                 void BubbleDown (Node item)
 160                 {
 161                         if (item == null || (item.Left == null && item.Right == null))
 162                                 return;
 163
 164                         if (item.Left == null)
 165                                 SwapBubbleDown (item, item.Right);
 166                         else if (item.Right == null)
 167                                 SwapBubbleDown (item, item.Left);
 168                         else {
 169                                 if (item.Left.Data.ExpiresAt < item.Right.Data.ExpiresAt)
 170                                         SwapBubbleDown (item, item.Left);
 171                                 else
 172                                         SwapBubbleDown (item, item.Right);
 173                         }
 174                 }
 175
 176                 void SwapBubbleDown (Node item, Node otherItem)
 177                 {
 178                         if (otherItem.Data.ExpiresAt < item.Data.ExpiresAt) {
 179                                 item.Data = otherItem.SwapData (item.Data);
 180                                 BubbleDown (otherItem);
 181                         }
 182                 }
 183
 184                 void BubbleUp (Node item)
 185                 {
 186                         if (item == null || item.Data == null)
 187                                 return;
 188
 189                         Node parent = item.Parent;
 190                         if (parent == null)
 191                                 return;
 192
 193                         if (item.Data.ExpiresAt > parent.Data.ExpiresAt)
 194                                 return;
 195
 196                         item.Data = parent.SwapData (item.Data);
 197
 198                         BubbleUp (parent);
 199                 }
 200
 201                 public string GetDotScript ()
 202                 {
 203                         StringBuilder sb = new StringBuilder ();
 204
 205                         sb.Append ("graph CacheItemPriorityQueue {\n");
 206                         sb.Append ("\tnode [color=lightblue, style=filled];\n");
 207                         if (root != null) {
 208                                 if (root.Left == null && root.Right == null)
 209                                         sb.AppendFormat ("\t{0};", root.Data.ExpiresAt);
 210                                 else
 211                                         TraverseTree (sb, root);
 212                         }
 213                         sb.Append ("}\n");
 214
 215                         return sb.ToString ();
 216                 }
 217
 218                 void TraverseTree (StringBuilder sb, Node root)
 219                 {
 220                         if (root.Left != null) {
 221                                 sb.AppendFormat ("\t{0} -- {1};\n", root.Data.ExpiresAt, root.Left.Data.ExpiresAt);
 222                                 TraverseTree (sb, root.Left);
 223                         }
 224
 225                         if (root.Right != null) {
 226                                 sb.AppendFormat ("\t{0} -- {1};\n", root.Data.ExpiresAt, root.Right.Data.ExpiresAt);
 227                                 TraverseTree (sb, root.Right);
 228                         }
 229                 }
 230         }
 231 }