in src/main/java/org/apache/datasketches/hll/Hll4Update.java [37:115]
static final void internalHll4Update(final AbstractHllArray host, final int slotNo,
final int newValue) {
assert ((0 <= slotNo) && (slotNo < (1 << host.getLgConfigK())));
final int curMin = host.getCurMin();
final int rawStoredOldNibble = host.getNibble(slotNo); //could be 0
final int lbOnOldValue = rawStoredOldNibble + curMin; //provable lower bound, could be 0
if (newValue <= lbOnOldValue) { return; }
//Thus: newValue > lbOnOldValue AND newValue > curMin
AuxHashMap auxHashMap; // = host.getAuxHashMap();
final int actualOldValue;
final int shiftedNewValue; //value - curMin
//Based on whether we have an AUX_TOKEN and whether the shiftedNewValue is greater than
// AUX_TOKEN, we have four cases for how to actually modify the data structure:
// 1. (shiftedNewValue >= AUX_TOKEN) && (rawStoredOldNibble = AUX_TOKEN) //881:
// The byte array already contains aux token
// This is the case where old and new values are both exceptions.
// Therefore, the 4-bit array already is AUX_TOKEN. Only need to update auxMap
// 2. (shiftedNewValue < AUX_TOKEN) && (rawStoredOldNibble = AUX_TOKEN) //885
// This is the (hypothetical) case where old value is an exception and the new one is not,
// which is impossible given that curMin has not changed here and the newValue > oldValue.
// 3. (shiftedNewValue >= AUX_TOKEN) && (rawStoredOldNibble < AUX_TOKEN) //892
// This is the case where the old value is not an exception and the new value is.
// Therefore the AUX_TOKEN must be stored in the 4-bit array and the new value
// added to the exception table.
// 4. (shiftedNewValue < AUX_TOKEN) && (rawStoredOldNibble < AUX_TOKEN) //897
// This is the case where neither the old value nor the new value is an exception.
// Therefore we just overwrite the 4-bit array with the shifted new value.
if (rawStoredOldNibble == AUX_TOKEN) { //846 Note: This is rare and really hard to test!
auxHashMap = host.getAuxHashMap(); //auxHashMap must already exist.
assert auxHashMap != null;
actualOldValue = auxHashMap.mustFindValueFor(slotNo);//lgtm [java/dereferenced-value-may-be-null]
if (newValue <= actualOldValue) { return; }
//We know that the array will be changed, but we haven't actually updated yet.
AbstractHllArray.hipAndKxQIncrementalUpdate(host, actualOldValue, newValue);
shiftedNewValue = newValue - curMin;
assert (shiftedNewValue >= 0);
if (shiftedNewValue >= AUX_TOKEN) { //CASE 1:
auxHashMap.mustReplace(slotNo, newValue); //lgtm [java/dereferenced-value-may-be-null]
}
//else //CASE 2: impossible
} else { //rawStoredOldNibble < AUX_TOKEN
actualOldValue = lbOnOldValue;
//We know that the array will be changed, but we haven't actually updated yet.
AbstractHllArray.hipAndKxQIncrementalUpdate(host, actualOldValue, newValue);
shiftedNewValue = newValue - curMin;
assert (shiftedNewValue >= 0);
if (shiftedNewValue >= AUX_TOKEN) { //CASE 3: //892
host.putNibble(slotNo, AUX_TOKEN);
auxHashMap = host.getAuxHashMap();
if (auxHashMap == null) {
auxHashMap = host.getNewAuxHashMap();
host.putAuxHashMap(auxHashMap, false);
}
auxHashMap.mustAdd(slotNo, newValue);
}
else { // CASE 4: //897
host.putNibble(slotNo, shiftedNewValue);
}
}
// We just changed the HLL array, so it might be time to change curMin
if (actualOldValue == curMin) { //908
assert (host.getNumAtCurMin() >= 1);
host.decNumAtCurMin();
while (host.getNumAtCurMin() == 0) {
//increases curMin by 1, and builds a new aux table,
// shifts values in 4-bit table, and recounts curMin
shiftToBiggerCurMin(host);
}
}
}