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