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 using System;
  13 using System.Collections;
  14
  15 namespace System.Xml {
  16         //
  17         // This class implements the name table as a simple
  18         // hashtable, using buckets and a linked list.
  19         //
  20         public class NameTable : XmlNameTable {
  21
  22                 const int INITIAL_BUCKETS = 2 << 6; // 64
  23
  24                 int count = INITIAL_BUCKETS;
  25                 Entry [] buckets = new Entry [INITIAL_BUCKETS];
  26                 int size;
  27
  28                 public NameTable () {}
  29
  30                 class Entry {
  31                         public string str;
  32                         public int hash, len;
  33                         public Entry next;
  34
  35                         public Entry (string str, int hash, Entry next)
  36                         {
  37                                 this.str = str;
  38                                 this.len = str.Length;
  39                                 this.hash = hash;
  40                                 this.next = next;
  41                         }
  42                 }
  43
  44                 public override string Add (char [] key, int start, int len)
  45                 {
  46                         if (((0 > start) && (start >= key.Length))
  47                            || ((0 > len) && (len >= key.Length - len)))
  48                                 throw new IndexOutOfRangeException ("The Index is out of range.");
  49
  50                         if (len == 0) return String.Empty;
  51
  52                         int h = 0;
  53                         // This is from the String.Gethash () icall
  54                         for (int i = start; i < len; i++)
  55                                 h = (h << 5) - h + key [i];
  56                         // h must be be >= 0
  57                         h &= 0x7FFFFFFF;
  58
  59
  60                         for (Entry e = buckets [h % count]; e != null; e = e.next) {
  61                                 if (e.hash == h && e.len == len && StrEqArray (e.str, key, start))
  62                                         return e.str;
  63                         }
  64                         return AddEntry (new string (key, start, len), h);
  65                 }
  66
  67                 public override string Add (string key)
  68                 {
  69                         if (key == null) throw new ArgumentNullException ("key");
  70
  71                         int keyLen = key.Length;
  72                         if (keyLen == 0) return String.Empty;
  73
  74                         int h = 0;
  75                         // This is from the String.Gethash () icall
  76                         for (int i = 0; i < keyLen; i++)
  77                                 h = (h << 5) - h + key [i];
  78
  79                         // h must be be >= 0
  80                         h &= 0x7FFFFFFF;
  81
  82                         for (Entry e = buckets [h % count]; e != null; e = e.next) {
  83                                 if (e.hash == h && e.len == key.Length && e.str == key)
  84                                         return e.str;
  85                         }
  86
  87                         return AddEntry (key, h);
  88                 }
  89
  90                 public override string Get (char [] key, int start, int len)
  91                 {
  92                         if (((0 > start) && (start >= key.Length))
  93                            || ((0 > len) && (len >= key.Length - len)))
  94                                 throw new IndexOutOfRangeException ("The Index is out of range.");
  95
  96                         if (len == 0) return String.Empty;
  97
  98                         int h = 0;
  99                         // This is from the String.Gethash () icall
 100                         for (int i = start; i < len; i++)
 101                                 h = (h << 5) - h + key [i];
 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 == len && StrEqArray (e.str, key, start))
 107                                         return e.str;
 108                         }
 109
 110                         return null;
 111                 }
 112
 113                 public override string Get (string value) {
 114                         if (value == null) throw new ArgumentNullException ("value");
 115
 116                         int valLen = value.Length;
 117                         if (valLen == 0) return String.Empty;
 118
 119                         int h = 0;
 120                         // This is from the String.Gethash () icall
 121                         for (int i = 0; i < valLen; i++)
 122                                 h = (h << 5) - h + value [i];
 123                         // h must be be >= 0
 124                         h &= 0x7FFFFFFF;
 125
 126                         for (Entry e = buckets [h % count]; e != null; e = e.next) {
 127                                 if (e.hash == h && e.len == value.Length && e.str == value)
 128                                         return e.str;
 129                         }
 130
 131                         return null;
 132                 }
 133
 134                 string AddEntry (string str, int hash)
 135                 {
 136                         int bucket = hash % count;
 137                         buckets [bucket] = new Entry (str, hash, buckets [bucket]);
 138
 139                         // Grow whenever we double in size
 140                         if (size++ == count) {
 141                                 count <<= 1;
 142                                 int csub1 = count - 1;
 143
 144                                 Entry [] newBuckets = new Entry [count];
 145                                 foreach (Entry root in buckets) {
 146                                         Entry e = root;
 147                                         while (e != null) {
 148                                                 int newLoc = e.hash & csub1;
 149                                                 Entry n = e.next;
 150                                                 e.next = newBuckets [newLoc];
 151                                                 newBuckets [newLoc] = e;
 152                                                 e = n;
 153                                         }
 154                                 }
 155
 156                                 buckets = newBuckets;
 157                         }
 158
 159                         return str;
 160                 }
 161
 162                 static bool StrEqArray (string str, char [] str2, int start)
 163                 {
 164                         for (int i = 0; i < str.Length; i++) {
 165                                 if (str [i] != str2 [start + i])
 166                                         return false;
 167                         }
 168                         return true;
 169                 }
 170         }
 171 }