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                 public virtual void GetObjectData (SerializationInfo info, StreamingContext context)
 536                 {
 537                         if (info == null)
 538                                 throw new ArgumentNullException ("info");
 539
 540                         info.AddValue ("LoadFactor", loadFactor);
 541                         info.AddValue ("Version", modificationCount);
 542 #if NET_2_0
 543                         if (equalityComparer != null)
 544                                 info.AddValue ("KeyComparer", equalityComparer);
 545                         else
 546                                 info.AddValue ("Comparer", comparerRef);
 547 #else
 548                                 info.AddValue ("Comparer", comparerRef);
 549 #endif
 550                         info.AddValue ("HashCodeProvider", hcpRef);
 551                         info.AddValue ("HashSize", this.table.Length);
 552 // Create Keys
 553                         Object [] keys = new Object[inUse];
 554                         CopyToArray(keys, 0, EnumeratorMode.KEY_MODE);
 555
 556 // Create Values
 557                         Object [] values = new Object[inUse];
 558                         CopyToArray(values, 0, EnumeratorMode.VALUE_MODE);
 559
 560                         info.AddValue ("Keys", keys);
 561                         info.AddValue ("Values", values);
 562
 563 #if NET_2_0
 564                         info.AddValue ("equalityComparer", equalityComparer);
 565 #endif
 566                 }
 567
 568 #if NET_2_0
 569                 [MonoTODO ("Serialize equalityComparer")]
 570 #endif
 571                 public virtual void OnDeserialization (object sender)
 572                 {
 573                         if (serializationInfo == null) return;
 574
 575                         loadFactor = (float) serializationInfo.GetValue ("LoadFactor", typeof(float));
 576                         modificationCount = (int) serializationInfo.GetValue ("Version", typeof(int));
 577 #if NET_2_0
 578                         try {
 579                                 equalityComparer = (IEqualityComparer) serializationInfo.GetValue ("KeyComparer", typeof (object));
 580                         } catch {
 581                                 // If not found, try to get "Comparer"
 582                         }
 583
 584                         if (equalityComparer == null)
 585                                 comparerRef = (IComparer) serializationInfo.GetValue ("Comparer", typeof (object));
 586 #else
 587                         comparerRef = (IComparer) serializationInfo.GetValue ("Comparer", typeof (object));
 588 #endif
 589
 590                         hcpRef = (IHashCodeProvider) serializationInfo.GetValue ("HashCodeProvider", typeof (object));
 591                         int size = (int) serializationInfo.GetValue ("HashSize", typeof(int));
 592
 593                         Object [] keys = (Object []) serializationInfo.GetValue("Keys", typeof(Object [] ));
 594                         Object [] values = (Object []) serializationInfo.GetValue("Values", typeof(Object [] ));
 595
 596                         if (keys.Length != values.Length)
 597                           throw new SerializationException("Keys and values of uneven size");
 598
 599                         size = ToPrime (size);
 600                         this.SetTable (new Slot [size]);
 601
 602                         for(int i=0;i<keys.Length;i++)
 603                                 Add(keys[i], values[i]);
 604
 605                         AdjustThreshold();
 606
 607                         serializationInfo = null;
 608                 }
 609
 610                 /// <summary>
 611                 ///  Returns a synchronized (thread-safe)
 612                 ///  wrapper for the Hashtable.
 613                 /// </summary>
 614                 public static Hashtable Synchronized (Hashtable table)
 615                 {
 616                         if (table == null)
 617                                 throw new ArgumentNullException("table");
 618                         return new SyncHashtable (table);
 619                 }
 620
 621
 622
 623                 //
 624                 // Protected instance methods
 625                 //
 626
 627                 /// <summary>Returns the hash code for the specified key.</summary>
 628                 protected virtual int GetHash (Object key)
 629                 {
 630 #if NET_2_0
 631                         if (equalityComparer != null)
 632                                 return equalityComparer.GetHashCode (key);
 633 #endif
 634                         if (hcpRef == null)
 635                                 return key.GetHashCode ();
 636
 637                         return hcpRef.GetHashCode (key);
 638                 }
 639
 640                 /// <summary>
 641                 ///  Compares a specific Object with a specific key
 642                 ///  in the Hashtable.
 643                 /// </summary>
 644                 protected virtual bool KeyEquals (Object item, Object key)
 645                 {
 646 #if NET_2_0
 647                         if (equalityComparer != null)
 648                                 return equalityComparer.Equals (item, key);
 649 #endif
 650                         if (comparerRef == null)
 651                                 return item.Equals (key);
 652
 653                         return comparerRef.Compare (item, key) == 0;
 654                 }
 655
 656
 657
 658                 //
 659                 // Private instance methods
 660                 //
 661
 662                 private void AdjustThreshold ()
 663                 {
 664                         int size = table.Length;
 665
 666                         threshold = (int) (size*loadFactor);
 667                         if (this.threshold >= size)
 668                                 threshold = size-1;
 669                 }
 670
 671                 private void SetTable (Slot [] table)
 672                 {
 673                         if (table == null)
 674                                 throw new ArgumentNullException ("table");
 675
 676                         this.table = table;
 677                         AdjustThreshold ();
 678                 }
 679
 680                 private int Find (Object key)
 681                 {
 682                         if (key == null)
 683                                 throw new ArgumentNullException ("key", "null key");
 684
 685                         Slot [] table = this.table;
 686                         uint size = (uint) table.Length;
 687                         int h = this.GetHash (key) & Int32.MaxValue;
 688                         uint indx = (uint)h;
 689                         uint step = (uint) ((h >> 5)+1) % (size-1)+1;
 690
 691
 692                         for (uint i = size; i > 0; i--) {
 693                                 indx %= size;
 694                                 Slot entry = table [indx];
 695                                 Object k = entry.key;
 696                                 if (k == null)
 697                                         break;
 698
 699                                 if (k == key || ((entry.hashMix & Int32.MaxValue) == h
 700                                     && this.KeyEquals (key, k))) {
 701                                         return (int) indx;
 702                                 }
 703
 704                                 if ((entry.hashMix & CHAIN_MARKER) == 0)
 705                                         break;
 706
 707                                 indx += step;
 708                         }
 709                         return -1;
 710                 }
 711
 712
 713                 private void Rehash ()
 714                 {
 715                         int oldSize = this.table.Length;
 716
 717                         // From the SDK docs:
 718                         //   Hashtable is automatically increased
 719                         //   to the smallest prime number that is larger
 720                         //   than twice the current number of Hashtable buckets
 721                         uint newSize = (uint)ToPrime ((oldSize<<1)|1);
 722
 723
 724                         Slot [] newTable = new Slot [newSize];
 725                         Slot [] table = this.table;
 726
 727                         for (int i = 0;i<oldSize;i++) {
 728                                 Slot s = table [i];
 729                                 if (s.key!= null) {
 730                                         int h = s.hashMix & Int32.MaxValue;
 731                                         uint spot = (uint)h;
 732                                         uint step = ((uint) (h>>5)+1)% (newSize-1)+1;
 733                                         for (uint j = spot%newSize;;spot+= step, j = spot%newSize) {
 734                                                 // No check for KeyMarker.Removed here,
 735                                                 // because the table is just allocated.
 736                                                 if (newTable [j].key == null) {
 737                                                         newTable [j].key = s.key;
 738                                                         newTable [j].value = s.value;
 739                                                         newTable [j].hashMix |= h;
 740                                                         break;
 741                                                 } else {
 742                                                         newTable [j].hashMix |= CHAIN_MARKER;
 743                                                 }
 744                                         }
 745                                 }
 746                         }
 747
 748                         ++this.modificationCount;
 749
 750                         this.SetTable (newTable);
 751                 }
 752
 753
 754                 private void PutImpl (Object key, Object value, bool overwrite)
 755                 {
 756                         if (key == null)
 757                                 throw new ArgumentNullException ("key", "null key");
 758
 759                         if (this.inUse >= this.threshold)
 760                                 this.Rehash ();
 761
 762                         uint size = (uint)this.table.Length;
 763
 764                         int h = this.GetHash (key) & Int32.MaxValue;
 765                         uint spot = (uint)h;
 766                         uint step = (uint) ((spot>>5)+1)% (size-1)+1;
 767                         Slot [] table = this.table;
 768                         Slot entry;
 769
 770                         int freeIndx = -1;
 771                         for (int i = 0; i < size; i++) {
 772                                 int indx = (int) (spot % size);
 773                                 entry = table [indx];
 774
 775                                 if (freeIndx == -1
 776                                     && entry.key == KeyMarker.Removed
 777                                     && (entry.hashMix & CHAIN_MARKER) != 0)
 778                                         freeIndx = indx;
 779
 780                                 if (entry.key == null ||
 781                                     (entry.key == KeyMarker.Removed
 782                                      && (entry.hashMix & CHAIN_MARKER) == 0)) {
 783
 784                                         if (freeIndx == -1)
 785                                                 freeIndx = indx;
 786                                         break;
 787                                 }
 788
 789                                 if ((entry.hashMix & Int32.MaxValue) == h && KeyEquals (key, entry.key)) {
 790                                         if (overwrite) {
 791                                                 table [indx].value = value;
 792                                                 ++this.modificationCount;
 793                                         } else {
 794                                                 // Handle Add ():
 795                                                 // An entry with the same key already exists in the Hashtable.
 796                                                 throw new ArgumentException (
 797                                                                 "Key duplication when adding: " + key);
 798                                         }
 799                                         return;
 800                                 }
 801
 802                                 if (freeIndx == -1) {
 803                                         table [indx].hashMix |= CHAIN_MARKER;
 804                                 }
 805
 806                                 spot+= step;
 807
 808                         }
 809
 810                         if (freeIndx!= -1) {
 811                                 table [freeIndx].key = key;
 812                                 table [freeIndx].value = value;
 813                                 table [freeIndx].hashMix |= h;
 814
 815                                 ++this.inUse;
 816                                 ++this.modificationCount;
 817                         }
 818
 819                 }
 820
 821                 private void  CopyToArray (Array arr, int i,
 822                                            EnumeratorMode mode)
 823                 {
 824                         IEnumerator it = new Enumerator (this, mode);
 825
 826                         while (it.MoveNext ()) {
 827                                 arr.SetValue (it.Current, i++);
 828                         }
 829                 }
 830
 831
 832
 833                 //
 834                 // Private static methods
 835                 //
 836                 internal static bool TestPrime (int x)
 837                 {
 838                         if ((x & 1) != 0) {
 839                                 int top = (int)Math.Sqrt (x);
 840
 841                                 for (int n = 3; n < top; n += 2) {
 842                                         if ((x % n) == 0)
 843                                                 return false;
 844                                 }
 845                                 return true;
 846                         }
 847                         // There is only one even prime - 2.
 848                         return (x == 2);
 849                 }
 850
 851                 internal static int CalcPrime (int x)
 852                 {
 853                         for (int i = (x & (~1))-1; i< Int32.MaxValue; i += 2) {
 854                                 if (TestPrime (i)) return i;
 855                         }
 856                         return x;
 857                 }
 858
 859                 internal static int ToPrime (int x)
 860                 {
 861                         for (int i = 0; i < primeTbl.Length; i++) {
 862                                 if (x <= primeTbl [i])
 863                                         return primeTbl [i];
 864                         }
 865                         return CalcPrime (x);
 866                 }
 867
 868
 869
 870
 871                 //
 872                 // Inner classes
 873                 //
 874
 875                 private enum EnumeratorMode : int {KEY_MODE = 0, VALUE_MODE, ENTRY_MODE};
 876
 877                 [Serializable]
 878                 private sealed class Enumerator : IDictionaryEnumerator, IEnumerator {
 879
 880                         private Hashtable host;
 881                         private int stamp;
 882                         private int pos;
 883                         private int size;
 884                         private EnumeratorMode mode;
 885
 886                         private Object currentKey;
 887                         private Object currentValue;
 888
 889                         private readonly static string xstr = "Hashtable.Enumerator: snapshot out of sync.";
 890
 891                         public Enumerator (Hashtable host, EnumeratorMode mode) {
 892                                 this.host = host;
 893                                 stamp = host.modificationCount;
 894                                 size = host.table.Length;
 895                                 this.mode = mode;
 896                                 Reset ();
 897                         }
 898
 899                         public Enumerator (Hashtable host)
 900                                    : this (host, EnumeratorMode.KEY_MODE) {}
 901
 902
 903                         private void FailFast ()
 904                         {
 905                                 if (host.modificationCount != stamp) {
 906                                         throw new InvalidOperationException (xstr);
 907                                 }
 908                         }
 909
 910                         public void Reset ()
 911                         {
 912                                 FailFast ();
 913
 914                                 pos = -1;
 915                                 currentKey = null;
 916                                 currentValue = null;
 917                         }
 918
 919                         public bool MoveNext ()
 920                         {
 921                                 FailFast ();
 922
 923                                 if (pos < size) {
 924                                         while (++pos < size) {
 925                                                 Slot entry = host.table [pos];
 926
 927                                                 if (entry.key != null && entry.key != KeyMarker.Removed) {
 928                                                         currentKey = entry.key;
 929                                                         currentValue = entry.value;
 930                                                         return true;
 931                                                 }
 932                                         }
 933                                 }
 934
 935                                 currentKey = null;
 936                                 currentValue = null;
 937                                 return false;
 938                         }
 939
 940                         public DictionaryEntry Entry
 941                         {
 942                                 get {
 943                                         if (currentKey == null) throw new InvalidOperationException ();
 944                                         FailFast ();
 945                                         return new DictionaryEntry (currentKey, currentValue);
 946                                 }
 947                         }
 948
 949                         public Object Key {
 950                                 get {
 951                                         if (currentKey == null) throw new InvalidOperationException ();
 952                                         FailFast ();
 953                                         return currentKey;
 954                                 }
 955                         }
 956
 957                         public Object Value {
 958                                 get {
 959                                         if (currentKey == null) throw new InvalidOperationException ();
 960                                         FailFast ();
 961                                         return currentValue;
 962                                 }
 963                         }
 964
 965                         public Object Current {
 966                                 get {
 967                                         if (currentKey == null) throw new InvalidOperationException ();
 968
 969                                         switch (mode) {
 970                                         case EnumeratorMode.KEY_MODE:
 971                                                 return currentKey;
 972                                         case EnumeratorMode.VALUE_MODE:
 973                                                 return currentValue;
 974                                         case EnumeratorMode.ENTRY_MODE:
 975                                                 return new DictionaryEntry (currentKey, currentValue);
 976                                         }
 977                                         throw new Exception ("should never happen");
 978                                 }
 979                         }
 980                 }
 981
 982                 [Serializable]
 983                 private class HashKeys : ICollection, IEnumerable {
 984
 985                         private Hashtable host;
 986
 987                         public HashKeys (Hashtable host) {
 988                                 if (host == null)
 989                                         throw new ArgumentNullException ();
 990
 991                                 this.host = host;
 992                         }
 993
 994                         // ICollection
 995
 996                         public virtual int Count {
 997                                 get {
 998                                         return host.Count;
 999                                 }
1000                         }
1001
1002                         public virtual bool IsSynchronized {
1003                                 get {
1004                                         return host.IsSynchronized;
1005                                 }
1006                         }
1007
1008                         public virtual Object SyncRoot {
1009                                 get {return host.SyncRoot;}
1010                         }
1011
1012                         public virtual void CopyTo (Array array, int arrayIndex)
1013                         {
1014                                 if (array == null)
1015                                         throw new ArgumentNullException ("array");
1016                                 if (array.Rank != 1)
1017                                         throw new ArgumentException ("array");
1018                                 if (arrayIndex < 0)
1019                                         throw new ArgumentOutOfRangeException ("arrayIndex");
1020                                 if (array.Length - arrayIndex < Count)
1021                                         throw new ArgumentException ("not enough space");
1022
1023                                 host.CopyToArray (array, arrayIndex, EnumeratorMode.KEY_MODE);
1024                         }
1025
1026                         // IEnumerable
1027
1028                         public virtual IEnumerator GetEnumerator ()
1029                         {
1030                                 return new Hashtable.Enumerator (host, EnumeratorMode.KEY_MODE);
1031                         }
1032                 }
1033
1034                 [Serializable]
1035                 private class HashValues : ICollection, IEnumerable {
1036
1037                         private Hashtable host;
1038
1039                         public HashValues (Hashtable host) {
1040                                 if (host == null)
1041                                         throw new ArgumentNullException ();
1042
1043                                 this.host = host;
1044                         }
1045
1046                         // ICollection
1047
1048                         public virtual int Count {
1049                                 get {
1050                                         return host.Count;
1051                                 }
1052                         }
1053
1054                         public virtual bool IsSynchronized {
1055                                 get {
1056                                         return host.IsSynchronized;
1057                                 }
1058                         }
1059
1060                         public virtual Object SyncRoot {
1061                                 get {
1062                                         return host.SyncRoot;
1063                                 }
1064                         }
1065
1066                         public virtual void CopyTo (Array array, int arrayIndex)
1067                         {
1068                                 if (array == null)
1069                                         throw new ArgumentNullException ("array");
1070                                 if (array.Rank != 1)
1071                                         throw new ArgumentException ("array");
1072                                 if (arrayIndex < 0)
1073                                         throw new ArgumentOutOfRangeException ("arrayIndex");
1074                                 if (array.Length - arrayIndex < Count)
1075                                         throw new ArgumentException ("not enough space");
1076
1077                                 host.CopyToArray (array, arrayIndex, EnumeratorMode.VALUE_MODE);
1078                         }
1079
1080                         // IEnumerable
1081
1082                         public virtual IEnumerator GetEnumerator ()
1083                         {
1084                                 return new Hashtable.Enumerator (host, EnumeratorMode.VALUE_MODE);
1085                         }
1086                 }
1087
1088
1089                 [Serializable]
1090                 private class SyncHashtable : Hashtable, IEnumerable {
1091
1092                         private Hashtable host;
1093
1094                         public SyncHashtable (Hashtable host) {
1095                                 if (host == null)
1096                                         throw new ArgumentNullException ();
1097
1098                                 this.host = host;
1099                         }
1100
1101                         internal SyncHashtable (SerializationInfo info, StreamingContext context)
1102                         {
1103                                 host = (Hashtable) info.GetValue("ParentTable", typeof(Hashtable));
1104                         }
1105
1106                         public override void GetObjectData (SerializationInfo info, StreamingContext context)
1107                         {
1108                                 info.AddValue ("ParentTable", host);
1109                         }
1110
1111                         // ICollection
1112
1113                         public override int Count {
1114                                 get {
1115                                         return host.Count;
1116                                 }
1117                         }
1118
1119                         public override bool IsSynchronized {
1120                                 get {
1121                                         return true;
1122                                 }
1123                         }
1124
1125                         public override Object SyncRoot {
1126                                 get {
1127                                         return host.SyncRoot;
1128                                 }
1129                         }
1130
1131
1132
1133                         // IDictionary
1134
1135                         public override bool IsFixedSize {
1136                                 get {
1137                                         return host.IsFixedSize;
1138                                 }
1139                         }
1140
1141
1142                         public override bool IsReadOnly {
1143                                 get {
1144                                         return host.IsReadOnly;
1145                                 }
1146                         }
1147
1148                         public override ICollection Keys {
1149                                 get {
1150                                         ICollection keys = null;
1151                                         lock (host.SyncRoot) {
1152                                                 keys = host.Keys;
1153                                         }
1154                                         return keys;
1155                                 }
1156                         }
1157
1158                         public override ICollection Values {
1159                                 get {
1160                                         ICollection vals = null;
1161                                         lock (host.SyncRoot) {
1162                                                 vals = host.Values;
1163                                         }
1164                                         return vals;
1165                                 }
1166                         }
1167
1168
1169
1170                         public override Object this [Object key] {
1171                                 get {
1172                                         return host [key];
1173                                 }
1174                                 set {
1175                                         lock (host.SyncRoot) {
1176                                                 host [key] = value;
1177                                         }
1178                                 }
1179                         }
1180
1181                         // IEnumerable
1182
1183                         IEnumerator IEnumerable.GetEnumerator ()
1184                         {
1185                                 return new Enumerator (host, EnumeratorMode.ENTRY_MODE);
1186                         }
1187
1188
1189
1190
1191                         // ICollection
1192
1193                         public override void CopyTo (Array array, int arrayIndex)
1194                         {
1195                                 host.CopyTo (array, arrayIndex);
1196                         }
1197
1198
1199                         // IDictionary
1200
1201                         public override void Add (Object key, Object value)
1202                         {
1203                                 lock (host.SyncRoot) {
1204                                         host.Add (key, value);
1205                                 }
1206                         }
1207
1208                         public override void Clear ()
1209                         {
1210                                 lock (host.SyncRoot) {
1211                                         host.Clear ();
1212                                 }
1213                         }
1214
1215                         public override bool Contains (Object key)
1216                         {
1217                                 return (host.Find (key) >= 0);
1218                         }
1219
1220                         public override IDictionaryEnumerator GetEnumerator ()
1221                         {
1222                                 return new Enumerator (host, EnumeratorMode.ENTRY_MODE);
1223                         }
1224
1225                         public override void Remove (Object key)
1226                         {
1227                                 lock (host.SyncRoot) {
1228                                         host.Remove (key);
1229                                 }
1230                         }
1231
1232
1233
1234                         public override bool ContainsKey (object key)
1235                         {
1236                                 return host.Contains (key);
1237                         }
1238
1239                         public override bool ContainsValue (object value)
1240                         {
1241                                 return host.ContainsValue (value);
1242                         }
1243
1244
1245                         // ICloneable
1246
1247                         public override object Clone ()
1248                         {
1249                                 lock(host.SyncRoot) {
1250                                         return new SyncHashtable( (Hashtable) host.Clone () );
1251                                 }
1252                         }
1253
1254                 } // SyncHashtable
1255
1256
1257         } // Hashtable
1258
1259 }