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