Author: raja
Date: 2005-06-27 04:36:29 -0400 (Mon, 27 Jun 2005)
New Revision: 46538
Modified:
trunk/mcs/class/corlib/System.Collections.Generic/ChangeLog
trunk/mcs/class/corlib/System.Collections.Generic/Dictionary.cs
trunk/mcs/class/corlib/Test/System.Collections.Generic/ChangeLog
trunk/mcs/class/corlib/Test/System.Collections.Generic/DictionaryTest.cs
Log:
In System.Collections.Generic:
Introduce some thread-safety by removing the modify-on-read
move-to-front heuristic.
* Dictionary.cs (_enumeratorGeneration, _enumerators): Remove.
(Count): Add internal property set. Invalidate enumerators when
Count is changed. Change all references of _usedSlots to Count.
(this): Invalidate enumerators when the value of some slot is
changed, even if the layout of the data-structure isn't modified.
(DoHash): Remove null-key check. All codepaths leading to this
function already have the check.
(GetSlot): Remove move-to-front heuristic.
(Remove): Update.
In Test/System.Collections.Generic:
* DictionaryTest.cs (FailFastTest1, FailFastTest2, FailFastTest3):
New tests to ensure that enumerators are invalidated on
modifications to the dictionary.
Modified: trunk/mcs/class/corlib/System.Collections.Generic/ChangeLog
===================================================================
--- trunk/mcs/class/corlib/System.Collections.Generic/ChangeLog 2005-06-27
08:33:39 UTC (rev 46537)
+++ trunk/mcs/class/corlib/System.Collections.Generic/ChangeLog 2005-06-27
08:36:29 UTC (rev 46538)
@@ -1,3 +1,17 @@
+2005-06-27 Raja R Harinath <[EMAIL PROTECTED]>
+
+ Introduce some thread-safety by removing the modify-on-read
+ move-to-front heuristic.
+ * Dictionary.cs (_enumeratorGeneration, _enumerators): Remove.
+ (Count): Add internal property set. Invalidate enumerators when
+ Count is changed. Change all references of _usedSlots to Count.
+ (this): Invalidate enumerators when the value of some slot is
+ changed, even if the layout of the data-structure isn't modified.
+ (DoHash): Remove null-key check. All codepaths leading to this
+ function already have the check.
+ (GetSlot): Remove move-to-front heuristic.
+ (Remove): Update.
+
2005-06-24 Martin Baulig <[EMAIL PROTECTED]>
* IDictionary.cs: Use the same type parameter names than on MS.
Modified: trunk/mcs/class/corlib/System.Collections.Generic/Dictionary.cs
===================================================================
--- trunk/mcs/class/corlib/System.Collections.Generic/Dictionary.cs
2005-06-27 08:33:39 UTC (rev 46537)
+++ trunk/mcs/class/corlib/System.Collections.Generic/Dictionary.cs
2005-06-27 08:36:29 UTC (rev 46538)
@@ -73,11 +73,14 @@
SerializationInfo _serializationInfo;
private uint _generation;
- private uint _enumeratorGeneration;
- private uint _enumerators;
public int Count {
get { return _usedSlots; }
+ /* FIXME: this should be 'private' not 'internal'. */
+ internal set {
+ _usedSlots = value;
+ ++_generation;
+ }
}
public TValue this [TKey key] {
@@ -90,13 +93,14 @@
}
set {
- ++_generation;
int index;
Slot slot = GetSlot (key, out index);
- if (slot == null)
+ if (slot == null) {
DoAdd (index, key, value);
- else
+ } else {
+ ++_generation;
slot.Data.Value = value;
+ }
}
}
@@ -126,9 +130,8 @@
throw new ArgumentNullException ("dictionary");
int capacity = dictionary.Count;
Init (capacity, comparer);
- foreach (KeyValuePair<TKey, TValue> entry in
dictionary) {
+ foreach (KeyValuePair<TKey, TValue> entry in dictionary)
this.Add (entry.Key, entry.Value);
- }
}
public Dictionary (int capacity, IEqualityComparer<TKey>
comparer)
@@ -156,8 +159,6 @@
_table = new Slot [capacity];
SetThreshold ();
_generation = 0;
- _enumeratorGeneration = 0;
- _enumerators = 0;
}
void CopyTo (KeyValuePair<TKey, TValue> [] array, int index)
@@ -168,7 +169,7 @@
throw new ArgumentOutOfRangeException ("index");
if (index >= array.Length)
throw new ArgumentException ("index larger than
largest valid index of array");
- if (array.Length - index < _usedSlots)
+ if (array.Length - index < Count)
throw new ArgumentException ("Destination array
cannot hold the requested elements!");
for (int i = 0; i < _table.Length; ++i) {
@@ -205,32 +206,24 @@
public void Add (TKey key, TValue value)
{
- ++_generation;
int index;
Slot slot = GetSlot (key, out index);
-
if (slot != null)
throw new ArgumentException ("An element with
the same key already exists in the dictionary.");
-
DoAdd (index, key, value);
}
void DoAdd (int index, TKey key, TValue value)
{
- if (_usedSlots >= _threshold) {
+ if (Count++ >= _threshold) {
Resize ();
index = DoHash (key);
}
-
_table [index] = new Slot (key, value, _table [index]);
- ++_usedSlots;
}
private int DoHash (TKey key)
{
- if (key == null)
- throw new ArgumentNullException ("key", "null
key");
-
int size = this._table.Length;
int h = _hcp.GetHashCode (key) & Int32.MaxValue;
int spot = (int) ((uint) h % size);
@@ -243,10 +236,9 @@
public void Clear ()
{
- ++_generation;
+ Count = 0;
for (int i = 0; i < _table.Length; i++)
_table [i] = null;
- _usedSlots = 0;
}
public bool ContainsKey (TKey key)
@@ -275,9 +267,9 @@
throw new ArgumentNullException ("info");
info.AddValue ("hcp", _hcp);
- KeyValuePair<TKey, TValue>[] data = null;
- if (_usedSlots > 0) {
- data = new KeyValuePair<TKey,TValue>
[_usedSlots];
+ KeyValuePair<TKey, TValue> [] data = null;
+ if (Count > 0) {
+ data = new KeyValuePair<TKey,TValue> [Count];
CopyTo (data, 0);
}
info.AddValue ("data", data);
@@ -300,7 +292,7 @@
_table = new Slot [buckets];
SetThreshold ();
- _usedSlots = 0;
+ Count = 0;
if (data != null) {
for (int i = 0; i < data.Length; ++i)
@@ -311,24 +303,25 @@
public bool Remove (TKey key)
{
- ++_generation;
int index;
Slot slot = GetSlot (key, out index);
-
if (slot == null)
return false;
- // If GetSlot returns a valid slot, the given key is at
the head of the chain.
- if (_table [index] != slot)
- throw new SystemException ("dictionary has
inconsistent state, aborting");
- _table [index] = _table [index].Next;
- --_usedSlots;
+ --Count;
+ if (slot == _table [index]) {
+ _table [index] = _table [index].Next;
+ } else {
+ Slot prev = _table [index];
+ while (prev.Next != slot)
+ prev = prev.Next;
+ prev.Next = slot.Next;
+ }
return true;
}
//
// Return the slot containing key, and set 'index' to the chain
the key was found in.
- // Also try to ensure that the found key is the first element
of its chain.
// If the key is not found, return null and set 'index' to the
chain that would've contained the key.
//
private Slot GetSlot (TKey key, out int index)
@@ -336,22 +329,9 @@
if (key == null)
throw new ArgumentNullException ("key");
index = DoHash (key);
- Slot prev = null;
Slot slot = _table [index];
-
- while (slot != null && !_hcp.Equals (key,
slot.Data.Key)) {
- prev = slot;
+ while (slot != null && !_hcp.Equals (key,
slot.Data.Key))
slot = slot.Next;
- }
-
- if (slot != null && prev != null &&
- (_enumeratorGeneration != _generation ||
_enumerators == 0)) {
- // Move to the head of the list
- prev.Next = slot.Next;
- slot.Next = _table [index];
- _table [index] = slot;
- }
-
return slot;
}
@@ -495,13 +475,11 @@
internal Enumerator (Dictionary<TKey, TValue>
dictionary)
{
- ++dictionary._enumerators;
_dictionary = dictionary;
- _stamp = dictionary._enumeratorGeneration =
dictionary._generation;
+ _stamp = dictionary._generation;
// The following stanza is identical to
IEnumerator.Reset (),
- // but because of the
- // definite assignment rule, we cannot call it
here.
+ // but because of the definite assignment rule,
we cannot call it here.
_nextIndex = 0;
_current = null;
}
@@ -534,40 +512,30 @@
}
object IEnumerator.Current {
- get {
- VerifyState ();
- return new DictionaryEntry
(_current.Data.Key, _current.Data.Value);
- }
+ get { return ((IDictionaryEnumerator)
this).Entry; }
}
- DictionaryEntry IDictionaryEnumerator.Entry {
- get {
- VerifyState ();
- return new DictionaryEntry
(_current.Data.Key, _current.Data.Value);
- }
- }
-
void IEnumerator.Reset ()
{
_nextIndex = 0;
_current = null;
}
- object IDictionaryEnumerator.Key
- {
+ DictionaryEntry IDictionaryEnumerator.Entry {
get {
VerifyState ();
- return _current.Data.Key;
+ return new DictionaryEntry
(_current.Data.Key, _current.Data.Value);
}
}
- object IDictionaryEnumerator.Value
- {
- get {
- VerifyState ();
- return _current.Data.Value;
- }
+
+ object IDictionaryEnumerator.Key {
+ get { return Current.Key; }
}
+ object IDictionaryEnumerator.Value {
+ get { return Current.Value; }
+ }
+
void VerifyState ()
{
if (_dictionary == null)
@@ -580,7 +548,6 @@
public void Dispose ()
{
_current = null;
- --_dictionary._enumerators;
_dictionary = null;
}
}
@@ -605,7 +572,7 @@
throw new ArgumentOutOfRangeException
("index");
if (index >= array.Length)
throw new ArgumentException ("index
larger than largest valid index of array");
- if (array.Length - index <
_dictionary._usedSlots)
+ if (array.Length - index < _dictionary.Count)
throw new ArgumentException
("Destination array cannot hold the requested elements!");
foreach (TKey k in this)
@@ -721,7 +688,7 @@
throw new ArgumentOutOfRangeException
("index");
if (index >= array.Length)
throw new ArgumentException ("index
larger than largest valid index of array");
- if (array.Length - index <
_dictionary._usedSlots)
+ if (array.Length - index < _dictionary.Count)
throw new ArgumentException
("Destination array cannot hold the requested elements!");
foreach (TValue k in this)
Modified: trunk/mcs/class/corlib/Test/System.Collections.Generic/ChangeLog
===================================================================
--- trunk/mcs/class/corlib/Test/System.Collections.Generic/ChangeLog
2005-06-27 08:33:39 UTC (rev 46537)
+++ trunk/mcs/class/corlib/Test/System.Collections.Generic/ChangeLog
2005-06-27 08:36:29 UTC (rev 46538)
@@ -1,3 +1,9 @@
+2005-06-27 Raja R Harinath <[EMAIL PROTECTED]>
+
+ * DictionaryTest.cs (FailFastTest1, FailFastTest2, FailFastTest3):
+ New tests to ensure that enumerators are invalidated on
+ modifications to the dictionary.
+
2005-06-22 Raja R Harinath <[EMAIL PROTECTED]>
* DictionaryTest.cs (KeyValueEnumeratorTest): Add test for infloop
Modified:
trunk/mcs/class/corlib/Test/System.Collections.Generic/DictionaryTest.cs
===================================================================
--- trunk/mcs/class/corlib/Test/System.Collections.Generic/DictionaryTest.cs
2005-06-27 08:33:39 UTC (rev 46537)
+++ trunk/mcs/class/corlib/Test/System.Collections.Generic/DictionaryTest.cs
2005-06-27 08:36:29 UTC (rev 46538)
@@ -511,6 +511,48 @@
Assert.IsFalse(((object) enumerator.Current) is
DictionaryEntry);
}
+ [Test, ExpectedException (typeof (InvalidOperationException))]
+ public void FailFastTest1 ()
+ {
+ Dictionary<int, int> d = new Dictionary<int, int> ();
+ d [1] = 1;
+ int count = 0;
+ foreach (KeyValuePair<int, int> kv in d) {
+ d [kv.Key + 1] = kv.Value + 1;
+ if (count++ != 0)
+ Assert.Fail ("Should not be reached");
+ }
+ Assert.Fail ("Should not be reached");
+ }
+
+ [Test, ExpectedException (typeof (InvalidOperationException))]
+ public void FailFastTest2 ()
+ {
+ Dictionary<int, int> d = new Dictionary<int, int> ();
+ d [1] = 1;
+ int count = 0;
+ foreach (int i in d.Keys) {
+ d [i + 1] = i + 1;
+ if (count++ != 0)
+ Assert.Fail ("Should not be reached");
+ }
+ Assert.Fail ("Should not be reached");
+ }
+
+ [Test, ExpectedException (typeof (InvalidOperationException))]
+ public void FailFastTest3 ()
+ {
+ Dictionary<int, int> d = new Dictionary<int, int> ();
+ d [1] = 1;
+ int count = 0;
+ foreach (int i in d.Keys) {
+ d [i] = i;
+ if (count++ != 0)
+ Assert.Fail ("Should not be reached");
+ }
+ Assert.Fail ("Should not be reached");
+ }
+
[Test]
public void SerializationTest()
{
_______________________________________________
Mono-patches maillist - [email protected]
http://lists.ximian.com/mailman/listinfo/mono-patches
