001: /*
002: * Copyright 1999-2004 The Apache Software Foundation.
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License");
005: * you may not use this file except in compliance with the License.
006: * You may obtain a copy of the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS,
012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013: * See the License for the specific language governing permissions and
014: * limitations under the License.
015: */
016: /*
017: * $Id: ExpandedNameTable.java,v 1.14 2005/01/24 00:34:35 mcnamara Exp $
018: */
019: package org.apache.xml.dtm.ref;
020:
021: import org.apache.xml.dtm.DTM;
022:
023: /**
024: * This is a default implementation of a table that manages mappings from
025: * expanded names to expandedNameIDs.
026: *
027: * %OPT% The performance of the getExpandedTypeID() method is very important
028: * to DTM building. To get the best performance out of this class, we implement
029: * a simple hash algorithm directly into this class, instead of using the
030: * inefficient java.util.Hashtable. The code for the get and put operations
031: * are combined in getExpandedTypeID() method to share the same hash calculation
032: * code. We only need to implement the rehash() interface which is used to
033: * expand the hash table.
034: */
035: public class ExpandedNameTable {
036:
037: /** Array of extended types for this document */
038: private ExtendedType[] m_extendedTypes;
039:
040: /** The initial size of the m_extendedTypes array */
041: private static int m_initialSize = 128;
042:
043: /** Next available extended type */
044: // %REVIEW% Since this is (should be) always equal
045: // to the length of m_extendedTypes, do we need this?
046: private int m_nextType;
047:
048: // These are all the types prerotated, for caller convenience.
049: public static final int ELEMENT = ((int) DTM.ELEMENT_NODE);
050: public static final int ATTRIBUTE = ((int) DTM.ATTRIBUTE_NODE);
051: public static final int TEXT = ((int) DTM.TEXT_NODE);
052: public static final int CDATA_SECTION = ((int) DTM.CDATA_SECTION_NODE);
053: public static final int ENTITY_REFERENCE = ((int) DTM.ENTITY_REFERENCE_NODE);
054: public static final int ENTITY = ((int) DTM.ENTITY_NODE);
055: public static final int PROCESSING_INSTRUCTION = ((int) DTM.PROCESSING_INSTRUCTION_NODE);
056: public static final int COMMENT = ((int) DTM.COMMENT_NODE);
057: public static final int DOCUMENT = ((int) DTM.DOCUMENT_NODE);
058: public static final int DOCUMENT_TYPE = ((int) DTM.DOCUMENT_TYPE_NODE);
059: public static final int DOCUMENT_FRAGMENT = ((int) DTM.DOCUMENT_FRAGMENT_NODE);
060: public static final int NOTATION = ((int) DTM.NOTATION_NODE);
061: public static final int NAMESPACE = ((int) DTM.NAMESPACE_NODE);
062:
063: /** Workspace for lookup. NOT THREAD SAFE!
064: * */
065: ExtendedType hashET = new ExtendedType(-1, "", "");
066:
067: /** The array to store the default extended types. */
068: private static ExtendedType[] m_defaultExtendedTypes;
069:
070: /**
071: * The default load factor of the Hashtable.
072: * This is used to calcualte the threshold.
073: */
074: private static float m_loadFactor = 0.75f;
075:
076: /**
077: * The initial capacity of the hash table. Use a bigger number
078: * to avoid the cost of expanding the table.
079: */
080: private static int m_initialCapacity = 203;
081:
082: /**
083: * The capacity of the hash table, i.e. the size of the
084: * internal HashEntry array.
085: */
086: private int m_capacity;
087:
088: /**
089: * The threshold of the hash table, which is equal to capacity * loadFactor.
090: * If the number of entries in the hash table is bigger than the threshold,
091: * the hash table needs to be expanded.
092: */
093: private int m_threshold;
094:
095: /**
096: * The internal array to store the hash entries.
097: * Each array member is a slot for a hash bucket.
098: */
099: private HashEntry[] m_table;
100:
101: /**
102: * Init default values
103: */
104: static {
105: m_defaultExtendedTypes = new ExtendedType[DTM.NTYPES];
106:
107: for (int i = 0; i < DTM.NTYPES; i++) {
108: m_defaultExtendedTypes[i] = new ExtendedType(i, "", "");
109: }
110: }
111:
112: /**
113: * Create an expanded name table.
114: */
115: public ExpandedNameTable() {
116: m_capacity = m_initialCapacity;
117: m_threshold = (int) (m_capacity * m_loadFactor);
118: m_table = new HashEntry[m_capacity];
119:
120: initExtendedTypes();
121: }
122:
123: /**
124: * Initialize the vector of extended types with the
125: * basic DOM node types.
126: */
127: private void initExtendedTypes() {
128: m_extendedTypes = new ExtendedType[m_initialSize];
129: for (int i = 0; i < DTM.NTYPES; i++) {
130: m_extendedTypes[i] = m_defaultExtendedTypes[i];
131: m_table[i] = new HashEntry(m_defaultExtendedTypes[i], i, i,
132: null);
133: }
134:
135: m_nextType = DTM.NTYPES;
136: }
137:
138: /**
139: * Given an expanded name represented by namespace, local name and node type,
140: * return an ID. If the expanded-name does not exist in the internal tables,
141: * the entry will be created, and the ID will be returned. Any additional
142: * nodes that are created that have this expanded name will use this ID.
143: *
144: * @param namespace The namespace
145: * @param localName The local name
146: * @param type The node type
147: *
148: * @return the expanded-name id of the node.
149: */
150: public int getExpandedTypeID(String namespace, String localName,
151: int type) {
152: return getExpandedTypeID(namespace, localName, type, false);
153: }
154:
155: /**
156: * Given an expanded name represented by namespace, local name and node type,
157: * return an ID. If the expanded-name does not exist in the internal tables,
158: * the entry will be created, and the ID will be returned. Any additional
159: * nodes that are created that have this expanded name will use this ID.
160: * <p>
161: * If searchOnly is true, we will return -1 if the name is not found in the
162: * table, otherwise the name is added to the table and the expanded name id
163: * of the new entry is returned.
164: *
165: * @param namespace The namespace
166: * @param localName The local name
167: * @param type The node type
168: * @param searchOnly If it is true, we will only search for the expanded name.
169: * -1 is return is the name is not found.
170: *
171: * @return the expanded-name id of the node.
172: */
173: public int getExpandedTypeID(String namespace, String localName,
174: int type, boolean searchOnly) {
175: if (null == namespace)
176: namespace = "";
177: if (null == localName)
178: localName = "";
179:
180: // Calculate the hash code
181: int hash = type + namespace.hashCode() + localName.hashCode();
182:
183: // Redefine the hashET object to represent the new expanded name.
184: hashET.redefine(type, namespace, localName, hash);
185:
186: // Calculate the index into the HashEntry table.
187: int index = hash % m_capacity;
188: if (index < 0)
189: index = -index;
190:
191: // Look up the expanded name in the hash table. Return the id if
192: // the expanded name is already in the hash table.
193: for (HashEntry e = m_table[index]; e != null; e = e.next) {
194: if (e.hash == hash && e.key.equals(hashET))
195: return e.value;
196: }
197:
198: if (searchOnly) {
199: return DTM.NULL;
200: }
201:
202: // Expand the internal HashEntry array if necessary.
203: if (m_nextType > m_threshold) {
204: rehash();
205: index = hash % m_capacity;
206: if (index < 0)
207: index = -index;
208: }
209:
210: // Create a new ExtendedType object
211: ExtendedType newET = new ExtendedType(type, namespace,
212: localName, hash);
213:
214: // Expand the m_extendedTypes array if necessary.
215: if (m_extendedTypes.length == m_nextType) {
216: ExtendedType[] newArray = new ExtendedType[m_extendedTypes.length * 2];
217: System.arraycopy(m_extendedTypes, 0, newArray, 0,
218: m_extendedTypes.length);
219: m_extendedTypes = newArray;
220: }
221:
222: m_extendedTypes[m_nextType] = newET;
223:
224: // Create a new hash entry for the new ExtendedType and put it into
225: // the table.
226: HashEntry entry = new HashEntry(newET, m_nextType, hash,
227: m_table[index]);
228: m_table[index] = entry;
229:
230: return m_nextType++;
231: }
232:
233: /**
234: * Increases the capacity of and internally reorganizes the hashtable,
235: * in order to accommodate and access its entries more efficiently.
236: * This method is called when the number of keys in the hashtable exceeds
237: * this hashtable's capacity and load factor.
238: */
239: private void rehash() {
240: int oldCapacity = m_capacity;
241: HashEntry[] oldTable = m_table;
242:
243: int newCapacity = 2 * oldCapacity + 1;
244: m_capacity = newCapacity;
245: m_threshold = (int) (newCapacity * m_loadFactor);
246:
247: m_table = new HashEntry[newCapacity];
248: for (int i = oldCapacity - 1; i >= 0; i--) {
249: for (HashEntry old = oldTable[i]; old != null;) {
250: HashEntry e = old;
251: old = old.next;
252:
253: int newIndex = e.hash % newCapacity;
254: if (newIndex < 0)
255: newIndex = -newIndex;
256:
257: e.next = m_table[newIndex];
258: m_table[newIndex] = e;
259: }
260: }
261: }
262:
263: /**
264: * Given a type, return an expanded name ID.Any additional nodes that are
265: * created that have this expanded name will use this ID.
266: *
267: * @return the expanded-name id of the node.
268: */
269: public int getExpandedTypeID(int type) {
270: return type;
271: }
272:
273: /**
274: * Given an expanded-name ID, return the local name part.
275: *
276: * @param ExpandedNameID an ID that represents an expanded-name.
277: * @return String Local name of this node, or null if the node has no name.
278: */
279: public String getLocalName(int ExpandedNameID) {
280: return m_extendedTypes[ExpandedNameID].getLocalName();
281: }
282:
283: /**
284: * Given an expanded-name ID, return the local name ID.
285: *
286: * @param ExpandedNameID an ID that represents an expanded-name.
287: * @return The id of this local name.
288: */
289: public final int getLocalNameID(int ExpandedNameID) {
290: // ExtendedType etype = m_extendedTypes[ExpandedNameID];
291: if (m_extendedTypes[ExpandedNameID].getLocalName().equals(""))
292: return 0;
293: else
294: return ExpandedNameID;
295: }
296:
297: /**
298: * Given an expanded-name ID, return the namespace URI part.
299: *
300: * @param ExpandedNameID an ID that represents an expanded-name.
301: * @return String URI value of this node's namespace, or null if no
302: * namespace was resolved.
303: */
304: public String getNamespace(int ExpandedNameID) {
305: String namespace = m_extendedTypes[ExpandedNameID]
306: .getNamespace();
307: return (namespace.equals("") ? null : namespace);
308: }
309:
310: /**
311: * Given an expanded-name ID, return the namespace URI ID.
312: *
313: * @param ExpandedNameID an ID that represents an expanded-name.
314: * @return The id of this namespace.
315: */
316: public final int getNamespaceID(int ExpandedNameID) {
317: //ExtendedType etype = m_extendedTypes[ExpandedNameID];
318: if (m_extendedTypes[ExpandedNameID].getNamespace().equals(""))
319: return 0;
320: else
321: return ExpandedNameID;
322: }
323:
324: /**
325: * Given an expanded-name ID, return the local name ID.
326: *
327: * @param ExpandedNameID an ID that represents an expanded-name.
328: * @return The id of this local name.
329: */
330: public final short getType(int ExpandedNameID) {
331: //ExtendedType etype = m_extendedTypes[ExpandedNameID];
332: return (short) m_extendedTypes[ExpandedNameID].getNodeType();
333: }
334:
335: /**
336: * Return the size of the ExpandedNameTable
337: *
338: * @return The size of the ExpandedNameTable
339: */
340: public int getSize() {
341: return m_nextType;
342: }
343:
344: /**
345: * Return the array of extended types
346: *
347: * @return The array of extended types
348: */
349: public ExtendedType[] getExtendedTypes() {
350: return m_extendedTypes;
351: }
352:
353: /**
354: * Inner class which represents a hash table entry.
355: * The field next points to the next entry which is hashed into
356: * the same bucket in the case of "hash collision".
357: */
358: private static final class HashEntry {
359: ExtendedType key;
360: int value;
361: int hash;
362: HashEntry next;
363:
364: protected HashEntry(ExtendedType key, int value, int hash,
365: HashEntry next) {
366: this.key = key;
367: this.value = value;
368: this.hash = hash;
369: this.next = next;
370: }
371: }
372:
373: }
|