[incubator-datasketches-cpp] 01/01: fixed a bug in hll4

[al...@apache.org]

This is an automated email from the ASF dual-hosted git repository.

alsay pushed a commit to branch hll4_fix
in repository https://gitbox.apache.org/repos/asf/incubator-datasketches-cpp.git

commit 933c3d8f643e6874fe7e6c7b333240e3e3ebe7ed
Author: AlexanderSaydakov <Al...@users.noreply.github.com>
AuthorDate: Thu Mar 12 17:10:24 2020 -0700

    fixed a bug in hll4
---
 hll/include/Hll4Array-internal.hpp |  4 ++--
 hll/include/HllArray-internal.hpp  | 23 +++++++++++------------
 hll/include/HllArray.hpp           |  2 +-
 3 files changed, 14 insertions(+), 15 deletions(-)

diff --git a/hll/include/Hll4Array-internal.hpp b/hll/include/Hll4Array-internal.hpp
index 4f47817..30b24f7 100644
--- a/hll/include/Hll4Array-internal.hpp
+++ b/hll/include/Hll4Array-internal.hpp
@@ -115,7 +115,7 @@ uint8_t Hll4Array<A>::getSlot(int slotNo) const {
 template<typename A>
 uint8_t Hll4Array<A>::get_value(uint32_t index) const {
   const uint8_t value = getSlot(index);
-  if (value != HllUtil<A>::AUX_TOKEN) return value;
+  if (value != HllUtil<A>::AUX_TOKEN) return value + this->curMin;
   return auxHashMap->mustFindValueFor(index);
 }
 
@@ -164,7 +164,7 @@ void Hll4Array<A>::internalHll4Update(const int slotNo, const int newVal) {
        ? (lbOnOldValue) : (auxHashMap->mustFindValueFor(slotNo));
 
     if (newVal > actualOldValue) { // 848: actualOldValue could still be 0; newValue > 0
-      // we know that hte array will change, but we haven't actually updated yet
+      // we know that the array will change, but we haven't actually updated yet
       this->hipAndKxQIncrementalUpdate(actualOldValue, newVal);
 
       // newVal >= curMin
diff --git a/hll/include/HllArray-internal.hpp b/hll/include/HllArray-internal.hpp
index 52fc467..b8c0a57 100644
--- a/hll/include/HllArray-internal.hpp
+++ b/hll/include/HllArray-internal.hpp
@@ -644,7 +644,7 @@ HllArray<A>::const_iterator::const_iterator(const uint8_t* array, size_t array_s
 array(array), array_size(array_size), index(index), hll_type(hll_type), exceptions(exceptions), offset(offset), all(all)
 {
   while (this->index < array_size) {
-    value = get_value(array, this->index, hll_type);
+    value = get_value(array, this->index, hll_type, exceptions, offset);
     if (all || value != HllUtil<A>::EMPTY) break;
     this->index++;
   }
@@ -653,7 +653,7 @@ array(array), array_size(array_size), index(index), hll_type(hll_type), exceptio
 template<typename A>
 typename HllArray<A>::const_iterator& HllArray<A>::const_iterator::operator++() {
   while (++index < array_size) {
-    value = get_value(array, index, hll_type);
+    value = get_value(array, index, hll_type, exceptions, offset);
     if (all || value != HllUtil<A>::EMPTY) break;
   }
   return *this;
@@ -666,23 +666,22 @@ bool HllArray<A>::const_iterator::operator!=(const const_iterator& other) const
 
 template<typename A>
 uint32_t HllArray<A>::const_iterator::operator*() const {
-  if (hll_type == target_hll_type::HLL_4) {
-    if (value == HllUtil<A>::AUX_TOKEN) { // exception
-      return HllUtil<A>::pair(index, exceptions->mustFindValueFor(index));
-    }
-    return HllUtil<A>::pair(index, value + offset);
-  }
   return HllUtil<A>::pair(index, value);
 }
 
 template<typename A>
-uint8_t HllArray<A>::const_iterator::get_value(const uint8_t* array, size_t index, target_hll_type hll_type) {
+uint8_t HllArray<A>::const_iterator::get_value(const uint8_t* array, size_t index, target_hll_type hll_type, const AuxHashMap<A>* exceptions, uint8_t offset) {
   if (hll_type == target_hll_type::HLL_4) {
-    const uint8_t value = array[index >> 1];
+    uint8_t value = array[index >> 1];
     if ((index & 1) > 0) { // odd
-        return value >> 4;
+        value >>= 4;
+    } else {
+      value &= HllUtil<A>::loNibbleMask;
+    }
+    if (value == HllUtil<A>::AUX_TOKEN) { // exception
+      return exceptions->mustFindValueFor(index);
     }
-    return value & HllUtil<A>::loNibbleMask;
+    return value + offset;
   } else if (hll_type == target_hll_type::HLL_6) {
     const int start_bit = index * 6;
     const int shift = start_bit & 0x7;
diff --git a/hll/include/HllArray.hpp b/hll/include/HllArray.hpp
index 986587f..1cc64ea 100644
--- a/hll/include/HllArray.hpp
+++ b/hll/include/HllArray.hpp
@@ -128,7 +128,7 @@ private:
   uint8_t offset;
   bool all;
   uint8_t value; // cached value to avoid computing in operator++ and in operator*()
-  static inline uint8_t get_value(const uint8_t* array, size_t index, target_hll_type hll_type);
+  static inline uint8_t get_value(const uint8_t* array, size_t index, target_hll_type hll_type, const AuxHashMap<A>* exceptions, uint8_t offset);
 };
 
 }


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org