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