X-Git-Url: https://gerrit.simantics.org/r/gitweb?a=blobdiff_plain;f=bundles%2Forg.simantics.scl.runtime%2Fsrc%2Forg%2Fsimantics%2Fscl%2Fruntime%2Fchr%2FCHRHashIndex.java;fp=bundles%2Forg.simantics.scl.runtime%2Fsrc%2Forg%2Fsimantics%2Fscl%2Fruntime%2Fchr%2FCHRHashIndex.java;h=cd1f9c3c65a55dba18c6a64829097525ccb88ff6;hb=0ae2b770234dfc3cbb18bd38f324125cf0faca07;hp=d8102b7dd0351058f4bd18e8e8c326d783213f60;hpb=24e2b34260f219f0d1644ca7a138894980e25b14;p=simantics%2Fplatform.git diff --git a/bundles/org.simantics.scl.runtime/src/org/simantics/scl/runtime/chr/CHRHashIndex.java b/bundles/org.simantics.scl.runtime/src/org/simantics/scl/runtime/chr/CHRHashIndex.java index d8102b7dd..cd1f9c3c6 100644 --- a/bundles/org.simantics.scl.runtime/src/org/simantics/scl/runtime/chr/CHRHashIndex.java +++ b/bundles/org.simantics.scl.runtime/src/org/simantics/scl/runtime/chr/CHRHashIndex.java @@ -1,1616 +1,1616 @@ -/* - * Copyright 2014 the original author or authors. - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package org.simantics.scl.runtime.chr; - -import static java.util.Arrays.binarySearch; - -import java.util.Arrays; - -/** - * This class is adapted from MutableQHashObjSetGO class generated by Koloboke library. - * It is used by code generated by SCL compiler. - */ -public class CHRHashIndex { - - private static final double MIN_LOAD = 1.0 / 3.0; - private static final double MAX_LOAD = 2.0 / 3.0; - private static final double TARGET_LOAD = 0.5; - private static final double GROWTH_FACTOR = 2.0; - private static final int INITIAL_CAPACITY = 10; - - private static final Object REMOVED = new Object(); - private static final Object FREE = null; - - //////////////////////////// - // Fields - - /** The current number of occupied slots in the hash. */ - private int size; - - private int maxSize; - - /** The current number of free slots in the hash. */ - private int freeSlots; - - private int minFreeSlots; - - private int removedSlots; - - private Object[] set; - - private static int mix(int hash) { - return hash & Integer.MAX_VALUE; - } - - private boolean noRemoved() { - return removedSlots == 0; - } - - /** - * Creates data structures with a prime capacity at or near the minimum - * needed to hold {@code size} elements without triggering a rehash. - * - *

Should be called only in constructors and externalization code. - */ - private void init(int size) { - this.size = 0; - internalInit(targetCapacity(size)); - } - - private void internalInit(int capacity) { - initSlotCounts(capacity); - allocateArrays(capacity); - } - - private void initSlotCounts(int capacity) { - // No sense in trying to rehash after each insertion - // if the capacity is already reached the limit. - maxSize = !isMaxCapacity(capacity) ? maxSize(capacity) : capacity - 1; - minFreeSlots = minFreeSlots(capacity, size, MAX_LOAD, maxSize); - int freeSlots = this.freeSlots = capacity - size; - // free could be less than minFreeSlots only in case when capacity - // is not sufficient to comply load factor (due to saturation with - // Java array size limit). Set minFreeSlots to a half of free to avoid - // too often (instant) rehashing in this case. - if (freeSlots < minFreeSlots) this.minFreeSlots = (freeSlots + 1) / 2; - removedSlots = 0; - } - - private static int minFreeSlots(int capacity, int size, double maxLoad, int maxSize) { - double load = (double) size / (double) capacity; - // See "Tombstones purge from hashtable: theory and practice" wiki page - double rehashLoad = - 0.55 + 0.721 * load - 0.274 * load * load; - - int minFreeSlots; - // minFreeSlots shouldn't be less than `capacity - maxSize` - if (rehashLoad > maxLoad) { - minFreeSlots = (int) ((double) capacity * (1.0 - rehashLoad)); - } else { - minFreeSlots = capacity - maxSize; - } - // Need at least one free slot for open addressing - return minFreeSlots > 0 ? minFreeSlots : 1; - } - - ///////////////////////////// - // Modification hooks and rehash logic - - public boolean shrink() { - int newCapacity = targetCapacity(size); - if (removedSlots > 0 || newCapacity < set.length) { - rehash(newCapacity); - return true; - } else { - return false; - } - } - - private boolean tryRehashForExpansion(int newCapacity) { - // No sense in rehashing for expansion if we already reached Java array - // size limit. - if (newCapacity > set.length || removedSlots > 0) { - rehash(newCapacity); - return true; - } else { - if (freeSlots < minFreeSlots) - minFreeSlots = (freeSlots + 1) / 2; - return false; - } - } - - public boolean ensureCapacity(long minSize) { - int intMinSize = (int) Math.min(minSize, (long) Integer.MAX_VALUE); - if (minSize < 0L) - throw new IllegalArgumentException( - "Min size should be positive, " + minSize + " given."); - int additionalSize = intMinSize - size; - if (additionalSize <= 0) - return false; - if (intMinSize > maxSize || freeSlots - additionalSize < minFreeSlots) { - return tryRehashForExpansion(targetCapacity(intMinSize)); - } else { - return false; - } - } - - private void postRemoveHook() { - size--; - removedSlots++; - } - - private void postFreeSlotInsertHook() { - if (++size > maxSize) { - if (tryRehashForExpansion(grownCapacity())) - return; - } - if (--freeSlots < minFreeSlots) { - if (!tryRehashIfTooFewFreeSlots() && freeSlots == 0) { - throw new CHRHashOverflowException(); - } - } - } - - private void postRemovedSlotInsertHook() { - if (++size > maxSize) { - if (tryRehashForExpansion(grownCapacity())) - return; - } - removedSlots--; - } - - private boolean tryRehashIfTooFewFreeSlots() { - if (removedSlots > 0) { - rehash(targetCapacity(size)); - return true; - } else { - return tryRehashForExpansion(grownCapacity()); - } - } - - /** For initial hash table construction and rehash to target load (shrink, tombstones purge). */ - private int targetCapacity(int size) { - return capacity(size, targetLoadInverse.scaleUpper(size)); - } - - /** The highest qHash prime below Integer.MAX_VALUE (which is a qHash prime too). */ - private static final int MAX_INT_CAPACITY = 2147483587; - - - private boolean isMaxCapacity(int capacity) { - return capacity >= MAX_INT_CAPACITY; - } - - private int grownCapacity() { - return nearestGreaterCapacity(grow(set.length), size); - } - - protected boolean keyEquals(Object a, Object b) { - return a.equals(b); - } - - protected int keyHashCode(Object key) { - return key.hashCode(); - } - - - public boolean contains(Object key) { - return index(key) >= 0; - } - - private int index(Object key) { - // noinspection unchecked - Object[] keys = set; - int capacity, index; - Object cur; - if ((cur = keys[index = mix(keyHashCode(key)) % (capacity = keys.length)]) == key) { - // key is present - return index; - } else { - if (cur == FREE) { - // key is absent, free slot - return -1; - } else { - if (cur != REMOVED) { - if (keyEquals(key, cur)) { - // key is present - return index; - } else { - if (noRemoved()) { - int bIndex = index, fIndex = index, step = 1; - while (true) { - if ((bIndex -= step) < 0) bIndex += capacity; - if ((cur = keys[bIndex]) == key) { - // key is present - return bIndex; - } else if (cur == FREE) { - // key is absent, free slot - return -1; - } - else if (keyEquals(key, cur)) { - // key is present - return bIndex; - } - int t; - if ((t = (fIndex += step) - capacity) >= 0) fIndex = t; - if ((cur = keys[fIndex]) == key) { - // key is present - return fIndex; - } else if (cur == FREE) { - // key is absent, free slot - return -1; - } - else if (keyEquals(key, cur)) { - // key is present - return fIndex; - } - step += 2; - } - } - } - } - int bIndex = index, fIndex = index, step = 1; - while (true) { - if ((bIndex -= step) < 0) bIndex += capacity; - if ((cur = keys[bIndex]) == key) { - // key is present - return bIndex; - } else if (cur == FREE) { - // key is absent, free slot - return -1; - } - else if (cur != REMOVED && keyEquals(key, cur)) { - // key is present - return bIndex; - } - int t; - if ((t = (fIndex += step) - capacity) >= 0) fIndex = t; - if ((cur = keys[fIndex]) == key) { - // key is present - return fIndex; - } else if (cur == FREE) { - // key is absent, free slot - return -1; - } - else if (cur != REMOVED && keyEquals(key, cur)) { - // key is present - return fIndex; - } - step += 2; - } - } - } - } - - private void allocateArrays(int capacity) { - set = new Object[capacity]; - // not necessary because FREE = null - // Arrays.fill(set, FREE); - } - - - public Object[] toArray() { - Object[] result = new Object[size]; - if (size == 0) - return result; - int resultIndex = 0; - Object[] keys = set; - if (noRemoved()) { - for (int i = keys.length - 1; i >= 0; i--) { - Object key; - // noinspection unchecked - if ((key = keys[i]) != FREE) { - result[resultIndex++] = key; - } - } - } else { - for (int i = keys.length - 1; i >= 0; i--) { - Object key; - // noinspection unchecked - if ((key = keys[i]) != FREE && key != REMOVED) { - result[resultIndex++] = key; - } - } - } - return result; - } - - @SuppressWarnings("unchecked") - public T[] toArray(T[] a) { - if (a.length < size) { - Class elementType = a.getClass().getComponentType(); - a = (T[]) java.lang.reflect.Array.newInstance(elementType, size); - } - if (size == 0) { - if (a.length > 0) - a[0] = null; - return a; - } - int resultIndex = 0; - Object[] keys = set; - if (noRemoved()) { - for (int i = keys.length - 1; i >= 0; i--) { - Object key; - // noinspection unchecked - if ((key = keys[i]) != FREE) { - a[resultIndex++] = (T) key; - } - } - } else { - for (int i = keys.length - 1; i >= 0; i--) { - Object key; - // noinspection unchecked - if ((key = keys[i]) != FREE && key != REMOVED) { - a[resultIndex++] = (T) key; - } - } - } - if (a.length > resultIndex) - a[resultIndex] = null; - return a; - } - - private void rehash(int newCapacity) { - Object[] keys = set; - int removedSlots = this.removedSlots; - internalInit(newCapacity); - Object[] newKeys = set; - int capacity = newKeys.length; - if (removedSlots == 0) { - for (int i = keys.length - 1; i >= 0; i--) { - Object key; - // noinspection unchecked - if ((key = keys[i]) != FREE) { - int index; - if (newKeys[index = mix(keyHashCode(key)) % capacity] != FREE) { - int bIndex = index, fIndex = index, step = 1; - while (true) { - if ((bIndex -= step) < 0) bIndex += capacity; - if (newKeys[bIndex] == FREE) { - index = bIndex; - break; - } - int t; - if ((t = (fIndex += step) - capacity) >= 0) fIndex = t; - if (newKeys[fIndex] == FREE) { - index = fIndex; - break; - } - step += 2; - } - } - newKeys[index] = key; - } - } - } else { - for (int i = keys.length - 1; i >= 0; i--) { - Object key; - // noinspection unchecked - if ((key = keys[i]) != FREE && key != REMOVED) { - int index; - if (newKeys[index = mix(keyHashCode(key)) % capacity] != FREE) { - int bIndex = index, fIndex = index, step = 1; - while (true) { - if ((bIndex -= step) < 0) bIndex += capacity; - if (newKeys[bIndex] == FREE) { - index = bIndex; - break; - } - int t; - if ((t = (fIndex += step) - capacity) >= 0) fIndex = t; - if (newKeys[fIndex] == FREE) { - index = fIndex; - break; - } - step += 2; - } - } - newKeys[index] = key; - } - } - } - } - - public void clear() { - size = 0; - freeSlots = set.length; - removedSlots = 0; - Arrays.fill(set, FREE); - } - - - public CHRHashIndex() { - init(INITIAL_CAPACITY); - } - - public boolean add(Object key) { - Object[] keys = set; - int capacity, index; - Object cur; - keyAbsentFreeSlot: - if ((cur = keys[index = mix(keyHashCode(key)) % (capacity = keys.length)]) != FREE) { - if (cur == key) { - // key is present - return false; - } else { - int firstRemoved; - if (cur != REMOVED) { - if (!keyEquals(key, cur)) { - if (noRemoved()) { - int bIndex = index, fIndex = index, step = 1; - while (true) { - if ((bIndex -= step) < 0) bIndex += capacity; - if ((cur = keys[bIndex]) == FREE) { - index = bIndex; - break keyAbsentFreeSlot; - } else if (cur == key || (keyEquals(key, cur))) { - // key is present - return false; - } - int t; - if ((t = (fIndex += step) - capacity) >= 0) fIndex = t; - if ((cur = keys[fIndex]) == FREE) { - index = fIndex; - break keyAbsentFreeSlot; - } else if (cur == key || (keyEquals(key, cur))) { - // key is present - return false; - } - step += 2; - } - } else { - firstRemoved = -1; - } - } else { - // key is present - return false; - } - } else { - firstRemoved = index; - } - keyAbsentRemovedSlot: { - int bIndex = index, fIndex = index, step = 1; - while (true) { - if ((bIndex -= step) < 0) bIndex += capacity; - if ((cur = keys[bIndex]) == FREE) { - if (firstRemoved < 0) { - index = bIndex; - break keyAbsentFreeSlot; - } else { - break keyAbsentRemovedSlot; - } - } else if (cur == key) { - // key is present - return false; - } else if (cur != REMOVED) { - if (keyEquals(key, cur)) { - // key is present - return false; - } - } else if (firstRemoved < 0) { - firstRemoved = bIndex; - } - int t; - if ((t = (fIndex += step) - capacity) >= 0) fIndex = t; - if ((cur = keys[fIndex]) == FREE) { - if (firstRemoved < 0) { - index = fIndex; - break keyAbsentFreeSlot; - } else { - break keyAbsentRemovedSlot; - } - } else if (cur == key) { - // key is present - return false; - } else if (cur != REMOVED) { - if (keyEquals(key, cur)) { - // key is present - return false; - } - } else if (firstRemoved < 0) { - firstRemoved = fIndex; - } - step += 2; - } - } - // key is absent, removed slot - keys[firstRemoved] = key; - postRemovedSlotInsertHook(); - return true; - } - } - // key is absent, free slot - keys[index] = key; - postFreeSlotInsertHook(); - return true; - } - - /** - * Assumes that the given value doesn't already exist in the index - * (only optimized with this assumption, the method works correctly - * even if the assumption does not hold). - * Returns the old equal element that the given value replaces or - * null if there is no such elements. - */ - public Object addFreshAndReturnOld(Object key) { - Object[] keys = set; - int capacity, index; - Object cur; - keyAbsentFreeSlot: if ((cur = keys[index = mix(keyHashCode(key)) % (capacity = keys.length)]) != FREE) { - int firstRemoved; - if (cur != REMOVED) { - if (!keyEquals(key, cur)) { - if (noRemoved()) { - int bIndex = index, fIndex = index, step = 1; - while (true) { - if ((bIndex -= step) < 0) bIndex += capacity; - if ((cur = keys[bIndex]) == FREE) { - index = bIndex; - break keyAbsentFreeSlot; - } else if (keyEquals(key, cur)) { - keys[bIndex] = key; - return cur; - } - int t; - if ((t = (fIndex += step) - capacity) >= 0) fIndex = t; - if ((cur = keys[fIndex]) == FREE) { - index = fIndex; - break keyAbsentFreeSlot; - } else if (keyEquals(key, cur)) { - keys[fIndex] = key; - return cur; - } - step += 2; - } - } else { - firstRemoved = -1; - } - } else { - keys[index] = key; - return cur; - } - } else { - firstRemoved = index; - } - keyAbsentRemovedSlot: { - int bIndex = index, fIndex = index, step = 1; - while (true) { - if ((bIndex -= step) < 0) bIndex += capacity; - if ((cur = keys[bIndex]) == FREE) { - if (firstRemoved < 0) { - index = bIndex; - break keyAbsentFreeSlot; - } else { - break keyAbsentRemovedSlot; - } - } else if (cur != REMOVED) { - if (keyEquals(key, cur)) { - keys[bIndex] = key; - return cur; - } - } else if (firstRemoved < 0) { - firstRemoved = bIndex; - } - int t; - if ((t = (fIndex += step) - capacity) >= 0) fIndex = t; - if ((cur = keys[fIndex]) == FREE) { - if (firstRemoved < 0) { - index = fIndex; - break keyAbsentFreeSlot; - } else { - break keyAbsentRemovedSlot; - } - } else if (cur != REMOVED) { - if (keyEquals(key, cur)) { - keys[fIndex] = key; - return cur; - } - } else if (firstRemoved < 0) { - firstRemoved = fIndex; - } - step += 2; - } - } - // key is absent, removed slot - keys[firstRemoved] = key; - postRemovedSlotInsertHook(); - return null; - } - // key is absent, free slot - keys[index] = key; - postFreeSlotInsertHook(); - return null; - } - - public Object addFreshAndReturnOldNoRemovals(Object key) { - Object[] keys = set; - int capacity, index; - Object cur; - keyAbsentFreeSlot: if ((cur = keys[index = mix(keyHashCode(key)) % (capacity = keys.length)]) != FREE) { - if (!keyEquals(key, cur)) { - int bIndex = index, fIndex = index, step = 1; - while (true) { - if ((bIndex -= step) < 0) bIndex += capacity; - if ((cur = keys[bIndex]) == FREE) { - index = bIndex; - break keyAbsentFreeSlot; - } else if (keyEquals(key, cur)) { - keys[bIndex] = key; - return cur; - } - int t; - if ((t = (fIndex += step) - capacity) >= 0) fIndex = t; - if ((cur = keys[fIndex]) == FREE) { - index = fIndex; - break keyAbsentFreeSlot; - } else if (keyEquals(key, cur)) { - keys[fIndex] = key; - return cur; - } - step += 2; - } - } else { - keys[index] = key; - return cur; - } - } - // key is absent, free slot - keys[index] = key; - postFreeSlotInsertHook(); - return null; - } - - public boolean remove(Object key) { - // noinspection unchecked - Object[] keys = set; - int capacity, index; - Object cur; - keyPresent: - if ((cur = keys[index = mix(keyHashCode(key)) % (capacity = keys.length)]) != key) { - if (cur == FREE) { - // key is absent, free slot - return false; - } else { - if (cur != REMOVED) { - if (keyEquals(key, cur)) { - break keyPresent; - } else { - if (noRemoved()) { - int bIndex = index, fIndex = index, step = 1; - while (true) { - if ((bIndex -= step) < 0) bIndex += capacity; - if ((cur = keys[bIndex]) == key) { - index = bIndex; - break keyPresent; - } else if (cur == FREE) { - // key is absent, free slot - return false; - } - else if (keyEquals(key, cur)) { - index = bIndex; - break keyPresent; - } - int t; - if ((t = (fIndex += step) - capacity) >= 0) fIndex = t; - if ((cur = keys[fIndex]) == key) { - index = fIndex; - break keyPresent; - } else if (cur == FREE) { - // key is absent, free slot - return false; - } - else if (keyEquals(key, cur)) { - index = fIndex; - break keyPresent; - } - step += 2; - } - } - } - } - int bIndex = index, fIndex = index, step = 1; - while (true) { - if ((bIndex -= step) < 0) bIndex += capacity; - if ((cur = keys[bIndex]) == key) { - index = bIndex; - break keyPresent; - } else if (cur == FREE) { - // key is absent, free slot - return false; - } - else if (cur != REMOVED && keyEquals(key, cur)) { - index = bIndex; - break keyPresent; - } - int t; - if ((t = (fIndex += step) - capacity) >= 0) fIndex = t; - if ((cur = keys[fIndex]) == key) { - index = fIndex; - break keyPresent; - } else if (cur == FREE) { - // key is absent, free slot - return false; - } - else if (cur != REMOVED && keyEquals(key, cur)) { - index = fIndex; - break keyPresent; - } - step += 2; - } - } - } - // key is present - keys[index] = REMOVED; - postRemoveHook(); - return true; - } - - /** - * Assumes that the key exists in the index. Removes it. - */ - public void removeKnownToExistKey(Object key) { - Object[] keys = set; - int capacity, index; - keyPresent: if (keys[index = mix(keyHashCode(key)) % (capacity = keys.length)] != key) { - int bIndex = index, fIndex = index, step = 1; - while (true) { - if ((bIndex -= step) < 0) bIndex += capacity; - if (keys[bIndex] == key) { - index = bIndex; - break keyPresent; - } - int t; - if ((t = (fIndex += step) - capacity) >= 0) fIndex = t; - if (keys[fIndex] == key) { - index = fIndex; - break keyPresent; - } - step += 2; - } - } - keys[index] = REMOVED; - postRemoveHook(); - } - - /** - * Assumes that the key exists in the index. Replaces it with an equal key. - */ - public void replaceKnownToExistKey(Object key, Object replacement) { - Object[] keys = set; - int capacity, index; - keyPresent: if (keys[index = mix(keyHashCode(key)) % (capacity = keys.length)] != key) { - int bIndex = index, fIndex = index, step = 1; - while (true) { - if ((bIndex -= step) < 0) bIndex += capacity; - if (keys[bIndex] == key) { - index = bIndex; - break keyPresent; - } - int t; - if ((t = (fIndex += step) - capacity) >= 0) fIndex = t; - if (keys[fIndex] == key) { - index = fIndex; - break keyPresent; - } - step += 2; - } - } - keys[index] = replacement; - } - - public Object getEqual(Object key) { - // noinspection unchecked - Object[] keys = set; - int capacity, index; - Object cur; - if ((cur = keys[index = mix(keyHashCode(key)) % (capacity = keys.length)]) == FREE) - return null; - if (cur != REMOVED) { - if (keyEquals(key, cur)) - return cur; - if (noRemoved()) { - int bIndex = index, fIndex = index, step = 1; - while (true) { - if ((bIndex -= step) < 0) bIndex += capacity; - if ((cur = keys[bIndex]) == FREE) - return null; - else if (keyEquals(key, cur)) - return cur; - int t; - if ((t = (fIndex += step) - capacity) >= 0) fIndex = t; - if ((cur = keys[fIndex]) == FREE) - return null; - else if (keyEquals(key, cur)) - return cur; - step += 2; - } - } - } - int bIndex = index, fIndex = index, step = 1; - while (true) { - if ((bIndex -= step) < 0) bIndex += capacity; - if ((cur = keys[bIndex]) == FREE) - return null; - else if (cur != REMOVED && keyEquals(key, cur)) - return cur; - int t; - if ((t = (fIndex += step) - capacity) >= 0) fIndex = t; - if ((cur = keys[fIndex]) == FREE) - return null; - else if (cur != REMOVED && keyEquals(key, cur)) - return cur; - step += 2; - } - } - - public Object getEqualNoRemovals(Object key) { - Object[] keys = set; - int capacity, index; - Object cur; - if ((cur = keys[index = mix(keyHashCode(key)) % (capacity = keys.length)]) == FREE) - return null; - if (keyEquals(key, cur)) - return cur; - int bIndex = index, fIndex = index, step = 1; - while (true) { - if ((bIndex -= step) < 0) bIndex += capacity; - if ((cur = keys[bIndex]) == FREE) - return null; - else if (keyEquals(key, cur)) - return cur; - int t; - if ((t = (fIndex += step) - capacity) >= 0) fIndex = t; - if ((cur = keys[fIndex]) == FREE) - return null; - else if (keyEquals(key, cur)) - return cur; - step += 2; - } - } - - private static final Scaler minLoadInverse = Scaler.by(1.0 / MIN_LOAD); - private static final Scaler targetLoadInverse = Scaler.by(1.0 / TARGET_LOAD); - private static final Scaler maxLoad = Scaler.by(MAX_LOAD); - private static final Scaler maxLoadInverse = Scaler.by(1.0 / MAX_LOAD); - private static final Scaler growthFactor = Scaler.by(GROWTH_FACTOR); - - /** - * Computes hash table capacity for the given size and min load of this config. - * - * @param size size of the hash table to compute capacity for - * @return if the given size is non-negative, returns the least int capacity such that - * size / capacity < {@code config().getMinLoad()}, or {@code Integer.MAX_VALUE} - * if there is no such capacity. If size is negative, result is undefined. - */ - private static int maxCapacity(int size) { - return minLoadInverse.scaleUpper(size); - } - - /** - * Computes hash table capacity for the given size and max load of this config. - * - * @param size size of the hash table to compute capacity for - * @return if the given size is non-negative, returns the least int capacity such that - * size / capacity < {@code config().getMaxLoad()}, or {@code Integer.MAX_VALUE} - * if there is no such capacity. If size is negative, result is undefined. - */ - private static int minCapacity(int size) { - return maxLoadInverse.scaleUpper(size); - } - - private static int maxSize(int capacity) { - return maxLoad.scaleLower(capacity); - } - - /** - * Computes grown hash table capacity for the given capacity and growth factor of this config. - * - * @param capacity capacity of the hash table to grow - * @return if the given capacity is non-negative, returns the least int capacity - * such that |new capacity - the given capacity * {@code config().getGrowthFactor()}| < - * 1, or {@code Integer.MAX_VALUE} if there is no such capacity. - * If the given capacity is negative, result is undefined. - */ - private static int grow(int capacity) { - return growthFactor.scaleLower(capacity); - } - - /** - * Chooses lesser or greater capacity, which one is better for the given {@code size} and - * hash config. (The {@code desiredCapacity} is just precomputed - * {@code conf.targetCapacity(size)}). - * - *

Chooses the capacity which is closer to the {@code desiredCapacity} and conform min or - * max capacity bounds for the given {@code size} and hash config. - * - *

If both {@code lesserCapacity} and {@code greaterCapacity} are out of these bounds, - * {@code onFail} value is returned. - * - * @param conf the {@code HashConfigWrapper} - * @param size should be non-negative - * @param desiredCapacity precomputed {@code conf.targetCapacity(size)} - * @param lesserCapacity should be greater than the {@code size} but lesser - * than the {@code desiredCapacity} - * @param greaterCapacity should be greater than the {@code desiredCapacity} - * @param onFail the value to return if both {@code lesserCapacity} and {@code greaterCapacity} - * are lesser than min size and greater than max size respectively - * for the given hash config and size - * @return {@code lesserCapacity} or {@code greaterCapacity} - * @see #chooseBetter(HashConfigWrapper, long, long, long, long, long) - */ - private static int chooseBetter(int size, - int desiredCapacity, int lesserCapacity, int greaterCapacity, int onFail) { - assert 0 <= size; - assert size < lesserCapacity && lesserCapacity < desiredCapacity; - assert desiredCapacity < greaterCapacity; - if (greaterCapacity - desiredCapacity <= desiredCapacity - lesserCapacity && - greaterCapacity <= maxCapacity(size)) { - return greaterCapacity; - } - return lesserCapacity >= minCapacity(size) ? lesserCapacity : onFail; - } - - private static int capacity(int size, int desiredCapacity) { - int lesserCapacity, greaterCapacity; - if (desiredCapacity <= MAX_LOOKUP_CAPACITY) { - int smallTableIndex = SMALL_LOOKUP_TABLE_INDICES[desiredCapacity]; - greaterCapacity = SMALL_LOOKUP_TABLE_CAPACITIES[smallTableIndex]; - if (greaterCapacity == desiredCapacity || smallTableIndex == 0) - return greaterCapacity; - lesserCapacity = SMALL_LOOKUP_TABLE_CAPACITIES[smallTableIndex - 1]; - } - else if (desiredCapacity <= MAX_REGULAR_CHAR_CAPACITY) { - int capIndex = binarySearch(REGULAR_CHAR_CAPACITIES, (char) desiredCapacity); - if (capIndex >= 0) // desiredCapacity is found in REGULAR_CHAR_CAPACITIES - return desiredCapacity; - capIndex = ~capIndex; - lesserCapacity = capIndex > 0 ? - (int) REGULAR_CHAR_CAPACITIES[capIndex - 1] : MAX_LOOKUP_CAPACITY; - greaterCapacity = REGULAR_CHAR_CAPACITIES[capIndex]; - } - else if (desiredCapacity <= MAX_REGULAR_INT_CAPACITY) { - int capIndex = binarySearch(REGULAR_INT_CAPACITIES, desiredCapacity); - if (capIndex >= 0) // desiredCapacity is found in REGULAR_INT_CAPACITIES - return desiredCapacity; - capIndex = ~capIndex; - lesserCapacity = capIndex > 0 ? - REGULAR_INT_CAPACITIES[capIndex - 1] : MAX_REGULAR_CHAR_CAPACITY; - greaterCapacity = REGULAR_INT_CAPACITIES[capIndex]; - } - else { - // Since size could be virtual (expected), don't prematurely throw - // HashOverflowException. If sizes near to Integer.MAX_VALUE is the case, - // version accepting long size should be used. - return MAX_INT_CAPACITY; - } - return chooseBetter(size, desiredCapacity, lesserCapacity, greaterCapacity, - greaterCapacity); - } - - /** For grow rehash. */ - private static int nearestGreaterCapacity(int desiredCapacity, int currentSize) { - assert currentSize >= 0 : "currentSize must be non-negative"; - if (desiredCapacity <= MAX_LOOKUP_CAPACITY) - return SMALL_LOOKUP_TABLE_CAPACITIES[SMALL_LOOKUP_TABLE_INDICES[desiredCapacity]]; - if (desiredCapacity <= MAX_REGULAR_CHAR_CAPACITY) { - int capIndex = binarySearch(REGULAR_CHAR_CAPACITIES, (char) desiredCapacity); - // capIndex >= 0 => desiredCapacity IS a regular capacity - return capIndex < 0 ? REGULAR_CHAR_CAPACITIES[~capIndex] : desiredCapacity; - } - final boolean simpleArrays = true; - if (desiredCapacity <= MAX_REGULAR_INT_CAPACITY) { - int capIndex = binarySearch(REGULAR_INT_CAPACITIES, desiredCapacity); - return capIndex < 0 ? REGULAR_INT_CAPACITIES[~capIndex] : desiredCapacity; - } - int maxCapacity = MAX_INT_CAPACITY; - // overflow-aware - if (currentSize - maxCapacity < 0) - return maxCapacity; - if (simpleArrays && currentSize - Integer.MAX_VALUE < 0) { - // Integer.MAX_VALUE is also a qHash prime, but likely will cause OutOfMemoryError - return Integer.MAX_VALUE; - } else { - // QHash must have at least 1 free slot - throw new CHRHashOverflowException(); - } - } - - private static final char[] SMALL_LOOKUP_TABLE_CAPACITIES = new char[] { - 7, 11, 19, 23, 31, 43, 47, 59, 67, 71, - 79, 83, 103, 107, 127, 131, 139, 151, 163, 167, - 179, 191, 199, 211, 223, 227, 239, 251, 263, 271, - 283, 307, 311, 331, 347, 359, 367, 379, 383, 419, - 431, 439, 443, 463, 467, 479, 487, 491, 499, 503, - 523, 547, 563, 571, 587, 599, 607, 619, 631, 643, - 647, 659, 683, 691, 719, 727, 739, 743, 751, 787, - 811, 823, 827, 839, 859, 863, 883, 887, 907, 911, - 919, 947, 967, 971, 983, 991, 1019 - }; - - private static final byte[] SMALL_LOOKUP_TABLE_INDICES = new byte[] { - 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, - 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, - 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, - 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, - 5, 5, 5, 5, 6, 6, 6, 6, 7, 7, - 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, - 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, - 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, - 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, - 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, - 12, 12, 12, 12, 13, 13, 13, 13, 14, 14, - 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, - 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, - 15, 15, 16, 16, 16, 16, 16, 16, 16, 16, - 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, - 17, 17, 18, 18, 18, 18, 18, 18, 18, 18, - 18, 18, 18, 18, 19, 19, 19, 19, 20, 20, - 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, - 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, - 21, 21, 22, 22, 22, 22, 22, 22, 22, 22, - 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, - 23, 23, 24, 24, 24, 24, 24, 24, 24, 24, - 24, 24, 24, 24, 25, 25, 25, 25, 26, 26, - 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, - 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, - 27, 27, 28, 28, 28, 28, 28, 28, 28, 28, - 28, 28, 28, 28, 29, 29, 29, 29, 29, 29, - 29, 29, 30, 30, 30, 30, 30, 30, 30, 30, - 30, 30, 30, 30, 31, 31, 31, 31, 31, 31, - 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, - 31, 31, 31, 31, 31, 31, 31, 31, 32, 32, - 32, 32, 33, 33, 33, 33, 33, 33, 33, 33, - 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, - 33, 33, 34, 34, 34, 34, 34, 34, 34, 34, - 34, 34, 34, 34, 34, 34, 34, 34, 35, 35, - 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, - 36, 36, 36, 36, 36, 36, 36, 36, 37, 37, - 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, - 38, 38, 38, 38, 39, 39, 39, 39, 39, 39, - 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, - 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, - 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, - 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, - 40, 40, 41, 41, 41, 41, 41, 41, 41, 41, - 42, 42, 42, 42, 43, 43, 43, 43, 43, 43, - 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, - 43, 43, 43, 43, 44, 44, 44, 44, 45, 45, - 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, - 46, 46, 46, 46, 46, 46, 46, 46, 47, 47, - 47, 47, 48, 48, 48, 48, 48, 48, 48, 48, - 49, 49, 49, 49, 50, 50, 50, 50, 50, 50, - 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, - 50, 50, 50, 50, 51, 51, 51, 51, 51, 51, - 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, - 51, 51, 51, 51, 51, 51, 51, 51, 52, 52, - 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, - 52, 52, 52, 52, 53, 53, 53, 53, 53, 53, - 53, 53, 54, 54, 54, 54, 54, 54, 54, 54, - 54, 54, 54, 54, 54, 54, 54, 54, 55, 55, - 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, - 56, 56, 56, 56, 56, 56, 56, 56, 57, 57, - 57, 57, 57, 57, 57, 57, 57, 57, 57, 57, - 58, 58, 58, 58, 58, 58, 58, 58, 58, 58, - 58, 58, 59, 59, 59, 59, 59, 59, 59, 59, - 59, 59, 59, 59, 60, 60, 60, 60, 61, 61, - 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, - 62, 62, 62, 62, 62, 62, 62, 62, 62, 62, - 62, 62, 62, 62, 62, 62, 62, 62, 62, 62, - 62, 62, 62, 62, 63, 63, 63, 63, 63, 63, - 63, 63, 64, 64, 64, 64, 64, 64, 64, 64, - 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, - 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, - 65, 65, 65, 65, 65, 65, 65, 65, 66, 66, - 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, - 67, 67, 67, 67, 68, 68, 68, 68, 68, 68, - 68, 68, 69, 69, 69, 69, 69, 69, 69, 69, - 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, - 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, - 69, 69, 69, 69, 69, 69, 69, 69, 70, 70, - 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, - 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, - 70, 70, 71, 71, 71, 71, 71, 71, 71, 71, - 71, 71, 71, 71, 72, 72, 72, 72, 73, 73, - 73, 73, 73, 73, 73, 73, 73, 73, 73, 73, - 74, 74, 74, 74, 74, 74, 74, 74, 74, 74, - 74, 74, 74, 74, 74, 74, 74, 74, 74, 74, - 75, 75, 75, 75, 76, 76, 76, 76, 76, 76, - 76, 76, 76, 76, 76, 76, 76, 76, 76, 76, - 76, 76, 76, 76, 77, 77, 77, 77, 78, 78, - 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, - 78, 78, 78, 78, 78, 78, 78, 78, 79, 79, - 79, 79, 80, 80, 80, 80, 80, 80, 80, 80, - 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, - 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, - 81, 81, 81, 81, 81, 81, 81, 81, 82, 82, - 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, - 82, 82, 82, 82, 82, 82, 82, 82, 83, 83, - 83, 83, 84, 84, 84, 84, 84, 84, 84, 84, - 84, 84, 84, 84, 85, 85, 85, 85, 85, 85, - 85, 85, 86, 86, 86, 86, 86, 86, 86, 86, - 86, 86, 86, 86, 86, 86, 86, 86, 86, 86, - 86, 86, 86, 86, 86, 86, 86, 86, 86, 86 - }; - - /** Compile-time constant expression */ - private static final int MAX_LOOKUP_CAPACITY = 1019; - static { - if (MAX_LOOKUP_CAPACITY != - SMALL_LOOKUP_TABLE_CAPACITIES[SMALL_LOOKUP_TABLE_CAPACITIES.length - 1]) { - throw new AssertionError(); - } - } - - /** - * These capacities and other regular capacities from {@link #REGULAR_INT_CAPACITIES} - * and {@link #REGULAR_LONG_CAPACITIES} arrays are generated using a single command - * {@code $ java QHashCapacities 40 0.005}, i. e. trying to keep 0.5% max difference between - * neighbouring capacities. - * - * @see {@link #main(String[])} - * @see {@link #generateRegularCapacities(long, double)} - */ - private static final char[] REGULAR_CHAR_CAPACITIES = new char[] { - 1031, 1039, - 1051, 1063, 1087, 1091, 1103, 1123, 1151, 1163, 1171, 1187, - 1223, 1231, 1259, 1279, 1283, 1291, 1303, 1307, 1319, 1327, - 1367, 1399, 1423, 1427, 1439, 1447, 1451, 1459, 1471, 1483, - 1487, 1499, 1511, 1523, 1531, 1543, 1559, 1567, 1571, 1579, - 1583, 1607, 1619, 1627, 1663, 1667, 1699, 1723, 1747, 1759, - 1783, 1787, 1811, 1823, 1831, 1847, 1867, 1871, 1879, 1907, - 1931, 1951, 1979, 1987, 1999, 2003, 2011, 2027, 2039, 2063, - 2083, 2087, 2099, 2111, 2131, 2143, 2179, 2203, 2207, 2239, - 2243, 2251, 2267, 2287, 2311, 2339, 2347, 2351, 2371, 2383, - 2399, 2411, 2423, 2447, 2459, 2467, 2503, 2531, 2539, 2543, - 2551, 2579, 2591, 2647, 2659, 2663, 2671, 2683, 2687, 2699, - 2707, 2711, 2719, 2731, 2767, 2791, 2803, 2819, 2843, 2851, - 2879, 2887, 2903, 2927, 2939, 2963, 2971, 2999, 3011, 3019, - 3023, 3067, 3079, 3083, 3119, 3163, 3167, 3187, 3191, 3203, - 3251, 3259, 3271, 3299, 3307, 3319, 3323, 3331, 3343, 3347, - 3359, 3371, 3391, 3407, 3463, 3467, 3491, 3499, 3511, 3527, - 3539, 3547, 3559, 3571, 3583, 3607, 3623, 3631, 3643, 3659, - 3671, 3691, 3719, 3727, 3739, 3767, 3779, 3803, 3823, 3847, - 3851, 3863, 3907, 3911, 3919, 3923, 3931, 3943, 3947, 3967, - 4003, 4007, 4019, 4027, 4051, 4079, 4091, 4099, 4111, 4127, - 4139, 4159, 4211, 4219, 4231, 4243, 4259, 4271, 4283, 4327, - 4339, 4363, 4391, 4423, 4447, 4451, 4463, 4483, 4507, 4519, - 4523, 4547, 4567, 4583, 4591, 4603, 4639, 4643, 4651, 4663, - 4679, 4691, 4703, 4723, 4751, 4759, 4783, 4787, 4799, 4831, - 4871, 4903, 4919, 4931, 4943, 4951, 4967, 4987, 4999, 5003, - 5011, 5023, 5039, 5051, 5059, 5087, 5099, 5107, 5119, 5147, - 5167, 5171, 5179, 5227, 5231, 5279, 5303, 5323, 5347, 5351, - 5387, 5399, 5407, 5419, 5431, 5443, 5471, 5479, 5483, 5503, - 5507, 5519, 5527, 5531, 5563, 5591, 5623, 5639, 5647, 5651, - 5659, 5683, 5711, 5743, 5779, 5783, 5791, 5807, 5827, 5839, - 5843, 5851, 5867, 5879, 5903, 5923, 5927, 5939, 5987, 6007, - 6011, 6043, 6047, 6067, 6079, 6091, 6131, 6143, 6151, 6163, - 6199, 6203, 6211, 6247, 6263, 6271, 6287, 6299, 6311, 6323, - 6343, 6359, 6367, 6379, 6427, 6451, 6491, 6547, 6551, 6563, - 6571, 6599, 6607, 6619, 6659, 6679, 6691, 6703, 6719, 6763, - 6779, 6791, 6803, 6823, 6827, 6863, 6871, 6883, 6899, 6907, - 6911, 6947, 6959, 6967, 6971, 6983, 6991, 7019, 7027, 7039, - 7043, 7079, 7103, 7127, 7151, 7159, 7187, 7207, 7211, 7219, - 7243, 7247, 7283, 7307, 7331, 7351, 7411, 7451, 7459, 7487, - 7499, 7507, 7523, 7547, 7559, 7583, 7591, 7603, 7607, 7639, - 7643, 7687, 7691, 7699, 7703, 7723, 7727, 7759, 7823, 7867, - 7879, 7883, 7907, 7919, 7927, 7951, 7963, 8011, 8039, 8059, - 8087, 8111, 8123, 8147, 8167, 8171, 8179, 8191, 8219, 8231, - 8243, 8263, 8287, 8291, 8311, 8363, 8387, 8419, 8423, 8431, - 8443, 8447, 8467, 8527, 8539, 8543, 8563, 8599, 8623, 8627, - 8647, 8663, 8699, 8707, 8719, 8731, 8747, 8779, 8783, 8803, - 8807, 8819, 8831, 8839, 8863, 8867, 8887, 8923, 8951, 8963, - 8971, 8999, 9007, 9011, 9043, 9059, 9067, 9091, 9103, 9127, - 9151, 9187, 9199, 9203, 9227, 9239, 9283, 9311, 9319, 9323, - 9343, 9371, 9391, 9403, 9419, 9431, 9439, 9463, 9467, 9479, - 9491, 9511, 9539, 9547, 9551, 9587, 9619, 9623, 9631, 9643, - 9679, 9719, 9739, 9743, 9767, 9787, 9791, 9803, 9811, 9839, - 9851, 9859, 9871, 9883, 9887, 9907, 9923, 9931, 9967, 10007, - 10039, 10067, 10079, 10091, 10099, 10103, 10111, 10139, 10151, 10159, - 10163, 10211, 10223, 10243, 10247, 10259, 10267, 10271, 10303, 10331, - 10343, 10391, 10399, 10427, 10459, 10463, 10487, 10499, 10531, 10559, - 10567, 10607, 10627, 10631, 10639, 10651, 10663, 10667, 10687, 10691, - 10711, 10723, 10739, 10771, 10799, 10831, 10847, 10859, 10867, 10883, - 10891, 10903, 10939, 10979, 10987, 11003, 11027, 11047, 11059, 11071, - 11083, 11087, 11119, 11131, 11159, 11171, 11239, 11243, 11251, 11279, - 11287, 11299, 11311, 11351, 11383, 11399, 11411, 11423, 11443, 11447, - 11467, 11471, 11483, 11491, 11503, 11519, 11527, 11551, 11579, 11587, - 11699, 11719, 11731, 11743, 11779, 11783, 11807, 11827, 11831, 11839, - 11863, 11867, 11887, 11903, 11923, 11927, 11939, 11959, 11971, 11987, - 12007, 12011, 12043, 12071, 12107, 12119, 12143, 12163, 12203, 12211, - 12227, 12239, 12251, 12263, 12323, 12343, 12347, 12379, 12391, 12451, - 12479, 12487, 12491, 12503, 12511, 12527, 12539, 12547, 12583, 12611, - 12619, 12647, 12659, 12671, 12703, 12739, 12743, 12763, 12791, 12799, - 12823, 12899, 12919, 12979, 13043, 13099, 13159, 13219, 13259, 13291, - 13339, 13399, 13463, 13523, 13567, 13619, 13679, 13711, 13763, 13831, - 13879, 13931, 13999, 14051, 14083, 14143, 14207, 14243, 14303, 14323, - 14387, 14431, 14503, 14563, 14627, 14683, 14723, 14779, 14851, 14923, - 14983, 15031, 15083, 15131, 15187, 15259, 15307, 15383, 15439, 15511, - 15551, 15607, 15667, 15727, 15787, 15859, 15919, 15991, 16063, 16111, - 16187, 16267, 16339, 16411, 16427, 16487, 16547, 16619, 16691, 16747, - 16811, 16879, 16963, 17047, 17123, 17207, 17291, 17359, 17443, 17519, - 17579, 17659, 17747, 17807, 17891, 17959, 18043, 18119, 18199, 18287, - 18367, 18427, 18503, 18583, 18671, 18719, 18787, 18839, 18899, 18959, - 19051, 19139, 19231, 19319, 19379, 19423, 19507, 19603, 19687, 19751, - 19843, 19927, 20023, 20123, 20219, 20287, 20347, 20443, 20543, 20611, - 20707, 20807, 20879, 20939, 21011, 21107, 21179, 21283, 21379, 21467, - 21559, 21647, 21739, 21839, 21943, 22039, 22147, 22247, 22343, 22447, - 22531, 22639, 22751, 22859, 22943, 23027, 23131, 23227, 23339, 23447, - 23563, 23663, 23767, 23879, 23971, 24043, 24151, 24239, 24359, 24379, - 24499, 24571, 24683, 24799, 24907, 25031, 25111, 25219, 25339, 25463, - 25579, 25679, 25799, 25903, 25999, 26099, 26227, 26339, 26407, 26539, - 26627, 26759, 26879, 27011, 27143, 27271, 27407, 27527, 27631, 27751, - 27883, 28019, 28151, 28279, 28387, 28499, 28619, 28751, 28879, 29023, - 29167, 29303, 29443, 29587, 29723, 29851, 29983, 30119, 30259, 30391, - 30539, 30671, 30803, 30931, 31079, 31231, 31387, 31543, 31699, 31847, - 31963, 32099, 32251, 32371, 32531, 32687, 32839, 32887, 33023, 33179, - 33331, 33479, 33647, 33811, 33967, 34123, 34231, 34403, 34543, 34703, - 34871, 35023, 35171, 35339, 35507, 35671, 35803, 35951, 36131, 36299, - 36451, 36587, 36767, 36943, 37123, 37307, 37447, 37619, 37799, 37987, - 38167, 38351, 38543, 38671, 38851, 39043, 39227, 39419, 39607, 39779, - 39971, 40151, 40343, 40499, 40699, 40847, 41039, 41243, 41443, 41647, - 41843, 41983, 42179, 42359, 42571, 42743, 42943, 43151, 43331, 43543, - 43759, 43943, 44131, 44351, 44563, 44771, 44959, 45179, 45403, 45599, - 45823, 46051, 46271, 46471, 46687, 46919, 47111, 47339, 47563, 47791, - 48023, 48259, 48491, 48731, 48947, 49171, 49391, 49627, 49871, 50111, - 50359, 50587, 50839, 51031, 51263, 51511, 51767, 52027, 52259, 52511, - 52747, 53003, 53267, 53527, 53791, 54059, 54311, 54583, 54851, 55079, - 55331, 55579, 55843, 56123, 56383, 56659, 56911, 57191, 57467, 57719, - 57991, 58271, 58543, 58831, 59107, 59387, 59659, 59951, 60251, 60527, - 60811, 61091, 61379, 61687, 61991, 62299, 62591, 62903, 63179, 63487, - 63803, 64123, 64439, 64747, 65063, 65371 - }; - - /** Compile-time constant expression */ - private static final int MAX_REGULAR_CHAR_CAPACITY = 65371; - static { - if (MAX_REGULAR_CHAR_CAPACITY != - REGULAR_CHAR_CAPACITIES[REGULAR_CHAR_CAPACITIES.length - 1]) - throw new AssertionError(); - } - - - private static final int[] REGULAR_INT_CAPACITIES = new int[] { - 65687, 65827, 66103, 66431, - 66751, 67079, 67391, 67699, 68023, 68351, 68687, 69031, 69371, 69691, - 69991, 70327, 70627, 70979, 71327, 71647, 71947, 72271, 72623, 72931, - 73291, 73643, 73999, 74323, 74687, 75011, 75367, 75731, 76091, 76463, - 76819, 77167, 77527, 77899, 78259, 78607, 78979, 79319, 79687, 80039, - 80407, 80803, 81203, 81611, 82003, 82387, 82787, 83203, 83563, 83891, - 84299, 84691, 85103, 85523, 85931, 86351, 86783, 87211, 87643, 88079, - 88499, 88919, 89363, 89759, 90187, 90631, 91079, 91499, 91939, 92399, - 92863, 93307, 93763, 94219, 94687, 95131, 95603, 96059, 96527, 96979, - 97459, 97919, 98387, 98867, 99347, 99823, 100291, 100787, 101267, 101719, - 102191, 102667, 103171, 103687, 104207, 104707, 105227, 105751, 106279, 106787, - 107323, 107827, 108343, 108883, 109423, 109943, 110479, 111031, 111539, 112067, - 112603, 113159, 113719, 114259, 114799, 115363, 115931, 116491, 117071, 117659, - 118247, 118831, 119419, 119963, 120539, 121123, 121687, 122263, 122867, 123479, - 124067, 124643, 125243, 125863, 126443, 127031, 127607, 128239, 128879, 129499, - 130147, 130783, 131363, 131543, 132199, 132859, 133519, 134171, 134807, 135463, - 136139, 136811, 137491, 138179, 138863, 139511, 140191, 140891, 141587, 142271, - 142979, 143687, 144379, 145091, 145799, 146519, 147211, 147919, 148627, 149371, - 150107, 150847, 151603, 152363, 153107, 153871, 154619, 155371, 156119, 156887, - 157667, 158443, 159223, 160019, 160807, 161611, 162419, 163211, 164023, 164839, - 165667, 166487, 167311, 168151, 168991, 169823, 170647, 171491, 172331, 173183, - 174047, 174907, 175783, 176651, 177511, 178403, 179287, 180179, 181003, 181871, - 182779, 183691, 184607, 185519, 186451, 187367, 188291, 189199, 190147, 191047, - 192007, 192971, 193939, 194911, 195887, 196871, 197831, 198811, 199783, 200771, - 201743, 202751, 203767, 204751, 205759, 206779, 207799, 208843, 209887, 210907, - 211927, 212987, 214003, 215051, 216119, 217199, 218279, 219371, 220447, 221539, - 222587, 223667, 224683, 225751, 226819, 227947, 228983, 230123, 231271, 232391, - 233551, 234659, 235783, 236947, 238099, 239287, 240479, 241603, 242807, 244003, - 245171, 246371, 247607, 248851, 250091, 251323, 252559, 253787, 255043, 256307, - 257591, 258871, 260171, 261427, 262723, 263951, 265271, 266587, 267887, 269219, - 270563, 271919, 273271, 274579, 275911, 277223, 278591, 279967, 281363, 282767, - 284159, 285559, 286987, 288403, 289843, 291299, 292759, 294223, 295699, 297151, - 298631, 300119, 301579, 303091, 304559, 306083, 307583, 309091, 310643, 312199, - 313679, 315247, 316819, 318403, 319967, 321547, 323123, 324743, 326351, 327967, - 329587, 331231, 332887, 334547, 336199, 337859, 339467, 341171, 342871, 344587, - 346303, 348011, 349759, 351503, 353263, 355027, 356803, 358591, 360391, 362143, - 363959, 365779, 367603, 369407, 371227, 373091, 374939, 376787, 378667, 380563, - 382463, 384359, 386279, 388211, 390151, 392099, 394063, 396031, 398011, 399979, - 401939, 403951, 405947, 407923, 409967, 412019, 414083, 416147, 418199, 420263, - 422311, 424423, 426527, 428639, 430783, 432931, 435103, 437263, 439459, 441667, - 443867, 446087, 448303, 450479, 452731, 454991, 457267, 459523, 461803, 464119, - 466423, 468739, 471091, 473443, 475807, 478171, 480563, 482947, 485347, 487783, - 490207, 492647, 495119, 497587, 500083, 502543, 505067, 507599, 510127, 512663, - 515191, 517739, 520339, 522947, 525571, 528163, 530807, 533447, 536111, 538799, - 541483, 544199, 546919, 549623, 552379, 555143, 557927, 560719, 563503, 566311, - 569083, 571939, 574799, 577627, 580471, 583367, 586291, 589187, 592139, 595087, - 598051, 601031, 604031, 607043, 610063, 613099, 616171, 619247, 622331, 625451, - 628583, 631711, 634859, 638023, 641227, 644431, 647659, 650911, 654163, 657431, - 660727, 664043, 667363, 670711, 674059, 677387, 680783, 684191, 687623, 691051, - 694511, 697979, 701479, 704999, 708527, 712067, 715639, 719179, 722783, 726367, - 729991, 733651, 737327, 741007, 744727, 748463, 752183, 755959, 759719, 763523, - 767323, 771143, 775007, 778871, 782783, 786659, 790567, 794531, 798487, 802471, - 806503, 810539, 814579, 818659, 822763, 826879, 831023, 835123, 839303, 843503, - 847727, 851971, 856187, 860479, 864803, 869119, 873463, 877843, 882239, 886651, - 891103, 895571, 900019, 904531, 909071, 913639, 918199, 922807, 927403, 931999, - 936679, 941383, 946091, 950839, 955607, 960383, 965179, 970027, 974891, 979787, - 984703, 989623, 994559, 999491, 1004483, 1009483, 1014547, 1019639, 1024703, 1029823, - 1034983, 1040167, 1045391, 1050631, 1054171, 1059439, 1064743, 1070087, 1075463, 1080847, - 1086259, 1091711, 1097179, 1102691, 1108223, 1113787, 1119359, 1124983, 1130627, 1136299, - 1142003, 1147739, 1153487, 1159283, 1165103, 1170947, 1176827, 1182739, 1188667, 1194631, - 1200607, 1206619, 1212671, 1218727, 1224823, 1230967, 1237139, 1243343, 1249559, 1255811, - 1262119, 1268447, 1274803, 1281187, 1287623, 1294087, 1300571, 1307063, 1313623, 1320191, - 1326791, 1333411, 1340107, 1346827, 1353551, 1360327, 1367159, 1374007, 1380887, 1387783, - 1394747, 1401739, 1408763, 1415803, 1422899, 1430027, 1437199, 1444411, 1451603, 1458871, - 1466147, 1473503, 1480903, 1488343, 1495751, 1503247, 1510759, 1518343, 1525963, 1533583, - 1541251, 1548947, 1556719, 1564499, 1572359, 1580251, 1588159, 1596107, 1604123, 1612183, - 1620247, 1628383, 1636543, 1644691, 1652947, 1661243, 1669543, 1677899, 1686319, 1694767, - 1703267, 1711799, 1720399, 1729043, 1737691, 1746419, 1755179, 1763959, 1772819, 1781699, - 1790599, 1799591, 1808627, 1817663, 1826771, 1835923, 1845119, 1854379, 1863671, 1873019, - 1882403, 1891859, 1901359, 1910891, 1920487, 1930099, 1939787, 1949527, 1959283, 1969111, - 1978927, 1988839, 1998827, 2008807, 2018899, 2029003, 2039179, 2049419, 2059711, 2069959, - 2080339, 2090771, 2101259, 2106551, 2117119, 2127739, 2138387, 2149127, 2159923, 2170771, - 2181671, 2192623, 2203631, 2214691, 2225819, 2236987, 2248223, 2259503, 2270803, 2282207, - 2293567, 2305091, 2316667, 2328307, 2340007, 2351731, 2363507, 2375327, 2387243, 2399207, - 2411243, 2423359, 2435519, 2447743, 2460043, 2472403, 2484803, 2497259, 2509807, 2522407, - 2535059, 2547791, 2560583, 2573423, 2586343, 2599327, 2612383, 2625487, 2638651, 2651899, - 2665199, 2678551, 2692003, 2705519, 2719111, 2732759, 2746423, 2760223, 2774071, 2788007, - 2802011, 2816059, 2830151, 2844367, 2858623, 2872967, 2887363, 2901839, 2916383, 2930999, - 2945707, 2960467, 2975339, 2990279, 3005267, 3020351, 3035507, 3050759, 3066067, 3081443, - 3096911, 3112391, 3127979, 3143671, 3159439, 3175259, 3191099, 3207119, 3223223, 3239419, - 3255683, 3272039, 3288479, 3304991, 3321583, 3338263, 3355031, 3371867, 3388799, 3405791, - 3422807, 3439987, 3457271, 3474599, 3492043, 3509587, 3527219, 3544907, 3562711, 3580579, - 3598519, 3616583, 3634727, 3652991, 3671347, 3689771, 3708283, 3726911, 3745631, 3764443, - 3783343, 3802283, 3821327, 3840479, 3859759, 3879023, 3898483, 3918067, 3937751, 3957479, - 3977339, 3997307, 4017359, 4037531, 4057799, 4078187, 4098659, 4119239, 4139923, 4160711, - 4181579, 4202567, 4210807, 4231943, 4253203, 4274551, 4295999, 4317571, 4339207, 4361003, - 4382879, 4404899, 4426999, 4449227, 4471559, 4494019, 4516571, 4539247, 4562039, 4584959, - 4607987, 4631131, 4654399, 4677779, 4701239, 4724831, 4748563, 4772399, 4796371, 4820443, - 4844659, 4868999, 4893419, 4918007, 4942687, 4967491, 4992419, 5017447, 5042647, 5067967, - 5093423, 5119007, 5144707, 5170519, 5196467, 5222579, 5248787, 5275159, 5301623, 5328251, - 5355019, 5381927, 5408947, 5436127, 5463391, 5490787, 5518351, 5546071, 5573927, 5601907, - 5630039, 5658307, 5686739, 5715299, 5743987, 5772847, 5801843, 5830963, 5860243, 5889683, - 5919271, 5948939, 5978831, 6008867, 6038999, 6069311, 6099767, 6130391, 6161063, 6192023, - 6223099, 6254359, 6285787, 6317327, 6349043, 6380939, 6412999, 6445223, 6477599, 6510107, - 6542803, 6575671, 6608639, 6641839, 6675211, 6708739, 6742363, 6776207, 6810247, 6844447, - 6878803, 6913351, 6948079, 6982907, 7017979, 7053223, 7088611, 7124231, 7159987, 7195963, - 7232111, 7268423, 7304939, 7341647, 7378531, 7415599, 7452859, 7490303, 7527911, 7565627, - 7603627, 7641791, 7680191, 7718771, 7757543, 7796491, 7835647, 7874983, 7914551, 7954319, - 7994279, 8034451, 8074811, 8115383, 8156147, 8197099, 8238247, 8279627, 8321227, 8363023, - 8405003, 8419511, 8461787, 8504291, 8546999, 8589923, 8633063, 8676431, 8719987, 8763803, - 8807803, 8852059, 8896483, 8941171, 8986091, 9031207, 9076579, 9122143, 9167923, 9213979, - 9260263, 9306779, 9353483, 9400463, 9447667, 9495139, 9542843, 9590699, 9638891, 9687323, - 9735991, 9784903, 9834047, 9883463, 9933059, 9982939, 10033063, 10083443, 10134107, 10185011, - 10236179, 10287587, 10339267, 10391219, 10443431, 10495907, 10548623, 10601627, 10654871, 10708403, - 10762211, 10816271, 10870619, 10925227, 10980059, 11035223, 11090627, 11146279, 11202251, 11258483, - 11314987, 11371807, 11428931, 11486347, 11544047, 11602043, 11660339, 11718923, 11777791, 11836963, - 11896427, 11956199, 12016187, 12076567, 12137183, 12198139, 12259399, 12320983, 12382823, 12445039, - 12507559, 12570403, 12633559, 12697039, 12760843, 12824899, 12889339, 12954079, 13019143, 13084531, - 13150279, 13216331, 13282723, 13349411, 13416463, 13483751, 13551467, 13619563, 13687987, 13756739, - 13825831, 13895291, 13965103, 14035279, 14105759, 14176619, 14247847, 14319419, 14391359, 14463667, - 14536307, 14609351, 14682719, 14756491, 14830603, 14905123, 14980019, 15055259, 15130903, 15206899, - 15283291, 15360071, 15437239, 15514783, 15592739, 15671087, 15749819, 15828947, 15908423, 15988363, - 16068691, 16149431, 16230491, 16312039, 16394003, 16476371, 16559159, 16642343, 16725971, 16810007, - 16836587, 16921183, 17006167, 17091623, 17177507, 17263783, 17350519, 17437691, 17525243, 17613307, - 17701807, 17790739, 17880067, 17969911, 18060187, 18150911, 18242083, 18333703, 18425819, 18518363, - 18611419, 18704927, 18798907, 18893351, 18988267, 19083679, 19179551, 19275847, 19372699, 19470019, - 19567811, 19666123, 19764947, 19864267, 19964059, 20064371, 20165143, 20266391, 20368211, 20470547, - 20573411, 20676791, 20780659, 20885071, 20989967, 21095423, 21201347, 21307859, 21414923, 21522511, - 21630659, 21739351, 21848579, 21958367, 22068647, 22179511, 22290943, 22402951, 22515511, 22628651, - 22742303, 22856527, 22971259, 23086667, 23202643, 23319227, 23436407, 23554099, 23672459, 23791399, - 23910947, 24031087, 24151807, 24273163, 24395023, 24517607, 24640799, 24764611, 24889043, 25014071, - 25139767, 25266071, 25393031, 25520623, 25648867, 25777639, 25907143, 26037299, 26168099, 26299571, - 26431723, 26564507, 26697991, 26832139, 26966963, 27102419, 27238559, 27375419, 27512951, 27651191, - 27790127, 27929723, 28070071, 28211123, 28352887, 28495351, 28638539, 28782419, 28927039, 29072399, - 29218403, 29365207, 29512739, 29661043, 29810023, 29959819, 30110347, 30261643, 30413707, 30566519, - 30720119, 30874483, 31029587, 31185443, 31342139, 31499599, 31657783, 31816847, 31976723, 32137403, - 32298863, 32461159, 32624239, 32788099, 32952839, 33118391, 33284803, 33452047, 33619979, 33670103, - 33839243, 34009279, 34180163, 34351879, 34524491, 34697951, 34872283, 35047483, 35223599, 35400583, - 35578471, 35757247, 35936903, 36117467, 36298943, 36481343, 36664651, 36848891, 37033987, 37220047, - 37407059, 37595027, 37783927, 37973783, 38164571, 38356327, 38548999, 38742707, 38937319, 39132979, - 39329627, 39527123, 39725723, 39925339, 40125947, 40327571, 40530199, 40733867, 40938523, 41144203, - 41350943, 41558687, 41767483, 41977367, 42188287, 42400243, 42613303, 42827431, 43042631, 43258907, - 43476287, 43694747, 43914307, 44134931, 44356639, 44579503, 44803511, 45028639, 45254899, 45482291, - 45710831, 45940523, 46171351, 46403347, 46636519, 46870867, 47106379, 47343083, 47580983, 47820079, - 48060359, 48301867, 48544583, 48788503, 49033651, 49280003, 49527619, 49776479, 50026607, 50277979, - 50530619, 50784523, 51039683, 51296159, 51553903, 51812927, 52073279, 52334951, 52597891, 52862143, - 53127779, 53394727, 53663039, 53932651, 54203659, 54476027, 54749771, 55024859, 55301359, 55579243, - 55858459, 56139079, 56421151, 56704667, 56989571, 57275927, 57563699, 57852943, 58143583, 58435703, - 58729331, 59024443, 59321039, 59619127, 59918687, 60219779, 60522379, 60826511, 61132163, 61439239, - 61747963, 62058247, 62370079, 62683463, 62998451, 63314959, 63633079, 63952799, 64274159, 64597111, - 64921699, 65247907, 65575747, 65905267, 66236431, 66569267, 66903779, 67239967, 67338643, 67677007, - 68017067, 68358739, 68702143, 69047299, 69394219, 69742919, 70093327, 70445519, 70799507, 71155267, - 71512787, 71872127, 72233279, 72596243, 72961039, 73327651, 73696111, 74066411, 74438591, 74812651, - 75188591, 75566347, 75946067, 76327703, 76711231, 77096707, 77484083, 77873431, 78264727, 78657983, - 79053187, 79450363, 79849543, 80250763, 80654027, 81059287, 81466579, 81875951, 82287379, 82700791, - 83116367, 83534023, 83953763, 84375623, 84799619, 85225739, 85653947, 86084287, 86516863, 86951603, - 87388531, 87827647, 88268987, 88712527, 89158283, 89606287, 90056467, 90508987, 90963799, 91420867, - 91880263, 92341967, 92805983, 93272327, 93741019, 94212031, 94685419, 95161219, 95639387, 96119927, - 96602903, 97088339, 97576163, 98066491, 98559259, 99054523, 99552227, 100052467, 100555243, 101060539, - 101568287, 102078679, 102591631, 103107119, 103625239, 104145887, 104669179, 105195127, 105723743, 106254899, - 106788827, 107325451, 107864747, 108406763, 108951503, 109498943, 110049059, 110602031, 111157807, 111716383, - 112277699, 112841863, 113408767, 113978507, 114551263, 115126883, 115705351, 116286743, 116871091, 117458347, - 118048547, 118641739, 119237927, 119837059, 120439243, 121044431, 121652599, 122263903, 122878211, 123495683, - 124116191, 124739887, 125366567, 125996539, 126629663, 127265951, 127905443, 128548139, 129194083, 129843299, - 130495763, 131151491, 131810491, 132472831, 133138519, 133807547, 134479879, 134673607, 135350351, 136030471, - 136714027, 137400979, 138091427, 138785203, 139482599, 140183503, 140887919, 141595859, 142307287, 143022359, - 143741047, 144463339, 145189259, 145918711, 146651903, 147388823, 148129447, 148873787, 149621891, 150373759, - 151129399, 151888843, 152652103, 153419159, 154190087, 154964867, 155743583, 156526207, 157312763, 158103259, - 158897743, 159696211, 160498699, 161305211, 162115787, 162930419, 163749119, 164571971, 165398927, 166230007, - 167065303, 167904791, 168748499, 169596463, 170448683, 171305207, 172165991, 173031143, 173900563, 174774427, - 175652671, 176535311, 177422411, 178313951, 179209991, 180110471, 181015519, 181925111, 182839303, 183758039, - 184681411, 185609447, 186542099, 187479491, 188421539, 189368371, 190319959, 191276291, 192237431, 193203431, - 194174191, 195149939, 196130579, 197116159, 198106663, 199102151, 200102579, 201108043, 202118563, 203134123, - 204154859, 205180751, 206211799, 207248011, 208289351, 209336027, 210387907, 211445131, 212507651, 213575503, - 214648699, 215727247, 216811267, 217900763, 218995739, 220096183, 221202119, 222313643, 223430791, 224553523, - 225681923, 226815983, 227955727, 229101203, 230252411, 231409439, 232572299, 233740999, 234915539, 236095939, - 237282343, 238474711, 239672963, 240877339, 242087771, 243304219, 244526851, 245755619, 246990559, 248231707, - 249479099, 250732739, 251992667, 253258879, 254531507, 255810559, 257096039, 258387967, 259686391, 260991287, - 262302791, 263620879, 264945587, 266276947, 267614983, 268959767, 269344759, 270698227, 272058491, 273425591, - 274799579, 276180431, 277568219, 278963011, 280364803, 281773571, 283189499, 284612527, 286042723, 287480071, - 288924599, 290376451, 291835627, 293302123, 294775991, 296257271, 297745967, 299242171, 300745843, 302257051, - 303775919, 305302427, 306836599, 308378407, 309928027, 311485423, 313050587, 314623703, 316204703, 317793559, - 319390507, 320995471, 322608491, 324229639, 325858867, 327496339, 329142019, 330795991, 332458267, 334128887, - 335807831, 337495303, 339191227, 340895683, 342608719, 344330351, 346060571, 347799511, 349547071, 351303583, - 353068907, 354843119, 356626211, 358418243, 360219283, 362029403, 363848627, 365676923, 367514491, 369361231, - 371217299, 373082707, 374957483, 376841587, 378735251, 380638387, 382551083, 384473399, 386405387, 388347103, - 390298547, 392259767, 394230899, 396211903, 398202899, 400203871, 402214927, 404236087, 406267391, 408308899, - 410360539, 412422631, 414495091, 416577947, 418671283, 420775151, 422889583, 425014571, 427150247, 429296719, - 431453983, 433622011, 435800971, 437990923, 440191879, 442403887, 444627019, 446861267, 449106787, 451363571, - 453631727, 455911259, 458202211, 460504699, 462818767, 465144487, 467481851, 469831003, 472191851, 474564667, - 476949379, 479346103, 481754807, 484175663, 486608687, 489053951, 491511491, 493981363, 496463519, 498958307, - 501465563, 503985479, 506518063, 509063299, 511621387, 514192271, 516776131, 519372859, 521982751, 524605747, - 527241899, 529891199, 532553939, 535230083, 537919639, 538685971, 541392743, 544113239, 546847447, 549595367, - 552357139, 555132803, 557922367, 560725951, 563543663, 566375527, 569221603, 572081959, 574956703, 577845787, - 580749511, 583667831, 586600783, 589548499, 592511039, 595488451, 598480807, 601488211, 604510703, 607548371, - 610601371, 613669687, 616753427, 619852679, 622967503, 626097991, 629244167, 632406163, 635584031, 638777903, - 641987839, 645213847, 648456091, 651714607, 654989519, 658280863, 661588783, 664913323, 668254571, 671612587, - 674987507, 678379379, 681788203, 685214251, 688657483, 692117983, 695595931, 699091331, 702604327, 706134991, - 709683371, 713249591, 716833727, 720435851, 724056107, 727694531, 731351279, 735026371, 738719939, 742432063, - 746162863, 749912399, 753680731, 757468067, 761274403, 765099883, 768944587, 772808551, 776691959, 780594923, - 784517507, 788459759, 792421843, 796403831, 800405831, 804427927, 808470259, 812532911, 816615971, 820719539, - 824843651, 828988331, 833154031, 837340703, 841548427, 845777279, 850027351, 854298799, 858591751, 862906279, - 867242491, 871600487, 875980379, 880382287, 884806283, 889252471, 893721071, 898212083, 902725711, 907261963, - 911821051, 916403011, 921007907, 925636079, 930287503, 934962299, 939660587, 944382499, 949128119, 953897599, - 958691051, 963508519, 968350231, 973216267, 978106799, 983021807, 987961591, 992926211, 997915771, 1002930347, - 1007970143, 1013035271, 1018125743, 1023241907, 1028383823, 1033551523, 1038745151, 1043964947, 1049210831, 1054483151, - 1059782051, 1065107587, 1070459851, 1075839019, 1077368339, 1082782187, 1088223299, 1093691743, 1099187591, 1104711019, - 1110262327, 1115841499, 1121448739, 1127084059, 1132747771, 1138439959, 1144160711, 1149910183, 1155688603, 1161496079, - 1167332711, 1173198647, 1179094079, 1185019067, 1190973899, 1196958667, 1202973511, 1209018599, 1215094019, 1221199951, - 1227336631, 1233504079, 1239702463, 1245932059, 1252193003, 1258485419, 1264809463, 1271165167, 1277552923, 1283972759, - 1290424799, 1296909343, 1303426459, 1309976287, 1316559071, 1323174883, 1329823987, 1336506463, 1343222567, 1349972251, - 1356756031, 1363573879, 1370425967, 1377312463, 1384233491, 1391189419, 1398180307, 1405206307, 1412267611, 1419364259, - 1426496711, 1433664959, 1440869279, 1448109779, 1455386671, 1462700131, 1470050363, 1477437523, 1484861771, 1492323307, - 1499822383, 1507359151, 1514933747, 1522546447, 1530197423, 1537886851, 1545614899, 1553381771, 1561187699, 1569032827, - 1576917379, 1584841567, 1592805583, 1600809611, 1608853859, 1616938507, 1625063819, 1633229951, 1641437099, 1649685467, - 1657975307, 1666306819, 1674680207, 1683095671, 1691553427, 1700053627, 1708596587, 1717182347, 1725811267, 1734483643, - 1743199571, 1751959367, 1760763107, 1769611087, 1778503583, 1787440747, 1796422847, 1805449999, 1814522603, 1823640799, - 1832804767, 1842014791, 1851271043, 1860573907, 1869923411, 1879319999, 1888763743, 1898254999, 1907793931, 1917380807, - 1927015879, 1936699351, 1946431363, 1956212243, 1966042451, 1975922059, 1985851247, 1995830323, 2005859543, 2015939239, - 2026069559, 2036250751, 2046483151, 2056766983, 2067102431, 2077489807, 2087929451, 2098421519, 2108966287, 2119564099, - 2130215159, 2140919723, - }; - - - // Compile-time constant expressions - private static final int MAX_REGULAR_CAPACITY_FOR_DOUBLED_ARRAY = 107325451; - private static final int MAX_REGULAR_INT_CAPACITY = 2140919723; - static { - if (MAX_REGULAR_INT_CAPACITY != REGULAR_INT_CAPACITIES[REGULAR_INT_CAPACITIES.length - 1] || - binarySearch(REGULAR_INT_CAPACITIES, MAX_REGULAR_CAPACITY_FOR_DOUBLED_ARRAY) < 0) - throw new AssertionError(); - } - - /** - * Class for precise and fast scaling non-negative integers by positive doubles. - * - *

Used in {@link com.koloboke.collect.impl.hash.HashConfigWrapper}. - * - *

Latencies of operations on floating stack, required for simple approach scaling - * 

-     *                       Haswell  Steamroller
-     * FILD (long -> double) 6        11
-     * FMUL                  5        5
-     * FDIV                  10-24    9-37
-     * FIST (double -> long) 7        7
-     *
- * - *

In major cases {@code Scaler} allows to replace this - * with megamorphic call cost + a few clock cycles. - */ - private static class Scaler { - - public static Scaler by(double scale) { - if (Double.isNaN(scale) || scale <= 0.0 || Double.isInfinite(scale)) - throw new IllegalArgumentException( - "Scale should be a finite positive number, " + scale + " is given"); - if (scale == 0.25) return BY_0_25; - // Special "precise" BigDecimal forms for scales which are inversions of custom - // scales are needed to preserve inversion consistency - if (scale == 1.0 / 3.0) return BY_3_0_INVERSE; - if (scale == 0.5) return BY_0_5; - if (scale == 1 / 1.5) return BY_1_5_INVERSE; - if (scale == 0.75) return BY_0_75; - if (scale == 1.0) return BY_1_0; - if (scale == 1.0 / 0.75) return BY_0_75_INVERSE; - if (scale == 1.5) return BY_1_5; - if (scale == 2.0) return BY_2_0; - if (scale == 3.0) return BY_3_0; - if (scale == 4.0) return BY_4_0; - return new Scaler(scale); - } - - static final Scaler BY_0_25 = new Scaler(0.25) { - @Override public int scaleUpper(int n) { check(n); return (n >> 2) + 1 ; } - @Override public int scaleLower(int n) { check(n); return n >> 2 ; } - }; - - static final Scaler BY_3_0_INVERSE = new Scaler(1.0 / 3.0); - - static final Scaler BY_0_5 = new Scaler(0.5) { - @Override public int scaleUpper(int n) { check(n); return (n >> 1) + 1 ; } - @Override public int scaleLower(int n) { check(n); return n >> 1 ; } - }; - - static final Scaler BY_1_5_INVERSE = new Scaler(1.0 / 1.5); - - static final Scaler BY_0_75 = new Scaler(0.75) { - @Override public int scaleUpper(int n) { check(n); int r = n - (n >> 2); return (n & 3 ) != 0 ? r : r + 1 ; } - @Override public int scaleLower(int n) { check(n); int r = n - (n >> 2); return (n & 3 ) != 0 ? r - 1 : r ; } - }; - - static final Scaler BY_1_0 = new Scaler(1.0) { - @Override public int scaleUpper(int n) { check(n); return n < Integer.MAX_VALUE ? n + 1 : Integer.MAX_VALUE; } - @Override public int scaleLower(int n) { check(n); return n ; } - }; - - static final Scaler BY_0_75_INVERSE = new Scaler(1.0 / 0.75); - - static final Scaler BY_1_5 = new Scaler(1.5) { - @Override public int scaleUpper(int n) { check(n); return n <= 1431655764 ? n + (n >> 1) + 1 : Integer.MAX_VALUE; } - @Override public int scaleLower(int n) { check(n); return n <= 1431655764 ? n + (n >> 1) : Integer.MAX_VALUE; } - }; - - static final Scaler BY_2_0 = new Scaler(2.0) { - @Override public int scaleUpper(int n) { check(n); return n < (1 << 30) ? (n << 1) + 1 : Integer.MAX_VALUE; } - @Override public int scaleLower(int n) { check(n); return n < (1 << 30) ? (n << 1) : Integer.MAX_VALUE; } - }; - - static final Scaler BY_3_0 = new Scaler(3.0) { - @Override public int scaleUpper(int n) { check(n); return n <= 715827882 ? n + (n << 1) + 1 : Integer.MAX_VALUE; } - @Override public int scaleLower(int n) { check(n); return n <= 715827882 ? n + (n << 1) : Integer.MAX_VALUE; } - }; - - static final Scaler BY_4_0 = new Scaler(4.0) { - @Override public int scaleUpper(int n) { check(n); return n < (1 << 29) ? (n << 2) + 1 : Integer.MAX_VALUE; } - @Override public int scaleLower(int n) { check(n); return n < (1 << 29) ? (n << 2) : Integer.MAX_VALUE; } - }; - - private static void check(int n) { - assert n >= 0 : "n should be non-negative, otherwise result is undefined"; - } - - final double scale; - - private Scaler(double scale) { - this.scale = scale; - } - - public int scaleUpper(int n) { - check(n); - int lower = (int) ((double) n * scale); - return lower < Integer.MAX_VALUE ? lower + 1 : Integer.MAX_VALUE; - } - - public int scaleLower(int n) { - check(n); - return (int) ((double) n * scale); - } - } -} +/* + * Copyright 2014 the original author or authors. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.simantics.scl.runtime.chr; + +import static java.util.Arrays.binarySearch; + +import java.util.Arrays; + +/** + * This class is adapted from MutableQHashObjSetGO class generated by Koloboke library. + * It is used by code generated by SCL compiler. + */ +public class CHRHashIndex { + + private static final double MIN_LOAD = 1.0 / 3.0; + private static final double MAX_LOAD = 2.0 / 3.0; + private static final double TARGET_LOAD = 0.5; + private static final double GROWTH_FACTOR = 2.0; + private static final int INITIAL_CAPACITY = 10; + + private static final Object REMOVED = new Object(); + private static final Object FREE = null; + + //////////////////////////// + // Fields + + /** The current number of occupied slots in the hash. */ + private int size; + + private int maxSize; + + /** The current number of free slots in the hash. */ + private int freeSlots; + + private int minFreeSlots; + + private int removedSlots; + + private Object[] set; + + private static int mix(int hash) { + return hash & Integer.MAX_VALUE; + } + + private boolean noRemoved() { + return removedSlots == 0; + } + + /** + * Creates data structures with a prime capacity at or near the minimum + * needed to hold {@code size} elements without triggering a rehash. + * + *

Should be called only in constructors and externalization code. + */ + private void init(int size) { + this.size = 0; + internalInit(targetCapacity(size)); + } + + private void internalInit(int capacity) { + initSlotCounts(capacity); + allocateArrays(capacity); + } + + private void initSlotCounts(int capacity) { + // No sense in trying to rehash after each insertion + // if the capacity is already reached the limit. + maxSize = !isMaxCapacity(capacity) ? maxSize(capacity) : capacity - 1; + minFreeSlots = minFreeSlots(capacity, size, MAX_LOAD, maxSize); + int freeSlots = this.freeSlots = capacity - size; + // free could be less than minFreeSlots only in case when capacity + // is not sufficient to comply load factor (due to saturation with + // Java array size limit). Set minFreeSlots to a half of free to avoid + // too often (instant) rehashing in this case. + if (freeSlots < minFreeSlots) this.minFreeSlots = (freeSlots + 1) / 2; + removedSlots = 0; + } + + private static int minFreeSlots(int capacity, int size, double maxLoad, int maxSize) { + double load = (double) size / (double) capacity; + // See "Tombstones purge from hashtable: theory and practice" wiki page + double rehashLoad = + 0.55 + 0.721 * load - 0.274 * load * load; + + int minFreeSlots; + // minFreeSlots shouldn't be less than `capacity - maxSize` + if (rehashLoad > maxLoad) { + minFreeSlots = (int) ((double) capacity * (1.0 - rehashLoad)); + } else { + minFreeSlots = capacity - maxSize; + } + // Need at least one free slot for open addressing + return minFreeSlots > 0 ? minFreeSlots : 1; + } + + ///////////////////////////// + // Modification hooks and rehash logic + + public boolean shrink() { + int newCapacity = targetCapacity(size); + if (removedSlots > 0 || newCapacity < set.length) { + rehash(newCapacity); + return true; + } else { + return false; + } + } + + private boolean tryRehashForExpansion(int newCapacity) { + // No sense in rehashing for expansion if we already reached Java array + // size limit. + if (newCapacity > set.length || removedSlots > 0) { + rehash(newCapacity); + return true; + } else { + if (freeSlots < minFreeSlots) + minFreeSlots = (freeSlots + 1) / 2; + return false; + } + } + + public boolean ensureCapacity(long minSize) { + int intMinSize = (int) Math.min(minSize, (long) Integer.MAX_VALUE); + if (minSize < 0L) + throw new IllegalArgumentException( + "Min size should be positive, " + minSize + " given."); + int additionalSize = intMinSize - size; + if (additionalSize <= 0) + return false; + if (intMinSize > maxSize || freeSlots - additionalSize < minFreeSlots) { + return tryRehashForExpansion(targetCapacity(intMinSize)); + } else { + return false; + } + } + + private void postRemoveHook() { + size--; + removedSlots++; + } + + private void postFreeSlotInsertHook() { + if (++size > maxSize) { + if (tryRehashForExpansion(grownCapacity())) + return; + } + if (--freeSlots < minFreeSlots) { + if (!tryRehashIfTooFewFreeSlots() && freeSlots == 0) { + throw new CHRHashOverflowException(); + } + } + } + + private void postRemovedSlotInsertHook() { + if (++size > maxSize) { + if (tryRehashForExpansion(grownCapacity())) + return; + } + removedSlots--; + } + + private boolean tryRehashIfTooFewFreeSlots() { + if (removedSlots > 0) { + rehash(targetCapacity(size)); + return true; + } else { + return tryRehashForExpansion(grownCapacity()); + } + } + + /** For initial hash table construction and rehash to target load (shrink, tombstones purge). */ + private int targetCapacity(int size) { + return capacity(size, targetLoadInverse.scaleUpper(size)); + } + + /** The highest qHash prime below Integer.MAX_VALUE (which is a qHash prime too). */ + private static final int MAX_INT_CAPACITY = 2147483587; + + + private boolean isMaxCapacity(int capacity) { + return capacity >= MAX_INT_CAPACITY; + } + + private int grownCapacity() { + return nearestGreaterCapacity(grow(set.length), size); + } + + protected boolean keyEquals(Object a, Object b) { + return a.equals(b); + } + + protected int keyHashCode(Object key) { + return key.hashCode(); + } + + + public boolean contains(Object key) { + return index(key) >= 0; + } + + private int index(Object key) { + // noinspection unchecked + Object[] keys = set; + int capacity, index; + Object cur; + if ((cur = keys[index = mix(keyHashCode(key)) % (capacity = keys.length)]) == key) { + // key is present + return index; + } else { + if (cur == FREE) { + // key is absent, free slot + return -1; + } else { + if (cur != REMOVED) { + if (keyEquals(key, cur)) { + // key is present + return index; + } else { + if (noRemoved()) { + int bIndex = index, fIndex = index, step = 1; + while (true) { + if ((bIndex -= step) < 0) bIndex += capacity; + if ((cur = keys[bIndex]) == key) { + // key is present + return bIndex; + } else if (cur == FREE) { + // key is absent, free slot + return -1; + } + else if (keyEquals(key, cur)) { + // key is present + return bIndex; + } + int t; + if ((t = (fIndex += step) - capacity) >= 0) fIndex = t; + if ((cur = keys[fIndex]) == key) { + // key is present + return fIndex; + } else if (cur == FREE) { + // key is absent, free slot + return -1; + } + else if (keyEquals(key, cur)) { + // key is present + return fIndex; + } + step += 2; + } + } + } + } + int bIndex = index, fIndex = index, step = 1; + while (true) { + if ((bIndex -= step) < 0) bIndex += capacity; + if ((cur = keys[bIndex]) == key) { + // key is present + return bIndex; + } else if (cur == FREE) { + // key is absent, free slot + return -1; + } + else if (cur != REMOVED && keyEquals(key, cur)) { + // key is present + return bIndex; + } + int t; + if ((t = (fIndex += step) - capacity) >= 0) fIndex = t; + if ((cur = keys[fIndex]) == key) { + // key is present + return fIndex; + } else if (cur == FREE) { + // key is absent, free slot + return -1; + } + else if (cur != REMOVED && keyEquals(key, cur)) { + // key is present + return fIndex; + } + step += 2; + } + } + } + } + + private void allocateArrays(int capacity) { + set = new Object[capacity]; + // not necessary because FREE = null + // Arrays.fill(set, FREE); + } + + + public Object[] toArray() { + Object[] result = new Object[size]; + if (size == 0) + return result; + int resultIndex = 0; + Object[] keys = set; + if (noRemoved()) { + for (int i = keys.length - 1; i >= 0; i--) { + Object key; + // noinspection unchecked + if ((key = keys[i]) != FREE) { + result[resultIndex++] = key; + } + } + } else { + for (int i = keys.length - 1; i >= 0; i--) { + Object key; + // noinspection unchecked + if ((key = keys[i]) != FREE && key != REMOVED) { + result[resultIndex++] = key; + } + } + } + return result; + } + + @SuppressWarnings("unchecked") + public T[] toArray(T[] a) { + if (a.length < size) { + Class elementType = a.getClass().getComponentType(); + a = (T[]) java.lang.reflect.Array.newInstance(elementType, size); + } + if (size == 0) { + if (a.length > 0) + a[0] = null; + return a; + } + int resultIndex = 0; + Object[] keys = set; + if (noRemoved()) { + for (int i = keys.length - 1; i >= 0; i--) { + Object key; + // noinspection unchecked + if ((key = keys[i]) != FREE) { + a[resultIndex++] = (T) key; + } + } + } else { + for (int i = keys.length - 1; i >= 0; i--) { + Object key; + // noinspection unchecked + if ((key = keys[i]) != FREE && key != REMOVED) { + a[resultIndex++] = (T) key; + } + } + } + if (a.length > resultIndex) + a[resultIndex] = null; + return a; + } + + private void rehash(int newCapacity) { + Object[] keys = set; + int removedSlots = this.removedSlots; + internalInit(newCapacity); + Object[] newKeys = set; + int capacity = newKeys.length; + if (removedSlots == 0) { + for (int i = keys.length - 1; i >= 0; i--) { + Object key; + // noinspection unchecked + if ((key = keys[i]) != FREE) { + int index; + if (newKeys[index = mix(keyHashCode(key)) % capacity] != FREE) { + int bIndex = index, fIndex = index, step = 1; + while (true) { + if ((bIndex -= step) < 0) bIndex += capacity; + if (newKeys[bIndex] == FREE) { + index = bIndex; + break; + } + int t; + if ((t = (fIndex += step) - capacity) >= 0) fIndex = t; + if (newKeys[fIndex] == FREE) { + index = fIndex; + break; + } + step += 2; + } + } + newKeys[index] = key; + } + } + } else { + for (int i = keys.length - 1; i >= 0; i--) { + Object key; + // noinspection unchecked + if ((key = keys[i]) != FREE && key != REMOVED) { + int index; + if (newKeys[index = mix(keyHashCode(key)) % capacity] != FREE) { + int bIndex = index, fIndex = index, step = 1; + while (true) { + if ((bIndex -= step) < 0) bIndex += capacity; + if (newKeys[bIndex] == FREE) { + index = bIndex; + break; + } + int t; + if ((t = (fIndex += step) - capacity) >= 0) fIndex = t; + if (newKeys[fIndex] == FREE) { + index = fIndex; + break; + } + step += 2; + } + } + newKeys[index] = key; + } + } + } + } + + public void clear() { + size = 0; + freeSlots = set.length; + removedSlots = 0; + Arrays.fill(set, FREE); + } + + + public CHRHashIndex() { + init(INITIAL_CAPACITY); + } + + public boolean add(Object key) { + Object[] keys = set; + int capacity, index; + Object cur; + keyAbsentFreeSlot: + if ((cur = keys[index = mix(keyHashCode(key)) % (capacity = keys.length)]) != FREE) { + if (cur == key) { + // key is present + return false; + } else { + int firstRemoved; + if (cur != REMOVED) { + if (!keyEquals(key, cur)) { + if (noRemoved()) { + int bIndex = index, fIndex = index, step = 1; + while (true) { + if ((bIndex -= step) < 0) bIndex += capacity; + if ((cur = keys[bIndex]) == FREE) { + index = bIndex; + break keyAbsentFreeSlot; + } else if (cur == key || (keyEquals(key, cur))) { + // key is present + return false; + } + int t; + if ((t = (fIndex += step) - capacity) >= 0) fIndex = t; + if ((cur = keys[fIndex]) == FREE) { + index = fIndex; + break keyAbsentFreeSlot; + } else if (cur == key || (keyEquals(key, cur))) { + // key is present + return false; + } + step += 2; + } + } else { + firstRemoved = -1; + } + } else { + // key is present + return false; + } + } else { + firstRemoved = index; + } + keyAbsentRemovedSlot: { + int bIndex = index, fIndex = index, step = 1; + while (true) { + if ((bIndex -= step) < 0) bIndex += capacity; + if ((cur = keys[bIndex]) == FREE) { + if (firstRemoved < 0) { + index = bIndex; + break keyAbsentFreeSlot; + } else { + break keyAbsentRemovedSlot; + } + } else if (cur == key) { + // key is present + return false; + } else if (cur != REMOVED) { + if (keyEquals(key, cur)) { + // key is present + return false; + } + } else if (firstRemoved < 0) { + firstRemoved = bIndex; + } + int t; + if ((t = (fIndex += step) - capacity) >= 0) fIndex = t; + if ((cur = keys[fIndex]) == FREE) { + if (firstRemoved < 0) { + index = fIndex; + break keyAbsentFreeSlot; + } else { + break keyAbsentRemovedSlot; + } + } else if (cur == key) { + // key is present + return false; + } else if (cur != REMOVED) { + if (keyEquals(key, cur)) { + // key is present + return false; + } + } else if (firstRemoved < 0) { + firstRemoved = fIndex; + } + step += 2; + } + } + // key is absent, removed slot + keys[firstRemoved] = key; + postRemovedSlotInsertHook(); + return true; + } + } + // key is absent, free slot + keys[index] = key; + postFreeSlotInsertHook(); + return true; + } + + /** + * Assumes that the given value doesn't already exist in the index + * (only optimized with this assumption, the method works correctly + * even if the assumption does not hold). + * Returns the old equal element that the given value replaces or + * null if there is no such elements. + */ + public Object addFreshAndReturnOld(Object key) { + Object[] keys = set; + int capacity, index; + Object cur; + keyAbsentFreeSlot: if ((cur = keys[index = mix(keyHashCode(key)) % (capacity = keys.length)]) != FREE) { + int firstRemoved; + if (cur != REMOVED) { + if (!keyEquals(key, cur)) { + if (noRemoved()) { + int bIndex = index, fIndex = index, step = 1; + while (true) { + if ((bIndex -= step) < 0) bIndex += capacity; + if ((cur = keys[bIndex]) == FREE) { + index = bIndex; + break keyAbsentFreeSlot; + } else if (keyEquals(key, cur)) { + keys[bIndex] = key; + return cur; + } + int t; + if ((t = (fIndex += step) - capacity) >= 0) fIndex = t; + if ((cur = keys[fIndex]) == FREE) { + index = fIndex; + break keyAbsentFreeSlot; + } else if (keyEquals(key, cur)) { + keys[fIndex] = key; + return cur; + } + step += 2; + } + } else { + firstRemoved = -1; + } + } else { + keys[index] = key; + return cur; + } + } else { + firstRemoved = index; + } + keyAbsentRemovedSlot: { + int bIndex = index, fIndex = index, step = 1; + while (true) { + if ((bIndex -= step) < 0) bIndex += capacity; + if ((cur = keys[bIndex]) == FREE) { + if (firstRemoved < 0) { + index = bIndex; + break keyAbsentFreeSlot; + } else { + break keyAbsentRemovedSlot; + } + } else if (cur != REMOVED) { + if (keyEquals(key, cur)) { + keys[bIndex] = key; + return cur; + } + } else if (firstRemoved < 0) { + firstRemoved = bIndex; + } + int t; + if ((t = (fIndex += step) - capacity) >= 0) fIndex = t; + if ((cur = keys[fIndex]) == FREE) { + if (firstRemoved < 0) { + index = fIndex; + break keyAbsentFreeSlot; + } else { + break keyAbsentRemovedSlot; + } + } else if (cur != REMOVED) { + if (keyEquals(key, cur)) { + keys[fIndex] = key; + return cur; + } + } else if (firstRemoved < 0) { + firstRemoved = fIndex; + } + step += 2; + } + } + // key is absent, removed slot + keys[firstRemoved] = key; + postRemovedSlotInsertHook(); + return null; + } + // key is absent, free slot + keys[index] = key; + postFreeSlotInsertHook(); + return null; + } + + public Object addFreshAndReturnOldNoRemovals(Object key) { + Object[] keys = set; + int capacity, index; + Object cur; + keyAbsentFreeSlot: if ((cur = keys[index = mix(keyHashCode(key)) % (capacity = keys.length)]) != FREE) { + if (!keyEquals(key, cur)) { + int bIndex = index, fIndex = index, step = 1; + while (true) { + if ((bIndex -= step) < 0) bIndex += capacity; + if ((cur = keys[bIndex]) == FREE) { + index = bIndex; + break keyAbsentFreeSlot; + } else if (keyEquals(key, cur)) { + keys[bIndex] = key; + return cur; + } + int t; + if ((t = (fIndex += step) - capacity) >= 0) fIndex = t; + if ((cur = keys[fIndex]) == FREE) { + index = fIndex; + break keyAbsentFreeSlot; + } else if (keyEquals(key, cur)) { + keys[fIndex] = key; + return cur; + } + step += 2; + } + } else { + keys[index] = key; + return cur; + } + } + // key is absent, free slot + keys[index] = key; + postFreeSlotInsertHook(); + return null; + } + + public boolean remove(Object key) { + // noinspection unchecked + Object[] keys = set; + int capacity, index; + Object cur; + keyPresent: + if ((cur = keys[index = mix(keyHashCode(key)) % (capacity = keys.length)]) != key) { + if (cur == FREE) { + // key is absent, free slot + return false; + } else { + if (cur != REMOVED) { + if (keyEquals(key, cur)) { + break keyPresent; + } else { + if (noRemoved()) { + int bIndex = index, fIndex = index, step = 1; + while (true) { + if ((bIndex -= step) < 0) bIndex += capacity; + if ((cur = keys[bIndex]) == key) { + index = bIndex; + break keyPresent; + } else if (cur == FREE) { + // key is absent, free slot + return false; + } + else if (keyEquals(key, cur)) { + index = bIndex; + break keyPresent; + } + int t; + if ((t = (fIndex += step) - capacity) >= 0) fIndex = t; + if ((cur = keys[fIndex]) == key) { + index = fIndex; + break keyPresent; + } else if (cur == FREE) { + // key is absent, free slot + return false; + } + else if (keyEquals(key, cur)) { + index = fIndex; + break keyPresent; + } + step += 2; + } + } + } + } + int bIndex = index, fIndex = index, step = 1; + while (true) { + if ((bIndex -= step) < 0) bIndex += capacity; + if ((cur = keys[bIndex]) == key) { + index = bIndex; + break keyPresent; + } else if (cur == FREE) { + // key is absent, free slot + return false; + } + else if (cur != REMOVED && keyEquals(key, cur)) { + index = bIndex; + break keyPresent; + } + int t; + if ((t = (fIndex += step) - capacity) >= 0) fIndex = t; + if ((cur = keys[fIndex]) == key) { + index = fIndex; + break keyPresent; + } else if (cur == FREE) { + // key is absent, free slot + return false; + } + else if (cur != REMOVED && keyEquals(key, cur)) { + index = fIndex; + break keyPresent; + } + step += 2; + } + } + } + // key is present + keys[index] = REMOVED; + postRemoveHook(); + return true; + } + + /** + * Assumes that the key exists in the index. Removes it. + */ + public void removeKnownToExistKey(Object key) { + Object[] keys = set; + int capacity, index; + keyPresent: if (keys[index = mix(keyHashCode(key)) % (capacity = keys.length)] != key) { + int bIndex = index, fIndex = index, step = 1; + while (true) { + if ((bIndex -= step) < 0) bIndex += capacity; + if (keys[bIndex] == key) { + index = bIndex; + break keyPresent; + } + int t; + if ((t = (fIndex += step) - capacity) >= 0) fIndex = t; + if (keys[fIndex] == key) { + index = fIndex; + break keyPresent; + } + step += 2; + } + } + keys[index] = REMOVED; + postRemoveHook(); + } + + /** + * Assumes that the key exists in the index. Replaces it with an equal key. + */ + public void replaceKnownToExistKey(Object key, Object replacement) { + Object[] keys = set; + int capacity, index; + keyPresent: if (keys[index = mix(keyHashCode(key)) % (capacity = keys.length)] != key) { + int bIndex = index, fIndex = index, step = 1; + while (true) { + if ((bIndex -= step) < 0) bIndex += capacity; + if (keys[bIndex] == key) { + index = bIndex; + break keyPresent; + } + int t; + if ((t = (fIndex += step) - capacity) >= 0) fIndex = t; + if (keys[fIndex] == key) { + index = fIndex; + break keyPresent; + } + step += 2; + } + } + keys[index] = replacement; + } + + public Object getEqual(Object key) { + // noinspection unchecked + Object[] keys = set; + int capacity, index; + Object cur; + if ((cur = keys[index = mix(keyHashCode(key)) % (capacity = keys.length)]) == FREE) + return null; + if (cur != REMOVED) { + if (keyEquals(key, cur)) + return cur; + if (noRemoved()) { + int bIndex = index, fIndex = index, step = 1; + while (true) { + if ((bIndex -= step) < 0) bIndex += capacity; + if ((cur = keys[bIndex]) == FREE) + return null; + else if (keyEquals(key, cur)) + return cur; + int t; + if ((t = (fIndex += step) - capacity) >= 0) fIndex = t; + if ((cur = keys[fIndex]) == FREE) + return null; + else if (keyEquals(key, cur)) + return cur; + step += 2; + } + } + } + int bIndex = index, fIndex = index, step = 1; + while (true) { + if ((bIndex -= step) < 0) bIndex += capacity; + if ((cur = keys[bIndex]) == FREE) + return null; + else if (cur != REMOVED && keyEquals(key, cur)) + return cur; + int t; + if ((t = (fIndex += step) - capacity) >= 0) fIndex = t; + if ((cur = keys[fIndex]) == FREE) + return null; + else if (cur != REMOVED && keyEquals(key, cur)) + return cur; + step += 2; + } + } + + public Object getEqualNoRemovals(Object key) { + Object[] keys = set; + int capacity, index; + Object cur; + if ((cur = keys[index = mix(keyHashCode(key)) % (capacity = keys.length)]) == FREE) + return null; + if (keyEquals(key, cur)) + return cur; + int bIndex = index, fIndex = index, step = 1; + while (true) { + if ((bIndex -= step) < 0) bIndex += capacity; + if ((cur = keys[bIndex]) == FREE) + return null; + else if (keyEquals(key, cur)) + return cur; + int t; + if ((t = (fIndex += step) - capacity) >= 0) fIndex = t; + if ((cur = keys[fIndex]) == FREE) + return null; + else if (keyEquals(key, cur)) + return cur; + step += 2; + } + } + + private static final Scaler minLoadInverse = Scaler.by(1.0 / MIN_LOAD); + private static final Scaler targetLoadInverse = Scaler.by(1.0 / TARGET_LOAD); + private static final Scaler maxLoad = Scaler.by(MAX_LOAD); + private static final Scaler maxLoadInverse = Scaler.by(1.0 / MAX_LOAD); + private static final Scaler growthFactor = Scaler.by(GROWTH_FACTOR); + + /** + * Computes hash table capacity for the given size and min load of this config. + * + * @param size size of the hash table to compute capacity for + * @return if the given size is non-negative, returns the least int capacity such that + * size / capacity < {@code config().getMinLoad()}, or {@code Integer.MAX_VALUE} + * if there is no such capacity. If size is negative, result is undefined. + */ + private static int maxCapacity(int size) { + return minLoadInverse.scaleUpper(size); + } + + /** + * Computes hash table capacity for the given size and max load of this config. + * + * @param size size of the hash table to compute capacity for + * @return if the given size is non-negative, returns the least int capacity such that + * size / capacity < {@code config().getMaxLoad()}, or {@code Integer.MAX_VALUE} + * if there is no such capacity. If size is negative, result is undefined. + */ + private static int minCapacity(int size) { + return maxLoadInverse.scaleUpper(size); + } + + private static int maxSize(int capacity) { + return maxLoad.scaleLower(capacity); + } + + /** + * Computes grown hash table capacity for the given capacity and growth factor of this config. + * + * @param capacity capacity of the hash table to grow + * @return if the given capacity is non-negative, returns the least int capacity + * such that |new capacity - the given capacity * {@code config().getGrowthFactor()}| < + * 1, or {@code Integer.MAX_VALUE} if there is no such capacity. + * If the given capacity is negative, result is undefined. + */ + private static int grow(int capacity) { + return growthFactor.scaleLower(capacity); + } + + /** + * Chooses lesser or greater capacity, which one is better for the given {@code size} and + * hash config. (The {@code desiredCapacity} is just precomputed + * {@code conf.targetCapacity(size)}). + * + *

Chooses the capacity which is closer to the {@code desiredCapacity} and conform min or + * max capacity bounds for the given {@code size} and hash config. + * + *

If both {@code lesserCapacity} and {@code greaterCapacity} are out of these bounds, + * {@code onFail} value is returned. + * + * @param conf the {@code HashConfigWrapper} + * @param size should be non-negative + * @param desiredCapacity precomputed {@code conf.targetCapacity(size)} + * @param lesserCapacity should be greater than the {@code size} but lesser + * than the {@code desiredCapacity} + * @param greaterCapacity should be greater than the {@code desiredCapacity} + * @param onFail the value to return if both {@code lesserCapacity} and {@code greaterCapacity} + * are lesser than min size and greater than max size respectively + * for the given hash config and size + * @return {@code lesserCapacity} or {@code greaterCapacity} + * @see #chooseBetter(HashConfigWrapper, long, long, long, long, long) + */ + private static int chooseBetter(int size, + int desiredCapacity, int lesserCapacity, int greaterCapacity, int onFail) { + assert 0 <= size; + assert size < lesserCapacity && lesserCapacity < desiredCapacity; + assert desiredCapacity < greaterCapacity; + if (greaterCapacity - desiredCapacity <= desiredCapacity - lesserCapacity && + greaterCapacity <= maxCapacity(size)) { + return greaterCapacity; + } + return lesserCapacity >= minCapacity(size) ? lesserCapacity : onFail; + } + + private static int capacity(int size, int desiredCapacity) { + int lesserCapacity, greaterCapacity; + if (desiredCapacity <= MAX_LOOKUP_CAPACITY) { + int smallTableIndex = SMALL_LOOKUP_TABLE_INDICES[desiredCapacity]; + greaterCapacity = SMALL_LOOKUP_TABLE_CAPACITIES[smallTableIndex]; + if (greaterCapacity == desiredCapacity || smallTableIndex == 0) + return greaterCapacity; + lesserCapacity = SMALL_LOOKUP_TABLE_CAPACITIES[smallTableIndex - 1]; + } + else if (desiredCapacity <= MAX_REGULAR_CHAR_CAPACITY) { + int capIndex = binarySearch(REGULAR_CHAR_CAPACITIES, (char) desiredCapacity); + if (capIndex >= 0) // desiredCapacity is found in REGULAR_CHAR_CAPACITIES + return desiredCapacity; + capIndex = ~capIndex; + lesserCapacity = capIndex > 0 ? + (int) REGULAR_CHAR_CAPACITIES[capIndex - 1] : MAX_LOOKUP_CAPACITY; + greaterCapacity = REGULAR_CHAR_CAPACITIES[capIndex]; + } + else if (desiredCapacity <= MAX_REGULAR_INT_CAPACITY) { + int capIndex = binarySearch(REGULAR_INT_CAPACITIES, desiredCapacity); + if (capIndex >= 0) // desiredCapacity is found in REGULAR_INT_CAPACITIES + return desiredCapacity; + capIndex = ~capIndex; + lesserCapacity = capIndex > 0 ? + REGULAR_INT_CAPACITIES[capIndex - 1] : MAX_REGULAR_CHAR_CAPACITY; + greaterCapacity = REGULAR_INT_CAPACITIES[capIndex]; + } + else { + // Since size could be virtual (expected), don't prematurely throw + // HashOverflowException. If sizes near to Integer.MAX_VALUE is the case, + // version accepting long size should be used. + return MAX_INT_CAPACITY; + } + return chooseBetter(size, desiredCapacity, lesserCapacity, greaterCapacity, + greaterCapacity); + } + + /** For grow rehash. */ + private static int nearestGreaterCapacity(int desiredCapacity, int currentSize) { + assert currentSize >= 0 : "currentSize must be non-negative"; + if (desiredCapacity <= MAX_LOOKUP_CAPACITY) + return SMALL_LOOKUP_TABLE_CAPACITIES[SMALL_LOOKUP_TABLE_INDICES[desiredCapacity]]; + if (desiredCapacity <= MAX_REGULAR_CHAR_CAPACITY) { + int capIndex = binarySearch(REGULAR_CHAR_CAPACITIES, (char) desiredCapacity); + // capIndex >= 0 => desiredCapacity IS a regular capacity + return capIndex < 0 ? REGULAR_CHAR_CAPACITIES[~capIndex] : desiredCapacity; + } + final boolean simpleArrays = true; + if (desiredCapacity <= MAX_REGULAR_INT_CAPACITY) { + int capIndex = binarySearch(REGULAR_INT_CAPACITIES, desiredCapacity); + return capIndex < 0 ? REGULAR_INT_CAPACITIES[~capIndex] : desiredCapacity; + } + int maxCapacity = MAX_INT_CAPACITY; + // overflow-aware + if (currentSize - maxCapacity < 0) + return maxCapacity; + if (simpleArrays && currentSize - Integer.MAX_VALUE < 0) { + // Integer.MAX_VALUE is also a qHash prime, but likely will cause OutOfMemoryError + return Integer.MAX_VALUE; + } else { + // QHash must have at least 1 free slot + throw new CHRHashOverflowException(); + } + } + + private static final char[] SMALL_LOOKUP_TABLE_CAPACITIES = new char[] { + 7, 11, 19, 23, 31, 43, 47, 59, 67, 71, + 79, 83, 103, 107, 127, 131, 139, 151, 163, 167, + 179, 191, 199, 211, 223, 227, 239, 251, 263, 271, + 283, 307, 311, 331, 347, 359, 367, 379, 383, 419, + 431, 439, 443, 463, 467, 479, 487, 491, 499, 503, + 523, 547, 563, 571, 587, 599, 607, 619, 631, 643, + 647, 659, 683, 691, 719, 727, 739, 743, 751, 787, + 811, 823, 827, 839, 859, 863, 883, 887, 907, 911, + 919, 947, 967, 971, 983, 991, 1019 + }; + + private static final byte[] SMALL_LOOKUP_TABLE_INDICES = new byte[] { + 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, + 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, + 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, + 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, + 5, 5, 5, 5, 6, 6, 6, 6, 7, 7, + 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, + 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, + 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, + 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, + 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, + 12, 12, 12, 12, 13, 13, 13, 13, 14, 14, + 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, + 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, + 15, 15, 16, 16, 16, 16, 16, 16, 16, 16, + 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, + 17, 17, 18, 18, 18, 18, 18, 18, 18, 18, + 18, 18, 18, 18, 19, 19, 19, 19, 20, 20, + 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, + 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, + 21, 21, 22, 22, 22, 22, 22, 22, 22, 22, + 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, + 23, 23, 24, 24, 24, 24, 24, 24, 24, 24, + 24, 24, 24, 24, 25, 25, 25, 25, 26, 26, + 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, + 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, + 27, 27, 28, 28, 28, 28, 28, 28, 28, 28, + 28, 28, 28, 28, 29, 29, 29, 29, 29, 29, + 29, 29, 30, 30, 30, 30, 30, 30, 30, 30, + 30, 30, 30, 30, 31, 31, 31, 31, 31, 31, + 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, + 31, 31, 31, 31, 31, 31, 31, 31, 32, 32, + 32, 32, 33, 33, 33, 33, 33, 33, 33, 33, + 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, + 33, 33, 34, 34, 34, 34, 34, 34, 34, 34, + 34, 34, 34, 34, 34, 34, 34, 34, 35, 35, + 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, + 36, 36, 36, 36, 36, 36, 36, 36, 37, 37, + 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, + 38, 38, 38, 38, 39, 39, 39, 39, 39, 39, + 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, + 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, + 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, + 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, + 40, 40, 41, 41, 41, 41, 41, 41, 41, 41, + 42, 42, 42, 42, 43, 43, 43, 43, 43, 43, + 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, + 43, 43, 43, 43, 44, 44, 44, 44, 45, 45, + 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, + 46, 46, 46, 46, 46, 46, 46, 46, 47, 47, + 47, 47, 48, 48, 48, 48, 48, 48, 48, 48, + 49, 49, 49, 49, 50, 50, 50, 50, 50, 50, + 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, + 50, 50, 50, 50, 51, 51, 51, 51, 51, 51, + 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, + 51, 51, 51, 51, 51, 51, 51, 51, 52, 52, + 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, + 52, 52, 52, 52, 53, 53, 53, 53, 53, 53, + 53, 53, 54, 54, 54, 54, 54, 54, 54, 54, + 54, 54, 54, 54, 54, 54, 54, 54, 55, 55, + 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, + 56, 56, 56, 56, 56, 56, 56, 56, 57, 57, + 57, 57, 57, 57, 57, 57, 57, 57, 57, 57, + 58, 58, 58, 58, 58, 58, 58, 58, 58, 58, + 58, 58, 59, 59, 59, 59, 59, 59, 59, 59, + 59, 59, 59, 59, 60, 60, 60, 60, 61, 61, + 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, + 62, 62, 62, 62, 62, 62, 62, 62, 62, 62, + 62, 62, 62, 62, 62, 62, 62, 62, 62, 62, + 62, 62, 62, 62, 63, 63, 63, 63, 63, 63, + 63, 63, 64, 64, 64, 64, 64, 64, 64, 64, + 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, + 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, + 65, 65, 65, 65, 65, 65, 65, 65, 66, 66, + 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, + 67, 67, 67, 67, 68, 68, 68, 68, 68, 68, + 68, 68, 69, 69, 69, 69, 69, 69, 69, 69, + 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, + 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, + 69, 69, 69, 69, 69, 69, 69, 69, 70, 70, + 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, + 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, + 70, 70, 71, 71, 71, 71, 71, 71, 71, 71, + 71, 71, 71, 71, 72, 72, 72, 72, 73, 73, + 73, 73, 73, 73, 73, 73, 73, 73, 73, 73, + 74, 74, 74, 74, 74, 74, 74, 74, 74, 74, + 74, 74, 74, 74, 74, 74, 74, 74, 74, 74, + 75, 75, 75, 75, 76, 76, 76, 76, 76, 76, + 76, 76, 76, 76, 76, 76, 76, 76, 76, 76, + 76, 76, 76, 76, 77, 77, 77, 77, 78, 78, + 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, + 78, 78, 78, 78, 78, 78, 78, 78, 79, 79, + 79, 79, 80, 80, 80, 80, 80, 80, 80, 80, + 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, + 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, + 81, 81, 81, 81, 81, 81, 81, 81, 82, 82, + 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, + 82, 82, 82, 82, 82, 82, 82, 82, 83, 83, + 83, 83, 84, 84, 84, 84, 84, 84, 84, 84, + 84, 84, 84, 84, 85, 85, 85, 85, 85, 85, + 85, 85, 86, 86, 86, 86, 86, 86, 86, 86, + 86, 86, 86, 86, 86, 86, 86, 86, 86, 86, + 86, 86, 86, 86, 86, 86, 86, 86, 86, 86 + }; + + /** Compile-time constant expression */ + private static final int MAX_LOOKUP_CAPACITY = 1019; + static { + if (MAX_LOOKUP_CAPACITY != + SMALL_LOOKUP_TABLE_CAPACITIES[SMALL_LOOKUP_TABLE_CAPACITIES.length - 1]) { + throw new AssertionError(); + } + } + + /** + * These capacities and other regular capacities from {@link #REGULAR_INT_CAPACITIES} + * and {@link #REGULAR_LONG_CAPACITIES} arrays are generated using a single command + * {@code $ java QHashCapacities 40 0.005}, i. e. trying to keep 0.5% max difference between + * neighbouring capacities. + * + * @see {@link #main(String[])} + * @see {@link #generateRegularCapacities(long, double)} + */ + private static final char[] REGULAR_CHAR_CAPACITIES = new char[] { + 1031, 1039, + 1051, 1063, 1087, 1091, 1103, 1123, 1151, 1163, 1171, 1187, + 1223, 1231, 1259, 1279, 1283, 1291, 1303, 1307, 1319, 1327, + 1367, 1399, 1423, 1427, 1439, 1447, 1451, 1459, 1471, 1483, + 1487, 1499, 1511, 1523, 1531, 1543, 1559, 1567, 1571, 1579, + 1583, 1607, 1619, 1627, 1663, 1667, 1699, 1723, 1747, 1759, + 1783, 1787, 1811, 1823, 1831, 1847, 1867, 1871, 1879, 1907, + 1931, 1951, 1979, 1987, 1999, 2003, 2011, 2027, 2039, 2063, + 2083, 2087, 2099, 2111, 2131, 2143, 2179, 2203, 2207, 2239, + 2243, 2251, 2267, 2287, 2311, 2339, 2347, 2351, 2371, 2383, + 2399, 2411, 2423, 2447, 2459, 2467, 2503, 2531, 2539, 2543, + 2551, 2579, 2591, 2647, 2659, 2663, 2671, 2683, 2687, 2699, + 2707, 2711, 2719, 2731, 2767, 2791, 2803, 2819, 2843, 2851, + 2879, 2887, 2903, 2927, 2939, 2963, 2971, 2999, 3011, 3019, + 3023, 3067, 3079, 3083, 3119, 3163, 3167, 3187, 3191, 3203, + 3251, 3259, 3271, 3299, 3307, 3319, 3323, 3331, 3343, 3347, + 3359, 3371, 3391, 3407, 3463, 3467, 3491, 3499, 3511, 3527, + 3539, 3547, 3559, 3571, 3583, 3607, 3623, 3631, 3643, 3659, + 3671, 3691, 3719, 3727, 3739, 3767, 3779, 3803, 3823, 3847, + 3851, 3863, 3907, 3911, 3919, 3923, 3931, 3943, 3947, 3967, + 4003, 4007, 4019, 4027, 4051, 4079, 4091, 4099, 4111, 4127, + 4139, 4159, 4211, 4219, 4231, 4243, 4259, 4271, 4283, 4327, + 4339, 4363, 4391, 4423, 4447, 4451, 4463, 4483, 4507, 4519, + 4523, 4547, 4567, 4583, 4591, 4603, 4639, 4643, 4651, 4663, + 4679, 4691, 4703, 4723, 4751, 4759, 4783, 4787, 4799, 4831, + 4871, 4903, 4919, 4931, 4943, 4951, 4967, 4987, 4999, 5003, + 5011, 5023, 5039, 5051, 5059, 5087, 5099, 5107, 5119, 5147, + 5167, 5171, 5179, 5227, 5231, 5279, 5303, 5323, 5347, 5351, + 5387, 5399, 5407, 5419, 5431, 5443, 5471, 5479, 5483, 5503, + 5507, 5519, 5527, 5531, 5563, 5591, 5623, 5639, 5647, 5651, + 5659, 5683, 5711, 5743, 5779, 5783, 5791, 5807, 5827, 5839, + 5843, 5851, 5867, 5879, 5903, 5923, 5927, 5939, 5987, 6007, + 6011, 6043, 6047, 6067, 6079, 6091, 6131, 6143, 6151, 6163, + 6199, 6203, 6211, 6247, 6263, 6271, 6287, 6299, 6311, 6323, + 6343, 6359, 6367, 6379, 6427, 6451, 6491, 6547, 6551, 6563, + 6571, 6599, 6607, 6619, 6659, 6679, 6691, 6703, 6719, 6763, + 6779, 6791, 6803, 6823, 6827, 6863, 6871, 6883, 6899, 6907, + 6911, 6947, 6959, 6967, 6971, 6983, 6991, 7019, 7027, 7039, + 7043, 7079, 7103, 7127, 7151, 7159, 7187, 7207, 7211, 7219, + 7243, 7247, 7283, 7307, 7331, 7351, 7411, 7451, 7459, 7487, + 7499, 7507, 7523, 7547, 7559, 7583, 7591, 7603, 7607, 7639, + 7643, 7687, 7691, 7699, 7703, 7723, 7727, 7759, 7823, 7867, + 7879, 7883, 7907, 7919, 7927, 7951, 7963, 8011, 8039, 8059, + 8087, 8111, 8123, 8147, 8167, 8171, 8179, 8191, 8219, 8231, + 8243, 8263, 8287, 8291, 8311, 8363, 8387, 8419, 8423, 8431, + 8443, 8447, 8467, 8527, 8539, 8543, 8563, 8599, 8623, 8627, + 8647, 8663, 8699, 8707, 8719, 8731, 8747, 8779, 8783, 8803, + 8807, 8819, 8831, 8839, 8863, 8867, 8887, 8923, 8951, 8963, + 8971, 8999, 9007, 9011, 9043, 9059, 9067, 9091, 9103, 9127, + 9151, 9187, 9199, 9203, 9227, 9239, 9283, 9311, 9319, 9323, + 9343, 9371, 9391, 9403, 9419, 9431, 9439, 9463, 9467, 9479, + 9491, 9511, 9539, 9547, 9551, 9587, 9619, 9623, 9631, 9643, + 9679, 9719, 9739, 9743, 9767, 9787, 9791, 9803, 9811, 9839, + 9851, 9859, 9871, 9883, 9887, 9907, 9923, 9931, 9967, 10007, + 10039, 10067, 10079, 10091, 10099, 10103, 10111, 10139, 10151, 10159, + 10163, 10211, 10223, 10243, 10247, 10259, 10267, 10271, 10303, 10331, + 10343, 10391, 10399, 10427, 10459, 10463, 10487, 10499, 10531, 10559, + 10567, 10607, 10627, 10631, 10639, 10651, 10663, 10667, 10687, 10691, + 10711, 10723, 10739, 10771, 10799, 10831, 10847, 10859, 10867, 10883, + 10891, 10903, 10939, 10979, 10987, 11003, 11027, 11047, 11059, 11071, + 11083, 11087, 11119, 11131, 11159, 11171, 11239, 11243, 11251, 11279, + 11287, 11299, 11311, 11351, 11383, 11399, 11411, 11423, 11443, 11447, + 11467, 11471, 11483, 11491, 11503, 11519, 11527, 11551, 11579, 11587, + 11699, 11719, 11731, 11743, 11779, 11783, 11807, 11827, 11831, 11839, + 11863, 11867, 11887, 11903, 11923, 11927, 11939, 11959, 11971, 11987, + 12007, 12011, 12043, 12071, 12107, 12119, 12143, 12163, 12203, 12211, + 12227, 12239, 12251, 12263, 12323, 12343, 12347, 12379, 12391, 12451, + 12479, 12487, 12491, 12503, 12511, 12527, 12539, 12547, 12583, 12611, + 12619, 12647, 12659, 12671, 12703, 12739, 12743, 12763, 12791, 12799, + 12823, 12899, 12919, 12979, 13043, 13099, 13159, 13219, 13259, 13291, + 13339, 13399, 13463, 13523, 13567, 13619, 13679, 13711, 13763, 13831, + 13879, 13931, 13999, 14051, 14083, 14143, 14207, 14243, 14303, 14323, + 14387, 14431, 14503, 14563, 14627, 14683, 14723, 14779, 14851, 14923, + 14983, 15031, 15083, 15131, 15187, 15259, 15307, 15383, 15439, 15511, + 15551, 15607, 15667, 15727, 15787, 15859, 15919, 15991, 16063, 16111, + 16187, 16267, 16339, 16411, 16427, 16487, 16547, 16619, 16691, 16747, + 16811, 16879, 16963, 17047, 17123, 17207, 17291, 17359, 17443, 17519, + 17579, 17659, 17747, 17807, 17891, 17959, 18043, 18119, 18199, 18287, + 18367, 18427, 18503, 18583, 18671, 18719, 18787, 18839, 18899, 18959, + 19051, 19139, 19231, 19319, 19379, 19423, 19507, 19603, 19687, 19751, + 19843, 19927, 20023, 20123, 20219, 20287, 20347, 20443, 20543, 20611, + 20707, 20807, 20879, 20939, 21011, 21107, 21179, 21283, 21379, 21467, + 21559, 21647, 21739, 21839, 21943, 22039, 22147, 22247, 22343, 22447, + 22531, 22639, 22751, 22859, 22943, 23027, 23131, 23227, 23339, 23447, + 23563, 23663, 23767, 23879, 23971, 24043, 24151, 24239, 24359, 24379, + 24499, 24571, 24683, 24799, 24907, 25031, 25111, 25219, 25339, 25463, + 25579, 25679, 25799, 25903, 25999, 26099, 26227, 26339, 26407, 26539, + 26627, 26759, 26879, 27011, 27143, 27271, 27407, 27527, 27631, 27751, + 27883, 28019, 28151, 28279, 28387, 28499, 28619, 28751, 28879, 29023, + 29167, 29303, 29443, 29587, 29723, 29851, 29983, 30119, 30259, 30391, + 30539, 30671, 30803, 30931, 31079, 31231, 31387, 31543, 31699, 31847, + 31963, 32099, 32251, 32371, 32531, 32687, 32839, 32887, 33023, 33179, + 33331, 33479, 33647, 33811, 33967, 34123, 34231, 34403, 34543, 34703, + 34871, 35023, 35171, 35339, 35507, 35671, 35803, 35951, 36131, 36299, + 36451, 36587, 36767, 36943, 37123, 37307, 37447, 37619, 37799, 37987, + 38167, 38351, 38543, 38671, 38851, 39043, 39227, 39419, 39607, 39779, + 39971, 40151, 40343, 40499, 40699, 40847, 41039, 41243, 41443, 41647, + 41843, 41983, 42179, 42359, 42571, 42743, 42943, 43151, 43331, 43543, + 43759, 43943, 44131, 44351, 44563, 44771, 44959, 45179, 45403, 45599, + 45823, 46051, 46271, 46471, 46687, 46919, 47111, 47339, 47563, 47791, + 48023, 48259, 48491, 48731, 48947, 49171, 49391, 49627, 49871, 50111, + 50359, 50587, 50839, 51031, 51263, 51511, 51767, 52027, 52259, 52511, + 52747, 53003, 53267, 53527, 53791, 54059, 54311, 54583, 54851, 55079, + 55331, 55579, 55843, 56123, 56383, 56659, 56911, 57191, 57467, 57719, + 57991, 58271, 58543, 58831, 59107, 59387, 59659, 59951, 60251, 60527, + 60811, 61091, 61379, 61687, 61991, 62299, 62591, 62903, 63179, 63487, + 63803, 64123, 64439, 64747, 65063, 65371 + }; + + /** Compile-time constant expression */ + private static final int MAX_REGULAR_CHAR_CAPACITY = 65371; + static { + if (MAX_REGULAR_CHAR_CAPACITY != + REGULAR_CHAR_CAPACITIES[REGULAR_CHAR_CAPACITIES.length - 1]) + throw new AssertionError(); + } + + + private static final int[] REGULAR_INT_CAPACITIES = new int[] { + 65687, 65827, 66103, 66431, + 66751, 67079, 67391, 67699, 68023, 68351, 68687, 69031, 69371, 69691, + 69991, 70327, 70627, 70979, 71327, 71647, 71947, 72271, 72623, 72931, + 73291, 73643, 73999, 74323, 74687, 75011, 75367, 75731, 76091, 76463, + 76819, 77167, 77527, 77899, 78259, 78607, 78979, 79319, 79687, 80039, + 80407, 80803, 81203, 81611, 82003, 82387, 82787, 83203, 83563, 83891, + 84299, 84691, 85103, 85523, 85931, 86351, 86783, 87211, 87643, 88079, + 88499, 88919, 89363, 89759, 90187, 90631, 91079, 91499, 91939, 92399, + 92863, 93307, 93763, 94219, 94687, 95131, 95603, 96059, 96527, 96979, + 97459, 97919, 98387, 98867, 99347, 99823, 100291, 100787, 101267, 101719, + 102191, 102667, 103171, 103687, 104207, 104707, 105227, 105751, 106279, 106787, + 107323, 107827, 108343, 108883, 109423, 109943, 110479, 111031, 111539, 112067, + 112603, 113159, 113719, 114259, 114799, 115363, 115931, 116491, 117071, 117659, + 118247, 118831, 119419, 119963, 120539, 121123, 121687, 122263, 122867, 123479, + 124067, 124643, 125243, 125863, 126443, 127031, 127607, 128239, 128879, 129499, + 130147, 130783, 131363, 131543, 132199, 132859, 133519, 134171, 134807, 135463, + 136139, 136811, 137491, 138179, 138863, 139511, 140191, 140891, 141587, 142271, + 142979, 143687, 144379, 145091, 145799, 146519, 147211, 147919, 148627, 149371, + 150107, 150847, 151603, 152363, 153107, 153871, 154619, 155371, 156119, 156887, + 157667, 158443, 159223, 160019, 160807, 161611, 162419, 163211, 164023, 164839, + 165667, 166487, 167311, 168151, 168991, 169823, 170647, 171491, 172331, 173183, + 174047, 174907, 175783, 176651, 177511, 178403, 179287, 180179, 181003, 181871, + 182779, 183691, 184607, 185519, 186451, 187367, 188291, 189199, 190147, 191047, + 192007, 192971, 193939, 194911, 195887, 196871, 197831, 198811, 199783, 200771, + 201743, 202751, 203767, 204751, 205759, 206779, 207799, 208843, 209887, 210907, + 211927, 212987, 214003, 215051, 216119, 217199, 218279, 219371, 220447, 221539, + 222587, 223667, 224683, 225751, 226819, 227947, 228983, 230123, 231271, 232391, + 233551, 234659, 235783, 236947, 238099, 239287, 240479, 241603, 242807, 244003, + 245171, 246371, 247607, 248851, 250091, 251323, 252559, 253787, 255043, 256307, + 257591, 258871, 260171, 261427, 262723, 263951, 265271, 266587, 267887, 269219, + 270563, 271919, 273271, 274579, 275911, 277223, 278591, 279967, 281363, 282767, + 284159, 285559, 286987, 288403, 289843, 291299, 292759, 294223, 295699, 297151, + 298631, 300119, 301579, 303091, 304559, 306083, 307583, 309091, 310643, 312199, + 313679, 315247, 316819, 318403, 319967, 321547, 323123, 324743, 326351, 327967, + 329587, 331231, 332887, 334547, 336199, 337859, 339467, 341171, 342871, 344587, + 346303, 348011, 349759, 351503, 353263, 355027, 356803, 358591, 360391, 362143, + 363959, 365779, 367603, 369407, 371227, 373091, 374939, 376787, 378667, 380563, + 382463, 384359, 386279, 388211, 390151, 392099, 394063, 396031, 398011, 399979, + 401939, 403951, 405947, 407923, 409967, 412019, 414083, 416147, 418199, 420263, + 422311, 424423, 426527, 428639, 430783, 432931, 435103, 437263, 439459, 441667, + 443867, 446087, 448303, 450479, 452731, 454991, 457267, 459523, 461803, 464119, + 466423, 468739, 471091, 473443, 475807, 478171, 480563, 482947, 485347, 487783, + 490207, 492647, 495119, 497587, 500083, 502543, 505067, 507599, 510127, 512663, + 515191, 517739, 520339, 522947, 525571, 528163, 530807, 533447, 536111, 538799, + 541483, 544199, 546919, 549623, 552379, 555143, 557927, 560719, 563503, 566311, + 569083, 571939, 574799, 577627, 580471, 583367, 586291, 589187, 592139, 595087, + 598051, 601031, 604031, 607043, 610063, 613099, 616171, 619247, 622331, 625451, + 628583, 631711, 634859, 638023, 641227, 644431, 647659, 650911, 654163, 657431, + 660727, 664043, 667363, 670711, 674059, 677387, 680783, 684191, 687623, 691051, + 694511, 697979, 701479, 704999, 708527, 712067, 715639, 719179, 722783, 726367, + 729991, 733651, 737327, 741007, 744727, 748463, 752183, 755959, 759719, 763523, + 767323, 771143, 775007, 778871, 782783, 786659, 790567, 794531, 798487, 802471, + 806503, 810539, 814579, 818659, 822763, 826879, 831023, 835123, 839303, 843503, + 847727, 851971, 856187, 860479, 864803, 869119, 873463, 877843, 882239, 886651, + 891103, 895571, 900019, 904531, 909071, 913639, 918199, 922807, 927403, 931999, + 936679, 941383, 946091, 950839, 955607, 960383, 965179, 970027, 974891, 979787, + 984703, 989623, 994559, 999491, 1004483, 1009483, 1014547, 1019639, 1024703, 1029823, + 1034983, 1040167, 1045391, 1050631, 1054171, 1059439, 1064743, 1070087, 1075463, 1080847, + 1086259, 1091711, 1097179, 1102691, 1108223, 1113787, 1119359, 1124983, 1130627, 1136299, + 1142003, 1147739, 1153487, 1159283, 1165103, 1170947, 1176827, 1182739, 1188667, 1194631, + 1200607, 1206619, 1212671, 1218727, 1224823, 1230967, 1237139, 1243343, 1249559, 1255811, + 1262119, 1268447, 1274803, 1281187, 1287623, 1294087, 1300571, 1307063, 1313623, 1320191, + 1326791, 1333411, 1340107, 1346827, 1353551, 1360327, 1367159, 1374007, 1380887, 1387783, + 1394747, 1401739, 1408763, 1415803, 1422899, 1430027, 1437199, 1444411, 1451603, 1458871, + 1466147, 1473503, 1480903, 1488343, 1495751, 1503247, 1510759, 1518343, 1525963, 1533583, + 1541251, 1548947, 1556719, 1564499, 1572359, 1580251, 1588159, 1596107, 1604123, 1612183, + 1620247, 1628383, 1636543, 1644691, 1652947, 1661243, 1669543, 1677899, 1686319, 1694767, + 1703267, 1711799, 1720399, 1729043, 1737691, 1746419, 1755179, 1763959, 1772819, 1781699, + 1790599, 1799591, 1808627, 1817663, 1826771, 1835923, 1845119, 1854379, 1863671, 1873019, + 1882403, 1891859, 1901359, 1910891, 1920487, 1930099, 1939787, 1949527, 1959283, 1969111, + 1978927, 1988839, 1998827, 2008807, 2018899, 2029003, 2039179, 2049419, 2059711, 2069959, + 2080339, 2090771, 2101259, 2106551, 2117119, 2127739, 2138387, 2149127, 2159923, 2170771, + 2181671, 2192623, 2203631, 2214691, 2225819, 2236987, 2248223, 2259503, 2270803, 2282207, + 2293567, 2305091, 2316667, 2328307, 2340007, 2351731, 2363507, 2375327, 2387243, 2399207, + 2411243, 2423359, 2435519, 2447743, 2460043, 2472403, 2484803, 2497259, 2509807, 2522407, + 2535059, 2547791, 2560583, 2573423, 2586343, 2599327, 2612383, 2625487, 2638651, 2651899, + 2665199, 2678551, 2692003, 2705519, 2719111, 2732759, 2746423, 2760223, 2774071, 2788007, + 2802011, 2816059, 2830151, 2844367, 2858623, 2872967, 2887363, 2901839, 2916383, 2930999, + 2945707, 2960467, 2975339, 2990279, 3005267, 3020351, 3035507, 3050759, 3066067, 3081443, + 3096911, 3112391, 3127979, 3143671, 3159439, 3175259, 3191099, 3207119, 3223223, 3239419, + 3255683, 3272039, 3288479, 3304991, 3321583, 3338263, 3355031, 3371867, 3388799, 3405791, + 3422807, 3439987, 3457271, 3474599, 3492043, 3509587, 3527219, 3544907, 3562711, 3580579, + 3598519, 3616583, 3634727, 3652991, 3671347, 3689771, 3708283, 3726911, 3745631, 3764443, + 3783343, 3802283, 3821327, 3840479, 3859759, 3879023, 3898483, 3918067, 3937751, 3957479, + 3977339, 3997307, 4017359, 4037531, 4057799, 4078187, 4098659, 4119239, 4139923, 4160711, + 4181579, 4202567, 4210807, 4231943, 4253203, 4274551, 4295999, 4317571, 4339207, 4361003, + 4382879, 4404899, 4426999, 4449227, 4471559, 4494019, 4516571, 4539247, 4562039, 4584959, + 4607987, 4631131, 4654399, 4677779, 4701239, 4724831, 4748563, 4772399, 4796371, 4820443, + 4844659, 4868999, 4893419, 4918007, 4942687, 4967491, 4992419, 5017447, 5042647, 5067967, + 5093423, 5119007, 5144707, 5170519, 5196467, 5222579, 5248787, 5275159, 5301623, 5328251, + 5355019, 5381927, 5408947, 5436127, 5463391, 5490787, 5518351, 5546071, 5573927, 5601907, + 5630039, 5658307, 5686739, 5715299, 5743987, 5772847, 5801843, 5830963, 5860243, 5889683, + 5919271, 5948939, 5978831, 6008867, 6038999, 6069311, 6099767, 6130391, 6161063, 6192023, + 6223099, 6254359, 6285787, 6317327, 6349043, 6380939, 6412999, 6445223, 6477599, 6510107, + 6542803, 6575671, 6608639, 6641839, 6675211, 6708739, 6742363, 6776207, 6810247, 6844447, + 6878803, 6913351, 6948079, 6982907, 7017979, 7053223, 7088611, 7124231, 7159987, 7195963, + 7232111, 7268423, 7304939, 7341647, 7378531, 7415599, 7452859, 7490303, 7527911, 7565627, + 7603627, 7641791, 7680191, 7718771, 7757543, 7796491, 7835647, 7874983, 7914551, 7954319, + 7994279, 8034451, 8074811, 8115383, 8156147, 8197099, 8238247, 8279627, 8321227, 8363023, + 8405003, 8419511, 8461787, 8504291, 8546999, 8589923, 8633063, 8676431, 8719987, 8763803, + 8807803, 8852059, 8896483, 8941171, 8986091, 9031207, 9076579, 9122143, 9167923, 9213979, + 9260263, 9306779, 9353483, 9400463, 9447667, 9495139, 9542843, 9590699, 9638891, 9687323, + 9735991, 9784903, 9834047, 9883463, 9933059, 9982939, 10033063, 10083443, 10134107, 10185011, + 10236179, 10287587, 10339267, 10391219, 10443431, 10495907, 10548623, 10601627, 10654871, 10708403, + 10762211, 10816271, 10870619, 10925227, 10980059, 11035223, 11090627, 11146279, 11202251, 11258483, + 11314987, 11371807, 11428931, 11486347, 11544047, 11602043, 11660339, 11718923, 11777791, 11836963, + 11896427, 11956199, 12016187, 12076567, 12137183, 12198139, 12259399, 12320983, 12382823, 12445039, + 12507559, 12570403, 12633559, 12697039, 12760843, 12824899, 12889339, 12954079, 13019143, 13084531, + 13150279, 13216331, 13282723, 13349411, 13416463, 13483751, 13551467, 13619563, 13687987, 13756739, + 13825831, 13895291, 13965103, 14035279, 14105759, 14176619, 14247847, 14319419, 14391359, 14463667, + 14536307, 14609351, 14682719, 14756491, 14830603, 14905123, 14980019, 15055259, 15130903, 15206899, + 15283291, 15360071, 15437239, 15514783, 15592739, 15671087, 15749819, 15828947, 15908423, 15988363, + 16068691, 16149431, 16230491, 16312039, 16394003, 16476371, 16559159, 16642343, 16725971, 16810007, + 16836587, 16921183, 17006167, 17091623, 17177507, 17263783, 17350519, 17437691, 17525243, 17613307, + 17701807, 17790739, 17880067, 17969911, 18060187, 18150911, 18242083, 18333703, 18425819, 18518363, + 18611419, 18704927, 18798907, 18893351, 18988267, 19083679, 19179551, 19275847, 19372699, 19470019, + 19567811, 19666123, 19764947, 19864267, 19964059, 20064371, 20165143, 20266391, 20368211, 20470547, + 20573411, 20676791, 20780659, 20885071, 20989967, 21095423, 21201347, 21307859, 21414923, 21522511, + 21630659, 21739351, 21848579, 21958367, 22068647, 22179511, 22290943, 22402951, 22515511, 22628651, + 22742303, 22856527, 22971259, 23086667, 23202643, 23319227, 23436407, 23554099, 23672459, 23791399, + 23910947, 24031087, 24151807, 24273163, 24395023, 24517607, 24640799, 24764611, 24889043, 25014071, + 25139767, 25266071, 25393031, 25520623, 25648867, 25777639, 25907143, 26037299, 26168099, 26299571, + 26431723, 26564507, 26697991, 26832139, 26966963, 27102419, 27238559, 27375419, 27512951, 27651191, + 27790127, 27929723, 28070071, 28211123, 28352887, 28495351, 28638539, 28782419, 28927039, 29072399, + 29218403, 29365207, 29512739, 29661043, 29810023, 29959819, 30110347, 30261643, 30413707, 30566519, + 30720119, 30874483, 31029587, 31185443, 31342139, 31499599, 31657783, 31816847, 31976723, 32137403, + 32298863, 32461159, 32624239, 32788099, 32952839, 33118391, 33284803, 33452047, 33619979, 33670103, + 33839243, 34009279, 34180163, 34351879, 34524491, 34697951, 34872283, 35047483, 35223599, 35400583, + 35578471, 35757247, 35936903, 36117467, 36298943, 36481343, 36664651, 36848891, 37033987, 37220047, + 37407059, 37595027, 37783927, 37973783, 38164571, 38356327, 38548999, 38742707, 38937319, 39132979, + 39329627, 39527123, 39725723, 39925339, 40125947, 40327571, 40530199, 40733867, 40938523, 41144203, + 41350943, 41558687, 41767483, 41977367, 42188287, 42400243, 42613303, 42827431, 43042631, 43258907, + 43476287, 43694747, 43914307, 44134931, 44356639, 44579503, 44803511, 45028639, 45254899, 45482291, + 45710831, 45940523, 46171351, 46403347, 46636519, 46870867, 47106379, 47343083, 47580983, 47820079, + 48060359, 48301867, 48544583, 48788503, 49033651, 49280003, 49527619, 49776479, 50026607, 50277979, + 50530619, 50784523, 51039683, 51296159, 51553903, 51812927, 52073279, 52334951, 52597891, 52862143, + 53127779, 53394727, 53663039, 53932651, 54203659, 54476027, 54749771, 55024859, 55301359, 55579243, + 55858459, 56139079, 56421151, 56704667, 56989571, 57275927, 57563699, 57852943, 58143583, 58435703, + 58729331, 59024443, 59321039, 59619127, 59918687, 60219779, 60522379, 60826511, 61132163, 61439239, + 61747963, 62058247, 62370079, 62683463, 62998451, 63314959, 63633079, 63952799, 64274159, 64597111, + 64921699, 65247907, 65575747, 65905267, 66236431, 66569267, 66903779, 67239967, 67338643, 67677007, + 68017067, 68358739, 68702143, 69047299, 69394219, 69742919, 70093327, 70445519, 70799507, 71155267, + 71512787, 71872127, 72233279, 72596243, 72961039, 73327651, 73696111, 74066411, 74438591, 74812651, + 75188591, 75566347, 75946067, 76327703, 76711231, 77096707, 77484083, 77873431, 78264727, 78657983, + 79053187, 79450363, 79849543, 80250763, 80654027, 81059287, 81466579, 81875951, 82287379, 82700791, + 83116367, 83534023, 83953763, 84375623, 84799619, 85225739, 85653947, 86084287, 86516863, 86951603, + 87388531, 87827647, 88268987, 88712527, 89158283, 89606287, 90056467, 90508987, 90963799, 91420867, + 91880263, 92341967, 92805983, 93272327, 93741019, 94212031, 94685419, 95161219, 95639387, 96119927, + 96602903, 97088339, 97576163, 98066491, 98559259, 99054523, 99552227, 100052467, 100555243, 101060539, + 101568287, 102078679, 102591631, 103107119, 103625239, 104145887, 104669179, 105195127, 105723743, 106254899, + 106788827, 107325451, 107864747, 108406763, 108951503, 109498943, 110049059, 110602031, 111157807, 111716383, + 112277699, 112841863, 113408767, 113978507, 114551263, 115126883, 115705351, 116286743, 116871091, 117458347, + 118048547, 118641739, 119237927, 119837059, 120439243, 121044431, 121652599, 122263903, 122878211, 123495683, + 124116191, 124739887, 125366567, 125996539, 126629663, 127265951, 127905443, 128548139, 129194083, 129843299, + 130495763, 131151491, 131810491, 132472831, 133138519, 133807547, 134479879, 134673607, 135350351, 136030471, + 136714027, 137400979, 138091427, 138785203, 139482599, 140183503, 140887919, 141595859, 142307287, 143022359, + 143741047, 144463339, 145189259, 145918711, 146651903, 147388823, 148129447, 148873787, 149621891, 150373759, + 151129399, 151888843, 152652103, 153419159, 154190087, 154964867, 155743583, 156526207, 157312763, 158103259, + 158897743, 159696211, 160498699, 161305211, 162115787, 162930419, 163749119, 164571971, 165398927, 166230007, + 167065303, 167904791, 168748499, 169596463, 170448683, 171305207, 172165991, 173031143, 173900563, 174774427, + 175652671, 176535311, 177422411, 178313951, 179209991, 180110471, 181015519, 181925111, 182839303, 183758039, + 184681411, 185609447, 186542099, 187479491, 188421539, 189368371, 190319959, 191276291, 192237431, 193203431, + 194174191, 195149939, 196130579, 197116159, 198106663, 199102151, 200102579, 201108043, 202118563, 203134123, + 204154859, 205180751, 206211799, 207248011, 208289351, 209336027, 210387907, 211445131, 212507651, 213575503, + 214648699, 215727247, 216811267, 217900763, 218995739, 220096183, 221202119, 222313643, 223430791, 224553523, + 225681923, 226815983, 227955727, 229101203, 230252411, 231409439, 232572299, 233740999, 234915539, 236095939, + 237282343, 238474711, 239672963, 240877339, 242087771, 243304219, 244526851, 245755619, 246990559, 248231707, + 249479099, 250732739, 251992667, 253258879, 254531507, 255810559, 257096039, 258387967, 259686391, 260991287, + 262302791, 263620879, 264945587, 266276947, 267614983, 268959767, 269344759, 270698227, 272058491, 273425591, + 274799579, 276180431, 277568219, 278963011, 280364803, 281773571, 283189499, 284612527, 286042723, 287480071, + 288924599, 290376451, 291835627, 293302123, 294775991, 296257271, 297745967, 299242171, 300745843, 302257051, + 303775919, 305302427, 306836599, 308378407, 309928027, 311485423, 313050587, 314623703, 316204703, 317793559, + 319390507, 320995471, 322608491, 324229639, 325858867, 327496339, 329142019, 330795991, 332458267, 334128887, + 335807831, 337495303, 339191227, 340895683, 342608719, 344330351, 346060571, 347799511, 349547071, 351303583, + 353068907, 354843119, 356626211, 358418243, 360219283, 362029403, 363848627, 365676923, 367514491, 369361231, + 371217299, 373082707, 374957483, 376841587, 378735251, 380638387, 382551083, 384473399, 386405387, 388347103, + 390298547, 392259767, 394230899, 396211903, 398202899, 400203871, 402214927, 404236087, 406267391, 408308899, + 410360539, 412422631, 414495091, 416577947, 418671283, 420775151, 422889583, 425014571, 427150247, 429296719, + 431453983, 433622011, 435800971, 437990923, 440191879, 442403887, 444627019, 446861267, 449106787, 451363571, + 453631727, 455911259, 458202211, 460504699, 462818767, 465144487, 467481851, 469831003, 472191851, 474564667, + 476949379, 479346103, 481754807, 484175663, 486608687, 489053951, 491511491, 493981363, 496463519, 498958307, + 501465563, 503985479, 506518063, 509063299, 511621387, 514192271, 516776131, 519372859, 521982751, 524605747, + 527241899, 529891199, 532553939, 535230083, 537919639, 538685971, 541392743, 544113239, 546847447, 549595367, + 552357139, 555132803, 557922367, 560725951, 563543663, 566375527, 569221603, 572081959, 574956703, 577845787, + 580749511, 583667831, 586600783, 589548499, 592511039, 595488451, 598480807, 601488211, 604510703, 607548371, + 610601371, 613669687, 616753427, 619852679, 622967503, 626097991, 629244167, 632406163, 635584031, 638777903, + 641987839, 645213847, 648456091, 651714607, 654989519, 658280863, 661588783, 664913323, 668254571, 671612587, + 674987507, 678379379, 681788203, 685214251, 688657483, 692117983, 695595931, 699091331, 702604327, 706134991, + 709683371, 713249591, 716833727, 720435851, 724056107, 727694531, 731351279, 735026371, 738719939, 742432063, + 746162863, 749912399, 753680731, 757468067, 761274403, 765099883, 768944587, 772808551, 776691959, 780594923, + 784517507, 788459759, 792421843, 796403831, 800405831, 804427927, 808470259, 812532911, 816615971, 820719539, + 824843651, 828988331, 833154031, 837340703, 841548427, 845777279, 850027351, 854298799, 858591751, 862906279, + 867242491, 871600487, 875980379, 880382287, 884806283, 889252471, 893721071, 898212083, 902725711, 907261963, + 911821051, 916403011, 921007907, 925636079, 930287503, 934962299, 939660587, 944382499, 949128119, 953897599, + 958691051, 963508519, 968350231, 973216267, 978106799, 983021807, 987961591, 992926211, 997915771, 1002930347, + 1007970143, 1013035271, 1018125743, 1023241907, 1028383823, 1033551523, 1038745151, 1043964947, 1049210831, 1054483151, + 1059782051, 1065107587, 1070459851, 1075839019, 1077368339, 1082782187, 1088223299, 1093691743, 1099187591, 1104711019, + 1110262327, 1115841499, 1121448739, 1127084059, 1132747771, 1138439959, 1144160711, 1149910183, 1155688603, 1161496079, + 1167332711, 1173198647, 1179094079, 1185019067, 1190973899, 1196958667, 1202973511, 1209018599, 1215094019, 1221199951, + 1227336631, 1233504079, 1239702463, 1245932059, 1252193003, 1258485419, 1264809463, 1271165167, 1277552923, 1283972759, + 1290424799, 1296909343, 1303426459, 1309976287, 1316559071, 1323174883, 1329823987, 1336506463, 1343222567, 1349972251, + 1356756031, 1363573879, 1370425967, 1377312463, 1384233491, 1391189419, 1398180307, 1405206307, 1412267611, 1419364259, + 1426496711, 1433664959, 1440869279, 1448109779, 1455386671, 1462700131, 1470050363, 1477437523, 1484861771, 1492323307, + 1499822383, 1507359151, 1514933747, 1522546447, 1530197423, 1537886851, 1545614899, 1553381771, 1561187699, 1569032827, + 1576917379, 1584841567, 1592805583, 1600809611, 1608853859, 1616938507, 1625063819, 1633229951, 1641437099, 1649685467, + 1657975307, 1666306819, 1674680207, 1683095671, 1691553427, 1700053627, 1708596587, 1717182347, 1725811267, 1734483643, + 1743199571, 1751959367, 1760763107, 1769611087, 1778503583, 1787440747, 1796422847, 1805449999, 1814522603, 1823640799, + 1832804767, 1842014791, 1851271043, 1860573907, 1869923411, 1879319999, 1888763743, 1898254999, 1907793931, 1917380807, + 1927015879, 1936699351, 1946431363, 1956212243, 1966042451, 1975922059, 1985851247, 1995830323, 2005859543, 2015939239, + 2026069559, 2036250751, 2046483151, 2056766983, 2067102431, 2077489807, 2087929451, 2098421519, 2108966287, 2119564099, + 2130215159, 2140919723, + }; + + + // Compile-time constant expressions + private static final int MAX_REGULAR_CAPACITY_FOR_DOUBLED_ARRAY = 107325451; + private static final int MAX_REGULAR_INT_CAPACITY = 2140919723; + static { + if (MAX_REGULAR_INT_CAPACITY != REGULAR_INT_CAPACITIES[REGULAR_INT_CAPACITIES.length - 1] || + binarySearch(REGULAR_INT_CAPACITIES, MAX_REGULAR_CAPACITY_FOR_DOUBLED_ARRAY) < 0) + throw new AssertionError(); + } + + /** + * Class for precise and fast scaling non-negative integers by positive doubles. + * + *

Used in {@link com.koloboke.collect.impl.hash.HashConfigWrapper}. + * + *

Latencies of operations on floating stack, required for simple approach scaling + * 

+     *                       Haswell  Steamroller
+     * FILD (long -> double) 6        11
+     * FMUL                  5        5
+     * FDIV                  10-24    9-37
+     * FIST (double -> long) 7        7
+     *
+ * + *

In major cases {@code Scaler} allows to replace this + * with megamorphic call cost + a few clock cycles. + */ + private static class Scaler { + + public static Scaler by(double scale) { + if (Double.isNaN(scale) || scale <= 0.0 || Double.isInfinite(scale)) + throw new IllegalArgumentException( + "Scale should be a finite positive number, " + scale + " is given"); + if (scale == 0.25) return BY_0_25; + // Special "precise" BigDecimal forms for scales which are inversions of custom + // scales are needed to preserve inversion consistency + if (scale == 1.0 / 3.0) return BY_3_0_INVERSE; + if (scale == 0.5) return BY_0_5; + if (scale == 1 / 1.5) return BY_1_5_INVERSE; + if (scale == 0.75) return BY_0_75; + if (scale == 1.0) return BY_1_0; + if (scale == 1.0 / 0.75) return BY_0_75_INVERSE; + if (scale == 1.5) return BY_1_5; + if (scale == 2.0) return BY_2_0; + if (scale == 3.0) return BY_3_0; + if (scale == 4.0) return BY_4_0; + return new Scaler(scale); + } + + static final Scaler BY_0_25 = new Scaler(0.25) { + @Override public int scaleUpper(int n) { check(n); return (n >> 2) + 1 ; } + @Override public int scaleLower(int n) { check(n); return n >> 2 ; } + }; + + static final Scaler BY_3_0_INVERSE = new Scaler(1.0 / 3.0); + + static final Scaler BY_0_5 = new Scaler(0.5) { + @Override public int scaleUpper(int n) { check(n); return (n >> 1) + 1 ; } + @Override public int scaleLower(int n) { check(n); return n >> 1 ; } + }; + + static final Scaler BY_1_5_INVERSE = new Scaler(1.0 / 1.5); + + static final Scaler BY_0_75 = new Scaler(0.75) { + @Override public int scaleUpper(int n) { check(n); int r = n - (n >> 2); return (n & 3 ) != 0 ? r : r + 1 ; } + @Override public int scaleLower(int n) { check(n); int r = n - (n >> 2); return (n & 3 ) != 0 ? r - 1 : r ; } + }; + + static final Scaler BY_1_0 = new Scaler(1.0) { + @Override public int scaleUpper(int n) { check(n); return n < Integer.MAX_VALUE ? n + 1 : Integer.MAX_VALUE; } + @Override public int scaleLower(int n) { check(n); return n ; } + }; + + static final Scaler BY_0_75_INVERSE = new Scaler(1.0 / 0.75); + + static final Scaler BY_1_5 = new Scaler(1.5) { + @Override public int scaleUpper(int n) { check(n); return n <= 1431655764 ? n + (n >> 1) + 1 : Integer.MAX_VALUE; } + @Override public int scaleLower(int n) { check(n); return n <= 1431655764 ? n + (n >> 1) : Integer.MAX_VALUE; } + }; + + static final Scaler BY_2_0 = new Scaler(2.0) { + @Override public int scaleUpper(int n) { check(n); return n < (1 << 30) ? (n << 1) + 1 : Integer.MAX_VALUE; } + @Override public int scaleLower(int n) { check(n); return n < (1 << 30) ? (n << 1) : Integer.MAX_VALUE; } + }; + + static final Scaler BY_3_0 = new Scaler(3.0) { + @Override public int scaleUpper(int n) { check(n); return n <= 715827882 ? n + (n << 1) + 1 : Integer.MAX_VALUE; } + @Override public int scaleLower(int n) { check(n); return n <= 715827882 ? n + (n << 1) : Integer.MAX_VALUE; } + }; + + static final Scaler BY_4_0 = new Scaler(4.0) { + @Override public int scaleUpper(int n) { check(n); return n < (1 << 29) ? (n << 2) + 1 : Integer.MAX_VALUE; } + @Override public int scaleLower(int n) { check(n); return n < (1 << 29) ? (n << 2) : Integer.MAX_VALUE; } + }; + + private static void check(int n) { + assert n >= 0 : "n should be non-negative, otherwise result is undefined"; + } + + final double scale; + + private Scaler(double scale) { + this.scale = scale; + } + + public int scaleUpper(int n) { + check(n); + int lower = (int) ((double) n * scale); + return lower < Integer.MAX_VALUE ? lower + 1 : Integer.MAX_VALUE; + } + + public int scaleLower(int n) { + check(n); + return (int) ((double) n * scale); + } + } +}