diff options
author | Sven Gothel <[email protected]> | 2019-12-31 03:06:59 +0100 |
---|---|---|
committer | Sven Gothel <[email protected]> | 2019-12-31 03:06:59 +0100 |
commit | 178c7b9d40e06a04790542241912ca21d2c7b92f (patch) | |
tree | fdc483d48020ab2d5929e4611092e08ee8f0da8b /src/java | |
parent | c6fabb0ac94000afe29156f170c63080a37c034b (diff) |
WeakIdentityHashMap: Refine capacity computation; Bitfield.Util add 'PowerOf2' functions
Diffstat (limited to 'src/java')
-rw-r--r-- | src/java/com/jogamp/common/util/Bitfield.java | 52 | ||||
-rw-r--r-- | src/java/com/jogamp/common/util/WeakIdentityHashMap.java | 55 |
2 files changed, 105 insertions, 2 deletions
diff --git a/src/java/com/jogamp/common/util/Bitfield.java b/src/java/com/jogamp/common/util/Bitfield.java index 4b2b9d5..dd6fa18 100644 --- a/src/java/com/jogamp/common/util/Bitfield.java +++ b/src/java/com/jogamp/common/util/Bitfield.java @@ -42,6 +42,14 @@ public interface Bitfield { */ public static class Util { /** + * Maximum 32bit integer value being of {@link #isPowerOf2(int)}. + * <p> + * We rely on the JVM spec {@link Integer#SIZE} == 32. + * </p> + */ + public static final int MAX_POWER_OF_2 = 1 << ( Integer.SIZE - 2 ); + + /** * Returns the 32 bit mask of n-bits, i.e. n low order 1’s. * <p> * Implementation handles n == 32. @@ -67,6 +75,9 @@ public interface Bitfield { * http://tekpool.wordpress.com/category/bit-count/ * http://www.hackersdelight.org/ * </pre> + * <p> + * We rely on the JVM spec {@link Integer#SIZE} == 32. + * </p> */ public static final int bitCount(int n) { // Note: Original used 'unsigned int', @@ -87,6 +98,47 @@ public interface Bitfield { n = n + (n >>> 16); return n & 0x3f; } + + /** + * Returns {@code true} if the given integer is a power of 2 + * <p> + * Source: bithacks: http://www.graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2 + * </p> + */ + public static final boolean isPowerOf2(final int n) { + return 0<n && 0 == (n & (n - 1)); + } + /** + * Returns the next higher power of 2 of 32-bit of given {@code n} + * <p> + * Source: bithacks: http://www.graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2 + * </p> + * <p> + * We rely on the JVM spec {@link Integer#SIZE} == 32. + * </p> + */ + public static final int nextPowerOf2(int n) { + n--; + n |= n >>> 1; + n |= n >>> 2; + n |= n >>> 4; + n |= n >>> 8; + n |= n >>> 16; + return (n < 0) ? 1 : n + 1; // avoid edge case where n is 0, it would return 0, which isn't a power of 2 + } + /** + * If the given {@code n} is not {@link #isPowerOf2(int)} return {@link #nextPowerOf2(int)}, + * otherwise return {@code n} unchanged. + * <pre> + * return isPowerOf2(n) ? n : nextPowerOf2(n); + * </pre> + * <p> + * We rely on the JVM spec {@link Integer#SIZE} == 32. + * </p> + */ + public static final int roundToPowerOf2(final int n) { + return isPowerOf2(n) ? n : nextPowerOf2(n); + } } /** * Simple {@link Bitfield} factory for returning the efficient implementation. diff --git a/src/java/com/jogamp/common/util/WeakIdentityHashMap.java b/src/java/com/jogamp/common/util/WeakIdentityHashMap.java index f6a93bd..fd865ba 100644 --- a/src/java/com/jogamp/common/util/WeakIdentityHashMap.java +++ b/src/java/com/jogamp/common/util/WeakIdentityHashMap.java @@ -89,15 +89,64 @@ public class WeakIdentityHashMap<K, V> implements Map<K, V> { * Usable slots before resize are {@code capacity * loadFactor}. * </p> * <p> - * Capacity for n-slots w/o resize would be {@code Math.ceil(n/loadFactor)}. + * Capacity for n-slots w/o resize would be {@code (float)n/loadFactor + 1.0f}, see {@link #capacityForRequiredSize(int, float[])}. * </p> * @param initialCapacity default value would be 16, i.e. 12 slots @ 0.75f loadFactor before resize * @param loadFactor default value would be 0.75f + * @see #capacityForRequiredSize(int, float[]) + * @see #createWithRequiredSize(int, float) */ public WeakIdentityHashMap(final int initialCapacity, final float loadFactor) { backingStore = new HashMap<>(initialCapacity, loadFactor); } + /** + * Static creation method using {@link #capacityForRequiredSize(int, float[])} + * to instantiate a new {@link WeakIdentityHashMap} via {@link #WeakIdentityHashMap(int, float)}. + * + * @param requiredSize the user desired n-slots before resize + * @param loadFactor given loadFactor, which might be increased a little to avoid next PowerOf2 bloat + * @return the new {@link WeakIdentityHashMap} instance + */ + @SuppressWarnings("rawtypes") + public static WeakIdentityHashMap<?, ?> createWithRequiredSize(final int requiredSize, final float loadFactor) { + final float[] lf = { loadFactor }; + final int icap = capacityForRequiredSize(requiredSize, lf); + return new WeakIdentityHashMap(icap, lf[0]); + } + + /** + * Returns the [initial] capacity using the given {@code loadFactor} + * and {@code requiredSize}. + * <p> + * General calculation is {@code (float)requiredSize/loadFactor + 1.0f}, using {@code loadFactor := 0.75f}. + * </p> + * <p> + * In case above computed capacity is {@link Bitfield.Util#isPowerOf2(int)}, + * the given {@code loadFactor} will be increased to avoid next PowerOf2 table size initialization. + * </p> + * @param requiredSize the user desired n-slots before resize + * @param loadFactor given loadFactor, which might be increased a little to avoid next PowerOf2 bloat + * @return the [initial] capacity to be used for {@link #WeakIdentityHashMap(int, float)} + */ + public static int capacityForRequiredSize(final int requiredSize, final float[] loadFactor) { + if( requiredSize >= Bitfield.Util.MAX_POWER_OF_2 ) { + return Integer.MAX_VALUE; + } + float lf = loadFactor[0]; + int c0 = (int)( requiredSize/lf + 1.0f ); + if( !Bitfield.Util.isPowerOf2(c0) || 0.86f <= lf ) { + return c0; + } + do { + lf += 0.01f; + c0 = (int)( requiredSize/lf + 1.0f ); + } while( Bitfield.Util.isPowerOf2(c0) && 0.86f > lf ); + + loadFactor[0] = lf; + return c0; + } + @Override public void clear() { backingStore.clear(); @@ -192,7 +241,9 @@ public class WeakIdentityHashMap<K, V> implements Map<K, V> { public void putAll(final Map<? extends K, ? extends V> t) { final int n = t.size(); if ( 0 < n ) { - final Map<IdentityWeakReference<K>, V> t2 = new HashMap<>((int)Math.ceil(n/0.75), 0.75f); + final float[] lf = { 0.75f }; + final int icap = capacityForRequiredSize(n, lf); + final Map<IdentityWeakReference<K>, V> t2 = new HashMap<>(icap, lf[0]); for (final Map.Entry<? extends K, ? extends V> e : t.entrySet()) { t2.put(new IdentityWeakReference<K>(e.getKey(), queue), e.getValue()); } |