Author: raja
Date: 2005-08-03 09:48:31 -0400 (Wed, 03 Aug 2005)
New Revision: 47958
Modified:
trunk/mcs/class/System/System.Collections.Specialized/ChangeLog
trunk/mcs/class/System/System.Collections.Specialized/ListDictionary.cs
Log:
* ListDictionary.cs: Rewrite to reduce key comparison overhead.
Unify all list traversals into FindEntry.
(AreEqual): Remove.
(FindEntry): Split into two duplicate loops, one when comparer ==
null, the other when it isn't. Add new out parameter that points
to the entry preceding the result.
(Add, AddImpl, this []): Update.
(Remove): Use FindEntry for traversal.
(CopyTo): Add more tests.
(ListEntryEnumerator): Simplify.
(ListEntryCollection, ListEntryCollectionEnumerator): Likewise.
(I started out to delete AreEqual, but it ended up into an drive-by cleanup)
Modified: trunk/mcs/class/System/System.Collections.Specialized/ChangeLog
===================================================================
--- trunk/mcs/class/System/System.Collections.Specialized/ChangeLog
2005-08-03 13:27:21 UTC (rev 47957)
+++ trunk/mcs/class/System/System.Collections.Specialized/ChangeLog
2005-08-03 13:48:31 UTC (rev 47958)
@@ -1,5 +1,17 @@
2005-08-03 Raja R Harinath <[EMAIL PROTECTED]>
+ * ListDictionary.cs: Rewrite to reduce key comparison overhead.
+ Unify all list traversals into FindEntry.
+ (AreEqual): Remove.
+ (FindEntry): Split into two duplicate loops, one when comparer ==
+ null, the other when it isn't. Add new out parameter that points
+ to the entry preceding the result.
+ (Add, AddImpl, this []): Update.
+ (Remove): Use FindEntry for traversal.
+ (CopyTo): Add more tests.
+ (ListEntryEnumerator): Simplify.
+ (ListEntryCollection, ListEntryCollectionEnumerator): Likewise.
+
* HybridDictionary.cs: Rewrite to avoid a test on each operation.
(list, hashtable): Remove.
(inner): New IDictionary field that can hold either a list
Modified:
trunk/mcs/class/System/System.Collections.Specialized/ListDictionary.cs
===================================================================
--- trunk/mcs/class/System/System.Collections.Specialized/ListDictionary.cs
2005-08-03 13:27:21 UTC (rev 47957)
+++ trunk/mcs/class/System/System.Collections.Specialized/ListDictionary.cs
2005-08-03 13:48:31 UTC (rev 47958)
@@ -1,465 +1,356 @@
-
-//
-// Permission is hereby granted, free of charge, to any person obtaining
-// a copy of this software and associated documentation files (the
-// "Software"), to deal in the Software without restriction, including
-// without limitation the rights to use, copy, modify, merge, publish,
-// distribute, sublicense, and/or sell copies of the Software, and to
-// permit persons to whom the Software is furnished to do so, subject to
-// the following conditions:
-//
-// The above copyright notice and this permission notice shall be
-// included in all copies or substantial portions of the Software.
-//
-// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
-// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
-// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
-// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
-// LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
-// OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
-// WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
-//
-namespace System.Collections.Specialized
-{
- [Serializable]
- public class ListDictionary : IDictionary, ICollection, IEnumerable
- {
- private int count;
- private int modCount;
- private ListEntry root;
- private IComparer comparer;
-
-
- public ListDictionary()
- {
- count = 0;
- modCount = 0;
- comparer = null;
- root = null;
- }
-
- public ListDictionary(IComparer comparer) : this()
- {
- this.comparer = comparer;
- }
-
- private bool AreEqual(object obj1, object obj2)
- {
- if (comparer != null) {
- if (comparer.Compare(obj1, obj2) == 0) {
- return true;
- }
- } else {
- if (obj1.Equals(obj2)) {
- return true;
- }
- }
-
- return false;
- }
-
- private ListEntry FindEntry(object key)
- {
- if (key == null) {
- throw new ArgumentNullException("Attempted
lookup for a null key.");
- }
-
- if (root == null) {
- return null;
- } else {
- ListEntry entry = root;
-
- while (entry != null) {
- if (AreEqual(key, entry.key)) {
- return entry;
- }
-
- entry = entry.next;
- }
- }
-
- return null;
- }
-
- private void AddImpl(object key, object value)
- {
- if (key == null) {
- throw new ArgumentNullException("Attempted add
with a null key.");
- }
-
- if (root == null) {
- root = new ListEntry();
- root.key = key;
- root.value = value;
- } else {
- ListEntry entry = root;
-
- while (entry != null) {
- if (AreEqual(key, entry.key)) {
- throw new
ArgumentException("Duplicate key in add.");
- }
-
- if (entry.next == null) {
- break;
- }
-
- entry = entry.next;
- }
-
- entry.next = new ListEntry();
- entry.next.key = key;
- entry.next.value = value;
- }
-
- count++;
- modCount++;
- }
-
- // IEnumerable Interface
- IEnumerator IEnumerable.GetEnumerator()
- {
- return new ListEntryEnumerator(this);
- }
-
- // ICollection Interface
- public int Count {
- get {
- return count;
- }
- }
-
- public bool IsSynchronized {
- get {
- return false;
- }
- }
-
- public object SyncRoot {
- get {
- return this;
- }
- }
-
- public void CopyTo(Array array, int index)
- {
- if (array == null)
- throw new ArgumentNullException(
- "array",
- "Array cannot be null.");
-
- if (index < 0)
- throw new ArgumentOutOfRangeException("index",
"index is less than 0");
-
- int i = index;
- foreach ( DictionaryEntry entry in this )
- array.SetValue( entry, i++ );
- }
-
- // IDictionary Interface
- public bool IsFixedSize
- {
- get {
- return false;
- }
- }
-
- public bool IsReadOnly
- {
- get {
- return false;
- }
- }
-
- // Indexer
- public object this[object key]
- {
- get {
- ListEntry entry = FindEntry(key);
- return entry == null ? entry : entry.value;
- }
-
- set {
- ListEntry entry = FindEntry(key);
- if (entry != null)
- entry.value = value;
- else
- AddImpl(key, value);
- }
- }
-
- public ICollection Keys
- {
- get {
- return new ListEntryCollection(this, true);
- }
- }
-
- public ICollection Values
- {
- get {
- return new ListEntryCollection(this, false);
- }
- }
-
- public void Add(object key, object value)
- {
- AddImpl(key, value);
- }
-
- public void Clear()
- {
- root = null;
- count = 0;
- modCount++;
- }
-
- public bool Contains(object key)
- {
- return FindEntry(key) != null ? true : false;
- }
-
- public IDictionaryEnumerator GetEnumerator()
- {
- return new ListEntryEnumerator(this);
- }
-
- public void Remove(object key)
- {
- if (key == null)
- throw new ArgumentNullException(
- "key",
- "Key cannot be null.");
-
-
- ListEntry entry = root;
-
- for (ListEntry prev = null; entry != null; prev =
entry, entry = entry.next) {
- if (AreEqual(key, entry.key)) {
- if (prev != null) {
- prev.next = entry.next;
- } else {
- root = entry.next;
- }
-
- entry.value = null;
- count--;
- modCount++;
- }
- }
- }
-
-
- [Serializable]
- private class ListEntry
- {
- public object key = null;
- public object value = null;
- public ListEntry next = null;
- }
-
-
- private class ListEntryEnumerator : IEnumerator,
IDictionaryEnumerator
- {
- private ListDictionary dict;
- private bool isAtStart;
- private ListEntry current;
- private int version;
-
- public ListEntryEnumerator(ListDictionary dict)
- {
- this.dict = dict;
- version = dict.modCount;
- Reset();
- }
-
- private void FailFast()
- {
- if (version != dict.modCount) {
- throw new InvalidOperationException(
- "The ListDictionary's contents
changed after this enumerator was instantiated.");
- }
- }
-
- public bool MoveNext()
- {
- FailFast();
-
- if (isAtStart) {
- current = dict.root;
- isAtStart = false;
- } else {
- current = current.next;
- }
-
- return current != null ? true : false;
- }
-
- public void Reset()
- {
- FailFast();
-
- isAtStart = true;
- current = null;
- }
-
- public object Current
- {
- get {
- FailFast();
-
- if (isAtStart || current == null) {
- throw new
InvalidOperationException(
- "Enumerator is
positioned before the collection's first element or after the last element.");
- }
-
- return new DictionaryEntry(current.key,
current.value);
- }
- }
-
- // IDictionaryEnumerator
- public DictionaryEntry Entry
- {
- get {
- FailFast();
- return (DictionaryEntry) Current;
- }
- }
-
- public object Key
- {
- get {
- FailFast();
-
- if (isAtStart || current == null) {
- throw new
InvalidOperationException(
- "Enumerator is
positioned before the collection's first element or after the last element.");
- }
-
- return current.key;
- }
- }
-
- public object Value
- {
- get {
- FailFast();
-
- if (isAtStart || current == null) {
- throw new
InvalidOperationException(
- "Enumerator is
positioned before the collection's first element or after the last element.");
- }
-
- return current.value;
- }
- }
- }
-
- private class ListEntryCollection : ICollection
- {
- private ListDictionary dict;
- private bool isKeyList;
-
- public ListEntryCollection(ListDictionary dict, bool
isKeyList)
- {
- this.dict = dict;
- this.isKeyList = isKeyList;
- }
-
- // ICollection Interface
- public int Count {
- get {
- return dict.Count;
- }
- }
-
- public bool IsSynchronized
- {
- get {
- return false;
- }
- }
-
- public object SyncRoot
- {
- get {
- return dict.SyncRoot;
- }
- }
-
- public void CopyTo(Array array, int index)
- {
- int i = index;
- foreach ( object obj in this )
- array.SetValue( obj, i++ );
- }
-
- // IEnumerable Interface
- public IEnumerator GetEnumerator()
- {
- return new ListEntryCollectionEnumerator(dict,
isKeyList);
- }
-
- private class ListEntryCollectionEnumerator :
IEnumerator
- {
- private ListDictionary dict;
- private bool isKeyList;
- private bool isAtStart;
- private int version;
- private ListEntry current;
-
- public
ListEntryCollectionEnumerator(ListDictionary dict, bool isKeyList)
- {
- this.dict = dict;
- this.isKeyList = isKeyList;
- isAtStart = true;
- version = dict.modCount;
- }
-
- private void FailFast()
- {
- if (version != dict.modCount) {
- throw new
InvalidOperationException(
- "The Collection's
contents changed after this " +
- "enumerator was
instantiated.");
- }
- }
-
- public object Current
- {
- get {
- FailFast();
-
- if (isAtStart || current ==
null) {
- throw new
InvalidOperationException(
- "Enumerator is
positioned before the collection's " +
- "first element
or after the last element.");
- }
-
- return isKeyList ? current.key
: current.value;
- }
- }
-
- public bool MoveNext()
- {
- FailFast();
-
- if (isAtStart) {
- current = dict.root;
- isAtStart = false;
- } else {
- current = current.next;
- }
-
- return current != null ? true : false;
- }
-
- public void Reset()
- {
- FailFast();
- isAtStart = true;
- current = null;
- }
- }
- }
- }
-}
+//
+// System.Collections.Specialized.ListDictionary.cs
+//
+// Copyright (C) 2004, 2005 Novell (http://www.novell.com)
+//
+
+//
+// Permission is hereby granted, free of charge, to any person obtaining
+// a copy of this software and associated documentation files (the
+// "Software"), to deal in the Software without restriction, including
+// without limitation the rights to use, copy, modify, merge, publish,
+// distribute, sublicense, and/or sell copies of the Software, and to
+// permit persons to whom the Software is furnished to do so, subject to
+// the following conditions:
+//
+// The above copyright notice and this permission notice shall be
+// included in all copies or substantial portions of the Software.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
+// LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
+// OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
+// WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+//
+namespace System.Collections.Specialized
+{
+ [Serializable]
+ public class ListDictionary : IDictionary, ICollection, IEnumerable {
+ private int count;
+ private int modCount;
+ private ListEntry root;
+ private IComparer comparer;
+
+ public ListDictionary ()
+ {
+ count = 0;
+ modCount = 0;
+ comparer = null;
+ root = null;
+ }
+
+ public ListDictionary (IComparer comparer) : this ()
+ {
+ this.comparer = comparer;
+ }
+
+ private ListEntry FindEntry (object key, out ListEntry prev)
+ {
+ if (key == null)
+ throw new ArgumentNullException ("key",
"Attempted lookup for a null key.");
+
+ ListEntry entry = root;
+ prev = null;
+ if (comparer == null) {
+ while (entry != null) {
+ if (key.Equals (entry.key))
+ break;
+ prev = entry;
+ entry = entry.next;
+ }
+ } else {
+ while (entry != null) {
+ if (comparer.Compare (key, entry.key)
== 0)
+ break;
+ prev = entry;
+ entry = entry.next;
+ }
+ }
+ return entry;
+ }
+
+ private void AddImpl (object key, object value, ListEntry prev)
+ {
+ //
+ // Code in the MCS compiler (doc.cs) appears to depend
on the new entry being
+ // added at the end, even though we don't promise any
such thing.
+ // Preferably, this code would just have been:
+ //
+ // root = new ListEntry (key, value, root);
+ //
+ if (prev == null)
+ root = new ListEntry (key, value, root);
+ else
+ prev.next = new ListEntry (key, value,
prev.next);
+ ++count;
+ ++modCount;
+ }
+
+ // IEnumerable Interface
+ IEnumerator IEnumerable.GetEnumerator ()
+ {
+ return new ListEntryEnumerator (this);
+ }
+
+ // ICollection Interface
+ public int Count {
+ get { return count; }
+ }
+
+ public bool IsSynchronized {
+ get { return false; }
+ }
+
+ public object SyncRoot {
+ get { return this; }
+ }
+
+ public void CopyTo (Array array, int index)
+ {
+ if (array == null)
+ throw new ArgumentNullException ("array",
"Array cannot be null.");
+ if (index < 0)
+ throw new ArgumentOutOfRangeException ("index",
"index is less than 0");
+ if (index > array.Length)
+ throw new IndexOutOfRangeException ("index is
too large");
+ if (Count > array.Length - index)
+ throw new ArgumentException ("Not enough room
in the array");
+
+ foreach (DictionaryEntry entry in this)
+ array.SetValue (entry, index++);
+ }
+
+ // IDictionary Interface
+ public bool IsFixedSize {
+ get { return false; }
+ }
+
+ public bool IsReadOnly {
+ get { return false; }
+ }
+
+ // Indexer
+ public object this [object key] {
+ get {
+ ListEntry prev;
+ ListEntry entry = FindEntry (key, out prev);
+ return entry == null ? null : entry.value;
+ }
+
+ set {
+ ListEntry prev;
+ ListEntry entry = FindEntry (key, out prev);
+ if (entry != null)
+ entry.value = value;
+ else
+ AddImpl (key, value, prev);
+ }
+ }
+
+ public ICollection Keys {
+ get { return new ListEntryCollection (this, true); }
+ }
+
+ public ICollection Values {
+ get { return new ListEntryCollection (this, false); }
+ }
+
+ public void Add (object key, object value)
+ {
+ ListEntry prev;
+ ListEntry entry = FindEntry (key, out prev);
+ if (entry != null)
+ throw new ArgumentException ("key", "Duplicate
key in add.");
+
+ AddImpl (key, value, prev);
+ }
+
+ public void Clear ()
+ {
+ root = null;
+ count = 0;
+ modCount++;
+ }
+
+ public bool Contains (object key)
+ {
+ ListEntry prev;
+ return FindEntry (key, out prev) != null;
+ }
+
+ public IDictionaryEnumerator GetEnumerator ()
+ {
+ return new ListEntryEnumerator (this);
+ }
+
+ public void Remove (object key)
+ {
+ ListEntry prev;
+ ListEntry entry = FindEntry (key, out prev);
+ if (entry == null)
+ return;
+ if (prev == null)
+ root = entry.next;
+ else
+ prev.next = entry.next;
+ entry.value = null;
+ count--;
+ modCount++;
+ }
+
+
+ [Serializable]
+ private class ListEntry {
+ public object key;
+ public object value;
+ public ListEntry next;
+ public ListEntry (object key, object value, ListEntry
next)
+ {
+ this.key = key;
+ this.value = value;
+ this.next = next;
+ }
+ }
+
+ private class ListEntryEnumerator : IEnumerator,
IDictionaryEnumerator {
+ private ListDictionary dict;
+ private bool isAtStart;
+ private ListEntry current;
+ private int version;
+
+ public ListEntryEnumerator (ListDictionary dict)
+ {
+ this.dict = dict;
+ version = dict.modCount;
+ Reset();
+ }
+
+ private void FailFast()
+ {
+ if (version != dict.modCount) {
+ throw new InvalidOperationException (
+ "The ListDictionary's contents
changed after this enumerator was instantiated.");
+ }
+ }
+
+ public bool MoveNext ()
+ {
+ FailFast ();
+ if (current == null && !isAtStart)
+ return false;
+ current = isAtStart ? dict.root : current.next;
+ isAtStart = false;
+ return current != null;
+ }
+
+ public void Reset ()
+ {
+ FailFast ();
+ isAtStart = true;
+ current = null;
+ }
+
+ public object Current {
+ get { return Entry; }
+ }
+
+ private ListEntry ListEntry {
+ get {
+ FailFast ();
+ if (current == null)
+ throw new
InvalidOperationException (
+ "Enumerator is
positioned before the collection's first element or after the last element.");
+ return current;
+ }
+ }
+
+ // IDictionaryEnumerator
+ public DictionaryEntry Entry {
+ get {
+ object key = ListEntry.key;
+ return new DictionaryEntry (key,
current.value);
+ }
+ }
+
+ public object Key {
+ get { return ListEntry.key; }
+ }
+
+ public object Value {
+ get { return ListEntry.value; }
+ }
+ }
+
+ private class ListEntryCollection : ICollection {
+ private ListDictionary dict;
+ private bool isKeyList;
+
+ public ListEntryCollection (ListDictionary dict, bool
isKeyList)
+ {
+ this.dict = dict;
+ this.isKeyList = isKeyList;
+ }
+
+ // ICollection Interface
+ public int Count {
+ get { return dict.Count; }
+ }
+
+ public bool IsSynchronized {
+ get { return false; }
+ }
+
+ public object SyncRoot {
+ get { return dict.SyncRoot; }
+ }
+
+ public void CopyTo (Array array, int index)
+ {
+ if (array == null)
+ throw new ArgumentNullException
("array", "Array cannot be null.");
+ if (index < 0)
+ throw new ArgumentOutOfRangeException
("index", "index is less than 0");
+ if (index > array.Length)
+ throw new IndexOutOfRangeException
("index is too large");
+ if (Count > array.Length - index)
+ throw new ArgumentException ("Not
enough room in the array");
+
+ foreach (object obj in this)
+ array.SetValue (obj, index++);
+ }
+
+ // IEnumerable Interface
+ public IEnumerator GetEnumerator()
+ {
+ return new ListEntryCollectionEnumerator
(dict.GetEnumerator (), isKeyList);
+ }
+
+ private class ListEntryCollectionEnumerator :
IEnumerator {
+ private IDictionaryEnumerator inner;
+ private bool isKeyList;
+
+ public ListEntryCollectionEnumerator
(IDictionaryEnumerator inner, bool isKeyList)
+ {
+ this.inner = inner;
+ this.isKeyList = isKeyList;
+ }
+
+ public object Current {
+ get { return isKeyList ? inner.Key :
inner.Value; }
+ }
+
+ public bool MoveNext ()
+ {
+ return inner.MoveNext ();
+ }
+
+ public void Reset ()
+ {
+ inner.Reset ();
+ }
+ }
+ }
+ }
+}
Property changes on:
trunk/mcs/class/System/System.Collections.Specialized/ListDictionary.cs
___________________________________________________________________
Name: svn:eol-style
+ native
_______________________________________________
Mono-patches maillist - [email protected]
http://lists.ximian.com/mailman/listinfo/mono-patches
