The Labs \ Source Viewer \ SSCLI \ System.Xml \ Entry

  1. //------------------------------------------------------------------------------
  2. // <copyright file="NameTable.cs" company="Microsoft">
  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. // </copyright>
  14. //------------------------------------------------------------------------------
  15. using System;
  16. namespace System.Xml
  17. {
  18.    
  19.     /// <include file='doc\NameTable.uex' path='docs/doc[@for="NameTable"]/*' />
  20.     /// <devdoc>
  21.     /// <para>
  22.     /// XmlNameTable implemented as a simple hash table.
  23.     /// </para>
  24.     /// </devdoc>
  25.     public class NameTable : XmlNameTable
  26.     {
  27.         //
  28.         // Private types
  29.         //
  30.         class Entry
  31.         {
  32.             internal string str;
  33.             internal int hashCode;
  34.             internal Entry next;
  35.            
  36.             internal Entry(string str, int hashCode, Entry next)
  37.             {
  38.                 this.str = str;
  39.                 this.hashCode = hashCode;
  40.                 this.next = next;
  41.             }
  42.         }
  43.        
  44.         //
  45.         // Fields
  46.         //
  47.         Entry[] entries;
  48.         int count;
  49.         int mask;
  50.         int hashCodeRandomizer;
  51.        
  52.         //
  53.         // Constructor
  54.         //
  55.         /// <include file='doc\NameTable.uex' path='docs/doc[@for="NameTable.NameTable"]/*' />
  56.         /// <devdoc>
  57.         /// Public constructor.
  58.         /// </devdoc>
  59.         public NameTable()
  60.         {
  61.             mask = 31;
  62.             entries = new Entry[mask + 1];
  63.             hashCodeRandomizer = Environment.TickCount;
  64.         }
  65.        
  66.         //
  67.         // XmlNameTable public methods
  68.         //
  69.         /// <include file='doc\NameTable.uex' path='docs/doc[@for="NameTable.Add"]/*' />
  70.         /// <devdoc>
  71.         /// Add the given string to the NameTable or return
  72.         /// the existing string if it is already in the NameTable.
  73.         /// </devdoc>
  74.         public override string Add(string key)
  75.         {
  76.             if (key == null) {
  77.                 throw new ArgumentNullException("key");
  78.             }
  79.             int len = key.Length;
  80.             if (len == 0) {
  81.                 return string.Empty;
  82.             }
  83.             int hashCode = len + hashCodeRandomizer;
  84.             // use key.Length to eliminate the rangecheck
  85.             for (int i = 0; i < key.Length; i++) {
  86.                 hashCode += (hashCode << 7) ^ key[i];
  87.             }
  88.             // mix it a bit more
  89.             hashCode -= hashCode >> 17;
  90.             hashCode -= hashCode >> 11;
  91.             hashCode -= hashCode >> 5;
  92.            
  93.             for (Entry e = entries[hashCode & mask]; e != null; e = e.next) {
  94.                 if (e.hashCode == hashCode && e.str.Equals(key)) {
  95.                     return e.str;
  96.                 }
  97.             }
  98.             return AddEntry(key, hashCode);
  99.         }
  100.        
  101.         /// <include file='doc\NameTable.uex' path='docs/doc[@for="NameTable.Add1"]/*' />
  102.         /// <devdoc>
  103.         /// Add the given string to the NameTable or return
  104.         /// the existing string if it is already in the NameTable.
  105.         /// </devdoc>
  106.         public override string Add(char[] key, int start, int len)
  107.         {
  108.             if (len == 0) {
  109.                 return string.Empty;
  110.             }
  111.            
  112.             int hashCode = len + hashCodeRandomizer;
  113.             hashCode += (hashCode << 7) ^ key[start];
  114.             // this will throw IndexOutOfRangeException in case the start index is invalid
  115.             int end = start + len;
  116.             for (int i = start + 1; i < end; i++) {
  117.                 hashCode += (hashCode << 7) ^ key[i];
  118.             }
  119.             // mix it a bit more
  120.             hashCode -= hashCode >> 17;
  121.             hashCode -= hashCode >> 11;
  122.             hashCode -= hashCode >> 5;
  123.            
  124.             for (Entry e = entries[hashCode & mask]; e != null; e = e.next) {
  125.                 if (e.hashCode == hashCode && TextEquals(e.str, key, start)) {
  126.                     return e.str;
  127.                 }
  128.             }
  129.             return AddEntry(new string(key, start, len), hashCode);
  130.         }
  131.        
  132.         /// <include file='doc\NameTable.uex' path='docs/doc[@for="NameTable.Get"]/*' />
  133.         /// <devdoc>
  134.         /// Find the matching string in the NameTable.
  135.         /// </devdoc>
  136.         public override string Get(string value)
  137.         {
  138.             if (value == null) {
  139.                 throw new ArgumentNullException("value");
  140.             }
  141.             if (value.Length == 0) {
  142.                 return string.Empty;
  143.             }
  144.            
  145.             int len = value.Length + hashCodeRandomizer;
  146.             int hashCode = len;
  147.             // use value.Length to eliminate the rangecheck
  148.             for (int i = 0; i < value.Length; i++) {
  149.                 hashCode += (hashCode << 7) ^ value[i];
  150.             }
  151.             // mix it a bit more
  152.             hashCode -= hashCode >> 17;
  153.             hashCode -= hashCode >> 11;
  154.             hashCode -= hashCode >> 5;
  155.            
  156.             for (Entry e = entries[hashCode & mask]; e != null; e = e.next) {
  157.                 if (e.hashCode == hashCode && e.str.Equals(value)) {
  158.                     return e.str;
  159.                 }
  160.             }
  161.             return null;
  162.         }
  163.        
  164.         /// <include file='doc\NameTable.uex' path='docs/doc[@for="NameTable.Get1"]/*' />
  165.         /// <devdoc>
  166.         /// Find the matching string atom given a range of
  167.         /// characters.
  168.         /// </devdoc>
  169.         public override string Get(char[] key, int start, int len)
  170.         {
  171.             if (len == 0) {
  172.                 return string.Empty;
  173.             }
  174.            
  175.             int hashCode = len + hashCodeRandomizer;
  176.             hashCode += (hashCode << 7) ^ key[start];
  177.             // this will throw IndexOutOfRangeException in case the start index is invalid
  178.             int end = start + len;
  179.             for (int i = start + 1; i < end; i++) {
  180.                 hashCode += (hashCode << 7) ^ key[i];
  181.             }
  182.             // mix it a bit more
  183.             hashCode -= hashCode >> 17;
  184.             hashCode -= hashCode >> 11;
  185.             hashCode -= hashCode >> 5;
  186.            
  187.             for (Entry e = entries[hashCode & mask]; e != null; e = e.next) {
  188.                 if (e.hashCode == hashCode && TextEquals(e.str, key, start)) {
  189.                     return e.str;
  190.                 }
  191.             }
  192.             return null;
  193.         }
  194.        
  195.         //
  196.         // Private methods
  197.         //
  198.        
  199.         private string AddEntry(string str, int hashCode)
  200.         {
  201.             int index = hashCode & mask;
  202.             Entry e = new Entry(str, hashCode, entries[index]);
  203.             entries[index] = e;
  204.             if (count++ == mask) {
  205.                 Grow();
  206.             }
  207.             return e.str;
  208.         }
  209.        
  210.         private void Grow()
  211.         {
  212.             int newMask = mask * 2 + 1;
  213.             Entry[] oldEntries = entries;
  214.             Entry[] newEntries = new Entry[newMask + 1];
  215.            
  216.             // use oldEntries.Length to eliminate the rangecheck
  217.             for (int i = 0; i < oldEntries.Length; i++) {
  218.                 Entry e = oldEntries[i];
  219.                 while (e != null) {
  220.                     int newIndex = e.hashCode & newMask;
  221.                     Entry tmp = e.next;
  222.                     e.next = newEntries[newIndex];
  223.                     newEntries[newIndex] = e;
  224.                     e = tmp;
  225.                 }
  226.             }
  227.            
  228.             entries = newEntries;
  229.             mask = newMask;
  230.         }
  231.        
  232.         private static bool TextEquals(string array, char[] text, int start)
  233.         {
  234.             // use array.Length to eliminate the rangecheck
  235.             for (int i = 0; i < array.Length; i++) {
  236.                 if (array[i] != text[start + i]) {
  237.                     return false;
  238.                 }
  239.             }
  240.             return true;
  241.         }
  242.     }
  243. }

Developer Fusion