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

   1 //
   2 // System.Xml.NameTable.cs
   3 //
   4 // Authors:
   5 //      Duncan Mak (duncan@ximian.com)
   6 //      Ben Maurer (bmaurer@users.sourceforge.net)
   7 //
   8 // (C) Ximian, Inc.
   9 // (C) 2003 Ben Maurer
  10 //
  11
  12 //
  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:
  20 //
  21 // The above copyright notice and this permission notice shall be
  22 // included in all copies or substantial portions of the Software.
  23 //
  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.
  31 //
  32
  33 using System;
  34 using System.Collections;
  35
  36 namespace System.Xml {
  37
  38         //
  39         // This class implements the name table as a simple
  40         // hashtable, using buckets and a linked list.
  41         //
  42         public class NameTable : XmlNameTable {
  43
  44                 const int INITIAL_BUCKETS = 2 << 6; // 64
  45
  46                 int count = INITIAL_BUCKETS;
  47                 Entry [] buckets = new Entry [INITIAL_BUCKETS];
  48                 int size;
  49
  50                 public NameTable () {}
  51
  52                 class Entry {
  53                         public string str;
  54                         public int hash, len;
  55                         public Entry next;
  56
  57                         public Entry (string str, int hash, Entry next)
  58                         {
  59                                 this.str = str;
  60                                 this.len = str.Length;
  61                                 this.hash = hash;
  62                                 this.next = next;
  63                         }
  64                 }
  65
  66                 public override string Add (char [] key, int start, int len)
  67                 {
  68                         if (((0 > start) && (start >= key.Length))
  69                            || ((0 > len) && (len >= key.Length - len)))
  70                                 throw new IndexOutOfRangeException ("The Index is out of range.");
  71
  72                         if (len == 0) return String.Empty;
  73
  74                         int h = 0;
  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];
  79                         // h must be be >= 0
  80                         h &= 0x7FFFFFFF;
  81
  82
  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))
  85                                         return e.str;
  86                         }
  87                         return AddEntry (new string (key, start, len), h);
  88                 }
  89
  90                 public override string Add (string key)
  91                 {
  92                         if (key == null) throw new ArgumentNullException ("key");
  93
  94                         int keyLen = key.Length;
  95                         if (keyLen == 0) return String.Empty;
  96
  97                         int h = 0;
  98                         // This is from the String.Gethash () icall
  99                         for (int i = 0; i < keyLen; i++)
 100                                 h = (h << 5) - h + key [i];
 101
 102                         // h must be be >= 0
 103                         h &= 0x7FFFFFFF;
 104
 105                         for (Entry e = buckets [h % count]; e != null; e = e.next) {
 106                                 if (e.hash == h && e.len == key.Length && e.str == key)
 107                                         return e.str;
 108                         }
 109
 110                         return AddEntry (key, h);
 111                 }
 112
 113                 public override string Get (char [] key, int start, int len)
 114                 {
 115                         if (((0 > start) && (start >= key.Length))
 116                            || ((0 > len) && (len >= key.Length - len)))
 117                                 throw new IndexOutOfRangeException ("The Index is out of range.");
 118
 119                         if (len == 0) return String.Empty;
 120
 121                         int h = 0;
 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];
 126                         // h must be be >= 0
 127                         h &= 0x7FFFFFFF;
 128
 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))
 131                                         return e.str;
 132                         }
 133
 134                         return null;
 135                 }
 136
 137                 public override string Get (string value) {
 138                         if (value == null) throw new ArgumentNullException ("value");
 139
 140                         int valLen = value.Length;
 141                         if (valLen == 0) return String.Empty;
 142
 143                         int h = 0;
 144                         // This is from the String.Gethash () icall
 145                         for (int i = 0; i < valLen; i++)
 146                                 h = (h << 5) - h + value [i];
 147                         // h must be be >= 0
 148                         h &= 0x7FFFFFFF;
 149
 150                         for (Entry e = buckets [h % count]; e != null; e = e.next) {
 151                                 if (e.hash == h && e.len == value.Length && e.str == value)
 152                                         return e.str;
 153                         }
 154
 155                         return null;
 156                 }
 157
 158                 string AddEntry (string str, int hash)
 159                 {
 160                         int bucket = hash % count;
 161                         buckets [bucket] = new Entry (str, hash, buckets [bucket]);
 162
 163                         // Grow whenever we double in size
 164                         if (size++ == count) {
 165                                 count <<= 1;
 166                                 int csub1 = count - 1;
 167
 168                                 Entry [] newBuckets = new Entry [count];
 169                                 for (int i = 0; i < buckets.Length; i++) {
 170                                         Entry root = buckets [i];
 171                                         Entry e = root;
 172                                         while (e != null) {
 173                                                 int newLoc = e.hash & csub1;
 174                                                 Entry n = e.next;
 175                                                 e.next = newBuckets [newLoc];
 176                                                 newBuckets [newLoc] = e;
 177                                                 e = n;
 178                                         }
 179                                 }
 180
 181                                 buckets = newBuckets;
 182                         }
 183
 184                         return str;
 185                 }
 186
 187                 static bool StrEqArray (string str, char [] str2, int start)
 188                 {
 189                         int i = str.Length;
 190                         i --;
 191                         start += i;
 192                         do
 193                         {
 194                                 if (str[i] != str2[start])
 195                                         return false;
 196
 197                                 i--;
 198                                 start--;
 199                         }
 200                         while(i >= 0);
 201
 202                         return true;
 203                 }
 204         }
 205 }