mcs/class/System/System.Text.RegularExpressions/cache.cs

   1 //\r
   2 // assembly:    System\r
   3 // namespace:   System.Text.RegularExpressions\r
   4 // file:        cache.cs\r
   5 //\r
   6 // author:      Dan Lewis (dlewis@gmx.co.uk)\r
   7 //              (c) 2002\r
   8 \r
   9 //\r
  10 // Permission is hereby granted, free of charge, to any person obtaining\r
  11 // a copy of this software and associated documentation files (the\r
  12 // "Software"), to deal in the Software without restriction, including\r
  13 // without limitation the rights to use, copy, modify, merge, publish,\r
  14 // distribute, sublicense, and/or sell copies of the Software, and to\r
  15 // permit persons to whom the Software is furnished to do so, subject to\r
  16 // the following conditions:\r
  17 // \r
  18 // The above copyright notice and this permission notice shall be\r
  19 // included in all copies or substantial portions of the Software.\r
  20 // \r
  21 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,\r
  22 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF\r
  23 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND\r
  24 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE\r
  25 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION\r
  26 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION\r
  27 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.\r
  28 //\r
  29 \r
  30 using System;\r
  31 using System.Collections;\r
  32 \r
  33 namespace System.Text.RegularExpressions {\r
  34 \r
  35         class FactoryCache {\r
  36                 public FactoryCache (int capacity) {\r
  37                         this.capacity = capacity;\r
  38                         this.factories = new Hashtable (capacity);\r
  39                         this.mru_list = new MRUList ();\r
  40                 }\r
  41 \r
  42                 public void Add (string pattern, RegexOptions options, IMachineFactory factory) {\r
  43                         lock (this) {\r
  44                                 Key k = new Key (pattern, options);\r
  45                                 Cleanup ();\r
  46                                 factories[k] = factory;\r
  47                                 mru_list.Use (k);\r
  48                         }\r
  49                 }\r
  50 \r
  51                 // lock must be held by the caller\r
  52                 void Cleanup ()\r
  53                 {\r
  54                         while (factories.Count >= capacity && capacity > 0) {\r
  55                                 object victim = mru_list.Evict ();\r
  56                                 if (victim != null)\r
  57                                         factories.Remove ((Key) victim);\r
  58                         }\r
  59                 }\r
  60 \r
  61                 public IMachineFactory Lookup (string pattern, RegexOptions options) {\r
  62                         lock (this) {\r
  63                                 Key k = new Key (pattern, options);\r
  64                                 if (factories.Contains (k)) {\r
  65                                         mru_list.Use (k);\r
  66                                         return (IMachineFactory)factories[k];\r
  67                                 }\r
  68                         }\r
  69 \r
  70                         return null;\r
  71                 }\r
  72 \r
  73                 public int Capacity {\r
  74                         get { return capacity; }\r
  75                         set {\r
  76                                 // < 0 check done in the caller (Regex.CacheSize)\r
  77                                 lock (this) {\r
  78                                         capacity = value;\r
  79                                         Cleanup ();\r
  80                                 }\r
  81                         }\r
  82                 }\r
  83 \r
  84                 private int capacity;\r
  85                 private Hashtable factories;\r
  86                 private MRUList mru_list;\r
  87 \r
  88                 class Key {\r
  89                         public string pattern;\r
  90                         public RegexOptions options;\r
  91 \r
  92                         public Key (string pattern, RegexOptions options) {\r
  93                                 this.pattern = pattern;\r
  94                                 this.options = options;\r
  95                         }\r
  96                         \r
  97                         public override int GetHashCode () {\r
  98                                 return pattern.GetHashCode () ^ (int)options;\r
  99                         }\r
 100 \r
 101                         public override bool Equals (object o) {\r
 102                                 if (o == null || !(o is Key))\r
 103                                         return false;\r
 104 \r
 105                                 Key k = (Key)o;\r
 106                                 return options == k.options && pattern.Equals (k.pattern);\r
 107                         }\r
 108 \r
 109                         public override string ToString () {\r
 110                                 return "('" + pattern + "', [" + options + "])";\r
 111                         }\r
 112                 }\r
 113         }\r
 114 \r
 115         class MRUList {\r
 116                 public MRUList () {\r
 117                         head = tail = null;\r
 118                 }\r
 119 \r
 120                 public void Use (object o) {\r
 121                         Node node;\r
 122 \r
 123                         if (head == null) {\r
 124                                 node = new Node (o);\r
 125                                 head = tail = node;\r
 126                                 return;\r
 127                         }\r
 128 \r
 129                         node = head;\r
 130                         while (node != null && !o.Equals (node.value))\r
 131                                 node = node.previous;\r
 132 \r
 133                         if (node == null)\r
 134                                 node = new Node (o);\r
 135                         else {\r
 136                                 if (node == head)\r
 137                                         return;\r
 138 \r
 139                                 if (node == tail)\r
 140                                         tail = node.next;\r
 141                                 else\r
 142                                         node.previous.next = node.next;\r
 143 \r
 144                                 node.next.previous = node.previous;\r
 145                         }\r
 146 \r
 147                         head.next = node;\r
 148                         node.previous = head;\r
 149                         node.next = null;\r
 150                         head = node;\r
 151                 }\r
 152 \r
 153                 public object Evict () {\r
 154                         if (tail == null)\r
 155                                 return null;\r
 156 \r
 157                         object o = tail.value;\r
 158                         tail = tail.next;\r
 159 \r
 160                         if (tail == null)\r
 161                                 head = null;\r
 162                         else\r
 163                                 tail.previous = null;\r
 164 \r
 165                         return o;\r
 166                 }\r
 167 \r
 168                 private Node head, tail;\r
 169 \r
 170                 private class Node {\r
 171                         public object value;\r
 172                         public Node previous, next;\r
 173 \r
 174                         public Node (object value) {\r
 175                                 this.value = value;\r
 176                         }\r
 177                 }\r
 178         }\r
 179 }\r