• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * Licensed to the Apache Software Foundation (ASF) under one
3  * or more contributor license agreements. See the NOTICE file
4  * distributed with this work for additional information
5  * regarding copyright ownership. The ASF licenses this file
6  * to you under the Apache License, Version 2.0 (the  "License");
7  * you may not use this file except in compliance with the License.
8  * You may obtain a copy of the License at
9  *
10  *     http://www.apache.org/licenses/LICENSE-2.0
11  *
12  * Unless required by applicable law or agreed to in writing, software
13  * distributed under the License is distributed on an "AS IS" BASIS,
14  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15  * See the License for the specific language governing permissions and
16  * limitations under the License.
17  */
18 /*
19  * $Id: ExpandedNameTable.java 468653 2006-10-28 07:07:05Z minchau $
20  */
21 package org.apache.xml.dtm.ref;
22 
23 import org.apache.xml.dtm.DTM;
24 
25 /**
26  * This is a default implementation of a table that manages mappings from
27  * expanded names to expandedNameIDs.
28  *
29  * %OPT% The performance of the getExpandedTypeID() method is very important
30  * to DTM building. To get the best performance out of this class, we implement
31  * a simple hash algorithm directly into this class, instead of using the
32  * inefficient java.util.Hashtable. The code for the get and put operations
33  * are combined in getExpandedTypeID() method to share the same hash calculation
34  * code. We only need to implement the rehash() interface which is used to
35  * expand the hash table.
36  */
37 public class ExpandedNameTable
38 {
39 
40   /** Array of extended types for this document   */
41   private ExtendedType[] m_extendedTypes;
42 
43   /** The initial size of the m_extendedTypes array */
44   private static int m_initialSize = 128;
45 
46   /** Next available extended type   */
47   // %REVIEW% Since this is (should be) always equal
48   // to the length of m_extendedTypes, do we need this?
49   private int m_nextType;
50 
51   // These are all the types prerotated, for caller convenience.
52   public static final int ELEMENT = ((int)DTM.ELEMENT_NODE) ;
53   public static final int ATTRIBUTE = ((int)DTM.ATTRIBUTE_NODE) ;
54   public static final int TEXT = ((int)DTM.TEXT_NODE) ;
55   public static final int CDATA_SECTION = ((int)DTM.CDATA_SECTION_NODE) ;
56   public static final int ENTITY_REFERENCE = ((int)DTM.ENTITY_REFERENCE_NODE) ;
57   public static final int ENTITY = ((int)DTM.ENTITY_NODE) ;
58   public static final int PROCESSING_INSTRUCTION = ((int)DTM.PROCESSING_INSTRUCTION_NODE) ;
59   public static final int COMMENT = ((int)DTM.COMMENT_NODE) ;
60   public static final int DOCUMENT = ((int)DTM.DOCUMENT_NODE) ;
61   public static final int DOCUMENT_TYPE = ((int)DTM.DOCUMENT_TYPE_NODE) ;
62   public static final int DOCUMENT_FRAGMENT =((int)DTM.DOCUMENT_FRAGMENT_NODE) ;
63   public static final int NOTATION = ((int)DTM.NOTATION_NODE) ;
64   public static final int NAMESPACE = ((int)DTM.NAMESPACE_NODE) ;
65 
66   /** Workspace for lookup. NOT THREAD SAFE!
67    * */
68   ExtendedType hashET = new ExtendedType(-1, "", "");
69 
70   /** The array to store the default extended types. */
71   private static ExtendedType[] m_defaultExtendedTypes;
72 
73   /**
74    * The default load factor of the Hashtable.
75    * This is used to calcualte the threshold.
76    */
77   private static float m_loadFactor = 0.75f;
78 
79   /**
80    * The initial capacity of the hash table. Use a bigger number
81    * to avoid the cost of expanding the table.
82    */
83   private static int m_initialCapacity = 203;
84 
85   /**
86    * The capacity of the hash table, i.e. the size of the
87    * internal HashEntry array.
88    */
89   private int m_capacity;
90 
91   /**
92    * The threshold of the hash table, which is equal to capacity * loadFactor.
93    * If the number of entries in the hash table is bigger than the threshold,
94    * the hash table needs to be expanded.
95    */
96   private int m_threshold;
97 
98   /**
99    * 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    */
ExpandedNameTable()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    */
initExtendedTypes()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    */
getExpandedTypeID(String namespace, String localName, int type)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    */
getExpandedTypeID(String namespace, String localName, int type, boolean searchOnly)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    */
rehash()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    */
getExpandedTypeID(int type)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    */
getLocalName(int ExpandedNameID)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    */
getLocalNameID(int ExpandedNameID)300   public final int getLocalNameID(int ExpandedNameID)
301   {
302     // ExtendedType etype = m_extendedTypes[ExpandedNameID];
303     if (m_extendedTypes[ExpandedNameID].getLocalName().equals(""))
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    */
getNamespace(int ExpandedNameID)317   public String getNamespace(int ExpandedNameID)
318   {
319     String namespace = m_extendedTypes[ExpandedNameID].getNamespace();
320     return (namespace.equals("") ? 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    */
getNamespaceID(int ExpandedNameID)329   public final int getNamespaceID(int ExpandedNameID)
330   {
331     //ExtendedType etype = m_extendedTypes[ExpandedNameID];
332     if (m_extendedTypes[ExpandedNameID].getNamespace().equals(""))
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    */
getType(int ExpandedNameID)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    */
getSize()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    */
getExtendedTypes()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 
HashEntry(ExtendedType key, int value, int hash, HashEntry next)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 }
392