Creating a weak dictionary in .NET
Tags: dotnet, csharp
Published: 2022-11-10 04:14:15

I once found myself in need of a dictionary for temporarily holding references to some objects. This dictionary was to hold weak references to its values so that said values would become eligible for garbage collection once they were no longer needed.

Such a `WeakDictionary` would be useful when:

- you need a temporary handle to objects having a known key, and
- your code isn't aware of when these objects fall out of use (i.e. you can't remove the entries explicitly).

The most obvious solution to this scenario would be to use a `Dictionary<KeyType, WeakReference>` object. The [WeakReference](https://learn.microsoft.com/en-us/dotnet/api/system.weakreference?view=net-6.0) will ensure that the dictionary doesn't contribute to the reference count of the object being referenced, allowing the object to be reclaimed by garbage collection even if it still has an entry in the dictionary.

However, if our code isn't aware of when an entry can be safely removed, dictionary entries will accumulate over time. We would like for the dictionary to automatically remove any "stale" entries.

In the spirit of [test-driven development](https://en.wikipedia.org/wiki/Test-driven_development) here's an NUnit test that shows how we would expect the `WeakDictionary` to behave.

_Due to the way the garbage collector is implemented in .NET Core, there are a few hoops we need to jump through in order to ensure the test works. See this [StackOverflow answer](https://stackoverflow.com/a/68836653/359765). In particular, compiler optimizations need to be switched on in the test project, and the debugger must not be attached._

{% gist https://gist.github.com/bhaeussermann/e649dc300069359ae8e4654a4041586d %}

While searching for a solution, I quickly came across [this StackOverflow post](https://stackoverflow.com/questions/2784291/good-implementation-of-weak-dictionary-in-net). Whereas there were a lot of proposed answers, none of them were really what I was looking for. Each answer either:

- implemented a dictionary with weak references to the _keys_ as opposed to the _values_, or
- relied on an explicit "purge" operation that needed to be called from time to time in order to clean up old references. I was looking for an implementation that would remove the entries of garbage collected objects immediately.

Thankfully, though, the answers that were there provided me with the necessary ingredients that enabled me to create a dictionary that would work the intended way.

A key ingredient is the [ConditionalWeakTable](https://learn.microsoft.com/en-us/dotnet/api/system.runtime.compilerservices.conditionalweaktable-2?view=net-6.0). It is a dictionary-like data structure that holds weak references to its keys and removes an entry when the key is garbage collected. This is exactly what we need, except we need that behavior on the _value_ as opposed to the _key_.

Using this `ConditionalWeakTable` internally is a good start to our implementation of the `WeakDictionary` as it may enable us to automatically remove dictionary entries when a value gets garbage collected: just add _values_ of the `WeakDictionary` as _keys_ to the `ConditionalWeakTable` and use it to properly maintain the entries in a separate dictionary.

{% gist https://gist.github.com/bhaeussermann/feaf2fec0aee076674fa9d124aba9463 %}

But how do we become aware of when an entry is removed from the `conditionalWeakTable` in order to remove the corresponding entry from the `internalDictionary`?

Think about what happens when a key object of the `WeakDictionary` is garbage collected:

- The corresponding entry from `conditionalWeakTable` is removed.
- This causes the reference count of the corresponding _value_ in the `conditionalWeakTable` (typed as `object`) to be decremented, causing it to be garbage collected as well (provided there are no other references to it).

Together with the fact that when an object is garbage collected, its finalizer (historically known as a destructor) will be invoked, this provides us with a way to act on this event by using a class such as the following:

{% gist https://gist.github.com/bhaeussermann/bd30b69ee87e779df58294866287223e %}

We make this class be the _value_ type of `conditionalWeakTable` and bring everything together in our class' `Add()` method as follows:

{% gist https://gist.github.com/bhaeussermann/68a4ade1f4761654bfd8d45cc267da9f %}

This way when a value object is garbage collected, it will immediately be removed from `internalDictionary`.

All of the remaining methods of the `IDictionary<>` interface are implemented to simply relay the method call to `internalDictionary`.

We run the test and, sure enough, it passes!

This gives us a useful data structure to use when we need key-based access to objects whose life-time we don't control.

The complete implementation is available in the [GitHub repo](https://github.com/bhaeussermann/weak-dictionary).
The library is available as a [NuGet package](https://www.nuget.org/packages/BernhardHaus.Collections.WeakDictionary).