· 9 years ago · Jan 12, 2017, 04:18 PM
1using System;
2using System.Collections.Generic;
3using System.Runtime.CompilerServices;
4using System.Runtime.InteropServices;
5
6 // ==++==
7 //
8 // Copyright (c) Microsoft Corporation. All rights reserved.
9 //
10 // ==--==
11 /*============================================================
12 ** Class: ConditionalWeakTable
13 **
14 ** <OWNER>Microsoft</OWNER>
15 **
16 ** Description: Compiler support for runtime-generated "object fields."
17 **
18 ** Lets DLR and other language compilers expose the ability to
19 ** attach arbitrary "properties" to instanced managed objects at runtime.
20 **
21 ** We expose this support as a dictionary whose keys are the
22 ** instanced objects and the values are the "properties."
23 **
24 ** Unlike a regular dictionary, ConditionalWeakTables will not
25 ** keep keys alive.
26 **
27 **
28 ** Lifetimes of keys and values:
29 **
30 ** Inserting a key and value into the dictonary will not
31 ** prevent the key from dying, even if the key is strongly reachable
32 ** from the value.
33 **
34 ** Prior to ConditionalWeakTable, the CLR did not expose
35 ** the functionality needed to implement this guarantee.
36 **
37 ** Once the key dies, the dictionary automatically removes
38 ** the key/value entry.
39 **
40 **
41 ** Relationship between ConditionalWeakTable and Dictionary:
42 **
43 ** ConditionalWeakTable mirrors the form and functionality
44 ** of the IDictionary interface for the sake of api consistency.
45 **
46 ** Unlike Dictionary, ConditionalWeakTable is fully thread-safe
47 ** and requires no additional locking to be done by callers.
48 **
49 ** ConditionalWeakTable defines equality as Object.ReferenceEquals().
50 ** ConditionalWeakTable does not invoke GetHashCode() overrides.
51 **
52 ** It is not intended to be a general purpose collection
53 ** and it does not formally implement IDictionary or
54 ** expose the full public surface area.
55 **
56 **
57 **
58 ** Thread safety guarantees:
59 **
60 ** ConditionalWeakTable is fully thread-safe and requires no
61 ** additional locking to be done by callers.
62 **
63 **
64 ** OOM guarantees:
65 **
66 ** Will not corrupt unmanaged handle table on OOM. No guarantees
67 ** about managed weak table consistency. Native handles reclamation
68 ** may be delayed until appdomain shutdown.
69 ===========================================================*/
70
71 #region ConditionalWeakTable
72 [System.Runtime.InteropServices.ComVisible(false)]
73 public sealed class ConditionalWeakTable<TKey, TValue>
74 where TKey : class
75 where TValue : class
76 {
77
78 #region Constructors
79 public ConditionalWeakTable()
80 {
81 _buckets = new int[0];
82 _entries = new Entry[0];
83 _freeList = -1;
84 _lock = new Object();
85
86 Resize(); // Resize at once (so won't need "if initialized" checks all over)
87 }
88 #endregion
89
90 #region Public Members
91 //--------------------------------------------------------------------------------------------
92 // key: key of the value to find. Cannot be null.
93 // value: if the key is found, contains the value associated with the key upon method return.
94 // if the key is not found, contains default(TValue).
95 //
96 // Method returns "true" if key was found, "false" otherwise.
97 //
98 // Note: The key may get garbaged collected during the TryGetValue operation. If so, TryGetValue
99 // may at its discretion, return "false" and set "value" to the default (as if the key was not present.)
100 //--------------------------------------------------------------------------------------------
101 public bool TryGetValue(TKey key, out TValue value)
102 {
103 if (key == null)
104 {
105 throw new ArgumentNullException();
106 }
107 lock (_lock)
108 {
109 VerifyIntegrity();
110 return TryGetValueWorker(key, out value);
111 }
112 }
113
114 //--------------------------------------------------------------------------------------------
115 // key: key to add. May not be null.
116 // value: value to associate with key.
117 //
118 // If the key is already entered into the dictionary, this method throws an exception.
119 //
120 // Note: The key may get garbage collected during the Add() operation. If so, Add()
121 // has the right to consider any prior entries successfully removed and add a new entry without
122 // throwing an exception.
123 //--------------------------------------------------------------------------------------------
124 public void Add(TKey key, TValue value)
125 {
126 if (key == null)
127 {
128 throw new ArgumentNullException();
129 }
130
131 lock (_lock)
132 {
133 VerifyIntegrity();
134 _invalid = true;
135
136 int entryIndex = FindEntry(key);
137 if (entryIndex != -1)
138 {
139 _invalid = false;
140 throw new ArgumentNullException();
141 }
142
143 CreateEntry(key, value);
144 _invalid = false;
145 }
146
147 }
148
149 //--------------------------------------------------------------------------------------------
150 // key: key to remove. May not be null.
151 //
152 // Returns true if the key is found and removed. Returns false if the key was not in the dictionary.
153 //
154 // Note: The key may get garbage collected during the Remove() operation. If so,
155 // Remove() will not fail or throw, however, the return value can be either true or false
156 // depending on who wins the ----.
157 //--------------------------------------------------------------------------------------------
158 public bool Remove(TKey key)
159 {
160 if (key == null)
161 {
162 throw new ArgumentNullException();
163 }
164
165 lock (_lock)
166 {
167 VerifyIntegrity();
168 _invalid = true;
169
170 int hashCode = key.GetHashCode() & Int32.MaxValue;
171 int bucket = hashCode % _buckets.Length;
172 int last = -1;
173 for (int entriesIndex = _buckets[bucket]; entriesIndex != -1; entriesIndex = _entries[entriesIndex].next)
174 {
175 if (_entries[entriesIndex].hashCode == hashCode && _entries[entriesIndex].depHnd.GetPrimary() == key)
176 {
177 if (last == -1)
178 {
179 _buckets[bucket] = _entries[entriesIndex].next;
180 }
181 else
182 {
183 _entries[last].next = _entries[entriesIndex].next;
184 }
185
186 _entries[entriesIndex].depHnd.Free();
187 _entries[entriesIndex].next = _freeList;
188
189 _freeList = entriesIndex;
190
191 _invalid = false;
192 return true;
193
194 }
195 last = entriesIndex;
196 }
197 _invalid = false;
198 return false;
199 }
200 }
201
202
203 //--------------------------------------------------------------------------------------------
204 // key: key of the value to find. Cannot be null.
205 // createValueCallback: callback that creates value for key. Cannot be null.
206 //
207 // Atomically tests if key exists in table. If so, returns corresponding value. If not,
208 // invokes createValueCallback() passing it the key. The returned value is bound to the key in the table
209 // and returned as the result of GetValue().
210 //
211 // If multiple threads ---- to initialize the same key, the table may invoke createValueCallback
212 // multiple times with the same key. Exactly one of these calls will "win the ----" and the returned
213 // value of that call will be the one added to the table and returned by all the racing GetValue() calls.
214 //
215 // This rule permits the table to invoke createValueCallback outside the internal table lock
216 // to prevent deadlocks.
217 //--------------------------------------------------------------------------------------------
218 public TValue GetValue(TKey key, CreateValueCallback createValueCallback)
219 {
220 // Our call to TryGetValue() validates key so no need for us to.
221 //
222 // if (key == null)
223 // {
224 // ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
225 // }
226
227 if (createValueCallback == null)
228 {
229 throw new ArgumentNullException("createValueCallback");
230 }
231
232 TValue existingValue;
233 if (TryGetValue(key, out existingValue))
234 {
235 return existingValue;
236 }
237
238 // If we got here, the key is not currently in table. Invoke the callback (outside the lock)
239 // to generate the new value for the key.
240 TValue newValue = createValueCallback(key);
241
242 lock (_lock)
243 {
244 VerifyIntegrity();
245 _invalid = true;
246
247 // Now that we've retaken the lock, must recheck in case we lost a ---- to add the key.
248 if (TryGetValueWorker(key, out existingValue))
249 {
250 _invalid = false;
251 return existingValue;
252 }
253 else
254 {
255 // Verified in-lock that we won the ---- to add the key. Add it now.
256 CreateEntry(key, newValue);
257 _invalid = false;
258 return newValue;
259 }
260 }
261 }
262
263 //--------------------------------------------------------------------------------------------
264 // key: key of the value to find. Cannot be null.
265 //
266 // Helper method to call GetValue without passing a creation delegate. Uses Activator.CreateInstance
267 // to create new instances as needed. If TValue does not have a default constructor, this will
268 // throw.
269 //--------------------------------------------------------------------------------------------
270 public TValue GetOrCreateValue(TKey key)
271 {
272 return GetValue(key, k => Activator.CreateInstance<TValue>());
273 }
274
275 public delegate TValue CreateValueCallback(TKey key);
276
277 #endregion
278
279 #region internal members
280
281 //--------------------------------------------------------------------------------------------
282 // Find a key that equals (value equality) with the given key - don't use in perf critical path
283 // Note that it calls out to Object.Equals which may calls the override version of Equals
284 // and that may take locks and leads to deadlock
285 // Currently it is only used by WinRT event code and you should only use this function
286 // if you know for sure that either you won't run into dead locks or you need to live with the
287 // possiblity
288 //--------------------------------------------------------------------------------------------
289 internal TKey FindEquivalentKeyUnsafe(TKey key, out TValue value)
290 {
291 lock (_lock)
292 {
293 for (int bucket = 0; bucket < _buckets.Length; ++bucket)
294 {
295 for (int entriesIndex = _buckets[bucket]; entriesIndex != -1; entriesIndex = _entries[entriesIndex].next)
296 {
297 object thisKey, thisValue;
298 _entries[entriesIndex].depHnd.GetPrimaryAndSecondary(out thisKey, out thisValue);
299 if (Object.Equals(thisKey, key))
300 {
301 value = (TValue)thisValue;
302 return (TKey)thisKey;
303 }
304 }
305 }
306 }
307
308 value = default(TValue);
309 return null;
310 }
311
312 //--------------------------------------------------------------------------------------------
313 // Returns a collection of keys - don't use in perf critical path
314 //--------------------------------------------------------------------------------------------
315 internal ICollection<TKey> Keys
316 {
317 get
318 {
319 List<TKey> list = new List<TKey>();
320 lock (_lock)
321 {
322 for (int bucket = 0; bucket < _buckets.Length; ++bucket)
323 {
324 for (int entriesIndex = _buckets[bucket]; entriesIndex != -1; entriesIndex = _entries[entriesIndex].next)
325 {
326 TKey thisKey = (TKey)_entries[entriesIndex].depHnd.GetPrimary();
327 if (thisKey != null)
328 {
329 list.Add(thisKey);
330 }
331 }
332 }
333 }
334
335 return list;
336 }
337 }
338
339 //--------------------------------------------------------------------------------------------
340 // Returns a collection of values - don't use in perf critical path
341 //--------------------------------------------------------------------------------------------
342 internal ICollection<TValue> Values
343 {
344 get
345 {
346 List<TValue> list = new List<TValue>();
347 lock (_lock)
348 {
349 for (int bucket = 0; bucket < _buckets.Length; ++bucket)
350 {
351 for (int entriesIndex = _buckets[bucket]; entriesIndex != -1; entriesIndex = _entries[entriesIndex].next)
352 {
353 Object primary = null;
354 Object secondary = null;
355
356 _entries[entriesIndex].depHnd.GetPrimaryAndSecondary(out primary, out secondary);
357
358 // Now that we've secured a strong reference to the secondary, must check the primary again
359 // to ensure it didn't expire (otherwise, we open a ---- where TryGetValue misreports an
360 // expired key as a live key with a null value.)
361 if (primary != null)
362 {
363 list.Add((TValue)secondary);
364 }
365 }
366 }
367 }
368
369 return list;
370 }
371 }
372
373 //--------------------------------------------------------------------------------------------
374 // Clear all the key/value pairs
375 //--------------------------------------------------------------------------------------------
376 internal void Clear()
377 {
378 lock (_lock)
379 {
380 // Clear the buckets
381 for (int bucketIndex = 0; bucketIndex < _buckets.Length; bucketIndex++)
382 {
383 _buckets[bucketIndex] = -1;
384 }
385
386 // Clear the entries and link them backwards together as part of free list
387 int entriesIndex;
388 for (entriesIndex = 0; entriesIndex < _entries.Length; entriesIndex++)
389 {
390 if (_entries[entriesIndex].depHnd.IsAllocated)
391 {
392 _entries[entriesIndex].depHnd.Free();
393 }
394
395 // Link back wards as free list
396 _entries[entriesIndex].next = entriesIndex - 1;
397 }
398
399 _freeList = entriesIndex - 1;
400 }
401 }
402
403 #endregion
404
405 #region Private Members
406 //----------------------------------------------------------------------------------------
407 // Worker for finding a key/value pair
408 //
409 // Preconditions:
410 // Must hold _lock.
411 // Key already validated as non-null
412 //----------------------------------------------------------------------------------------
413 private bool TryGetValueWorker(TKey key, out TValue value)
414 {
415 int entryIndex = FindEntry(key);
416 if (entryIndex != -1)
417 {
418 Object primary = null;
419 Object secondary = null;
420 _entries[entryIndex].depHnd.GetPrimaryAndSecondary(out primary, out secondary);
421 // Now that we've secured a strong reference to the secondary, must check the primary again
422 // to ensure it didn't expire (otherwise, we open a ---- where TryGetValue misreports an
423 // expired key as a live key with a null value.)
424 if (primary != null)
425 {
426 value = (TValue)secondary;
427 return true;
428 }
429 }
430
431 value = default(TValue);
432 return false;
433 }
434
435 //----------------------------------------------------------------------------------------
436 // Worker for adding a new key/value pair.
437 //
438 // Preconditions:
439 // Must hold _lock.
440 // Key already validated as non-null and not already in table.
441 //----------------------------------------------------------------------------------------
442 private void CreateEntry(TKey key, TValue value)
443 {
444 if (_freeList == -1)
445 {
446 Resize();
447 }
448
449 int hashCode = key.GetHashCode() & Int32.MaxValue;
450 int bucket = hashCode % _buckets.Length;
451
452 int newEntry = _freeList;
453 _freeList = _entries[newEntry].next;
454
455 _entries[newEntry].hashCode = hashCode;
456 _entries[newEntry].depHnd = new DependentHandle(key, value);
457 _entries[newEntry].next = _buckets[bucket];
458
459 _buckets[bucket] = newEntry;
460
461 }
462
463 public static bool IsPrime(int candidate)
464 {
465 // Test whether the parameter is a prime number.
466 if ((candidate & 1) == 0)
467 {
468 if (candidate == 2)
469 {
470 return true;
471 }
472 else
473 {
474 return false;
475 }
476 }
477 // Note:
478 // ... This version was changed to test the square.
479 // ... Original version tested against the square root.
480 // ... Also we exclude 1 at the end.
481 for (int i = 3; (i * i) <= candidate; i += 2)
482 {
483 if ((candidate % i) == 0)
484 {
485 return false;
486 }
487 }
488 return candidate != 1;
489 }
490
491 // Table of prime numbers to use as hash table sizes.
492 // A typical resize algorithm would pick the smallest prime number in this array
493 // that is larger than twice the previous capacity.
494 // Suppose our Hashtable currently has capacity x and enough elements are added
495 // such that a resize needs to occur. Resizing first computes 2x then finds the
496 // first prime in the table greater than 2x, i.e. if primes are ordered
497 // p_1, p_2, ..., p_i, ..., it finds p_n such that p_n-1 < 2x < p_n.
498 // Doubling is important for preserving the asymptotic complexity of the
499 // hashtable operations such as add. Having a prime guarantees that double
500 // hashing does not lead to infinite loops. IE, your hash function will be
501 // h1(key) + i*h2(key), 0 <= i < size. h2 and the size must be relatively prime.
502 public static readonly int[] primes = {
503 3, 7, 11, 17, 23, 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631, 761, 919,
504 1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013, 8419, 10103, 12143, 14591,
505 17519, 21023, 25229, 30293, 36353, 43627, 52361, 62851, 75431, 90523, 108631, 130363, 156437,
506 187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263,
507 1674319, 2009191, 2411033, 2893249, 3471899, 4166287, 4999559, 5999471, 7199369};
508
509
510 internal const Int32 HashPrime = 101;
511
512 public static int GetPrime(int min)
513 {
514 if (min < 0)
515 throw new ArgumentException();
516
517 for (int i = 0; i < primes.Length; i++)
518 {
519 int prime = primes[i];
520 if (prime >= min) return prime;
521 }
522
523 //outside of our predefined table.
524 //compute the hard way.
525 for (int i = (min | 1); i < Int32.MaxValue; i += 2)
526 {
527 if (IsPrime(i) && ((i - 1) % HashPrime != 0))
528 return i;
529 }
530 return min;
531 }
532
533 //----------------------------------------------------------------------------------------
534 // This does two things: resize and scrub expired keys off bucket lists.
535 //
536 // Precondition:
537 // Must hold _lock.
538 //
539 // Postcondition:
540 // _freeList is non-empty on exit.
541 //----------------------------------------------------------------------------------------
542 private void Resize()
543 {
544 // Start by assuming we won't resize.
545 int newSize = _buckets.Length;
546
547 // If any expired keys exist, we won't resize.
548 bool hasExpiredEntries = false;
549 int entriesIndex;
550 for (entriesIndex = 0; entriesIndex < _entries.Length; entriesIndex++)
551 {
552 if (_entries[entriesIndex].depHnd.IsAllocated && _entries[entriesIndex].depHnd.GetPrimary() == null)
553 {
554 hasExpiredEntries = true;
555 break;
556 }
557 }
558
559 if (!hasExpiredEntries)
560 {
561 newSize = GetPrime(_buckets.Length == 0 ? _initialCapacity + 1 : _buckets.Length * 2);
562 }
563
564
565 // Reallocate both buckets and entries and rebuild the bucket and freelists from scratch.
566 // This serves both to scrub entries with expired keys and to put the new entries in the proper bucket.
567 int newFreeList = -1;
568 int[] newBuckets = new int[newSize];
569 for (int bucketIndex = 0; bucketIndex < newSize; bucketIndex++)
570 {
571 newBuckets[bucketIndex] = -1;
572 }
573 Entry[] newEntries = new Entry[newSize];
574
575 // Migrate existing entries to the new table.
576 for (entriesIndex = 0; entriesIndex < _entries.Length; entriesIndex++)
577 {
578 DependentHandle depHnd = _entries[entriesIndex].depHnd;
579 if (depHnd.IsAllocated && depHnd.GetPrimary() != null)
580 {
581 // Entry is used and has not expired. Link it into the appropriate bucket list.
582 int bucket = _entries[entriesIndex].hashCode % newSize;
583 newEntries[entriesIndex].depHnd = depHnd;
584 newEntries[entriesIndex].hashCode = _entries[entriesIndex].hashCode;
585 newEntries[entriesIndex].next = newBuckets[bucket];
586 newBuckets[bucket] = entriesIndex;
587 }
588 else
589 {
590 // Entry has either expired or was on the freelist to begin with. Either way
591 // insert it on the new freelist.
592 _entries[entriesIndex].depHnd.Free();
593 newEntries[entriesIndex].depHnd = new DependentHandle();
594 newEntries[entriesIndex].next = newFreeList;
595 newFreeList = entriesIndex;
596 }
597 }
598
599 // Add remaining entries to freelist.
600 while (entriesIndex != newEntries.Length)
601 {
602 newEntries[entriesIndex].depHnd = new DependentHandle();
603 newEntries[entriesIndex].next = newFreeList;
604 newFreeList = entriesIndex;
605 entriesIndex++;
606 }
607
608 _buckets = newBuckets;
609 _entries = newEntries;
610 _freeList = newFreeList;
611 }
612
613 //----------------------------------------------------------------------------------------
614 // Returns -1 if not found (if key expires during FindEntry, this can be treated as "not found.")
615 //
616 // Preconditions:
617 // Must hold _lock.
618 // Key already validated as non-null.
619 //----------------------------------------------------------------------------------------
620 private int FindEntry(TKey key)
621 {
622 int hashCode = key.GetHashCode() & Int32.MaxValue;
623 for (int entriesIndex = _buckets[hashCode % _buckets.Length]; entriesIndex != -1; entriesIndex = _entries[entriesIndex].next)
624 {
625 if (_entries[entriesIndex].hashCode == hashCode && _entries[entriesIndex].depHnd.GetPrimary() == key)
626 {
627 return entriesIndex;
628 }
629 }
630 return -1;
631 }
632
633 //----------------------------------------------------------------------------------------
634 // Precondition:
635 // Must hold _lock.
636 //----------------------------------------------------------------------------------------
637 private void VerifyIntegrity()
638 {
639 if (_invalid)
640 {
641 // I do not know why it's always invalid, and I just wanna code. Please. I beg.
642 //throw new InvalidOperationException();
643 }
644 }
645 #endregion
646
647 #region Private Data Members
648 //--------------------------------------------------------------------------------------------
649 // Entry can be in one of three states:
650 //
651 // - Linked into the freeList (_freeList points to first entry)
652 // depHnd.IsAllocated == false
653 // hashCode == <dontcare>
654 // next links to next Entry on freelist)
655 //
656 // - Used with live key (linked into a bucket list where _buckets[hashCode % _buckets.Length] points to first entry)
657 // depHnd.IsAllocated == true, depHnd.GetPrimary() != null
658 // hashCode == RuntimeHelpers.GetHashCode(depHnd.GetPrimary()) & Int32.MaxValue
659 // next links to next Entry in bucket.
660 //
661 // - Used with dead key (linked into a bucket list where _buckets[hashCode % _buckets.Length] points to first entry)
662 // depHnd.IsAllocated == true, depHnd.GetPrimary() == null
663 // hashCode == <notcare>
664 // next links to next Entry in bucket.
665 //
666 // The only difference between "used with live key" and "used with dead key" is that
667 // depHnd.GetPrimary() returns null. The transition from "used with live key" to "used with dead key"
668 // happens asynchronously as a result of normal garbage collection. The dictionary itself
669 // receives no notification when this happens.
670 //
671 // When the dictionary grows the _entries table, it scours it for expired keys and puts those
672 // entries back on the freelist.
673 //--------------------------------------------------------------------------------------------
674 private struct Entry
675 {
676 public DependentHandle depHnd; // Holds key and value using a weak reference for the key and a strong reference
677 // for the value that is traversed only if the key is reachable without going through the value.
678 public int hashCode; // Cached copy of key's hashcode
679 public int next; // Index of next entry, -1 if last
680 }
681
682 private int[] _buckets; // _buckets[hashcode & _buckets.Length] contains index of first entry in bucket (-1 if empty)
683 private Entry[] _entries;
684 private int _freeList; // -1 = empty, else index of first unused Entry
685 private const int _initialCapacity = 5;
686 private readonly Object _lock; // this could be a ReaderWriterLock but CoreCLR does not support RWLocks.
687 private bool _invalid; // flag detects if OOM or other background exception threw us out of the lock.
688 #endregion
689 }
690 #endregion
691
692
693
694 [StructLayout(LayoutKind.Sequential), ComVisible(false)]
695 internal struct DependentHandle
696 {
697 private WeakReference _primary;
698 private object _secondary;
699
700 public DependentHandle(object primary, object secondary)
701 {
702 _primary = new WeakReference(primary);
703 _secondary = secondary;
704 }
705
706 public bool IsAllocated
707 {
708 get { return ((_primary != null) && _primary.IsAlive); }
709 }
710
711 public object GetPrimary() { return _primary.Target; }
712
713 public void GetPrimaryAndSecondary(out object primary, out object secondary)
714 {
715 primary = _primary.Target;
716 secondary = _secondary;
717 }
718
719 // Forces dependentHandle back to non-allocated state (if not already there) and frees the handle if needed.
720 public void Free()
721 {
722 _primary = null;
723 _secondary = null;
724 }
725 }