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