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                         if (serializationInfo == null) return;
 458
 459                         loadFactor = (float) serializationInfo.GetValue ("LoadFactor", typeof(float));
 460                         modificationCount = (int) serializationInfo.GetValue ("Version", typeof(int));
 461                         comparerRef = (IComparer) serializationInfo.GetValue ("Comparer", typeof (object));
 462                         hcpRef = (IHashCodeProvider) serializationInfo.GetValue ("HashCodeProvider", typeof (object));
 463                         int size = (int) serializationInfo.GetValue ("HashSize", typeof(int));
 464
 465                         Object [] keys = (Object []) serializationInfo.GetValue("Keys", typeof(Object [] ));
 466                         Object [] values = (Object []) serializationInfo.GetValue("Values", typeof(Object [] ));
 467
 468                         if (keys.Length != values.Length)
 469                           throw new SerializationException("Keys and values of uneven size");
 470
 471                         size = ToPrime (size);
 472                         this.SetTable (new Slot [size]);
 473
 474                         for(int i=0;i<keys.Length;i++)
 475                                 Add(keys[i], values[i]);
 476
 477                         AdjustThreshold();
 478
 479                         serializationInfo = null;
 480                 }
 481
 482                 /// <summary>
 483                 ///  Returns a synchronized (thread-safe)
 484                 ///  wrapper for the Hashtable.
 485                 /// </summary>
 486                 public static Hashtable Synchronized (Hashtable table)
 487                 {
 488                         if (table == null)
 489                                 throw new ArgumentNullException("table");
 490                         return new SyncHashtable (table);
 491                 }
 492
 493
 494
 495                 //
 496                 // Protected instance methods
 497                 //
 498
 499                 /// <summary>Returns the hash code for the specified key.</summary>
 500                 protected virtual int GetHash (Object key)
 501                 {
 502                         IHashCodeProvider hcp = this.hcp;
 503                         return (hcp!= null)
 504                                 ? hcp.GetHashCode (key)
 505                                 : key.GetHashCode ();
 506                 }
 507
 508                 /// <summary>
 509                 ///  Compares a specific Object with a specific key
 510                 ///  in the Hashtable.
 511                 /// </summary>
 512                 protected virtual bool KeyEquals (Object item, Object key)
 513                 {
 514                         IComparer c = this.comparer;
 515                         if (c!= null)
 516                                 return (c.Compare (item, key) == 0);
 517                         else
 518                                 return item.Equals (key);
 519                 }
 520
 521
 522
 523                 //
 524                 // Private instance methods
 525                 //
 526
 527                 private void AdjustThreshold ()
 528                 {
 529                         int size = table.Length;
 530
 531                         threshold = (int) (size*loadFactor);
 532                         if (this.threshold >= size)
 533                                 threshold = size-1;
 534                 }
 535
 536                 private void SetTable (Slot [] table)
 537                 {
 538                         if (table == null)
 539                                 throw new ArgumentNullException ("table");
 540
 541                         this.table = table;
 542                         AdjustThreshold ();
 543                 }
 544
 545                 private Object GetImpl (Object key)
 546                 {
 547                         int i = Find (key);
 548
 549                         if (i >= 0)
 550                                 return table [i].value;
 551                         else
 552                                 return null;
 553                 }
 554
 555
 556                 private int Find (Object key)
 557                 {
 558                         if (key == null)
 559                                 throw new ArgumentNullException ("key", "null key");
 560
 561                         uint size = (uint) this.table.Length;
 562                         int h = this.GetHash (key) & Int32.MaxValue;
 563                         uint spot = (uint)h;
 564                         uint step = (uint) ((h >> 5)+1) % (size-1)+1;
 565                         Slot[] table = this.table;
 566
 567                         for (uint i = 0; i < size;i++) {
 568                                 int indx = (int) (spot % size);
 569                                 Slot entry = table [indx];
 570                                 Object k = entry.key;
 571                                 if (k == null)
 572                                         return -1;
 573                                 if (k == key || ((entry.hashMix & Int32.MaxValue) == h
 574                                     && this.KeyEquals (key, k))) {
 575                                         return indx;
 576                                 }
 577
 578                                 if ((entry.hashMix & CHAIN_MARKER) == 0)
 579                                         return -1;
 580
 581                                 spot+= step;
 582                         }
 583                         return -1;
 584                 }
 585
 586
 587                 private void Rehash ()
 588                 {
 589                         int oldSize = this.table.Length;
 590
 591                         // From the SDK docs:
 592                         //   Hashtable is automatically increased
 593                         //   to the smallest prime number that is larger
 594                         //   than twice the current number of Hashtable buckets
 595                         uint newSize = (uint)ToPrime ((oldSize<<1)|1);
 596
 597
 598                         Slot [] newTable = new Slot [newSize];
 599                         Slot [] table = this.table;
 600
 601                         for (int i = 0;i<oldSize;i++) {
 602                                 Slot s = table [i];
 603                                 if (s.key!= null) {
 604                                         int h = s.hashMix & Int32.MaxValue;
 605                                         uint spot = (uint)h;
 606                                         uint step = ((uint) (h>>5)+1)% (newSize-1)+1;
 607                                         for (uint j = spot%newSize;;spot+= step, j = spot%newSize) {
 608                                                 // No check for KeyMarker.Removed here,
 609                                                 // because the table is just allocated.
 610                                                 if (newTable [j].key == null) {
 611                                                         newTable [j].key = s.key;
 612                                                         newTable [j].value = s.value;
 613                                                         newTable [j].hashMix |= h;
 614                                                         break;
 615                                                 } else {
 616                                                         newTable [j].hashMix |= CHAIN_MARKER;
 617                                                 }
 618                                         }
 619                                 }
 620                         }
 621
 622                         ++this.modificationCount;
 623
 624                         this.SetTable (newTable);
 625                 }
 626
 627
 628                 private void PutImpl (Object key, Object value, bool overwrite)
 629                 {
 630                         if (key == null)
 631                                 throw new ArgumentNullException ("key", "null key");
 632
 633                         uint size = (uint)this.table.Length;
 634                         if (this.inUse >= this.threshold) {
 635                                 this.Rehash ();
 636                                 size = (uint)this.table.Length;
 637                         }
 638
 639                         int h = this.GetHash (key) & Int32.MaxValue;
 640                         uint spot = (uint)h;
 641                         uint step = (uint) ((spot>>5)+1)% (size-1)+1;
 642                         Slot [] table = this.table;
 643                         Slot entry;
 644
 645                         int freeIndx = -1;
 646                         for (int i = 0; i < size; i++) {
 647                                 int indx = (int) (spot % size);
 648                                 entry = table [indx];
 649
 650                                 if (freeIndx == -1
 651                                     && entry.key == KeyMarker.Removed
 652                                     && (entry.hashMix & CHAIN_MARKER) != 0)
 653                                         freeIndx = indx;
 654
 655                                 if (entry.key == null ||
 656                                     (entry.key == KeyMarker.Removed
 657                                      && (entry.hashMix & CHAIN_MARKER) == 0)) {
 658
 659                                         if (freeIndx == -1)
 660                                                 freeIndx = indx;
 661                                         break;
 662                                 }
 663
 664                                 if ((entry.hashMix & Int32.MaxValue) == h && KeyEquals (key, entry.key)) {
 665                                         if (overwrite) {
 666                                                 table [indx].value = value;
 667                                                 ++this.modificationCount;
 668                                         } else {
 669                                                 // Handle Add ():
 670                                                 // An entry with the same key already exists in the Hashtable.
 671                                                 throw new ArgumentException (
 672                                                                 "Key duplication when adding: " + key);
 673                                         }
 674                                         return;
 675                                 }
 676
 677                                 if (freeIndx == -1) {
 678                                         table [indx].hashMix |= CHAIN_MARKER;
 679                                 }
 680
 681                                 spot+= step;
 682
 683                         }
 684
 685                         if (freeIndx!= -1) {
 686                                 table [freeIndx].key = key;
 687                                 table [freeIndx].value = value;
 688                                 table [freeIndx].hashMix |= h;
 689
 690                                 ++this.inUse;
 691                                 ++this.modificationCount;
 692                         }
 693
 694                 }
 695
 696                 private void  CopyToArray (Array arr, int i,
 697                                            EnumeratorMode mode)
 698                 {
 699                         IEnumerator it = new Enumerator (this, mode);
 700
 701                         while (it.MoveNext ()) {
 702                                 arr.SetValue (it.Current, i++);
 703                         }
 704                 }
 705
 706
 707
 708                 //
 709                 // Private static methods
 710                 //
 711                 private static bool TestPrime (int x)
 712                 {
 713                         if ((x & 1) != 0) {
 714                                 for (int n = 3; n< (int)Math.Sqrt (x); n += 2) {
 715                                         if ((x % n) == 0)
 716                                                 return false;
 717                                 }
 718                                 return true;
 719                         }
 720                         // There is only one even prime - 2.
 721                         return (x == 2);
 722                 }
 723
 724                 private static int CalcPrime (int x)
 725                 {
 726                         for (int i = (x & (~1))-1; i< Int32.MaxValue; i += 2) {
 727                                 if (TestPrime (i)) return i;
 728                         }
 729                         return x;
 730                 }
 731
 732                 private static int ToPrime (int x)
 733                 {
 734                         for (int i = 0; i < primeTbl.Length; i++) {
 735                                 if (x <= primeTbl [i])
 736                                         return primeTbl [i];
 737                         }
 738                         return CalcPrime (x);
 739                 }
 740
 741
 742
 743
 744                 //
 745                 // Inner classes
 746                 //
 747
 748                 private enum EnumeratorMode : int {KEY_MODE = 0, VALUE_MODE, ENTRY_MODE};
 749
 750                 private sealed class Enumerator : IDictionaryEnumerator, IEnumerator {
 751
 752                         private Hashtable host;
 753                         private int stamp;
 754                         private int pos;
 755                         private int size;
 756                         private EnumeratorMode mode;
 757
 758                         private Object currentKey;
 759                         private Object currentValue;
 760
 761                         private readonly static string xstr = "Hashtable.Enumerator: snapshot out of sync.";
 762
 763                         public Enumerator (Hashtable host, EnumeratorMode mode) {
 764                                 this.host = host;
 765                                 stamp = host.modificationCount;
 766                                 size = host.table.Length;
 767                                 this.mode = mode;
 768                                 Reset ();
 769                         }
 770
 771                         public Enumerator (Hashtable host)
 772                                    : this (host, EnumeratorMode.KEY_MODE) {}
 773
 774
 775                         private void FailFast ()
 776                         {
 777                                 if (host.modificationCount != stamp) {
 778                                         throw new InvalidOperationException (xstr);
 779                                 }
 780                         }
 781
 782                         public void Reset ()
 783                         {
 784                                 FailFast ();
 785
 786                                 pos = -1;
 787                                 currentKey = null;
 788                                 currentValue = null;
 789                         }
 790
 791                         public bool MoveNext ()
 792                         {
 793                                 FailFast ();
 794
 795                                 if (pos < size) {
 796                                         while (++pos < size) {
 797                                                 Slot entry = host.table [pos];
 798
 799                                                 if (entry.key != null && entry.key != KeyMarker.Removed) {
 800                                                         currentKey = entry.key;
 801                                                         currentValue = entry.value;
 802                                                         return true;
 803                                                 }
 804                                         }
 805                                 }
 806
 807                                 currentKey = null;
 808                                 currentValue = null;
 809                                 return false;
 810                         }
 811
 812                         public DictionaryEntry Entry
 813                         {
 814                                 get {
 815                                         if (currentKey == null) throw new InvalidOperationException ();
 816                                         FailFast ();
 817                                         return new DictionaryEntry (currentKey, currentValue);
 818                                 }
 819                         }
 820
 821                         public Object Key {
 822                                 get {
 823                                         if (currentKey == null) throw new InvalidOperationException ();
 824                                         FailFast ();
 825                                         return currentKey;
 826                                 }
 827                         }
 828
 829                         public Object Value {
 830                                 get {
 831                                         if (currentKey == null) throw new InvalidOperationException ();
 832                                         FailFast ();
 833                                         return currentValue;
 834                                 }
 835                         }
 836
 837                         public Object Current {
 838                                 get {
 839                                         if (currentKey == null) throw new InvalidOperationException ();
 840
 841                                         switch (mode) {
 842                                         case EnumeratorMode.KEY_MODE:
 843                                                 return currentKey;
 844                                         case EnumeratorMode.VALUE_MODE:
 845                                                 return currentValue;
 846                                         case EnumeratorMode.ENTRY_MODE:
 847                                                 return new DictionaryEntry (currentKey, currentValue);
 848                                         }
 849                                         throw new Exception ("should never happen");
 850                                 }
 851                         }
 852                 }
 853
 854
 855
 856                 private class HashKeys : ICollection, IEnumerable {
 857
 858                         private Hashtable host;
 859
 860                         public HashKeys (Hashtable host) {
 861                                 if (host == null)
 862                                         throw new ArgumentNullException ();
 863
 864                                 this.host = host;
 865                         }
 866
 867                         // ICollection
 868
 869                         public virtual int Count {
 870                                 get {
 871                                         return host.Count;
 872                                 }
 873                         }
 874
 875                         public virtual bool IsSynchronized {
 876                                 get {
 877                                         return host.IsSynchronized;
 878                                 }
 879                         }
 880
 881                         public virtual Object SyncRoot {
 882                                 get {return host.SyncRoot;}
 883                         }
 884
 885                         public virtual void CopyTo (Array array, int arrayIndex)
 886                         {
 887                                 if (array == null)
 888                                         throw new ArgumentNullException ("array");
 889                                 if (array.Rank != 1)
 890                                         throw new ArgumentException ("array");
 891                                 if (arrayIndex < 0)
 892                                         throw new ArgumentOutOfRangeException ("arrayIndex");
 893                                 if (array.Length - arrayIndex < Count)
 894                                         throw new ArgumentException ("not enough space");
 895
 896                                 host.CopyToArray (array, arrayIndex, EnumeratorMode.KEY_MODE);
 897                         }
 898
 899                         // IEnumerable
 900
 901                         public virtual IEnumerator GetEnumerator ()
 902                         {
 903                                 return new Hashtable.Enumerator (host, EnumeratorMode.KEY_MODE);
 904                         }
 905                 }
 906
 907
 908                 private class HashValues : ICollection, IEnumerable {
 909
 910                         private Hashtable host;
 911
 912                         public HashValues (Hashtable host) {
 913                                 if (host == null)
 914                                         throw new ArgumentNullException ();
 915
 916                                 this.host = host;
 917                         }
 918
 919                         // ICollection
 920
 921                         public virtual int Count {
 922                                 get {
 923                                         return host.Count;
 924                                 }
 925                         }
 926
 927                         public virtual bool IsSynchronized {
 928                                 get {
 929                                         return host.IsSynchronized;
 930                                 }
 931                         }
 932
 933                         public virtual Object SyncRoot {
 934                                 get {
 935                                         return host.SyncRoot;
 936                                 }
 937                         }
 938
 939                         public virtual void CopyTo (Array array, int arrayIndex)
 940                         {
 941                                 if (array == null)
 942                                         throw new ArgumentNullException ("array");
 943                                 if (array.Rank != 1)
 944                                         throw new ArgumentException ("array");
 945                                 if (arrayIndex < 0)
 946                                         throw new ArgumentOutOfRangeException ("arrayIndex");
 947                                 if (array.Length - arrayIndex < Count)
 948                                         throw new ArgumentException ("not enough space");
 949
 950                                 host.CopyToArray (array, arrayIndex, EnumeratorMode.VALUE_MODE);
 951                         }
 952
 953                         // IEnumerable
 954
 955                         public virtual IEnumerator GetEnumerator ()
 956                         {
 957                                 return new Hashtable.Enumerator (host, EnumeratorMode.VALUE_MODE);
 958                         }
 959                 }
 960
 961
 962                 [Serializable]
 963                 private class SyncHashtable : Hashtable, IEnumerable {
 964
 965                         private Hashtable host;
 966
 967                         public SyncHashtable (Hashtable host) {
 968                                 if (host == null)
 969                                         throw new ArgumentNullException ();
 970
 971                                 this.host = host;
 972                         }
 973
 974                         internal SyncHashtable (SerializationInfo info, StreamingContext context)
 975                         {
 976                                 host = (Hashtable) info.GetValue("ParentTable", typeof(Hashtable));
 977                         }
 978
 979                         public override void GetObjectData (SerializationInfo info, StreamingContext context)
 980                         {
 981                                 info.AddValue ("ParentTable", host);
 982                         }
 983
 984                         // ICollection
 985
 986                         public override int Count {
 987                                 get {
 988                                         return host.Count;
 989                                 }
 990                         }
 991
 992                         public override bool IsSynchronized {
 993                                 get {
 994                                         return true;
 995                                 }
 996                         }
 997
 998                         public override Object SyncRoot {
 999                                 get {
1000                                         return host.SyncRoot;
1001                                 }
1002                         }
1003
1004
1005
1006                         // IDictionary
1007
1008                         public override bool IsFixedSize {
1009                                 get {
1010                                         return host.IsFixedSize;
1011                                 }
1012                         }
1013
1014
1015                         public override bool IsReadOnly {
1016                                 get {
1017                                         return host.IsReadOnly;
1018                                 }
1019                         }
1020
1021                         public override ICollection Keys {
1022                                 get {
1023                                         ICollection keys = null;
1024                                         lock (host.SyncRoot) {
1025                                                 keys = host.Keys;
1026                                         }
1027                                         return keys;
1028                                 }
1029                         }
1030
1031                         public override ICollection Values {
1032                                 get {
1033                                         ICollection vals = null;
1034                                         lock (host.SyncRoot) {
1035                                                 vals = host.Values;
1036                                         }
1037                                         return vals;
1038                                 }
1039                         }
1040
1041
1042
1043                         public override Object this [Object key] {
1044                                 get {
1045                                         return host.GetImpl (key);
1046                                 }
1047                                 set {
1048                                         lock (host.SyncRoot) {
1049                                                 host.PutImpl (key, value, true);
1050                                         }
1051                                 }
1052                         }
1053
1054                         // IEnumerable
1055
1056                         IEnumerator IEnumerable.GetEnumerator ()
1057                         {
1058                                 return new Enumerator (host, EnumeratorMode.KEY_MODE);
1059                         }
1060
1061
1062
1063
1064                         // ICollection
1065
1066                         public override void CopyTo (Array array, int arrayIndex)
1067                         {
1068                                 host.CopyTo (array, arrayIndex);
1069                         }
1070
1071
1072                         // IDictionary
1073
1074                         public override void Add (Object key, Object value)
1075                         {
1076                                 lock (host.SyncRoot) {
1077                                         host.PutImpl (key, value, false);
1078                                 }
1079                         }
1080
1081                         public override void Clear ()
1082                         {
1083                                 lock (host.SyncRoot) {
1084                                         host.Clear ();
1085                                 }
1086                         }
1087
1088                         public override bool Contains (Object key)
1089                         {
1090                                 return (host.Find (key) >= 0);
1091                         }
1092
1093                         public override IDictionaryEnumerator GetEnumerator ()
1094                         {
1095                                 return new Enumerator (host, EnumeratorMode.ENTRY_MODE);
1096                         }
1097
1098                         public override void Remove (Object key)
1099                         {
1100                                 lock (host.SyncRoot) {
1101                                         host.Remove (key);
1102                                 }
1103                         }
1104
1105
1106
1107                         public override bool ContainsKey (object key)
1108                         {
1109                                 return host.Contains (key);
1110                         }
1111
1112                         public override bool ContainsValue (object value)
1113                         {
1114                                 return host.ContainsValue (value);
1115                         }
1116
1117
1118                         // ICloneable
1119
1120                         public override object Clone ()
1121                         {
1122                                 lock(host.SyncRoot) {
1123                                         return new SyncHashtable( (Hashtable) host.Clone () );
1124                                 }
1125                         }
1126
1127                 } // SyncHashtable
1128
1129
1130         } // Hashtable
1131
1132 }