mcs/class/corlib/System.Collections/Hashtable.cs

   1 //
   2 // System.Collections.Hashtable.cs
   3 //
   4 // Author:
   5 //   Sergey Chaban (serge@wildwestsoftware.com)
   6 //
   7
   8 //
   9 // Copyright (C) 2004-2005 Novell, Inc (http://www.novell.com)
  10 //
  11 // Permission is hereby granted, free of charge, to any person obtaining
  12 // a copy of this software and associated documentation files (the
  13 // "Software"), to deal in the Software without restriction, including
  14 // without limitation the rights to use, copy, modify, merge, publish,
  15 // distribute, sublicense, and/or sell copies of the Software, and to
  16 // permit persons to whom the Software is furnished to do so, subject to
  17 // the following conditions:
  18 //
  19 // The above copyright notice and this permission notice shall be
  20 // included in all copies or substantial portions of the Software.
  21 //
  22 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  23 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  24 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  25 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  26 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  27 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  28 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  29 //
  30
  31 using System;
  32 using System.Collections;
  33 using System.Runtime.Serialization;
  34
  35 #if NET_2_0
  36 using System.Runtime.ConstrainedExecution;
  37 using System.Runtime.InteropServices;
  38 #endif
  39
  40 namespace System.Collections {
  41
  42 #if NET_2_0
  43         [ComVisible(true)]
  44 #endif
  45         [Serializable]
  46         public class Hashtable : IDictionary, ICollection,
  47                 IEnumerable, ICloneable, ISerializable, IDeserializationCallback
  48         {
  49
  50                 [Serializable]
  51                 internal struct Slot {
  52                         internal Object key;
  53
  54                         internal Object value;
  55
  56                         // Hashcode. Chains are also marked through this.
  57                         internal int hashMix;
  58                 }
  59
  60                 [Serializable]
  61                 internal class KeyMarker: IObjectReference
  62                 {
  63                         public readonly static KeyMarker Removed = new KeyMarker();
  64                         public object GetRealObject (StreamingContext context)
  65                         { return KeyMarker.Removed; }
  66                 }
  67
  68                 //
  69                 // Private data
  70                 //
  71
  72                 const int CHAIN_MARKER  = ~Int32.MaxValue;
  73
  74
  75                 private int inUse;
  76                 private int modificationCount;
  77                 private float loadFactor;
  78                 private Slot [] table;
  79                 private int threshold;
  80
  81                 private HashKeys hashKeys;
  82                 private HashValues hashValues;
  83
  84                 private IHashCodeProvider hcpRef;
  85                 private IComparer comparerRef;
  86                 private SerializationInfo serializationInfo;
  87
  88 #if NET_2_0
  89                 private IEqualityComparer equalityComparer;
  90 #endif
  91
  92                 private static readonly int [] primeTbl = {
  93                         11,
  94                         19,
  95                         37,
  96                         73,
  97                         109,
  98                         163,
  99                         251,
 100                         367,
 101                         557,
 102                         823,
 103                         1237,
 104                         1861,
 105                         2777,
 106                         4177,
 107                         6247,
 108                         9371,
 109                         14057,
 110                         21089,
 111                         31627,
 112                         47431,
 113                         71143,
 114                         106721,
 115                         160073,
 116                         240101,
 117                         360163,
 118                         540217,
 119                         810343,
 120                         1215497,
 121                         1823231,
 122                         2734867,
 123                         4102283,
 124                         6153409,
 125                         9230113,
 126                         13845163
 127                 };
 128
 129                 //
 130                 // Constructors
 131                 //
 132
 133                 public Hashtable () : this (0, 1.0f) {}
 134
 135 #if NET_2_0
 136                 [Obsolete ("Please use Hashtable(int, float, IEqualityComparer) instead")]
 137 #endif
 138                 public Hashtable (int capacity, float loadFactor, IHashCodeProvider hcp, IComparer comparer) {
 139                         if (capacity<0)
 140                                 throw new ArgumentOutOfRangeException ("capacity", "negative capacity");
 141
 142                         if (loadFactor < 0.1f || loadFactor > 1.0f || Single.IsNaN (loadFactor))
 143                                 throw new ArgumentOutOfRangeException ("loadFactor", "load factor");
 144
 145                         if (capacity == 0) ++capacity;
 146                         this.loadFactor = 0.75f*loadFactor;
 147                         double tableSize = capacity / this.loadFactor;
 148
 149                         if (tableSize > Int32.MaxValue)
 150                                 throw new ArgumentException ("Size is too big");
 151
 152                         int size = (int) tableSize;
 153                         size = ToPrime (size);
 154                         this.SetTable (new Slot [size]);
 155
 156                         this.hcp = hcp;
 157                         this.comparer = comparer;
 158
 159                         this.inUse = 0;
 160                         this.modificationCount = 0;
 161                 }
 162
 163                 public Hashtable (int capacity, float loadFactor) :
 164                         this (capacity, loadFactor, null, null)
 165                 {
 166                 }
 167
 168                 public Hashtable (int capacity) : this (capacity, 1.0f)
 169                 {
 170                 }
 171
 172 #if NET_2_0
 173                 [Obsolete ("Please use Hashtable(int, IEqualityComparer) instead")]
 174 #endif
 175                 public Hashtable (int capacity,
 176                                   IHashCodeProvider hcp,
 177                                   IComparer comparer)
 178                         : this (capacity, 1.0f, hcp, comparer)
 179                 {
 180                 }
 181
 182 #if NET_2_0
 183                 [Obsolete ("Please use Hashtable(IDictionary, float, IEqualityComparer) instead")]
 184 #endif
 185                 public Hashtable (IDictionary d, float loadFactor,
 186                                   IHashCodeProvider hcp, IComparer comparer)
 187                         : this (d!=null ? d.Count : 0,
 188                                 loadFactor, hcp, comparer)
 189                 {
 190
 191                         if (d  ==  null)
 192                                 throw new ArgumentNullException ("dictionary");
 193
 194                         IDictionaryEnumerator it = d.GetEnumerator ();
 195                         while (it.MoveNext ()) {
 196                                 Add (it.Key, it.Value);
 197                         }
 198
 199                 }
 200
 201                 public Hashtable (IDictionary d, float loadFactor)
 202                        : this (d, loadFactor, null, null)
 203                 {
 204                 }
 205
 206
 207                 public Hashtable (IDictionary d) : this (d, 1.0f)
 208                 {
 209                 }
 210
 211 #if NET_2_0
 212                 [Obsolete ("Please use Hashtable(IDictionary, IEqualityComparer) instead")]
 213 #endif
 214                 public Hashtable (IDictionary d, IHashCodeProvider hcp, IComparer comparer)
 215                                  : this (d, 1.0f, hcp, comparer)
 216                 {
 217                 }
 218
 219 #if NET_2_0
 220                 [Obsolete ("Please use Hashtable(IEqualityComparer) instead")]
 221 #endif
 222                 public Hashtable (IHashCodeProvider hcp, IComparer comparer)
 223                                  : this (1, 1.0f, hcp, comparer)
 224                 {
 225                 }
 226
 227                 protected Hashtable (SerializationInfo info, StreamingContext context)
 228                 {
 229                         serializationInfo = info;
 230                 }
 231
 232 #if NET_2_0
 233                 public Hashtable (IDictionary d, IEqualityComparer equalityComparer) : this (d, 1.0f, equalityComparer)
 234                 {
 235                 }
 236
 237                 public Hashtable (IDictionary d, float loadFactor, IEqualityComparer equalityComparer) : this (d, loadFactor)
 238                 {
 239                         this.equalityComparer = equalityComparer;
 240                 }
 241
 242                 public Hashtable (IEqualityComparer equalityComparer) : this (1, 1.0f, equalityComparer)
 243                 {
 244                 }
 245
 246                 public Hashtable (int capacity, IEqualityComparer equalityComparer) : this (capacity, 1.0f, equalityComparer)
 247                 {
 248                 }
 249
 250                 public Hashtable (int capacity, float loadFactor, IEqualityComparer equalityComparer) : this (capacity, loadFactor)
 251                 {
 252                         this.equalityComparer = equalityComparer;
 253                 }
 254 #endif
 255
 256                 //
 257                 // Properties
 258                 //
 259
 260 #if NET_2_0
 261                 [Obsolete ("Please use EqualityComparer property.")]
 262 #endif
 263                 protected IComparer comparer {
 264                         set {
 265                                 comparerRef = value;
 266                         }
 267                         get {
 268                                 return comparerRef;
 269                         }
 270                 }
 271
 272 #if NET_2_0
 273                 [Obsolete ("Please use EqualityComparer property.")]
 274 #endif
 275                 protected IHashCodeProvider hcp {
 276                         set {
 277                                 hcpRef = value;
 278                         }
 279                         get {
 280                                 return hcpRef;
 281                         }
 282                 }
 283
 284 #if NET_2_0
 285                 protected IEqualityComparer EqualityComparer {
 286                         get {
 287                                 return equalityComparer;
 288                         }
 289                 }
 290 #endif
 291
 292                 // ICollection
 293
 294                 public virtual int Count {
 295                         get {
 296                                 return inUse;
 297                         }
 298                 }
 299
 300                 public virtual bool IsSynchronized {
 301                         get {
 302                                 return false;
 303                         }
 304                 }
 305
 306                 public virtual Object SyncRoot {
 307                         get {
 308                                 return this;
 309                         }
 310                 }
 311
 312
 313
 314                 // IDictionary
 315
 316                 public virtual bool IsFixedSize {
 317                         get {
 318                                 return false;
 319                         }
 320                 }
 321
 322
 323                 public virtual bool IsReadOnly {
 324                         get {
 325                                 return false;
 326                         }
 327                 }
 328
 329                 public virtual ICollection Keys {
 330                         get {
 331                                 if (this.hashKeys == null)
 332                                         this.hashKeys = new HashKeys (this);
 333                                 return this.hashKeys;
 334                         }
 335                 }
 336
 337                 public virtual ICollection Values {
 338                         get {
 339                                 if (this.hashValues == null)
 340                                         this.hashValues = new HashValues (this);
 341                                 return this.hashValues;
 342                         }
 343                 }
 344
 345
 346
 347                 public virtual Object this [Object key] {
 348                         get {
 349                                 if (key == null)
 350                                         throw new ArgumentNullException ("key", "null key");
 351
 352                                 Slot [] table = this.table;
 353                                 uint size = (uint) table.Length;
 354                                 int h = this.GetHash (key) & Int32.MaxValue;
 355                                 uint indx = (uint)h;
 356                                 uint step = (uint) ((h >> 5)+1) % (size-1)+1;
 357
 358
 359                                 for (uint i = size; i > 0; i--) {
 360                                         indx %= size;
 361                                         Slot entry = table [indx];
 362                                         Object k = entry.key;
 363                                         if (k == null)
 364                                                 break;
 365
 366                                         if (k == key || ((entry.hashMix & Int32.MaxValue) == h
 367                                             && this.KeyEquals (key, k))) {
 368                                                 return entry.value;
 369                                         }
 370
 371                                         if ((entry.hashMix & CHAIN_MARKER) == 0)
 372                                                 break;
 373
 374                                         indx += step;
 375                                 }
 376
 377                                 return null;
 378                         }
 379
 380                         set {
 381                                 PutImpl (key, value, true);
 382                         }
 383                 }
 384
 385
 386
 387
 388                 //
 389                 // Interface methods
 390                 //
 391
 392
 393                 // IEnumerable
 394
 395                 IEnumerator IEnumerable.GetEnumerator ()
 396                 {
 397                         return new Enumerator (this, EnumeratorMode.ENTRY_MODE);
 398                 }
 399
 400
 401                 // ICollection
 402                 public virtual void CopyTo (Array array, int arrayIndex)
 403                 {
 404                         if (null == array)
 405                                 throw new ArgumentNullException ("array");
 406
 407                         if (arrayIndex < 0)
 408                                 throw new ArgumentOutOfRangeException ("arrayIndex");
 409
 410                         if (array.Rank > 1)
 411                                 throw new ArgumentException ("array is multidimensional");
 412
 413                         if ((array.Length > 0) && (arrayIndex >= array.Length))
 414                                 throw new ArgumentException ("arrayIndex is equal to or greater than array.Length");
 415
 416                         if (arrayIndex + this.inUse > array.Length)
 417                                 throw new ArgumentException ("Not enough room from arrayIndex to end of array for this Hashtable");
 418
 419                         IDictionaryEnumerator it = GetEnumerator ();
 420                         int i = arrayIndex;
 421
 422                         while (it.MoveNext ()) {
 423                                 array.SetValue (it.Entry, i++);
 424                         }
 425                 }
 426
 427
 428                 // IDictionary
 429
 430                 public virtual void Add (Object key, Object value)
 431                 {
 432                         PutImpl (key, value, false);
 433                 }
 434
 435 #if NET_2_0
 436                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
 437 #endif
 438                 public virtual void Clear ()
 439                 {
 440                         for (int i = 0;i<table.Length;i++) {
 441                                 table [i].key = null;
 442                                 table [i].value = null;
 443                                 table [i].hashMix = 0;
 444                         }
 445
 446                         inUse = 0;
 447                         modificationCount++;
 448                 }
 449
 450                 public virtual bool Contains (Object key)
 451                 {
 452                         return (Find (key) >= 0);
 453                 }
 454
 455                 public virtual IDictionaryEnumerator GetEnumerator ()
 456                 {
 457                         return new Enumerator (this, EnumeratorMode.ENTRY_MODE);
 458                 }
 459
 460 #if NET_2_0
 461                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
 462 #endif
 463                 public virtual void Remove (Object key)
 464                 {
 465                         int i = Find (key);
 466                         if (i >= 0) {
 467                                 Slot [] table = this.table;
 468                                 int h = table [i].hashMix;
 469                                 h &= CHAIN_MARKER;
 470                                 table [i].hashMix = h;
 471                                 table [i].key = (h != 0)
 472                                               ? KeyMarker.Removed
 473                                               : null;
 474                                 table [i].value = null;
 475                                 --inUse;
 476                                 ++modificationCount;
 477                         }
 478                 }
 479
 480                 public virtual bool ContainsKey (object key)
 481                 {
 482                         return Contains (key);
 483                 }
 484
 485                 public virtual bool ContainsValue (object value)
 486                 {
 487                         int size = this.table.Length;
 488                         Slot [] table = this.table;
 489                         if (value == null) {
 490                                 for (int i = 0; i < size; i++) {
 491                                         Slot entry = table [i];
 492                                         if (entry.key != null && entry.key!= KeyMarker.Removed
 493                                         && entry.value == null) {
 494                                                 return true;
 495                                         }
 496                                 }
 497                         } else {
 498                                 for (int i = 0; i < size; i++) {
 499                                         Slot entry = table [i];
 500                                         if (entry.key != null && entry.key!= KeyMarker.Removed
 501                                         && value.Equals (entry.value)) {
 502                                                 return true;
 503                                         }
 504                                 }
 505                         }
 506                         return false;
 507                 }
 508
 509
 510                 // ICloneable
 511
 512                 public virtual object Clone ()
 513                 {
 514 #if NET_2_0
 515                         Hashtable ht = new Hashtable (Count, equalityComparer);
 516                         ht.hcp = this.hcp;
 517                         ht.comparer = this.comparer;
 518 #else
 519                         Hashtable ht = new Hashtable (Count, hcp, comparer);
 520 #endif
 521                         ht.inUse = 0;
 522                         ht.loadFactor = this.loadFactor;
 523
 524                         // FIXME: maybe it's faster to simply
 525                         //        copy the back-end array?
 526
 527                         IDictionaryEnumerator it = GetEnumerator ();
 528                         while (it.MoveNext ()) {
 529                                 ht [it.Key] = it.Value;
 530                         }
 531
 532                         return ht;
 533                 }
 534
 535 #if NET_2_0
 536                 [MonoTODO ("Serialize equalityComparer")]
 537 #endif
 538                 public virtual void GetObjectData (SerializationInfo info, StreamingContext context)
 539                 {
 540                         if (info == null)
 541                                 throw new ArgumentNullException ("info");
 542
 543                         info.AddValue ("LoadFactor", loadFactor);
 544                         info.AddValue ("Version", modificationCount);
 545                         info.AddValue ("Comparer", comparerRef);
 546                         info.AddValue ("HashCodeProvider", hcpRef);
 547                         info.AddValue ("HashSize", this.table.Length);
 548 // Create Keys
 549                         Object [] keys = new Object[inUse];
 550                         CopyToArray(keys, 0, EnumeratorMode.KEY_MODE);
 551
 552 // Create Values
 553                         Object [] values = new Object[inUse];
 554                         CopyToArray(values, 0, EnumeratorMode.VALUE_MODE);
 555
 556                         info.AddValue ("Keys", keys);
 557                         info.AddValue ("Values", values);
 558
 559                 }
 560
 561 #if NET_2_0
 562                 [MonoTODO ("Serialize equalityComparer")]
 563 #endif
 564                 public virtual void OnDeserialization (object sender)
 565                 {
 566                         if (serializationInfo == null) return;
 567
 568                         loadFactor = (float) serializationInfo.GetValue ("LoadFactor", typeof(float));
 569                         modificationCount = (int) serializationInfo.GetValue ("Version", typeof(int));
 570                         comparerRef = (IComparer) serializationInfo.GetValue ("Comparer", typeof (object));
 571                         hcpRef = (IHashCodeProvider) serializationInfo.GetValue ("HashCodeProvider", typeof (object));
 572                         int size = (int) serializationInfo.GetValue ("HashSize", typeof(int));
 573
 574                         Object [] keys = (Object []) serializationInfo.GetValue("Keys", typeof(Object [] ));
 575                         Object [] values = (Object []) serializationInfo.GetValue("Values", typeof(Object [] ));
 576
 577                         if (keys.Length != values.Length)
 578                           throw new SerializationException("Keys and values of uneven size");
 579
 580                         size = ToPrime (size);
 581                         this.SetTable (new Slot [size]);
 582
 583                         for(int i=0;i<keys.Length;i++)
 584                                 Add(keys[i], values[i]);
 585
 586                         AdjustThreshold();
 587
 588                         serializationInfo = null;
 589                 }
 590
 591                 /// <summary>
 592                 ///  Returns a synchronized (thread-safe)
 593                 ///  wrapper for the Hashtable.
 594                 /// </summary>
 595                 public static Hashtable Synchronized (Hashtable table)
 596                 {
 597                         if (table == null)
 598                                 throw new ArgumentNullException("table");
 599                         return new SyncHashtable (table);
 600                 }
 601
 602
 603
 604                 //
 605                 // Protected instance methods
 606                 //
 607
 608                 /// <summary>Returns the hash code for the specified key.</summary>
 609                 protected virtual int GetHash (Object key)
 610                 {
 611 #if NET_2_0
 612                         if (equalityComparer != null)
 613                                 return equalityComparer.GetHashCode (key);
 614 #endif
 615                         if (hcpRef == null)
 616                                 return key.GetHashCode ();
 617
 618                         return hcpRef.GetHashCode (key);
 619                 }
 620
 621                 /// <summary>
 622                 ///  Compares a specific Object with a specific key
 623                 ///  in the Hashtable.
 624                 /// </summary>
 625                 protected virtual bool KeyEquals (Object item, Object key)
 626                 {
 627 #if NET_2_0
 628                         if (equalityComparer != null)
 629                                 return equalityComparer.Equals (item, key);
 630 #endif
 631                         if (comparerRef == null)
 632                                 return item.Equals (key);
 633
 634                         return comparerRef.Compare (item, key) == 0;
 635                 }
 636
 637
 638
 639                 //
 640                 // Private instance methods
 641                 //
 642
 643                 private void AdjustThreshold ()
 644                 {
 645                         int size = table.Length;
 646
 647                         threshold = (int) (size*loadFactor);
 648                         if (this.threshold >= size)
 649                                 threshold = size-1;
 650                 }
 651
 652                 private void SetTable (Slot [] table)
 653                 {
 654                         if (table == null)
 655                                 throw new ArgumentNullException ("table");
 656
 657                         this.table = table;
 658                         AdjustThreshold ();
 659                 }
 660
 661                 private int Find (Object key)
 662                 {
 663                         if (key == null)
 664                                 throw new ArgumentNullException ("key", "null key");
 665
 666                         Slot [] table = this.table;
 667                         uint size = (uint) table.Length;
 668                         int h = this.GetHash (key) & Int32.MaxValue;
 669                         uint indx = (uint)h;
 670                         uint step = (uint) ((h >> 5)+1) % (size-1)+1;
 671
 672
 673                         for (uint i = size; i > 0; i--) {
 674                                 indx %= size;
 675                                 Slot entry = table [indx];
 676                                 Object k = entry.key;
 677                                 if (k == null)
 678                                         break;
 679
 680                                 if (k == key || ((entry.hashMix & Int32.MaxValue) == h
 681                                     && this.KeyEquals (key, k))) {
 682                                         return (int) indx;
 683                                 }
 684
 685                                 if ((entry.hashMix & CHAIN_MARKER) == 0)
 686                                         break;
 687
 688                                 indx += step;
 689                         }
 690                         return -1;
 691                 }
 692
 693
 694                 private void Rehash ()
 695                 {
 696                         int oldSize = this.table.Length;
 697
 698                         // From the SDK docs:
 699                         //   Hashtable is automatically increased
 700                         //   to the smallest prime number that is larger
 701                         //   than twice the current number of Hashtable buckets
 702                         uint newSize = (uint)ToPrime ((oldSize<<1)|1);
 703
 704
 705                         Slot [] newTable = new Slot [newSize];
 706                         Slot [] table = this.table;
 707
 708                         for (int i = 0;i<oldSize;i++) {
 709                                 Slot s = table [i];
 710                                 if (s.key!= null) {
 711                                         int h = s.hashMix & Int32.MaxValue;
 712                                         uint spot = (uint)h;
 713                                         uint step = ((uint) (h>>5)+1)% (newSize-1)+1;
 714                                         for (uint j = spot%newSize;;spot+= step, j = spot%newSize) {
 715                                                 // No check for KeyMarker.Removed here,
 716                                                 // because the table is just allocated.
 717                                                 if (newTable [j].key == null) {
 718                                                         newTable [j].key = s.key;
 719                                                         newTable [j].value = s.value;
 720                                                         newTable [j].hashMix |= h;
 721                                                         break;
 722                                                 } else {
 723                                                         newTable [j].hashMix |= CHAIN_MARKER;
 724                                                 }
 725                                         }
 726                                 }
 727                         }
 728
 729                         ++this.modificationCount;
 730
 731                         this.SetTable (newTable);
 732                 }
 733
 734
 735                 private void PutImpl (Object key, Object value, bool overwrite)
 736                 {
 737                         if (key == null)
 738                                 throw new ArgumentNullException ("key", "null key");
 739
 740                         if (this.inUse >= this.threshold)
 741                                 this.Rehash ();
 742
 743                         uint size = (uint)this.table.Length;
 744
 745                         int h = this.GetHash (key) & Int32.MaxValue;
 746                         uint spot = (uint)h;
 747                         uint step = (uint) ((spot>>5)+1)% (size-1)+1;
 748                         Slot [] table = this.table;
 749                         Slot entry;
 750
 751                         int freeIndx = -1;
 752                         for (int i = 0; i < size; i++) {
 753                                 int indx = (int) (spot % size);
 754                                 entry = table [indx];
 755
 756                                 if (freeIndx == -1
 757                                     && entry.key == KeyMarker.Removed
 758                                     && (entry.hashMix & CHAIN_MARKER) != 0)
 759                                         freeIndx = indx;
 760
 761                                 if (entry.key == null ||
 762                                     (entry.key == KeyMarker.Removed
 763                                      && (entry.hashMix & CHAIN_MARKER) == 0)) {
 764
 765                                         if (freeIndx == -1)
 766                                                 freeIndx = indx;
 767                                         break;
 768                                 }
 769
 770                                 if ((entry.hashMix & Int32.MaxValue) == h && KeyEquals (key, entry.key)) {
 771                                         if (overwrite) {
 772                                                 table [indx].value = value;
 773                                                 ++this.modificationCount;
 774                                         } else {
 775                                                 // Handle Add ():
 776                                                 // An entry with the same key already exists in the Hashtable.
 777                                                 throw new ArgumentException (
 778                                                                 "Key duplication when adding: " + key);
 779                                         }
 780                                         return;
 781                                 }
 782
 783                                 if (freeIndx == -1) {
 784                                         table [indx].hashMix |= CHAIN_MARKER;
 785                                 }
 786
 787                                 spot+= step;
 788
 789                         }
 790
 791                         if (freeIndx!= -1) {
 792                                 table [freeIndx].key = key;
 793                                 table [freeIndx].value = value;
 794                                 table [freeIndx].hashMix |= h;
 795
 796                                 ++this.inUse;
 797                                 ++this.modificationCount;
 798                         }
 799
 800                 }
 801
 802                 private void  CopyToArray (Array arr, int i,
 803                                            EnumeratorMode mode)
 804                 {
 805                         IEnumerator it = new Enumerator (this, mode);
 806
 807                         while (it.MoveNext ()) {
 808                                 arr.SetValue (it.Current, i++);
 809                         }
 810                 }
 811
 812
 813
 814                 //
 815                 // Private static methods
 816                 //
 817                 internal static bool TestPrime (int x)
 818                 {
 819                         if ((x & 1) != 0) {
 820                                 int top = (int)Math.Sqrt (x);
 821
 822                                 for (int n = 3; n < top; n += 2) {
 823                                         if ((x % n) == 0)
 824                                                 return false;
 825                                 }
 826                                 return true;
 827                         }
 828                         // There is only one even prime - 2.
 829                         return (x == 2);
 830                 }
 831
 832                 internal static int CalcPrime (int x)
 833                 {
 834                         for (int i = (x & (~1))-1; i< Int32.MaxValue; i += 2) {
 835                                 if (TestPrime (i)) return i;
 836                         }
 837                         return x;
 838                 }
 839
 840                 internal static int ToPrime (int x)
 841                 {
 842                         for (int i = 0; i < primeTbl.Length; i++) {
 843                                 if (x <= primeTbl [i])
 844                                         return primeTbl [i];
 845                         }
 846                         return CalcPrime (x);
 847                 }
 848
 849
 850
 851
 852                 //
 853                 // Inner classes
 854                 //
 855
 856                 private enum EnumeratorMode : int {KEY_MODE = 0, VALUE_MODE, ENTRY_MODE};
 857
 858                 [Serializable]
 859                 private sealed class Enumerator : IDictionaryEnumerator, IEnumerator {
 860
 861                         private Hashtable host;
 862                         private int stamp;
 863                         private int pos;
 864                         private int size;
 865                         private EnumeratorMode mode;
 866
 867                         private Object currentKey;
 868                         private Object currentValue;
 869
 870                         private readonly static string xstr = "Hashtable.Enumerator: snapshot out of sync.";
 871
 872                         public Enumerator (Hashtable host, EnumeratorMode mode) {
 873                                 this.host = host;
 874                                 stamp = host.modificationCount;
 875                                 size = host.table.Length;
 876                                 this.mode = mode;
 877                                 Reset ();
 878                         }
 879
 880                         public Enumerator (Hashtable host)
 881                                    : this (host, EnumeratorMode.KEY_MODE) {}
 882
 883
 884                         private void FailFast ()
 885                         {
 886                                 if (host.modificationCount != stamp) {
 887                                         throw new InvalidOperationException (xstr);
 888                                 }
 889                         }
 890
 891                         public void Reset ()
 892                         {
 893                                 FailFast ();
 894
 895                                 pos = -1;
 896                                 currentKey = null;
 897                                 currentValue = null;
 898                         }
 899
 900                         public bool MoveNext ()
 901                         {
 902                                 FailFast ();
 903
 904                                 if (pos < size) {
 905                                         while (++pos < size) {
 906                                                 Slot entry = host.table [pos];
 907
 908                                                 if (entry.key != null && entry.key != KeyMarker.Removed) {
 909                                                         currentKey = entry.key;
 910                                                         currentValue = entry.value;
 911                                                         return true;
 912                                                 }
 913                                         }
 914                                 }
 915
 916                                 currentKey = null;
 917                                 currentValue = null;
 918                                 return false;
 919                         }
 920
 921                         public DictionaryEntry Entry
 922                         {
 923                                 get {
 924                                         if (currentKey == null) throw new InvalidOperationException ();
 925                                         FailFast ();
 926                                         return new DictionaryEntry (currentKey, currentValue);
 927                                 }
 928                         }
 929
 930                         public Object Key {
 931                                 get {
 932                                         if (currentKey == null) throw new InvalidOperationException ();
 933                                         FailFast ();
 934                                         return currentKey;
 935                                 }
 936                         }
 937
 938                         public Object Value {
 939                                 get {
 940                                         if (currentKey == null) throw new InvalidOperationException ();
 941                                         FailFast ();
 942                                         return currentValue;
 943                                 }
 944                         }
 945
 946                         public Object Current {
 947                                 get {
 948                                         if (currentKey == null) throw new InvalidOperationException ();
 949
 950                                         switch (mode) {
 951                                         case EnumeratorMode.KEY_MODE:
 952                                                 return currentKey;
 953                                         case EnumeratorMode.VALUE_MODE:
 954                                                 return currentValue;
 955                                         case EnumeratorMode.ENTRY_MODE:
 956                                                 return new DictionaryEntry (currentKey, currentValue);
 957                                         }
 958                                         throw new Exception ("should never happen");
 959                                 }
 960                         }
 961                 }
 962
 963                 [Serializable]
 964                 private class HashKeys : ICollection, IEnumerable {
 965
 966                         private Hashtable host;
 967
 968                         public HashKeys (Hashtable host) {
 969                                 if (host == null)
 970                                         throw new ArgumentNullException ();
 971
 972                                 this.host = host;
 973                         }
 974
 975                         // ICollection
 976
 977                         public virtual int Count {
 978                                 get {
 979                                         return host.Count;
 980                                 }
 981                         }
 982
 983                         public virtual bool IsSynchronized {
 984                                 get {
 985                                         return host.IsSynchronized;
 986                                 }
 987                         }
 988
 989                         public virtual Object SyncRoot {
 990                                 get {return host.SyncRoot;}
 991                         }
 992
 993                         public virtual void CopyTo (Array array, int arrayIndex)
 994                         {
 995                                 if (array == null)
 996                                         throw new ArgumentNullException ("array");
 997                                 if (array.Rank != 1)
 998                                         throw new ArgumentException ("array");
 999                                 if (arrayIndex < 0)
1000                                         throw new ArgumentOutOfRangeException ("arrayIndex");
1001                                 if (array.Length - arrayIndex < Count)
1002                                         throw new ArgumentException ("not enough space");
1003
1004                                 host.CopyToArray (array, arrayIndex, EnumeratorMode.KEY_MODE);
1005                         }
1006
1007                         // IEnumerable
1008
1009                         public virtual IEnumerator GetEnumerator ()
1010                         {
1011                                 return new Hashtable.Enumerator (host, EnumeratorMode.KEY_MODE);
1012                         }
1013                 }
1014
1015                 [Serializable]
1016                 private class HashValues : ICollection, IEnumerable {
1017
1018                         private Hashtable host;
1019
1020                         public HashValues (Hashtable host) {
1021                                 if (host == null)
1022                                         throw new ArgumentNullException ();
1023
1024                                 this.host = host;
1025                         }
1026
1027                         // ICollection
1028
1029                         public virtual int Count {
1030                                 get {
1031                                         return host.Count;
1032                                 }
1033                         }
1034
1035                         public virtual bool IsSynchronized {
1036                                 get {
1037                                         return host.IsSynchronized;
1038                                 }
1039                         }
1040
1041                         public virtual Object SyncRoot {
1042                                 get {
1043                                         return host.SyncRoot;
1044                                 }
1045                         }
1046
1047                         public virtual void CopyTo (Array array, int arrayIndex)
1048                         {
1049                                 if (array == null)
1050                                         throw new ArgumentNullException ("array");
1051                                 if (array.Rank != 1)
1052                                         throw new ArgumentException ("array");
1053                                 if (arrayIndex < 0)
1054                                         throw new ArgumentOutOfRangeException ("arrayIndex");
1055                                 if (array.Length - arrayIndex < Count)
1056                                         throw new ArgumentException ("not enough space");
1057
1058                                 host.CopyToArray (array, arrayIndex, EnumeratorMode.VALUE_MODE);
1059                         }
1060
1061                         // IEnumerable
1062
1063                         public virtual IEnumerator GetEnumerator ()
1064                         {
1065                                 return new Hashtable.Enumerator (host, EnumeratorMode.VALUE_MODE);
1066                         }
1067                 }
1068
1069
1070                 [Serializable]
1071                 private class SyncHashtable : Hashtable, IEnumerable {
1072
1073                         private Hashtable host;
1074
1075                         public SyncHashtable (Hashtable host) {
1076                                 if (host == null)
1077                                         throw new ArgumentNullException ();
1078
1079                                 this.host = host;
1080                         }
1081
1082                         internal SyncHashtable (SerializationInfo info, StreamingContext context)
1083                         {
1084                                 host = (Hashtable) info.GetValue("ParentTable", typeof(Hashtable));
1085                         }
1086
1087                         public override void GetObjectData (SerializationInfo info, StreamingContext context)
1088                         {
1089                                 info.AddValue ("ParentTable", host);
1090                         }
1091
1092                         // ICollection
1093
1094                         public override int Count {
1095                                 get {
1096                                         return host.Count;
1097                                 }
1098                         }
1099
1100                         public override bool IsSynchronized {
1101                                 get {
1102                                         return true;
1103                                 }
1104                         }
1105
1106                         public override Object SyncRoot {
1107                                 get {
1108                                         return host.SyncRoot;
1109                                 }
1110                         }
1111
1112
1113
1114                         // IDictionary
1115
1116                         public override bool IsFixedSize {
1117                                 get {
1118                                         return host.IsFixedSize;
1119                                 }
1120                         }
1121
1122
1123                         public override bool IsReadOnly {
1124                                 get {
1125                                         return host.IsReadOnly;
1126                                 }
1127                         }
1128
1129                         public override ICollection Keys {
1130                                 get {
1131                                         ICollection keys = null;
1132                                         lock (host.SyncRoot) {
1133                                                 keys = host.Keys;
1134                                         }
1135                                         return keys;
1136                                 }
1137                         }
1138
1139                         public override ICollection Values {
1140                                 get {
1141                                         ICollection vals = null;
1142                                         lock (host.SyncRoot) {
1143                                                 vals = host.Values;
1144                                         }
1145                                         return vals;
1146                                 }
1147                         }
1148
1149
1150
1151                         public override Object this [Object key] {
1152                                 get {
1153                                         return host [key];
1154                                 }
1155                                 set {
1156                                         lock (host.SyncRoot) {
1157                                                 host [key] = value;
1158                                         }
1159                                 }
1160                         }
1161
1162                         // IEnumerable
1163
1164                         IEnumerator IEnumerable.GetEnumerator ()
1165                         {
1166                                 return new Enumerator (host, EnumeratorMode.ENTRY_MODE);
1167                         }
1168
1169
1170
1171
1172                         // ICollection
1173
1174                         public override void CopyTo (Array array, int arrayIndex)
1175                         {
1176                                 host.CopyTo (array, arrayIndex);
1177                         }
1178
1179
1180                         // IDictionary
1181
1182                         public override void Add (Object key, Object value)
1183                         {
1184                                 lock (host.SyncRoot) {
1185                                         host.Add (key, value);
1186                                 }
1187                         }
1188
1189                         public override void Clear ()
1190                         {
1191                                 lock (host.SyncRoot) {
1192                                         host.Clear ();
1193                                 }
1194                         }
1195
1196                         public override bool Contains (Object key)
1197                         {
1198                                 return (host.Find (key) >= 0);
1199                         }
1200
1201                         public override IDictionaryEnumerator GetEnumerator ()
1202                         {
1203                                 return new Enumerator (host, EnumeratorMode.ENTRY_MODE);
1204                         }
1205
1206                         public override void Remove (Object key)
1207                         {
1208                                 lock (host.SyncRoot) {
1209                                         host.Remove (key);
1210                                 }
1211                         }
1212
1213
1214
1215                         public override bool ContainsKey (object key)
1216                         {
1217                                 return host.Contains (key);
1218                         }
1219
1220                         public override bool ContainsValue (object value)
1221                         {
1222                                 return host.ContainsValue (value);
1223                         }
1224
1225
1226                         // ICloneable
1227
1228                         public override object Clone ()
1229                         {
1230                                 lock(host.SyncRoot) {
1231                                         return new SyncHashtable( (Hashtable) host.Clone () );
1232                                 }
1233                         }
1234
1235                 } // SyncHashtable
1236
1237
1238         } // Hashtable
1239
1240 }