13,002,107 members (75,907 online)
alternative version

#### Stats

20.3K views
12 bookmarked
Posted 27 Mar 2010

# Creating a Weak List

, 27 Mar 2010
 Rate this:
This article explains how to create a weak list (a list that allows items to be collected by the GC)

## Introduction

This article explains how to create a weak list (a list that allows items to be collected by the GC).

I already wrote an article about WeakArrays, but the problem of weak arrays is that they have fixed length. Now, I will explain how to create a weak list.

First, how can we create a weak list?

Solution 1: In our class, we create a list of `WeakReferences`, but we implement all methods to get and set values of the data type, so the weak references are not seen. This one has the problem that each `WeakReference `has a destructor.

Solution 2: In our class, we create a list of `GCHandles`. We also implement all methods to get and set values of the data type, so the `GCHandles `are not seen. We must then implement the finalizer to free all `GCHandles `at once.

Solution 3: In our class, we create an `Array `of `GCHandles`, and control when such array must be resized, in a process similar to the original list. We must also implement the finalizer.

I must say that all of the solutions work but the first one is the slowest and the last one is the one that allows better control of everything. But, I will try to explain only the last one, which is the approach I use.

So, the things needed to write a weak list are:

• How a normal list works
• How to make the "weak" part work
• And how to make it thread-safe. Even if the list is theoretically only used by one Thread, the GC always runs as another thread at unexpected times.

## The Normal List

The normal list, in practice, is very simple. It contains an array (in my case, I initialize it with length 32) and a `Count`. Every time an item is added, it tries to put the item into the actual count and then increase the count. Of course, if there are more items than count, then a new array is created, with double the size, and the item is put at the `Count `position and `Count `is incremented. Of course, there are a lot of methods, like `IndexOf`, `Remove `and others, but they find items sequentially and, if one item is removed, all items are copied to one position before, and then the `Count `is decremented. Simple, isn't it?

Now, how do we make it weak?

As I said earlier, I will use `GCHandles`. So, instead of having a `Button[] `(if we have an `WeakList<button>`) or a `string[] `(if we have a `WeakList<string>`), we will always have a `GCHandle[]`. Then, to get a value at a given index, we will have a code that follows this pattern:

```public T this[int index]
{
get
{
// validates if the index is not out of range.
return (T)fHandles[index].Target;
}
set
{
// validates if the index is not out of range.

// checks if the GCHandle is initialized.
// if it is, set is Target.
// if it is not, then Alloc a new Weak GCHandle and set it to that position.
}
}```

But, two important things:

First, this "pattern" is not yet thread-safe, and it must be. Second, the `Count `will be a fake value. It will only tell how many Items where added that we do not know to have been collected. So, a list with `count `5 can, in fact, have 0 real items because all of them where collected.

And, finally, we must make it thread-safe.

The simplest way to make things thread-safe is to use Locks. And that's what I do. I don't use `ReaderWriterLocks `because they are slower than custom locks, and their benefit is only useful when the write operations are really slow, which is not the case. So, each method should lock the object (or better, some internal synchronization object), check if the object was not disposed, and then do its real work.

Ok... I said finally, but there are 2 more steps:

1. Implement `IDispose`. This is only needed to follow the guideline that, instead of counting on the `GarbageCollector `to finalize our object, if we know it will not be used anymore, we can free it immediately, and so the entire object will be collected in the next collection (if we run the finalizer, the object will only be collected one generation after that in which its finalizer was run).
2. Know when items were collected, so all the `GCHandles `that are now `null `can be removed.

To do this, we can constantly check the number of collection counts (at each insert method, for example), we can use a secondary thread with a timer, or we can discover when a collection was done to call an event. I already created a class (`GCUtils`) which has the `Collected `event. This is almost a hack, as I create an object without strong references (so it is always collected) and, in its finalize, I re-register it for finalize (so it does not die) and call set a `ManualResetEvent `object. So, as soon the GC terminates and all threads start to run again, my thread that is waiting on such `ManualResetEvent `calls the `Collected `event. Such event has the advantage that, if collections happen frequently, then the extra items will be removed frequently. And, if collections take long time to happen, then there will not be a process trying to remove them for nothing. But any method will work. So, the object must be locked, the number of non-collected items must be counted, then a new array must be created with, at least, the number of non-collected items and, finally, all valid handles must be copied and `null `handles must be freed. Note that between the count and the copy to the new array, more items can be collected, so the count must only be set after such copy is done.

And, that's finally it.

Now I will show the code for some key-methods:

```// This is the constructor that allows you to set its initial capacity.
// The default constructor calls this with a value of 32.
public WeakList(int initialCapacity)
{
if (initialCapacity < 1)
throw new ArgumentOutOfRangeException
("initialCapacity", "The initial accepted capacity value is 1.");

fHandles = new GCHandle[initialCapacity];
GCUtils.Collected += p_Collected;
}

// This will free all handles. It is already inside a lock
// (if called manually) or runs single-threaded (if from finalizer).
protected override void Dispose(bool disposing)
{
// if the dispose was called manually,
// we must unregister ourselves from the GCUtils.Collected method.
// we do not need to do this if this object is being collected,
// as the Collected event is also we and, so,
// it was already removed from there.
if (disposing)
GCUtils.Collected -= p_Collected;

// here we will free all allocated handles.
// After all, even if the objects can be collected,
// the handles must be freed.
var handles = fHandles;
if (handles != null)
{
int count = handles.Length;
for (int i=0; i<count; i++)
{
var handle = handles[i];
if (handle.IsAllocated)
handle.Free();
}

fHandles = null;
}

base.Dispose(disposing);
}

{
if (item == null)
throw new ArgumentNullException("item");

lock(DisposeLock) // the original code use AbortSafe.Lock,
{
CheckUndisposed();

int count = Count;
if (count == fHandles.Length)
Array.Resize(ref fHandles, count * 2);

try
{
}
finally
{
// If one happens after the Alloc and before the
// handle is set, then thanks to this finally
// block the exception will only happen after
// setting the handle in the array.
fHandles[count] = GCHandle.Alloc(item, GCHandleType.Weak);
}
Count++;
}
}```

To see the full implementation, download the library and look at Caching\WeakList.cs.

## The Future

Well, I don't know when I will publish the other articles, but I plan to explain how a `WeakHashSet `and a `WeakDictionary `work, as I think both are more useful than weak-lists.

## History

• 26th March, 2010: Initial version

## Share

I started to program computers when I was 11 years old, as a hobbyist, programming in AMOS Basic and Blitz Basic for Amiga.
At 12 I had my first try with assembler, but it was too difficult at the time. Then, in the same year, I learned C and, after learning C, I was finally able to learn assembler (for Motorola 680x0).
Not sure, but probably between 12 and 13, I started to learn C++. I always programmed "in an object oriented way", but using function pointers instead of virtual methods.

At 15 I started to learn Pascal at school and to use Delphi. At 16 I started my first internship (using Delphi). At 18 I started to work professionally using C++ and since then I've developed my programming skills as a professional developer in C++ and C#, generally creating libraries that help other developers do their work easier, faster and with less errors.

Take a look at: http://paulozemek.azurewebsites.net/
Or e-mail me at: paulozemek@outlook.com

Codeproject MVP 2012, 2015 & 2016
Microsoft MVP 2013-2014 (now I work at Microsoft so I can't be a Microsoft MVP anymore)

## You may also be interested in...

 First Prev Next
 Comparing references Christophe Bertrand16-Oct-13 23:43 Christophe Bertrand 16-Oct-13 23:43
 In WeakKeyDictionary.cs, I suggest to replace `if (target == key)` for `if (object.ReferenceEquals(target, key))` It seems more adequate comparing references than values. Thank you for sharing your work.
 Re: Comparing references Paulo Zemek17-Oct-13 5:27 Paulo Zemek 17-Oct-13 5:27
 Re: Comparing references Christophe Bertrand21-Oct-13 2:35 Christophe Bertrand 21-Oct-13 2:35
 Re: Comparing references Paulo Zemek21-Oct-13 6:15 Paulo Zemek 21-Oct-13 6:15
 Re: Comparing references Paulo Zemek21-Oct-13 6:20 Paulo Zemek 21-Oct-13 6:20
 Re: Comparing references Christophe Bertrand22-Oct-13 22:53 Christophe Bertrand 22-Oct-13 22:53
 Re: Comparing references Paulo Zemek23-Oct-13 10:45 Paulo Zemek 23-Oct-13 10:45
 WeakList vs List(of WeakReference) supercat929-Mar-10 5:33 supercat9 29-Mar-10 5:33
 Re: WeakList vs List(of WeakReference) Paulo Zemek29-Mar-10 14:58 Paulo Zemek 29-Mar-10 14:58
 This looks ok start Sacha Barber27-Mar-10 22:43 Sacha Barber 27-Mar-10 22:43
 Re: This looks ok start Paulo Zemek29-Mar-10 1:37 Paulo Zemek 29-Mar-10 1:37
 Re: This looks ok start Sacha Barber29-Mar-10 1:50 Sacha Barber 29-Mar-10 1:50
 Last Visit: 31-Dec-99 18:00     Last Update: 26-Jun-17 10:43 Refresh 1