package com.fasterxml.jackson.core.sym;

import java.util.Arrays;
import java.util.BitSet;
import java.util.concurrent.atomic.AtomicReference;

import com.fasterxml.jackson.core.JsonFactory;
import com.fasterxml.jackson.core.util.InternCache;

This class is a kind of specialized type-safe Map, from char array to
String value. Specialization means that in addition to type-safety
and specific access patterns (key char array, Value optionally interned
String; values added on access if necessary), and that instances are
meant to be used concurrently, but by using well-defined mechanisms
to obtain such concurrently usable instances. Main use for the class
is to store symbol table information for things like compilers and
parsers; especially when number of symbols (keywords) is limited.

For optimal performance, usage pattern should be one where matches
should be very common (especially after "warm-up"), and as with most hash-based
maps/sets, that hash codes are uniformly distributed. Also, collisions
are slightly more expensive than with HashMap or HashSet, since hash codes
are not used in resolving collisions; that is, equals() comparison is
done with all symbols in same bucket index.

Finally, rehashing is also more expensive, as hash codes are not
stored; rehashing requires all entries' hash codes to be recalculated.
Reason for not storing hash codes is reduced memory usage, hoping
for better memory locality.

Usual usage pattern is to create a single "master" instance, and either
use that instance in sequential fashion, or to create derived "child"
instances, which after use, are asked to return possible symbol additions
to master instance. In either case benefit is that symbol table gets
initialized so that further uses are more efficient, as eventually all
symbols needed will already be in symbol table. At that point no more
Symbol String allocations are needed, nor changes to symbol table itself.

Note that while individual SymbolTable instances are NOT thread-safe
(much like generic collection classes), concurrently used "child"
instances can be freely used without synchronization. However, using
master table concurrently with child instances can only be done if
access to master instance is read-only (i.e. no modifications done).
/**
 * This class is a kind of specialized type-safe Map, from char array to
 * String value. Specialization means that in addition to type-safety
 * and specific access patterns (key char array, Value optionally interned
 * String; values added on access if necessary), and that instances are
 * meant to be used concurrently, but by using well-defined mechanisms
 * to obtain such concurrently usable instances. Main use for the class
 * is to store symbol table information for things like compilers and
 * parsers; especially when number of symbols (keywords) is limited.
 *<p>
 * For optimal performance, usage pattern should be one where matches
 * should be very common (especially after "warm-up"), and as with most hash-based
 * maps/sets, that hash codes are uniformly distributed. Also, collisions
 * are slightly more expensive than with HashMap or HashSet, since hash codes
 * are not used in resolving collisions; that is, equals() comparison is
 * done with all symbols in same bucket index.<br>
 * Finally, rehashing is also more expensive, as hash codes are not
 * stored; rehashing requires all entries' hash codes to be recalculated.
 * Reason for not storing hash codes is reduced memory usage, hoping
 * for better memory locality.
 *<p>
 * Usual usage pattern is to create a single "master" instance, and either
 * use that instance in sequential fashion, or to create derived "child"
 * instances, which after use, are asked to return possible symbol additions
 * to master instance. In either case benefit is that symbol table gets
 * initialized so that further uses are more efficient, as eventually all
 * symbols needed will already be in symbol table. At that point no more
 * Symbol String allocations are needed, nor changes to symbol table itself.
 *<p>
 * Note that while individual SymbolTable instances are NOT thread-safe
 * (much like generic collection classes), concurrently used "child"
 * instances can be freely used without synchronization. However, using
 * master table concurrently with child instances can only be done if
 * access to master instance is read-only (i.e. no modifications done).
 */
public final class CharsToNameCanonicalizer
{
    /* If we use "multiply-add" based hash algorithm, this is the multiplier
     * we use.
     *<p>
     * Note that JDK uses 31; but it seems that 33 produces fewer collisions,
     * at least with tests we have.
     */
    public final static int HASH_MULT = 33;

    
Default initial table size. Shouldn't be miniscule (as there's
cost to both array realloc and rehashing), but let's keep
it reasonably small. For systems that properly 
reuse factories it doesn't matter either way; but when
recreating factories often, initial overhead may dominate.
/**
     * Default initial table size. Shouldn't be miniscule (as there's
     * cost to both array realloc and rehashing), but let's keep
     * it reasonably small. For systems that properly 
     * reuse factories it doesn't matter either way; but when
     * recreating factories often, initial overhead may dominate.
     */
    private static final int DEFAULT_T_SIZE = 64;

    
Let's not expand symbol tables past some maximum size;
this should protected against OOMEs caused by large documents
with unique (~= random) names.
/**
     * Let's not expand symbol tables past some maximum size;
     * this should protected against OOMEs caused by large documents
     * with unique (~= random) names.
     */
    private static final int MAX_T_SIZE = 0x10000; // 64k entries == 256k mem

    
Let's only share reasonably sized symbol tables. Max size set to 3/4 of 16k;
this corresponds to 64k main hash index. This should allow for enough distinct
names for almost any case.
/**
     * Let's only share reasonably sized symbol tables. Max size set to 3/4 of 16k;
     * this corresponds to 64k main hash index. This should allow for enough distinct
     * names for almost any case.
     */
    static final int MAX_ENTRIES_FOR_REUSE = 12000;

    
Also: to thwart attacks based on hash collisions (which may or may not
be cheap to calculate), we will need to detect "too long"
collision chains. Let's start with static value of 100 entries
for the longest legal chain.

Note: longest chain we have been able to produce without malicious
intent has been 38 (with "com.fasterxml.jackson.core.main.TestWithTonsaSymbols");
our setting should be reasonable here.
Since:
2.1/**
     * Also: to thwart attacks based on hash collisions (which may or may not
     * be cheap to calculate), we will need to detect "too long"
     * collision chains. Let's start with static value of 100 entries
     * for the longest legal chain.
     *<p>
     * Note: longest chain we have been able to produce without malicious
     * intent has been 38 (with "com.fasterxml.jackson.core.main.TestWithTonsaSymbols");
     * our setting should be reasonable here.
     * 
     * @since 2.1
     */
    static final int MAX_COLL_CHAIN_LENGTH = 100;

    /*
    /**********************************************************
    /* Configuration
    /**********************************************************
     */

    
Sharing of learnt symbols is done by optional linking of symbol
table instances with their parents. When parent linkage is
defined, and child instance is released (call to release),
parent's shared tables may be updated from the child instance.
/**
     * Sharing of learnt symbols is done by optional linking of symbol
     * table instances with their parents. When parent linkage is
     * defined, and child instance is released (call to <code>release</code>),
     * parent's shared tables may be updated from the child instance.
     */
    final private CharsToNameCanonicalizer _parent;

    
Member that is only used by the root table instance: root
passes immutable state info child instances, and children
may return new state if they add entries to the table.
Child tables do NOT use the reference.
/**
     * Member that is only used by the root table instance: root
     * passes immutable state info child instances, and children
     * may return new state if they add entries to the table.
     * Child tables do NOT use the reference.
     */
    final private AtomicReference<TableInfo> _tableInfo;

    
Seed value we use as the base to make hash codes non-static between
different runs, but still stable for lifetime of a single symbol table
instance.
This is done for security reasons, to avoid potential DoS attack via
hash collisions.
Since:
2.1/**
     * Seed value we use as the base to make hash codes non-static between
     * different runs, but still stable for lifetime of a single symbol table
     * instance.
     * This is done for security reasons, to avoid potential DoS attack via
     * hash collisions.
     * 
     * @since 2.1
     */
    final private int _seed;

    final private int _flags;

    
Whether any canonicalization should be attempted (whether using
intern or not.

NOTE: non-final since we may need to disable this with overflow.
/**
     * Whether any canonicalization should be attempted (whether using
     * intern or not.
     *<p>
     * NOTE: non-final since we may need to disable this with overflow.
     */
    private boolean _canonicalize;

    /*
    /**********************************************************
    /* Actual symbol table data
    /**********************************************************
     */

    
Primary matching symbols; it's expected most match occur from
here.
/**
     * Primary matching symbols; it's expected most match occur from
     * here.
     */
    private String[] _symbols;

    
Overflow buckets; if primary doesn't match, lookup is done
from here.

Note: Number of buckets is half of number of symbol entries, on
assumption there's less need for buckets.
/**
     * Overflow buckets; if primary doesn't match, lookup is done
     * from here.
     *<p>
     * Note: Number of buckets is half of number of symbol entries, on
     * assumption there's less need for buckets.
     */
    private Bucket[] _buckets;

    
Current size (number of entries); needed to know if and when
rehash.
/**
     * Current size (number of entries); needed to know if and when
     * rehash.
     */
    private int _size;

    
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.
/**
     * 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.
     */
    private int _sizeThreshold;

    
Mask used to get index from hash values; equal to
_buckets.length - 1, when _buckets.length is
a power of two.
/**
     * Mask used to get index from hash values; equal to
     * <code>_buckets.length - 1</code>, when _buckets.length is
     * a power of two.
     */
    private int _indexMask;

    
We need to keep track of the longest collision list; this is needed
both to indicate problems with attacks and to allow flushing for
other cases.
Since:
2.1/**
     * We need to keep track of the longest collision list; this is needed
     * both to indicate problems with attacks and to allow flushing for
     * other cases.
     * 
     * @since 2.1
     */
    private int _longestCollisionList;

    /*
    /**********************************************************
    /* State regarding shared arrays
    /**********************************************************
     */

    
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)
/**
     * 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.
     *<p>
     * 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)
     */
    private boolean _hashShared;

    /*
    /**********************************************************
    /* Bit of DoS detection goodness
    /**********************************************************
     */

    
Lazily constructed structure that is used to keep track of
collision buckets that have overflowed once: this is used
to detect likely attempts at denial-of-service attacks that
uses hash collisions.
Since:
2.4/**
     * Lazily constructed structure that is used to keep track of
     * collision buckets that have overflowed once: this is used
     * to detect likely attempts at denial-of-service attacks that
     * uses hash collisions.
     * 
     * @since 2.4
     */
    private BitSet _overflows;

    /*
    /**********************************************************
    /* Life-cycle: constructors
    /**********************************************************
     */

    
Main method for constructing a root symbol table instance.
/**
     * Main method for constructing a root symbol table instance.
     */
    private CharsToNameCanonicalizer(int seed)
    {
        _parent = null;
        _seed = seed;
        
        // these settings don't really matter for the bootstrap instance
        _canonicalize = true;
        _flags = -1;
        // And we'll also set flags so no copying of buckets is needed:
        _hashShared = false; // doesn't really matter for root instance
        _longestCollisionList = 0;

        _tableInfo = new AtomicReference<TableInfo>(TableInfo.createInitial(DEFAULT_T_SIZE));
        // and actually do NOT assign buffers so we'll find if anyone tried to
        // use root instance
    }

    
Internal constructor used when creating child instances.
/**
     * Internal constructor used when creating child instances.
     */
    private CharsToNameCanonicalizer(CharsToNameCanonicalizer parent, int flags, int seed,
            TableInfo parentState)
    {
        _parent = parent;
        _seed = seed;
        _tableInfo = null; // not used by child tables
        _flags = flags;
        _canonicalize = JsonFactory.Feature.CANONICALIZE_FIELD_NAMES.enabledIn(flags);

        // Then copy shared state
        _symbols = parentState.symbols;
        _buckets = parentState.buckets;

        _size = parentState.size;
        _longestCollisionList = parentState.longestCollisionList;

        // Hard-coded fill factor, 75%
        int arrayLen = (_symbols.length);
        _sizeThreshold = _thresholdSize(arrayLen);
        _indexMask =  (arrayLen - 1);

        // Need to make copies of arrays, if/when adding new entries
        _hashShared = true;
    }

    private static int _thresholdSize(int hashAreaSize) { return hashAreaSize - (hashAreaSize >> 2); }

    /*
    /**********************************************************
    /* Life-cycle: factory methods, merging
    /**********************************************************
     */

    
Method called to create root canonicalizer for a JsonFactory instance. Root instance is never used directly; its main use is for storing and sharing underlying symbol arrays as needed. /**
     * Method called to create root canonicalizer for a {@link com.fasterxml.jackson.core.JsonFactory}
     * instance. Root instance is never used directly; its main use is for
     * storing and sharing underlying symbol arrays as needed.
     */
    public static CharsToNameCanonicalizer createRoot() {
        // Need to use a variable seed, to thwart hash-collision based attacks.
        // 14-Feb-2017, tatu: not sure it actually helps, at all, since it won't
        //   change mixing or any of the steps. Should likely just remove in future.
        long now = System.currentTimeMillis();
        // ensure it's not 0; and might as well require to be odd so:
        int seed = (((int) now) + ((int) (now >>> 32))) | 1;
        return createRoot(seed);
    }

    protected static CharsToNameCanonicalizer createRoot(int seed) {
        return new CharsToNameCanonicalizer(seed);
    }
    
"Factory" method; will create a new child instance of this symbol
table. It will be a copy-on-write instance, ie. it will only use
read-only copy of parent's data, but when changes are needed, a
copy will be created.

Note: while this method is synchronized, it is generally not
safe to both use makeChild/mergeChild, AND to use instance
actively. Instead, a separate 'root' instance should be used
on which only makeChild/mergeChild are called, but instance itself
is not used as a symbol table.
/**
     * "Factory" method; will create a new child instance of this symbol
     * table. It will be a copy-on-write instance, ie. it will only use
     * read-only copy of parent's data, but when changes are needed, a
     * copy will be created.
     *<p>
     * Note: while this method is synchronized, it is generally not
     * safe to both use makeChild/mergeChild, AND to use instance
     * actively. Instead, a separate 'root' instance should be used
     * on which only makeChild/mergeChild are called, but instance itself
     * is not used as a symbol table.
     */
    public CharsToNameCanonicalizer makeChild(int flags) {
        return new CharsToNameCanonicalizer(this, flags, _seed, _tableInfo.get());
    }

    
Method called by the using code to indicate it is done with this instance.
This lets instance merge accumulated changes into parent (if need be),
safely and efficiently, and without calling code having to know about parent
information.
/**
     * Method called by the using code to indicate it is done with this instance.
     * This lets instance merge accumulated changes into parent (if need be),
     * safely and efficiently, and without calling code having to know about parent
     * information.
     */
    public void release() {
        // If nothing has been added, nothing to do
        if (!maybeDirty()) { return; }

        // we will try to merge if child table has new entries
        if (_parent != null && _canonicalize) { // canonicalize set to false if max size was reached
            _parent.mergeChild(new TableInfo(this));
            // Let's also mark this instance as dirty, so that just in
            // case release was too early, there's no corruption of possibly shared data.
            _hashShared = true;
        }
    }

    
Method that allows contents of child table to potentially be
"merged in" with contents of this symbol table.

Note that caller has to make sure symbol table passed in is
really a child or sibling of this symbol table.
/**
     * Method that allows contents of child table to potentially be
     * "merged in" with contents of this symbol table.
     *<p>
     * Note that caller has to make sure symbol table passed in is
     * really a child or sibling of this symbol table.
     */
    private void mergeChild(TableInfo childState)
    {
        final int childCount = childState.size;
        TableInfo currState = _tableInfo.get();

        // Should usually grow; but occasionally could also shrink if (but only if)
        // collision list overflow ends up clearing some collision lists.
        if (childCount == currState.size) {
            return;
        }
        // One caveat: let's try to avoid problems with  degenerate cases of documents with
        // generated "random" names: for these, symbol tables would bloat indefinitely.
        // One way to do this is to just purge tables if they grow
        // too large, and that's what we'll do here.
        if (childCount > MAX_ENTRIES_FOR_REUSE) {
            // At any rate, need to clean up the tables
            childState = TableInfo.createInitial(DEFAULT_T_SIZE);
        }
        _tableInfo.compareAndSet(currState, childState);
    }

    /*
    /**********************************************************
    /* Public API, generic accessors:
    /**********************************************************
     */

    public int size() {
        if (_tableInfo != null) { // root table
            return _tableInfo.get().size;
        }
        // nope, child table
        return _size;
    }

    
Method for checking number of primary hash buckets this symbol
table uses.
Since:
2.1/**
     * Method for checking number of primary hash buckets this symbol
     * table uses.
     * 
     * @since 2.1
     */
    public int bucketCount() {  return _symbols.length; }
    public boolean maybeDirty() { return !_hashShared; }
    public int hashSeed() { return _seed; }

    
Method mostly needed by unit tests; calculates number of entries that are in collision list. Value can be at most (size - 1), but should usually be much lower, ideally 0. 
Since:
2.1/**
     * Method mostly needed by unit tests; calculates number of
     * entries that are in collision list. Value can be at most
     * ({@link #size} - 1), but should usually be much lower, ideally 0.
     * 
     * @since 2.1
     */
    public int collisionCount() {
        int count = 0;
        
        for (Bucket bucket : _buckets) {
            if (bucket != null) {
                count += bucket.length;
            }
        }
        return count;
    }

    
Method mostly needed by unit tests; calculates length of the longest collision chain. This should typically be a low number, but may be up to size - 1 in the pathological case 
Since:
2.1/**
     * Method mostly needed by unit tests; calculates length of the
     * longest collision chain. This should typically be a low number,
     * but may be up to {@link #size} - 1 in the pathological case
     * 
     * @since 2.1
     */
    public int maxCollisionLength() { return _longestCollisionList; }

    /*
    /**********************************************************
    /* Public API, accessing symbols:
    /**********************************************************
     */

    public String findSymbol(char[] buffer, int start, int len, int h)
    {
        if (len < 1) { // empty Strings are simplest to handle up front
            return "";
        }
        if (!_canonicalize) { // [JACKSON-259]
            return new String(buffer, start, len);
        }

        /* Related to problems with sub-standard hashing (somewhat
         * relevant for collision attacks too), let's try little
         * bit of shuffling to improve hash codes.
         * (note, however, that this can't help with full collisions)
         */
        int index = _hashToIndex(h);
        String sym = _symbols[index];

        // Optimal case; checking existing primary symbol for hash index:
        if (sym != null) {
            // Let's inline primary String equality checking:
            if (sym.length() == len) {
                int i = 0;
                while (sym.charAt(i) == buffer[start+i]) {
                    // Optimal case; primary match found
                    if (++i == len) {
                        return sym;
                    }
                }
            }
            Bucket b = _buckets[index>>1];
            if (b != null) {
                sym = b.has(buffer, start, len);
                if (sym != null) {
                    return sym;
                }
                sym = _findSymbol2(buffer, start, len, b.next);
                if (sym != null) {
                    return sym;
                }
            }
        }
        return _addSymbol(buffer, start, len, h, index);
    }

    private String _findSymbol2(char[] buffer, int start, int len, Bucket b) {
        while (b != null) {
            String sym = b.has(buffer, start, len);
            if (sym != null) {
                return sym;
            }
            b = b.next;
        }
        return null;
    }

    private String _addSymbol(char[] buffer, int start, int len, int h, int index)
    {
        if (_hashShared) { //need to do copy-on-write?
            copyArrays();
            _hashShared = false;
        } else if (_size >= _sizeThreshold) { // Need to expand?
            rehash();
            // Need to recalc hash; rare occurrence (index mask has been
             // recalculated as part of rehash)
            index = _hashToIndex(calcHash(buffer, start, len));
        }

        String newSymbol = new String(buffer, start, len);
        if (JsonFactory.Feature.INTERN_FIELD_NAMES.enabledIn(_flags)) {
            newSymbol = InternCache.instance.intern(newSymbol);
        }
        ++_size;
        // Ok; do we need to add primary entry, or a bucket?
        if (_symbols[index] == null) {
            _symbols[index] = newSymbol;
        } else {
            final int bix = (index >> 1);
            Bucket newB = new Bucket(newSymbol, _buckets[bix]);
            int collLen = newB.length;
            if (collLen > MAX_COLL_CHAIN_LENGTH) {
                // 23-May-2014, tatu: Instead of throwing an exception right away,
                //    let's handle in bit smarter way.
                _handleSpillOverflow(bix, newB, index);
            } else {
                _buckets[bix] = newB;
                _longestCollisionList = Math.max(collLen, _longestCollisionList);
            }
        }
        return newSymbol;
    }

    
Method called when an overflow bucket has hit the maximum expected length:
this may be a case of DoS attack. Deal with it based on settings by either
clearing up bucket (to avoid indefinite expansion) or throwing exception.
Currently the first overflow for any single bucket DOES NOT throw an exception,
only second time (per symbol table instance)
/**
     * Method called when an overflow bucket has hit the maximum expected length:
     * this may be a case of DoS attack. Deal with it based on settings by either
     * clearing up bucket (to avoid indefinite expansion) or throwing exception.
     * Currently the first overflow for any single bucket DOES NOT throw an exception,
     * only second time (per symbol table instance)
     */
    private void _handleSpillOverflow(int bucketIndex, Bucket newBucket, int mainIndex)
    {
        if (_overflows == null) {
            _overflows = new BitSet();
            _overflows.set(bucketIndex);
        } else {
            if (_overflows.get(bucketIndex)) {
                // Has happened once already for this bucket index, so probably not coincidental...
                if (JsonFactory.Feature.FAIL_ON_SYMBOL_HASH_OVERFLOW.enabledIn(_flags)) {
                    reportTooManyCollisions(MAX_COLL_CHAIN_LENGTH);
                }
                // but even if we don't fail, we will stop canonicalizing as safety measure
                // (so as not to cause problems with PermGen)
                _canonicalize = false;
            } else {
                _overflows.set(bucketIndex);
            }
        }

        // regardless, if we get this far, clear up the bucket, adjust size appropriately.
        _symbols[mainIndex] = newBucket.symbol;
        _buckets[bucketIndex] = null;
        // newBucket contains new symbol; but we will
        _size -= (newBucket.length);
        // we could calculate longest; but for now just mark as invalid
        _longestCollisionList = -1;
    }

    
Helper method that takes in a "raw" hash value, shuffles it as necessary,
and truncates to be used as the index.
/**
     * Helper method that takes in a "raw" hash value, shuffles it as necessary,
     * and truncates to be used as the index.
     */
    public int _hashToIndex(int rawHash) {
        // doing these seems to help a bit
        rawHash += (rawHash >>> 15);
        rawHash ^= (rawHash << 7);
        rawHash += (rawHash >>> 3);
        return (rawHash & _indexMask);
    }

    
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.
Params:
len – Length of String; has to be at least 1 (caller guarantees
  this pre-condition)/**
     * 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.
     *
     * @param len Length of String; has to be at least 1 (caller guarantees
     *   this pre-condition)
     */
    public int calcHash(char[] buffer, int start, int len) {
        int hash = _seed;
        for (int i = start, end = start+len; i < end; ++i) {
            hash = (hash * HASH_MULT) + (int) buffer[i];
        }
        // NOTE: shuffling, if any, is done in 'findSymbol()', not here:
        return (hash == 0) ? 1 : hash;
    }

    public int calcHash(String key)
    {
        final int len = key.length();
        
        int hash = _seed;
        for (int i = 0; i < len; ++i) {
            hash = (hash * HASH_MULT) + (int) key.charAt(i);
        }
        // NOTE: shuffling, if any, is done in 'findSymbol()', not here:
        return (hash == 0) ? 1 : hash;
    }

    /*
    /**********************************************************
    /* Internal methods
    /**********************************************************
     */

    
Method called when copy-on-write is needed; generally when first
change is made to a derived symbol table.
/**
     * Method called when copy-on-write is needed; generally when first
     * change is made to a derived symbol table.
     */
    private void copyArrays() {
        final String[] oldSyms = _symbols;
        _symbols = Arrays.copyOf(oldSyms, oldSyms.length);
        final Bucket[] oldBuckets = _buckets;
        _buckets = Arrays.copyOf(oldBuckets, oldBuckets.length);
    }

    
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.
/**
     * 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.
     */
    private void rehash() {
        final int size = _symbols.length;
        int newSize = size + size;

        /* 12-Mar-2010, tatu: Let's actually limit maximum size we are
         *    prepared to use, to guard against OOME in case of unbounded
         *    name sets (unique [non-repeating] names)
         */
        if (newSize > MAX_T_SIZE) {
            // If this happens, there's no point in either growing or shrinking hash areas.
            // Rather, let's just cut our losses and stop canonicalizing.
            _size = 0;
            _canonicalize = false;
            // in theory, could just leave these as null, but...
            _symbols = new String[DEFAULT_T_SIZE];
            _buckets = new Bucket[DEFAULT_T_SIZE>>1];
            _indexMask = DEFAULT_T_SIZE-1;
            _hashShared = false;
            return;
        }

        final String[] oldSyms = _symbols;
        final Bucket[] oldBuckets = _buckets;
        _symbols = new String[newSize];
        _buckets = new Bucket[newSize >> 1];
        // Let's update index mask, threshold, now (needed for rehashing)
        _indexMask = newSize - 1;
        _sizeThreshold = _thresholdSize(newSize);

        int count = 0; // let's do sanity check

        // Need to do two loops, unfortunately, since spill-over area is
        // only half the size:
        int maxColl = 0;
        for (int i = 0; i < size; ++i) {
            String symbol = oldSyms[i];
            if (symbol != null) {
                ++count;
                int index = _hashToIndex(calcHash(symbol));
                if (_symbols[index] == null) {
                    _symbols[index] = symbol;
                } else {
                    int bix = (index >> 1);
                    Bucket newB = new Bucket(symbol, _buckets[bix]);
                    _buckets[bix] = newB;
                    maxColl = Math.max(maxColl, newB.length);
                }
            }
        }

        final int bucketSize = (size >> 1);
        for (int i = 0; i < bucketSize; ++i) {
            Bucket b = oldBuckets[i];
            while (b != null) {
                ++count;
                String symbol = b.symbol;
                int index = _hashToIndex(calcHash(symbol));
                if (_symbols[index] == null) {
                    _symbols[index] = symbol;
                } else {
                    int bix = (index >> 1);
                    Bucket newB = new Bucket(symbol, _buckets[bix]);
                    _buckets[bix] = newB;
                    maxColl = Math.max(maxColl, newB.length);
                }
                b = b.next;
            }
        }
        _longestCollisionList = maxColl;
        _overflows = null;

        if (count != _size) {
            throw new IllegalStateException(String.format(
                    "Internal error on SymbolTable.rehash(): had %d entries; now have %d",
                    _size, count));
        }
    }

    
Since:
2.1/**
     * @since 2.1
     */
    protected void reportTooManyCollisions(int maxLen) {
        throw new IllegalStateException("Longest collision chain in symbol table (of size "+_size
                +") now exceeds maximum, "+maxLen+" -- suspect a DoS attack based on hash collisions");
    }

    // since 2.10, for tests only
    
Diagnostics method that will verify that internal data structures are consistent;
not meant as user-facing method but only for test suites and possible troubleshooting.
Since:
2.10/**
     * Diagnostics method that will verify that internal data structures are consistent;
     * not meant as user-facing method but only for test suites and possible troubleshooting.
     *
     * @since 2.10
     */
    protected void verifyInternalConsistency() {
        int count = 0;
        final int size = _symbols.length;

        for (int i = 0; i < size; ++i) {
            String symbol = _symbols[i];
            if (symbol != null) {
                ++count;
            }
        }

        final int bucketSize = (size >> 1);
        for (int i = 0; i < bucketSize; ++i) {
            for (Bucket b = _buckets[i]; b != null; b = b.next) {
                ++count;
            }
        }
        if (count != _size) {
            throw new IllegalStateException(String.format("Internal error: expected internal size %d vs calculated count %d",
                    _size, count));
        }
    }

    // For debugging, comment out
    /*
    @Override
    public String toString()
    {
        StringBuilder sb = new StringBuilder();
        int primaryCount = 0;
        for (String s : _symbols) {
            if (s != null) ++primaryCount;
        }
        
        sb.append("[BytesToNameCanonicalizer, size: ");
        sb.append(_size);
        sb.append('/');
        sb.append(_symbols.length);
        sb.append(", ");
        sb.append(primaryCount);
        sb.append('/');
        sb.append(_size - primaryCount);
        sb.append(" coll; avg length: ");

        // Average length: minimum of 1 for all (1 == primary hit);
        // and then 1 per each traversal for collisions/buckets
        //int maxDist = 1;
        int pathCount = _size;
        for (Bucket b : _buckets) {
            if (b != null) {
                int spillLen = b.length;
                for (int j = 1; j <= spillLen; ++j) {
                    pathCount += j;
                }
            }
        }
        double avgLength;

        if (_size == 0) {
            avgLength = 0.0;
        } else {
            avgLength = (double) pathCount / (double) _size;
        }
        // let's round up a bit (two 2 decimal places)
        //avgLength -= (avgLength % 0.01);

        sb.append(avgLength);
        sb.append(']');
        return sb.toString();
    }
*/

    /*
    /**********************************************************
    /* Helper classes
    /**********************************************************
     */

    
This class is a symbol table entry. Each entry acts as a node
in a linked list.
/**
     * This class is a symbol table entry. Each entry acts as a node
     * in a linked list.
     */
    static final class Bucket
    {
        public final String symbol;
        public final Bucket next;
        public final int length;

        public Bucket(String s, Bucket n) {
            symbol = s;
            next = n;
            length = (n == null) ? 1 : n.length+1;
        }

        public String has(char[] buf, int start, int len) {
            if (symbol.length() != len) {
                return null;
            }
            int i = 0;
            do {
                if (symbol.charAt(i) != buf[start+i]) {
                    return null;
                }
            } while (++i < len);
            return symbol;
        }
    }

    
Immutable value class used for sharing information as efficiently
as possible, by only require synchronization of reference manipulation
but not access to contents.
Since:
2.8.7/**
     * Immutable value class used for sharing information as efficiently
     * as possible, by only require synchronization of reference manipulation
     * but not access to contents.
     * 
     * @since 2.8.7
     */
    private final static class TableInfo
    {
        final int size;
        final int longestCollisionList;
        final String[] symbols;
        final Bucket[] buckets;

        public TableInfo(int size, int longestCollisionList,
                String[] symbols, Bucket[] buckets)
        {
            this.size = size;
            this.longestCollisionList = longestCollisionList;
            this.symbols = symbols;
            this.buckets = buckets;
        }

        public TableInfo(CharsToNameCanonicalizer src)
        {
            this.size = src._size;
            this.longestCollisionList = src._longestCollisionList;
            this.symbols = src._symbols;
            this.buckets = src._buckets;
        }

        public static TableInfo createInitial(int sz) {
            return new TableInfo(0,
                    0, // longestCollisionList
                    new String[sz], new Bucket[sz >> 1]);
        }
    }
}