leerho commented on code in PR #582:
URL: https://github.com/apache/datasketches-cpp/pull/582#discussion_r4623164518


##########
kll/include/kll_sketch_impl.hpp:
##########
@@ -193,6 +193,62 @@ void kll_sketch<T, C, A>::update(FwdT&& item) {
   reset_sorted_view();
 }
 
+template<typename T, typename C, typename A>
+template<typename FwdT>
+void kll_sketch<T, C, A>::update(FwdT&& item, uint64_t weight) {
+  if (!check_update_item(item)) { return; }
+  if (weight == 0) throw std::invalid_argument("weight must be at least 1");
+  if (weight > kll_constants::MAX_WEIGHT) {
+    throw std::invalid_argument("weight must be less than 2^61: " + 
std::to_string(weight));
+  }
+  if (weight == 1) {
+    update(std::forward<FwdT>(item));
+    return;
+  }
+  allocate_items(); // first, so that a failure leaves the sketch unchanged
+  if (weight < levels_[0]) { // fits into level zero without compaction
+    update_min_max(static_cast<const T&>(item));
+    // construct each copy before counting it, so that a failed copy leaves a 
valid sketch
+    for (uint64_t i = 1; i < weight; ++i) {
+      new (&items_[levels_[0] - 1]) T(static_cast<const T&>(item));
+      internal_update();
+    }
+    new (&items_[levels_[0] - 1]) T(std::forward<FwdT>(item));
+    internal_update();
+    reset_sorted_view();
+  } else {
+    merge(kll_sketch(k_, static_cast<const T&>(item), weight, comparator_, 
allocator_));
+  }
+}
+
+// An item at level h carries weight 2^h, so one copy of the item at each level
+// whose bit is set in the weight is an exact sketch of that many copies.
+// The weight is less than 2^61, so this needs at most 61 levels.
+template<typename T, typename C, typename A>
+kll_sketch<T, C, A>::kll_sketch(uint16_t k, const T& item, uint64_t weight, 
const C& comparator, const A& allocator):
+comparator_(comparator),
+allocator_(allocator),
+k_(k),
+m_(kll_constants::DEFAULT_M),
+min_k_(k),
+num_levels_(static_cast<uint8_t>(64 - count_leading_zeros_in_u64(weight))),
+is_level_zero_sorted_(true),
+n_(weight),
+levels_(num_levels_ + 1, 0, allocator),
+items_(nullptr),
+items_size_(0),
+min_item_(item),
+max_item_(item),
+sorted_view_(nullptr)
+{
+  for (uint8_t level = 0; level < num_levels_; ++level) {
+    levels_[level + 1] = levels_[level] + static_cast<uint32_t>((weight >> 
level) & 1);
+  }
+  items_size_ = levels_[num_levels_];
+  items_ = allocator_.allocate(items_size_);
+  for (uint32_t i = 0; i < items_size_; ++i) new (&items_[i]) T(item);

Review Comment:
   You're right, thanks. If a copy of the item throws, the destructor doesn't 
run, so the storage and the copies already made leaked. Fixed in 0ab4ab60: the 
constructor now destroys the copies it made and frees the storage before 
rethrowing.



##########
kll/include/kll_sketch_impl.hpp:
##########
@@ -193,6 +193,62 @@ void kll_sketch<T, C, A>::update(FwdT&& item) {
   reset_sorted_view();
 }
 
+template<typename T, typename C, typename A>
+template<typename FwdT>
+void kll_sketch<T, C, A>::update(FwdT&& item, uint64_t weight) {
+  if (!check_update_item(item)) { return; }
+  if (weight == 0) throw std::invalid_argument("weight must be at least 1");
+  if (weight > kll_constants::MAX_WEIGHT) {
+    throw std::invalid_argument("weight must be less than 2^61: " + 
std::to_string(weight));
+  }
+  if (weight == 1) {
+    update(std::forward<FwdT>(item));
+    return;
+  }
+  allocate_items(); // first, so that a failure leaves the sketch unchanged
+  if (weight < levels_[0]) { // fits into level zero without compaction
+    update_min_max(static_cast<const T&>(item));
+    // construct each copy before counting it, so that a failed copy leaves a 
valid sketch
+    for (uint64_t i = 1; i < weight; ++i) {
+      new (&items_[levels_[0] - 1]) T(static_cast<const T&>(item));
+      internal_update();
+    }

Review Comment:
   Good idea, done in 0ab4ab60. The weighted update now resets the sorted view 
right after `allocate_items()`, before it changes anything, so a failed copy 
can't leave a stale view.
   
   A new test, "failure at each item copy of a weighted update", makes each 
item copy throw in turn, for a weight that fits in level zero and one that goes 
through the merge. It checks for leaks and compares the sketch's ranks with 
those of a fresh copy. It fails without either fix. It also showed that 
`merge()` passed an rvalue source to `merge_higher_levels()` as an lvalue, so 
the higher levels were copied instead of moved. `merge()` now forwards it, so 
the merge in the weighted update copies no items.



-- 
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]


---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Reply via email to