This is an automated email from the ASF dual-hosted git repository. bchapuis pushed a commit to branch 681-handle-the-out-of-memory-errors in repository https://gitbox.apache.org/repos/asf/incubator-baremaps.git
commit 95be2b6d7244390e17ce94744bd2b9ed7a8d2ce1 Author: Bertil Chapuis <[email protected]> AuthorDate: Wed Jul 12 14:57:30 2023 +0200 Fix some warnings --- .../collection/Long2LongOpenHashDataMap.java | 433 +++++++++++------- .../collection/Long2LongPackedOpenHashDataMap.java | 367 +++++++++------ .../collection/Long2ObjectOpenHashDataMap.java | 505 ++++++++++++++------- 3 files changed, 812 insertions(+), 493 deletions(-) diff --git a/baremaps-core/src/main/java/org/apache/baremaps/database/collection/Long2LongOpenHashDataMap.java b/baremaps-core/src/main/java/org/apache/baremaps/database/collection/Long2LongOpenHashDataMap.java index ef8bc548..00e374be 100644 --- a/baremaps-core/src/main/java/org/apache/baremaps/database/collection/Long2LongOpenHashDataMap.java +++ b/baremaps-core/src/main/java/org/apache/baremaps/database/collection/Long2LongOpenHashDataMap.java @@ -35,31 +35,31 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap /** * The array of keys. */ - protected transient AbstractDataList<Long> key; + protected AbstractDataList<Long> key; /** * The array of values. */ - protected transient AbstractDataList<Long> value; + protected AbstractDataList<Long> value; /** * The mask for wrapping a position counter. */ - protected transient long mask; + protected long mask; /** * Whether this map contains the key zero. */ - protected transient boolean containsNullKey; + protected boolean containsNullKey; /** * The current table size. */ - protected transient long n; + protected long n; /** * Threshold after which we rehash. It must be the table size times {@link #f}. */ - protected transient long maxFill; + protected long maxFill; /** * We never resize below this threshold, which is the construction-time {#n}. */ - protected final transient long minN; + protected final long minN; /** * Number of entries in the set (including the key zero, if present). */ @@ -71,18 +71,16 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap /** * Cached set of entries. */ - protected transient FastEntrySet entries; + protected FastEntrySet entries; /** * Cached set of keys. */ - protected transient LongSet keys; + protected LongSet keys; /** * Cached collection of values. */ - protected transient LongCollection values; - - private Supplier<AbstractDataList<Long>> listSupplier; + protected LongCollection values; /** * Creates a new hash map. @@ -98,10 +96,12 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap float f, Supplier<AbstractDataList<Long>> keySupplier, Supplier<AbstractDataList<Long>> valueSupplier) { - if (f <= 0 || f >= 1) + if (f <= 0 || f >= 1) { throw new IllegalArgumentException("Load factor must be greater than 0 and smaller than 1"); - if (expected < 0) - throw new IllegalArgumentException("The expected number of elements must be nonnegative"); + } + if (expected < 0) { + throw new IllegalArgumentException("The expected number of elements must be non-negative"); + } this.f = f; this.minN = n = bigArraySize(expected, f); this.mask = n - 1; @@ -118,23 +118,26 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap private void ensureCapacity(final long capacity) { final long needed = bigArraySize(capacity, f); - if (needed > n) + if (needed > n) { rehash(needed); + } } private void tryCapacity(final long capacity) { final long needed = Math.min(1 << 30, Math.max(2, HashCommon.nextPowerOfTwo((long) Math.ceil(capacity / f)))); - if (needed > n) + if (needed > n) { rehash(needed); + } } private long removeEntry(final long pos) { final long oldValue = value.get(pos); size.decrementAndGet(); shiftKeys(pos); - if (n > minN && size.get() < maxFill / 4 && n > DEFAULT_INITIAL_SIZE) + if (n > minN && size.get() < maxFill / 4 && n > DEFAULT_INITIAL_SIZE) { rehash(n / 2); + } return oldValue; } @@ -142,48 +145,55 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap containsNullKey = false; final long oldValue = value.get(n); size.decrementAndGet(); - if (n > minN && size.get() < maxFill / 4 && n > DEFAULT_INITIAL_SIZE) + if (n > minN && size.get() < maxFill / 4 && n > DEFAULT_INITIAL_SIZE) { rehash(n / 2); + } return oldValue; } @Override public void putAll(Map<? extends Long, ? extends Long> m) { - if (f <= .5) - ensureCapacity(m.size()); // The resulting map will be sized for m.size() elements - else - tryCapacity(size() + m.size()); // The resulting map will be tentatively sized for size() + - // m.size() - // elements + if (f <= .5) { + ensureCapacity(m.size()); + } else { + tryCapacity(sizeAsLong() + m.size()); + } super.putAll(m); } private long find(final long k) { - if (((k) == (0))) + if (((k) == 0)) { return containsNullKey ? n : -(n + 1); + } long curr; long pos; // The starting point. - if (((curr = key.get(pos = HashCommon.mix((k)) & mask)) == (0))) + if (((curr = key.get(pos = HashCommon.mix((k)) & mask)) == 0)) { return -(pos + 1); - if (((k) == (curr))) + } + if (((k) == (curr))) { return pos; + } // There's always an unused entry. while (true) { - if (((curr = key.get(pos = (pos + 1) & mask)) == (0))) + if (((curr = key.get(pos = (pos + 1) & mask)) == 0)) { return -(pos + 1); - if (((k) == (curr))) + } + if (((k) == (curr))) { return pos; + } } } private void insert(final long pos, final long k, final long v) { - if (pos == n) + if (pos == n) { containsNullKey = true; + } key.set(pos, k); value.set(pos, v); - if (size.getAndIncrement() >= maxFill) + if (size.getAndIncrement() >= maxFill) { rehash(bigArraySize(size.get() + 1, f)); + } } @Override @@ -219,20 +229,24 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap */ public long addTo(final long k, final long incr) { long pos; - if (((k) == (0))) { - if (containsNullKey) + if (((k) == 0)) { + if (containsNullKey) { return addToValue(n, incr); + } pos = n; containsNullKey = true; } else { long curr; // The starting point. - if (!((curr = key.get(pos = HashCommon.mix((k)) & mask)) == (0))) { - if (((curr) == (k))) + if (!((curr = key.get(pos = HashCommon.mix((k)) & mask)) == 0)) { + if (((curr) == (k))) { return addToValue(pos, incr); - while (!((curr = key.get(pos = (pos + 1) & mask)) == (0))) - if (((curr) == (k))) + } + while (!((curr = key.get(pos = (pos + 1) & mask)) == 0)) { + if (((curr) == (k))) { return addToValue(pos, incr); + } + } } } key.set(pos, k); @@ -255,13 +269,14 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap for (;;) { pos = ((last = pos) + 1) & mask; for (;;) { - if (((curr = key.get(pos)) == (0))) { + if (((curr = key.get(pos)) == 0)) { key.set(last, 0L); return; } slot = HashCommon.mix((curr)) & mask; - if (last <= pos ? last >= slot || slot > pos : last >= slot && slot > pos) + if (last <= pos ? last >= slot || slot > pos : last >= slot && slot > pos) { break; + } pos = (pos + 1) & mask; } key.set(last, curr); @@ -272,75 +287,93 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap @Override public long remove(final long k) { - if (((k) == (0))) { - if (containsNullKey) + if (((k) == 0)) { + if (containsNullKey) { return removeNullEntry(); + } return defRetValue; } long curr; long pos; // The starting point. - if (((curr = key.get(pos = HashCommon.mix((k)) & mask)) == (0))) + if (((curr = key.get(pos = HashCommon.mix((k)) & mask)) == 0)) { return defRetValue; - if (((k) == (curr))) + } + if (((k) == (curr))) { return removeEntry(pos); + } while (true) { - if (((curr = key.get(pos = (pos + 1) & mask)) == (0))) + if (((curr = key.get(pos = (pos + 1) & mask)) == 0)) { return defRetValue; - if (((k) == (curr))) + } + if (((k) == (curr))) { return removeEntry(pos); + } } } @Override public long get(final long k) { - if (((k) == (0))) + if (((k) == 0)) { return containsNullKey ? value.get(n) : defRetValue; + } long curr; long pos; // The starting point. - if (((curr = key.get(pos = HashCommon.mix((k)) & mask)) == (0))) + if (((curr = key.get(pos = HashCommon.mix((k)) & mask)) == 0)) { return defRetValue; - if (((k) == (curr))) + } + if (((k) == (curr))) { return value.get(pos); + } // There's always an unused entry. while (true) { - if (((curr = key.get(pos = (pos + 1) & mask)) == (0))) + if (((curr = key.get(pos = (pos + 1) & mask)) == 0)) { return defRetValue; - if (((k) == (curr))) + } + if (((k) == (curr))) { return value.get(pos); + } } } @Override public boolean containsKey(final long k) { - if (((k) == (0))) + if (((k) == 0)) { return containsNullKey; + } long curr; long pos; // The starting point. - if (((curr = key.get(pos = HashCommon.mix((k)) & mask)) == (0))) + if (((curr = key.get(pos = HashCommon.mix((k)) & mask)) == 0)) { return false; - if (((k) == (curr))) + } + if (((k) == (curr))) { return true; + } // There's always an unused entry. while (true) { - if (((curr = key.get(pos = (pos + 1) & mask)) == (0))) + if (((curr = key.get(pos = (pos + 1) & mask)) == 0)) { return false; - if (((k) == (curr))) + } + if (((k) == (curr))) { return true; + } } } @Override public boolean containsValue(final long v) { - if (containsNullKey && ((value.get(n)) == (v))) + if (containsNullKey && ((value.get(n)) == (v))) { return true; - for (long i = n; i-- != 0;) - if (!((key.get(i)) == (0)) && ((value.get(i)) == (v))) + } + for (long i = n; i-- != 0;) { + if (!((key.get(i)) == 0) && ((value.get(i)) == (v))) { return true; + } + } return false; } @@ -350,21 +383,26 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap @Override public long getOrDefault(final long k, final long defaultValue) { - if (((k) == (0))) + if (((k) == 0)) { return containsNullKey ? value.get(n) : defaultValue; + } long curr; long pos; // The starting point. - if (((curr = key.get(pos = HashCommon.mix((k)) & mask)) == (0))) + if (((curr = key.get(pos = HashCommon.mix((k)) & mask)) == 0)) { return defaultValue; - if (((k) == (curr))) + } + if (((k) == (curr))) { return value.get(pos); + } // There's always an unused entry. while (true) { - if (((curr = key.get(pos = (pos + 1) & mask)) == (0))) + if (((curr = key.get(pos = (pos + 1) & mask)) == 0)) { return defaultValue; - if (((k) == (curr))) + } + if (((k) == (curr))) { return value.get(pos); + } } } @@ -374,8 +412,9 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap @Override public long putIfAbsent(final long k, final long v) { final long pos = find(k); - if (pos >= 0) + if (pos >= 0) { return value.get(pos); + } insert(-pos - 1, k, v); return defRetValue; } @@ -386,7 +425,7 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap @Override public boolean remove(final long k, final long v) { - if (((k) == (0))) { + if (((k) == 0)) { if (containsNullKey && ((v) == (value.get(n)))) { removeNullEntry(); return true; @@ -396,15 +435,17 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap long curr; long pos; // The starting point. - if (((curr = key.get(pos = HashCommon.mix((k)) & mask)) == (0))) + if (((curr = key.get(pos = HashCommon.mix((k)) & mask)) == 0)) { return false; + } if (((k) == (curr)) && ((v) == (value.get(pos)))) { removeEntry(pos); return true; } while (true) { - if (((curr = key.get(pos = (pos + 1) & mask)) == (0))) + if (((curr = key.get(pos = (pos + 1) & mask)) == 0)) { return false; + } if (((k) == (curr)) && ((v) == (value.get(pos)))) { removeEntry(pos); return true; @@ -418,8 +459,9 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap @Override public boolean replace(final long k, final long oldValue, final long v) { final long pos = find(k); - if (pos < 0 || !((oldValue) == (value.get(pos)))) + if (pos < 0 || !(oldValue == (value.get(pos)))) { return false; + } value.set(pos, v); return true; } @@ -430,8 +472,9 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap @Override public long replace(final long k, final long v) { final long pos = find(k); - if (pos < 0) + if (pos < 0) { return defRetValue; + } final long oldValue = value.get(pos); value.set(pos, v); return oldValue; @@ -445,8 +488,9 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap final java.util.function.LongUnaryOperator mappingFunction) { java.util.Objects.requireNonNull(mappingFunction); final long pos = find(k); - if (pos >= 0) + if (pos >= 0) { return value.get(pos); + } final long newValue = mappingFunction.applyAsLong(k); insert(-pos - 1, k, newValue); return newValue; @@ -459,10 +503,12 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap public long computeIfAbsent(final long key, final Long2LongFunction mappingFunction) { java.util.Objects.requireNonNull(mappingFunction); final long pos = find(key); - if (pos >= 0) + if (pos >= 0) { return value.get(pos); - if (!mappingFunction.containsKey(key)) + } + if (!mappingFunction.containsKey(key)) { return defRetValue; + } final long newValue = mappingFunction.get(key); insert(-pos - 1, key, newValue); return newValue; @@ -476,12 +522,14 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap final java.util.function.LongFunction<? extends Long> mappingFunction) { java.util.Objects.requireNonNull(mappingFunction); final long pos = find(k); - if (pos >= 0) + if (pos >= 0) { return value.get(pos); + } final Long newValue = mappingFunction.apply(k); - if (newValue == null) + if (newValue == null) { return defRetValue; - final long v = (newValue).longValue(); + } + final long v = newValue; insert(-pos - 1, k, v); return v; } @@ -490,21 +538,24 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap * {@inheritDoc} */ @Override - public long computeIfPresent(final long k, + public long computeIfPresent( + final long k, final java.util.function.BiFunction<? super Long, ? super Long, ? extends Long> remappingFunction) { java.util.Objects.requireNonNull(remappingFunction); final long pos = find(k); - if (pos < 0) + if (pos < 0) { return defRetValue; - final Long newValue = remappingFunction.apply(Long.valueOf(k), Long.valueOf(value.get(pos))); + } + final Long newValue = remappingFunction.apply(k, value.get(pos)); if (newValue == null) { - if (((k) == (0))) + if (((k) == 0)) { removeNullEntry(); - else + } else { removeEntry(pos); + } return defRetValue; } - long newVal = (newValue).longValue(); + long newVal = newValue; value.set(pos, newVal); return newVal; } @@ -513,22 +564,24 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap * {@inheritDoc} */ @Override - public long compute(final long k, + public long compute( + final long k, final java.util.function.BiFunction<? super Long, ? super Long, ? extends Long> remappingFunction) { java.util.Objects.requireNonNull(remappingFunction); final long pos = find(k); final Long newValue = - remappingFunction.apply(Long.valueOf(k), pos >= 0 ? Long.valueOf(value.get(pos)) : null); + remappingFunction.apply(k, pos >= 0 ? value.get(pos) : null); if (newValue == null) { if (pos >= 0) { - if (((k) == (0))) + if (((k) == 0)) { removeNullEntry(); - else + } else { removeEntry(pos); + } } return defRetValue; } - long newVal = (newValue).longValue(); + long newVal = newValue; if (pos < 0) { insert(-pos - 1, k, newVal); return newVal; @@ -544,24 +597,21 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap public long merge(final long k, final long v, final java.util.function.BiFunction<? super Long, ? super Long, ? extends Long> remappingFunction) { java.util.Objects.requireNonNull(remappingFunction); - final long pos = find(k); if (pos < 0) { - if (pos < 0) - insert(-pos - 1, k, v); - else - value.set(pos, v); + insert(-pos - 1, k, v); return v; } - final Long newValue = remappingFunction.apply(Long.valueOf(value.get(pos)), Long.valueOf(v)); + final Long newValue = remappingFunction.apply(value.get(pos), v); if (newValue == null) { - if (((k) == (0))) + if (((k) == 0)) { removeNullEntry(); - else + } else { removeEntry(pos); + } return defRetValue; } - long newVal = (newValue).longValue(); + long newVal = newValue; value.set(pos, newVal); return newVal; } @@ -575,11 +625,11 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap */ @Override public void clear() { - if (size.get() == 0) + if (size.get() == 0) { return; + } size.set(0); containsNullKey = false; - // TODO: Arrays.fill(key, (0)); } @Override @@ -653,7 +703,7 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap @Deprecated @Override public Long getKey() { - return Long.valueOf(key.get(index)); + return key.get(index); } /** @@ -664,7 +714,7 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap @Deprecated @Override public Long getValue() { - return Long.valueOf(value.get(index)); + return value.get(index); } /** @@ -675,14 +725,15 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap @Deprecated @Override public Long setValue(final Long v) { - return Long.valueOf(setValue((v).longValue())); + return setValue((v).longValue()); } @SuppressWarnings("unchecked") @Override public boolean equals(final Object o) { - if (!(o instanceof Map.Entry)) + if (!(o instanceof Map.Entry)) { return false; + } Map.Entry<Long, Long> e = (Map.Entry<Long, Long>) o; return ((key.get(index)) == ((e.getKey()).longValue())) && ((value.get(index)) == ((e.getValue()).longValue())); @@ -737,8 +788,9 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap } public long nextEntry() { - if (!hasNext()) + if (!hasNext()) { throw new NoSuchElementException(); + } c--; if (mustReturnNullKey) { mustReturnNullKey = false; @@ -748,14 +800,16 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap if (--pos < 0) { // We are just enumerating elements from the wrapped list. last = Integer.MIN_VALUE; - final long k = wrapped.getLong((int) -pos - 1); // TODO: check if -pos - 1 is correct + final long k = wrapped.getLong((int) -pos - 1); long p = (int) HashCommon.mix((k)) & mask; - while (!((k) == (key.get(p)))) + while (!(k == (key.get(p)))) { p = (p + 1) & mask; + } return p; } - if (!((key.get(pos)) == (0))) + if (!(key.get(pos) == 0)) { return last = pos; + } } } @@ -771,11 +825,12 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap last = Integer.MIN_VALUE; final long k = wrapped.getLong((int) -pos - 1); // TODO: check if -pos - 1 is correct long p = (int) HashCommon.mix((k)) & mask; - while (!((k) == (key.get(p)))) + while (!(k == (key.get(p)))) { p = (p + 1) & mask; + } acceptOnIndex(action, p); c--; - } else if (!((key.get(pos)) == (0))) { + } else if (!(key.get(pos) == 0)) { acceptOnIndex(action, last = pos); c--; } @@ -795,18 +850,20 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap for (;;) { pos = ((last = pos) + 1) & mask; for (;;) { - if (((curr = key.get(pos)) == (0))) { + if (((curr = key.get(pos)) == 0)) { key.set(last, 0L); return; } slot = (int) HashCommon.mix((curr)) & mask; - if (last <= pos ? last >= slot || slot > pos : last >= slot && slot > pos) + if (last <= pos ? last >= slot || slot > pos : last >= slot && slot > pos) { break; + } pos = (pos + 1) & mask; } if (pos < last) { // Wrapped entry. - if (wrapped == null) + if (wrapped == null) { wrapped = new LongArrayList(2); + } wrapped.add(key.get(pos)); } key.set(last, curr); @@ -815,17 +872,16 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap } public void remove() { - if (last == -1) + if (last == -1) { throw new IllegalStateException(); + } if (last == n) { containsNullKey = false; - } else if (pos >= 0) + } else if (pos >= 0) { shiftKeys(last); - else { + } else { // We're removing wrapped entries. - Long2LongOpenHashDataMap.this.remove(wrapped.getLong((int) -pos - 1)); // TODO: check if - // -pos - 1 - // is correct + Long2LongOpenHashDataMap.this.remove(wrapped.getLong((int) -pos - 1)); last = -1; // Note that we must not decrement size return; } @@ -835,8 +891,9 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap public int skip(final int n) { int i = n; - while (i-- != 0 && hasNext()) + while (i-- != 0 && hasNext()) { nextEntry(); + } return n - i - 1; } } @@ -853,7 +910,7 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap // forEachRemaining inherited from MapIterator superclass. @Override - final void acceptOnIndex(final Consumer<? super Long2LongMap.Entry> action, final long index) { + void acceptOnIndex(final Consumer<? super Long2LongMap.Entry> action, final long index) { action.accept(entry = new Long2LongOpenHashDataMap.MapEntry(index)); } @@ -877,7 +934,7 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap // forEachRemaining inherited from MapIterator superclass. @Override - final void acceptOnIndex(final Consumer<? super Long2LongMap.Entry> action, final long index) { + void acceptOnIndex(final Consumer<? super Long2LongMap.Entry> action, final long index) { entry.index = index; action.accept(entry); } @@ -924,7 +981,7 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap return true; } while (pos < max) { - if (!((key.get(pos)) == (0))) { + if (!(key.get(pos) == 0)) { ++c; acceptOnIndex(action, pos++); return true; @@ -941,7 +998,7 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap acceptOnIndex(action, n); } while (pos < max) { - if (!((key.get(pos)) == (0))) { + if (!(key.get(pos) == 0)) { acceptOnIndex(action, pos); ++c; } @@ -964,11 +1021,13 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap } public SplitType trySplit() { - if (pos >= max - 1) + if (pos >= max - 1) { return null; + } long retLen = (max - pos) >> 1; - if (retLen <= 1) + if (retLen <= 1) { return null; + } long myNewPos = pos + retLen; long retPos = pos; long retMax = myNewPos; @@ -984,10 +1043,12 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap } public long skip(long n) { - if (n < 0) + if (n < 0) { throw new IllegalArgumentException("Argument must be nonnegative: " + n); - if (n == 0) + } + if (n == 0) { return 0; + } long skipped = 0; if (mustReturnNull) { mustReturnNull = false; @@ -995,7 +1056,7 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap --n; } while (pos < max && n > 0) { - if (!((key.get(pos++)) == (0))) { + if (!(key.get(pos++) == 0)) { ++skipped; --n; } @@ -1023,12 +1084,12 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap } @Override - final void acceptOnIndex(final Consumer<? super Long2LongMap.Entry> action, final long index) { + void acceptOnIndex(final Consumer<? super Long2LongMap.Entry> action, final long index) { action.accept(new Long2LongOpenHashDataMap.MapEntry(index)); } @Override - final Long2LongOpenHashDataMap.EntrySpliterator makeForSplit(long pos, long max, + Long2LongOpenHashDataMap.EntrySpliterator makeForSplit(long pos, long max, boolean mustReturnNull) { return new Long2LongOpenHashDataMap.EntrySpliterator(pos, max, mustReturnNull, true); } @@ -1060,46 +1121,56 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap @Override public boolean contains(final Object o) { - if (!(o instanceof Map.Entry)) + if (!(o instanceof Map.Entry)) { return false; + } final Map.Entry<?, ?> e = (Map.Entry<?, ?>) o; - if (e.getKey() == null || !(e.getKey() instanceof Long)) + if (e.getKey() == null || !(e.getKey() instanceof Long)) { return false; - if (e.getValue() == null || !(e.getValue() instanceof Long)) + } + if (e.getValue() == null || !(e.getValue() instanceof Long)) { return false; - final long k = ((Long) (e.getKey())).longValue(); - final long v = ((Long) (e.getValue())).longValue(); - if (((k) == (0))) + } + final long k = (Long) (e.getKey()); + final long v = (Long) (e.getValue()); + if (((k) == 0)) { return Long2LongOpenHashDataMap.this.containsNullKey && ((value.get(n)) == (v)); + } long curr; long pos; // The starting point. - if (((curr = key.get(pos = (int) HashCommon.mix((k)) & mask)) == (0))) + if (((curr = key.get(pos = (int) HashCommon.mix((k)) & mask)) == 0)) { return false; - if (((k) == (curr))) + } + if (((k) == (curr))) { return ((value.get(pos)) == (v)); + } // There's always an unused entry. while (true) { - if (((curr = key.get(pos = (pos + 1) & mask)) == (0))) + if (((curr = key.get(pos = (pos + 1) & mask)) == 0)) { return false; - if (((k) == (curr))) + } + if (((k) == (curr))) { return ((value.get(pos)) == (v)); + } } } @Override - public boolean remove(final Object o) { - if (!(o instanceof Map.Entry)) + if (!(o instanceof Map.Entry)) { return false; + } final Map.Entry<?, ?> e = (Map.Entry<?, ?>) o; - if (e.getKey() == null || !(e.getKey() instanceof Long)) + if (e.getKey() == null || !(e.getKey() instanceof Long)) { return false; - if (e.getValue() == null || !(e.getValue() instanceof Long)) + } + if (e.getValue() == null || !(e.getValue() instanceof Long)) { return false; - final long k = ((Long) (e.getKey())).longValue(); - final long v = ((Long) (e.getValue())).longValue(); - if (((k) == (0))) { + } + final long k = (Long) e.getKey(); + final long v = (Long) e.getValue(); + if (((k) == 0)) { if (containsNullKey && ((value.get(n)) == (v))) { removeNullEntry(); return true; @@ -1109,8 +1180,9 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap long curr; long pos; // The starting point. - if (((curr = key.get(pos = (int) HashCommon.mix((k)) & mask)) == (0))) + if (((curr = key.get(pos = (int) HashCommon.mix((k)) & mask)) == 0)) { return false; + } if (((curr) == (k))) { if (((value.get(pos)) == (v))) { removeEntry(pos); @@ -1119,8 +1191,9 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap return false; } while (true) { - if (((curr = key.get(pos = (pos + 1) & mask)) == (0))) + if (((curr = key.get(pos = (pos + 1) & mask)) == 0)) { return false; + } if (((curr) == (k))) { if (((value.get(pos)) == (v))) { removeEntry(pos); @@ -1140,11 +1213,14 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap */ @Override public void forEach(final Consumer<? super Long2LongMap.Entry> consumer) { - if (containsNullKey) + if (containsNullKey) { consumer.accept(new AbstractLong2LongMap.BasicEntry(key.get(n), value.get(n))); - for (long pos = n; pos-- != 0;) - if (!((key.get(pos)) == (0))) + } + for (long pos = n; pos-- != 0;) { + if (!(key.get(pos) == 0)) { consumer.accept(new AbstractLong2LongMap.BasicEntry(key.get(pos), value.get(pos))); + } + } } /** @@ -1155,17 +1231,19 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap if (containsNullKey) { consumer.accept(new AbstractLong2LongMap.BasicEntry(key.get(n), value.get(n))); } - for (long pos = n; pos-- != 0;) - if (!((key.get(pos)) == (0))) { + for (long pos = n; pos-- != 0;) { + if (!(key.get(pos) == 0)) { consumer.accept(new AbstractLong2LongMap.BasicEntry(key.get(pos), value.get(pos))); } + } } } @Override public FastEntrySet long2LongEntrySet() { - if (entries == null) + if (entries == null) { entries = new Long2LongOpenHashDataMap.MapEntrySet(); + } return entries; } @@ -1188,7 +1266,7 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap // methods // avoids the boxing/unboxing @Override - final void acceptOnIndex(final java.util.function.LongConsumer action, final long index) { + void acceptOnIndex(final java.util.function.LongConsumer action, final long index) { action.accept(key.get(index)); } @@ -1218,12 +1296,13 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap } @Override - final void acceptOnIndex(final java.util.function.LongConsumer action, final long index) { + void acceptOnIndex(final java.util.function.LongConsumer action, final long index) { action.accept(key.get(index)); } @Override - final Long2LongOpenHashDataMap.KeySpliterator makeForSplit(long pos, long max, + Long2LongOpenHashDataMap.KeySpliterator makeForSplit( + long pos, long max, boolean mustReturnNull) { return new Long2LongOpenHashDataMap.KeySpliterator(pos, max, mustReturnNull, true); } @@ -1245,12 +1324,14 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap */ @Override public void forEach(final java.util.function.LongConsumer consumer) { - if (containsNullKey) + if (containsNullKey) { consumer.accept(key.get(n)); + } for (long pos = n; pos-- != 0;) { final long k = key.get(pos); - if (!((k) == (0))) + if (!(k == 0)) { consumer.accept(k); + } } } @@ -1279,8 +1360,9 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap @Override public LongSet keySet() { - if (keys == null) + if (keys == null) { keys = new Long2LongOpenHashDataMap.KeySet(); + } return keys; } @@ -1303,7 +1385,7 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap // methods // avoids the boxing/unboxing @Override - final void acceptOnIndex(final java.util.function.LongConsumer action, final long index) { + void acceptOnIndex(final java.util.function.LongConsumer action, final long index) { action.accept(value.get(index)); } @@ -1333,12 +1415,12 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap } @Override - final void acceptOnIndex(final java.util.function.LongConsumer action, final long index) { + void acceptOnIndex(final java.util.function.LongConsumer action, final long index) { action.accept(value.get(index)); } @Override - final Long2LongOpenHashDataMap.ValueSpliterator makeForSplit(long pos, long max, + Long2LongOpenHashDataMap.ValueSpliterator makeForSplit(long pos, long max, boolean mustReturnNull) { return new Long2LongOpenHashDataMap.ValueSpliterator(pos, max, mustReturnNull, true); } @@ -1361,11 +1443,14 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap /** {@inheritDoc} */ @Override public void forEach(final java.util.function.LongConsumer consumer) { - if (containsNullKey) + if (containsNullKey) { consumer.accept(value.get(n)); - for (long pos = n; pos-- != 0;) - if (!((key.get(pos)) == (0))) + } + for (long pos = n; pos-- != 0;) { + if (!(key.get(pos) == 0)) { consumer.accept(value.get(pos)); + } + } } @Override @@ -1414,7 +1499,7 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap * <p> * This method is useful when reusing maps. {@linkplain #clear() Clearing a map} leaves the table * size untouched. If you are reusing a map many times, you can call this method with a typical - * size to avoid keeping around a very large table just because of a few large transient maps. + * size to avoid keeping around a very large table just because of a few large maps. * * @param n the threshold for the trimming. * @return true if there was enough memory to trim the map. @@ -1448,10 +1533,10 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap final AbstractDataList<Long> newValue = valueSupplier.get(); long i = n, pos; for (long j = realSize(); j-- != 0;) { - while (((key.get(--i)) == (0))); - if (!((newKey - .get(pos = (int) mix((key.get(i))) & mask)) == (0))) - while (!((newKey.get(pos = (pos + 1) & mask)) == (0))); + while ((key.get(--i) == 0)); + if (!(newKey.get(pos = (int) mix(key.get(i)) & mask) == 0)) { + while (!(newKey.get(pos = (pos + 1) & mask) == 0)); + } newKey.set(pos, key.get(i)); newValue.set(pos, value.get(i)); } @@ -1476,16 +1561,18 @@ public class Long2LongOpenHashDataMap extends AbstractLong2LongMap public int hashCode() { int h = 0; for (long j = realSize(), i = 0, t = 0; j-- != 0;) { - while (((key.get(i)) == (0))) + while (((key.get(i)) == 0)) { i++; + } t = HashCommon.long2int(key.get(i)); t ^= HashCommon.long2int(value.get(i)); h += t; i++; } // Zero / null keys have hash zero. - if (containsNullKey) + if (containsNullKey) { h += HashCommon.long2int(value.get(n)); + } return h; } } diff --git a/baremaps-core/src/main/java/org/apache/baremaps/database/collection/Long2LongPackedOpenHashDataMap.java b/baremaps-core/src/main/java/org/apache/baremaps/database/collection/Long2LongPackedOpenHashDataMap.java index cda78863..7979e2c4 100644 --- a/baremaps-core/src/main/java/org/apache/baremaps/database/collection/Long2LongPackedOpenHashDataMap.java +++ b/baremaps-core/src/main/java/org/apache/baremaps/database/collection/Long2LongPackedOpenHashDataMap.java @@ -77,8 +77,6 @@ public class Long2LongPackedOpenHashDataMap extends AbstractLong2LongMap */ protected LongCollection values; - private Supplier<AbstractDataList<Long>> listSupplier; - /** * Creates a new hash map. * @@ -90,10 +88,12 @@ public class Long2LongPackedOpenHashDataMap extends AbstractLong2LongMap */ public Long2LongPackedOpenHashDataMap(final long expected, final float f, final Supplier<DataMap<Pair<Long, Long>>> indexSupplier) { - if (f <= 0 || f >= 1) + if (f <= 0 || f >= 1) { throw new IllegalArgumentException("Load factor must be greater than 0 and smaller than 1"); - if (expected < 0) + } + if (expected < 0) { throw new IllegalArgumentException("The expected number of elements must be nonnegative"); + } this.f = f; this.minN = n = bigArraySize(expected, f); this.mask = n - 1; @@ -108,23 +108,26 @@ public class Long2LongPackedOpenHashDataMap extends AbstractLong2LongMap private void ensureCapacity(final long capacity) { final long needed = bigArraySize(capacity, f); - if (needed > n) + if (needed > n) { rehash(needed); + } } private void tryCapacity(final long capacity) { final long needed = Math.min(1 << 30, Math.max(2, HashCommon.nextPowerOfTwo((long) Math.ceil(capacity / f)))); - if (needed > n) + if (needed > n) { rehash(needed); + } } private long removeEntry(final long pos) { final long oldValue = index.get(pos).right(); size.decrementAndGet(); shiftKeys(pos); - if (n > minN && size.get() < maxFill / 4 && n > DEFAULT_INITIAL_SIZE) + if (n > minN && size.get() < maxFill / 4 && n > DEFAULT_INITIAL_SIZE) { rehash(n / 2); + } return oldValue; } @@ -132,47 +135,52 @@ public class Long2LongPackedOpenHashDataMap extends AbstractLong2LongMap containsNullKey = false; final long oldValue = index.get(n).right(); size.decrementAndGet(); - if (n > minN && size.get() < maxFill / 4 && n > DEFAULT_INITIAL_SIZE) + if (n > minN && size.get() < maxFill / 4 && n > DEFAULT_INITIAL_SIZE) { rehash(n / 2); + } return oldValue; } @Override public void putAll(Map<? extends Long, ? extends Long> m) { - if (f <= .5) - ensureCapacity(m.size()); // The resulting map will be sized for m.size() elements - else - tryCapacity(size() + m.size()); // The resulting map will be tentatively sized for size() + - // m.size() - // elements + if (f <= .5) { + ensureCapacity(m.size()); + } else { + tryCapacity(size() + m.size()); + } super.putAll(m); } private long find(final long k) { - if (((k) == (0))) + if (((k) == 0)) { return containsNullKey ? n : -(n + 1); + } long curr; long pos; - // The starting point. - if (((curr = index.get(pos = HashCommon.mix((k)) & mask).left()) == (0))) + if (((curr = index.get(pos = HashCommon.mix((k)) & mask).left()) == 0)) { return -(pos + 1); - if (((k) == (curr))) + } + if (((k) == (curr))) { return pos; - // There's always an unused entry. + } while (true) { - if (((curr = index.get(pos = (pos + 1) & mask).left()) == (0))) + if (((curr = index.get(pos = (pos + 1) & mask).left()) == 0)) { return -(pos + 1); - if (((k) == (curr))) + } + if (((k) == (curr))) { return pos; + } } } private void insert(final long pos, final long k, final long v) { - if (pos == n) + if (pos == n) { containsNullKey = true; + } index.put(pos, new Pair<>(k, v)); - if (size.getAndIncrement() >= maxFill) + if (size.getAndIncrement() >= maxFill) { rehash(bigArraySize(size.get() + 1, f)); + } } @Override @@ -208,25 +216,30 @@ public class Long2LongPackedOpenHashDataMap extends AbstractLong2LongMap */ public long addTo(final long k, final long incr) { long pos; - if (((k) == (0))) { - if (containsNullKey) + if (((k) == 0)) { + if (containsNullKey) { return addToValue(n, incr); + } pos = n; containsNullKey = true; } else { long curr; // The starting point. - if (!((curr = index.get(pos = HashCommon.mix((k)) & mask).left()) == (0))) { - if (((curr) == (k))) + if (!((curr = index.get(pos = HashCommon.mix((k)) & mask).left()) == 0)) { + if ((curr == k)) { return addToValue(pos, incr); - while (!((curr = index.get(pos = (pos + 1) & mask).left()) == (0))) - if (((curr) == (k))) + } + while (!((curr = index.get(pos = (pos + 1) & mask).left()) == 0)) { + if ((curr == k)) { return addToValue(pos, incr); + } + } } } index.put(pos, new Pair<>(k, defRetValue + incr)); - if (size.incrementAndGet() >= maxFill) + if (size.incrementAndGet() >= maxFill) { rehash(bigArraySize(size.get() + 1, f)); + } return defRetValue; } @@ -243,13 +256,14 @@ public class Long2LongPackedOpenHashDataMap extends AbstractLong2LongMap for (;;) { pos = ((last = pos) + 1) & mask; for (;;) { - if (((curr = index.get(pos).left()) == (0))) { + if (((curr = index.get(pos).left()) == 0)) { index.put(last, new Pair<>(curr, 0L)); return; } slot = HashCommon.mix((curr)) & mask; - if (last <= pos ? last >= slot || slot > pos : last >= slot && slot > pos) + if (last <= pos ? last >= slot || slot > pos : last >= slot && slot > pos) { break; + } pos = (pos + 1) & mask; } index.put(last, new Pair<>(curr, index.get(pos).right())); @@ -259,75 +273,93 @@ public class Long2LongPackedOpenHashDataMap extends AbstractLong2LongMap @Override public long remove(final long k) { - if (((k) == (0))) { - if (containsNullKey) + if (((k) == 0)) { + if (containsNullKey) { return removeNullEntry(); + } return defRetValue; } long curr; long pos; // The starting point. - if (((curr = index.get(pos = HashCommon.mix((k)) & mask).left()) == (0))) + if (((curr = index.get(pos = HashCommon.mix((k)) & mask).left()) == 0)) { return defRetValue; - if (((k) == (curr))) + } + if (((k) == (curr))) { return removeEntry(pos); + } while (true) { - if (((curr = index.get(pos = (pos + 1) & mask).left()) == (0))) + if (((curr = index.get(pos = (pos + 1) & mask).left()) == 0)) { return defRetValue; - if (((k) == (curr))) + } + if (((k) == (curr))) { return removeEntry(pos); + } } } @Override public long get(final long k) { - if (((k) == (0))) + if (((k) == 0)) { return containsNullKey ? index.get(n).right() : defRetValue; + } long curr; long pos; // The starting point. - if (((curr = index.get(pos = HashCommon.mix((k)) & mask).left()) == (0))) + if (((curr = index.get(pos = HashCommon.mix((k)) & mask).left()) == 0)) { return defRetValue; - if (((k) == (curr))) + } + if (((k) == (curr))) { return index.get(pos).right(); + } // There's always an unused entry. while (true) { - if (((curr = index.get(pos = (pos + 1) & mask).left()) == (0))) + if (((curr = index.get(pos = (pos + 1) & mask).left()) == 0)) { return defRetValue; - if (((k) == (curr))) + } + if (((k) == (curr))) { return index.get(pos).right(); + } } } @Override public boolean containsKey(final long k) { - if (((k) == (0))) + if (((k) == 0)) { return containsNullKey; + } long curr; long pos; // The starting point. - if (((curr = index.get(pos = HashCommon.mix((k)) & mask).left()) == (0))) + if (((curr = index.get(pos = HashCommon.mix((k)) & mask).left()) == 0)) { return false; - if (((k) == (curr))) + } + if (((k) == (curr))) { return true; + } // There's always an unused entry. while (true) { - if (((curr = index.get(pos = (pos + 1) & mask).left()) == (0))) + if (((curr = index.get(pos = (pos + 1) & mask).left()) == 0)) { return false; - if (((k) == (curr))) + } + if (((k) == (curr))) { return true; + } } } @Override public boolean containsValue(final long v) { - if (containsNullKey && ((index.get(n).right()) == (v))) + if (containsNullKey && ((index.get(n).right()) == (v))) { return true; - for (long i = n; i-- != 0;) - if (!((index.get(i).left()) == (0)) && ((index.get(i).right()) == (v))) + } + for (long i = n; i-- != 0;) { + if (!((index.get(i).left()) == 0) && ((index.get(i).right()) == (v))) { return true; + } + } return false; } @@ -337,21 +369,26 @@ public class Long2LongPackedOpenHashDataMap extends AbstractLong2LongMap @Override public long getOrDefault(final long k, final long defaultValue) { - if (((k) == (0))) + if (((k) == 0)) { return containsNullKey ? index.get(n).right() : defaultValue; + } long curr; long pos; // The starting point. - if (((curr = index.get(pos = HashCommon.mix((k)) & mask).left()) == (0))) + if (((curr = index.get(pos = HashCommon.mix((k)) & mask).left()) == 0)) { return defaultValue; - if (((k) == (curr))) + } + if (((k) == (curr))) { return index.get(pos).right(); + } // There's always an unused entry. while (true) { - if (((curr = index.get(pos = (pos + 1) & mask).left()) == (0))) + if (((curr = index.get(pos = (pos + 1) & mask).left()) == 0)) { return defaultValue; - if (((k) == (curr))) + } + if (((k) == (curr))) { return index.get(pos).right(); + } } } @@ -361,8 +398,9 @@ public class Long2LongPackedOpenHashDataMap extends AbstractLong2LongMap @Override public long putIfAbsent(final long k, final long v) { final long pos = find(k); - if (pos >= 0) + if (pos >= 0) { return index.get(pos).right(); + } insert(-pos - 1, k, v); return defRetValue; } @@ -373,7 +411,7 @@ public class Long2LongPackedOpenHashDataMap extends AbstractLong2LongMap @Override public boolean remove(final long k, final long v) { - if (((k) == (0))) { + if (((k) == 0)) { if (containsNullKey && ((v) == (index.get(n).right()))) { removeNullEntry(); return true; @@ -383,15 +421,17 @@ public class Long2LongPackedOpenHashDataMap extends AbstractLong2LongMap long curr; long pos; // The starting point. - if (((curr = index.get(pos = HashCommon.mix((k)) & mask).left()) == (0))) + if (((curr = index.get(pos = HashCommon.mix((k)) & mask).left()) == 0)) { return false; + } if (((k) == (curr)) && ((v) == (index.get(pos).right()))) { removeEntry(pos); return true; } while (true) { - if (((curr = index.get(pos = (pos + 1) & mask).left()) == (0))) + if (((curr = index.get(pos = (pos + 1) & mask).left()) == 0)) { return false; + } if (((k) == (curr)) && ((v) == (index.get(pos).right()))) { removeEntry(pos); return true; @@ -405,8 +445,9 @@ public class Long2LongPackedOpenHashDataMap extends AbstractLong2LongMap @Override public boolean replace(final long k, final long oldValue, final long v) { final long pos = find(k); - if (pos < 0 || !((oldValue) == (index.get(pos).right()))) + if (pos < 0 || !((oldValue) == (index.get(pos).right()))) { return false; + } index.put(pos, new Pair<>(k, v)); return true; } @@ -417,8 +458,9 @@ public class Long2LongPackedOpenHashDataMap extends AbstractLong2LongMap @Override public long replace(final long k, final long v) { final long pos = find(k); - if (pos < 0) + if (pos < 0) { return defRetValue; + } final long oldValue = index.get(pos).right(); index.put(pos, new Pair<>(k, v)); return oldValue; @@ -432,8 +474,9 @@ public class Long2LongPackedOpenHashDataMap extends AbstractLong2LongMap final java.util.function.LongUnaryOperator mappingFunction) { java.util.Objects.requireNonNull(mappingFunction); final long pos = find(k); - if (pos >= 0) + if (pos >= 0) { return index.get(pos).right(); + } final long newValue = mappingFunction.applyAsLong(k); insert(-pos - 1, k, newValue); return newValue; @@ -446,10 +489,12 @@ public class Long2LongPackedOpenHashDataMap extends AbstractLong2LongMap public long computeIfAbsent(final long key, final Long2LongFunction mappingFunction) { java.util.Objects.requireNonNull(mappingFunction); final long pos = find(key); - if (pos >= 0) + if (pos >= 0) { return index.get(pos).right(); - if (!mappingFunction.containsKey(key)) + } + if (!mappingFunction.containsKey(key)) { return defRetValue; + } final long newValue = mappingFunction.get(key); insert(-pos - 1, key, newValue); return newValue; @@ -463,12 +508,14 @@ public class Long2LongPackedOpenHashDataMap extends AbstractLong2LongMap final java.util.function.LongFunction<? extends Long> mappingFunction) { java.util.Objects.requireNonNull(mappingFunction); final long pos = find(k); - if (pos >= 0) + if (pos >= 0) { return index.get(pos).right(); + } final Long newValue = mappingFunction.apply(k); - if (newValue == null) + if (newValue == null) { return defRetValue; - final long v = (newValue).longValue(); + } + final long v = newValue; insert(-pos - 1, k, v); return v; } @@ -481,18 +528,20 @@ public class Long2LongPackedOpenHashDataMap extends AbstractLong2LongMap final java.util.function.BiFunction<? super Long, ? super Long, ? extends Long> remappingFunction) { java.util.Objects.requireNonNull(remappingFunction); final long pos = find(k); - if (pos < 0) + if (pos < 0) { return defRetValue; + } final Long newValue = - remappingFunction.apply(Long.valueOf(k), Long.valueOf(index.get(pos).right())); + remappingFunction.apply(k, index.get(pos).right()); if (newValue == null) { - if (((k) == (0))) + if (((k) == 0)) { removeNullEntry(); - else + } else { removeEntry(pos); + } return defRetValue; } - long newVal = (newValue).longValue(); + long newVal = newValue; index.put(pos, new Pair<>(k, newVal)); return newVal; } @@ -506,24 +555,23 @@ public class Long2LongPackedOpenHashDataMap extends AbstractLong2LongMap java.util.Objects.requireNonNull(remappingFunction); final long pos = find(k); final Long newValue = - remappingFunction.apply(Long.valueOf(k), - pos >= 0 ? Long.valueOf(index.get(pos).right()) : null); + remappingFunction.apply(k, pos >= 0 ? index.get(pos).right() : null); if (newValue == null) { if (pos >= 0) { - if (((k) == (0))) + if (((k) == 0)) { removeNullEntry(); - else + } else { removeEntry(pos); + } } return defRetValue; } - long newVal = (newValue).longValue(); if (pos < 0) { - insert(-pos - 1, k, newVal); - return newVal; + insert(-pos - 1, k, newValue); + return newValue; } - index.put(pos, new Pair<>(k, newVal)); - return newVal; + index.put(pos, new Pair<>(k, newValue)); + return newValue; } /** @@ -536,22 +584,20 @@ public class Long2LongPackedOpenHashDataMap extends AbstractLong2LongMap final long pos = find(k); if (pos < 0) { - if (pos < 0) - insert(-pos - 1, k, v); - else - index.put(pos, new Pair<>(k, v)); + insert(-pos - 1, k, v); return v; } final Long newValue = - remappingFunction.apply(Long.valueOf(index.get(pos).right()), Long.valueOf(v)); + remappingFunction.apply(index.get(pos).right(), v); if (newValue == null) { - if (((k) == (0))) + if (((k) == 0)) { removeNullEntry(); - else + } else { removeEntry(pos); + } return defRetValue; } - long newVal = (newValue).longValue(); + long newVal = newValue; index.put(pos, new Pair<>(k, newVal)); return newVal; } @@ -565,11 +611,12 @@ public class Long2LongPackedOpenHashDataMap extends AbstractLong2LongMap */ @Override public void clear() { - if (size.get() == 0) + if (size.get() == 0) { return; + } size.set(0); containsNullKey = false; - // TODO: Arrays.fill(key, (0)); + // TODO: Arrays.fill(key, 0); } @Override @@ -645,7 +692,7 @@ public class Long2LongPackedOpenHashDataMap extends AbstractLong2LongMap @Deprecated @Override public Long getKey() { - return Long.valueOf(Long2LongPackedOpenHashDataMap.this.index.get(index).left()); + return Long2LongPackedOpenHashDataMap.this.index.get(index).left(); } /** @@ -656,7 +703,7 @@ public class Long2LongPackedOpenHashDataMap extends AbstractLong2LongMap @Deprecated @Override public Long getValue() { - return Long.valueOf(Long2LongPackedOpenHashDataMap.this.index.get(index).right()); + return Long2LongPackedOpenHashDataMap.this.index.get(index).right(); } /** @@ -667,14 +714,15 @@ public class Long2LongPackedOpenHashDataMap extends AbstractLong2LongMap @Deprecated @Override public Long setValue(final Long v) { - return Long.valueOf(setValue((v).longValue())); + return setValue(v); } @SuppressWarnings("unchecked") @Override public boolean equals(final Object o) { - if (!(o instanceof Map.Entry)) + if (!(o instanceof Map.Entry)) { return false; + } Map.Entry<Long, Long> e = (Map.Entry<Long, Long>) o; var pair = Long2LongPackedOpenHashDataMap.this.index.get(index); return ((pair.left()) == ((e.getKey()).longValue())) @@ -732,8 +780,9 @@ public class Long2LongPackedOpenHashDataMap extends AbstractLong2LongMap } public long nextEntry() { - if (!hasNext()) + if (!hasNext()) { throw new NoSuchElementException(); + } c--; if (mustReturnNullKey) { mustReturnNullKey = false; @@ -745,12 +794,14 @@ public class Long2LongPackedOpenHashDataMap extends AbstractLong2LongMap last = Integer.MIN_VALUE; final long k = wrapped.getLong((int) -pos - 1); // TODO: check if -pos - 1 is correct long p = (int) HashCommon.mix((k)) & mask; - while (!((k) == (index.get(p).left()))) + while (!((k) == (index.get(p).left()))) { p = (p + 1) & mask; + } return p; } - if (!((index.get(pos).left()) == (0))) + if (!((index.get(pos).left()) == 0)) { return last = pos; + } } } @@ -766,11 +817,12 @@ public class Long2LongPackedOpenHashDataMap extends AbstractLong2LongMap last = Integer.MIN_VALUE; final long k = wrapped.getLong((int) -pos - 1); // TODO: check if -pos - 1 is correct long p = (int) HashCommon.mix((k)) & mask; - while (!((k) == (index.get(p).left()))) + while (!((k) == (index.get(p).left()))) { p = (p + 1) & mask; + } acceptOnIndex(action, p); c--; - } else if (!((index.get(pos).left()) == (0))) { + } else if (!((index.get(pos).left()) == 0)) { acceptOnIndex(action, last = pos); c--; } @@ -790,19 +842,21 @@ public class Long2LongPackedOpenHashDataMap extends AbstractLong2LongMap for (;;) { pos = ((last = pos) + 1) & mask; for (;;) { - if (((curr = index.get(pos).left()) == (0))) { + if (((curr = index.get(pos).left()) == 0)) { index.put(last, new Pair<>(curr, 0L)); return; } slot = (int) HashCommon.mix((curr)) & mask; - if (last <= pos ? last >= slot || slot > pos : last >= slot && slot > pos) + if (last <= pos ? last >= slot || slot > pos : last >= slot && slot > pos) { break; + } pos = (pos + 1) & mask; } var pair = index.get(pos); if (pos < last) { // Wrapped entry. - if (wrapped == null) + if (wrapped == null) { wrapped = new LongArrayList(2); + } wrapped.add(pair.left()); } index.put(last, new Pair<>(curr, pair.right())); @@ -810,16 +864,17 @@ public class Long2LongPackedOpenHashDataMap extends AbstractLong2LongMap } public void remove() { - if (last == -1) + if (last == -1) { throw new IllegalStateException(); + } if (last == n) { containsNullKey = false; - } else if (pos >= 0) + } else if (pos >= 0) { shiftKeys(last); - else { + } else { // We're removing wrapped entries. Long2LongPackedOpenHashDataMap.this.remove(wrapped.getLong((int) -pos - 1)); // TODO: check - // if -pos - 1 + // if -pos - 1 // is correct last = -1; // Note that we must not decrement size return; @@ -830,8 +885,9 @@ public class Long2LongPackedOpenHashDataMap extends AbstractLong2LongMap public int skip(final int n) { int i = n; - while (i-- != 0 && hasNext()) + while (i-- != 0 && hasNext()) { nextEntry(); + } return n - i - 1; } } @@ -920,7 +976,7 @@ public class Long2LongPackedOpenHashDataMap extends AbstractLong2LongMap return true; } while (pos < max) { - if (!((index.get(pos).left()) == (0))) { + if (!((index.get(pos).left()) == 0)) { ++c; acceptOnIndex(action, pos++); return true; @@ -937,7 +993,7 @@ public class Long2LongPackedOpenHashDataMap extends AbstractLong2LongMap acceptOnIndex(action, n); } while (pos < max) { - if (!((index.get(pos).left()) == (0))) { + if (!((index.get(pos).left()) == 0)) { acceptOnIndex(action, pos); ++c; } @@ -960,11 +1016,13 @@ public class Long2LongPackedOpenHashDataMap extends AbstractLong2LongMap } public SplitType trySplit() { - if (pos >= max - 1) + if (pos >= max - 1) { return null; + } long retLen = (max - pos) >> 1; - if (retLen <= 1) + if (retLen <= 1) { return null; + } long myNewPos = pos + retLen; long retPos = pos; long retMax = myNewPos; @@ -980,10 +1038,12 @@ public class Long2LongPackedOpenHashDataMap extends AbstractLong2LongMap } public long skip(long n) { - if (n < 0) + if (n < 0) { throw new IllegalArgumentException("Argument must be nonnegative: " + n); - if (n == 0) + } + if (n == 0) { return 0; + } long skipped = 0; if (mustReturnNull) { mustReturnNull = false; @@ -991,7 +1051,7 @@ public class Long2LongPackedOpenHashDataMap extends AbstractLong2LongMap --n; } while (pos < max && n > 0) { - if (!((index.get(pos++).left()) == (0))) { + if (!((index.get(pos++).left()) == 0)) { ++skipped; --n; } @@ -1056,47 +1116,58 @@ public class Long2LongPackedOpenHashDataMap extends AbstractLong2LongMap @Override public boolean contains(final Object o) { - if (!(o instanceof Map.Entry)) + if (!(o instanceof Map.Entry)) { return false; + } final Map.Entry<?, ?> e = (Map.Entry<?, ?>) o; - if (e.getKey() == null || !(e.getKey() instanceof Long)) + if (e.getKey() == null || !(e.getKey() instanceof Long)) { return false; - if (e.getValue() == null || !(e.getValue() instanceof Long)) + } + if (e.getValue() == null || !(e.getValue() instanceof Long)) { return false; - final long k = ((Long) (e.getKey())).longValue(); - final long v = ((Long) (e.getValue())).longValue(); - if (((k) == (0))) + } + final long k = (Long) e.getKey(); + final long v = (Long) e.getValue(); + if (((k) == 0)) { return Long2LongPackedOpenHashDataMap.this.containsNullKey && ((index.get(n).right()) == (v)); + } long curr; long pos; // The starting point. - if (((curr = index.get(pos = (int) HashCommon.mix((k)) & mask).left()) == (0))) + if (((curr = index.get(pos = (int) HashCommon.mix((k)) & mask).left()) == 0)) { return false; - if (((k) == (curr))) + } + if (((k) == (curr))) { return ((index.get(pos).right()) == (v)); + } // There's always an unused entry. while (true) { - if (((curr = index.get(pos = (pos + 1) & mask).left()) == (0))) + if (((curr = index.get(pos = (pos + 1) & mask).left()) == 0)) { return false; - if (((k) == (curr))) + } + if (((k) == (curr))) { return ((index.get(pos).right()) == (v)); + } } } @Override public boolean remove(final Object o) { - if (!(o instanceof Map.Entry)) + if (!(o instanceof Map.Entry)) { return false; + } final Map.Entry<?, ?> e = (Map.Entry<?, ?>) o; - if (e.getKey() == null || !(e.getKey() instanceof Long)) + if (e.getKey() == null || !(e.getKey() instanceof Long)) { return false; - if (e.getValue() == null || !(e.getValue() instanceof Long)) + } + if (e.getValue() == null || !(e.getValue() instanceof Long)) { return false; - final long k = ((Long) (e.getKey())).longValue(); - final long v = ((Long) (e.getValue())).longValue(); - if (((k) == (0))) { + } + final long k = (Long) e.getKey(); + final long v = (Long) e.getValue(); + if (((k) == 0)) { if (containsNullKey && ((index.get(n).right()) == (v))) { removeNullEntry(); return true; @@ -1106,8 +1177,9 @@ public class Long2LongPackedOpenHashDataMap extends AbstractLong2LongMap long curr; long pos; // The starting point. - if (((curr = index.get(pos = (int) HashCommon.mix((k)) & mask).left()) == (0))) + if (((curr = index.get(pos = (int) HashCommon.mix((k)) & mask).left()) == 0)) { return false; + } if (((curr) == (k))) { if (((index.get(pos).right()) == (v))) { removeEntry(pos); @@ -1116,8 +1188,9 @@ public class Long2LongPackedOpenHashDataMap extends AbstractLong2LongMap return false; } while (true) { - if (((curr = index.get(pos = (pos + 1) & mask).left()) == (0))) + if (((curr = index.get(pos = (pos + 1) & mask).left()) == 0)) { return false; + } if (((curr) == (k))) { if (((index.get(pos).right()) == (v))) { removeEntry(pos); @@ -1143,8 +1216,9 @@ public class Long2LongPackedOpenHashDataMap extends AbstractLong2LongMap } for (long pos = n; pos-- != 0;) { var pair = index.get(pos); - if (!((pair.left()) == (0))) + if (!((pair.left()) == 0)) { consumer.accept(new BasicEntry(pair.left(), pair.right())); + } } } @@ -1159,7 +1233,7 @@ public class Long2LongPackedOpenHashDataMap extends AbstractLong2LongMap } for (long pos = n; pos-- != 0;) { var pair = index.get(pos); - if (!((pair.left()) == (0))) { + if (!((pair.left()) == 0)) { consumer.accept(new BasicEntry(pair.left(), pair.right())); } } @@ -1250,12 +1324,14 @@ public class Long2LongPackedOpenHashDataMap extends AbstractLong2LongMap */ @Override public void forEach(final LongConsumer consumer) { - if (containsNullKey) + if (containsNullKey) { consumer.accept(index.get(n).left()); + } for (long pos = n; pos-- != 0;) { final long k = index.get(pos).left(); - if (!((k) == (0))) + if (!((k) == 0)) { consumer.accept(k); + } } } @@ -1352,7 +1428,7 @@ public class Long2LongPackedOpenHashDataMap extends AbstractLong2LongMap @Override public LongCollection values() { - if (values == null) + if (values == null) { values = new AbstractLongCollection() { @Override public LongIterator iterator() { @@ -1372,7 +1448,7 @@ public class Long2LongPackedOpenHashDataMap extends AbstractLong2LongMap } for (long pos = n; pos-- != 0;) { var pair = index.get(pos); - if (!((pair.left()) == (0))) { + if (!((pair.left()) == 0)) { consumer.accept(pair.right()); } } @@ -1393,6 +1469,7 @@ public class Long2LongPackedOpenHashDataMap extends AbstractLong2LongMap Long2LongPackedOpenHashDataMap.this.clear(); } }; + } return values; } @@ -1424,7 +1501,7 @@ public class Long2LongPackedOpenHashDataMap extends AbstractLong2LongMap * <p> * This method is useful when reusing maps. {@linkplain #clear() Clearing a map} leaves the table * size untouched. If you are reusing a map many times, you can call this method with a typical - * size to avoid keeping around a very large table just because of a few large transient maps. + * size to avoid keeping around a very large table just because of a few large maps. * * @param n the threshold for the trimming. * @return true if there was enough memory to trim the map. @@ -1432,8 +1509,9 @@ public class Long2LongPackedOpenHashDataMap extends AbstractLong2LongMap */ public boolean trim(final long n) { final int l = HashCommon.nextPowerOfTwo((int) Math.ceil(n / f)); - if (l >= this.n || size.get() > maxFill(l, f)) + if (l >= this.n || size.get() > maxFill(l, f)) { return true; + } try { rehash(l); } catch (OutOfMemoryError cantDoIt) { @@ -1457,7 +1535,7 @@ public class Long2LongPackedOpenHashDataMap extends AbstractLong2LongMap final DataMap<Pair<Long, Long>> newIndex = indexSupplier.get(); long i = n, pos; for (long j = realSize(); j-- != 0;) { - while (index.get(--i).left() == (0)); + while (index.get(--i).left() == 0); if (!(newIndex.get(pos = HashCommon.mix(index.get(i).left()) & mask).left() == 0L)) { while (!(newIndex.get(pos = (pos + 1) & mask).left() == 0L)); } @@ -1495,8 +1573,9 @@ public class Long2LongPackedOpenHashDataMap extends AbstractLong2LongMap i++; } // Zero / null keys have hash zero. - if (containsNullKey) + if (containsNullKey) { h += HashCommon.long2int(index.get(n).right()); + } return h; } } diff --git a/baremaps-core/src/main/java/org/apache/baremaps/database/collection/Long2ObjectOpenHashDataMap.java b/baremaps-core/src/main/java/org/apache/baremaps/database/collection/Long2ObjectOpenHashDataMap.java index b030572b..7922fcbd 100644 --- a/baremaps-core/src/main/java/org/apache/baremaps/database/collection/Long2ObjectOpenHashDataMap.java +++ b/baremaps-core/src/main/java/org/apache/baremaps/database/collection/Long2ObjectOpenHashDataMap.java @@ -56,33 +56,58 @@ import java.util.function.Supplier; public class Long2ObjectOpenHashDataMap<V> extends AbstractLong2ObjectMap<V> implements DataMap<V>, Hash { - private Supplier<DataMap<Long>> keySupplier; - private Supplier<DataMap<V>> valueSupplier; - - /** The array of keys. */ - protected transient DataMap<Long> key; - /** The array of values. */ - protected transient DataMap<V> value; - /** The mask for wrapping a position counter. */ - protected transient long mask; - /** Whether this map contains the key zero. */ - protected transient boolean containsNullKey; - /** The current table size. */ - protected transient long n; - /** Threshold after which we rehash. It must be the table size times {@link #f}. */ - protected transient long maxFill; - /** We never resize below this threshold, which is the construction-time {#n}. */ - protected final transient long minN; - /** Number of entries in the set (including the key zero, if present). */ + private final Supplier<DataMap<Long>> keySupplier; + + private final Supplier<DataMap<V>> valueSupplier; + + /** + * The array of keys. + */ + protected DataMap<Long> key; + /** + * The array of values. + */ + protected DataMap<V> value; + /** + * The mask for wrapping a position counter. + */ + protected long mask; + /** + * Whether this map contains the key zero. + */ + protected boolean containsNullKey; + /** + * The current table size. + */ + protected long n; + /** + * Threshold after which we rehash. It must be the table size times {@link #f}. + */ + protected long maxFill; + /** + * We never resize below this threshold, which is the construction-time {#n}. + */ + protected final long minN; + /** + * Number of entries in the set (including the key zero, if present). + */ protected AtomicLong size = new AtomicLong();; - /** The acceptable load factor. */ + /** + * The acceptable load factor. + */ protected final float f; - /** Cached set of entries. */ - protected transient FastEntrySet<V> entries; - /** Cached set of keys. */ - protected transient LongSet keys; - /** Cached collection of values. */ - protected transient ObjectCollection<V> values; + /** + * Cached set of entries. + */ + protected FastEntrySet<V> entries; + /** + * Cached set of keys. + */ + protected LongSet keys; + /** + * Cached collection of values. + */ + protected ObjectCollection<V> values; /** * Creates a new hash map. @@ -99,10 +124,12 @@ public class Long2ObjectOpenHashDataMap<V> extends AbstractLong2ObjectMap<V> final float f, final Supplier<DataMap<Long>> keySupplier, final Supplier<DataMap<V>> valueSupplier) { - if (f <= 0 || f >= 1) + if (f <= 0 || f >= 1) { throw new IllegalArgumentException("Load factor must be greater than 0 and smaller than 1"); - if (expected < 0) + } + if (expected < 0) { throw new IllegalArgumentException("The expected number of elements must be nonnegative"); + } this.f = f; this.minN = n = bigArraySize(expected, f); this.mask = n - 1; @@ -119,15 +146,17 @@ public class Long2ObjectOpenHashDataMap<V> extends AbstractLong2ObjectMap<V> private void ensureCapacity(final long capacity) { final long needed = bigArraySize(capacity, f); - if (needed > n) + if (needed > n) { rehash(needed); + } } private void tryCapacity(final long capacity) { - final long needed = (long) Math.min(1 << 30, + final long needed = Math.min(1 << 30, Math.max(2, HashCommon.nextPowerOfTwo((long) Math.ceil(capacity / f)))); - if (needed > n) + if (needed > n) { rehash(needed); + } } private V removeEntry(final long pos) { @@ -135,8 +164,9 @@ public class Long2ObjectOpenHashDataMap<V> extends AbstractLong2ObjectMap<V> value.put(pos, null); size.decrementAndGet(); shiftKeys(pos); - if (n > minN && size.get() < maxFill / 4 && n > DEFAULT_INITIAL_SIZE) + if (n > minN && size.get() < maxFill / 4 && n > DEFAULT_INITIAL_SIZE) { rehash(n / 2); + } return oldValue; } @@ -145,48 +175,57 @@ public class Long2ObjectOpenHashDataMap<V> extends AbstractLong2ObjectMap<V> final V oldValue = value.get(n); value.put(n, null); size.decrementAndGet(); - if (n > minN && size.get() < maxFill / 4 && n > DEFAULT_INITIAL_SIZE) + if (n > minN && size.get() < maxFill / 4 && n > DEFAULT_INITIAL_SIZE) { rehash(n / 2); + } return oldValue; } @Override public void putAll(Map<? extends Long, ? extends V> m) { - if (f <= .5) + if (f <= .5) { ensureCapacity(m.size()); // The resulting map will be sized for m.size() elements - else + } else { tryCapacity(size() + m.size()); // The resulting map will be tentatively sized for size() + - // m.size() + } + // m.size() // elements super.putAll(m); } private long find(final long k) { - if (((k) == (0))) + if (((k) == 0)) { return containsNullKey ? n : -(n + 1); + } long curr; long pos; // The starting point. - if (((curr = key.get(pos = (long) HashCommon.mix((k)) & mask)) == (0))) + if (((curr = key.get(pos = HashCommon.mix((k)) & mask)) == 0)) { return -(pos + 1); - if (((k) == (curr))) + } + if (((k) == (curr))) { return pos; + } // There's always an unused entry. while (true) { - if (((curr = key.get(pos = (pos + 1) & mask)) == (0))) + if (((curr = key.get(pos = (pos + 1) & mask)) == 0)) { return -(pos + 1); - if (((k) == (curr))) + } + if (((k) == (curr))) { return pos; + } } } private void insert(final long pos, final long k, final V v) { - if (pos == n) + if (pos == n) { containsNullKey = true; + } key.put(pos, k); value.put(pos, v); - if (size.getAndIncrement() >= maxFill) + if (size.getAndIncrement() >= maxFill) { rehash(bigArraySize(size.get() + 1, f)); + } } @Override @@ -214,14 +253,15 @@ public class Long2ObjectOpenHashDataMap<V> extends AbstractLong2ObjectMap<V> for (;;) { pos = ((last = pos) + 1) & mask; for (;;) { - if (((curr = key.get(pos)) == (0))) { + if (((curr = key.get(pos)) == 0)) { key.put(last, 0L); value.put(last, null); return; } - slot = (long) HashCommon.mix((curr)) & mask; - if (last <= pos ? last >= slot || slot > pos : last >= slot && slot > pos) + slot = HashCommon.mix((curr)) & mask; + if (last <= pos ? last >= slot || slot > pos : last >= slot && slot > pos) { break; + } pos = (pos + 1) & mask; } key.put(last, curr); @@ -232,115 +272,145 @@ public class Long2ObjectOpenHashDataMap<V> extends AbstractLong2ObjectMap<V> @Override public V remove(final long k) { - if (((k) == (0))) { - if (containsNullKey) + if (((k) == 0)) { + if (containsNullKey) { return removeNullEntry(); + } return defRetValue; } long curr; long pos; // The starting point. - if (((curr = key.get(pos = (long) HashCommon.mix((k)) & mask)) == (0))) + if (((curr = key.get(pos = HashCommon.mix((k)) & mask)) == 0)) { return defRetValue; - if (((k) == (curr))) + } + if (((k) == (curr))) { return removeEntry(pos); + } while (true) { - if (((curr = key.get(pos = (pos + 1) & mask)) == (0))) + if (((curr = key.get(pos = (pos + 1) & mask)) == 0)) { return defRetValue; - if (((k) == (curr))) + } + if (((k) == (curr))) { return removeEntry(pos); + } } } @Override public V get(final long k) { - if (((k) == (0))) + if (((k) == 0)) { return containsNullKey ? value.get(n) : defRetValue; + } long curr; long pos; // The starting point. - if (((curr = key.get(pos = (long) HashCommon.mix((k)) & mask)) == (0))) + if (((curr = key.get(pos = HashCommon.mix((k)) & mask)) == 0)) { return defRetValue; - if (((k) == (curr))) + } + if (((k) == (curr))) { return value.get(pos); + } // There's always an unused entry. while (true) { - if (((curr = key.get(pos = (pos + 1) & mask)) == (0))) + if (((curr = key.get(pos = (pos + 1) & mask)) == 0)) { return defRetValue; - if (((k) == (curr))) + } + if (((k) == (curr))) { return value.get(pos); + } } } @Override public boolean containsKey(final long k) { - if (((k) == (0))) + if (((k) == 0)) { return containsNullKey; + } long curr; long pos; // The starting point. - if (((curr = key.get(pos = (long) HashCommon.mix((k)) & mask)) == (0))) + if (((curr = key.get(pos = HashCommon.mix((k)) & mask)) == 0)) { return false; - if (((k) == (curr))) + } + if (((k) == (curr))) { return true; + } // There's always an unused entry. while (true) { - if (((curr = key.get(pos = (pos + 1) & mask)) == (0))) + if (((curr = key.get(pos = (pos + 1) & mask)) == 0)) { return false; - if (((k) == (curr))) + } + if (((k) == (curr))) { return true; + } } } @Override public boolean containsValue(final Object v) { - if (containsNullKey && java.util.Objects.equals(value.get(n), v)) + if (containsNullKey && java.util.Objects.equals(value.get(n), v)) { return true; - for (long i = n; i-- != 0;) - if (!((key.get(i)) == (0)) && java.util.Objects.equals(value.get(i), v)) + } + for (long i = n; i-- != 0;) { + if (!((key.get(i)) == 0) && java.util.Objects.equals(value.get(i), v)) { return true; + } + } return false; } - /** {@inheritDoc} */ + /** + * {@inheritDoc} + */ @Override public V getOrDefault(final long k, final V defaultValue) { - if (((k) == (0))) + if (((k) == 0)) { return containsNullKey ? value.get(n) : defaultValue; + } long curr; long pos; // The starting point. - if (((curr = key.get(pos = (long) HashCommon.mix((k)) & mask)) == (0))) + if (((curr = key.get(pos = HashCommon.mix((k)) & mask)) == 0)) { return defaultValue; - if (((k) == (curr))) + } + if (((k) == (curr))) { return value.get(pos); + } // There's always an unused entry. while (true) { - if (((curr = key.get(pos = (pos + 1) & mask)) == (0))) + if (((curr = key.get(pos = (pos + 1) & mask)) == 0)) { return defaultValue; - if (((k) == (curr))) + } + if (((k) == (curr))) { return value.get(pos); + } } } - /** {@inheritDoc} */ + /** + * {@inheritDoc} + */ @Override public V putIfAbsent(final long k, final V v) { final long pos = find(k); - if (pos >= 0) + if (pos >= 0) { return value.get(pos); + } insert(-pos - 1, k, v); return defRetValue; } - /** {@inheritDoc} */ + /** + * {@inheritDoc} + */ @Override public boolean remove(final long k, final Object v) { - if (((k) == (0))) { + if (((k) == 0)) { if (containsNullKey && java.util.Objects.equals(v, value.get(n))) { removeNullEntry(); return true; @@ -350,15 +420,17 @@ public class Long2ObjectOpenHashDataMap<V> extends AbstractLong2ObjectMap<V> long curr; long pos; // The starting point. - if (((curr = key.get(pos = (long) HashCommon.mix((k)) & mask)) == (0))) + if (((curr = key.get(pos = HashCommon.mix((k)) & mask)) == 0)) { return false; + } if (((k) == (curr)) && java.util.Objects.equals(v, value.get(pos))) { removeEntry(pos); return true; } while (true) { - if (((curr = key.get(pos = (pos + 1) & mask)) == (0))) + if (((curr = key.get(pos = (pos + 1) & mask)) == 0)) { return false; + } if (((k) == (curr)) && java.util.Objects.equals(v, value.get(pos))) { removeEntry(pos); return true; @@ -366,102 +438,124 @@ public class Long2ObjectOpenHashDataMap<V> extends AbstractLong2ObjectMap<V> } } - /** {@inheritDoc} */ + /** + * {@inheritDoc} + */ @Override public boolean replace(final long k, final V oldValue, final V v) { final long pos = find(k); - if (pos < 0 || !java.util.Objects.equals(oldValue, value.get(pos))) + if (pos < 0 || !java.util.Objects.equals(oldValue, value.get(pos))) { return false; + } value.put(pos, v); return true; } - /** {@inheritDoc} */ + /** + * {@inheritDoc} + */ @Override public V replace(final long k, final V v) { final long pos = find(k); - if (pos < 0) + if (pos < 0) { return defRetValue; + } final V oldValue = value.get(pos); value.put(pos, v); return oldValue; } - /** {@inheritDoc} */ + /** + * {@inheritDoc} + */ @Override public V computeIfAbsent(final long k, final java.util.function.LongFunction<? extends V> mappingFunction) { java.util.Objects.requireNonNull(mappingFunction); final long pos = find(k); - if (pos >= 0) + if (pos >= 0) { return value.get(pos); + } final V newValue = mappingFunction.apply(k); insert(-pos - 1, k, newValue); return newValue; } - /** {@inheritDoc} */ + /** + * {@inheritDoc} + */ @Override public V computeIfAbsent(final long key, final Long2ObjectFunction<? extends V> mappingFunction) { java.util.Objects.requireNonNull(mappingFunction); final long pos = find(key); - if (pos >= 0) + if (pos >= 0) { return value.get(pos); - if (!mappingFunction.containsKey(key)) + } + if (!mappingFunction.containsKey(key)) { return defRetValue; + } final V newValue = mappingFunction.get(key); insert(-pos - 1, key, newValue); return newValue; } - /** {@inheritDoc} */ + /** + * {@inheritDoc} + */ @Override public V computeIfPresent(final long k, final java.util.function.BiFunction<? super Long, ? super V, ? extends V> remappingFunction) { java.util.Objects.requireNonNull(remappingFunction); final long pos = find(k); - if (pos < 0) + if (pos < 0) { return defRetValue; - if (value.get(pos) == null) + } + if (value.get(pos) == null) { return defRetValue; - final V newValue = remappingFunction.apply(Long.valueOf(k), (value.get(pos))); + } + final V newValue = remappingFunction.apply(k, (value.get(pos))); if (newValue == null) { - if (((k) == (0))) + if (((k) == 0)) { removeNullEntry(); - else + } else { removeEntry(pos); + } return defRetValue; } value.put(pos, newValue); return newValue; } - /** {@inheritDoc} */ + /** + * {@inheritDoc} + */ @Override public V compute(final long k, final java.util.function.BiFunction<? super Long, ? super V, ? extends V> remappingFunction) { java.util.Objects.requireNonNull(remappingFunction); final long pos = find(k); - final V newValue = remappingFunction.apply(Long.valueOf(k), pos >= 0 ? (value.get(pos)) : null); + final V newValue = remappingFunction.apply(k, pos >= 0 ? (value.get(pos)) : null); if (newValue == null) { if (pos >= 0) { - if (((k) == (0))) + if (((k) == 0)) { removeNullEntry(); - else + } else { removeEntry(pos); + } } return defRetValue; } - V newVal = (newValue); if (pos < 0) { - insert(-pos - 1, k, newVal); - return newVal; + insert(-pos - 1, k, (newValue)); + return (newValue); } - value.put(pos, newVal); - return newVal; + value.put(pos, (newValue)); + return (newValue); } - /** {@inheritDoc} */ + /** + * {@inheritDoc} + */ @Override public V merge(final long k, final V v, final java.util.function.BiFunction<? super V, ? super V, ? extends V> remappingFunction) { @@ -469,18 +563,20 @@ public class Long2ObjectOpenHashDataMap<V> extends AbstractLong2ObjectMap<V> java.util.Objects.requireNonNull(v); final long pos = find(k); if (pos < 0 || value.get(pos) == null) { - if (pos < 0) + if (pos < 0) { insert(-pos - 1, k, v); - else + } else { value.put(pos, v); + } return v; } final V newValue = remappingFunction.apply((value.get(pos)), (v)); if (newValue == null) { - if (((k) == (0))) + if (((k) == 0)) { removeNullEntry(); - else + } else { removeEntry(pos); + } return defRetValue; } value.put(pos, newValue); @@ -496,11 +592,12 @@ public class Long2ObjectOpenHashDataMap<V> extends AbstractLong2ObjectMap<V> */ @Override public void clear() { - if (size.get() == 0) + if (size.get() == 0) { return; + } size.set(0); containsNullKey = false; - // TODO: Arrays.fill(key, (0)); + // TODO: Arrays.fill(key, 0); // TODO: Arrays.fill(value, null); } @@ -581,8 +678,9 @@ public class Long2ObjectOpenHashDataMap<V> extends AbstractLong2ObjectMap<V> @SuppressWarnings("unchecked") @Override public boolean equals(final Object o) { - if (!(o instanceof Map.Entry)) + if (!(o instanceof Map.Entry)) { return false; + } Map.Entry<Long, V> e = (Map.Entry<Long, V>) o; return ((key.get(index)) == ((e.getKey()).longValue())) && java.util.Objects.equals(value.get(index), (e.getValue())); @@ -600,7 +698,9 @@ public class Long2ObjectOpenHashDataMap<V> extends AbstractLong2ObjectMap<V> } } - /** An iterator over a hash map. */ + /** + * An iterator over a hash map. + */ private abstract class MapIterator<ConsumerType> { /** * The index of the last entry returned, if positive or zero; initially, {@link #n}. If @@ -614,9 +714,13 @@ public class Long2ObjectOpenHashDataMap<V> extends AbstractLong2ObjectMap<V> * -1 if either we did not return an entry yet, or the last returned entry has been removed. */ long last = -1; - /** A downward counter measuring how many entries must still be returned. */ + /** + * A downward counter measuring how many entries must still be returned. + */ long c = size.get(); - /** A boolean telling us whether we should return the entry with the null key. */ + /** + * A boolean telling us whether we should return the entry with the null key. + */ boolean mustReturnNullKey = Long2ObjectOpenHashDataMap.this.containsNullKey; /** * A lazily allocated list containing keys of entries that have wrapped around the table because @@ -632,8 +736,9 @@ public class Long2ObjectOpenHashDataMap<V> extends AbstractLong2ObjectMap<V> } public long nextEntry() { - if (!hasNext()) + if (!hasNext()) { throw new NoSuchElementException(); + } c--; if (mustReturnNullKey) { mustReturnNullKey = false; @@ -644,13 +749,15 @@ public class Long2ObjectOpenHashDataMap<V> extends AbstractLong2ObjectMap<V> // We are just enumerating elements from the wrapped list. last = Integer.MIN_VALUE; final long k = wrapped.getLong((int) -pos - 1); // TODO: check if -pos - 1 is correct - long p = (long) HashCommon.mix((k)) & mask; - while (!((k) == (key.get(p)))) + long p = HashCommon.mix((k)) & mask; + while (!((k) == (key.get(p)))) { p = (p + 1) & mask; + } return p; } - if (!((key.get(pos)) == (0))) + if (!((key.get(pos)) == 0)) { return last = pos; + } } } @@ -665,12 +772,13 @@ public class Long2ObjectOpenHashDataMap<V> extends AbstractLong2ObjectMap<V> // We are just enumerating elements from the wrapped list. last = Integer.MIN_VALUE; final long k = wrapped.getLong((int) -pos - 1); // TODO: check if -pos - 1 is correct - long p = (long) HashCommon.mix((k)) & mask; - while (!((k) == (key.get(p)))) + long p = HashCommon.mix((k)) & mask; + while (!((k) == (key.get(p)))) { p = (p + 1) & mask; + } acceptOnIndex(action, p); c--; - } else if (!((key.get(pos)) == (0))) { + } else if (!((key.get(pos)) == 0)) { acceptOnIndex(action, last = pos); c--; } @@ -690,19 +798,21 @@ public class Long2ObjectOpenHashDataMap<V> extends AbstractLong2ObjectMap<V> for (;;) { pos = ((last = pos) + 1) & mask; for (;;) { - if (((curr = key.get(pos)) == (0))) { + if (((curr = key.get(pos)) == 0)) { key.put(last, 0L); value.put(last, null); return; } - slot = (long) HashCommon.mix((curr)) & mask; - if (last <= pos ? last >= slot || slot > pos : last >= slot && slot > pos) + slot = HashCommon.mix((curr)) & mask; + if (last <= pos ? last >= slot || slot > pos : last >= slot && slot > pos) { break; + } pos = (pos + 1) & mask; } if (pos < last) { // Wrapped entry. - if (wrapped == null) + if (wrapped == null) { wrapped = new LongArrayList(2); + } wrapped.add(key.get(pos)); } key.put(last, curr); @@ -711,18 +821,17 @@ public class Long2ObjectOpenHashDataMap<V> extends AbstractLong2ObjectMap<V> } public void remove() { - if (last == -1) + if (last == -1) { throw new IllegalStateException(); + } if (last == n) { containsNullKey = false; value.put(n, null); - } else if (pos >= 0) + } else if (pos >= 0) { shiftKeys(last); - else { + } else { // We're removing wrapped entries. - Long2ObjectOpenHashDataMap.this.remove(wrapped.getLong((int) -pos - 1)); // TODO: check if - // -pos - - // 1 is correct + Long2ObjectOpenHashDataMap.this.remove(wrapped.getLong((int) -pos - 1)); last = -1; // Note that we must not decrement size return; } @@ -732,8 +841,9 @@ public class Long2ObjectOpenHashDataMap<V> extends AbstractLong2ObjectMap<V> public long skip(final long n) { long i = n; - while (i-- != 0 && hasNext()) + while (i-- != 0 && hasNext()) { nextEntry(); + } return n - i - 1; } } @@ -787,11 +897,17 @@ public class Long2ObjectOpenHashDataMap<V> extends AbstractLong2ObjectMap<V> * this counts up instead of down. */ long pos = 0; - /** The maximum bucket (exclusive) to iterate to */ + /** + * The maximum bucket (exclusive) to iterate to + */ long max = n; - /** An upwards counter counting how many we have given */ + /** + * An upwards counter counting how many we have given + */ long c = 0; - /** A boolean telling us whether we should return the null key. */ + /** + * A boolean telling us whether we should return the null key. + */ boolean mustReturnNull = Long2ObjectOpenHashDataMap.this.containsNullKey; boolean hasSplit = false; @@ -816,7 +932,7 @@ public class Long2ObjectOpenHashDataMap<V> extends AbstractLong2ObjectMap<V> return true; } while (pos < max) { - if (!((key.get(pos)) == (0))) { + if (!((key.get(pos)) == 0)) { ++c; acceptOnIndex(action, pos++); return true; @@ -833,7 +949,7 @@ public class Long2ObjectOpenHashDataMap<V> extends AbstractLong2ObjectMap<V> acceptOnIndex(action, n); } while (pos < max) { - if (!((key.get(pos)) == (0))) { + if (!((key.get(pos)) == 0)) { acceptOnIndex(action, pos); ++c; } @@ -856,11 +972,13 @@ public class Long2ObjectOpenHashDataMap<V> extends AbstractLong2ObjectMap<V> } public SplitType trySplit() { - if (pos >= max - 1) + if (pos >= max - 1) { return null; + } long retLen = (max - pos) >> 1; - if (retLen <= 1) + if (retLen <= 1) { return null; + } long myNewPos = pos + retLen; long retPos = pos; long retMax = myNewPos; @@ -876,10 +994,12 @@ public class Long2ObjectOpenHashDataMap<V> extends AbstractLong2ObjectMap<V> } public long skip(long n) { - if (n < 0) + if (n < 0) { throw new IllegalArgumentException("Argument must be nonnegative: " + n); - if (n == 0) + } + if (n == 0) { return 0; + } long skipped = 0; if (mustReturnNull) { mustReturnNull = false; @@ -887,7 +1007,7 @@ public class Long2ObjectOpenHashDataMap<V> extends AbstractLong2ObjectMap<V> --n; } while (pos < max && n > 0) { - if (!((key.get(pos++)) == (0))) { + if (!((key.get(pos++)) == 0)) { ++skipped; --n; } @@ -947,43 +1067,52 @@ public class Long2ObjectOpenHashDataMap<V> extends AbstractLong2ObjectMap<V> @Override @SuppressWarnings("unchecked") public boolean contains(final Object o) { - if (!(o instanceof Map.Entry)) + if (!(o instanceof Map.Entry)) { return false; + } final Map.Entry<?, ?> e = (Map.Entry<?, ?>) o; - if (e.getKey() == null || !(e.getKey() instanceof Long)) + if (e.getKey() == null || !(e.getKey() instanceof Long)) { return false; - final long k = ((Long) (e.getKey())).longValue(); + } + final long k = (Long) e.getKey(); final V v = ((V) e.getValue()); - if (((k) == (0))) + if (((k) == 0)) { return Long2ObjectOpenHashDataMap.this.containsNullKey && java.util.Objects.equals(value.get(n), v); + } long curr; long pos; // The starting point. - if (((curr = key.get(pos = (long) HashCommon.mix((k)) & mask)) == (0))) + if (((curr = key.get(pos = HashCommon.mix((k)) & mask)) == 0)) { return false; - if (((k) == (curr))) + } + if (((k) == (curr))) { return java.util.Objects.equals(value.get(pos), v); + } // There's always an unused entry. while (true) { - if (((curr = key.get(pos = (pos + 1) & mask)) == (0))) + if (((curr = key.get(pos = (pos + 1) & mask)) == 0)) { return false; - if (((k) == (curr))) + } + if (((k) == (curr))) { return java.util.Objects.equals(value.get(pos), v); + } } } @Override @SuppressWarnings("unchecked") public boolean remove(final Object o) { - if (!(o instanceof Map.Entry)) + if (!(o instanceof Map.Entry)) { return false; + } final Map.Entry<?, ?> e = (Map.Entry<?, ?>) o; - if (e.getKey() == null || !(e.getKey() instanceof Long)) + if (e.getKey() == null || !(e.getKey() instanceof Long)) { return false; - final long k = ((Long) (e.getKey())).longValue(); + } + final long k = (Long) e.getKey(); final V v = ((V) e.getValue()); - if (((k) == (0))) { + if (((k) == 0)) { if (containsNullKey && java.util.Objects.equals(value.get(n), v)) { removeNullEntry(); return true; @@ -993,8 +1122,9 @@ public class Long2ObjectOpenHashDataMap<V> extends AbstractLong2ObjectMap<V> long curr; long pos; // The starting point. - if (((curr = key.get(pos = (long) HashCommon.mix((k)) & mask)) == (0))) + if (((curr = key.get(pos = HashCommon.mix((k)) & mask)) == 0)) { return false; + } if (((curr) == (k))) { if (java.util.Objects.equals(value.get(pos), v)) { removeEntry(pos); @@ -1003,8 +1133,9 @@ public class Long2ObjectOpenHashDataMap<V> extends AbstractLong2ObjectMap<V> return false; } while (true) { - if (((curr = key.get(pos = (pos + 1) & mask)) == (0))) + if (((curr = key.get(pos = (pos + 1) & mask)) == 0)) { return false; + } if (((curr) == (k))) { if (java.util.Objects.equals(value.get(pos), v)) { removeEntry(pos); @@ -1024,33 +1155,42 @@ public class Long2ObjectOpenHashDataMap<V> extends AbstractLong2ObjectMap<V> Long2ObjectOpenHashDataMap.this.clear(); } - /** {@inheritDoc} */ + /** + * {@inheritDoc} + */ @Override public void forEach(final Consumer<? super Long2ObjectMap.Entry<V>> consumer) { - if (containsNullKey) + if (containsNullKey) { consumer.accept(new AbstractLong2ObjectMap.BasicEntry<V>(key.get(n), value.get(n))); - for (long pos = n; pos-- != 0;) - if (!((key.get(pos)) == (0))) + } + for (long pos = n; pos-- != 0;) { + if (!((key.get(pos)) == 0)) { consumer.accept(new AbstractLong2ObjectMap.BasicEntry<V>(key.get(pos), value.get(pos))); + } + } } - /** {@inheritDoc} */ + /** + * {@inheritDoc} + */ @Override public void fastForEach(final Consumer<? super Long2ObjectMap.Entry<V>> consumer) { if (containsNullKey) { consumer.accept(new AbstractLong2ObjectMap.BasicEntry<>(key.get(n), value.get(n))); } - for (long pos = n; pos-- != 0;) - if (!((key.get(pos)) == (0))) { + for (long pos = n; pos-- != 0;) { + if (!((key.get(pos)) == 0)) { consumer.accept(new AbstractLong2ObjectMap.BasicEntry<>(key.get(pos), value.get(pos))); } + } } } @Override public FastEntrySet<V> long2ObjectEntrySet() { - if (entries == null) + if (entries == null) { entries = new MapEntrySet(); + } return entries; } @@ -1122,15 +1262,19 @@ public class Long2ObjectOpenHashDataMap<V> extends AbstractLong2ObjectMap<V> return new KeySpliterator(); } - /** {@inheritDoc} */ + /** + * {@inheritDoc} + */ @Override public void forEach(final java.util.function.LongConsumer consumer) { - if (containsNullKey) + if (containsNullKey) { consumer.accept(key.get(n)); + } for (long pos = n; pos-- != 0;) { final long k = key.get(pos); - if (!((k) == (0))) + if (!((k) == 0)) { consumer.accept(k); + } } } @@ -1159,8 +1303,9 @@ public class Long2ObjectOpenHashDataMap<V> extends AbstractLong2ObjectMap<V> @Override public LongSet keySet() { - if (keys == null) + if (keys == null) { keys = new KeySet(); + } return keys; } @@ -1223,7 +1368,7 @@ public class Long2ObjectOpenHashDataMap<V> extends AbstractLong2ObjectMap<V> @Override public ObjectCollection<V> values() { - if (values == null) + if (values == null) { values = new AbstractObjectCollection<V>() { @Override public ObjectIterator<V> iterator() { @@ -1238,11 +1383,14 @@ public class Long2ObjectOpenHashDataMap<V> extends AbstractLong2ObjectMap<V> /** {@inheritDoc} */ @Override public void forEach(final Consumer<? super V> consumer) { - if (containsNullKey) + if (containsNullKey) { consumer.accept(value.get(n)); - for (long pos = n; pos-- != 0;) - if (!((key.get(pos)) == (0))) + } + for (long pos = n; pos-- != 0;) { + if (!((key.get(pos)) == 0)) { consumer.accept(value.get(pos)); + } + } } @Override @@ -1260,6 +1408,7 @@ public class Long2ObjectOpenHashDataMap<V> extends AbstractLong2ObjectMap<V> Long2ObjectOpenHashDataMap.this.clear(); } }; + } return values; } @@ -1291,7 +1440,7 @@ public class Long2ObjectOpenHashDataMap<V> extends AbstractLong2ObjectMap<V> * <p> * This method is useful when reusing maps. {@linkplain #clear() Clearing a map} leaves the table * size untouched. If you are reusing a map many times, you can call this method with a typical - * size to avoid keeping around a very large table just because of a few large transient maps. + * size to avoid keeping around a very large table just because of a few large maps. * * @param n the threshold for the trimming. * @return true if there was enough memory to trim the map. @@ -1299,8 +1448,9 @@ public class Long2ObjectOpenHashDataMap<V> extends AbstractLong2ObjectMap<V> */ public boolean trim(final long n) { final long l = HashCommon.nextPowerOfTwo((long) Math.ceil(n / f)); - if (l >= this.n || size.get() > maxFill(l, f)) + if (l >= this.n || size.get() > maxFill(l, f)) { return true; + } try { rehash(l); } catch (OutOfMemoryError cantDoIt) { @@ -1327,7 +1477,7 @@ public class Long2ObjectOpenHashDataMap<V> extends AbstractLong2ObjectMap<V> long i = n, pos; for (long j = realSize(); j-- != 0;) { while ((key.get(--i) == 0)); - if (!((newKey.get(pos = (long) mix((key.get(i))) & mask)) == (0))) { + if (!((newKey.get(pos = mix((key.get(i))) & mask)) == 0)) { while (!(newKey.get(pos = (pos + 1) & mask) == 0)); } newKey.put(pos, key.get(i)); @@ -1343,7 +1493,7 @@ public class Long2ObjectOpenHashDataMap<V> extends AbstractLong2ObjectMap<V> /** * Returns a hash code for this map. - * + * <p> * This method overrides the generic method provided by the superclass. Since {@code equals()} is * not overriden, it is important that the value returned by this method is the same value as the * one returned by the overriden method. @@ -1354,17 +1504,20 @@ public class Long2ObjectOpenHashDataMap<V> extends AbstractLong2ObjectMap<V> public int hashCode() { int h = 0; for (long j = realSize(), i = 0, t = 0; j-- != 0;) { - while (((key.get(i)) == (0))) + while (((key.get(i)) == 0)) { i++; + } t = HashCommon.long2int(key.get(i)); - if (this != value.get(i)) + if (this != value.get(i)) { t ^= ((value.get(i)) == null ? 0 : (value.get(i)).hashCode()); + } h += t; i++; } // Zero / null keys have hash zero. - if (containsNullKey) + if (containsNullKey) { h += ((value.get(n)) == null ? 0 : (value.get(n)).hashCode()); + } return h; } }
