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 <[email protected]> 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 <[email protected]> --- .../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: [email protected] For additional commands, e-mail: [email protected]
