2 // System.Xml.NameTable.cs
5 // Duncan Mak (duncan@ximian.com)
6 // Ben Maurer (bmaurer@users.sourceforge.net)
13 // Permission is hereby granted, free of charge, to any person obtaining
14 // a copy of this software and associated documentation files (the
15 // "Software"), to deal in the Software without restriction, including
16 // without limitation the rights to use, copy, modify, merge, publish,
17 // distribute, sublicense, and/or sell copies of the Software, and to
18 // permit persons to whom the Software is furnished to do so, subject to
19 // the following conditions:
21 // The above copyright notice and this permission notice shall be
22 // included in all copies or substantial portions of the Software.
24 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
34 using System.Collections;
36 namespace System.Xml {
39 // This class implements the name table as a simple
40 // hashtable, using buckets and a linked list.
42 public class NameTable : XmlNameTable {
44 const int INITIAL_BUCKETS = 2 << 6; // 64
46 int count = INITIAL_BUCKETS;
47 Entry [] buckets = new Entry [INITIAL_BUCKETS];
50 public NameTable () {}
57 public Entry (string str, int hash, Entry next)
60 this.len = str.Length;
66 public override string Add (char [] key, int start, int len)
68 if (((0 > start) && (start >= key.Length))
69 || ((0 > len) && (len >= key.Length - len)))
70 throw new IndexOutOfRangeException ("The Index is out of range.");
72 if (len == 0) return String.Empty;
75 // This is from the String.Gethash () icall
76 int end = start + len;
77 for (int i = start; i < end; i++)
78 h = (h << 5) - h + key [i];
83 for (Entry e = buckets [h % count]; e != null; e = e.next) {
84 if (e.hash == h && e.len == len && StrEqArray (e.str, key, start))
87 return AddEntry (new string (key, start, len), h);
90 public override string Add (string key)
92 if (key == null) throw new ArgumentNullException ("key");
94 int keyLen = key.Length;
95 if (keyLen == 0) return String.Empty;
98 // This is from the String.Gethash () icall
99 for (int i = 0; i < keyLen; i++)
100 h = (h << 5) - h + key [i];
105 for (Entry e = buckets [h % count]; e != null; e = e.next) {
106 if (e.hash == h && e.len == key.Length && e.str == key)
110 return AddEntry (key, h);
113 public override string Get (char [] key, int start, int len)
115 if (((0 > start) && (start >= key.Length))
116 || ((0 > len) && (len >= key.Length - len)))
117 throw new IndexOutOfRangeException ("The Index is out of range.");
119 if (len == 0) return String.Empty;
122 // This is from the String.Gethash () icall
123 int end = start + len;
124 for (int i = start; i < end; i++)
125 h = (h << 5) - h + key [i];
129 for (Entry e = buckets [h % count]; e != null; e = e.next) {
130 if (e.hash == h && e.len == len && StrEqArray (e.str, key, start))
137 public override string Get (string value) {
138 if (value == null) throw new ArgumentNullException ("value");
140 int valLen = value.Length;
141 if (valLen == 0) return String.Empty;
144 // This is from the String.Gethash () icall
145 for (int i = 0; i < valLen; i++)
146 h = (h << 5) - h + value [i];
150 for (Entry e = buckets [h % count]; e != null; e = e.next) {
151 if (e.hash == h && e.len == value.Length && e.str == value)
158 string AddEntry (string str, int hash)
160 int bucket = hash % count;
161 buckets [bucket] = new Entry (str, hash, buckets [bucket]);
163 // Grow whenever we double in size
164 if (size++ == count) {
166 int csub1 = count - 1;
168 Entry [] newBuckets = new Entry [count];
169 for (int i = 0; i < buckets.Length; i++) {
170 Entry root = buckets [i];
173 int newLoc = e.hash & csub1;
175 e.next = newBuckets [newLoc];
176 newBuckets [newLoc] = e;
181 buckets = newBuckets;
187 static bool StrEqArray (string str, char [] str2, int start)
194 if (str[i] != str2[start])