libcore/luni/src/main/java/org/apache/xml/dtm/ref/ExpandedNameTable.java

   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    */
 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().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    */
 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    */
 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    */
 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 }