8
\$\begingroup\$

Occasionally I have need for a collection of objects in which each object is referenced "weakly" (meaning the GC is allowed to collect it even when the object is in the collection). Traditionally, I would use a simple List<WeakReference<MyObject>>, occasionally "purging" any WeakReference whose target object had been garbage-collected (typically as the list was iterated or updated).

I've found that the List<WeakReference<MyObject>> pattern has two major downsides:

  1. The code to purge the expired WeakReference objects is duplicated in all the places that use this pattern. It would be more convenient if this purging was handled automatically by the collection itself.
  2. Every WeakReference is its own heap-allocated object. If you want to store thousands of weakly-referenced objects, then that's thousands of additional objects that get allocated on the heap.

One could also use ConditionalWeakTable, but that class doesn't support iteration, which is crucial for my purposes.

What follows is my attempt at creating a WeakCollection<T> class which addresses both of those issues. I'd really appreciate it if anyone could look over my implementation and point out anything I'm being stupid about or important details I'm missing. I also welcome any general code-review type advice.

Once particular piece of advice I'm looking for is how best to detect whether the collection is modified during enumeration, so that it can throw an exception.

A few key details about my WeakCollection<T> class:

  • The tracking and removal of dead objects is completely hidden to the application. From the application's perspective, once an object is garbage-collected, it is instantly gone from the collection.
  • Instead of using .NET's WeakReference<T> class to store each object, it allocates a GCHandle (which is a value type) for every object stored in the collection.
  • As the collection is updated or iterated, it automatically checks for any dead objects and removes their corresponding GCHandle values. The Remove, Contains, CopyTo, and GetEnumerator methods do this as they iterate. The Add method does this once the number of contained objects exceeds twice the number that existed after the last purge, or once the capacity of the internal List<GCHandle> object is filled. There's also a Purge method that can be called manually.
  • This is not, and is not intended to be, thread-safe.
  • I've put a GC.KeepAlive(this) call at the end of every method to prevent the finalizer from running while the method executes, but I'm not 100% sure it's required in all cases. (But can't hurt, right?)

/// <summary>
/// Stores a collection of weakly-referenced objects, allowing the objects
/// in this collection to be garbage-collected. Garbage-collected objects
/// will be immediately removed from the collection.
/// </summary>
public class WeakCollection<T> : ICollection<T>
    where T : class
{
    private readonly List<GCHandle> _handles;
    private readonly bool _trackResurrection;
    private int _countAfterLastPurge;

    /// <summary>
    /// Creates a new WeakCollection.
    /// </summary>
    /// <param name="capacity">The initial number of objects that the WeakCollection can hold before resizing.</param>
    /// <param name="trackResurrection">If true, the object continues to be tracked even after it is finalized.</param>
    public WeakCollection(int capacity = 8, bool trackResurrection = false)
    {
        if(capacity <= 0)
            throw new ArgumentOutOfRangeException(nameof(capacity));

        _handles = new List<GCHandle>(capacity);
        _trackResurrection = trackResurrection;
    }

    /// <summary>
    /// Frees the handles allocated for this WeakCollection.
    /// </summary>
    ~WeakCollection()
    {
        for(int i = 0; i < _handles.Count; i++)
            _handles[i].Free();
    }

    /// <summary>
    /// Returns the approximate number of objects stored in this WeakCollection.
    /// The will never be less than the actual number of living objects, but may
    /// be larger if some objects have been garbage-collected.
    /// </summary>
    /// <param name="purge">
    /// If true, any garbage-collected objects will be purged before returning a value.
    /// Even if this is true, this method may still return a higher-than-living value
    /// if any objects are garbage-collected while this method is executing.
    /// </param>
    public int GetCount(bool purge)
    {
        if(purge)
            Purge();

        int count = _handles.Count;
        GC.KeepAlive(this);
        return count;
    }

    /// <summary>
    /// Adds the specified object to this WeakCollection.
    /// </summary>
    /// <remarks>
    /// This will occasionally purge the tracking memory for any garbage-collected objects.
    /// </remarks>
    public void Add(T obj)
    {
        if(obj == null)
            throw new ArgumentNullException(nameof(obj));

        if(_handles.Count == _handles.Capacity || _handles.Count + 1 > _countAfterLastPurge * 2)
            Purge();

        GCHandleType handleType = _trackResurrection ? GCHandleType.WeakTrackResurrection : GCHandleType.Weak;
        GCHandle handle = GCHandle.Alloc(obj, handleType);
        _handles.Add(handle);

        GC.KeepAlive(this);
    }

    /// <summary>
    /// Removes one occurrence of the specified object from this WeakCollection.
    /// </summary>
    /// <returns>True if the specified object was found and thus was removed.</returns>
    /// <remarks>
    /// This will automatically purge some objects as the collection is iterated while searching for the passed object.
    /// </remarks>
    public bool Remove(T obj)
    {
        if(obj == null)
            throw new ArgumentNullException(nameof(obj));

        bool found = false;
        for(int i = 0; i < _handles.Count;)
        {
            GCHandle handle = _handles[i];
            object target = handle.Target;
            if(target == obj)
            {
                found = true;
                handle.Free();
                _handles.RemoveAt(i);
                _countAfterLastPurge--;
                break;
            }
            else if(target == null)
            {
                handle.Free();
                _handles.RemoveAt(i);
                _countAfterLastPurge--;
            }
            else
            {
                i++;
            }
        }

        GC.KeepAlive(this);
        return found;
    }

    /// <summary>
    /// Removes all objects from this WeakCollection.
    /// </summary>
    public void Clear()
    {
        for(int i = 0; i < _handles.Count; i++)
            _handles[i].Free();
        _handles.Clear();

        GC.KeepAlive(this);
    }

    /// <summary>
    /// Returns whether this WeakCollection contains the specified object.
    /// </summary>
    /// <remarks>
    /// This will automatically purge some objects as the collection is iterated while searching for the passed object.
    /// </remarks>
    public bool Contains(T obj)
    {
        if(obj == null)
            throw new ArgumentNullException(nameof(obj));

        bool found = false;
        for(int i = 0; i < _handles.Count;)
        {
            GCHandle handle = _handles[i];
            object target = handle.Target;
            if(target == obj)
            {
                found = true;
                break;
            }
            else if(target == null)
            {
                handle.Free();
                _handles.RemoveAt(i);
                _countAfterLastPurge--;
            }
            else
            {
                i++;
            }
        }

        GC.KeepAlive(this);
        return found;
    }

    /// <summary>
    /// Returns an enumerator that iterates through all of the living objects in this WeakCollection.
    /// </summary>
    /// <remarks>
    /// This will purge the tracking memory for any garbage-collected objects as they are iterated.
    /// </remarks>
    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    /// <summary>
    /// Returns an enumerator that iterates through all of the living objects in this WeakCollection.
    /// </summary>
    /// <remarks>
    /// This will purge the tracking memory for any garbage-collected objects as they are iterated.
    /// </remarks>
    public IEnumerator<T> GetEnumerator()
    {
        for(int i = 0; i < _handles.Count;)
        {
            GCHandle handle = _handles[i];
            object target = handle.Target;
            if(target == null)
            {
                handle.Free();
                _handles.RemoveAt(i);
            }
            else
            {
                yield return (T)target;
                i++;
            }
        }

        _countAfterLastPurge = _handles.Count;

        GC.KeepAlive(this);
    }

    /// <summary>
    /// Copies the living objects stored in this WeakCollection to the specified array.
    /// </summary>
    /// <remarks>
    /// This will purge the tracking memory for any garbage-collected objects.
    /// </remarks>
    public void CopyTo(T[] array, int arrayIndex)
    {
        if(array == null)
            throw new ArgumentNullException(nameof(array));
        if(arrayIndex < 0)
            throw new ArgumentOutOfRangeException(nameof(arrayIndex));

        for(int i = 0; i < _handles.Count;)
        {
            GCHandle handle = _handles[i];
            object target = handle.Target;
            if(target == null)
            {
                handle.Free();
                _handles.RemoveAt(i);
            }
            else
            {
                if(arrayIndex >= array.Length)
                    throw new ArgumentOutOfRangeException(nameof(arrayIndex));
                array[arrayIndex++] = (T)target;
                i++;
            }
        }

        _countAfterLastPurge = _handles.Count;

        GC.KeepAlive(this);
    }

    /// <summary>
    /// Removes any memory allocated for tracking objects that have been collected and are no longer alive.
    /// </summary>
    public void Purge()
    {
        for(int i = 0; i < _handles.Count;)
        {
            GCHandle handle = _handles[i];
            if(handle.Target == null)
            {
                handle.Free();
                _handles.RemoveAt(i);
            }
            else
            {
                i++;
            }
        }

        _countAfterLastPurge = _handles.Count;

        GC.KeepAlive(this);
    }

    int ICollection<T>.Count => throw new NotSupportedException("The exact number of living objects in a WeakCollection can never be ascertained. Call GetCount() to get an approximate count of objects.");
    bool ICollection<T>.IsReadOnly => false;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Are you aware this already exists (more or less) as ConditionalWeakTable? \$\endgroup\$ – 404 May 23 '17 at 9:02
  • \$\begingroup\$ @eurotrash Yes, I'm aware of ConditionalWeakTable, but thanks for pointing it out! The main problem with ConditionalWeakTable is that you can't iterate through it, which is crucial for my purposes. I'll update the original question to point this out. Thanks! \$\endgroup\$ – Walt D May 23 '17 at 15:02
  • \$\begingroup\$ I have no idea why you want all those GC.KeepAlive(this). Why not let the finalizer run when it wants to? If the instance fields, such as _handles, can no longer be used, the garbage collector can run if it decides to? \$\endgroup\$ – Jeppe Stig Nielsen May 23 '17 at 20:39
  • 1
    \$\begingroup\$ Since you have a finalizer, maybe you should implement IDisposable? Then put the for loop that calls Free()in a normal method. When Dispose() is called by the careful user, you run the for loop and then do a GC.SuppressFinalize(this);. It will spare you all the disadvantages of being put on the finalizer queue if only the user remembers to call Dispose(), maybe by simply having a using statement. For the careless user, you still have the finalizer which calls the method with the for loop. \$\endgroup\$ – Jeppe Stig Nielsen May 23 '17 at 20:44
  • \$\begingroup\$ @JeppeStigNielsen That makes a lot of sense to me. But what puzzles me is that WeakReference, which is itself based on GCHandle, also has a finalizer to free its GCHandle, but doesn't have a Dispose() method. I wonder why they chose to not have a Dispose() method? \$\endgroup\$ – Walt D May 23 '17 at 21:00
4
\$\begingroup\$

You should reduce the amount of copy-pasting.

  1. You need to implement IndexOf method, and re-use it in both Contains and Remove.
  2. This code block

            GCHandle handle = _handles[i];
            object target = handle.Target;
            if(target == null)
            {
                handle.Free();
                _handles.RemoveAt(i);
            }
    

    is copy-pasted over and over again. Might as well extract it to separate method:

    //or return target and check for null
    //or return C#7 tuple
    bool TryGetTarget(int index, out T target)
    {
        target = (T)_handles[index].Target;
        if(target == null)
        {
             handle.Free();
             _handles.RemoveAt(index);
             return false;
        }
        return true;
    }
    

You decrement _countAfterLastPurge when you remove items from collection, but you don't change it when collection is cleared. Maybe you should?


Once particular piece of advice I'm looking for is how best to detect whether the collection is modified during enumeration, so that it can throw an exception.

A strange thing to ask, given that you modify your collection yourself inside GetEnumerator method. Consider not purging your collection during enumeration, and regular foreach loop will throw alright:

foreach(var target in _handles.Select(h => (T)h.Target).Where(t => t != null))
{
    yield return target;
}
//this will throw as well
//return _handles.Select(h => (T)h.Target).Where(t => t != null).GetEnumerator();

Alternatively, introduce a bool flag. Set it every time collection is modified by Add/Remove/etc. methods and check it before yielding each element.

\$\endgroup\$
  • \$\begingroup\$ OfType<T> or Cast<T> would be prettier and the former safer then .Select(h => (T)h.Target) ;-) I also think this (T)h.Target).Where(t => t != null) won't work because (T)h.Target this will crash if the cast is invalid. Did you mean to use as here? \$\endgroup\$ – t3chb0t May 23 '17 at 14:17
  • \$\begingroup\$ @t3chb0t, no, Target can never be anything but T as per OP's design, so cast will never fail (if it does than it is a bug). Target can still be null though (before the cast). Maybe it is better to cast after checking for null to make this clear. Same can be said about TryGetTarget method. \$\endgroup\$ – Nikita B May 23 '17 at 14:41
  • \$\begingroup\$ Thanks for the feedback! And definitely good catch on not clearing _countAfterLastPurge when the collection is cleared, I need to do that. \$\endgroup\$ – Walt D May 23 '17 at 15:09
  • \$\begingroup\$ In regards to throwing a modification exception, the point is that adding or removing an item from the collection while it is enumerated could cause a crash or unexpected iteration results, so it's definitely something I want to safeguard against. And a key aspect about this class is that it purges itself at every opportunity as it performs other actions, so I definitely want GetEnumerator() to purge as it enumerates. \$\endgroup\$ – Walt D May 23 '17 at 15:13
  • \$\begingroup\$ @WaltD, fair enough. In which case I suggest you check out List<T> implementation for inspiration, in particular how it uses version field to track changes. referencesource.microsoft.com/#mscorlib/system/collections/… \$\endgroup\$ – Nikita B May 23 '17 at 17:29
3
\$\begingroup\$

First of all, IMHO it's a nice piece of well-written code that seems to be OK as it is.

However, I have a few marginal comments:

Contains

When using a collection's Contains method, I would expect that it uses the default comparer for the corresponding type or a custom one. There is no real problem with using Object.ReferenceEquals instead, but actually that is a requirement of the WeakCollection's internals (which should be hidden from the user).

Count

Another particular thing is, that the count information is uncertainly. You addressed that by making the Count property throwing an exception. That is IMHO the right way to handle it, but it also restricts the usage of the ICollection abstraction.

GetCount

I would Rename the GetCount method to something that makes clear that the count information is uncertainly (e.g. GetCountAfterLastPurge). Actually, I would drop them and add a CountAfterLastPurge property (That appears below the Count property in intellisense) instead. If needed, Purge() can be called before in a separate step.... but that is a matter of taste i think.

CopyTo

Count is often used in combination with CopyTo(array) to determine the length of the array. That pattern may fail with the WeakCollection.

Conclusion

I can't see a real use case for Count / Contains / CopyTo on a collection that's list of items is affected unpredictable by the GC.

Therefore I think that the ICollection interface is not the right choose here. It is probably better to implement IEnumerable and add the required methods Add / Remove / Purge. Functions like Count or Contains, can be used after creating a 'snapshot' of the current collection - Maybe in combination with GC.TryStartNoGCRegion / GC.EndNoGCRegion to avoid subsequent garbage collection or by adding a reference to the item objects for temporary usage.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the feedback! I agree that Contains should use default equality. I do still see a use for Contains, since if you're calling Contains on an item, then by definition that item isn't dead yet. (Or wait, it could be if I switch to default equality and you pass it something that's "equals" but not "reference equals". Hmm, I'll need to think about that...). CopyTo certainly seems less useful, at least not without being told how many items actually got copied into the array. Thanks again! \$\endgroup\$ – Walt D May 23 '17 at 15:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.