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