Author: schor Date: Fri Dec 15 15:32:56 2017 New Revision: 1818293 URL: http://svn.apache.org/viewvc?rev=1818293&view=rev Log: [UIMA-5674] multiple hash map upgrade using common code, fixing edge cases.
Added: uima/uv3/uimaj-v3/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/Common_hash_support.java Modified: uima/uv3/uimaj-v3/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/Int2ObjHashMap.java uima/uv3/uimaj-v3/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/IntHashSet.java uima/uv3/uimaj-v3/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/Obj2IntIdentityHashMap.java uima/uv3/uimaj-v3/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/ObjHashSet.java Added: uima/uv3/uimaj-v3/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/Common_hash_support.java URL: http://svn.apache.org/viewvc/uima/uv3/uimaj-v3/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/Common_hash_support.java?rev=1818293&view=auto ============================================================================== --- uima/uv3/uimaj-v3/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/Common_hash_support.java (added) +++ uima/uv3/uimaj-v3/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/Common_hash_support.java Fri Dec 15 15:32:56 2017 @@ -0,0 +1,534 @@ +/* + * 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.uima.internal.util; + +import java.util.Arrays; +import java.util.function.IntConsumer; +import java.util.function.IntPredicate; +import java.util.function.IntSupplier; + +/** + * A common superclass for hash maps and hash sets + * + */ +public abstract class Common_hash_support { + + // set to true to collect statistics for tuning + // you have to also put a call to showHistogram() at the end of the run + protected static final boolean TUNE = false; + + protected static final int MIN_SIZE = 10; // 10 / .66 =15.15 + protected static final int MIN_CAPACITY = 16; + protected static final int MIN_CAPACITY_SHRINK = 64; // don't shrink below this - thrashing + + protected final float loadFactor; + + protected final int initialCapacity; + + protected int histogram []; + protected int maxProbe = 0; + + protected int sizeWhichTriggersExpansion; + private int size = 0; // number of elements in the table + + protected int removed = 0; // for rebalancing + + /** set to the first found_removed when searching */ + protected int found_removed; + + protected boolean secondTimeShrinkable = false; + + /** + * @param initialSizeBeforeExpanding the number of elements the table should hold before expanding + */ + public Common_hash_support(int initialSizeBeforeExpanding) { + this(initialSizeBeforeExpanding, 0.66F); + } + + public Common_hash_support(int initialSizeBeforeExpanding, float factor) { + this.loadFactor = factor; + this.initialCapacity = tableSpace(initialSizeBeforeExpanding, factor); + if (TUNE) { + histogram = new int[200]; + Arrays.fill(histogram, 0); + maxProbe = 0; + } + } + + public Common_hash_support(Common_hash_support orig) { + this(orig.initialCapacity); + this.sizeWhichTriggersExpansion = orig.sizeWhichTriggersExpansion; + this.size = orig.size; + this.removed = orig.removed; + this.secondTimeShrinkable = orig.secondTimeShrinkable; + + // copy doesn't do tuning measurements + this.histogram = null; + } + + public void clear() { + // see if size is less than the 1/2 size that triggers expansion + if (size + removed < (sizeWhichTriggersExpansion >>> 1)) { + // if 2nd time then shrink by 50% + // this is done to avoid thrashing around the threshold + if (secondTimeShrinkable) { + secondTimeShrinkable = false; + final int newCapacity = Math.max(initialCapacity, keys_length() >>> 1); + if (newCapacity < keys_length()) { + newTable(newCapacity); // shrink table by 50% + size = 0; + removed = 0; + resetHistogram(); + return; + } else { // don't shrink below minimum + clearExisting(); + return; + } + } else { + secondTimeShrinkable = true; + } + } else { + secondTimeShrinkable = false; // reset this to require 2 triggers in a row + } + clearExisting(); + } + + private void clearExisting() { + clearKeysAndValues(); + size = 0; + removed = 0; + resetHistogram(); + } + + /** It gets a ref to the current value of table, and then searches that array. + * Side effect: found_removed is set to the position of the first REMOVED_KEY (if any) encountered + * during the search. + * + * @param key_validity_checks check the key is valid or throw + * @param key_hash compute the hash code of the key + * @param is_eq_sor_not_present true if the key at the int position is == to the key, or is 0 + * @param is_removed_key true if the key at the int position is "removed" + * @return the probeAddr in keys array. The value is the not-present-value if not found + */ + protected int findPosition( + int hash, + IntPredicate is_eq_or_not_present, + IntPredicate is_removed_key) { + + found_removed = -1; +// final int hash = key_hash.getAsInt(); + +// final int[] localKeys = keys; + final int bitMask = keys_length() - 1; + + int nbrProbes = 1; + int probeDelta = 0; + int probeAddr = hash & bitMask; + + for (;;) { + + if (is_eq_or_not_present.test(probeAddr)) { + if (TUNE) { + updateHistogram(nbrProbes); + } + return probeAddr; + } + + if (found_removed == -1 && is_removed_key.test(probeAddr)) { + found_removed = probeAddr; + } + + if (TUNE) nbrProbes++; + + if (probeDelta < 13) { + probeDelta ++; // stop at a prime + // which guarantees all slots eventually traversed. + } + probeAddr = bitMask & (probeAddr + probeDelta); + } + +// +// // fast paths +// if (is_eq_or_not_present.test(probeAddr)) { +//// final int testKey = localKeys[probeAddr]; +//// if (testKey == 0 || testKey == key) { +// if (TUNE) { +// updateHistogram(1); +// } +// return probeAddr; +// } +// if (is_removed_key.test(probeAddr)) { +//// testKey == REMOVED_KEY) { +// found_removed = probeAddr; +// } +// return findPosition2(is_eq_or_not_present, is_removed_key, probeAddr); + } + +// private int findPosition2(IntPredicate is_eq_or_not_present, +// IntPredicate is_removed_key, +// int probeAddr) { +// final int bitMask = keys_length() - 1; +// int nbrProbes = 2; +// int probeDelta = 1; +// probeAddr = bitMask & (probeAddr + (probeDelta++)); +// +// while (true) { +// if (is_eq_or_not_present.test(probeAddr)) { +//// final int testKey = localKeys[probeAddr]; +//// if (testKey == 0 || testKey == key) { +// break; +// } +// +// if (found_removed == -1 && is_removed_key.test(probeAddr)) { +// found_removed = probeAddr; +// } +// nbrProbes++; +// if (probeDelta < 13) { +// probeDelta ++; // stop at a prime +// // which guarantees all slots eventually traversed. +// } +// probeAddr = bitMask & (probeAddr + (probeDelta++)); +// } +// +// if (TUNE) { +// final int pv = histogram[nbrProbes]; +// +// histogram[nbrProbes] = 1 + pv; +// if (maxProbe < nbrProbes) { +// maxProbe = nbrProbes; +// } +// } +// return probeAddr; +// } + + /** + * As REMOVED tokens populate, + * the number of 0's (representing free cells and + * also the end of bucket chain searches) drops. + * + * If this drops a lot, then searches take much longer. + * If there are no 0's left, searches never terminate! + * + * Keep the number of 0's at about 1 - load factor + * + */ + private void maybeRebalanceRemoves() { + final int old_capacity = keys_length(); + if (old_capacity <= MIN_CAPACITY_SHRINK) { + return; + } + int new_capacity = old_capacity >> 1; + +// //debug +// int sz = size; + + /****************************************************** + * Logic for clearing out the removed markers in bulk + * + * 3 cases: resize up (never happens), down, or the same + * + * Don't clear out if there's room left unless + * there's too much room left and should downsize + * + * Don't over do - avoid thrashing, avoid work for small sizes + * + * Case for upsizing: none. It's guaranteed there are always enough + * 0's for the load factor, by put/add implementation. + * + * Case for downsizing: if the size < 1/3 of the new capacity or, + * number being removed would be > 1/3 of the new capacity + ******************************************************/ + + if (removed + size >= sizeWhichTriggersExpansion) { + Misc.internalError(); // put or add always keeps this false. remove always reduces or keeps this value the same + } + + // REMOVED tags if there are enough of them to make it worthwhile + // or if just should shrink because removed + size is smaller than 1/3 the new capacity + int one_third_new_capacity = sizeWhichTriggersExpansion >> 2; + int one_half_new_capacity = new_capacity >> 1; + if (removed > one_half_new_capacity || (size < one_third_new_capacity)) { + if (size >= one_third_new_capacity) { + new_capacity = old_capacity; + } + if (TUNE) { + System.out.println("Capacity (maybe) decreasing from " + old_capacity + " to " + new_capacity + " removed= " + removed + " size= " + size); + } + copyOld2New(new_capacity, old_capacity); + } +// //debug +// if (sz != size) +// System.out.println("debug"); + } + + /** + * This method calls the subclass's copy_to_new_table method, + * passing an inner lambda containing common code for copying old to new. + * + * That inner lambda, when invoked by the copy_to_new_table method, + * is passed another lambda of one argument (the old index) + * which is called to copy each element. + * @param new_capacity + * @param old_capacity + */ + private void copyOld2New(int new_capacity, int old_capacity) { + copy_to_new_table( + new_capacity, + old_capacity, + + // this code assigned to "commonCopy" arg + (IntConsumer copyToNew, IntPredicate is_valid_old_key) -> { + newTable(new_capacity); + removed = 0; // reset before put, otherwise, causes premature expansion + for (int i = 0; i < old_capacity; i++) { + if (is_valid_old_key.test(i)) { + copyToNew.accept(i); + } + } + }); + } + + /** + * advance pos until it points to a non 0 or is 1 past end + * If pos is negative, start at 0. + * Don't move if pos already has valid key + * @param pos + * @return updated pos + */ + protected int moveToNextFilled(int pos) { + final int max = keys_length(); + if (pos < 0) { + pos = 0; + } + while (true) { + if (pos >= max) { + return pos; + } + if (is_valid_key(pos)) { + return pos; + } + pos ++; + } + } + + /** + * decrement pos until it points to a non 0 or is -1 + * If pos is beyond end start at end. + * Don't move if pos already has valid key + * @param pos + * @return updated pos + */ + protected int moveToPreviousFilled(int pos) { + final int max = keys_length(); + if (pos > max) { + pos = max - 1; + } + + while (true) { + if (pos < 0) { + return pos; + } + if (is_valid_key(pos)) { + return pos; + } + pos --; + } + } + + // called by clear, increase table size, decrease table size + protected void newTable(int capacity) { + capacity = Math.max(MIN_SIZE, Misc.nextHigherPowerOf2(capacity)); + newKeysAndValues(capacity); + sizeWhichTriggersExpansion = (int)(capacity * loadFactor); + } + + protected void incrementSize() { + size++; + if (size + removed >= sizeWhichTriggersExpansion) { + maybeIncreaseTableCapacity(); + } + } + + private void maybeIncreaseTableCapacity() { + int old_capacity = keys_length(); + int new_capacity = (removed >= size) + ? old_capacity + : 2 * old_capacity; + + if (TUNE) { + System.out.println("Capacity (maybe) increasing from " + old_capacity + " to " + new_capacity + ", removes= " + removed + " size=" + size); + } + + copyOld2New(new_capacity, old_capacity); + } + + /** + * + * @param keyNotFound - + * @return true if keyNotFound + */ + protected void commonPutOrAddNotFound() { + + if (found_removed != -1) { + removed --; // used up a removed slot + } + incrementSize(); +// debugValidate(); + } + + /** + * only called if actually found and removed an entry + */ + protected void commonRemove() { + removed ++; + size --; + maybeRebalanceRemoves(); +// debugValidate(); + } + + public int size() { + return size; + } + + @FunctionalInterface + public interface CommonCopyOld2New { + void apply(IntConsumer copyToNew, IntPredicate is_valid_old_key); + } + protected abstract boolean is_valid_key(int pos); + protected abstract int keys_length(); + protected abstract void newKeysAndValues(int capacity); + protected abstract void clearKeysAndValues(); + protected abstract void copy_to_new_table(int new_capacity, int old_capacity, CommonCopyOld2New r); + + protected void resetHistogram() { + if (TUNE) { + histogram = new int[200]; + Arrays.fill(histogram, 0); + maxProbe = 0; + } + } + + private void updateHistogram(int nbrProbes) { + histogram[nbrProbes] = 1 + histogram[nbrProbes]; + if (maxProbe < nbrProbes) { + maxProbe = nbrProbes; + } + } + + public void showHistogram() { + if (TUNE) { + int sumI = 0; + for (int i : histogram) { + sumI += i; + } + + System.out.format( + "Histogram of number of probes, loadfactor = %.1f, maxProbe=%,d nbr of find operations at last table size=%,d%n", + loadFactor, maxProbe, sumI); + for (int i = 0; i <= maxProbe; i++) { + if (i == maxProbe && histogram[i] == 0) { + System.out.println("huh?"); + } + System.out.println(i + ": " + histogram[i]); + } + + System.out.println("bytes / entry = " + (float) (keys_length()) * 8 / size()); + System.out.format("size = %,d, prevExpansionTriggerSize = %,d, next = %,d%n", + size(), + (int) ((keys_length() >>> 1) * loadFactor), + (int) (keys_length() * loadFactor)); + } + } + + // test case use + int getCapacity() { + return keys_length(); + } + + protected abstract class CommonKeyIterator implements IntListIterator { + + protected int curPosition; + + protected final int firstPosition; + + protected CommonKeyIterator() { + this.curPosition = moveToNextFilled(0); + firstPosition = curPosition; + } + + @Override + public boolean hasNext() { + return curPosition < keys_length() && curPosition >= 0; + } + + @Override + public boolean hasPrevious() { + if (curPosition > keys_length() || curPosition <= 0) { + return false; + } + + int test = moveToPreviousFilled(curPosition - 1); + return test >= 0; + } + + @Override + /** + * @see org.apache.uima.internal.util.IntListIterator#moveToStart() + */ + public void moveToStart() { + curPosition = moveToNextFilled(0); + } + + @Override + /** + * @see org.apache.uima.internal.util.IntListIterator#moveToEnd() + */ + public void moveToEnd() { + curPosition = moveToPreviousFilled(keys_length() - 1); + } + + } + + /** + * + * @param numberOfElements - + * @param factor - + * @return capacity of the main table (either 2 byte or 4 byte entries) + */ + public static int tableSpace(int numberOfElements, Float factor) { + if (numberOfElements < 0) { + throw new IllegalArgumentException("must be > 0"); + } + final int capacity = Math.round(numberOfElements / factor); + return Math.max(16, Misc.nextHigherPowerOf2(capacity)); + } + + protected void debugValidate() { + // count non-0, non-removed, compare to size + int sum = 0; + for (int i = 0; i < keys_length(); i ++) { + if (is_valid_key(i)) { + sum ++; + if (sum > size) { + System.out.println("debug"); + } + } + } + } +} Modified: uima/uv3/uimaj-v3/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/Int2ObjHashMap.java URL: http://svn.apache.org/viewvc/uima/uv3/uimaj-v3/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/Int2ObjHashMap.java?rev=1818293&r1=1818292&r2=1818293&view=diff ============================================================================== --- uima/uv3/uimaj-v3/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/Int2ObjHashMap.java (original) +++ uima/uv3/uimaj-v3/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/Int2ObjHashMap.java Fri Dec 15 15:32:56 2017 @@ -21,8 +21,11 @@ package org.apache.uima.internal.util; import java.lang.reflect.Array; import java.util.Arrays; +import java.util.HashSet; import java.util.Iterator; import java.util.NoSuchElementException; +import java.util.function.Consumer; +import java.util.function.IntConsumer; import org.apache.uima.util.impl.Constants; @@ -39,132 +42,35 @@ import org.apache.uima.util.impl.Constan * keys are non-0 ints * - 0 is reserved for the empty key slot * - Integer.MIN_VALUE is reserved for removed slot - * Entry set not (yet) impl * * values can be anything, but null is the value returned by get if not found so * values probably should not be null * - * remove not currently supported + * remove supported by replacing the value slot with null, and replacing the key slot with a "removed" token. + * A cleanout of removed items occurs when necessary. * */ -public class Int2ObjHashMap<T> { - - private class KeyIterator implements IntListIterator { +public class Int2ObjHashMap<T> extends Common_hash_support implements Iterable<IntEntry<T>>{ + + private static final int REMOVED_KEY = Integer.MIN_VALUE; - /** - * Keep this always pointing to a non-0 entry, or - * if not valid, outside the range - */ - private int curPosition; - - private final int firstPosition; - - private KeyIterator() { - this.curPosition = 0; - moveToNextFilled(); - firstPosition = curPosition; - } + private class KeyIterator extends CommonKeyIterator implements IntListIterator { - public final boolean hasNext() { - return curPosition < keys.length; - } - - public final int next() { - -// if (!hasNext()) { -// throw new NoSuchElementException(); -// } - try { - final int r = keys[curPosition++]; - moveToNextFilled(); - return r; - } catch (IndexOutOfBoundsException e) { - throw new NoSuchElementException(); - } - } - - /** - * @see org.apache.uima.internal.util.IntListIterator#hasPrevious() - */ - public boolean hasPrevious() { - return (curPosition > firstPosition); - } - - /** - * @see org.apache.uima.internal.util.IntListIterator#previous() - */ - public int previous() { - if (!hasPrevious()) { - throw new NoSuchElementException(); - } - curPosition --; - moveToPreviousFilled(); - return keys[curPosition]; - } - - /** - * @see org.apache.uima.internal.util.IntListIterator#moveToEnd() - */ - public void moveToEnd() { - curPosition = keys.length - 1; - moveToPreviousFilled(); - } - - /** - * @see org.apache.uima.internal.util.IntListIterator#moveToStart() - */ - public void moveToStart() { - curPosition = 0; - moveToNextFilled(); + @Override + public final int nextNvc() { + final int r = keys[curPosition]; + curPosition = moveToNextFilled(curPosition + 1); + return r; } - /** - * advance pos until it points to a non 0 or is 1 past end - * @param pos - * @return updated pos - */ - private void moveToNextFilled() { - final int max = keys.length; - while (true) { - if (curPosition >= max) { - return; - } - if (keys[curPosition] != 0) { - return; - } - curPosition ++; - } + @Override + public int previousNvc() { + curPosition = moveToPreviousFilled(curPosition - 1); + return keys[curPosition]; } - - /** - * decrement pos until it points to a non 0 or is -1 - * @param pos - * @return updated pos - */ - private void moveToPreviousFilled() { - final int max = keys.length; - if (curPosition > max) { - curPosition = max - 1; - } - - while (true) { - if (curPosition < 0) { - return; - } - if (keys[curPosition] != 0) { - return; - } - curPosition --; - } - } - } - - - // set to true to collect statistics for tuning - // you have to also put a call to showHistogram() at the end of the run - private static final boolean TUNE = false; - + } + // this load factor gives, for array doubling strategy: // between 1.5 * 8 bytes (2 words, one for key, one for value) = 12 and // 3 * 8 24 bytes per entry @@ -178,38 +84,36 @@ public class Int2ObjHashMap<T> { // See corresponding Int2IntPerfTest which is disabled normally - private final float loadFactor = (float)0.66; - - private final int initialCapacity; - - private int histogram []; - private int maxProbe = 0; - - private int sizeWhichTriggersExpansion; - private int size; // number of elements in the table +// private final float loadFactor = (float)0.66; +// +// private final int initialCapacity; +// +// private int histogram []; +// private int maxProbe = 0; +// +// private int sizeWhichTriggersExpansion; +// private int size; // number of elements in the table private int [] keys; private T [] values; - private boolean secondTimeShrinkable = false; +// private boolean secondTimeShrinkable = false; + + final private Class<T> componentType; // needed to make new instances of the value array + +// /** set to the first found_removed when searching */ +// private int found_removed; + +// private int removed = 0; // for rebalancing - final private Class<T> componentType; - public Int2ObjHashMap(Class<T> clazz) { - this(clazz, 16); + this(clazz, MIN_SIZE); } - public Int2ObjHashMap(Class<T> clazz, int initialCapacity) { + public Int2ObjHashMap(Class<T> clazz, int initialSizeBeforeExpanding) { + super(initialSizeBeforeExpanding); this.componentType = clazz; - initialCapacity = Misc.nextHigherPowerOf2(initialCapacity); - this.initialCapacity = initialCapacity; - newTableKeepSize(initialCapacity); - size = 0; - if (TUNE) { - histogram = new int[200]; - Arrays.fill(histogram, 0); - maxProbe = 0; - } + newTable(this.initialCapacity); } /** @@ -217,197 +121,316 @@ public class Int2ObjHashMap<T> { * @param clazz * @param initialCapacity */ - private Int2ObjHashMap( - Class<T> clazz, - int initialCapacity, - int sizeWhichTriggersExpansion, - int size, - int[] keys, - T[] values) { - this.componentType = clazz; - this.initialCapacity = Misc.nextHigherPowerOf2(initialCapacity); - this.sizeWhichTriggersExpansion = sizeWhichTriggersExpansion; - this.histogram = null; - this.size = size; - this.keys = Arrays.copyOf(keys, keys.length); - this.values = Arrays.copyOf(values, values.length); + private Int2ObjHashMap(Int2ObjHashMap orig) { + super(orig); + this.componentType = orig.componentType; + this.keys = Arrays.copyOf(orig.keys, keys.length); + this.values = (T[]) Arrays.copyOf(orig.values, values.length); } - private void newTableKeepSize(int capacity) { - // minimum size is 16 - capacity = Math.max(16, Misc.nextHigherPowerOf2(capacity)); - keys = new int[capacity]; - values = (T[]) Array.newInstance(componentType, capacity); - sizeWhichTriggersExpansion = (int)(capacity * loadFactor); - } - - private void incrementSize() { - if (size >= sizeWhichTriggersExpansion) { - increaseTableCapacity(); - } - size++; - } - - private void increaseTableCapacity() { - final int [] oldKeys = keys; - final T [] oldValues = values; - final int oldCapacity = oldKeys.length; - int newCapacity = 2 * oldCapacity; +// private void newTableKeepSize(int capacity) { +// capacity = Math.max(MIN_SIZE, Misc.nextHigherPowerOf2(capacity)); +// keys = new int[capacity]; +// values = (T[]) Array.newInstance(componentType, capacity); +// sizeWhichTriggersExpansion = (int)(capacity * loadFactor); +// } + +// protected void incrementSize() { +// if (size + removed >= sizeWhichTriggersExpansion) { +// increaseTableCapacity(); +// } +// size++; +// } + +// private void increaseTableCapacity() { +// final int [] oldKeys = keys; +// final T [] oldValues = values; +// final int oldCapacity = oldKeys.length; +// int newCapacity = 2 * oldCapacity; +// +// if (TUNE) { +// System.out.println("Capacity increasing from " + oldCapacity + " to " + newCapacity); +// } +// removed = 0; +// newTableKeepSize(newCapacity); +// int vi = 0; +// for (int key : oldKeys) { +// if (key != 0 && key != REMOVED_KEY) { +// putInner(key, oldValues[vi]); +// } +// vi++; +// } +// } - if (TUNE) { - System.out.println("Capacity increasing from " + oldCapacity + " to " + newCapacity); - } - newTableKeepSize(newCapacity); - int vi = 0; - for (int key : oldKeys) { - if (key != 0) { - putInner(key, oldValues[vi]); - } - vi++; - } - } - - // called by clear - private void newTable(int capacity) { - newTableKeepSize(capacity); - size = 0; - resetHistogram(); - } - - private void resetHistogram() { - if (TUNE) { - histogram = new int[200]; - Arrays.fill(histogram, 0); - maxProbe = 0; - } - } - - public void clear() { - // see if size is less than the 1/2 size that triggers expansion - if (size < (sizeWhichTriggersExpansion >>> 1)) { - // if 2nd time then shrink by 50% - // this is done to avoid thrashing around the threshold - if (secondTimeShrinkable) { - secondTimeShrinkable = false; - final int newCapacity = Math.max(initialCapacity, keys.length >>> 1); - if (newCapacity < keys.length) { - newTable(newCapacity); // shrink table by 50% - } else { // don't shrink below minimum - Arrays.fill(keys, 0); - Arrays.fill(values, null); - } - size = 0; - resetHistogram(); - return; - } else { - secondTimeShrinkable = true; - } - } else { - secondTimeShrinkable = false; // reset this to require 2 triggers in a row - } - size = 0; - Arrays.fill(keys, 0); - Arrays.fill(values, null); - resetHistogram(); - } +// // called by clear +// private void newTable(int capacity) { +// newTableKeepSize(capacity); +// size = 0; +// resetHistogram(); +// } + +// private void resetHistogram() { +// if (TUNE) { +// histogram = new int[200]; +// Arrays.fill(histogram, 0); +// maxProbe = 0; +// } +// } + +// public void clear() { +// // see if size is less than the 1/2 size that triggers expansion +// if (size < (sizeWhichTriggersExpansion >>> 1)) { +// // if 2nd time then shrink by 50% +// // this is done to avoid thrashing around the threshold +// if (secondTimeShrinkable) { +// secondTimeShrinkable = false; +// final int newCapacity = Math.max(initialCapacity, keys.length >>> 1); +// if (newCapacity < keys.length) { +// newTable(newCapacity); // shrink table by 50% +// } else { // don't shrink below minimum +// Arrays.fill(keys, 0); +// Arrays.fill(values, null); +// } +// size = 0; +// resetHistogram(); +// return; +// } else { +// secondTimeShrinkable = true; +// } +// } else { +// secondTimeShrinkable = false; // reset this to require 2 triggers in a row +// } +// size = 0; +// Arrays.fill(keys, 0); +// Arrays.fill(values, null); +// resetHistogram(); +// } - /** It gets a ref to the current value of table, and then searches that int array. - * - * @param key - - * @return the probeAddr in keys array - might have a 0 value, or the key value if found - */ - private int find(final int key) { - if (key == 0) { + /** + * Searches the keys for a match + * @param key - + * @return the probeAddr in keys array - The value[probeAddr] is 0 value if not found + */ + + private int findPosition(final int key) { + + if (key == 0) { throw new IllegalArgumentException("0 is an invalid key"); } - - final int hash = Misc.hashInt(key); - - final int[] localKeys = keys; - final int bitMask = localKeys.length - 1; - int probeAddr = hash & bitMask; - - // fast paths - final int testKey = localKeys[probeAddr]; - if (testKey == 0 || testKey == key) { - if (TUNE) { - updateHistogram(1); - } - return probeAddr; - } - - return find2(localKeys, key, probeAddr); - } - - private int find2(final int[] localKeys, final int key, int probeAddr) { - final int bitMask = localKeys.length - 1; - int nbrProbes = 2; - int probeDelta = 1; - probeAddr = bitMask & (probeAddr + (probeDelta++)); - - while (true) { - final int testKey = localKeys[probeAddr]; - if (testKey == 0 || testKey == key) { - break; - } - nbrProbes++; - probeAddr = bitMask & (probeAddr + (probeDelta++)); - } - - if (TUNE) { - final int pv = histogram[nbrProbes]; - - histogram[nbrProbes] = 1 + pv; - if (maxProbe < nbrProbes) { - maxProbe = nbrProbes; - } - } - return probeAddr; - } - - private void updateHistogram(int nbrProbes) { - histogram[nbrProbes] = 1 + histogram[nbrProbes]; - if (maxProbe < nbrProbes) { - maxProbe = nbrProbes; + if (key == REMOVED_KEY) { + throw new IllegalArgumentException("Integer.MIN_VALUE is an invalid key"); } + + + return findPosition( + + // key hash + Misc.hashInt(key), + + //is_eq_or_is_not_present + i -> keys[i] == 0 || keys[i] == key, + + // is_removed_key + i -> keys[i] == REMOVED_KEY + + ); + } +// private int find(final int key) { +// if (key == 0) { +// throw new IllegalArgumentException("0 is an invalid key"); +// } +// if (key == REMOVED_KEY) { +// throw new IllegalArgumentException("Integer.MIN_VALUE is an invalid key"); +// } +// found_removed = 0; +// final int hash = Misc.hashInt(key); +// +// final int[] localKeys = keys; +// final int bitMask = localKeys.length - 1; +// int probeAddr = hash & bitMask; +// +// // fast paths +// final int testKey = localKeys[probeAddr]; +// if (testKey == 0 || testKey == key) { +// if (TUNE) { +// updateHistogram(1); +// } +// return probeAddr; +// } +// if (testKey == REMOVED_KEY) { +// found_removed = probeAddr; +// } +// return find2(localKeys, key, probeAddr); +// } + +// private int find2(final int[] localKeys, final int key, int probeAddr) { +// final int bitMask = localKeys.length - 1; +// int nbrProbes = 2; +// int probeDelta = 1; +// probeAddr = bitMask & (probeAddr + (probeDelta++)); +// +// while (true) { +// final int testKey = localKeys[probeAddr]; +// if (testKey == 0 || testKey == key) { +// break; +// } +// if (found_removed == 0 && testKey == REMOVED_KEY) { +// found_removed = probeAddr; +// } +// nbrProbes++; +// probeAddr = bitMask & (probeAddr + (probeDelta++)); +// } +// +// if (TUNE) { +// final int pv = histogram[nbrProbes]; +// +// histogram[nbrProbes] = 1 + pv; +// if (maxProbe < nbrProbes) { +// maxProbe = nbrProbes; +// } +// } +// return probeAddr; +// } + +// private void updateHistogram(int nbrProbes) { +// histogram[nbrProbes] = 1 + histogram[nbrProbes]; +// if (maxProbe < nbrProbes) { +// maxProbe = nbrProbes; +// } +// } public T get(int key) { - return (key == 0) ? null : values[find(key)]; + return (key == 0) ? null : values[findPosition(key)]; } - public boolean containsKey(int key) { - int probeAddr = find(key); - return probeAddr != 0 && keys[probeAddr] != 0; + public T remove(int key) { + int pos = findPosition(key); + T v = values[pos]; + int k = keys[pos]; + if (k != 0) { + values[pos] = null; + keys[pos] = REMOVED_KEY; + commonRemove(); + } + return v; + } + +// private void maybeRebalanceRemoves() { +// final int new_capacity = keys.length >> 1; +// if (removed > REBALANCE_MIN_REMOVED && +// removed > new_capacity) { +// // cleanup will remove more than 1/2 the items +// +// int [] oldKeys = keys; +// T [] oldValues = values; +// newTable(new_capacity); +// removed = 0; // reset before put, otherwise, causes premature expansion +// +// for (int i = 0; i < oldKeys.length; i++) { +// int k = oldKeys[i]; +// if (k != 0 && k != REMOVED_KEY) { +// put(k, oldValues[i]); +// } +// } +// } +// } + + protected void copy_to_new_table( + /* ignored */int newCapacity, + /* ignored */int oldCapacity, + CommonCopyOld2New commonCopy) { + int [] oldKeys = keys; + T [] oldValues = values; + commonCopy.apply( + + // copyToNew + i -> + putInner(oldKeys[i], oldValues[i]), + + // is_valid_old_key + i -> + oldKeys[i] != 0 && oldKeys[i] != REMOVED_KEY); } - public boolean isKeyValid(int position) { - return (position != 0) && (keys[position] != 0); + // debug +// private void dump(int[] ks) { +// HashSet<Integer> found = new HashSet<>(); +// int nbr0 = 0; +// int nbrRmv = 0; +// for (int k : ks) { +// if (k == 0) { +// nbr0++; +// } else if (k == REMOVED_KEY) { +// nbrRmv ++; +// } else { +// boolean wasAdded = found.add(k); +// if (! wasAdded) { +// System.out.println("dups"); +// } +// } +// } +// } +// +// private boolean checkKeyExists(int key) { +// int c = 0; +// for (int i = 0; i < keys.length; i++) { +// int k = keys[i]; +// if (k == key) { +// c++; +// if (c > 1) { +// System.out.println("found key " + key + " in position " + i); +// return true; +// } +// } +// } +// return false; +// } + + + public boolean containsKey(int key) { + int probeAddr = findPosition(key); + return keys[probeAddr] != 0 ; } - + public T put(int key, T value) { - final int i = find(key); + int i = findPosition(key); final boolean keyNotFound = keys[i] == 0; final T prevValue = values[i]; + + if (! keyNotFound) { // key found + values[i] = value; + return prevValue; + } + + if (found_removed != -1) { + i = found_removed; // use the removed slot for the new value + } +// //debug +// if (checkKeyExists(key)) { +// find(key); +// System.out.println("stop"); +// } +// // debug +// if (key == 322 && (i == 618 || i == 617)) { +// find(key); +// System.out.println("stop"); +// } + keys[i] = key; values[i] = value; - if (keyNotFound) { - incrementSize(); - } + + commonPutOrAddNotFound(); return prevValue; } public void putInner(int key, T value) { - final int i = find(key); + final int i = findPosition(key); assert (keys[i] == 0); keys[i] = key; values[i] = value; } - - public int size() { - return size; - } - + public int[] getSortedKeys() { final int size = size(); if (size == 0) { @@ -416,7 +439,7 @@ public class Int2ObjHashMap<T> { final int[] r = new int[size]; int i = 0; for (int k : keys) { - if (k != 0) { + if (k != 0 && k != REMOVED_KEY) { r[i++] = k; } } @@ -437,6 +460,9 @@ public class Int2ObjHashMap<T> { throw new UnsupportedOperationException();// only makes sense for sorted things } + /** + * @return an iterator<T> over the values in random order + */ public Iterator<T> values() { return new Iterator<T>() { @@ -444,10 +470,8 @@ public class Int2ObjHashMap<T> { * Keep this always pointing to a non-0 entry, or * if not valid, outside the range */ - private int curPosition = 0; - { moveToNextFilled(); } // non-static initializer + private int curPosition = moveToNextFilled(0); - @Override public boolean hasNext() { return curPosition < keys.length; @@ -455,57 +479,83 @@ public class Int2ObjHashMap<T> { @Override public T next() { - try { - final T r = values[curPosition++]; - moveToNextFilled(); - return r; - } catch (IndexOutOfBoundsException e) { + if (!hasNext()) { throw new NoSuchElementException(); } + T r = values[curPosition]; + curPosition = moveToNextFilled(curPosition + 1); + return r; } - private void moveToNextFilled() { - final int max = keys.length; - while (true) { - if (curPosition >= max) { - return; - } - if (keys[curPosition] != 0) { - return; - } - curPosition ++; - } - } +// private void moveToNextFilled() { +// final int max = keys.length; +// while (true) { +// if (curPosition >= max) { +// return; +// } +// int k = keys[curPosition]; +// if (k != 0 && k != REMOVED_KEY) { +// return; +// } +// curPosition ++; +// } +// } }; } - public void showHistogram() { - if (TUNE) { - int sumI = 0; - for (int i : histogram) { - sumI += i; - } + public Int2ObjHashMap<T> copy() { + return new Int2ObjHashMap<>(this); + } + + @Override + public Iterator<IntEntry<T>> iterator() { + + return new Iterator<IntEntry<T>>() { - System.out.format( - "Histogram of number of probes, loadfactor = %.1f, maxProbe=%,d nbr of find operations at last table size=%,d%n", - loadFactor, maxProbe, sumI); - for (int i = 0; i <= maxProbe; i++) { - if (i == maxProbe && histogram[i] == 0) { - System.out.println("huh?"); + /** + * Keep this always pointing to a non-0 entry, or + * if not valid, outside the range + */ + private int curPosition = moveToNextFilled(0); + + @Override + public boolean hasNext() { + return curPosition < keys.length; + } + + @Override + public IntEntry next() { + if (!hasNext()) { + throw new NoSuchElementException(); } - System.out.println(i + ": " + histogram[i]); - } + final IntEntry<T> r = new IntEntry<>(keys[curPosition], values[curPosition]); + curPosition = moveToNextFilled(curPosition + 1); + return r; + } - System.out.println("bytes / entry = " + (float) (keys.length) * 8 / size()); - System.out.format("size = %,d, prevExpansionTriggerSize = %,d, next = %,d%n", - size(), - (int) ((keys.length >>> 1) * loadFactor), - (int) (keys.length * loadFactor)); - } + }; + } - public Int2ObjHashMap<T> copy() { - return new Int2ObjHashMap<>(componentType, initialCapacity, sizeWhichTriggersExpansion, size, keys, values); + protected int keys_length() { + return keys.length; + } + + @Override + protected boolean is_valid_key(int pos) { + return keys[pos] != 0 && keys[pos] != REMOVED_KEY; + } + + @Override + protected void newKeysAndValues(int size) { + keys = new int[size]; + values = (T[]) Array.newInstance(componentType, size); + } + + @Override + protected void clearKeysAndValues() { + Arrays.fill(keys, 0); + Arrays.fill(values, null); } } Modified: uima/uv3/uimaj-v3/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/IntHashSet.java URL: http://svn.apache.org/viewvc/uima/uv3/uimaj-v3/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/IntHashSet.java?rev=1818293&r1=1818292&r2=1818293&view=diff ============================================================================== --- uima/uv3/uimaj-v3/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/IntHashSet.java (original) +++ uima/uv3/uimaj-v3/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/IntHashSet.java Fri Dec 15 15:32:56 2017 @@ -21,11 +21,14 @@ package org.apache.uima.internal.util; import java.util.Arrays; import java.util.NoSuchElementException; +import java.util.function.IntPredicate; import org.apache.uima.util.impl.Constants; /** * A set of non-zero ints. + * Can be negative. + * * 0 reserved internally to indicate "not in the map"; * you will get an exception if you try to store 0 as a value. * @@ -51,40 +54,18 @@ import org.apache.uima.util.impl.Constan * * Automatically switches to full int representation if needed */ -public class IntHashSet implements PositiveIntSet { +public class IntHashSet extends Common_hash_support implements PositiveIntSet { - public static final int SIZE_NEEDING_4_BYTES = 256 * 256 - 2; - public static final float DEFAULT_LOAD_FACTOR = 0.66F; + public static final int SIZE_NEEDING_4_BYTES = 256 * 256 - 2; private static final int REMOVED4 = Integer.MIN_VALUE; private static final int REMOVED2 = Short.MIN_VALUE; - // set to true to collect statistics for tuning - // you have to also put a call to showHistogram() at the end of the run - private static final boolean TUNE = false; - - static int nextHigherPowerOf2(int i) { - return (i < 1) ? 1 : Integer.highestOneBit(i) << ( (Integer.bitCount(i) == 1 ? 0 : 1)); - } - // this load factor gives, for array doubling strategy: // between 1.5 * 4 bytes (1 word for key) = 6 and // 3 * 4 12 bytes per entry // This compares with 160 bytes/entry for the IntArrayRBT impl - - private final float loadFactor = DEFAULT_LOAD_FACTOR; - - private final int initialCapacity; - - private int histogram []; - private int maxProbe = 0; - - private int sizeWhichTriggersExpansion; - private int size; // number of elements in the table - private int nbrRemoved; // number of removed elements (coded as removed) - - private int removedPositionToUse = -1; - + // offset only used with keys2. values stored are key - offset // intent is to have them fit into short data type. // If the offset is 100,000, then the keys range from 100000 - 32766 to 100000 + 32767, includes "0" @@ -97,15 +78,15 @@ public class IntHashSet implements Posit private int [] keys4; private short[] keys2; - - private boolean secondTimeShrinkable = false; + + private boolean isMake4; // these are true values (before any offset adjustment) private int mostPositive = Integer.MIN_VALUE; private int mostNegative = Integer.MAX_VALUE; public IntHashSet() { - this(12, 0); + this(10, 0); } public IntHashSet(int initialCapacity) { @@ -114,87 +95,92 @@ public class IntHashSet implements Posit /** * - * @param initialCapacity - you can add this many before expansion + * @param initialSizeBeforeExpanding - you can add this many before expansion * @param offset - for values in the short range, the amount to subtract * before storing. * If == MIN_VALUE, then force 4 byte ints */ - public IntHashSet(int initialCapacity, int offset) { - this.initialCapacity = initialCapacity; - boolean force4 = offset == Integer.MIN_VALUE; - this.offset = force4 ? 0 : offset; - newTableKeepSize(tableSpace(initialCapacity), force4); - size = 0; - if (TUNE) { - histogram = new int[200]; - Arrays.fill(histogram, 0); - maxProbe = 0; - } + public IntHashSet(int initialSizeBeforeExpanding, int offset) { + super(initialSizeBeforeExpanding); + isMake4 = offset == Integer.MIN_VALUE; + this.offset = isMake4 ? 0 : offset; + newTable(this.initialCapacity); + resetTable(); } - /** - * The number of 32 bit words that are reserved when - * creating a table to hold the specified number of elements - * - * The number is a power of 2. - * - * The number is at least 16. - * - * The number is such that you could add this many elements without - * triggering the capacity expansion. - * - * @param numberOfElements - - * @return - - */ - public int tableSpace(int numberOfElements) { - return tableSpace(numberOfElements, loadFactor); - } +// /** +// * The number of 32 bit words that are reserved when +// * creating a table to hold the specified number of elements +// * +// * The number is a power of 2. +// * +// * The number is at least 16. +// * +// * The number is such that you could add this many elements without +// * triggering the capacity expansion. +// * +// * @param numberOfElements - +// * @return - +// */ +// public int tableSpace(int numberOfElements) { +// return tableSpace(numberOfElements, loadFactor); +// } +// - /** - * - * @param numberOfElements - - * @param factor - - * @return capacity of the main table (either 2 byte or 4 byte entries) - */ - public static int tableSpace(int numberOfElements, Float factor) { - if (numberOfElements < 0) { - throw new IllegalArgumentException("must be > 0"); - } - final int capacity = Math.round(numberOfElements / factor); - return Math.max(16, nextHigherPowerOf2(capacity)); - } - - private void newTableKeepSize(int capacity, boolean make4) { - if (!make4) { - capacity = Math.max(4, nextHigherPowerOf2(capacity)); - make4 = (capacity >= SIZE_NEEDING_4_BYTES); - } - // don't use short values unless - // the number of items is < 65536 - if (make4) { - keys4 = new int[capacity]; - keys2 = null; - } else { - keys2 = new short[capacity]; - keys4 = null; - } - sizeWhichTriggersExpansion = (int)(capacity * loadFactor); - nbrRemoved = 0; - } - - private void incrementSize() { - if ((size + nbrRemoved) >= sizeWhichTriggersExpansion) { - increaseTableCapacity(); - } - size++; + public static int tableSpace(int numberOfElements) { + return Common_hash_support.tableSpace(numberOfElements, 0.66f); } +// /** +// * +// * @param numberOfElements - +// * @param factor - +// * @return capacity of the main table (either 2 byte or 4 byte entries) +// */ +// public static int tableSpace(int numberOfElements, Float factor) { +// if (numberOfElements < 0) { +// throw new IllegalArgumentException("must be > 0"); +// } +// final int capacity = Math.round(numberOfElements / factor); +// return Math.max(16, Misc.nextHigherPowerOf2(capacity)); +// } +// +// private void newTableKeepSize(int capacity, boolean make4) { +// if (!make4) { +// capacity = Math.max(4, nextHigherPowerOf2(capacity)); +// // don't use short values unless +// // the number of items is < 65536 +// make4 = (capacity >= SIZE_NEEDING_4_BYTES); +// } +// +// if (make4) { +// keys4 = new int[capacity]; +// keys2 = null; +// } else { +// keys2 = new short[capacity]; +// keys4 = null; +// } +// sizeWhichTriggersExpansion = (int)(capacity * loadFactor); +// nbrRemoved = 0; +// } + + /** + * Method called by handleHashSet in PositiveIntSet + * to indicate if adding this many items would cause an expansion + * @return true if would not expand + */ public boolean wontExpand() { return wontExpand(1); } + /** + * Method called by handleHashSet in PositiveIntSet + * to indicate if adding this many items would cause an expansion + * @param n the number of items added + * @return true if would not expand + */ public boolean wontExpand(int n) { - return (size + nbrRemoved + n) < sizeWhichTriggersExpansion; + return (size() + removed + n) < sizeWhichTriggersExpansion; } public int getSpaceUsedInWords() { @@ -204,11 +190,7 @@ public class IntHashSet implements Posit public static int getSpaceOverheadInWords() { return 11; } - - private int getCapacity() { - return (null == keys4) ? keys2.length : keys4.length; - } - + /** * Only call this if using short values with offset * @param adjKey @@ -219,174 +201,176 @@ public class IntHashSet implements Posit return adjKey + offset + ((adjKey < 0) ? 1 : 0); } - private void increaseTableCapacity() { - final int oldCapacity = getCapacity(); - // keep same capacity if just removing the "removed" markers would - // shrink the used slots to the same they would have been had there been no removed, and - // the capacity was doubled. - final int newCapacity = (nbrRemoved > size) ? oldCapacity : oldCapacity << 1; - - if (keys2 != null) { - final short[] oldKeys = keys2; - newTableKeepSize(newCapacity, false); - if (newCapacity >= 256 * 256) { // = 65536 - // switch to 4 - if (TUNE) {System.out.println("Switching to 4 byte keys, Capacity increasing from " + oldCapacity + " to " + newCapacity);} - for (short adjKey : oldKeys) { - if (adjKey != 0 && adjKey != REMOVED2) { - addInner4(getRawFromAdjKey(adjKey)); - } - } - - } else { - if (TUNE) {System.out.println("Keeping 2 byte keys, Capacity increasing from " + oldCapacity + " to " + newCapacity);} - for (short adjKey : oldKeys) { - if (adjKey != 0 && adjKey != REMOVED2) { - addInner2(adjKey); - } - } - } - - } else { - final int [] oldKeys = keys4; - if (TUNE) {System.out.println("Capacity increasing from " + oldCapacity + " to " + newCapacity);} - newTableKeepSize(newCapacity, true); - for (int key : oldKeys) { - if (key != 0 && key != REMOVED4) { - addInner4(key); - } - } - } - } +// private void increaseTableCapacity() { +// final int oldCapacity = getCapacity(); +// // keep same capacity if just removing the "removed" markers would +// // shrink the used slots to the same they would have been had there been no removed, and +// // the capacity was doubled. +// final int newCapacity = (nbrRemoved > size) ? oldCapacity : oldCapacity << 1; +// +// if (keys2 != null) { +// final short[] oldKeys = keys2; +// newTableKeepSize(newCapacity, false); +// if (newCapacity >= 256 * 256) { // = 65536 +// // switch to 4 +// if (TUNE) {System.out.println("Switching to 4 byte keys, Capacity increasing from " + oldCapacity + " to " + newCapacity);} +// for (short adjKey : oldKeys) { +// if (adjKey != 0 && adjKey != REMOVED2) { +// addInner4(getRawFromAdjKey(adjKey)); +// } +// } +// +// } else { +// if (TUNE) {System.out.println("Keeping 2 byte keys, Capacity increasing from " + oldCapacity + " to " + newCapacity);} +// for (short adjKey : oldKeys) { +// if (adjKey != 0 && adjKey != REMOVED2) { +// addInner2(adjKey); +// } +// } +// } +// +// } else { +// final int [] oldKeys = keys4; +// if (TUNE) {System.out.println("Capacity increasing from " + oldCapacity + " to " + newCapacity);} +// newTableKeepSize(newCapacity, true); +// for (int key : oldKeys) { +// if (key != 0 && key != REMOVED4) { +// addInner4(key); +// } +// } +// } +// } - // called by clear - private void newTable(int capacity) { - newTableKeepSize(capacity, false); - resetTable(); - } - - private void resetHistogram() { - if (TUNE) { - histogram = new int[200]; - Arrays.fill(histogram, 0); - maxProbe = 0; - } - } +// // called by clear +// private void newTable(int capacity) { +// newTableKeepSize(capacity, false); +// resetTable(); +// } +// +// private void resetHistogram() { +// if (TUNE) { +// histogram = new int[200]; +// Arrays.fill(histogram, 0); +// maxProbe = 0; +// } +// } - private void resetArray() { - if (keys4 == null) { - Arrays.fill(keys2, (short)0); - } else { - Arrays.fill(keys4, 0); - } - resetTable(); - } +// private void resetArray() { +// if (keys4 == null) { +// Arrays.fill(keys2, (short)0); +// } else { +// Arrays.fill(keys4, 0); +// } +// resetTable(); +// } private void resetTable() { mostPositive = Integer.MIN_VALUE; mostNegative = Integer.MAX_VALUE; - resetHistogram(); - size = 0; - nbrRemoved = 0; +// resetHistogram(); +// size = 0; +// nbrRemoved = 0; } @Override public void clear() { - // see if size is less than the 1/2 size that triggers expansion - if (size < (sizeWhichTriggersExpansion >>> 1)) { - // if 2nd time then shrink by 50% - // this is done to avoid thrashing around the threshold - if (secondTimeShrinkable) { - secondTimeShrinkable = false; - final int currentCapacity = getCapacity(); - final int newCapacity = Math.max(initialCapacity, currentCapacity >>> 1); - if (newCapacity < currentCapacity) { - newTable(newCapacity); // shrink table by 50% - } else { // don't shrink below minimum - resetArray(); - } - return; - - } else { - secondTimeShrinkable = true; - } - } else { - secondTimeShrinkable = false; // reset this to require 2 triggers in a row - } - resetArray(); + super.clear(); + resetTable(); +// // see if size is less than the 1/2 size that triggers expansion +// if (size < (sizeWhichTriggersExpansion >>> 1)) { +// // if 2nd time then shrink by 50% +// // this is done to avoid thrashing around the threshold +// if (secondTimeShrinkable) { +// secondTimeShrinkable = false; +// final int currentCapacity = getCapacity(); +// final int newCapacity = Math.max(initialCapacity, currentCapacity >>> 1); +// if (newCapacity < currentCapacity) { +// newTable(newCapacity); // shrink table by 50% +// } else { // don't shrink below minimum +// resetArray(); +// } +// return; +// +// } else { +// secondTimeShrinkable = true; +// } +// } else { +// secondTimeShrinkable = false; // reset this to require 2 triggers in a row +// } +// resetArray(); } - /** - * returns a position in the key/value table - * if the key is not found, then the position will be to the - * place where the key would be put upon adding, and the - * current internal value of keys[position] would be 0. - * - * if the key is found, then keys[position] == key - * @param adjKey - raw key - offset (-1 if this value is 0 or negative, to skip 0, if shorts) - * @return the probeAddr in keys array - might have a 0 value, or the key value if found - */ - private int findPosition(final int adjKey) { - return findPosition(adjKey, false); - } - - private int findPosition(final int adjKey, final boolean includeRemoved) { - if (adjKey == 0) { - throw new IllegalArgumentException("0 is an invalid key"); - } - - final int hash = Misc.hashInt(adjKey); - int nbrProbes = 1; - int probeDelta = 1; - int probeAddr; - removedPositionToUse = -1; - - if (keys4 == null) { - final short[] localKeys2 = keys2; - final int bitMask = localKeys2.length - 1; - probeAddr = hash & bitMask; - - while (true) { - final int testKey = localKeys2[probeAddr]; - if (includeRemoved && (removedPositionToUse == -1) && (testKey == REMOVED2)) { - nbrRemoved --; // because caller will use this as a slot for adding - removedPositionToUse = probeAddr; - } - if (testKey == 0 || testKey == adjKey) { - break; - } - nbrProbes++; - probeAddr = bitMask & (probeAddr + (probeDelta++)); - } - } else { - final int[] localKeys4 = keys4; - final int bitMask = localKeys4.length - 1; - probeAddr = hash & bitMask; - while (true) { - final int testKey = localKeys4[probeAddr]; - if (includeRemoved && (removedPositionToUse == -1) && (testKey == REMOVED4)) { - nbrRemoved --; // because caller will use this as a slot for adding - removedPositionToUse = probeAddr; - } - if (testKey == 0 || testKey == adjKey) { - break; - } - nbrProbes++; - probeAddr = bitMask & (probeAddr + (probeDelta++)); - } - } - - if (TUNE) { - final int pv = histogram[nbrProbes]; - - histogram[nbrProbes] = 1 + pv; - if (maxProbe < nbrProbes) { - maxProbe = nbrProbes; - } - } - - return probeAddr; - } +// /** +// * returns a position in the key/value table +// * if the key is not found, then the position will be to the +// * place where the key would be put upon adding, and the +// * current internal value of keys[position] would be 0. +// * +// * if the key is found, then keys[position] == key +// * @param adjKey - raw key - offset (-1 if this value is 0 or negative, to skip 0, if shorts) +// * @return the probeAddr in keys array - might have a 0 value, or the key value if found +// */ +// private int findPosition(final int adjKey) { +// return findPosition(adjKey, false); +// } +// +// private int findPosition(final int adjKey, final boolean includeRemoved) { +// if (adjKey == 0) { +// throw new IllegalArgumentException("0 is an invalid key"); +// } +// +// final int hash = Misc.hashInt(adjKey); +// int nbrProbes = 1; +// int probeDelta = 1; +// int probeAddr; +// removedPositionToUse = -1; +// +// if (keys4 == null) { +// final short[] localKeys2 = keys2; +// final int bitMask = localKeys2.length - 1; +// probeAddr = hash & bitMask; +// +// while (true) { +// final int testKey = localKeys2[probeAddr]; +// if (includeRemoved && (removedPositionToUse == -1) && (testKey == REMOVED2)) { +// nbrRemoved --; // because caller will use this as a slot for adding +// removedPositionToUse = probeAddr; +// } +// if (testKey == 0 || testKey == adjKey) { +// break; +// } +// nbrProbes++; +// probeAddr = bitMask & (probeAddr + (probeDelta++)); +// } +// } else { +// final int[] localKeys4 = keys4; +// final int bitMask = localKeys4.length - 1; +// probeAddr = hash & bitMask; +// while (true) { +// final int testKey = localKeys4[probeAddr]; +// if (includeRemoved && (removedPositionToUse == -1) && (testKey == REMOVED4)) { +// nbrRemoved --; // because caller will use this as a slot for adding +// removedPositionToUse = probeAddr; +// } +// if (testKey == 0 || testKey == adjKey) { +// break; +// } +// nbrProbes++; +// probeAddr = bitMask & (probeAddr + (probeDelta++)); +// } +// } +// +// if (TUNE) { +// final int pv = histogram[nbrProbes]; +// +// histogram[nbrProbes] = 1 + pv; +// if (maxProbe < nbrProbes) { +// maxProbe = nbrProbes; +// } +// } +// +// return probeAddr; +// } // only called when keys are shorts private boolean isAdjKeyOutOfRange(int adjKey) { @@ -398,41 +382,112 @@ public class IntHashSet implements Posit @Override public boolean contains(int rawKey) { - return find(rawKey) != -1; + int pos = findPosition(rawKey); + if (pos == -1) { + return false; + } + if (keys4 == null) { + return keys2[pos] != 0; + } else { + return keys4[pos] != 0; + } } + /** + * This method is part of the PositiveSet API, and + * is defined to return an int that could be used with + * iterators to position them. + * + * For this case, it is not used, because + * the iterators don't support positioning this way + * because they are not sorted. + */ @Override public int find(int rawKey) { - if (rawKey == 0) { - return -1; - } + throw new UnsupportedOperationException(); + } + + /** + * @param rawKey the key value to find + * @return the position in the table if present, otherwise the position of the slot where the + * key value would be added, unless the new value is at a position which would require + * the key2 form to be switched to the key4 form, in which case, + * -1 is returned (means not found, and requires conversion to 4 byte keys) + */ + private int findPosition(int rawKey) { + + if (rawKey == 0) { + throw new IllegalArgumentException("0 is an invalid key"); + } + if (keys4 == null) { + // special handling for 2 byte keys with offsets // check for keys never stored in short table // adjKey of Short.MIN_VALUE which is the removed flag final int adjKey = getAdjKey(rawKey); if (isAdjKeyOutOfRange(adjKey)) { return -1; } - final int pos = findPosition(adjKey); - return (keys2[pos] == adjKey) ? pos : -1; + + if (rawKey == REMOVED2) { + throw new IllegalArgumentException(String.valueOf(REMOVED2) + " is an invalid key"); + } + + return findPositionAdjKey(adjKey); + + } else { + + if (rawKey == REMOVED4) { + throw new IllegalArgumentException(String.valueOf(REMOVED4) + " is an invalid key"); + } + + return findPosition4(rawKey); } - // using 4 byte keys, no offset - if (rawKey == Integer.MIN_VALUE) { - return -1; // not stored in table (reserved value for removed items) - } - final int pos = findPosition(rawKey); - return (keys4[pos] == rawKey) ? pos : -1; } + private int findPosition4(int rawKey) { + + return super.findPosition( + + // key hash + Misc.hashInt(rawKey), + + // is_eq_or_is_not_present + i -> keys4[i] == 0 || keys4[i] == rawKey, + + // is_removed_key + i -> keys4[i] == REMOVED4 + ); + } + + private int findPositionAdjKey(int adjKey) { + // special handling for 2 byte keys with offsets + // check for keys never stored in short table + // adjKey of Short.MIN_VALUE which is the removed flag + + return super.findPosition( + + // key hash + Misc.hashInt(adjKey), + + // is_eq_or_is_not_present + i -> keys2[i] == 0 || keys2[i] == adjKey, + + // is_removed_key + i -> keys2[i] == REMOVED2 + ); + } + + /** * return the adjusted key. * never called for 4 byte form * for 2 byte key mode, subtract the offset, and adjust by -1 if 0 or less * Note: returned value can be less than Short.MIN_VALUE * @param rawKey - * @return adjusted key + * @return adjusted key, a range from negative to positive, but never 0 */ private int getAdjKey(int rawKey) { // if (rawKey == 0 || (rawKey == Integer.MIN_VALUE)) { @@ -448,7 +503,9 @@ public class IntHashSet implements Posit private void switchTo4byte() { // convert to 4 byte because values can't be offset and fit in a short final short[] oldKeys = keys2; - newTableKeepSize(getCapacity(), true); // make a 4 table. same size + isMake4 = true; + newTable(getCapacity()); // make a 4 table. same size + removed = 0; for (short adjKey : oldKeys) { if (adjKey != 0 && adjKey != REMOVED2) { addInner4(getRawFromAdjKey(adjKey)); @@ -467,7 +524,7 @@ public class IntHashSet implements Posit throw new IllegalArgumentException("argument must be non-zero"); } - if (size == 0) { + if (size() == 0) { mostPositive = mostNegative = rawKey; } else { if (rawKey > mostPositive) { @@ -479,6 +536,9 @@ public class IntHashSet implements Posit } if (keys4 != null) { + if (rawKey == REMOVED4) { + throw new IllegalArgumentException(String.valueOf(REMOVED4) + " is an invalid key"); + } return find4AndAddIfMissing(rawKey); // short keys @@ -490,26 +550,42 @@ public class IntHashSet implements Posit // key in range } else { - final int i = findPosition(adjKey, true); // reuse removed slots + final int i = findPositionAdjKey(adjKey); if (keys2[i] == adjKey) { return false; } - keys2[ (removedPositionToUse != -1) ? removedPositionToUse : i ] = (short) adjKey; - incrementSize(); + keys2[ (found_removed != -1) ? found_removed : i ] = (short) adjKey; + commonPutOrAddNotFound(); return true; } } } private boolean find4AndAddIfMissing(int rawKey) { - removedPositionToUse = -1; - final int i = findPosition(rawKey, true); + int i = findPosition4(rawKey); if (keys4[i] == rawKey) { - return false; + return false; // already in table } - keys4[ (removedPositionToUse == -1) ? i : removedPositionToUse] = rawKey; - incrementSize(); + + if (found_removed == -1) { + keys4[i] = rawKey; + incrementSize(); + } else { + keys4[found_removed] = rawKey; + commonPutOrAddNotFound(); + } +// keys4[ (found_removed == -1) ? i : found_removed] = rawKey; +// commonPutOrAddNotFound(); +// +// +// removedPositionToUse = -1; +// final int i = findPosition(rawKey, true); +// if (keys4[i] == rawKey) { +// return false; +// } +// keys4[ (found_removed == -1) ? i : found_removed] = rawKey; +// incrementSize(); return true; } @@ -542,13 +618,13 @@ public class IntHashSet implements Posit * @param rawKey */ private void addInner4(int rawKey) { - final int i = findPosition(rawKey); + final int i = findPosition4(rawKey); assert(keys4[i] == 0); keys4[i] = rawKey; } private void addInner2(short adjKey) { - final int i = findPosition(adjKey); + final int i = findPositionAdjKey(adjKey); assert(keys2[i] == 0); keys2[i] = adjKey; } @@ -568,33 +644,35 @@ public class IntHashSet implements Posit */ @Override public boolean remove(int rawKey) { - final int pos = find(rawKey); - if (pos < 0) { +// debugValidate(); + final int pos = findPosition(rawKey); + if (pos == -1 || ((keys4 == null) + ? (keys2[pos] == 0) + : (keys4[pos] == 0)) ) { return false; } +// //debug +// if (size() <= 0) +// System.out.println("debug"); +// assert size() > 0; if (keys4 == null) { keys2[pos] = REMOVED2; } else { keys4[pos] = REMOVED4; } - - size--; - nbrRemoved ++; + if (rawKey == mostPositive) { mostPositive --; // a weak adjustment } if (rawKey == mostNegative) { mostNegative ++; // a weak adjustment } + + commonRemove(); return true; } - - @Override - public int size() { - return size; - } - + /** * * @return a value that is >= the actual most positive value in the table. @@ -651,16 +729,16 @@ public class IntHashSet implements Posit * For short keys, the value stored for adjKey == 0 is -1, adjKey == -1 is -2, etc. */ @Override - public int get(int index) { + public int get(int pos) { final int adjKey; if (keys4 == null) { - adjKey = keys2[index]; + adjKey = keys2[pos]; if (adjKey == 0 || adjKey == REMOVED2) { return 0; // null, not present } return getRawFromAdjKey(adjKey); } else { - adjKey = keys4[index]; + adjKey = keys4[pos]; if (adjKey == 0 || adjKey == REMOVED4) { return 0; // null, not present } @@ -668,65 +746,66 @@ public class IntHashSet implements Posit } } - /** - * advance pos until it points to a non 0 or is 1 past end - * @param pos - * @return updated pos - */ - private int moveToNextFilled(int pos) { - if (pos < 0) { - pos = 0; - } - - final int max = getCapacity(); - if (null == keys4) { - while (true) { - if (pos >= max) { - return pos; - } - int v = get(pos); - if (v != 0 && v != REMOVED2) { - return pos; - } - pos++; - } - } else { - // keys4 case - while (true) { - if (pos >= max) { - return pos; - } - int v = get(pos); - if (v != 0 && v != REMOVED4) { - return pos; - } - pos ++; - } - } - } +// /** +// * advance pos until it points to a non 0 or is 1 past end +// * @param pos +// * @return updated pos +// */ +// private int moveToNextFilled(int pos) { +// if (pos < 0) { +// pos = 0; +// } +// +// final int max = getCapacity(); +// if (null == keys4) { +// while (true) { +// if (pos >= max) { +// return pos; +// } +// int v = get(pos); +// if (v != 0 && v != REMOVED2) { +// return pos; +// } +// pos++; +// } +// } else { +// // keys4 case +// while (true) { +// if (pos >= max) { +// return pos; +// } +// int v = get(pos); +// if (v != 0 && v != REMOVED4) { +// return pos; +// } +// pos ++; +// } +// } +// } - /** - * decrement pos until it points to a non 0 or is -1 - * @param pos - * @return updated pos - */ - private int moveToPreviousFilled(int pos) { - final int max = getCapacity(); - if (pos > max) { - pos = max - 1; - } - - while (true) { - if (pos < 0) { - return pos; - } - int v = get(pos); - if (v != 0 && v != ( (keys4 == null) ? REMOVED2 : REMOVED4)) { - return pos; - } - pos --; - } - } +// /** +// * see if there's a value a pos +// * if not, decrement pos until it points to a non 0 or is -1 +// * @param pos to start looking for a value +// * @return a pos with a value, or -1. if there's a value at the original pos, then that pos is returned. +// */ +// private int moveToPreviousFilled(int pos) { +// final int max = getCapacity(); +// if (pos > max) { +// pos = max - 1; +// } +// +// while (true) { +// if (pos < 0) { +// return pos; +// } +// int v = get(pos); // bug - adjust key! +// if (v != 0 && v != ( (keys4 == null) ? REMOVED2 : REMOVED4)) { +// return pos; +// } +// pos --; +// } +// } private class IntHashSetIterator implements IntListIterator { @@ -741,29 +820,34 @@ public class IntHashSet implements Posit return curPosition < getCapacity(); } - public final int next() { - if (!hasNext()) { - throw new NoSuchElementException(); - } - return get(curPosition++); + public final int nextNvc() { + curPosition = moveToNextFilled(curPosition); + int r = get(curPosition); + curPosition = moveToNextFilled(curPosition + 1); + return r; } - + /** * @see org.apache.uima.internal.util.IntListIterator#hasPrevious() */ public boolean hasPrevious() { - curPosition = moveToPreviousFilled(curPosition); - return (curPosition >= 0); + int prev = moveToPreviousFilled(curPosition - 1); + return (prev >= 0); } - - /** - * @see org.apache.uima.internal.util.IntListIterator#previous() - */ + + @Override public int previous() { - if (!hasPrevious()) { + curPosition = moveToPreviousFilled(curPosition - 1); + if (curPosition < 0) { throw new NoSuchElementException(); } - return get(curPosition--); + return get(curPosition); + } + + @Override + public int previousNvc() { + curPosition = moveToPreviousFilled(curPosition - 1); + return get(curPosition); } /** @@ -859,7 +943,7 @@ public class IntHashSet implements Posit return String .format( "IntHashSet [loadFactor=%s, initialCapacity=%s, sizeWhichTriggersExpansion=%s, size=%s, offset=%s%n keys4=%s%n keys2=%s%n secondTimeShrinkable=%s, mostPositive=%s, mostNegative=%s]", - loadFactor, initialCapacity, sizeWhichTriggersExpansion, size, offset, + loadFactor, initialCapacity, sizeWhichTriggersExpansion, size(), offset, Arrays.toString(keys4), Arrays.toString(keys2), secondTimeShrinkable, mostPositive, mostNegative); } @@ -872,6 +956,82 @@ public class IntHashSet implements Posit int getOffset() { return offset; } + + @Override + protected boolean is_valid_key(int pos) { + if (keys4 == null) { + return keys2[pos] != 0 && keys2[pos] != REMOVED2; + } + return keys4[pos] != 0 && keys4[pos] != REMOVED4; + } + + @Override + protected int keys_length() { + return (keys4 == null) ? keys2.length : keys4.length; + } + + @Override + protected void newKeysAndValues(int capacity) { + if (isMake4) { + keys4 = new int[capacity]; + keys2 = null; + } else { + keys2 = new short[capacity]; + keys4 = null; + } + } + + @Override + protected void clearKeysAndValues() { + if (keys4 == null) { + Arrays.fill(keys2, (short)0); + } else { + Arrays.fill(keys4, 0); + } + resetTable(); + } + + @Override + protected void copy_to_new_table( + int new_capacity, + int old_capacity, + CommonCopyOld2New commonCopy) { + // logic covers + // 2 sizes of copying old 2 new + // logic to switch to 4 byte key size + + if (keys2 != null) { + final short[] oldKeys = keys2; + IntPredicate oldKeyValid = i -> oldKeys[i] != 0 && oldKeys[i] != REMOVED2; + + if (new_capacity >= 256 * 256) { // == 65536 + // switch to 4 + if (TUNE) {System.out.println("Switching to 4 byte keys");} + isMake4 = true; + commonCopy.apply( + // copyToNew + i -> addInner4(getRawFromAdjKey(oldKeys[i])), + + oldKeyValid); // is_valid_old_key + } else { + commonCopy.apply( + + // copyToNew + i -> addInner2(oldKeys[i]), + + oldKeyValid); // is_valid_old_key + } + } else { + final int[] oldKeys = keys4; +// if (TUNE) {System.out.println("Capacity increasing from " + old_capacity + " to " + new_capacity);} + commonCopy.apply( + // copyToNew + i -> addInner4(oldKeys[i]), + + i -> oldKeys[i] != 0 && oldKeys[i] != REMOVED4); + } + + } }