1 /* 2 * reserved comment block 3 * DO NOT REMOVE OR ALTER! 4 */ 5 /* 6 * Copyright 1999-2004 The Apache Software Foundation. 7 * 8 * Licensed under the Apache License, Version 2.0 (the "License"); 9 * you may not use this file except in compliance with the License. 10 * You may obtain a copy of the License at 11 * 12 * http://www.apache.org/licenses/LICENSE-2.0 13 * 14 * Unless required by applicable law or agreed to in writing, software 15 * distributed under the License is distributed on an "AS IS" BASIS, 16 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 17 * See the License for the specific language governing permissions and 18 * limitations under the License. 19 */ 20 /* 21 * $Id: ExpandedNameTable.java,v 1.2.4.1 2005/09/15 08:15:06 suresh_emailid Exp $ 22 */ 23 package com.sun.org.apache.xml.internal.dtm.ref; 24 25 import com.sun.org.apache.xml.internal.dtm.DTM; 26 27 /** 28 * This is a default implementation of a table that manages mappings from 29 * expanded names to expandedNameIDs. 30 * 31 * %OPT% The performance of the getExpandedTypeID() method is very important 32 * to DTM building. To get the best performance out of this class, we implement 33 * a simple hash algorithm directly into this class, instead of using the 34 * inefficient java.util.Hashtable. The code for the get and put operations 35 * are combined in getExpandedTypeID() method to share the same hash calculation 36 * code. We only need to implement the rehash() interface which is used to 37 * expand the hash table. 38 */ 39 public class ExpandedNameTable 40 { 41 42 /** Array of extended types for this document */ 43 private ExtendedType[] m_extendedTypes; 44 45 /** The initial size of the m_extendedTypes array */ 46 private static int m_initialSize = 128; 47 48 /** Next available extended type */ 49 // %REVIEW% Since this is (should be) always equal 50 // to the length of m_extendedTypes, do we need this? 51 private int m_nextType; 52 53 // These are all the types prerotated, for caller convenience. 54 public static final int ELEMENT = ((int)DTM.ELEMENT_NODE) ; 55 public static final int ATTRIBUTE = ((int)DTM.ATTRIBUTE_NODE) ; 56 public static final int TEXT = ((int)DTM.TEXT_NODE) ; 57 public static final int CDATA_SECTION = ((int)DTM.CDATA_SECTION_NODE) ; 58 public static final int ENTITY_REFERENCE = ((int)DTM.ENTITY_REFERENCE_NODE) ; 59 public static final int ENTITY = ((int)DTM.ENTITY_NODE) ; 60 public static final int PROCESSING_INSTRUCTION = ((int)DTM.PROCESSING_INSTRUCTION_NODE) ; 61 public static final int COMMENT = ((int)DTM.COMMENT_NODE) ; 62 public static final int DOCUMENT = ((int)DTM.DOCUMENT_NODE) ; 63 public static final int DOCUMENT_TYPE = ((int)DTM.DOCUMENT_TYPE_NODE) ; 64 public static final int DOCUMENT_FRAGMENT =((int)DTM.DOCUMENT_FRAGMENT_NODE) ; 65 public static final int NOTATION = ((int)DTM.NOTATION_NODE) ; 66 public static final int NAMESPACE = ((int)DTM.NAMESPACE_NODE) ; 67 68 /** Workspace for lookup. NOT THREAD SAFE! 69 * */ 70 ExtendedType hashET = new ExtendedType(-1, "", ""); 71 72 /** The array to store the default extended types. */ 73 private static ExtendedType[] m_defaultExtendedTypes; 74 75 /** 76 * The default load factor of the Hashtable. 77 * This is used to calcualte the threshold. 78 */ 79 private static float m_loadFactor = 0.75f; 80 81 /** 82 * The initial capacity of the hash table. Use a bigger number 83 * to avoid the cost of expanding the table. 84 */ 85 private static int m_initialCapacity = 203; 86 87 /** 88 * The capacity of the hash table, i.e. the size of the 89 * internal HashEntry array. 90 */ 91 private int m_capacity; 92 93 /** 94 * The threshold of the hash table, which is equal to capacity * loadFactor. 95 * If the number of entries in the hash table is bigger than the threshold, 96 * the hash table needs to be expanded. 97 */ 98 private int m_threshold; 99 100 /** 101 * The internal array to store the hash entries. 102 * Each array member is a slot for a hash bucket. 103 */ 104 private HashEntry[] m_table; 105 106 /** 107 * Init default values 108 */ 109 static { 110 m_defaultExtendedTypes = new ExtendedType[DTM.NTYPES]; 111 112 for (int i = 0; i < DTM.NTYPES; i++) 113 { 114 m_defaultExtendedTypes[i] = new ExtendedType(i, "", ""); 115 } 116 } 117 118 /** 119 * Create an expanded name table. 120 */ ExpandedNameTable()121 public ExpandedNameTable() 122 { 123 m_capacity = m_initialCapacity; 124 m_threshold = (int)(m_capacity * m_loadFactor); 125 m_table = new HashEntry[m_capacity]; 126 127 initExtendedTypes(); 128 } 129 130 131 /** 132 * Initialize the vector of extended types with the 133 * basic DOM node types. 134 */ initExtendedTypes()135 private void initExtendedTypes() 136 { 137 m_extendedTypes = new ExtendedType[m_initialSize]; 138 for (int i = 0; i < DTM.NTYPES; i++) { 139 m_extendedTypes[i] = m_defaultExtendedTypes[i]; 140 m_table[i] = new HashEntry(m_defaultExtendedTypes[i], i, i, null); 141 } 142 143 m_nextType = DTM.NTYPES; 144 } 145 146 /** 147 * Given an expanded name represented by namespace, local name and node type, 148 * return an ID. If the expanded-name does not exist in the internal tables, 149 * the entry will be created, and the ID will be returned. Any additional 150 * nodes that are created that have this expanded name will use this ID. 151 * 152 * @param namespace The namespace 153 * @param localName The local name 154 * @param type The node type 155 * 156 * @return the expanded-name id of the node. 157 */ getExpandedTypeID(String namespace, String localName, int type)158 public int getExpandedTypeID(String namespace, String localName, int type) 159 { 160 return getExpandedTypeID(namespace, localName, type, false); 161 } 162 163 /** 164 * Given an expanded name represented by namespace, local name and node type, 165 * return an ID. If the expanded-name does not exist in the internal tables, 166 * the entry will be created, and the ID will be returned. Any additional 167 * nodes that are created that have this expanded name will use this ID. 168 * <p> 169 * If searchOnly is true, we will return -1 if the name is not found in the 170 * table, otherwise the name is added to the table and the expanded name id 171 * of the new entry is returned. 172 * 173 * @param namespace The namespace 174 * @param localName The local name 175 * @param type The node type 176 * @param searchOnly If it is true, we will only search for the expanded name. 177 * -1 is return is the name is not found. 178 * 179 * @return the expanded-name id of the node. 180 */ getExpandedTypeID(String namespace, String localName, int type, boolean searchOnly)181 public int getExpandedTypeID(String namespace, String localName, int type, boolean searchOnly) 182 { 183 if (null == namespace) 184 namespace = ""; 185 if (null == localName) 186 localName = ""; 187 188 // Calculate the hash code 189 int hash = type + namespace.hashCode() + localName.hashCode(); 190 191 // Redefine the hashET object to represent the new expanded name. 192 hashET.redefine(type, namespace, localName, hash); 193 194 // Calculate the index into the HashEntry table. 195 int index = hash % m_capacity; 196 if (index < 0) 197 index = -index; 198 199 // Look up the expanded name in the hash table. Return the id if 200 // the expanded name is already in the hash table. 201 for (HashEntry e = m_table[index]; e != null; e = e.next) 202 { 203 if (e.hash == hash && e.key.equals(hashET)) 204 return e.value; 205 } 206 207 if (searchOnly) 208 { 209 return DTM.NULL; 210 } 211 212 // Expand the internal HashEntry array if necessary. 213 if (m_nextType > m_threshold) { 214 rehash(); 215 index = hash % m_capacity; 216 if (index < 0) 217 index = -index; 218 } 219 220 // Create a new ExtendedType object 221 ExtendedType newET = new ExtendedType(type, namespace, localName, hash); 222 223 // Expand the m_extendedTypes array if necessary. 224 if (m_extendedTypes.length == m_nextType) { 225 ExtendedType[] newArray = new ExtendedType[m_extendedTypes.length * 2]; 226 System.arraycopy(m_extendedTypes, 0, newArray, 0, 227 m_extendedTypes.length); 228 m_extendedTypes = newArray; 229 } 230 231 m_extendedTypes[m_nextType] = newET; 232 233 // Create a new hash entry for the new ExtendedType and put it into 234 // the table. 235 HashEntry entry = new HashEntry(newET, m_nextType, hash, m_table[index]); 236 m_table[index] = entry; 237 238 return m_nextType++; 239 } 240 241 /** 242 * Increases the capacity of and internally reorganizes the hashtable, 243 * in order to accommodate and access its entries more efficiently. 244 * This method is called when the number of keys in the hashtable exceeds 245 * this hashtable's capacity and load factor. 246 */ rehash()247 private void rehash() 248 { 249 int oldCapacity = m_capacity; 250 HashEntry[] oldTable = m_table; 251 252 int newCapacity = 2 * oldCapacity + 1; 253 m_capacity = newCapacity; 254 m_threshold = (int)(newCapacity * m_loadFactor); 255 256 m_table = new HashEntry[newCapacity]; 257 for (int i = oldCapacity-1; i >=0 ; i--) 258 { 259 for (HashEntry old = oldTable[i]; old != null; ) 260 { 261 HashEntry e = old; 262 old = old.next; 263 264 int newIndex = e.hash % newCapacity; 265 if (newIndex < 0) 266 newIndex = -newIndex; 267 268 e.next = m_table[newIndex]; 269 m_table[newIndex] = e; 270 } 271 } 272 } 273 274 /** 275 * Given a type, return an expanded name ID.Any additional nodes that are 276 * created that have this expanded name will use this ID. 277 * 278 * @return the expanded-name id of the node. 279 */ getExpandedTypeID(int type)280 public int getExpandedTypeID(int type) 281 { 282 return type; 283 } 284 285 /** 286 * Given an expanded-name ID, return the local name part. 287 * 288 * @param ExpandedNameID an ID that represents an expanded-name. 289 * @return String Local name of this node, or null if the node has no name. 290 */ getLocalName(int ExpandedNameID)291 public String getLocalName(int ExpandedNameID) 292 { 293 return m_extendedTypes[ExpandedNameID].getLocalName(); 294 } 295 296 /** 297 * Given an expanded-name ID, return the local name ID. 298 * 299 * @param ExpandedNameID an ID that represents an expanded-name. 300 * @return The id of this local name. 301 */ getLocalNameID(int ExpandedNameID)302 public final int getLocalNameID(int ExpandedNameID) 303 { 304 // ExtendedType etype = m_extendedTypes[ExpandedNameID]; 305 if (m_extendedTypes[ExpandedNameID].getLocalName().equals("")) 306 return 0; 307 else 308 return ExpandedNameID; 309 } 310 311 312 /** 313 * Given an expanded-name ID, return the namespace URI part. 314 * 315 * @param ExpandedNameID an ID that represents an expanded-name. 316 * @return String URI value of this node's namespace, or null if no 317 * namespace was resolved. 318 */ getNamespace(int ExpandedNameID)319 public String getNamespace(int ExpandedNameID) 320 { 321 String namespace = m_extendedTypes[ExpandedNameID].getNamespace(); 322 return (namespace.equals("") ? null : namespace); 323 } 324 325 /** 326 * Given an expanded-name ID, return the namespace URI ID. 327 * 328 * @param ExpandedNameID an ID that represents an expanded-name. 329 * @return The id of this namespace. 330 */ getNamespaceID(int ExpandedNameID)331 public final int getNamespaceID(int ExpandedNameID) 332 { 333 //ExtendedType etype = m_extendedTypes[ExpandedNameID]; 334 if (m_extendedTypes[ExpandedNameID].getNamespace().equals("")) 335 return 0; 336 else 337 return ExpandedNameID; 338 } 339 340 /** 341 * Given an expanded-name ID, return the local name ID. 342 * 343 * @param ExpandedNameID an ID that represents an expanded-name. 344 * @return The id of this local name. 345 */ getType(int ExpandedNameID)346 public final short getType(int ExpandedNameID) 347 { 348 //ExtendedType etype = m_extendedTypes[ExpandedNameID]; 349 return (short)m_extendedTypes[ExpandedNameID].getNodeType(); 350 } 351 352 /** 353 * Return the size of the ExpandedNameTable 354 * 355 * @return The size of the ExpandedNameTable 356 */ getSize()357 public int getSize() 358 { 359 return m_nextType; 360 } 361 362 /** 363 * Return the array of extended types 364 * 365 * @return The array of extended types 366 */ getExtendedTypes()367 public ExtendedType[] getExtendedTypes() 368 { 369 return m_extendedTypes; 370 } 371 372 /** 373 * Inner class which represents a hash table entry. 374 * The field next points to the next entry which is hashed into 375 * the same bucket in the case of "hash collision". 376 */ 377 private static final class HashEntry 378 { 379 ExtendedType key; 380 int value; 381 int hash; 382 HashEntry next; 383 HashEntry(ExtendedType key, int value, int hash, HashEntry next)384 protected HashEntry(ExtendedType key, int value, int hash, HashEntry next) 385 { 386 this.key = key; 387 this.value = value; 388 this.hash = hash; 389 this.next = next; 390 } 391 } 392 393 } 394