ExpandedNameTable


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