dschneider-pivotal commented on a change in pull request #6768: URL: https://github.com/apache/geode/pull/6768#discussion_r697733068
########## File path: geode-apis-compatible-with-redis/src/main/java/org/apache/geode/redis/internal/collections/Bytes2ObjectOpenHashMap.java ########## @@ -0,0 +1,1230 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more contributor license + * agreements. See the NOTICE file distributed with this work for additional information regarding + * copyright ownership. The ASF licenses this file to You under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance with the License. You may obtain a + * copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software distributed under the License + * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express + * or implied. See the License for the specific language governing permissions and limitations under + * the License. + */ +package org.apache.geode.redis.internal.collections; + +import static it.unimi.dsi.fastutil.HashCommon.arraySize; +import static it.unimi.dsi.fastutil.HashCommon.maxFill; + +import java.util.Arrays; +import java.util.Map; +import java.util.NoSuchElementException; +import java.util.function.Consumer; +import java.util.function.Predicate; + +import it.unimi.dsi.fastutil.Hash; +import it.unimi.dsi.fastutil.HashCommon; +import it.unimi.dsi.fastutil.Pair; +import it.unimi.dsi.fastutil.bytes.ByteArrays; +import it.unimi.dsi.fastutil.objects.AbstractObject2ObjectMap; +import it.unimi.dsi.fastutil.objects.AbstractObjectCollection; +import it.unimi.dsi.fastutil.objects.AbstractObjectSet; +import it.unimi.dsi.fastutil.objects.Object2ObjectMap; +import it.unimi.dsi.fastutil.objects.ObjectArrayList; +import it.unimi.dsi.fastutil.objects.ObjectCollection; +import it.unimi.dsi.fastutil.objects.ObjectIterator; +import it.unimi.dsi.fastutil.objects.ObjectSet; +import it.unimi.dsi.fastutil.objects.ObjectSpliterator; +import it.unimi.dsi.fastutil.objects.ObjectSpliterators; + +/** + * This class was derived from Object2ObjectOpenCustomHashMap. + * The differences are: + * 1. the keys are always a byte[] so no need for "strategy" field + * 2. the load factory is always the default so no need for the "f" field. + * 3. no support for the "null" key so no need for the boolean field that signifies a null key + * exists + * 4. the fields that cache a singleton instance for entrySet, keySet, and values + * no longer exist. + */ +public class Bytes2ObjectOpenHashMap<V> extends AbstractObject2ObjectMap<byte[], V> + implements java.io.Serializable, Cloneable, Hash { + private static final Strategy<byte[]> strategy = ByteArrays.HASH_STRATEGY; + private static final long serialVersionUID = 0L; + private static final boolean ASSERTS = false; + /** The array of keys. */ + protected transient byte[][] key; + /** The array of values. */ + protected transient V[] value; + /** The mask for wrapping a position counter. */ + protected transient int mask; + /** The current table size. */ + protected transient int n; + /** Threshold after which we rehash. It must be the table size times load factor. */ + protected transient int maxFill; + /** We never resize below this threshold, which is the construction-time {#n}. */ + protected final transient int minN; + /** Number of entries in the set */ + protected int size; + + /** + * Creates a new hash map. + * + * <p> + * The actual table size will be the least power of two greater than {@code expected}/{@code f}. + * + * @param expected the expected number of elements in the hash map. + */ + @SuppressWarnings("unchecked") + public Bytes2ObjectOpenHashMap(final int expected) { + if (expected < 0) + throw new IllegalArgumentException("The expected number of elements must be non-negative"); + minN = n = arraySize(expected, getLoadFactor()); + mask = n - 1; + maxFill = maxFill(n, getLoadFactor()); + key = new byte[n + 1][]; + value = (V[]) new Object[n + 1]; + } + + /** + * Creates a new hash map with initial expected {@link Hash#DEFAULT_INITIAL_SIZE} entries + * and {@link Hash#DEFAULT_LOAD_FACTOR} as load factor. + */ + public Bytes2ObjectOpenHashMap() { + this(DEFAULT_INITIAL_SIZE); + } + + /** + * Creates a new hash map with {@link Hash#DEFAULT_LOAD_FACTOR} as load factor copying a given + * one. + * + * @param m a {@link Map} to be copied into the new hash map. + */ + public Bytes2ObjectOpenHashMap(final Map<byte[], ? extends V> m) { + this(m.size()); + putAll(m); + } + + /** + * Returns the hashing strategy. + * + * @return the hashing strategy of this custom hash map. + */ + public Strategy<byte[]> strategy() { + return strategy; + } + + private int realSize() { + return size; + } + + private void ensureCapacity(final int capacity) { + final int needed = arraySize(capacity, getLoadFactor()); + if (needed > n) + rehash(needed); + } + + private void tryCapacity(final long capacity) { + final int needed = (int) Math.min(1 << 30, + Math.max(2, HashCommon.nextPowerOfTwo((long) Math.ceil(capacity / getLoadFactor())))); + if (needed > n) + rehash(needed); + } + + private V removeEntry(final int pos) { + final V oldValue = value[pos]; + value[pos] = null; + size--; + shiftKeys(pos); + if (n > minN && size < maxFill / 4 && n > DEFAULT_INITIAL_SIZE) + rehash(n / 2); + return oldValue; + } + + @Override + public void putAll(Map<? extends byte[], ? extends V> m) { + if (getLoadFactor() <= .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 + super.putAll(m); + } + + private int find(final byte[] k) { + byte[] curr; + final byte[][] key = this.key; + int pos; + // The starting point. + if (((curr = + key[pos = (HashCommon.mix(strategy().hashCode(k))) & mask]) == null)) + return -(pos + 1); + if ((strategy().equals((k), (curr)))) + return pos; + // There's always an unused entry. + while (true) { + if (((curr = key[pos = (pos + 1) & mask]) == null)) + return -(pos + 1); + if ((strategy().equals((k), (curr)))) + return pos; + } + } + + private void insert(final int pos, final byte[] k, final V v) { + key[pos] = k; + value[pos] = v; + if (size++ >= maxFill) + rehash(arraySize(size + 1, getLoadFactor())); + if (ASSERTS) + checkTable(); + } + + @Override + public V put(final byte[] k, final V v) { + final int pos = find(k); + if (pos < 0) { + insert(-pos - 1, k, v); + return defRetValue; + } + final V oldValue = value[pos]; + value[pos] = v; + return oldValue; + } + + /** + * Shifts left entries with the specified hash code, starting at the specified position, + * and empties the resulting free entry. + * + * @param pos a starting position. + */ + protected final void shiftKeys(int pos) { + // Shift entries with the same hash. + int last, slot; + byte[] curr; + final byte[][] key = this.key; + for (;;) { + pos = ((last = pos) + 1) & mask; + for (;;) { Review comment: yes -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
