This is an automated email from the ASF dual-hosted git repository. alsay pushed a commit to branch compressed_iterator in repository https://gitbox.apache.org/repos/asf/datasketches-java.git
commit bde0b6f2689ea671b7a2f72c1ecdf028565e3f9c Author: AlexanderSaydakov <[email protected]> AuthorDate: Tue Feb 4 16:15:20 2025 -0800 wrap(byte[]) --- .../theta/BytesCompactCompressedHashIterator.java | 93 ++++++++++++ .../theta/BytesCompactHashIterator.java | 53 +++++++ .../apache/datasketches/theta/CompactSketch.java | 54 +++++++ .../datasketches/theta/DirectCompactSketch.java | 4 +- .../theta/WrappedCompactCompressedSketch.java | 111 ++++++++++++++ .../datasketches/theta/WrappedCompactSketch.java | 165 +++++++++++++++++++++ .../datasketches/theta/CompactSketchTest.java | 34 +++++ 7 files changed, 512 insertions(+), 2 deletions(-) diff --git a/src/main/java/org/apache/datasketches/theta/BytesCompactCompressedHashIterator.java b/src/main/java/org/apache/datasketches/theta/BytesCompactCompressedHashIterator.java new file mode 100644 index 00000000..97792da2 --- /dev/null +++ b/src/main/java/org/apache/datasketches/theta/BytesCompactCompressedHashIterator.java @@ -0,0 +1,93 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +package org.apache.datasketches.theta; + +/* + * This is to uncompress serial version 4 sketch incrementally + */ +class BytesCompactCompressedHashIterator implements HashIterator { + private byte[] bytes; + private int offset; + private int entryBits; + private int numEntries; + private int index; + private long previous; + private int offsetBits; + private long[] buffer; + private boolean isBlockMode; + + BytesCompactCompressedHashIterator( + final byte[] bytes, + final int offset, + final int entryBits, + final int numEntries + ) { + this.bytes = bytes; + this.offset = offset; + this.entryBits = entryBits; + this.numEntries = numEntries; + index = -1; + previous = 0; + offsetBits = 0; + buffer = new long[8]; + isBlockMode = numEntries >= 8; + } + + @Override + public long get() { + return buffer[index & 7]; + } + + @Override + public boolean next() { + if (++index == numEntries) { return false; } + if (isBlockMode) { + if ((index & 7) == 0) { + if (numEntries - index >= 8) { + unpack8(); + } else { + isBlockMode = false; + unpack1(); + } + } + } else { + unpack1(); + } + return true; + } + + private void unpack1() { + final int i = index & 7; + BitPacking.unpackBits(buffer, i, entryBits, bytes, offset, offsetBits); + offset += (offsetBits + entryBits) >>> 3; + offsetBits = (offsetBits + entryBits) & 7; + buffer[i] += previous; + previous = buffer[i]; + } + + private void unpack8() { + BitPacking.unpackBitsBlock8(buffer, 0, bytes, offset, entryBits); + offset += entryBits; + for (int i = 0; i < 8; i++) { + buffer[i] += previous; + previous = buffer[i]; + } + } +} diff --git a/src/main/java/org/apache/datasketches/theta/BytesCompactHashIterator.java b/src/main/java/org/apache/datasketches/theta/BytesCompactHashIterator.java new file mode 100644 index 00000000..20e21da1 --- /dev/null +++ b/src/main/java/org/apache/datasketches/theta/BytesCompactHashIterator.java @@ -0,0 +1,53 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +package org.apache.datasketches.theta; + +import org.apache.datasketches.common.ByteArrayUtil; + +/* + * This is to iterate over serial version 3 sketch representation + */ +class BytesCompactHashIterator implements HashIterator { + final private byte[] bytes; + final private int offset; + final private int numEntries; + private int index; + + BytesCompactHashIterator( + final byte[] bytes, + final int offset, + final int numEntries + ) { + this.bytes = bytes; + this.offset = offset; + this.numEntries = numEntries; + index = -1; + } + + @Override + public long get() { + return ByteArrayUtil.getLongLE(bytes, offset + index * Long.BYTES); + } + + @Override + public boolean next() { + return ++index < numEntries; + } +} diff --git a/src/main/java/org/apache/datasketches/theta/CompactSketch.java b/src/main/java/org/apache/datasketches/theta/CompactSketch.java index 7a366fe0..b6431416 100644 --- a/src/main/java/org/apache/datasketches/theta/CompactSketch.java +++ b/src/main/java/org/apache/datasketches/theta/CompactSketch.java @@ -19,11 +19,15 @@ package org.apache.datasketches.theta; +import static org.apache.datasketches.common.ByteArrayUtil.getShortLE; import static org.apache.datasketches.common.Family.idToFamily; import static org.apache.datasketches.theta.PreambleUtil.COMPACT_FLAG_MASK; import static org.apache.datasketches.theta.PreambleUtil.EMPTY_FLAG_MASK; +import static org.apache.datasketches.theta.PreambleUtil.FLAGS_BYTE; import static org.apache.datasketches.theta.PreambleUtil.ORDERED_FLAG_MASK; +import static org.apache.datasketches.theta.PreambleUtil.PREAMBLE_LONGS_BYTE; import static org.apache.datasketches.theta.PreambleUtil.READ_ONLY_FLAG_MASK; +import static org.apache.datasketches.theta.PreambleUtil.SEED_HASH_SHORT; import static org.apache.datasketches.theta.PreambleUtil.extractFamilyID; import static org.apache.datasketches.theta.PreambleUtil.extractFlags; import static org.apache.datasketches.theta.PreambleUtil.extractPreLongs; @@ -224,6 +228,56 @@ public abstract class CompactSketch extends Sketch { "Corrupted: Serialization Version " + serVer + " not recognized."); } + public static CompactSketch wrap(final byte[] bytes) { + return wrap(bytes, ThetaUtil.DEFAULT_UPDATE_SEED, false); + } + + public static CompactSketch wrap(final byte[] bytes, final long expectedSeed) { + return wrap(bytes, expectedSeed, true); + } + + private static CompactSketch wrap(final byte[] bytes, final long seed, final boolean enforceSeed) { + final int serVer = bytes[PreambleUtil.SER_VER_BYTE]; + final int familyId = bytes[PreambleUtil.FAMILY_BYTE]; + final Family family = Family.idToFamily(familyId); + if (family != Family.COMPACT) { + throw new IllegalArgumentException("Corrupted: " + family + " is not Compact!"); + } + final short seedHash = ThetaUtil.computeSeedHash(seed); + if (serVer == 4) { + return WrappedCompactCompressedSketch.wrapInstance(bytes, seedHash); + } else if (serVer == 3) { + final int flags = bytes[FLAGS_BYTE]; + if ((flags & EMPTY_FLAG_MASK) > 0) { + return EmptyCompactSketch.getHeapInstance(Memory.wrap(bytes)); + } + final int preLongs = bytes[PREAMBLE_LONGS_BYTE]; + if (otherCheckForSingleItem(preLongs, serVer, familyId, flags)) { + return SingleItemSketch.heapify(Memory.wrap(bytes), enforceSeed ? seedHash : getShortLE(bytes, SEED_HASH_SHORT)); + } + //not empty & not singleItem + final boolean compactFlag = (flags & COMPACT_FLAG_MASK) > 0; + if (!compactFlag) { + throw new SketchesArgumentException( + "Corrupted: COMPACT family sketch image must have compact flag set"); + } + final boolean readOnly = (flags & READ_ONLY_FLAG_MASK) > 0; + if (!readOnly) { + throw new SketchesArgumentException( + "Corrupted: COMPACT family sketch image must have Read-Only flag set"); + } + return WrappedCompactSketch.wrapInstance(bytes, + enforceSeed ? seedHash : getShortLE(bytes, SEED_HASH_SHORT)); + } else if (serVer == 1) { + return ForwardCompatibility.heapify1to3(Memory.wrap(bytes), seedHash); + } else if (serVer == 2) { + return ForwardCompatibility.heapify2to3(Memory.wrap(bytes), + enforceSeed ? seedHash : getShortLE(bytes, SEED_HASH_SHORT)); + } + throw new SketchesArgumentException( + "Corrupted: Serialization Version " + serVer + " not recognized."); + } + //Sketch Overrides @Override diff --git a/src/main/java/org/apache/datasketches/theta/DirectCompactSketch.java b/src/main/java/org/apache/datasketches/theta/DirectCompactSketch.java index baedad17..15b03311 100644 --- a/src/main/java/org/apache/datasketches/theta/DirectCompactSketch.java +++ b/src/main/java/org/apache/datasketches/theta/DirectCompactSketch.java @@ -35,7 +35,7 @@ import org.apache.datasketches.thetacommon.ThetaUtil; /** * An off-heap (Direct), compact, read-only sketch. The internal hash array can be either ordered - * or unordered. + * or unordered. It is not empty, not a single item. * * <p>This sketch can only be associated with a Serialization Version 3 format binary image.</p> * @@ -57,7 +57,7 @@ class DirectCompactSketch extends CompactSketch { } /** - * Wraps the given Memory, which must be a SerVer 3, ordered, CompactSketch image. + * Wraps the given Memory, which must be a SerVer 3, CompactSketch image. * Must check the validity of the Memory before calling. The order bit must be set properly. * @param srcMem <a href="{@docRoot}/resources/dictionary.html#mem">See Memory</a> * @param seedHash The update seedHash. diff --git a/src/main/java/org/apache/datasketches/theta/WrappedCompactCompressedSketch.java b/src/main/java/org/apache/datasketches/theta/WrappedCompactCompressedSketch.java new file mode 100644 index 00000000..170c98ca --- /dev/null +++ b/src/main/java/org/apache/datasketches/theta/WrappedCompactCompressedSketch.java @@ -0,0 +1,111 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +package org.apache.datasketches.theta; + +import static org.apache.datasketches.theta.PreambleUtil.wholeBytesToHoldBits; +import static org.apache.datasketches.theta.PreambleUtil.ENTRY_BITS_BYTE_V4; +import static org.apache.datasketches.theta.PreambleUtil.NUM_ENTRIES_BYTES_BYTE_V4; +import static org.apache.datasketches.theta.PreambleUtil.PREAMBLE_LONGS_BYTE; + +import org.apache.datasketches.common.ByteArrayUtil; +import org.apache.datasketches.thetacommon.ThetaUtil; + +/** + * Wrapper around a serialized compact compressed read-only sketch. It is not empty, not a single item. + * + * <p>This sketch can only be associated with a Serialization Version 4 format binary image.</p> + */ +class WrappedCompactCompressedSketch extends WrappedCompactSketch { + + /** + * Construct this sketch with the given bytes. + * @param bytes containing serialized compact compressed sketch. + */ + WrappedCompactCompressedSketch(final byte[] bytes) { + super(bytes); + } + + /** + * Wraps the given bytes, which must be a SerVer 4 compressed CompactSketch image. + * @param bytes representation of serialized compressed compact sketch. + * @param seedHash The update seedHash. + * <a href="{@docRoot}/resources/dictionary.html#seedHash">See Seed Hash</a>. + * @return this sketch + */ + static WrappedCompactCompressedSketch wrapInstance(final byte[] bytes, final short seedHash) { + ThetaUtil.checkSeedHashes(ByteArrayUtil.getShortLE(bytes, PreambleUtil.SEED_HASH_SHORT), seedHash); + return new WrappedCompactCompressedSketch(bytes); + } + + //Sketch Overrides + + @Override + public int getCurrentBytes() { + final int preLongs = bytes_[PREAMBLE_LONGS_BYTE]; + final int entryBits = bytes_[ENTRY_BITS_BYTE_V4]; + final int numEntriesBytes = bytes_[NUM_ENTRIES_BYTES_BYTE_V4]; + return preLongs * Long.BYTES + numEntriesBytes + wholeBytesToHoldBits(getRetainedEntries() * entryBits); + } + + private static final int START_PACKED_DATA_EXACT_MODE = 8; + private static final int START_PACKED_DATA_ESTIMATION_MODE = 16; + + @Override + public int getRetainedEntries(final boolean valid) { //compact is always valid + // number of entries is stored using variable length encoding + // most significant bytes with all zeros are not stored + // one byte in the preamble has the number of non-zero bytes used + final int preLongs = bytes_[PREAMBLE_LONGS_BYTE]; // if > 1 then the second long has theta + final int numEntriesBytes = bytes_[NUM_ENTRIES_BYTES_BYTE_V4]; + int offsetBytes = preLongs > 1 ? START_PACKED_DATA_ESTIMATION_MODE : START_PACKED_DATA_EXACT_MODE; + int numEntries = 0; + for (int i = 0; i < numEntriesBytes; i++) { + numEntries |= Byte.toUnsignedInt(bytes_[offsetBytes++]) << (i << 3); + } + return numEntries; + } + + @Override + public long getThetaLong() { + final int preLongs = bytes_[PREAMBLE_LONGS_BYTE]; + return (preLongs > 1) ? ByteArrayUtil.getLongLE(bytes_, 8) : Long.MAX_VALUE; + } + + @Override + public boolean isEmpty() { + return false; + } + + @Override + public boolean isOrdered() { + return true; + } + + @Override + public HashIterator iterator() { + return new BytesCompactCompressedHashIterator( + bytes_, + (bytes_[PREAMBLE_LONGS_BYTE] > 1 ? START_PACKED_DATA_ESTIMATION_MODE : START_PACKED_DATA_EXACT_MODE) + + bytes_[NUM_ENTRIES_BYTES_BYTE_V4], + bytes_[ENTRY_BITS_BYTE_V4], + getRetainedEntries() + ); + } +} diff --git a/src/main/java/org/apache/datasketches/theta/WrappedCompactSketch.java b/src/main/java/org/apache/datasketches/theta/WrappedCompactSketch.java new file mode 100644 index 00000000..b1073159 --- /dev/null +++ b/src/main/java/org/apache/datasketches/theta/WrappedCompactSketch.java @@ -0,0 +1,165 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +package org.apache.datasketches.theta; + +import static org.apache.datasketches.common.ByteArrayUtil.getIntLE; +import static org.apache.datasketches.common.ByteArrayUtil.getLongLE; +import static org.apache.datasketches.common.ByteArrayUtil.getShortLE; +import static org.apache.datasketches.theta.CompactOperations.memoryToCompact; +import static org.apache.datasketches.theta.PreambleUtil.EMPTY_FLAG_MASK; +import static org.apache.datasketches.theta.PreambleUtil.ORDERED_FLAG_MASK; +import static org.apache.datasketches.theta.PreambleUtil.FLAGS_BYTE; +import static org.apache.datasketches.theta.PreambleUtil.RETAINED_ENTRIES_INT; +import static org.apache.datasketches.theta.PreambleUtil.PREAMBLE_LONGS_BYTE; +import static org.apache.datasketches.theta.PreambleUtil.THETA_LONG; +import static org.apache.datasketches.theta.PreambleUtil.SEED_HASH_SHORT; + +import java.util.Arrays; + +import org.apache.datasketches.memory.Memory; +import org.apache.datasketches.memory.WritableMemory; +import org.apache.datasketches.thetacommon.ThetaUtil; + +/** + * Wrapper around a serialized compact read-only sketch. It is not empty, not a single item. + * + * <p>This sketch can only be associated with a Serialization Version 3 format binary image.</p> + */ +class WrappedCompactSketch extends CompactSketch { + final byte[] bytes_; + + /** + * Construct this sketch with the given bytes. + * @param bytes containing serialized compact sketch. + */ + WrappedCompactSketch(final byte[] bytes) { + bytes_ = bytes; + } + + /** + * Wraps the given Memory, which must be a SerVer 3 CompactSketch image. + * @param bytes representation of serialized compressed compact sketch. + * @param seedHash The update seedHash. + * <a href="{@docRoot}/resources/dictionary.html#seedHash">See Seed Hash</a>. + * @return this sketch + */ + static WrappedCompactSketch wrapInstance(final byte[] bytes, final short seedHash) { + ThetaUtil.checkSeedHashes(getShortLE(bytes, SEED_HASH_SHORT), seedHash); + return new WrappedCompactSketch(bytes); + } + + //Sketch Overrides + + @Override + public CompactSketch compact(final boolean dstOrdered, final WritableMemory dstMem) { + return memoryToCompact(Memory.wrap(bytes_), dstOrdered, dstMem); + } + + @Override + public int getCurrentBytes() { + final int preLongs = bytes_[PreambleUtil.PREAMBLE_LONGS_BYTE]; + final int numEntries = (preLongs == 1) ? 0 : getIntLE(bytes_, RETAINED_ENTRIES_INT); + return (preLongs + numEntries) << 3; + } + + @Override + public int getRetainedEntries(final boolean valid) { //compact is always valid + final int preLongs = bytes_[PREAMBLE_LONGS_BYTE]; + return (preLongs == 1) ? 0 : getIntLE(bytes_, RETAINED_ENTRIES_INT); + } + + @Override + public long getThetaLong() { + final int preLongs = bytes_[PREAMBLE_LONGS_BYTE]; + return (preLongs > 2) ? getLongLE(bytes_, THETA_LONG) : Long.MAX_VALUE; + } + + @Override + public boolean hasMemory() { + return false; + } + + @Override + public boolean isDirect() { + return false; + } + + @Override + public boolean isEmpty() { + return (bytes_[FLAGS_BYTE] & EMPTY_FLAG_MASK) > 0; + } + + @Override + public boolean isOrdered() { + return (bytes_[FLAGS_BYTE] & ORDERED_FLAG_MASK) > 0; + } + + @Override + public boolean isSameResource(final Memory that) { + return false; + } + + @Override + public HashIterator iterator() { + return new BytesCompactHashIterator( + bytes_, + bytes_[PREAMBLE_LONGS_BYTE] << 3, + getRetainedEntries() + ); + } + + @Override + public byte[] toByteArray() { + return Arrays.copyOf(bytes_, getCurrentBytes()); + } + + //restricted methods + + @Override + long[] getCache() { + final long[] cache = new long[getRetainedEntries()]; + int i = 0; + HashIterator it = iterator(); + while (it.next()) { + cache[i++] = it.get(); + } + return cache; + } + + @Override + int getCompactPreambleLongs() { + return bytes_[PREAMBLE_LONGS_BYTE]; + } + + @Override + int getCurrentPreambleLongs() { + return bytes_[PREAMBLE_LONGS_BYTE]; + } + + @Override + Memory getMemory() { + return null; + } + + @Override + short getSeedHash() { + return getShortLE(bytes_, SEED_HASH_SHORT); + } +} diff --git a/src/test/java/org/apache/datasketches/theta/CompactSketchTest.java b/src/test/java/org/apache/datasketches/theta/CompactSketchTest.java index e0f79087..0b49f238 100644 --- a/src/test/java/org/apache/datasketches/theta/CompactSketchTest.java +++ b/src/test/java/org/apache/datasketches/theta/CompactSketchTest.java @@ -587,6 +587,40 @@ public class CompactSketchTest { } } + @Test + public void serializeWrapBytesV3() { + UpdateSketch sk = Sketches.updateSketchBuilder().build(); + for (int i = 0; i < 10000; i++) { + sk.update(i); + } + CompactSketch cs1 = sk.compact(); + byte[] bytes = cs1.toByteArray(); + CompactSketch cs2 = new WrappedCompactSketch(bytes); + assertEquals(cs1.getRetainedEntries(), cs2.getRetainedEntries()); + HashIterator it1 = cs1.iterator(); + HashIterator it2 = cs2.iterator(); + while (it1.next() && it2.next()) { + assertEquals(it2.get(), it2.get()); + } + } + + @Test + public void serializeWrapBytesV4() { + UpdateSketch sk = Sketches.updateSketchBuilder().build(); + for (int i = 0; i < 10000; i++) { + sk.update(i); + } + CompactSketch cs1 = sk.compact(); + byte[] bytes = cs1.toByteArrayCompressed(); + CompactSketch cs2 = new WrappedCompactCompressedSketch(bytes); + assertEquals(cs1.getRetainedEntries(), cs2.getRetainedEntries()); + HashIterator it1 = cs1.iterator(); + HashIterator it2 = cs2.iterator(); + while (it1.next() && it2.next()) { + assertEquals(it2.get(), it2.get()); + } + } + private static class State { String classType = null; int count = 0; --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
