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 2026/09/23 22:39:24 UTC
(datasketches-java) 01/01: Frequent items: empty means zero stream weight, not zero active items
This is an automated email from the ASF dual-hosted git repository.
leerho pushed a commit to branch fi-empty-semantics
in repository https://gitbox.apache.org/repos/asf/datasketches-java.git
commit 8da630178d8ef90f3216f41ae7202f87a1896e7c
Author: Lee Rhodes <le...@users.noreply.github.com>
AuthorDate: Wed Sep 23 15:39:15 2026 -0700
Frequent items: empty means zero stream weight, not zero active items
A purge can remove every counter while the stream weight and offset stay
positive. isEmpty() treated that state as empty, so toByteArray() wrote
the 8-byte empty form (losing stream weight and offset) and merge()
ignored the other sketch. Parallels apache/datasketches-cpp#527 and #529.
- isEmpty() returns streamWeight == 0 in FrequentLongsSketch and
FrequentItemsSketch.
- toByteArray() handles a non-empty sketch with no active items: full
preamble, no values or keys.
- getInstance(MemorySegment): emptiness is determined by PreLongs; the
empty flag is only cross-checked. Reject a non-empty image whose stream
weight is not positive.
- FrequentLongsSketch string form: flags from isEmpty(); getInstance(String)
masks the flag with EMPTY_FLAG_MASK, requires it to agree with the
stream weight, and accepts a non-empty sketch with no active items.
- PreambleUtil: document emptiness and the flags byte; remove unused
SER_DE_ID_SHORT.
- Cross-language: generate and check purged-to-zero images; checkCpp()
now reads the C++ ascii and utf8 images instead of the Java ones.
Co-Authored-By: Claude Opus 5.5 <no...@anthropic.com>
---
.../frequencies/FrequentItemsSketch.java | 25 +++--
.../frequencies/FrequentLongsSketch.java | 32 ++++--
.../datasketches/frequencies/PreambleUtil.java | 12 +-
.../org/apache/datasketches/frequencies/Util.java | 14 +++
.../FrequentItemsSketchCrossLanguageTest.java | 60 +++++++++-
.../datasketches/frequencies/ItemsSketchTest.java | 85 ++++++++++++++
.../datasketches/frequencies/LongsSketchTest.java | 123 ++++++++++++++++++++-
7 files changed, 324 insertions(+), 27 deletions(-)
diff --git a/src/main/java/org/apache/datasketches/frequencies/FrequentItemsSketch.java b/src/main/java/org/apache/datasketches/frequencies/FrequentItemsSketch.java
index 857d8e1f6..29967491f 100644
--- a/src/main/java/org/apache/datasketches/frequencies/FrequentItemsSketch.java
+++ b/src/main/java/org/apache/datasketches/frequencies/FrequentItemsSketch.java
@@ -43,6 +43,7 @@ import static org.apache.datasketches.frequencies.PreambleUtil.insertPreLongs;
import static org.apache.datasketches.frequencies.PreambleUtil.insertSerVer;
import static org.apache.datasketches.frequencies.Util.LG_MIN_MAP_SIZE;
import static org.apache.datasketches.frequencies.Util.SAMPLE_SIZE;
+import static org.apache.datasketches.frequencies.Util.checkStreamWeight;
import java.lang.foreign.MemorySegment;
import java.lang.reflect.Array;
@@ -242,7 +243,7 @@ public class FrequentItemsSketch<T> {
final int familyID = extractFamilyID(pre0); //Byte 2
final int lgMaxMapSize = extractLgMaxMapSize(pre0); //Byte 3
final int lgCurMapSize = extractLgCurMapSize(pre0); //Byte 4
- final boolean empty = (extractFlags(pre0) & EMPTY_FLAG_MASK) != 0; //Byte 5
+ final boolean emptyFlag = (extractFlags(pre0) & EMPTY_FLAG_MASK) != 0; //Byte 5
// Checks
final boolean preLongsEq1 = (preLongs == 1); //Byte 0
@@ -260,17 +261,19 @@ public class FrequentItemsSketch<T> {
throw new SketchesArgumentException(
"Possible Corruption: FamilyID must be " + actFamID + ": " + familyID);
}
- if (empty ^ preLongsEq1) { //Byte 5 and Byte 0
+ if (emptyFlag ^ preLongsEq1) { //Byte 5 and Byte 0
throw new SketchesArgumentException(
- "Possible Corruption: (PreLongs == 1) ^ Empty == True.");
+ "Possible Corruption: Empty flag does not match PreLongs: flags "
+ + extractFlags(pre0) + ", preLongs " + preLongs);
}
- if (empty) {
+ if (preLongsEq1) { //empty is determined by PreLongs
return new FrequentItemsSketch<>(lgMaxMapSize, LG_MIN_MAP_SIZE);
}
//get full preamble
final long[] preArr = new long[preLongs];
MemorySegment.copy(srcSeg, JAVA_LONG_UNALIGNED, 0, preArr, 0, preLongs);
+ checkStreamWeight(preArr[2]);
final FrequentItemsSketch<T> fis = new FrequentItemsSketch<>(lgMaxMapSize, lgCurMapSize);
fis.streamWeight = 0; //update after
@@ -448,12 +451,13 @@ public class FrequentItemsSketch<T> {
}
/**
- * Returns true if this sketch is empty
+ * Returns true if this sketch is empty, that is, it has not been updated with any positive count.
+ * A sketch that is not empty may retain no items if a purge removed all of them.
*
* @return true if this sketch is empty
*/
public boolean isEmpty() {
- return getNumActiveItems() == 0;
+ return streamWeight == 0;
}
/**
@@ -506,7 +510,8 @@ public class FrequentItemsSketch<T> {
outBytes = 8;
} else {
preLongs = Family.FREQUENCY.getMaxPreLongs();
- bytes = serDe.serializeToByteArray(hashMap.getActiveKeys());
+ //a purge may have removed all items
+ bytes = (activeItems > 0) ? serDe.serializeToByteArray(hashMap.getActiveKeys()) : new byte[0];
outBytes = ((preLongs + activeItems) << 3) + bytes.length;
}
final byte[] outArr = new byte[outBytes];
@@ -533,8 +538,10 @@ public class FrequentItemsSketch<T> {
MemorySegment.copy(preArr, 0, seg, JAVA_LONG_UNALIGNED, 0, preLongs);
final int preBytes = preLongs << 3;
- MemorySegment.copy(hashMap.getActiveValues(), 0, seg, JAVA_LONG_UNALIGNED, preBytes, activeItems);
- MemorySegment.copy(bytes, 0, seg, JAVA_BYTE, preBytes + (activeItems << 3), bytes.length);
+ if (activeItems > 0) {
+ MemorySegment.copy(hashMap.getActiveValues(), 0, seg, JAVA_LONG_UNALIGNED, preBytes, activeItems);
+ MemorySegment.copy(bytes, 0, seg, JAVA_BYTE, preBytes + (activeItems << 3), bytes.length);
+ }
}
return outArr;
}
diff --git a/src/main/java/org/apache/datasketches/frequencies/FrequentLongsSketch.java b/src/main/java/org/apache/datasketches/frequencies/FrequentLongsSketch.java
index f20e97352..81fba6fc8 100644
--- a/src/main/java/org/apache/datasketches/frequencies/FrequentLongsSketch.java
+++ b/src/main/java/org/apache/datasketches/frequencies/FrequentLongsSketch.java
@@ -42,6 +42,7 @@ import static org.apache.datasketches.frequencies.PreambleUtil.insertPreLongs;
import static org.apache.datasketches.frequencies.PreambleUtil.insertSerVer;
import static org.apache.datasketches.frequencies.Util.LG_MIN_MAP_SIZE;
import static org.apache.datasketches.frequencies.Util.SAMPLE_SIZE;
+import static org.apache.datasketches.frequencies.Util.checkStreamWeight;
import java.lang.foreign.MemorySegment;
import java.util.ArrayList;
@@ -235,7 +236,7 @@ public class FrequentLongsSketch {
final int familyID = extractFamilyID(pre0); //Byte 2
final int lgMaxMapSize = extractLgMaxMapSize(pre0); //Byte 3
final int lgCurMapSize = extractLgCurMapSize(pre0); //Byte 4
- final boolean empty = (extractFlags(pre0) & EMPTY_FLAG_MASK) != 0; //Byte 5
+ final boolean emptyFlag = (extractFlags(pre0) & EMPTY_FLAG_MASK) != 0; //Byte 5
// Checks
final boolean preLongsEq1 = (preLongs == 1); //Byte 0
@@ -253,17 +254,19 @@ public class FrequentLongsSketch {
throw new SketchesArgumentException(
"Possible Corruption: FamilyID must be " + actFamID + ": " + familyID);
}
- if (empty ^ preLongsEq1) { //Byte 5 and Byte 0
+ if (emptyFlag ^ preLongsEq1) { //Byte 5 and Byte 0
throw new SketchesArgumentException(
- "Possible Corruption: (PreLongs == 1) ^ Empty == True.");
+ "Possible Corruption: Empty flag does not match PreLongs: flags "
+ + extractFlags(pre0) + ", preLongs " + preLongs);
}
- if (empty) {
+ if (preLongsEq1) { //empty is determined by PreLongs
return new FrequentLongsSketch(lgMaxMapSize, LG_MIN_MAP_SIZE);
}
//get full preamble
final long[] preArr = new long[preLongs];
MemorySegment.copy(srcSeg, JAVA_LONG_UNALIGNED, 0, preArr, 0, preLongs);
+ checkStreamWeight(preArr[2]);
final FrequentLongsSketch fls = new FrequentLongsSketch(lgMaxMapSize, lgCurMapSize);
fls.streamWeight = 0; //update after
@@ -319,11 +322,13 @@ public class FrequentLongsSketch {
throw new SketchesArgumentException("Possible Corruption: Bad SerVer: " + serVer);
}
Family.FREQUENCY.checkFamilyID(famID);
- final boolean empty = flags > 0;
- if (!empty && (numActive == 0)) {
+ final boolean emptyFlag = (flags & EMPTY_FLAG_MASK) != 0;
+ if (emptyFlag != (streamWt == 0)) {
throw new SketchesArgumentException(
- "Possible Corruption: !Empty && NumActive=0; strLen: " + numActive);
+ "Possible Corruption: Empty flag does not match stream weight: flags "
+ + flags + ", stream weight " + streamWt);
}
+ if (streamWt != 0) { checkStreamWeight(streamWt); }
final int numTokens = tokens.length;
if ((2 * numActive) != (numTokens - STR_PREAMBLE_TOKENS - 2)) {
throw new SketchesArgumentException(
@@ -499,12 +504,13 @@ public class FrequentLongsSketch {
}
/**
- * Returns true if this sketch is empty
+ * Returns true if this sketch is empty, that is, it has not been updated with any positive count.
+ * A sketch that is not empty may retain no items if a purge removed all of them.
*
* @return true if this sketch is empty
*/
public boolean isEmpty() {
- return getNumActiveItems() == 0;
+ return streamWeight == 0;
}
/**
@@ -552,7 +558,7 @@ public class FrequentLongsSketch {
final int serVer = SER_VER; //0
final int famID = Family.FREQUENCY.getID(); //1
final int lgMaxMapSz = lgMaxMapSize; //2
- final int flags = (hashMap.getNumActive() == 0) ? EMPTY_FLAG_MASK : 0; //3
+ final int flags = isEmpty() ? EMPTY_FLAG_MASK : 0; //3
final String fmt = "%d,%d,%d,%d,%d,%d,";
final String s =
String.format(fmt, serVer, famID, lgMaxMapSz, flags, streamWeight, offset);
@@ -602,8 +608,10 @@ public class FrequentLongsSketch {
MemorySegment.copy(preArr, 0, seg, JAVA_LONG_UNALIGNED, 0, preLongs);
final int preBytes = preLongs << 3;
- MemorySegment.copy(hashMap.getActiveValues(), 0, seg, JAVA_LONG_UNALIGNED, preBytes, activeItems);
- MemorySegment.copy(hashMap.getActiveKeys(), 0, seg, JAVA_LONG_UNALIGNED, preBytes + (activeItems << 3), activeItems);
+ if (activeItems > 0) { //a purge may have removed all items
+ MemorySegment.copy(hashMap.getActiveValues(), 0, seg, JAVA_LONG_UNALIGNED, preBytes, activeItems);
+ MemorySegment.copy(hashMap.getActiveKeys(), 0, seg, JAVA_LONG_UNALIGNED, preBytes + (activeItems << 3), activeItems);
+ }
}
return outArr;
}
diff --git a/src/main/java/org/apache/datasketches/frequencies/PreambleUtil.java b/src/main/java/org/apache/datasketches/frequencies/PreambleUtil.java
index 490e89391..bd70855ce 100644
--- a/src/main/java/org/apache/datasketches/frequencies/PreambleUtil.java
+++ b/src/main/java/org/apache/datasketches/frequencies/PreambleUtil.java
@@ -57,9 +57,18 @@ import org.apache.datasketches.common.SketchesArgumentException;
* || 31 | 30 | 29 | 28 | 27 | 26 | 25 | 24 |
* 3 ||---------------------------------offset------------------------------------------|
* || 39 | 38 | 37 | 36 | 35 | 34 | 33 | 32 |
- * 5 ||----------start of values buffer, followed by keys buffer------------------------|
+ * 4 ||----------start of values buffer, followed by keys buffer------------------------|
* </pre>
*
+ * <p>Emptiness is determined by PreambleLongs: 1 if the sketch is empty, 4 otherwise.
+ * A sketch is empty if its stream length is zero. A non-empty sketch may have zero active items
+ * if a purge removed all of them; it is serialized with the full preamble and no items.</p>
+ *
+ * <p>Flags (byte 5): only the empty flag is defined, as bits 0 and 2 (mask 0x05). Due to a
+ * historical mistake C++ and Java used different bits, so both are set when writing and either
+ * is accepted when reading. It is only checked for consistency with PreambleLongs.
+ * No other flag bits are defined.</p>
+ *
* @author Lee Rhodes
*/
final class PreambleUtil {
@@ -74,7 +83,6 @@ final class PreambleUtil {
static final int LG_MAX_MAP_SIZE_BYTE = 3;
static final int LG_CUR_MAP_SIZE_BYTE = 4;
static final int FLAGS_BYTE = 5;
- static final int SER_DE_ID_SHORT = 6; // to 7
static final int ACTIVE_ITEMS_INT = 8; // to 11 : 0 to 4 in pre1
static final int STREAMLENGTH_LONG = 16; // to 23 : pre2
static final int OFFSET_LONG = 24; // to 31 : pre3
diff --git a/src/main/java/org/apache/datasketches/frequencies/Util.java b/src/main/java/org/apache/datasketches/frequencies/Util.java
index 743389068..f17d98402 100644
--- a/src/main/java/org/apache/datasketches/frequencies/Util.java
+++ b/src/main/java/org/apache/datasketches/frequencies/Util.java
@@ -19,6 +19,8 @@
package org.apache.datasketches.frequencies;
+import org.apache.datasketches.common.SketchesArgumentException;
+
final class Util {
private Util() {}
@@ -51,4 +53,16 @@ final class Util {
return key;
}
+ /**
+ * Checks the stream weight read from the serialized image of a non-empty sketch.
+ * @param streamWeight the stream weight
+ * @throws SketchesArgumentException if the stream weight is not positive
+ */
+ static void checkStreamWeight(final long streamWeight) {
+ if (streamWeight <= 0) {
+ throw new SketchesArgumentException(
+ "Possible Corruption: stream weight of a non-empty sketch must be positive: " + streamWeight);
+ }
+ }
+
}
diff --git a/src/test/java/org/apache/datasketches/frequencies/FrequentItemsSketchCrossLanguageTest.java b/src/test/java/org/apache/datasketches/frequencies/FrequentItemsSketchCrossLanguageTest.java
index dfa6b6d44..46fb7336c 100644
--- a/src/test/java/org/apache/datasketches/frequencies/FrequentItemsSketchCrossLanguageTest.java
+++ b/src/test/java/org/apache/datasketches/frequencies/FrequentItemsSketchCrossLanguageTest.java
@@ -72,6 +72,34 @@ public class FrequentItemsSketchCrossLanguageTest {
}
}
+ // lgMaxMapSize=8 -> capacity 192; the 193rd distinct item triggers a purge whose
+ // median (1) removes every counter: not empty, with no retained items
+ @Test(groups = {GENERATE_JAVA_FILES}, priority = 0)
+ public void generateBinariesForCompatibilityTestingLongsSketchPurged() throws IOException {
+ final FrequentLongsSketch sk = new FrequentLongsSketch(1 << 8);
+ for (int i = 1; i <= 193; i++) {
+ sk.update(i);
+ }
+ assertFalse(sk.isEmpty());
+ assertEquals(sk.getNumActiveItems(), 0);
+ assertEquals(sk.getStreamLength(), 193);
+ assertEquals(sk.getMaximumError(), 1);
+ putBytesToJavaPath("frequent_long_purged_java.sk", sk.toByteArray());
+ }
+
+ @Test(groups = {GENERATE_JAVA_FILES}, priority = 0)
+ public void generateBinariesForCompatibilityTestingStringsSketchPurged() throws IOException {
+ final FrequentItemsSketch<String> sk = new FrequentItemsSketch<>(1 << 8);
+ for (int i = 1; i <= 193; i++) {
+ sk.update(Integer.toString(i));
+ }
+ assertFalse(sk.isEmpty());
+ assertEquals(sk.getNumActiveItems(), 0);
+ assertEquals(sk.getStreamLength(), 193);
+ assertEquals(sk.getMaximumError(), 1);
+ putBytesToJavaPath("frequent_string_purged_java.sk", sk.toByteArray(new ArrayOfStringsSerDe()));
+ }
+
@Test(groups = {GENERATE_JAVA_FILES}, priority = 0)
public void generateBinariesForCompatibilityTestingStringsSketchAscii() throws IOException {
final FrequentItemsSketch<String> sk = new FrequentItemsSketch<>(64);
@@ -99,6 +127,8 @@ public class FrequentItemsSketchCrossLanguageTest {
public void checkJava() {
longs(GroupLanguage.JAVA);
strings(GroupLanguage.JAVA);
+ longsPurged(GroupLanguage.JAVA);
+ stringsPurged(GroupLanguage.JAVA);
stringsAscii(GroupLanguage.JAVA);
stringsUtf8(GroupLanguage.JAVA);
}
@@ -107,14 +137,18 @@ public class FrequentItemsSketchCrossLanguageTest {
public void checkCpp() {
longs(GroupLanguage.CPP);
strings(GroupLanguage.CPP);
- stringsAscii(GroupLanguage.JAVA);
- stringsUtf8(GroupLanguage.JAVA);
+ longsPurged(GroupLanguage.CPP);
+ stringsPurged(GroupLanguage.CPP);
+ stringsAscii(GroupLanguage.CPP);
+ stringsUtf8(GroupLanguage.CPP);
}
@Test(groups = {CHECK_GO_FILES})
public void checkGo() {
longs(GroupLanguage.GO);
strings(GroupLanguage.GO);
+ longsPurged(GroupLanguage.GO);
+ stringsPurged(GroupLanguage.GO);
stringsAscii(GroupLanguage.GO);
stringsUtf8(GroupLanguage.GO);
}
@@ -155,6 +189,28 @@ public class FrequentItemsSketchCrossLanguageTest {
}
}
+ private static void longsPurged(final GroupLanguage lang) {
+ final String fileName = "frequent_long_purged" + lang.sfx + ".sk";
+ final byte[] bytes = getFileBytes(lang.pth, fileName);
+ if (bytes.length == 0) { return; }
+ final FrequentLongsSketch sketch = FrequentLongsSketch.getInstance(MemorySegment.ofArray(bytes));
+ assertFalse(sketch.isEmpty());
+ assertEquals(sketch.getNumActiveItems(), 0);
+ assertEquals(sketch.getStreamLength(), 193);
+ assertEquals(sketch.getMaximumError(), 1);
+ }
+
+ private static void stringsPurged(final GroupLanguage lang) {
+ final String fileName = "frequent_string_purged" + lang.sfx + ".sk";
+ final byte[] bytes = getFileBytes(lang.pth, fileName);
+ if (bytes.length == 0) { return; }
+ final FrequentItemsSketch<String> sketch = FrequentItemsSketch.getInstance(MemorySegment.ofArray(bytes), new ArrayOfStringsSerDe());
+ assertFalse(sketch.isEmpty());
+ assertEquals(sketch.getNumActiveItems(), 0);
+ assertEquals(sketch.getStreamLength(), 193);
+ assertEquals(sketch.getMaximumError(), 1);
+ }
+
private static void stringsAscii(final GroupLanguage lang) {
final String fileName = "frequent_string_ascii" + lang.sfx + ".sk";
final byte[] bytes = getFileBytes(lang.pth, fileName);
diff --git a/src/test/java/org/apache/datasketches/frequencies/ItemsSketchTest.java b/src/test/java/org/apache/datasketches/frequencies/ItemsSketchTest.java
index e2628b877..73583a3ae 100644
--- a/src/test/java/org/apache/datasketches/frequencies/ItemsSketchTest.java
+++ b/src/test/java/org/apache/datasketches/frequencies/ItemsSketchTest.java
@@ -25,6 +25,7 @@ import static org.apache.datasketches.frequencies.PreambleUtil.FAMILY_BYTE;
import static org.apache.datasketches.frequencies.PreambleUtil.FLAGS_BYTE;
import static org.apache.datasketches.frequencies.PreambleUtil.PREAMBLE_LONGS_BYTE;
import static org.apache.datasketches.frequencies.PreambleUtil.SER_VER_BYTE;
+import static org.apache.datasketches.frequencies.PreambleUtil.STREAMLENGTH_LONG;
import static org.apache.datasketches.frequencies.Util.LG_MIN_MAP_SIZE;
import static org.testng.Assert.assertEquals;
import static org.testng.Assert.assertFalse;
@@ -415,6 +416,90 @@ public class ItemsSketchTest {
}
+ // lgMaxMapSize=8 -> capacity 192; the 193rd distinct item triggers a purge whose
+ // median (1) removes every counter: not empty, no retained items
+ private static FrequentItemsSketch<String> purgedToZero() {
+ final FrequentItemsSketch<String> sk = new FrequentItemsSketch<>(1 << 8);
+ for (int i = 0; i < 193; i++) { sk.update(Integer.toString(i)); }
+ return sk;
+ }
+
+ @Test
+ public void checkPurgedToZeroIsNotEmpty() {
+ final ArrayOfStringsSerDe serDe = new ArrayOfStringsSerDe();
+ final FrequentItemsSketch<String> sk = purgedToZero();
+ assertEquals(sk.getNumActiveItems(), 0);
+ assertFalse(sk.isEmpty());
+ assertEquals(sk.getStreamLength(), 193);
+ assertEquals(sk.getMaximumError(), 1);
+
+ final byte[] bytes = sk.toByteArray(serDe);
+ assertEquals(bytes.length, 32);
+ assertEquals(bytes[PREAMBLE_LONGS_BYTE], 4);
+ assertEquals(bytes[FLAGS_BYTE], 0);
+
+ final FrequentItemsSketch<String> sk2 = FrequentItemsSketch.getInstance(MemorySegment.ofArray(bytes), serDe);
+ assertFalse(sk2.isEmpty());
+ assertEquals(sk2.getNumActiveItems(), 0);
+ assertEquals(sk2.getStreamLength(), 193);
+ assertEquals(sk2.getMaximumError(), 1);
+
+ final FrequentItemsSketch<String> sk3 = new FrequentItemsSketch<>(1 << 8);
+ sk3.update("x");
+ sk3.merge(sk);
+ assertEquals(sk3.getStreamLength(), 194);
+ assertEquals(sk3.getMaximumError(), 1);
+ }
+
+ @Test
+ public void checkResetAfterPurge() {
+ final FrequentItemsSketch<String> sk = purgedToZero();
+ sk.reset();
+ assertTrue(sk.isEmpty());
+ assertEquals(sk.getStreamLength(), 0);
+ assertEquals(sk.getMaximumError(), 0);
+ assertEquals(sk.toByteArray(new ArrayOfStringsSerDe()).length, 8);
+ }
+
+ @Test
+ public void checkEmptyWithEitherLegacyFlag() {
+ final ArrayOfStringsSerDe serDe = new ArrayOfStringsSerDe();
+ final byte[] bytes = new FrequentItemsSketch<String>(1 << 8).toByteArray(serDe);
+ assertEquals(bytes.length, 8);
+ assertEquals(bytes[FLAGS_BYTE], 5);
+ for (final int flags : new int[] {1, 4, 5}) {
+ bytes[FLAGS_BYTE] = (byte) flags;
+ assertTrue(FrequentItemsSketch.getInstance(MemorySegment.ofArray(bytes), serDe).isEmpty());
+ }
+ }
+
+ @Test
+ public void checkCorruptEmptyPreamble() {
+ final ArrayOfStringsSerDe serDe = new ArrayOfStringsSerDe();
+ final byte[] empty = new FrequentItemsSketch<String>(1 << 8).toByteArray(serDe);
+ empty[FLAGS_BYTE] = 0; //preLongs 1 without empty flag
+ tryBadBytes(empty);
+
+ final FrequentItemsSketch<String> sk = new FrequentItemsSketch<>(1 << 8);
+ sk.update("a");
+ final byte[] flagged = sk.toByteArray(serDe);
+ flagged[FLAGS_BYTE] = 5; //preLongs 4 with empty flag
+ tryBadBytes(flagged);
+
+ final byte[] zeroWeight = sk.toByteArray(serDe);
+ MemorySegment.ofArray(zeroWeight).set(JAVA_LONG_UNALIGNED, STREAMLENGTH_LONG, 0L);
+ tryBadBytes(zeroWeight);
+ }
+
+ private static void tryBadBytes(final byte[] bytes) {
+ try {
+ FrequentItemsSketch.getInstance(MemorySegment.ofArray(bytes), new ArrayOfStringsSerDe());
+ fail();
+ } catch (final SketchesArgumentException e) {
+ //expected
+ }
+ }
+
/**
* @param s value to print
*/
diff --git a/src/test/java/org/apache/datasketches/frequencies/LongsSketchTest.java b/src/test/java/org/apache/datasketches/frequencies/LongsSketchTest.java
index c5c56079c..4df537c93 100644
--- a/src/test/java/org/apache/datasketches/frequencies/LongsSketchTest.java
+++ b/src/test/java/org/apache/datasketches/frequencies/LongsSketchTest.java
@@ -27,6 +27,7 @@ import static org.apache.datasketches.frequencies.PreambleUtil.FAMILY_BYTE;
import static org.apache.datasketches.frequencies.PreambleUtil.FLAGS_BYTE;
import static org.apache.datasketches.frequencies.PreambleUtil.PREAMBLE_LONGS_BYTE;
import static org.apache.datasketches.frequencies.PreambleUtil.SER_VER_BYTE;
+import static org.apache.datasketches.frequencies.PreambleUtil.STREAMLENGTH_LONG;
import static org.apache.datasketches.frequencies.Util.LG_MIN_MAP_SIZE;
import static org.testng.Assert.assertEquals;
import static org.testng.Assert.assertFalse;
@@ -533,15 +534,45 @@ public class LongsSketchTest {
}
}
+ @Test
+ public void checkStringDeserNonEmptyNoItems() {
+ final String s = "1," //serVer
+ + "10," //FamID
+ + "3," //lgMaxMapSz
+ + "0," //Empty Flag = false
+ + "7," //stream Len so far
+ + "1," //error offset
+ + "0," //numActive: a purge removed all items
+ + "8,"; //curMapLen
+ final FrequentLongsSketch sk = FrequentLongsSketch.getInstance(s);
+ assertFalse(sk.isEmpty());
+ assertEquals(sk.getNumActiveItems(), 0);
+ assertEquals(sk.getStreamLength(), 7);
+ assertEquals(sk.getMaximumError(), 1);
+ }
+
@Test(expectedExceptions = SketchesArgumentException.class)
- public void checkStringDeserEmptyCorrupt() {
+ public void checkStringDeserEmptyFlagMissing() {
final String s = "1," //serVer
+ "10," //FamID
+ "3," //lgMaxMapSz
+ "0," //Empty Flag = false ... corrupted, should be true
+ + "0," //stream Len: empty
+ + "0," //error offset
+ + "0," //numActive
+ + "8,"; //curMapLen
+ FrequentLongsSketch.getInstance(s);
+ }
+
+ @Test(expectedExceptions = SketchesArgumentException.class)
+ public void checkStringDeserEmptyFlagWithStreamLength() {
+ final String s = "1," //serVer
+ + "10," //FamID
+ + "3," //lgMaxMapSz
+ + "5," //Empty Flag = true ... corrupted, should be false
+ "7," //stream Len so far
+ "1," //error offset
- + "0," //numActive ...conflict with empty
+ + "0," //numActive
+ "8,"; //curMapLen
FrequentLongsSketch.getInstance(s);
}
@@ -600,6 +631,94 @@ public class LongsSketchTest {
}
}
+ // lgMaxMapSize=8 -> capacity 192; the 193rd distinct item triggers a purge whose
+ // median (1) removes every counter: not empty, no retained items
+ private static FrequentLongsSketch purgedToZero() {
+ final FrequentLongsSketch sk = new FrequentLongsSketch(1 << 8);
+ for (long i = 0; i < 193; i++) { sk.update(i); }
+ return sk;
+ }
+
+ @Test
+ public void checkPurgedToZeroIsNotEmpty() {
+ final FrequentLongsSketch sk = purgedToZero();
+ assertEquals(sk.getNumActiveItems(), 0);
+ assertFalse(sk.isEmpty());
+ assertEquals(sk.getStreamLength(), 193);
+ assertEquals(sk.getMaximumError(), 1);
+
+ final byte[] bytes = sk.toByteArray();
+ assertEquals(bytes.length, 32);
+ assertEquals(bytes[PREAMBLE_LONGS_BYTE], 4);
+ assertEquals(bytes[FLAGS_BYTE], 0);
+ assertEquals(sk.getStorageBytes(), 32);
+
+ final FrequentLongsSketch sk2 = FrequentLongsSketch.getInstance(MemorySegment.ofArray(bytes));
+ assertFalse(sk2.isEmpty());
+ assertEquals(sk2.getNumActiveItems(), 0);
+ assertEquals(sk2.getStreamLength(), 193);
+ assertEquals(sk2.getMaximumError(), 1);
+
+ final FrequentLongsSketch sk3 = FrequentLongsSketch.getInstance(sk.serializeToString());
+ assertFalse(sk3.isEmpty());
+ assertEquals(sk3.getStreamLength(), 193);
+ assertEquals(sk3.getMaximumError(), 1);
+ assertEquals(sk3.serializeToString(), sk.serializeToString());
+
+ final FrequentLongsSketch sk4 = new FrequentLongsSketch(1 << 8);
+ sk4.update(999_999);
+ sk4.merge(sk);
+ assertEquals(sk4.getStreamLength(), 194);
+ assertEquals(sk4.getMaximumError(), 1);
+ }
+
+ @Test
+ public void checkResetAfterPurge() {
+ final FrequentLongsSketch sk = purgedToZero();
+ sk.reset();
+ assertTrue(sk.isEmpty());
+ assertEquals(sk.getStreamLength(), 0);
+ assertEquals(sk.getMaximumError(), 0);
+ assertEquals(sk.toByteArray().length, 8);
+ }
+
+ @Test
+ public void checkEmptyWithEitherLegacyFlag() {
+ final byte[] bytes = new FrequentLongsSketch(1 << 8).toByteArray();
+ assertEquals(bytes.length, 8);
+ assertEquals(bytes[FLAGS_BYTE], 5);
+ for (final int flags : new int[] {1, 4, 5}) {
+ bytes[FLAGS_BYTE] = (byte) flags;
+ assertTrue(FrequentLongsSketch.getInstance(MemorySegment.ofArray(bytes)).isEmpty());
+ }
+ }
+
+ @Test
+ public void checkCorruptEmptyPreamble() {
+ final byte[] empty = new FrequentLongsSketch(1 << 8).toByteArray();
+ empty[FLAGS_BYTE] = 0; //preLongs 1 without empty flag
+ tryBadBytes(empty);
+
+ final FrequentLongsSketch sk = new FrequentLongsSketch(1 << 8);
+ sk.update(1);
+ final byte[] flagged = sk.toByteArray();
+ flagged[FLAGS_BYTE] = 5; //preLongs 4 with empty flag
+ tryBadBytes(flagged);
+
+ final byte[] zeroWeight = sk.toByteArray();
+ MemorySegment.ofArray(zeroWeight).set(JAVA_LONG_UNALIGNED, STREAMLENGTH_LONG, 0L);
+ tryBadBytes(zeroWeight);
+ }
+
+ private static void tryBadBytes(final byte[] bytes) {
+ try {
+ FrequentLongsSketch.getInstance(MemorySegment.ofArray(bytes));
+ fail();
+ } catch (final SketchesArgumentException e) {
+ //expected
+ }
+ }
+
/**
* @param s value to print
*/
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org