[Mono-dev] Dictionary implementation + concurrency

[Greg Young]

The .NET dictionary implementation is thread safe on reads/updates so
long as the internal collection does not grow and size is of reference
type or smaller. eg: if you set size to 1m items and had 100k with a
fill factor that did not cause an internal growth it would be
threadsafe. This assurance has been brought over from Hashtable (well
documented) and is relatively not well documented but many take a
dependency on it. The current mono implementation does not meet this
assurance.

			int cur = table [(hashCode & int.MaxValue) % table.Length] - 1;

			// walk linked list until right slot is found or end is reached
			while (cur != NO_SLOT) {
				// The ordering is important for compatibility with MS and strange
				// Object.Equals () implementations
				if (linkSlots [cur].HashCode == hashCode && hcp.Equals (keySlots
[cur], key)) {
					value = valueSlots [cur];
					return true;
				}
				cur = linkSlots [cur].Next;
			}

seems fine when accessing. However when adding...

			// find an empty slot
			cur = emptySlot;
			if (cur == NO_SLOT)
				cur = touchedSlots++;
			else
				emptySlot = linkSlots [cur].Next;

			// store the hash code of the added item,
			// prepend the added item to its linked list,
			// update the hash table
			linkSlots [cur].HashCode = hashCode;
			linkSlots [cur].Next = table [index] - 1;
			table [index] = cur + 1;

			// store item's data
			keySlots [cur] = key;
			valueSlots [cur] = value;

Can cause null reads of a key as its in linkSlots but the value slot
has not yet been updated. Setting keySlots after valueSlots would seem
to solve this. Pull request wanted?

Cheers,

Greg

-- 
Le doute n'est pas une condition agréable, mais la certitude est absurde.