Good implementation of weak dictionary in .Net
Solution 1
ConditionalWeakTable Class uses weak keys and automatically removes the key/value entry as soon as no other references to a key exist outside the table.
Solution 2
You'll need to write it yourself. It should be relatively straight forward, implementing the IDictionary<T,T> interface and then storing the actual values as WeakReferences<T>. You can then check the values on add/select using TryGetTarget to see if they're still alive.
public class WeakDictionary <TKey,TValue> : IDictionary<TKey,TValue>
where TValue : class
{
private readonly Dictionary<TKey,WeakReference<TValue>> innerDictionary = new Dictionary<TKey,WeakReference<TValue>>();
public TValue Index[ TKey key ]
{
get
{
// Use .TryGetTarget instead of .IsAlive and .Target
if (this.innerDictionary.TryGetValue(key, out WeakReference<TValue> wf) && wf.TryGetTarget(out TValue value))
{
return value;
}
return null;
}
}
private void Cull()
{
var deadKeys = this.innerDictionary.Where(kvp => kvp.Value.IsAlive).Select(kvp => kvp.Key).ToList();
foreach (var key in deadKeys)
{
_ = this.innerDictionary.TryRemove(key);
}
}
}
Solution 3
One problem with simply holding a dictionary of WeakReference objects is that there's no way, short of enumerating the entire dictionary, of removing from the Dictionary any WeakReference objects whose targets go out of scope.
It would be helpful if a WeakReference could include a delegate which would be invoked when the primary target went out of scope. As far as I know, there's no way to do that. If you don't mind adding another field and a little code to the objects you're storing within your "weak dictionary", I'd suggest creating what I call a "Finasposer" object, whose sole field is a MethodInvoker; when disposed, the MethodInvoker should be nulled out; the finalizer should Interlocked.Exchange() the MethodInvoker to null and--if its old value was non-null--invoke it. The object to be written in the dictionary should create a new Finasposer object, with a delegate that will cause the key to be removed from the dictionary when convenient.
Note that the neither the finalizer nor any delegate invoked thereby should never directly manipulate the dictionary, nor do anything that would require acquiring a lock. If the Finasposer holds a delegate, that delegate itself is guaranteed to be valid when Finalize executes, but the object attached to the delegate, and any objects referenced thereby, may be in unexpected states. It should be safe, however, for the Finasposer-called method to add to a linked list a reference to the object that went out of scope. The Dictionary's Add, Remove, and other methods could poll the linked list to see if any of the WeakReferences therein had died and needed to be cleaned out.
Solution 4
This will work without the performance problems of the other solutions.
(It doesn't rely on a "shrink" method being called upon every request in order to manually get rid of dead objects. And these "shrink" methods would have to loop through every item on every call. I do have a "shrink" method, but it is only called when the items would be enumerated anyway.)
The key to the problem is to use a "holder" object as a value in the ConditionalWeakTable, so that when the key gets dropped, the holder's finalizer will trigger, which removes the key from the "active list" of keys.
I tested this and it works.
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
namespace Util
{
public class WeakDictionary<TKey, TValue> : IDictionary<TKey, TValue>, IDisposable
where TKey : class
where TValue : class
{
private readonly object locker = new object();
//private readonly HashSet<WeakReference> weakKeySet = new HashSet<WeakReference>(new ObjectReferenceEqualityComparer<WeakReference>());
private ConditionalWeakTable<TKey, WeakKeyHolder> keyHolderMap = new ConditionalWeakTable<TKey, WeakKeyHolder>();
private Dictionary<WeakReference, TValue> valueMap = new Dictionary<WeakReference, TValue>(new ObjectReferenceEqualityComparer<WeakReference>());
private class WeakKeyHolder
{
private WeakDictionary<TKey, TValue> outer;
private WeakReference keyRef;
public WeakKeyHolder(WeakDictionary<TKey, TValue> outer, TKey key)
{
this.outer = outer;
this.WeakRef = new WeakReference(key);
}
public WeakReference WeakRef { get; private set; }
~WeakKeyHolder()
{
this.outer?.onKeyDrop(this.WeakRef); // Nullable operator used just in case this.outer gets set to null by GC before this finalizer runs. But I haven't had this happen.
}
}
private void onKeyDrop(WeakReference weakKeyRef)
{
lock(this.locker)
{
if (!this.bAlive)
return;
//this.weakKeySet.Remove(weakKeyRef);
this.valueMap.Remove(weakKeyRef);
}
}
// The reason for this is in case (for some reason which I have never seen) the finalizer trigger doesn't work
// There is not much performance penalty with this, since this is only called in cases when we would be enumerating the inner collections anyway.
private void manualShrink()
{
var keysToRemove = this.valueMap.Keys.Where(k => !k.IsAlive).ToList();
foreach (var key in keysToRemove)
valueMap.Remove(key);
}
private Dictionary<TKey, TValue> currentDictionary
{
get
{
lock(this.locker)
{
this.manualShrink();
return this.valueMap.ToDictionary(p => (TKey) p.Key.Target, p => p.Value);
}
}
}
public TValue this[TKey key]
{
get
{
if (this.TryGetValue(key, out var val))
return val;
throw new KeyNotFoundException();
}
set
{
this.set(key, value, isUpdateOkay: true);
}
}
private bool set(TKey key, TValue val, bool isUpdateOkay)
{
lock (this.locker)
{
if (this.keyHolderMap.TryGetValue(key, out var weakKeyHolder))
{
if (!isUpdateOkay)
return false;
this.valueMap[weakKeyHolder.WeakRef] = val;
return true;
}
weakKeyHolder = new WeakKeyHolder(this, key);
this.keyHolderMap.Add(key, weakKeyHolder);
//this.weakKeySet.Add(weakKeyHolder.WeakRef);
this.valueMap.Add(weakKeyHolder.WeakRef, val);
return true;
}
}
public ICollection<TKey> Keys
{
get
{
lock(this.locker)
{
this.manualShrink();
return this.valueMap.Keys.Select(k => (TKey) k.Target).ToList();
}
}
}
public ICollection<TValue> Values
{
get
{
lock (this.locker)
{
this.manualShrink();
return this.valueMap.Select(p => p.Value).ToList();
}
}
}
public int Count
{
get
{
lock (this.locker)
{
this.manualShrink();
return this.valueMap.Count;
}
}
}
public bool IsReadOnly => false;
public void Add(TKey key, TValue value)
{
if (!this.set(key, value, isUpdateOkay: false))
throw new ArgumentException("Key already exists");
}
public void Add(KeyValuePair<TKey, TValue> item)
{
this.Add(item.Key, item.Value);
}
public void Clear()
{
lock(this.locker)
{
this.keyHolderMap = new ConditionalWeakTable<TKey, WeakKeyHolder>();
this.valueMap.Clear();
}
}
public bool Contains(KeyValuePair<TKey, TValue> item)
{
WeakKeyHolder weakKeyHolder = null;
object curVal = null;
lock (this.locker)
{
if (!this.keyHolderMap.TryGetValue(item.Key, out weakKeyHolder))
return false;
curVal = weakKeyHolder.WeakRef.Target;
}
return (curVal?.Equals(item.Value) == true);
}
public bool ContainsKey(TKey key)
{
lock (this.locker)
{
return this.keyHolderMap.TryGetValue(key, out var weakKeyHolder);
}
}
public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
{
((IDictionary<TKey, TValue>) this.currentDictionary).CopyTo(array, arrayIndex);
}
public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
{
return this.currentDictionary.GetEnumerator();
}
public bool Remove(TKey key)
{
lock (this.locker)
{
if (!this.keyHolderMap.TryGetValue(key, out var weakKeyHolder))
return false;
this.keyHolderMap.Remove(key);
this.valueMap.Remove(weakKeyHolder.WeakRef);
return true;
}
}
public bool Remove(KeyValuePair<TKey, TValue> item)
{
lock (this.locker)
{
if (!this.keyHolderMap.TryGetValue(item.Key, out var weakKeyHolder))
return false;
if (weakKeyHolder.WeakRef.Target?.Equals(item.Value) != true)
return false;
this.keyHolderMap.Remove(item.Key);
this.valueMap.Remove(weakKeyHolder.WeakRef);
return true;
}
}
public bool TryGetValue(TKey key, out TValue value)
{
lock (this.locker)
{
if (!this.keyHolderMap.TryGetValue(key, out var weakKeyHolder))
{
value = default(TValue);
return false;
}
value = this.valueMap[weakKeyHolder.WeakRef];
return true;
}
}
IEnumerator IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
private bool bAlive = true;
public void Dispose()
{
this.Dispose(true);
}
protected void Dispose(bool bManual)
{
if (bManual)
{
Monitor.Enter(this.locker);
if (!this.bAlive)
return;
}
try
{
this.keyHolderMap = null;
this.valueMap = null;
this.bAlive = false;
}
finally
{
if (bManual)
Monitor.Exit(this.locker);
}
}
~WeakDictionary()
{
this.Dispose(false);
}
}
public class ObjectReferenceEqualityComparer<T> : IEqualityComparer<T>
{
public static ObjectReferenceEqualityComparer<T> Default = new ObjectReferenceEqualityComparer<T>();
public bool Equals(T x, T y)
{
return ReferenceEquals(x, y);
}
public int GetHashCode(T obj)
{
return RuntimeHelpers.GetHashCode(obj);
}
}
public class ObjectReferenceEqualityComparer : ObjectReferenceEqualityComparer<object>
{
}
}
Solution 5
It is one thing to have WeakReferences to values, but I found that Dictionary keys can also be a source of memory leaks. Here is a bare bones implementation with WeakReference to keys:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Common.library.collections {
/// <summary>
/// THIS DICTIONARY WILL NOT "HANG ON" TO THE KEYS IT USES
/// IF THE KEY IS GARBAGE COLLECTED, THE VALUE WILL BE RELEASED TOO
/// </summary>
public class Dictionary_usingWeakKey<K, V> {
//MAP FROM HASH CODE TO LIST OF KEY/VALUE PAIRS
private Dictionary<int, List<Pair>> dic = new Dictionary<int, List<Pair>>();
public void Add(K key, V value) {
if (value==null){
this.Remove(key);
return;
}//endif
List<Pair> list = null;
dic.TryGetValue(key.GetHashCode(), out list);
if (list == null) {
list = new List<Pair>();
dic.Add(key.GetHashCode(), list);
}//endif
Boolean isDirty = false;
foreach(Pair p in list){
if (p.Key.Target == null) {
isDirty = true;
continue;
}//endif
if (p.Key.Target == (Object)key) {
p.Value = (Object)value;
if (isDirty) cleanList(list);
return;
}//endif
}//for
if (isDirty) cleanList(list);
Pair newP=new Pair();
newP.Key = new WeakReference(key);
newP.Value = value;
list.Add(newP);
}//method
public bool ContainsKey(K key) {
List<Pair> list = null;
dic.TryGetValue(key.GetHashCode(), out list);
if (list == null) return false;
Boolean isDirty = false;
foreach (Pair p in list) {
if (p.Key.Target == null) {
isDirty = true;
continue;
}//endif
if (p.Key.Target == (Object)key) {
if (isDirty) cleanList(list);
return true;
}//endif
}//for
if (isDirty) cleanList(list);
return false;
}//method
private void cleanList(List<Pair> list) {
var temp = (from Pair p in list where p.Key.Target != null select p);
list.Clear();
list.AddRange(temp);
}//method
public bool Remove(K key) {
List<Pair> list = null;
dic.TryGetValue(key.GetHashCode(), out list);
if (list == null) return true;
foreach (Pair p in list) {
if (p.Key.Target == (Object)key) {
p.Value = null;
break;
}//endif
}//for
cleanList(list);
return true;
}//method
public V this[K key] {
get {
List<Pair> list = null;
dic.TryGetValue(key.GetHashCode(), out list);
if (list == null) return default(V);
Boolean isDirty = false;
foreach (Pair p in list) {
if (p.Key.Target == null) {
isDirty = true;
continue;
}//endif
if (p.Key.Target == (Object)key) {
if (isDirty) cleanList(list);
return (V)p.Value;
}//endif
}//for
if (isDirty) cleanList(list);
return default(V);
}
set {
this.Add(key, value);
}
}
public void Add(KeyValuePair<K, V> item) {
throw new NotImplementedException();
}
public void Clear() {
dic.Clear();
}
public bool Contains(KeyValuePair<K, V> item) {
throw new NotImplementedException();
}
public void CopyTo(KeyValuePair<K, V>[] array, int arrayIndex) {
throw new NotImplementedException();
}
public int Count {
get {
throw new NotImplementedException();
//return dic.Count();
}
}
public bool IsReadOnly {
get { return false; }
}
public bool Remove(KeyValuePair<K, V> item) {
throw new NotImplementedException();
}
public IEnumerator<KeyValuePair<K, V>> GetEnumerator() {
throw new NotImplementedException();
//return dic.GetEnumerator();
}
//System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
// return ((System.Collections.IEnumerable)dic).GetEnumerator();
//}
}//class
public class Pair{
public WeakReference Key;
public Object Value;
}//method
}
Comments
-
Konstantin Spirin almost 2 years
Where can I find good implementation of
IDictionarywhich uses weak references inside?Dictionary should be holding only weak references to values and eventually clean up itself of dead references.
Or should I just write it myself?