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