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 const float COMPACT_FACTOR = 0.5f; 59 const float EXPAND_FACTOR = 1.1f; 60 61 Ephemeron[] data; 62 object _lock = new object (); 63 int size; 64 CreateValueCallback(TKey key)65 public delegate TValue CreateValueCallback (TKey key); 66 ConditionalWeakTable()67 public ConditionalWeakTable () 68 { 69 data = new Ephemeron [INITIAL_SIZE]; 70 GC.register_ephemeron_array (data); 71 } 72 ~ConditionalWeakTable()73 ~ConditionalWeakTable () 74 { 75 } 76 RehashWithoutResize()77 private void RehashWithoutResize () 78 { 79 int len = data.Length; 80 81 for (int i = 0; i < len; i++) { 82 if (data [i].key == GC.EPHEMERON_TOMBSTONE) 83 data [i].key = null; 84 } 85 86 for (int i = 0; i < len; i++) { 87 object key = data [i].key; 88 if (key != null) { 89 int idx = (RuntimeHelpers.GetHashCode (key) & int.MaxValue) % len; 90 91 while (true) { 92 if (data [idx].key == null) { 93 // The object was not stored in its normal slot. Rehash 94 data [idx].key = key; 95 data [idx].value = data [i].value; 96 // At this point we have this Ephemeron entry duplicated in the array. Shouldn't 97 // be a problem. 98 data [i].key = null; 99 data [i].value = null; 100 break; 101 } else if (data [idx].key == key) { 102 /* We already have the key in the first available position, finished */ 103 break; 104 } 105 106 if (++idx == len) //Wrap around 107 idx = 0; 108 } 109 } 110 } 111 } 112 RecomputeSize()113 private void RecomputeSize () 114 { 115 size = 0; 116 for (int i = 0; i < data.Length; i++) { 117 if (data [i].key != null) 118 size++; 119 } 120 } 121 122 /*LOCKING: _lock must be held*/ Rehash()123 private void Rehash () 124 { 125 // Size doesn't track elements that die without being removed. Before attempting 126 // to rehash we traverse the array to see how many entries are left alive. We 127 // rehash the array into a new one which has a capacity relative to the number of 128 // live entries. 129 RecomputeSize (); 130 131 uint newLength = (uint)HashHelpers.GetPrime (((int)(size / LOAD_FACTOR) << 1) | 1); 132 133 if (newLength > data.Length * COMPACT_FACTOR && newLength < data.Length * EXPAND_FACTOR) { 134 /* Avoid unnecessary LOS allocations */ 135 RehashWithoutResize (); 136 return; 137 } 138 //Console.WriteLine ("--- resizing from {0} to {1}", data.Length, newLength); 139 140 Ephemeron[] tmp = new Ephemeron [newLength]; 141 GC.register_ephemeron_array (tmp); 142 size = 0; 143 144 for (int i = 0; i < data.Length; ++i) { 145 object key = data[i].key; 146 object value = data[i].value; 147 if (key == null || key == GC.EPHEMERON_TOMBSTONE) 148 continue; 149 150 int len = tmp.Length; 151 int idx, initial_idx; 152 int free_slot = -1; 153 154 idx = initial_idx = (RuntimeHelpers.GetHashCode (key) & int.MaxValue) % len; 155 156 do { 157 object k = tmp [idx].key; 158 159 //keys might be GC'd during Rehash 160 if (k == null || k == GC.EPHEMERON_TOMBSTONE) { 161 free_slot = idx; 162 break; 163 } 164 165 if (++idx == len) //Wrap around 166 idx = 0; 167 } while (idx != initial_idx); 168 169 tmp [free_slot].key = key; 170 tmp [free_slot].value = value; 171 ++size; 172 } 173 data = tmp; 174 } 175 176 Add(TKey key, TValue value)177 public void Add (TKey key, TValue value) 178 { 179 if (key == default (TKey)) 180 throw new ArgumentNullException ("Null key", "key"); 181 182 lock (_lock) { 183 if (size >= data.Length * LOAD_FACTOR) 184 Rehash (); 185 186 int len = data.Length; 187 int idx,initial_idx; 188 int free_slot = -1; 189 190 idx = initial_idx = (RuntimeHelpers.GetHashCode (key) & int.MaxValue) % len; 191 do { 192 object k = data [idx].key; 193 194 if (k == null) { 195 if (free_slot == -1) 196 free_slot = idx; 197 break; 198 } else if (k == GC.EPHEMERON_TOMBSTONE && free_slot == -1) { //Add requires us to check for dupes :( 199 free_slot = idx; 200 } else if (k == key) { 201 throw new ArgumentException ("Key already in the list", "key"); 202 } 203 204 if (++idx == len) //Wrap around 205 idx = 0; 206 } while (idx != initial_idx); 207 208 data [free_slot].key = key; 209 data [free_slot].value = value; 210 ++size; 211 } 212 } 213 Remove(TKey key)214 public bool Remove (TKey key) 215 { 216 if (key == default (TKey)) 217 throw new ArgumentNullException ("Null key", "key"); 218 219 lock (_lock) { 220 int len = data.Length; 221 int idx, initial_idx; 222 idx = initial_idx = (RuntimeHelpers.GetHashCode (key) & int.MaxValue) % len; 223 do { 224 object k = data[idx].key; 225 if (k == key) { 226 data [idx].key = GC.EPHEMERON_TOMBSTONE; 227 data [idx].value = null; 228 --size; 229 return true; 230 } 231 if (k == null) 232 break; 233 if (++idx == len) //Wrap around 234 idx = 0; 235 } while (idx != initial_idx); 236 } 237 return false; 238 } 239 TryGetValue(TKey key, out TValue value)240 public bool TryGetValue (TKey key, out TValue value) 241 { 242 if (key == null) 243 throw new ArgumentNullException ("Null key", "key"); 244 245 value = default (TValue); 246 lock (_lock) { 247 int len = data.Length; 248 int idx, initial_idx; 249 idx = initial_idx = (RuntimeHelpers.GetHashCode (key) & int.MaxValue) % len; 250 251 do { 252 object k = data [idx].key; 253 if (k == key) { 254 value = (TValue)data [idx].value; 255 return true; 256 } 257 if (k == null) 258 break; 259 if (++idx == len) //Wrap around 260 idx = 0; 261 } while (idx != initial_idx); 262 } 263 return false; 264 } 265 GetOrCreateValue(TKey key)266 public TValue GetOrCreateValue (TKey key) 267 { 268 return GetValue (key, k => Activator.CreateInstance<TValue> ()); 269 } 270 GetValue(TKey key, CreateValueCallback createValueCallback)271 public TValue GetValue (TKey key, CreateValueCallback createValueCallback) 272 { 273 if (createValueCallback == null) 274 throw new ArgumentNullException ("Null create delegate", "createValueCallback"); 275 276 TValue res; 277 278 lock (_lock) { 279 if (TryGetValue (key, out res)) 280 return res; 281 282 res = createValueCallback (key); 283 Add (key, res); 284 } 285 286 return res; 287 } 288 289 //-------------------------------------------------------------------------------------------- 290 // Find a key that equals (value equality) with the given key - don't use in perf critical path 291 // Note that it calls out to Object.Equals which may calls the override version of Equals 292 // and that may take locks and leads to deadlock 293 // Currently it is only used by WinRT event code and you should only use this function 294 // if you know for sure that either you won't run into dead locks or you need to live with the 295 // possiblity 296 //-------------------------------------------------------------------------------------------- 297 [System.Security.SecuritySafeCritical] 298 [FriendAccessAllowed] FindEquivalentKeyUnsafe(TKey key, out TValue value)299 internal TKey FindEquivalentKeyUnsafe(TKey key, out TValue value) 300 { 301 lock (_lock) 302 { 303 for (int i = 0; i < data.Length; ++i) 304 { 305 var item = data[i]; 306 if (Object.Equals(item.key, key)) 307 { 308 value = (TValue)item.value; 309 return (TKey)item.key; 310 } 311 } 312 } 313 314 value = default(TValue); 315 return null; 316 } 317 318 //-------------------------------------------------------------------------------------------- 319 // Clear all the key/value pairs 320 //-------------------------------------------------------------------------------------------- 321 [System.Security.SecuritySafeCritical] Clear()322 internal void Clear() 323 { 324 lock (_lock) 325 { 326 for (int i = 0; i < data.Length; i++) 327 { 328 data[i].key = GC.EPHEMERON_TOMBSTONE; 329 data[i].value = null; 330 } 331 332 size = 0; 333 } 334 } 335 336 // extracted from ../../../../external/referencesource/mscorlib/system/runtime/compilerservices/ 337 internal ICollection<TKey> Keys 338 { 339 [System.Security.SecuritySafeCritical] 340 get 341 { 342 var tombstone = GC.EPHEMERON_TOMBSTONE; 343 List<TKey> list = new List<TKey>(data.Length); 344 lock (_lock) 345 { 346 for (int i = 0; i < data.Length; ++i) 347 { 348 TKey key = (TKey) data [i].key; 349 if (key != null && key != tombstone) 350 list.Add (key); 351 } 352 } 353 return list; 354 } 355 } 356 357 internal ICollection<TValue> Values 358 { 359 [System.Security.SecuritySafeCritical] 360 get 361 { 362 var tombstone = GC.EPHEMERON_TOMBSTONE; 363 List<TValue> list = new List<TValue>(data.Length); 364 lock (_lock) 365 { 366 for (int i = 0; i < data.Length; ++i) 367 { 368 var item = data[i]; 369 if (item.key != null && item.key != tombstone) 370 list.Add((TValue)item.value); 371 } 372 } 373 374 return list; 375 } 376 } 377 } 378 } 379