You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datasketches.apache.org by le...@apache.org on 2024/02/29 19:44:25 UTC
(datasketches-java) 01/02: Adding some asserts for self-merging and long overruns.
This is an automated email from the ASF dual-hosted git repository.
leerho pushed a commit to branch debug_issue_514
in repository https://gitbox.apache.org/repos/asf/datasketches-java.git
commit 67cf69f80f76e1f498105d581a471d70d8ba2f9e
Author: Lee Rhodes <le...@users.noreply.github.com>
AuthorDate: Wed Feb 28 15:31:27 2024 -0800
Adding some asserts for self-merging and long overruns.
---
.../org/apache/datasketches/kll/KllDoublesHelper.java | 7 +++++--
.../org/apache/datasketches/kll/KllDoublesSketch.java | 3 ++-
.../java/org/apache/datasketches/kll/KllHelper.java | 1 +
.../datasketches/quantilescommon/QuantilesAPI.java | 1 +
.../java/org/apache/datasketches/common/Shuffle.java | 18 ++++++++++++++++++
5 files changed, 27 insertions(+), 3 deletions(-)
diff --git a/src/main/java/org/apache/datasketches/kll/KllDoublesHelper.java b/src/main/java/org/apache/datasketches/kll/KllDoublesHelper.java
index 88da49e3..8a5c98b9 100644
--- a/src/main/java/org/apache/datasketches/kll/KllDoublesHelper.java
+++ b/src/main/java/org/apache/datasketches/kll/KllDoublesHelper.java
@@ -123,8 +123,7 @@ final class KllDoublesHelper {
}
//assumes readOnly = false and UPDATABLE, called from KllDoublesSketch::merge
- static void mergeDoubleImpl(final KllDoublesSketch mySketch,
- final KllDoublesSketch otherDblSk) {
+ static void mergeDoubleImpl(final KllDoublesSketch mySketch, final KllDoublesSketch otherDblSk) {
if (otherDblSk.isEmpty()) { return; }
//capture my key mutable fields before doing any merging
@@ -133,6 +132,8 @@ final class KllDoublesHelper {
final double myMax = myEmpty ? Double.NaN : mySketch.getMaxItem();
final int myMinK = mySketch.getMinK();
final long finalN = mySketch.getN() + otherDblSk.getN();
+ assert finalN <= Long.MAX_VALUE && finalN >= 0 :
+ "The input count has exceeded the capacity of a long and the capability of this sketch.";
//buffers that are referenced multiple times
final int otherNumLevels = otherDblSk.getNumLevels();
@@ -400,6 +401,8 @@ final class KllDoublesHelper {
// If we are at the current top level, add an empty level above it for convenience,
// but do not increment numLevels until later
if (curLevel == (numLevels - 1)) {
+ assert curLevel + 2 < 60 :
+ "The number of levels has exceeded the capability of this sketch.";
inLevels[curLevel + 2] = inLevels[curLevel + 1];
}
diff --git a/src/main/java/org/apache/datasketches/kll/KllDoublesSketch.java b/src/main/java/org/apache/datasketches/kll/KllDoublesSketch.java
index 3cef8471..8883734c 100644
--- a/src/main/java/org/apache/datasketches/kll/KllDoublesSketch.java
+++ b/src/main/java/org/apache/datasketches/kll/KllDoublesSketch.java
@@ -276,7 +276,8 @@ public abstract class KllDoublesSketch extends KllSketch implements QuantilesDou
@Override
public final void merge(final KllSketch other) {
if (readOnly || sketchStructure != UPDATABLE) { throw new SketchesArgumentException(TGT_IS_READ_ONLY_MSG); }
- final KllDoublesSketch othDblSk = (KllDoublesSketch)other; //check cast first
+ if (this == other) { throw new SketchesArgumentException(SELF_MERGE_MSG); }
+ final KllDoublesSketch othDblSk = (KllDoublesSketch)other;
if (othDblSk.isEmpty()) { return; } //then check empty
KllDoublesHelper.mergeDoubleImpl(this, othDblSk);
kllDoublesSV = null;
diff --git a/src/main/java/org/apache/datasketches/kll/KllHelper.java b/src/main/java/org/apache/datasketches/kll/KllHelper.java
index f1d1df9b..ae829506 100644
--- a/src/main/java/org/apache/datasketches/kll/KllHelper.java
+++ b/src/main/java/org/apache/datasketches/kll/KllHelper.java
@@ -632,6 +632,7 @@ final class KllHelper {
//grow levels arr by one and copy the old data to the new array, extra space at the top.
myNewLevelsArr = Arrays.copyOf(myCurLevelsArr, myCurNumLevels + 2);
assert myNewLevelsArr.length == myCurLevelsArr.length + 1;
+ assert myNewLevelsArr.length <= 60 : "The number of levels has exceeded the capability of this sketch.";
myNewNumLevels = myCurNumLevels + 1;
sketch.incNumLevels(); //increment for off-heap
} else {
diff --git a/src/main/java/org/apache/datasketches/quantilescommon/QuantilesAPI.java b/src/main/java/org/apache/datasketches/quantilescommon/QuantilesAPI.java
index 38502eca..f433519e 100644
--- a/src/main/java/org/apache/datasketches/quantilescommon/QuantilesAPI.java
+++ b/src/main/java/org/apache/datasketches/quantilescommon/QuantilesAPI.java
@@ -209,6 +209,7 @@ public interface QuantilesAPI {
static String NOT_SINGLE_ITEM_MSG = "Sketch does not have just one item. ";
static String MEM_REQ_SVR_NULL_MSG = "MemoryRequestServer must not be null. ";
static String TGT_IS_READ_ONLY_MSG = "Target sketch is Read Only, cannot write. ";
+ static String SELF_MERGE_MSG = "A sketch cannot merge with itself. ";
/**
* Gets the user configured parameter k, which controls the accuracy of the sketch
diff --git a/src/test/java/org/apache/datasketches/common/Shuffle.java b/src/test/java/org/apache/datasketches/common/Shuffle.java
index 992d15ab..223e3486 100644
--- a/src/test/java/org/apache/datasketches/common/Shuffle.java
+++ b/src/test/java/org/apache/datasketches/common/Shuffle.java
@@ -99,4 +99,22 @@ public final class Shuffle {
array[i2] = value;
}
+ /**
+ * Shuffle the given input array of type T
+ * @param array input array
+ */
+ public static <T> void shuffle(final T[] array) {
+ final int arrLen = array.length;
+ for (int i = 0; i < arrLen; i++) {
+ final int r = rand.nextInt(i + 1);
+ swap(array, i, r);
+ }
+ }
+
+ private static<T> void swap(final T[] array, final int i1, final int i2) {
+ final T value = array[i1];
+ array[i1] = array[i2];
+ array[i2] = value;
+ }
+
}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org