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                         uint size = (uint)this.table.Length;
 741                         if (this.inUse >= this.threshold) {
 742                                 this.Rehash ();
 743                                 size = (uint)this.table.Length;
 744                         }
 745
 746                         int h = this.GetHash (key) & Int32.MaxValue;
 747                         uint spot = (uint)h;
 748                         uint step = (uint) ((spot>>5)+1)% (size-1)+1;
 749                         Slot [] table = this.table;
 750                         Slot entry;
 751
 752                         int freeIndx = -1;
 753                         for (int i = 0; i < size; i++) {
 754                                 int indx = (int) (spot % size);
 755                                 entry = table [indx];
 756
 757                                 if (freeIndx == -1
 758                                     && entry.key == KeyMarker.Removed
 759                                     && (entry.hashMix & CHAIN_MARKER) != 0)
 760                                         freeIndx = indx;
 761
 762                                 if (entry.key == null ||
 763                                     (entry.key == KeyMarker.Removed
 764                                      && (entry.hashMix & CHAIN_MARKER) == 0)) {
 765
 766                                         if (freeIndx == -1)
 767                                                 freeIndx = indx;
 768                                         break;
 769                                 }
 770
 771                                 if ((entry.hashMix & Int32.MaxValue) == h && KeyEquals (key, entry.key)) {
 772                                         if (overwrite) {
 773                                                 table [indx].value = value;
 774                                                 ++this.modificationCount;
 775                                         } else {
 776                                                 // Handle Add ():
 777                                                 // An entry with the same key already exists in the Hashtable.
 778                                                 throw new ArgumentException (
 779                                                                 "Key duplication when adding: " + key);
 780                                         }
 781                                         return;
 782                                 }
 783
 784                                 if (freeIndx == -1) {
 785                                         table [indx].hashMix |= CHAIN_MARKER;
 786                                 }
 787
 788                                 spot+= step;
 789
 790                         }
 791
 792                         if (freeIndx!= -1) {
 793                                 table [freeIndx].key = key;
 794                                 table [freeIndx].value = value;
 795                                 table [freeIndx].hashMix |= h;
 796
 797                                 ++this.inUse;
 798                                 ++this.modificationCount;
 799                         }
 800
 801                 }
 802
 803                 private void  CopyToArray (Array arr, int i,
 804                                            EnumeratorMode mode)
 805                 {
 806                         IEnumerator it = new Enumerator (this, mode);
 807
 808                         while (it.MoveNext ()) {
 809                                 arr.SetValue (it.Current, i++);
 810                         }
 811                 }
 812
 813
 814
 815                 //
 816                 // Private static methods
 817                 //
 818                 internal static bool TestPrime (int x)
 819                 {
 820                         if ((x & 1) != 0) {
 821                                 for (int n = 3; n< (int)Math.Sqrt (x); n += 2) {
 822                                         if ((x % n) == 0)
 823                                                 return false;
 824                                 }
 825                                 return true;
 826                         }
 827                         // There is only one even prime - 2.
 828                         return (x == 2);
 829                 }
 830
 831                 internal static int CalcPrime (int x)
 832                 {
 833                         for (int i = (x & (~1))-1; i< Int32.MaxValue; i += 2) {
 834                                 if (TestPrime (i)) return i;
 835                         }
 836                         return x;
 837                 }
 838
 839                 internal static int ToPrime (int x)
 840                 {
 841                         for (int i = 0; i < primeTbl.Length; i++) {
 842                                 if (x <= primeTbl [i])
 843                                         return primeTbl [i];
 844                         }
 845                         return CalcPrime (x);
 846                 }
 847
 848
 849
 850
 851                 //
 852                 // Inner classes
 853                 //
 854
 855                 private enum EnumeratorMode : int {KEY_MODE = 0, VALUE_MODE, ENTRY_MODE};
 856
 857                 [Serializable]
 858                 private sealed class Enumerator : IDictionaryEnumerator, IEnumerator {
 859
 860                         private Hashtable host;
 861                         private int stamp;
 862                         private int pos;
 863                         private int size;
 864                         private EnumeratorMode mode;
 865
 866                         private Object currentKey;
 867                         private Object currentValue;
 868
 869                         private readonly static string xstr = "Hashtable.Enumerator: snapshot out of sync.";
 870
 871                         public Enumerator (Hashtable host, EnumeratorMode mode) {
 872                                 this.host = host;
 873                                 stamp = host.modificationCount;
 874                                 size = host.table.Length;
 875                                 this.mode = mode;
 876                                 Reset ();
 877                         }
 878
 879                         public Enumerator (Hashtable host)
 880                                    : this (host, EnumeratorMode.KEY_MODE) {}
 881
 882
 883                         private void FailFast ()
 884                         {
 885                                 if (host.modificationCount != stamp) {
 886                                         throw new InvalidOperationException (xstr);
 887                                 }
 888                         }
 889
 890                         public void Reset ()
 891                         {
 892                                 FailFast ();
 893
 894                                 pos = -1;
 895                                 currentKey = null;
 896                                 currentValue = null;
 897                         }
 898
 899                         public bool MoveNext ()
 900                         {
 901                                 FailFast ();
 902
 903                                 if (pos < size) {
 904                                         while (++pos < size) {
 905                                                 Slot entry = host.table [pos];
 906
 907                                                 if (entry.key != null && entry.key != KeyMarker.Removed) {
 908                                                         currentKey = entry.key;
 909                                                         currentValue = entry.value;
 910                                                         return true;
 911                                                 }
 912                                         }
 913                                 }
 914
 915                                 currentKey = null;
 916                                 currentValue = null;
 917                                 return false;
 918                         }
 919
 920                         public DictionaryEntry Entry
 921                         {
 922                                 get {
 923                                         if (currentKey == null) throw new InvalidOperationException ();
 924                                         FailFast ();
 925                                         return new DictionaryEntry (currentKey, currentValue);
 926                                 }
 927                         }
 928
 929                         public Object Key {
 930                                 get {
 931                                         if (currentKey == null) throw new InvalidOperationException ();
 932                                         FailFast ();
 933                                         return currentKey;
 934                                 }
 935                         }
 936
 937                         public Object Value {
 938                                 get {
 939                                         if (currentKey == null) throw new InvalidOperationException ();
 940                                         FailFast ();
 941                                         return currentValue;
 942                                 }
 943                         }
 944
 945                         public Object Current {
 946                                 get {
 947                                         if (currentKey == null) throw new InvalidOperationException ();
 948
 949                                         switch (mode) {
 950                                         case EnumeratorMode.KEY_MODE:
 951                                                 return currentKey;
 952                                         case EnumeratorMode.VALUE_MODE:
 953                                                 return currentValue;
 954                                         case EnumeratorMode.ENTRY_MODE:
 955                                                 return new DictionaryEntry (currentKey, currentValue);
 956                                         }
 957                                         throw new Exception ("should never happen");
 958                                 }
 959                         }
 960                 }
 961
 962                 [Serializable]
 963                 private class HashKeys : ICollection, IEnumerable {
 964
 965                         private Hashtable host;
 966
 967                         public HashKeys (Hashtable host) {
 968                                 if (host == null)
 969                                         throw new ArgumentNullException ();
 970
 971                                 this.host = host;
 972                         }
 973
 974                         // ICollection
 975
 976                         public virtual int Count {
 977                                 get {
 978                                         return host.Count;
 979                                 }
 980                         }
 981
 982                         public virtual bool IsSynchronized {
 983                                 get {
 984                                         return host.IsSynchronized;
 985                                 }
 986                         }
 987
 988                         public virtual Object SyncRoot {
 989                                 get {return host.SyncRoot;}
 990                         }
 991
 992                         public virtual void CopyTo (Array array, int arrayIndex)
 993                         {
 994                                 if (array == null)
 995                                         throw new ArgumentNullException ("array");
 996                                 if (array.Rank != 1)
 997                                         throw new ArgumentException ("array");
 998                                 if (arrayIndex < 0)
 999                                         throw new ArgumentOutOfRangeException ("arrayIndex");
1000                                 if (array.Length - arrayIndex < Count)
1001                                         throw new ArgumentException ("not enough space");
1002
1003                                 host.CopyToArray (array, arrayIndex, EnumeratorMode.KEY_MODE);
1004                         }
1005
1006                         // IEnumerable
1007
1008                         public virtual IEnumerator GetEnumerator ()
1009                         {
1010                                 return new Hashtable.Enumerator (host, EnumeratorMode.KEY_MODE);
1011                         }
1012                 }
1013
1014                 [Serializable]
1015                 private class HashValues : ICollection, IEnumerable {
1016
1017                         private Hashtable host;
1018
1019                         public HashValues (Hashtable host) {
1020                                 if (host == null)
1021                                         throw new ArgumentNullException ();
1022
1023                                 this.host = host;
1024                         }
1025
1026                         // ICollection
1027
1028                         public virtual int Count {
1029                                 get {
1030                                         return host.Count;
1031                                 }
1032                         }
1033
1034                         public virtual bool IsSynchronized {
1035                                 get {
1036                                         return host.IsSynchronized;
1037                                 }
1038                         }
1039
1040                         public virtual Object SyncRoot {
1041                                 get {
1042                                         return host.SyncRoot;
1043                                 }
1044                         }
1045
1046                         public virtual void CopyTo (Array array, int arrayIndex)
1047                         {
1048                                 if (array == null)
1049                                         throw new ArgumentNullException ("array");
1050                                 if (array.Rank != 1)
1051                                         throw new ArgumentException ("array");
1052                                 if (arrayIndex < 0)
1053                                         throw new ArgumentOutOfRangeException ("arrayIndex");
1054                                 if (array.Length - arrayIndex < Count)
1055                                         throw new ArgumentException ("not enough space");
1056
1057                                 host.CopyToArray (array, arrayIndex, EnumeratorMode.VALUE_MODE);
1058                         }
1059
1060                         // IEnumerable
1061
1062                         public virtual IEnumerator GetEnumerator ()
1063                         {
1064                                 return new Hashtable.Enumerator (host, EnumeratorMode.VALUE_MODE);
1065                         }
1066                 }
1067
1068
1069                 [Serializable]
1070                 private class SyncHashtable : Hashtable, IEnumerable {
1071
1072                         private Hashtable host;
1073
1074                         public SyncHashtable (Hashtable host) {
1075                                 if (host == null)
1076                                         throw new ArgumentNullException ();
1077
1078                                 this.host = host;
1079                         }
1080
1081                         internal SyncHashtable (SerializationInfo info, StreamingContext context)
1082                         {
1083                                 host = (Hashtable) info.GetValue("ParentTable", typeof(Hashtable));
1084                         }
1085
1086                         public override void GetObjectData (SerializationInfo info, StreamingContext context)
1087                         {
1088                                 info.AddValue ("ParentTable", host);
1089                         }
1090
1091                         // ICollection
1092
1093                         public override int Count {
1094                                 get {
1095                                         return host.Count;
1096                                 }
1097                         }
1098
1099                         public override bool IsSynchronized {
1100                                 get {
1101                                         return true;
1102                                 }
1103                         }
1104
1105                         public override Object SyncRoot {
1106                                 get {
1107                                         return host.SyncRoot;
1108                                 }
1109                         }
1110
1111
1112
1113                         // IDictionary
1114
1115                         public override bool IsFixedSize {
1116                                 get {
1117                                         return host.IsFixedSize;
1118                                 }
1119                         }
1120
1121
1122                         public override bool IsReadOnly {
1123                                 get {
1124                                         return host.IsReadOnly;
1125                                 }
1126                         }
1127
1128                         public override ICollection Keys {
1129                                 get {
1130                                         ICollection keys = null;
1131                                         lock (host.SyncRoot) {
1132                                                 keys = host.Keys;
1133                                         }
1134                                         return keys;
1135                                 }
1136                         }
1137
1138                         public override ICollection Values {
1139                                 get {
1140                                         ICollection vals = null;
1141                                         lock (host.SyncRoot) {
1142                                                 vals = host.Values;
1143                                         }
1144                                         return vals;
1145                                 }
1146                         }
1147
1148
1149
1150                         public override Object this [Object key] {
1151                                 get {
1152                                         return host [key];
1153                                 }
1154                                 set {
1155                                         lock (host.SyncRoot) {
1156                                                 host [key] = value;
1157                                         }
1158                                 }
1159                         }
1160
1161                         // IEnumerable
1162
1163                         IEnumerator IEnumerable.GetEnumerator ()
1164                         {
1165                                 return new Enumerator (host, EnumeratorMode.ENTRY_MODE);
1166                         }
1167
1168
1169
1170
1171                         // ICollection
1172
1173                         public override void CopyTo (Array array, int arrayIndex)
1174                         {
1175                                 host.CopyTo (array, arrayIndex);
1176                         }
1177
1178
1179                         // IDictionary
1180
1181                         public override void Add (Object key, Object value)
1182                         {
1183                                 lock (host.SyncRoot) {
1184                                         host.Add (key, value);
1185                                 }
1186                         }
1187
1188                         public override void Clear ()
1189                         {
1190                                 lock (host.SyncRoot) {
1191                                         host.Clear ();
1192                                 }
1193                         }
1194
1195                         public override bool Contains (Object key)
1196                         {
1197                                 return (host.Find (key) >= 0);
1198                         }
1199
1200                         public override IDictionaryEnumerator GetEnumerator ()
1201                         {
1202                                 return new Enumerator (host, EnumeratorMode.ENTRY_MODE);
1203                         }
1204
1205                         public override void Remove (Object key)
1206                         {
1207                                 lock (host.SyncRoot) {
1208                                         host.Remove (key);
1209                                 }
1210                         }
1211
1212
1213
1214                         public override bool ContainsKey (object key)
1215                         {
1216                                 return host.Contains (key);
1217                         }
1218
1219                         public override bool ContainsValue (object value)
1220                         {
1221                                 return host.ContainsValue (value);
1222                         }
1223
1224
1225                         // ICloneable
1226
1227                         public override object Clone ()
1228                         {
1229                                 lock(host.SyncRoot) {
1230                                         return new SyncHashtable( (Hashtable) host.Clone () );
1231                                 }
1232                         }
1233
1234                 } // SyncHashtable
1235
1236
1237         } // Hashtable
1238
1239 }