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