19f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson/* 29f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Licensed to the Apache Software Foundation (ASF) under one 39f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * or more contributor license agreements. See the NOTICE file 49f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * distributed with this work for additional information 59f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * regarding copyright ownership. The ASF licenses this file 69f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * to you under the Apache License, Version 2.0 (the "License"); 79f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * you may not use this file except in compliance with the License. 89f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * You may obtain a copy of the License at 99f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 109f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * http://www.apache.org/licenses/LICENSE-2.0 119f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 129f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Unless required by applicable law or agreed to in writing, software 139f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * distributed under the License is distributed on an "AS IS" BASIS, 149f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 159f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * See the License for the specific language governing permissions and 169f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * limitations under the License. 179f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 189f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson/* 199f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * $Id: ExpandedNameTable.java 468653 2006-10-28 07:07:05Z minchau $ 209f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 219f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilsonpackage org.apache.xml.dtm.ref; 229f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 239f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilsonimport org.apache.xml.dtm.DTM; 249f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 259f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson/** 269f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * This is a default implementation of a table that manages mappings from 279f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * expanded names to expandedNameIDs. 289f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 299f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * %OPT% The performance of the getExpandedTypeID() method is very important 309f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * to DTM building. To get the best performance out of this class, we implement 319f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * a simple hash algorithm directly into this class, instead of using the 329f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * inefficient java.util.Hashtable. The code for the get and put operations 339f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * are combined in getExpandedTypeID() method to share the same hash calculation 349f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * code. We only need to implement the rehash() interface which is used to 359f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * expand the hash table. 369f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 379f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilsonpublic class ExpandedNameTable 389f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson{ 399f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 409f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** Array of extended types for this document */ 419f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson private ExtendedType[] m_extendedTypes; 429f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 439f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** The initial size of the m_extendedTypes array */ 449f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson private static int m_initialSize = 128; 459f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 469f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** Next available extended type */ 479f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // %REVIEW% Since this is (should be) always equal 489f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // to the length of m_extendedTypes, do we need this? 499f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson private int m_nextType; 509f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 519f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // These are all the types prerotated, for caller convenience. 529f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public static final int ELEMENT = ((int)DTM.ELEMENT_NODE) ; 539f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public static final int ATTRIBUTE = ((int)DTM.ATTRIBUTE_NODE) ; 549f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public static final int TEXT = ((int)DTM.TEXT_NODE) ; 559f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public static final int CDATA_SECTION = ((int)DTM.CDATA_SECTION_NODE) ; 569f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public static final int ENTITY_REFERENCE = ((int)DTM.ENTITY_REFERENCE_NODE) ; 579f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public static final int ENTITY = ((int)DTM.ENTITY_NODE) ; 589f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public static final int PROCESSING_INSTRUCTION = ((int)DTM.PROCESSING_INSTRUCTION_NODE) ; 599f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public static final int COMMENT = ((int)DTM.COMMENT_NODE) ; 609f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public static final int DOCUMENT = ((int)DTM.DOCUMENT_NODE) ; 619f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public static final int DOCUMENT_TYPE = ((int)DTM.DOCUMENT_TYPE_NODE) ; 629f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public static final int DOCUMENT_FRAGMENT =((int)DTM.DOCUMENT_FRAGMENT_NODE) ; 639f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public static final int NOTATION = ((int)DTM.NOTATION_NODE) ; 649f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public static final int NAMESPACE = ((int)DTM.NAMESPACE_NODE) ; 659f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 669f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** Workspace for lookup. NOT THREAD SAFE! 679f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * */ 689f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson ExtendedType hashET = new ExtendedType(-1, "", ""); 699f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 709f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** The array to store the default extended types. */ 719f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson private static ExtendedType[] m_defaultExtendedTypes; 729f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 739f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 749f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * The default load factor of the Hashtable. 759f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * This is used to calcualte the threshold. 769f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 779f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson private static float m_loadFactor = 0.75f; 789f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 799f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 809f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * The initial capacity of the hash table. Use a bigger number 819f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * to avoid the cost of expanding the table. 829f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 839f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson private static int m_initialCapacity = 203; 849f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 859f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 869f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * The capacity of the hash table, i.e. the size of the 879f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * internal HashEntry array. 889f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 899f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson private int m_capacity; 909f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 919f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 929f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * The threshold of the hash table, which is equal to capacity * loadFactor. 939f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * If the number of entries in the hash table is bigger than the threshold, 949f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * the hash table needs to be expanded. 959f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 969f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson private int m_threshold; 979f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 989f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 999f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * The internal array to store the hash entries. 1009f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Each array member is a slot for a hash bucket. 1019f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 1029f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson private HashEntry[] m_table; 1039f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1049f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 1059f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Init default values 1069f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 1079f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson static { 1089f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_defaultExtendedTypes = new ExtendedType[DTM.NTYPES]; 1099f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1109f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson for (int i = 0; i < DTM.NTYPES; i++) 1119f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1129f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_defaultExtendedTypes[i] = new ExtendedType(i, "", ""); 1139f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1149f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1159f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1169f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 1179f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Create an expanded name table. 1189f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 1199f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public ExpandedNameTable() 1209f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1219f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_capacity = m_initialCapacity; 1229f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_threshold = (int)(m_capacity * m_loadFactor); 1239f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_table = new HashEntry[m_capacity]; 1249f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1259f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson initExtendedTypes(); 1269f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1279f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1289f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1299f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 1309f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Initialize the vector of extended types with the 1319f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * basic DOM node types. 1329f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 1339f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson private void initExtendedTypes() 1349f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1359f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_extendedTypes = new ExtendedType[m_initialSize]; 1369f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson for (int i = 0; i < DTM.NTYPES; i++) { 1379f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_extendedTypes[i] = m_defaultExtendedTypes[i]; 1389f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_table[i] = new HashEntry(m_defaultExtendedTypes[i], i, i, null); 1399f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1409f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1419f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_nextType = DTM.NTYPES; 1429f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1439f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1449f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 1459f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Given an expanded name represented by namespace, local name and node type, 1469f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * return an ID. If the expanded-name does not exist in the internal tables, 1479f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * the entry will be created, and the ID will be returned. Any additional 1489f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * nodes that are created that have this expanded name will use this ID. 1499f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 1509f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param namespace The namespace 1519f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param localName The local name 1529f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param type The node type 1539f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 1549f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return the expanded-name id of the node. 1559f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 1569f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public int getExpandedTypeID(String namespace, String localName, int type) 1579f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1589f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return getExpandedTypeID(namespace, localName, type, false); 1599f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1609f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1619f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 1629f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Given an expanded name represented by namespace, local name and node type, 1639f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * return an ID. If the expanded-name does not exist in the internal tables, 1649f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * the entry will be created, and the ID will be returned. Any additional 1659f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * nodes that are created that have this expanded name will use this ID. 1669f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * <p> 1679f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * If searchOnly is true, we will return -1 if the name is not found in the 1689f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * table, otherwise the name is added to the table and the expanded name id 1699f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * of the new entry is returned. 1709f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 1719f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param namespace The namespace 1729f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param localName The local name 1739f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param type The node type 1749f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param searchOnly If it is true, we will only search for the expanded name. 1759f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * -1 is return is the name is not found. 1769f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 1779f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return the expanded-name id of the node. 1789f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 1799f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public int getExpandedTypeID(String namespace, String localName, int type, boolean searchOnly) 1809f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1819f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (null == namespace) 1829f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson namespace = ""; 1839f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (null == localName) 1849f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson localName = ""; 1859f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1869f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // Calculate the hash code 1879f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int hash = type + namespace.hashCode() + localName.hashCode(); 1889f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1899f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // Redefine the hashET object to represent the new expanded name. 1909f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson hashET.redefine(type, namespace, localName, hash); 1919f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1929f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // Calculate the index into the HashEntry table. 1939f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int index = hash % m_capacity; 1949f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (index < 0) 1959f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson index = -index; 1969f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1979f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // Look up the expanded name in the hash table. Return the id if 1989f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // the expanded name is already in the hash table. 1999f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson for (HashEntry e = m_table[index]; e != null; e = e.next) 2009f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2019f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (e.hash == hash && e.key.equals(hashET)) 2029f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return e.value; 2039f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2049f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2059f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (searchOnly) 2069f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2079f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return DTM.NULL; 2089f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2099f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2109f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // Expand the internal HashEntry array if necessary. 2119f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (m_nextType > m_threshold) { 2129f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson rehash(); 2139f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson index = hash % m_capacity; 2149f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (index < 0) 2159f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson index = -index; 2169f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2179f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2189f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // Create a new ExtendedType object 2199f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson ExtendedType newET = new ExtendedType(type, namespace, localName, hash); 2209f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2219f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // Expand the m_extendedTypes array if necessary. 2229f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (m_extendedTypes.length == m_nextType) { 2239f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson ExtendedType[] newArray = new ExtendedType[m_extendedTypes.length * 2]; 2249f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson System.arraycopy(m_extendedTypes, 0, newArray, 0, 2259f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_extendedTypes.length); 2269f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_extendedTypes = newArray; 2279f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2289f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2299f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_extendedTypes[m_nextType] = newET; 2309f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2319f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // Create a new hash entry for the new ExtendedType and put it into 2329f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // the table. 2339f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson HashEntry entry = new HashEntry(newET, m_nextType, hash, m_table[index]); 2349f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_table[index] = entry; 2359f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2369f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return m_nextType++; 2379f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2389f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2399f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 2409f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Increases the capacity of and internally reorganizes the hashtable, 2419f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * in order to accommodate and access its entries more efficiently. 2429f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * This method is called when the number of keys in the hashtable exceeds 2439f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * this hashtable's capacity and load factor. 2449f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 2459f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson private void rehash() 2469f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2479f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int oldCapacity = m_capacity; 2489f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson HashEntry[] oldTable = m_table; 2499f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2509f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int newCapacity = 2 * oldCapacity + 1; 2519f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_capacity = newCapacity; 2529f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_threshold = (int)(newCapacity * m_loadFactor); 2539f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2549f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_table = new HashEntry[newCapacity]; 2559f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson for (int i = oldCapacity-1; i >=0 ; i--) 2569f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2579f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson for (HashEntry old = oldTable[i]; old != null; ) 2589f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2599f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson HashEntry e = old; 2609f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson old = old.next; 2619f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2629f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int newIndex = e.hash % newCapacity; 2639f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (newIndex < 0) 2649f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson newIndex = -newIndex; 2659f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2669f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson e.next = m_table[newIndex]; 2679f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_table[newIndex] = e; 2689f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2699f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2709f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2719f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2729f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 2739f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Given a type, return an expanded name ID.Any additional nodes that are 2749f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * created that have this expanded name will use this ID. 2759f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 2769f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return the expanded-name id of the node. 2779f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 2789f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public int getExpandedTypeID(int type) 2799f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2809f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return type; 2819f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2829f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2839f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 2849f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Given an expanded-name ID, return the local name part. 2859f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 2869f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param ExpandedNameID an ID that represents an expanded-name. 2879f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return String Local name of this node, or null if the node has no name. 2889f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 2899f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public String getLocalName(int ExpandedNameID) 2909f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2919f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return m_extendedTypes[ExpandedNameID].getLocalName(); 2929f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2939f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2949f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 2959f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Given an expanded-name ID, return the local name ID. 2969f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 2979f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param ExpandedNameID an ID that represents an expanded-name. 2989f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return The id of this local name. 2999f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 3009f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public final int getLocalNameID(int ExpandedNameID) 3019f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 3029f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // ExtendedType etype = m_extendedTypes[ExpandedNameID]; 3039f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (m_extendedTypes[ExpandedNameID].getLocalName().equals("")) 3049f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return 0; 3059f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson else 3069f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return ExpandedNameID; 3079f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 3089f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3099f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3109f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 3119f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Given an expanded-name ID, return the namespace URI part. 3129f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 3139f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param ExpandedNameID an ID that represents an expanded-name. 3149f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return String URI value of this node's namespace, or null if no 3159f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * namespace was resolved. 3169f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 3179f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public String getNamespace(int ExpandedNameID) 3189f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 3199f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson String namespace = m_extendedTypes[ExpandedNameID].getNamespace(); 3209f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return (namespace.equals("") ? null : namespace); 3219f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 3229f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3239f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 3249f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Given an expanded-name ID, return the namespace URI ID. 3259f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 3269f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param ExpandedNameID an ID that represents an expanded-name. 3279f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return The id of this namespace. 3289f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 3299f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public final int getNamespaceID(int ExpandedNameID) 3309f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 3319f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson //ExtendedType etype = m_extendedTypes[ExpandedNameID]; 3329f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (m_extendedTypes[ExpandedNameID].getNamespace().equals("")) 3339f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return 0; 3349f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson else 3359f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return ExpandedNameID; 3369f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 3379f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3389f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 3399f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Given an expanded-name ID, return the local name ID. 3409f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 3419f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param ExpandedNameID an ID that represents an expanded-name. 3429f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return The id of this local name. 3439f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 3449f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public final short getType(int ExpandedNameID) 3459f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 3469f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson //ExtendedType etype = m_extendedTypes[ExpandedNameID]; 3479f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return (short)m_extendedTypes[ExpandedNameID].getNodeType(); 3489f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 3499f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3509f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 3519f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Return the size of the ExpandedNameTable 3529f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 3539f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return The size of the ExpandedNameTable 3549f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 3559f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public int getSize() 3569f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 3579f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return m_nextType; 3589f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 3599f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3609f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 3619f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Return the array of extended types 3629f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 3639f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return The array of extended types 3649f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 3659f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public ExtendedType[] getExtendedTypes() 3669f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 3679f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return m_extendedTypes; 3689f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 3699f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3709f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 3719f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Inner class which represents a hash table entry. 3729f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * The field next points to the next entry which is hashed into 3739f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * the same bucket in the case of "hash collision". 3749f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 3759f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson private static final class HashEntry 3769f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 3779f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson ExtendedType key; 3789f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int value; 3799f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int hash; 3809f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson HashEntry next; 3819f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3829f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson protected HashEntry(ExtendedType key, int value, int hash, HashEntry next) 3839f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 3849f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson this.key = key; 3859f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson this.value = value; 3869f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson this.hash = hash; 3879f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson this.next = next; 3889f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 3899f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 3909f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3919f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson} 392