The Labs \ Source Viewer \ SSCLI \ Microsoft.JScript \ SimpleHashtableEnumerator

  1. // ==++==
  2. //
  3. //
  4. // Copyright (c) 2006 Microsoft Corporation. All rights reserved.
  5. //
  6. // The use and distribution terms for this software are contained in the file
  7. // named license.txt, which can be found in the root of this distribution.
  8. // By using this software in any fashion, you are agreeing to be bound by the
  9. // terms of this license.
  10. //
  11. // You must not remove this notice, or any other, from this software.
  12. //
  13. //
  14. // ==--==
  15. namespace Microsoft.JScript
  16. {
  17.    
  18.     using System;
  19.     using System.Collections;
  20.     using System.Globalization;
  21.     using System.Reflection;
  22.    
  23.     internal sealed class HashtableEntry
  24.     {
  25.         internal object key;
  26.         internal object value;
  27.         internal uint hashCode;
  28.         internal HashtableEntry next;
  29.        
  30.         internal HashtableEntry(object key, object value, uint hashCode, HashtableEntry next)
  31.         {
  32.             this.key = key;
  33.             this.value = value;
  34.             this.hashCode = hashCode;
  35.             this.next = next;
  36.         }
  37.     }
  38.    
  39.     public sealed class SimpleHashtable
  40.     {
  41.         private HashtableEntry[] table;
  42.         internal int count;
  43.         private uint threshold;
  44.        
  45.         public SimpleHashtable(uint threshold)
  46.         {
  47.             if (threshold < 8)
  48.                 threshold = 8;
  49.             this.table = new HashtableEntry[(int)(threshold * 2 - 1)];
  50.             this.count = 0;
  51.             this.threshold = threshold;
  52.         }
  53.        
  54.         public IDictionaryEnumerator GetEnumerator()
  55.         {
  56.             return new SimpleHashtableEnumerator(this.table);
  57.         }
  58.        
  59.         private HashtableEntry GetHashtableEntry(object key, uint hashCode)
  60.         {
  61.             int index = (int)(hashCode % (uint)this.table.Length);
  62.             HashtableEntry e = this.table[index];
  63.             if (e == null)
  64.                 return null;
  65.             if (e.key == key)
  66.                 return e;
  67.             HashtableEntry prev = e;
  68.             HashtableEntry curr = e.next;
  69.             while (curr != null) {
  70.                 if (curr.key == key)
  71.                     return curr;
  72.                 prev = curr;
  73.                 curr = curr.next;
  74.             }
  75.             if (e.hashCode == hashCode && e.key.Equals(key)) {
  76.                 e.key = key;
  77.                 return e;
  78.             }
  79.             prev = e;
  80.             curr = e.next;
  81.             while (curr != null) {
  82.                 if (curr.hashCode == hashCode && curr.key.Equals(key)) {
  83.                     curr.key = key;
  84.                     return curr;
  85.                 }
  86.                 prev = curr;
  87.                 curr = curr.next;
  88.             }
  89.             return null;
  90.         }
  91.        
  92.         internal object IgnoreCaseGet(string name)
  93.         {
  94.             for (uint i = 0uint n = (uint)this.table.Length; i < n; i++) {
  95.                 HashtableEntry e = this.table[i];
  96.                 while (e != null) {
  97.                     if (String.Compare((string)e.key, name, StringComparison.OrdinalIgnoreCase) == 0)
  98.                         return e.value;
  99.                     e = e.next;
  100.                 }
  101.             }
  102.             return null;
  103.         }
  104.        
  105.         private void Rehash()
  106.         {
  107.             HashtableEntry[] oldTable = this.table;
  108.             uint threshold = this.threshold = (uint)(oldTable.Length + 1);
  109.             uint newCapacity = threshold * 2 - 1;
  110.             HashtableEntry[] newTable = this.table = new HashtableEntry[newCapacity];
  111.             for (uint i = threshold - 1; i-- > 0;) {
  112.                 for (HashtableEntry old = oldTable[(int)i]; old != null;) {
  113.                     HashtableEntry e = old;
  114.                     old = old.next;
  115.                     int index = (int)(e.hashCode % newCapacity);
  116.                     e.next = newTable[index];
  117.                     newTable[index] = e;
  118.                 }
  119.             }
  120.         }
  121.        
  122.         public void Remove(object key)
  123.         {
  124.             uint hashCode = (uint)key.GetHashCode();
  125.             int index = (int)(hashCode % (uint)this.table.Length);
  126.             HashtableEntry e = this.table[index];
  127.             Debug.Assert(e != null);
  128.             this.count--;
  129.             while (e != null && e.hashCode == hashCode && (e.key == key || e.key.Equals(key)))
  130.                 e = e.next;
  131.             this.table[index] = e;
  132.             do {
  133.                 if (e == null)
  134.                     return;
  135.                 HashtableEntry f = e.next;
  136.                 while (f != null && f.hashCode == hashCode && (f.key == key || f.key.Equals(key)))
  137.                     f = f.next;
  138.                 e.next = f;
  139.                 e = f;
  140.             }
  141.             while (true);
  142.         }
  143.        
  144.         public object this[object key]
  145.         {
  146.             get {
  147.                 HashtableEntry e = this.GetHashtableEntry(key, (uint)key.GetHashCode());
  148.                 if (e == null)
  149.                     return null;
  150.                 return e.value;
  151.             }
  152.             set {
  153.                 uint hashCode = (uint)key.GetHashCode();
  154.                 HashtableEntry e = this.GetHashtableEntry(key, hashCode);
  155.                 if (e != null) {
  156.                     e.value = value;
  157.                     return;
  158.                 }
  159.                 if (++this.count >= this.threshold)
  160.                     this.Rehash();
  161.                 int index = (int)(hashCode % (uint)this.table.Length);
  162.                 this.table[index] = new HashtableEntry(key, value, hashCode, this.table[index]);
  163.             }
  164.         }
  165.        
  166.     }
  167.    
  168.     internal sealed class SimpleHashtableEnumerator : IDictionaryEnumerator
  169.     {
  170.         private HashtableEntry[] table;
  171.         private int count;
  172.         private int index;
  173.         private HashtableEntry currentEntry;
  174.        
  175.         internal SimpleHashtableEnumerator(HashtableEntry[] table)
  176.         {
  177.             this.table = table;
  178.             this.count = table.Length;
  179.             this.index = -1;
  180.             this.currentEntry = null;
  181.         }
  182.        
  183.         public object Current {
  184.             //Used by expando classes to enumerate all the keys in the hashtable
  185.             get { return this.Key; }
  186.         }
  187.        
  188.         public DictionaryEntry Entry {
  189.             get { return new DictionaryEntry(this.Key, this.Value); }
  190.         }
  191.        
  192.         public object Key {
  193.             get { return this.currentEntry.key; }
  194.         }
  195.        
  196.         public bool MoveNext()
  197.         {
  198.             HashtableEntry[] table = this.table;
  199.             if (this.currentEntry != null) {
  200.                 this.currentEntry = this.currentEntry.next;
  201.                 if (this.currentEntry != null)
  202.                     return true;
  203.             }
  204.             for (int i = ++this.indexint n = this.count; i < n; i++)
  205.                 if (table[i] != null) {
  206.                     this.index = i;
  207.                     this.currentEntry = table[i];
  208.                     return true;
  209.                 }
  210.             return false;
  211.         }
  212.        
  213.         public void Reset()
  214.         {
  215.             this.index = -1;
  216.             this.currentEntry = null;
  217.         }
  218.        
  219.         public object Value {
  220.             get { return this.currentEntry.value; }
  221.         }
  222.        
  223.     }
  224.    
  225. }

Developer Fusion