Click here to Skip to main content
Click here to Skip to main content

Tagged as

Creating a Weak List

, 27 Mar 2010 CPOL
Rate this:
Please Sign up or sign in to vote.
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);
}

public void Add(T item)
{
	if (item == null)
		throw new ArgumentNullException("item");

	lock(DisposeLock) // the original code use AbortSafe.Lock,
	                  // but that is because I am paranoic about Thread.Abort.
	{
		CheckUndisposed();

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

		try
		{
		}
		finally
		{
			// again, I am paranoic about Thread.Abort.
			// 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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Paulo Zemek
Engineer Microsoft Corporation
United States United States
I started to program computers when I was 11 years old, as a hobbist, 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 they work easier, faster and with less errors.
 
Now I just started working as a Senior Software Engineer at Microsoft.
 
Want more info or simply want to contact me?
Take a look at: http://paulozemek.azurewebsites.net/
Or e-mail me at: paulozemek@outlook.com
 
Codeproject MVP 2012
Microsoft MVP 2013-2014

Comments and Discussions

 
SuggestionComparing references PinmemberChristophe Bertrand17-Oct-13 0:43 
GeneralRe: Comparing references PinprofessionalPaulo Zemek17-Oct-13 6:27 
AnswerRe: Comparing references PinmemberChristophe Bertrand21-Oct-13 3:35 
GeneralRe: Comparing references PinprofessionalPaulo Zemek21-Oct-13 7:15 
GeneralRe: Comparing references PinprofessionalPaulo Zemek21-Oct-13 7:20 
Considering your class, try this:
public static bool AreEqual<T>(T a, T b)
where
	T: class
{
	return a == b;
}
static void Main(string[] args)
{
	var a = new NeverEquals();
	Console.WriteLine(a == a);
	Console.WriteLine(AreEqual(a, a));
 
	Console.ReadLine();
}
 
Note that the method AreEqual doesn't even compile if I dont put the where T: class.
And the result of AreEqual(a, a), which uses the == is true, even with the Console.WriteLine(a == a) returning false.
GeneralRe: Comparing references PinmemberChristophe Bertrand22-Oct-13 23:53 
GeneralRe: Comparing references PinprofessionalPaulo Zemek23-Oct-13 11:45 
GeneralWeakList vs List(of WeakReference) Pinmembersupercat929-Mar-10 6:33 
GeneralRe: WeakList vs List(of WeakReference) PinmemberPaulo Zemek29-Mar-10 15:58 
GeneralThis looks ok start PinmvpSacha Barber27-Mar-10 23:43 
GeneralRe: This looks ok start PinmemberPaulo Zemek29-Mar-10 2:37 
GeneralRe: This looks ok start PinmvpSacha Barber29-Mar-10 2:50 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web04 | 2.8.141216.1 | Last Updated 27 Mar 2010
Article Copyright 2010 by Paulo Zemek
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid