1 2006-04-16 Jonathan Chambers <joncham@gmail.com>
3 * List.cs: Clear entry in RemoveAt after removing item.
6 2007-03-27 Alan McGovern <alan.mcgovern@gmail.com>
8 * List.cs: Optimized several methods to increase performance
10 2007-03-21 Juraj Skripsky <js@hotfeet.ch>
12 * List.cs (FindAllStackBits): Small optimization to the new code.
13 Built resulting List<T> directly as an array, wrap it in a List<T>
14 afterwards. Stop the filling of the result array as soon as all
15 matching items have been processed.
17 2007-03-20 Juan Cristóbal Olivares <juancri@gmail.com>
19 * List.cs (FindAll): Optimize FindAll using a bitmask to determine
20 the number of positive matches, this increases the performance in
21 all cases below 10,000,000 elements extensively:
24 old method: 00:00:00.0126610 (26x)
25 stackalloc bit method: 00:00:00.0004750 (1x)
26 array bit method: 00:00:00.0010700 (2x)
27 heap bit method: 00:00:00.0038830 (8x)
30 old method: 00:00:00.0139250 (24x)
31 stackalloc bit method: 00:00:00.0005670 (1x)
32 array bit method: 00:00:00.0010890 (2x)
33 heap bit method: 00:00:00.0034920 (6x)
36 old method: 00:00:00.0136110 (12x)
37 stackalloc bit method: 00:00:00.0011240 (1x)
38 array bit method: 00:00:00.0016450 (1.4x)
39 heap bit method: 00:00:00.0043110 (3x)
42 old method: 00:00:00.0175970 (3x)
43 stackalloc bit method: 00:00:00.0085630 (1.5x)
44 array bit method: 00:00:00.0055010 (1x)
45 heap bit method: 00:00:00.0099590 (1.8x)
48 old method: 00:00:00.0210330 (2x)
49 array bit method: 00:00:00.0100430 (1x)
50 heap bit method: 00:00:00.0154150 (1.5x)
53 old method: 00:00:00.1243730 (1.2x)
54 array bit method: 00:00:00.0973110 (1x)
55 heap bit method: 00:00:00.1285650 (1.3x)
58 old method: 00:00:00.9252570 (1x)
59 array bit method: 00:00:00.9632300 ( 1.05x)
60 heap bit method: 00:00:01.1098490 (1.20x)
62 2007-03-08 David Mitchell <dmitchell@logos.com>
64 * List.cs: Fix the case where List.set_Item(int index) throws
65 inappropriate exception when index is equal to List.Count
67 List.IndexOf(object item) and IList.Contains(object item) throw
68 exceptions when given invalid types.
70 IList.Add(object item) throws InvalidCastException when item is
71 not of the correct type.
73 2007-03-08 Gert Driesen <drieseng@users.sourceforge.net>
75 * Comparer.cs: Renamed IComparableOfTComparer<T> to GenericComparer<T>
76 to fix binary serialization compatibility with MS.
78 2007-03-05 David Mitchell <dmitchell@logos.com>
80 * Dictionary.cs: An instance of Dictionary<TKey,TValue> is
81 supposed to throw a KeyNotFoundException when
82 the user attempts to retrieve the value associated with a key that
83 is not in the dictionary.
85 On the other hand, an instance of IDictionary is supposed to
86 return null in similar circumstances.
88 2007-03-05 David Mitchell <dmitchell@logos.com>
90 * List.cs: Fix InsertRange bug (80930).
92 2006-09-15 Gert Driesen <drieseng@users.sourceforge.net>
94 * List.cs: Fixed binary serialization compatibility with MS.NET.
95 Increment version whenever _items is modified; this fixes version
98 2006-09-06 Zoltan Varga <vargaz@gmail.com>
100 * Dictionary.cs: Speed up get_Item/set_Item/GetPrev () a bit. Increase capacity
101 specified by the user so 'capacity' elements can really be added without resizing.
103 2006-07-12 Zoltan Varga <vargaz@gmail.com>
105 * Dictionary.cs: Swap order of parameters to cmp.Equals () to improve
106 compatibility with MS.NET and strange Equals () implementations.
108 2006-05-17 Kazuki Oikawa <kazuki@panicode.com>
110 * List.cs : implemented Sort(Comparison <T>).
112 2006-05-08 Atsushi Enomoto <atsushi@ximian.com>
114 * List.cs : use proper comparer in Contains(), IndexOf() and
115 LastIndexOf(). Patch by Kazuki Oikawa. Fixed bug #77277.
117 2006-03-16 Ankit Jain <jankit@novell.com>
119 * List.cs (CheckIndex): Check for -ve indices and allow index == size.
120 (Insert): Use CheckIndex.
122 2006-03-12 Zoltan Varga <vargaz@gmail.com>
124 * List.cs: Applied patch from <kazuki@panicode.com>. Fixes #77504.
126 2006-02-10 Martin Baulig <martin@ximian.com>
129 (IComparableOfTComparer): `T' must implement `IComparable<T>' and
132 Tue Jan 24 18:22:54 CET 2006 Paolo Molaro <lupus@ximian.com>
134 * Dictionary.cs: avoid long reminder operations.
136 2006-01-23 Raja R Harinath <rharinath@novell.com>
138 Speed up remove. Use 'dict[k]=v' as a self-tuning hint.
139 * Dictionary.cs (GetSlot): Move data-structure traversal to ...
140 (GetPrev): ... this. Returns the slot prior to the place we're
141 looking for, or null if that place is the head of the chain.
143 (this.set): Use it. Implement move-to-front on set.
145 * Dictionary.cs (ToTKey, ToTValue): New helpers to convert from
147 (IDictionary.this, IDictionary.Add): Use them.
148 (IDictionary.Contains, IDictionary.Remove): If the types don't
151 2006-01-19 Raja R Harinath <rharinath@novell.com>
153 Fix to pass new nunit tests.
154 * Dictionary.cs (ShimEnumerator): New class. Implement the
155 requirement that ((IDictionary) foo).GetEnumerator ().Current has
156 type DictionaryEntry.
157 (IDictionary.GetEnumerator): Use ShimEnumerator.
158 (Enumerator.Current): Now has type KeyValuePair<TKey, TValue>.
159 (Enumerator.MoveNext): Use VerifyState.
160 (Enumerator.VerifyState): Move validation of 'current' field to ...
161 (Enumerator.CurrentSlot): ... this.
162 (Enumerator.Current, Enumerator.IDictionaryEnumerator.Entry):
164 (CopyTo, ICollection.CopyTo): Use subtle reasoning to replace a
165 '>=' with a '>'. Don't throw an ArgumentException when
166 index==array.Length && Count==0.
167 (KeyCollection.CopyTo, ValueCollection.CopyTo): Likewise, and thus
168 obviate the need to check (dictionary.Count == 0).
170 2005-12-20 Sebastien Pouliot <sebastien@ximian.com>
172 * List.cs: Applied Atsushi's patch for Sort (bug 76361) now that the
173 generic versions of Array.Sort are implemented.
175 2005-12-19 Sebastien Pouliot <sebastien@ximian.com>
177 * Dictionary.cs: Added [Serializable] attribute to both inner
178 Enumerator struct in Key and Value inner collection classes.
179 * EqualityComparer.cs: Added missing IEqualityComparer interface.
180 * List.cs: Added [Serializable] attribute to both inner Enumerator
183 2005-12-19 Sebastien Pouliot <sebastien@ximian.com>
185 * Dictionary.cs: Fixed ICollection.CopyTo to use DictionaryEntry. Fixed
186 Key and Value CopyTo not to throw exception if the dictionary is empty
188 * List.cs: Fix exception reporting to match MS behaviour (2.0 final).
190 2005-11-19 Zoltan Varga <vargaz@gmail.com>
192 * KeyNotFoundException.cs: Add default message.
194 2005-09-18 Miguel de Icaza <miguel@novell.com>
196 * Dictionary.cs: Change style for internal fields.
198 If the capacity is zero, set the capacity to our default size as 0
199 is an allowed parameter in .NET
201 2005-08-10 Kamil Skalski <nazgul@nemerle.org>
203 * KeyValuePair.cs, Dictionary.cs: Change Key and Value to properties to match
204 .NET 2.0 July CTP. Update its use in Dictionary, since now we
205 cannot write to them.
207 2005-07-10 Kamil Skalski <nazgul@nemerle.org>
209 * Comparer.cs, EqualityComparer.cs: Use MakeGenericType instead of BindGenericParameters.
212 2005-06-27 Raja R Harinath <rharinath@novell.com>
214 Introduce some thread-safety by removing the modify-on-read
215 move-to-front heuristic.
216 * Dictionary.cs (_enumeratorGeneration, _enumerators): Remove.
217 (Count): Add internal property set. Invalidate enumerators when
218 Count is changed. Change all references of _usedSlots to Count.
219 (this): Invalidate enumerators when the value of some slot is
220 changed, even if the layout of the data-structure isn't modified.
221 (DoHash): Remove null-key check. All codepaths leading to this
222 function already have the check.
223 (GetSlot): Remove move-to-front heuristic.
226 2005-06-24 Martin Baulig <martin@ximian.com>
228 * IDictionary.cs: Use the same type parameter names than on MS.
230 * IDictionary.cs, Dictionary.cs: We don't need the `CLSCompliant'
233 2005-06-23 Martin Baulig <martin@ximian.com>
235 * *.cs: Removed the `[ComVisible(false)]' attributes everywhere.
237 2005-06-22 Raja R Harinath <rharinath@novell.com>
239 * Dictionary.cs (_generation, _enumeratorGeneration, _enumerators):
240 New fields to implement fail-fast semantics. All code that
241 modifies the table increment _generation.
242 (GetSlot): Use _hcp to compare keys. Return the slot containing
243 the key, rather than the index. Avoid move-to-front heuristic
244 when there's an enumerator coursing through the table.
245 (this, Add, TryGetValue, ContainsKey, Remove): Update to change.
246 (Enumerator.Enumerator): Save the generation of the dictionary.
247 (Enumerator.Dispose): Inform dictionary that the enumerator is no more.
248 (Enumerator.MoveNext, Enumerator.VerifyState): Fail if the
249 dictionary has been modified.
251 2005-06-20 David waite <mass@akuma.org>
253 * List.cs : substantial changes and optimizations
254 (AddCollection, AddEnumerable): new internal specializations of AddRange
255 (AsReadOnly): returns specific IList<T> to match ms.net 2.0b2 api.
256 (Clear): reset size to zero on clear
257 (ConvertAll): catch null converter, use Add to prevent OutOfBounds
259 (FindAll, FindIndex, FindLast, FindLastIndex, RemoveAll, TrueForAll):
261 (FindLastIndex): correct index parameters based on ms.net 2005b2 behavior
262 (ForEach): catch null action
263 (CheckIndex): new internal function similar to CheckRange for functions
264 which only provide a starting index
265 (InsertCollection, InsertEnumerable): new internal specializations of
267 (ReadOnlyList): removed, ReadOnlyCollection in
268 System.Collections.ObjectModel is used instead now
270 2005-06-16 David Waite <mass@akuma.org>
272 * Dictionary.cs (EnumerationMode): Remove.
273 (Enumerator): Remove return type flag - legacy return is expected to
274 always return a DictionaryEntry
275 (Enumerator): Make constructor internal, it is not public on ms.net
277 (VerifyState): Added method to check state preconditions and throw
278 appropriate exceptions.
279 (KeyCollection,ValueCollection): Mark sealed to match ms.net beta 2
280 (KeyCollection.Enumerator._hostEnumerator): make exact struct type,
281 rather than boxing and using by interface
282 (KeyCollection.Enumerator.Dispose): Call _hostEnumerator.Dispose.
283 (ValueCollection.Enumerator._hostEnumerator): make exact struct type,
284 rather than boxing and using by interface
285 (ValueCollection.Enumerator.Dispose): Call _hostEnumerator.Dispose.
286 * EqualityComparer.cs (DefaultComparer, IEquatableOfTEqualityComparer):
287 Mark as serializable.
289 2005-06-16 Raja R Harinath <rharinath@novell.com>
291 * Dictionary.cs (GetKeys, GetValues): Remove.
292 (SetThreshold): New function to calculate the resize threshold.
293 (CopyTo): Don't use foreach syntax.
294 (ContainsValue): Likewise. Use default equality comparer of the
296 (GetObjectData): Use CopyTo to copy into temporary array. Don't
297 save redundant _usedSlots and _threshold.
298 (OnDeserialization): Rewrite.
299 (ICollection<>.CopyTo): Forward to CopyTo.
300 (Enumerator._nextIndex): Rename to from _index.
301 (Enumerator._next, Enumerator.FixNext): Remove.
302 (Enumerator.Current): Rewrite to avoid need for _next.
303 (Enumerator.IEnumerator.Reset): Update.
304 (KeyCollection): Is also IEnumerable<TKey> and IEnumerable.
305 Update methods to conform to standard.
306 (KeyCollection.GetEnumerator): Restore. Return the correct type.
307 (KeyCollection.Enumerator): Rename from KeyEnumerator. Simple
308 wrapper that forwards to Dictionary<,>.Enumerator.
309 (ValueCollection): Likewise.
311 2005-06-12 David Waite <dwaite@gmail.com>
313 * IKeyComparer.cs: removed
314 * KeyValuePair.cs: add same-style ToString as ms.net Beta2 impl,
315 make Serializable, use correct field names.
316 * Dictionary.cs: Miscelaneus clean-ups, added serialization
317 support, use Hashtable prime functions
319 2005-06-12 Ben Maurer <bmaurer@ximian.com>
321 * Comparer.cs, EqualityComparer.cs: Important performance hack:
322 make sure that we don't box stuff and do reflection on every
323 comparison. We use reflection at cctor time rather than on every
326 2005-06-09 Raja R Harinath <rharinath@novell.com>
328 Simplify Enumerator.MoveNext to make it "obviously correct", rather
329 than require subtle reasoning about the state of various variables.
330 * Dictionary.cs (Enumerator._isValid): Remove. Replace all uses
331 with "_current == null".
332 (Enumerator._validNodeVisited): Remove.
333 (Enumerator._next): New. Holds the the next position.
334 (Enumerator.FixNest): New helper function that ensures that _next
336 (Enumerator.MoveNext): Simplify. Now, copies _next to _current
337 and advances _next if possible.
339 2005-06-08 Martin Baulig <martin@ximian.com>
341 * Dictionary.cs (Dictionary.KeyEnumerator): Removed the public
342 GetEnumerator() function since it's returning the wrong type.
343 (Dictionary.ValueEnumerator): Likewise. Fix #75073.
345 2005-06-08 Ankit Jain <ankit@corewars.org>
347 * Dictionary.cs (Dictionary<TKey, TValue>.MoveNext): Allow traversal of chain in last slot
348 of the table. Fixes #75168.
350 2005-06-04 Ben Maurer <bmaurer@ximian.com>
352 * *.cs: 2.0 api fixups
354 2005-05-26 Miguel de Icaza <miguel@novell.com>
356 * Dictionary.cs: Remove the `Hash' name from the Dictionary
357 internal classes, make them public.
359 2005-05-26 Zoltan Varga <vargaz@freemail.hu>
361 * Dictionary.cs: Fix a warning.
363 * IDictionary.cs: Add missing TryGetValue method.
365 2005-05-19 Geoff Norton <gnorton@customerdna.com>
367 * List.cs (Insert): Resize the array before the shift if needed
369 2005-05-18 Miguel de Icaza <miguel@novell.com>
371 * List.cs (GetRange): Implement.
373 Do not do lazy loading of data. Not worth adding an
374 extra check, and not worth the bugs.
376 This decision wont be discussed until: a) a full List regression
377 test suite exists and b) performance benchmarks are created. (b)
378 depends on (a) or the argument wont even be heard.
380 2005-05-13 Atsushi Enomoto <atsushi@ximian.com>
382 * Queue.cs, Stack.cs: moved to System.dll
384 2005-05-06 Martin Baulig <martin@ximian.com>
386 * *.cs: Add CLSCompliant(true) where missing.
388 2005-05-06 Zoltan Varga <vargaz@freemail.hu>
390 * *.cs: Remove CLSCompliant(false) attributes.
392 2005-05-05 Zoltan Varga <vargaz@freemail.hu>
394 * List.cs: Applied patch from Mart Roosmaa (roosmaa@gmail.com).
395 Fix Insert method. Fixes #74824.
397 2005-04-29 Martin Baulig <martin@ximian.com>
399 Reflect latest spec changes.
401 * IEnumerable.cs (IEnumerable<T>): Implement IEnumerable.
402 * IEnumerator.cs (IEnumerator<T>): Implement IEnumerator.
404 2005-04-29 Raja R Harinath <rharinath@novell.com>
407 * Dictionary.cs (Slot<K,V>): Move to ...
408 (Dictionary<K,V>.Slot): ... here.
410 2005-04-28 Martin Baulig <martin@ximian.com>
412 * Dictionary.cs, Queue.cs, Stack.cs, List.cs, Comparer.cs: Don't
413 duplicate type parameters in the nested classes.
415 2005-04-20 Zoltan Varga <vargaz@freemail.hu>
417 * List.cs: Fix ToArray () method. Fixes #74675.
419 2005-04-04 Raja R Harinath <rharinath@novell.com>
421 * Dictionary.cs: Update to draft of Feb 27. Add some argument checks.
422 (GetSlot): Don't throw KeyNotFoundException. Unify all list
423 traversals in here. Move found key to head of chain, and return
424 the index of the chain suitable for/containing the key.
425 (Item, Add, Remove): Simplify, and remove FIXMEs.
426 (Resize): Reuse linked list nodes from old table.
427 (Dictionary.CopyTo, HashKeyCollection.CopyTo, HashValueCollection.CopyTo):
428 Add some argument checks.
430 2005-04-02 Ben Maurer <bmaurer@ximian.com>
432 * Dictionary.cs: Real impl.
434 2005-02-21 Martin Baulig <martin@ximian.com>
436 * IComparer.cs: Reverted the last change here, Equals() and
437 GetHashCode() have been removed a long time ago.
439 2005-02-21 Kazuki Oikawa <kazuki@panicode.com>
441 * IComparer.cs, IDictionary.cs: Corrected the wrong declaration.
443 2005-02-11 Carlos Alberto Cortez <calberto.cortez@gmail.com>
445 * List.cs: Added internal ReadOnlyCollection class,
446 which is a wrapper for a read only IList<T> version of the List<T>.
447 Used in AsReadOnly () method.
449 2005-02-07 Ben Maurer <bmaurer@ximian.com>
451 * List.cs (CheckRange): Comparison error. Duh!
452 (Shift): really deal with neg. delta. Also, adjust the `size'.
454 Based on a patch from Marc Denty (marc.denty@libertysurf.fr).
458 2005-01-29 Ben Maurer <bmaurer@ximian.com>
460 * Queue.cs: `duh' bugs.
462 2004-12-27 Ben Maurer <bmaurer@ximian.com>
464 * Stack.cs: Stupid bug fixes.
466 * List.cs: My new (mostly untested ;-) impl of List
467 <T>. Implements most of the API.
469 2004-12-26 Ben Maurer <bmaurer@ximian.com>
471 * Queue.cs: New, non-linked-list based impl.
473 2004-11-29 Ben Maurer <bmaurer@ximian.com>
475 * Comparer.cs: Update this class.
477 2004-11-25 Carlos Alberto Cortez <calberto.cortez@gmail.com>
479 * List.cs: Enumerator changed to behave like the MS impl.
481 2004-11-25 Ben Maurer <bmaurer@ximian.com>
483 * Stack.cs: New, list based impl. Waiting for some gmcs fixes.
485 2004-11-10 Martin Baulig <martin@ximian.com>
487 * IDictionary.cs (IDictionary): `IsReadOnly' and `Clear' are
488 inherited from ICollection.
490 2004-09-20 Gert Driesen <drieseng@users.sourceforge.net>
492 * ReadOnlyCollection.cs: Moved to System assembly
493 * Collection.cs: Moved to System assembly
495 2004-09-07 Carlos Alberto Cortez <carlos@unixmexico.org>
497 * ReadOnlyCollection.cs: New file and changes to
498 Collection.cs tu support it.
500 2004-09-05 Marek Safar <marek.safar@seznam.cz>
502 * Dictionary.cs: Added new file (no implementation).
504 2004-09-03 Carlos Alberto Cortez <carlos@unixmexico.org>
506 * Collection.cs: Small improvements related to
507 style, resizing, and type checking.
509 2004-09-01 Carlos Alberto Cortez <carlos@unixmexico.org>
511 * Collection.cs: New file.
513 2004-08-04 Martin Baulig <martin@ximian.com>
515 * List.cs (List<T>.Enumerator): Made this a struct.
516 (List<T>.GetEnumerator): The public method now returns the
519 2004-08-02 Martin Baulig <martin@ximian.com>
521 Started to do some API review.
523 * ICollection.cs (ICollection<T>): Added IsReadOnly, Add, Clear,
526 * IList.cs (IList<T>): Removed Add, Clear, Constains, Remove,
527 IsReadOnly and IsFixedSize.
529 2004-08-02 Martin Baulig <martin@ximian.com>
531 * IList.cs (IList.Add): Changed return type to void.
533 * List.cs (List.Add): Likewise.
535 2004-07-16 Martin Baulig <martin@ximian.com>
537 * IComparable.cs: Removed, it's in System.
539 2004-07-12 Duncan Mak <duncan@ximian.com>
541 * KeyNotFoundException.cs: Added.
543 2004-06-18 Ben Maurer <bmaurer@ximian.com>
545 * Comparer.cs: v2 impl. Some workarounds for gmcs are enabled.
547 2004-05-26 Sebastien Pouliot <sebastien@ximian.com>
549 * Queue.cs: Fixed possible integer overflow in CopyTo methods.
550 * Stack.cs: Fixed possible integer overflow in CopyTo methods.
552 2004-03-13 Martin Baulig <martin@ximian.com>
554 * Stack.cs, Queue.cs, List.cs: Implement the non-generic interfaces.
556 2004-03-11 Martin Baulig <martin@ximian.com>
560 2004-03-11 Martin Baulig <martin@ximian.com>
562 * Stack.cs, Queue.cs: Just use `Node' for the nested class, not
563 `Node<T>' (which would create another type parameter `T'
564 overriding `T' from the outer class).
566 2004-02-23 Martin Baulig <martin@ximian.com>
568 * Stack.cs, Queue.cs: New files. Hmm, looks like I forgot to add
569 them to CVS; they're already on my hard disk since December or so.
571 2003-12-08 Martin Baulig <martin@ximian.com>
573 * *.cs: require GENERICS.
575 2003-11-08 Ben Maurer <bmaurer@users.sourceforge.net>
577 * *.cs: require NET_2_0 and GENERICS
579 2003-11-07 Ben Maurer <bmaurer@users.sourceforge.net>
581 * IComparable.cs, IComparer.cs, IDictionary.cs, IKeyComparer.cs, KeyValuePair.cs
584 2003-11-06 Martin Baulig <martin@ximian.com>
586 * ICollection.cs, IList.cs, IEnumerator.cs, IEnumerable.cs:
587 Started to implement the System.Collections.Generic classes.