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