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

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