mcs/class/corlib/System.Runtime.CompilerServices/ConditionalWeakTable.cs

   1 //
   2 // ConditionalWeakTable.cs
   3 //
   4 // Author:
   5 //   Rodrigo Kumpera (rkumpera@novell.com)
   6 //
   7 // Copyright (C) 2010 Novell, Inc (http://www.novell.com)
   8 //
   9 // Permission is hereby granted, free of charge, to any person obtaining
  10 // a copy of this software and associated documentation files (the
  11 // "Software"), to deal in the Software without restriction, including
  12 // without limitation the rights to use, copy, modify, merge, publish,
  13 // distribute, sublicense, and/or sell copies of the Software, and to
  14 // permit persons to whom the Software is furnished to do so, subject to
  15 // the following conditions:
  16 //
  17 // The above copyright notice and this permission notice shall be
  18 // included in all copies or substantial portions of the Software.
  19 //
  20 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  21 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  22 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  23 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  24 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  25 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  26 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  27 //
  28
  29 using System;
  30 using System.Collections;
  31 using System.Collections.Generic;
  32
  33 namespace System.Runtime.CompilerServices
  34 {
  35         internal struct Ephemeron
  36         {
  37                 internal object key;
  38                 internal object value;
  39         }
  40
  41         /*
  42         TODO:
  43                 The runtime need to inform the table about how many entries were expired.
  44                 Compact the table when there are too many tombstones.
  45                 Rehash to a smaller size when there are too few entries.
  46                 Change rehash condition check to use non-fp code.
  47                 Look into using quatratic probing/double hashing to reduce clustering problems.
  48                 Make reads and non-expanding writes (add/remove) lock free.
  49         */
  50         public sealed class ConditionalWeakTable<TKey, TValue>
  51                 where TKey : class
  52                 where TValue : class
  53         {
  54                 const int INITIAL_SIZE = 13;
  55                 const float LOAD_FACTOR = 0.7f;
  56
  57                 Ephemeron[] data;
  58                 object _lock = new object ();
  59                 int size;
  60
  61                 public delegate TValue CreateValueCallback (TKey key);
  62
  63                 public ConditionalWeakTable ()
  64                 {
  65                         data = new Ephemeron [INITIAL_SIZE];
  66                         GC.register_ephemeron_array (data);
  67                 }
  68
  69                 ~ConditionalWeakTable ()
  70                 {
  71                 }
  72
  73                 /*LOCKING: _lock must be held*/
  74                 void Rehash () {
  75                         uint newSize = (uint)HashHelpers.GetPrime ((data.Length << 1) | 1);
  76                         //Console.WriteLine ("--- resizing from {0} to {1}", data.Length, newSize);
  77
  78                         Ephemeron[] tmp = new Ephemeron [newSize];
  79                         GC.register_ephemeron_array (tmp);
  80                         size = 0;
  81
  82                         for (int i = 0; i < data.Length; ++i) {
  83                                 object key = data[i].key;
  84                                 object value = data[i].value;
  85                                 if (key == null || key == GC.EPHEMERON_TOMBSTONE)
  86                                         continue;
  87
  88                                 int len = tmp.Length;
  89                                 int idx, initial_idx;
  90                                 int free_slot = -1;
  91
  92                                 idx = initial_idx = (RuntimeHelpers.GetHashCode (key) & int.MaxValue) % len;
  93
  94                                 do {
  95                                         object k = tmp [idx].key;
  96
  97                                         //keys might be GC'd during Rehash
  98                                         if (k == null || k == GC.EPHEMERON_TOMBSTONE) {
  99                                                 free_slot = idx;
 100                                                 break;
 101                                         }
 102
 103                                         if (++idx == len) //Wrap around
 104                                                 idx = 0;
 105                                 } while (idx != initial_idx);
 106
 107                                 tmp [free_slot].key = key;
 108                                 tmp [free_slot].value = value;
 109                                 ++size;
 110                         }
 111                         data = tmp;
 112                 }
 113
 114
 115                 public void Add (TKey key, TValue value)
 116                 {
 117                         if (key == default (TKey))
 118                                 throw new ArgumentNullException ("Null key", "key");
 119
 120                         lock (_lock) {
 121                                 if (size >= data.Length * LOAD_FACTOR)
 122                                         Rehash ();
 123
 124                                 int len = data.Length;
 125                                 int idx,initial_idx;
 126                                 int free_slot = -1;
 127
 128                                 idx = initial_idx = (RuntimeHelpers.GetHashCode (key) & int.MaxValue) % len;
 129                                 do {
 130                                         object k = data [idx].key;
 131
 132                                         if (k == null) {
 133                                                 if (free_slot == -1)
 134                                                         free_slot = idx;
 135                                                 break;
 136                                         } else if (k == GC.EPHEMERON_TOMBSTONE && free_slot == -1) { //Add requires us to check for dupes :(
 137                                                 free_slot = idx;
 138                                         } else if (k == key) {
 139                                                 throw new ArgumentException ("Key already in the list", "key");
 140                                         }
 141
 142                                         if (++idx == len) //Wrap around
 143                                                 idx = 0;
 144                                 } while (idx != initial_idx);
 145
 146                                 data [free_slot].key = key;
 147                                 data [free_slot].value = value;
 148                                 ++size;
 149                         }
 150                 }
 151
 152                 public bool Remove (TKey key)
 153                 {
 154                         if (key == default (TKey))
 155                                 throw new ArgumentNullException ("Null key", "key");
 156
 157                         lock (_lock) {
 158                                 int len = data.Length;
 159                                 int idx, initial_idx;
 160                                 idx = initial_idx = (RuntimeHelpers.GetHashCode (key) & int.MaxValue) % len;
 161                                 do {
 162                                         object k = data[idx].key;
 163                                         if (k == key) {
 164                                                 data [idx].key = GC.EPHEMERON_TOMBSTONE;
 165                                                 data [idx].value = null;
 166                                                 --size;
 167                                                 return true;
 168                                         }
 169                                         if (k == null)
 170                                                 break;
 171                                         if (++idx == len) //Wrap around
 172                                                 idx = 0;
 173                                 } while (idx != initial_idx);
 174                         }
 175                         return false;
 176                 }
 177
 178                 public bool TryGetValue (TKey key, out TValue value)
 179                 {
 180                         if (key == null)
 181                                 throw new ArgumentNullException ("Null key", "key");
 182
 183                         value = default (TValue);
 184                         lock (_lock) {
 185                                 int len = data.Length;
 186                                 int idx, initial_idx;
 187                                 idx = initial_idx = (RuntimeHelpers.GetHashCode (key) & int.MaxValue) % len;
 188
 189                                 do {
 190                                         object k = data [idx].key;
 191                                         if (k == key) {
 192                                                 value = (TValue)data [idx].value;
 193                                                 return true;
 194                                         }
 195                                         if (k == null)
 196                                                 break;
 197                                         if (++idx == len) //Wrap around
 198                                                 idx = 0;
 199                                 } while (idx != initial_idx);
 200                         }
 201                         return false;
 202                 }
 203
 204                 public TValue GetOrCreateValue (TKey key)
 205                 {
 206                         return GetValue (key, k => Activator.CreateInstance<TValue> ());
 207                 }
 208
 209                 public TValue GetValue (TKey key, CreateValueCallback createValueCallback)
 210                 {
 211                         if (createValueCallback == null)
 212                                 throw new ArgumentNullException ("Null create delegate", "createValueCallback");
 213
 214                         TValue res;
 215
 216                         lock (_lock) {
 217                                 if (TryGetValue (key, out res))
 218                                         return res;
 219
 220                                 res = createValueCallback (key);
 221                                 Add (key, res);
 222                         }
 223
 224                         return res;
 225                 }
 226
 227                 // extracted from ../../../../external/referencesource/mscorlib/system/runtime/compilerservices/
 228                 internal ICollection<TKey> Keys
 229                 {
 230                         [System.Security.SecuritySafeCritical]
 231                         get
 232                         {
 233                                 List<TKey> list = new List<TKey>(data.Length);
 234                                 lock (_lock)
 235                                 {
 236                                         for (int i = 0; i < data.Length; ++i)
 237                                         {
 238                                                 TKey key = (TKey) data [i].key;
 239                                                 if (key != null)
 240                                                         list.Add (key);
 241                                         }
 242                                 }
 243                                 return list;
 244                         }
 245                 }
 246         }
 247 }