Package com.ctc.wstx.util

Class ElementIdMap

java.lang.Object
com.ctc.wstx.util.ElementIdMap
public final class ElementIdMap extends Object
This class is a specialized type-safe linked hash map used for storing ElementId instances. ElementId instances represent both id definitions (values of element attributes that have type ID in DTD), and references (values of element attributes of type IDREF and IDREFS). These definitions and references are stored for the purpose of verifying that all referenced id values are defined, and that none are defined more than once.

Note: there are 2 somewhat distinct usage modes, by DTDValidator and by MSV-based validators. DTDs pass raw character arrays, whereas MSV-based validators operate on Strings. This is the main reason for 2 distinct sets of methods.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    protected static final int
    DEFAULT_SIZE
    Default initial table size; set so that usually it need not be expanded.
    protected static final int
    FILL_PCT
    Let's use 80% fill factor...
    protected final int
    mHashSeed
    Seed mixed into the per-character hash, to defend against collision attacks crafted from attribute values.
    protected ElementId
    mHead
     
    protected static final int
    MIN_SIZE
     
    protected int
    mIndexMask
    Mask used to get index from hash values; equal to mBuckets.length - 1, when mBuckets.length is a power of two.
    protected int
    mSize
    Current size (number of entries); needed to know if and when rehash.
    protected int
    mSizeThreshold
    Limit that indicates maximum size this instance can hold before it needs to be expanded and rehashed.
    protected ElementId[]
    mTable
    Actual hash table area
    protected ElementId
    mTail
     

  • Constructor Summary

    Constructors
    Constructor
    Description
    ElementIdMap()
     
    ElementIdMap(int initialSize)
    This constructor is mainly used for testing, as it can be sized appropriately to test rehashing etc.

  • Method Summary

    Modifier and Type
    Method
    Description
    ElementId
    addDefined(char[] buffer, int start, int len, int hash, Location loc, PrefixedName elemName, PrefixedName attrName)
    Method called when an id definition is encountered.
    ElementId
    addDefined(String idStr, Location loc, PrefixedName elemName, PrefixedName attrName)
     
    ElementId
    addReferenced(char[] buffer, int start, int len, int hash, Location loc, PrefixedName elemName, PrefixedName attrName)
    Method called when a reference to id is encountered.
    ElementId
    addReferenced(String idStr, Location loc, PrefixedName elemName, PrefixedName attrName)
     
    static int
    calcHash(char[] buffer, int start, int len)
    Deprecated.
    since 7.2; retained for binary compatibility.
    static int
    calcHash(char[] buffer, int start, int len, int seed)
    Implementation of a hashing method for variable length Strings.
    static int
    calcHash(String key)
    Deprecated.
    since 7.2; retained for binary compatibility.
    static int
    calcHash(String key, int seed)
     
    ElementId
    getFirstUndefined()
     
    int
    getHashSeed()
    Returns the random seed that callers must fold into per-character hash computation for keys looked up in this table.
    private void
    rehash()
    Method called when size (number of entries) of symbol table grows so big that load factor is exceeded.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Field Details

    • DEFAULT_SIZE

      protected static final int DEFAULT_SIZE
      Default initial table size; set so that usually it need not be expanded.
      See Also:

    • MIN_SIZE

      protected static final int MIN_SIZE
      See Also:

    • FILL_PCT

      protected static final int FILL_PCT
      Let's use 80% fill factor...
      See Also:

    • mTable

      protected ElementId[] mTable
      Actual hash table area

    • mSize

      protected int mSize
      Current size (number of entries); needed to know if and when rehash.

    • mSizeThreshold

      protected int mSizeThreshold
      Limit that indicates maximum size this instance can hold before it needs to be expanded and rehashed. Calculated using fill factor passed in to constructor.

    • mIndexMask

      protected int mIndexMask
      Mask used to get index from hash values; equal to mBuckets.length - 1, when mBuckets.length is a power of two.

    • mHead

      protected ElementId mHead

    • mTail

      protected ElementId mTail

    • mHashSeed

      protected final int mHashSeed
      Seed mixed into the per-character hash, to defend against collision attacks crafted from attribute values. See issue #12.

  • Constructor Details

    • ElementIdMap

      public ElementIdMap()

    • ElementIdMap

      public ElementIdMap(int initialSize)
      This constructor is mainly used for testing, as it can be sized appropriately to test rehashing etc.

  • Method Details

    • getHashSeed

      public int getHashSeed()
      Returns the random seed that callers must fold into per-character hash computation for keys looked up in this table.

    • getFirstUndefined

      public ElementId getFirstUndefined()

    • addReferenced

      public ElementId addReferenced(char[] buffer, int start, int len, int hash, Location loc, PrefixedName elemName, PrefixedName attrName)
      Method called when a reference to id is encountered. If so, need to check if specified id entry (ref or definiton) exists; and if not, to add a reference marker.

    • addReferenced

      public ElementId addReferenced(String idStr, Location loc, PrefixedName elemName, PrefixedName attrName)

    • addDefined

      public ElementId addDefined(char[] buffer, int start, int len, int hash, Location loc, PrefixedName elemName, PrefixedName attrName)
      Method called when an id definition is encountered. If so, need to check if specified id entry (ref or definiton) exists. If not, need to add the definition marker. If it does exist, need to 'upgrade it', if it was a reference marker; otherwise need to just return the old entry, and expect caller to check for dups and report the error.

    • addDefined

      public ElementId addDefined(String idStr, Location loc, PrefixedName elemName, PrefixedName attrName)

    • calcHash

      public static int calcHash(char[] buffer, int start, int len, int seed)
      Implementation of a hashing method for variable length Strings. Most of the time intention is that this calculation is done by caller during parsing, not here; however, sometimes it needs to be done for parsed "String" too.

      Seed and finalizer match SymbolTable.calcHash(char[], int, int, int), so attacker- chosen names cannot land in the same bucket without knowing the table's per-instance seed.

      Parameters:
      len - Length of String; has to be at least 1 (caller guarantees this pre-condition)
      seed - Per-table seed obtained from getHashSeed()

    • calcHash

      public static int calcHash(String key, int seed)

    • calcHash

      @Deprecated public static int calcHash(char[] buffer, int start, int len)
      Deprecated.
      since 7.2; retained for binary compatibility. Use calcHash(char[], int, int, int) with getHashSeed().

    • calcHash

      @Deprecated public static int calcHash(String key)
      Deprecated.
      since 7.2; retained for binary compatibility. Use calcHash(String, int) with getHashSeed().

    • rehash

      private void rehash()
      Method called when size (number of entries) of symbol table grows so big that load factor is exceeded. Since size has to remain power of two, arrays will then always be doubled. Main work is really redistributing old entries into new String/Bucket entries.