Package org.apache.uima.internal.util
Class Common_hash_support
- java.lang.Object
-
- org.apache.uima.internal.util.Common_hash_support
-
- Direct Known Subclasses:
Int2ObjHashMap
,IntHashSet
,Obj2IntIdentityHashMap
,ObjHashSet
public abstract class Common_hash_support extends java.lang.Object
A common superclass for hash maps and hash sets
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description static interface
Common_hash_support.CommonCopyOld2New
protected class
Common_hash_support.CommonKeyIterator
-
Field Summary
Fields Modifier and Type Field Description protected int
found_removed
set to the first found_removed when searchingprotected int[]
histogram
protected int
initialCapacity
protected float
loadFactor
protected int
maxProbe
protected static int
MIN_CAPACITY
protected static int
MIN_CAPACITY_SHRINK
protected static int
MIN_SIZE
protected int
removed
protected boolean
secondTimeShrinkable
private int
size
protected int
sizeWhichTriggersExpansion
protected static boolean
TUNE
private static Common_hash_support
tune_instance
-
Constructor Summary
Constructors Constructor Description Common_hash_support(int initialSizeBeforeExpanding)
Common_hash_support(int initialSizeBeforeExpanding, float factor)
Common_hash_support(Common_hash_support orig)
-
Method Summary
All Methods Static Methods Instance Methods Abstract Methods Concrete Methods Modifier and Type Method Description void
clear()
private void
clearExisting()
protected abstract void
clearKeysAndValues()
protected void
commonPutOrAddNotFound()
protected void
commonRemove()
only called if actually found and removed an entryprotected abstract void
copy_to_new_table(int new_capacity, int old_capacity, Common_hash_support.CommonCopyOld2New r)
private void
copyOld2New(int new_capacity, int old_capacity)
This method calls the subclass's copy_to_new_table method, passing an inner lambda containing common code for copying old to new.protected void
debugValidate()
protected int
findPosition(int hash, java.util.function.IntPredicate is_eq_or_not_present, java.util.function.IntPredicate is_removed_key)
It gets a ref to the current value of table, and then searches that array.(package private) int
getCapacity()
protected void
incrementSize()
protected abstract boolean
is_valid_key(int pos)
protected abstract int
keys_length()
private void
maybeIncreaseTableCapacity()
private void
maybeRebalanceRemoves()
As REMOVED tokens populate, the number of 0's (representing free cells and also the end of bucket chain searches) drops.protected int
moveToNextFilled(int pos)
advance pos until it points to a non 0 or is 1 past end If pos is negative, start at 0.protected int
moveToPreviousFilled(int pos)
decrement pos until it points to a non 0 or is -1 If pos is beyond end start at end.protected abstract void
newKeysAndValues(int capacity)
protected void
newTable(int capacity)
protected void
resetHistogram()
void
showHistogram()
int
size()
static int
tableSpace(int numberOfElements, java.lang.Float factor)
private void
updateHistogram(int nbrProbes)
-
-
-
Field Detail
-
TUNE
protected static final boolean TUNE
- See Also:
- Constant Field Values
-
tune_instance
private static Common_hash_support tune_instance
-
MIN_SIZE
protected static final int MIN_SIZE
- See Also:
- Constant Field Values
-
MIN_CAPACITY
protected static final int MIN_CAPACITY
- See Also:
- Constant Field Values
-
MIN_CAPACITY_SHRINK
protected static final int MIN_CAPACITY_SHRINK
- See Also:
- Constant Field Values
-
loadFactor
protected final float loadFactor
-
initialCapacity
protected final int initialCapacity
-
histogram
protected int[] histogram
-
maxProbe
protected int maxProbe
-
sizeWhichTriggersExpansion
protected int sizeWhichTriggersExpansion
-
size
private int size
-
removed
protected int removed
-
found_removed
protected int found_removed
set to the first found_removed when searching
-
secondTimeShrinkable
protected boolean secondTimeShrinkable
-
-
Constructor Detail
-
Common_hash_support
public Common_hash_support(int initialSizeBeforeExpanding)
- Parameters:
initialSizeBeforeExpanding
- the number of elements the table should hold before expanding
-
Common_hash_support
public Common_hash_support(int initialSizeBeforeExpanding, float factor)
-
Common_hash_support
public Common_hash_support(Common_hash_support orig)
-
-
Method Detail
-
clear
public void clear()
-
clearExisting
private void clearExisting()
-
findPosition
protected int findPosition(int hash, java.util.function.IntPredicate is_eq_or_not_present, java.util.function.IntPredicate is_removed_key)
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.- Parameters:
hash
- the hash code of the keyis_eq_or_not_present
- true if the key at the int position is == to the key, or is 0is_removed_key
- true if the key at the int position is "removed"- Returns:
- the probeAddr in keys array. The value is the not-present-value if not found
-
maybeRebalanceRemoves
private void maybeRebalanceRemoves()
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
-
copyOld2New
private void copyOld2New(int new_capacity, int old_capacity)
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.- Parameters:
new_capacity
-old_capacity
-
-
moveToNextFilled
protected int moveToNextFilled(int pos)
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- Parameters:
pos
- -- Returns:
- updated pos
-
moveToPreviousFilled
protected int moveToPreviousFilled(int 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- Parameters:
pos
- -- Returns:
- updated pos
-
newTable
protected void newTable(int capacity)
-
incrementSize
protected void incrementSize()
-
maybeIncreaseTableCapacity
private void maybeIncreaseTableCapacity()
-
commonPutOrAddNotFound
protected void commonPutOrAddNotFound()
-
commonRemove
protected void commonRemove()
only called if actually found and removed an entry
-
size
public int size()
-
is_valid_key
protected abstract boolean is_valid_key(int pos)
-
keys_length
protected abstract int keys_length()
-
newKeysAndValues
protected abstract void newKeysAndValues(int capacity)
-
clearKeysAndValues
protected abstract void clearKeysAndValues()
-
copy_to_new_table
protected abstract void copy_to_new_table(int new_capacity, int old_capacity, Common_hash_support.CommonCopyOld2New r)
-
resetHistogram
protected void resetHistogram()
-
updateHistogram
private void updateHistogram(int nbrProbes)
-
showHistogram
public void showHistogram()
-
getCapacity
int getCapacity()
-
tableSpace
public static int tableSpace(int numberOfElements, java.lang.Float factor)
- Parameters:
numberOfElements
- -factor
- -- Returns:
- capacity of the main table (either 2 byte or 4 byte entries)
-
debugValidate
protected void debugValidate()
-
-