mcs/class/referencesource/System.Xml/System/Xml/NameTable.cs

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