Class WNameTable


  • public final class WNameTable
    extends NameTable
    This is a symbol table implementation used for storing byte-based WNames.
    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      (package private) static class  WNameTable.Bucket  
    • Field Summary

      Fields 
      Modifier and Type Field Description
      (package private) static int INITIAL_COLLISION_LEN  
      (package private) static int LAST_VALID_BUCKET
      Bucket index is 8 bits, and value 0 is reserved to represent 'empty' status.
      private int mCollCount
      Total number of WNames in collision buckets (included in mCount along with primary entries)
      private int mCollEnd
      Index of the first unused collision bucket entry (== size of the used portion of collision list): less than or equal to 0xFF (255), since max number of entries is 255 (8-bit, minus 0 used as 'empty' marker)
      private WNameTable.Bucket[] mCollList
      Array of heads of collision bucket chains; size dynamically
      private boolean mCollListShared
      Flag that indicates whether underlying data structures for the collision list are shared or not.
      private int mCount
      Total number of WNames in the symbol table
      (package private) static int MIN_HASH_SIZE  
      private int[] mMainHash
      Array of 2^N size, which contains combination of 24-bits of hash (0 to indicate 'empty' slot), and 8-bit collision bucket index (0 to indicate empty collision bucket chain; otherwise subtract one from index)
      private int mMainHashMask
      Mask used to truncate 32-bit hash value to current hash array size; essentially, hash array size - 1 (since hash array sizes are 2^N).
      private boolean mMainHashShared
      Flag that indicates whether underlying data structures for the main hash area are shared or not.
      private WName[] mMainNames
      Array that contains WName instances matching entries in mMainHash.
      private boolean mMainNamesShared  
      (package private) WNameFactory mNameFactory  
      private boolean mNeedRehash
      This flag is set if, after adding a new entry, it is deemed that a rehash is warranted if any more entries are to be added.
      (package private) WNameTable mParent
      Parent reference is needed to be able to merge new symbols if and as necessary
    • Constructor Summary

      Constructors 
      Modifier Constructor Description
      protected WNameTable​(int hashSize)  
      private WNameTable​(WNameTable parent, WNameFactory f)
      Constructor used when creating a child instance
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      private void addSymbol​(WName symbol)  
      protected WNameTable createChild​(WNameFactory f)  
      private void expandCollision()  
      private int findBestBucket()
      Method called to find the best bucket to spill a WName over to: usually the first bucket that has only one entry, but in general first one of the buckets with least number of entries
      WName findSymbol​(java.lang.String localName)  
      WName findSymbol​(java.lang.String prefix, java.lang.String localName)
      Finds and returns name matching the specified symbol, if such name already exists in the table; or if not, creates name object, adds to the table, and returns it.
      void markAsShared()  
      boolean maybeDirty()
      Method called to check to quickly see if a child symbol table may have gotten additional entries.
      private boolean mergeFromChild​(WNameTable child)  
      boolean mergeToParent()  
      void nuke()
      Method used by test code, to reset state of the name table.
      private void rehash()  
      int size()  
      java.lang.String toDebugString()  
      java.lang.String toString()  
      private void unshareCollision()  
      private void unshareMain()
      Method that needs to be called, if the main hash structure is (may be) shared.
      private void unshareNames()  
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
    • Field Detail

      • LAST_VALID_BUCKET

        static final int LAST_VALID_BUCKET
        Bucket index is 8 bits, and value 0 is reserved to represent 'empty' status.
        See Also:
        Constant Field Values
      • mParent

        final WNameTable mParent
        Parent reference is needed to be able to merge new symbols if and as necessary
      • mCount

        private int mCount
        Total number of WNames in the symbol table
      • mMainHashMask

        private int mMainHashMask
        Mask used to truncate 32-bit hash value to current hash array size; essentially, hash array size - 1 (since hash array sizes are 2^N).
      • mMainHash

        private int[] mMainHash
        Array of 2^N size, which contains combination of 24-bits of hash (0 to indicate 'empty' slot), and 8-bit collision bucket index (0 to indicate empty collision bucket chain; otherwise subtract one from index)
      • mMainNames

        private WName[] mMainNames
        Array that contains WName instances matching entries in mMainHash. Contains nulls for unused entries.
      • mCollList

        private WNameTable.Bucket[] mCollList
        Array of heads of collision bucket chains; size dynamically
      • mCollCount

        private int mCollCount
        Total number of WNames in collision buckets (included in mCount along with primary entries)
      • mCollEnd

        private int mCollEnd
        Index of the first unused collision bucket entry (== size of the used portion of collision list): less than or equal to 0xFF (255), since max number of entries is 255 (8-bit, minus 0 used as 'empty' marker)
      • mNeedRehash

        private transient boolean mNeedRehash
        This flag is set if, after adding a new entry, it is deemed that a rehash is warranted if any more entries are to be added.
      • mMainHashShared

        private boolean mMainHashShared
        Flag that indicates whether underlying data structures for the main hash area are shared or not. If they are, then they need to be handled in copy-on-write way, i.e. if they need to be modified, a copy needs to be made first; at this point it will not be shared any more, and can be modified.

        This flag needs to be checked both when adding new main entries, and when adding new collision list queues (i.e. creating a new collision list head entry)

      • mMainNamesShared

        private boolean mMainNamesShared
      • mCollListShared

        private boolean mCollListShared
        Flag that indicates whether underlying data structures for the collision list are shared or not. If they are, then they need to be handled in copy-on-write way, i.e. if they need to be modified, a copy needs to be made first; at this point it will not be shared any more, and can be modified.

        This flag needs to be checked when adding new collision entries.

    • Constructor Detail

      • WNameTable

        protected WNameTable​(int hashSize)
      • WNameTable

        private WNameTable​(WNameTable parent,
                           WNameFactory f)
        Constructor used when creating a child instance
    • Method Detail

      • mergeToParent

        public boolean mergeToParent()
      • mergeFromChild

        private boolean mergeFromChild​(WNameTable child)
      • markAsShared

        public void markAsShared()
      • nuke

        public void nuke()
        Method used by test code, to reset state of the name table.
      • size

        public int size()
        Specified by:
        size in class NameTable
      • maybeDirty

        public boolean maybeDirty()
        Method called to check to quickly see if a child symbol table may have gotten additional entries. Used for checking to see if a child table should be merged into shared table.
        Specified by:
        maybeDirty in class NameTable
      • findSymbol

        public WName findSymbol​(java.lang.String localName)
                         throws javax.xml.stream.XMLStreamException
        Throws:
        javax.xml.stream.XMLStreamException
      • findSymbol

        public WName findSymbol​(java.lang.String prefix,
                                java.lang.String localName)
                         throws javax.xml.stream.XMLStreamException
        Finds and returns name matching the specified symbol, if such name already exists in the table; or if not, creates name object, adds to the table, and returns it.
        Throws:
        javax.xml.stream.XMLStreamException
      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object
      • toDebugString

        public java.lang.String toDebugString()
      • addSymbol

        private void addSymbol​(WName symbol)
      • rehash

        private void rehash()
      • findBestBucket

        private int findBestBucket()
        Method called to find the best bucket to spill a WName over to: usually the first bucket that has only one entry, but in general first one of the buckets with least number of entries
      • unshareMain

        private void unshareMain()
        Method that needs to be called, if the main hash structure is (may be) shared. This happens every time something is added, even if addition is to the collision list (since collision list index comes from lowest 8 bits of the primary hash entry)
      • unshareCollision

        private void unshareCollision()
      • unshareNames

        private void unshareNames()
      • expandCollision

        private void expandCollision()