aboutsummaryrefslogtreecommitdiffstats
path: root/src/java
diff options
context:
space:
mode:
authorSven Gothel <[email protected]>2019-12-31 03:06:59 +0100
committerSven Gothel <[email protected]>2019-12-31 03:06:59 +0100
commit178c7b9d40e06a04790542241912ca21d2c7b92f (patch)
treefdc483d48020ab2d5929e4611092e08ee8f0da8b /src/java
parentc6fabb0ac94000afe29156f170c63080a37c034b (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.java52
-rw-r--r--src/java/com/jogamp/common/util/WeakIdentityHashMap.java55
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());
}