#106

Build # #106

Build Type

push

Committed by

Commit Message

<a href="https://github.com/apache/datasketches-java/commit/<a class=hub.com/apache/datasketches-java/commit/976201e491c493f06b69bf61adfc1eaf6cff7e2d">976201e49<a href="https://github.com/apache/datasketches-java/commit/976201e491c493f06b69bf61adfc1eaf6cff7e2d">">Merge </a><a class="double-link" href="https://github.com/apache/datasketches-java/commit/<a class="double-link" href="https://github.com/apache/datasketches-java/commit/370df32e4bf62a920feb0ac3abd5bc4428f3cf57">370df32e4</a>">370df32e4</a><a href="https://github.com/apache/datasketches-java/commit/976201e491c493f06b69bf61adfc1eaf6cff7e2d"> into c0763777f">c0763777f</a>

Run Details

390 of 390 new or added lines in 8 files covered. (100.0%)

17652 of 17899 relevant lines covered (98.62%)

0.99 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

83.7

/src/main/java/org/apache/datasketches/tuple/CompactSketch.java

/*
 * 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.tuple;

import static org.apache.datasketches.HashOperations.count;

import java.lang.reflect.Array;
import java.nio.ByteOrder;

import org.apache.datasketches.ByteArrayUtil;
import org.apache.datasketches.Family;
import org.apache.datasketches.ResizeFactor;
import org.apache.datasketches.SketchesArgumentException;
import org.apache.datasketches.memory.Memory;

/**
 * CompactSketches are never created directly. They are created as a result of
 * the compact() method of an UpdatableSketch or as a result of the getResult()
 * method of a set operation like Union, Intersection or AnotB. CompactSketch
 * consists of a compact list (i.e. no intervening spaces) of hash values,
 * corresponding list of Summaries, and a value for theta. The lists may or may
 * not be ordered. CompactSketch is read-only.
 *
 * @param <S> type of Summary
 */
public class CompactSketch<S extends Summary> extends Sketch<S> {
  private static final byte serialVersionWithSummaryClassNameUID = 1;
  private static final byte serialVersionUIDLegacy = 2;
  private static final byte serialVersionUID = 3;
  private static final short defaultSeedHash = (short) 37836; // for compatibility with C++
  private long[] hashArr_;
  private S[] summaryArr_;

  private enum FlagsLegacy { IS_BIG_ENDIAN, IS_EMPTY, HAS_ENTRIES, IS_THETA_INCLUDED }

  private enum Flags { IS_BIG_ENDIAN, IS_READ_ONLY, IS_EMPTY, IS_COMPACT, IS_ORDERED }

  /**
   * Create a CompactSketch from correct components
   * @param hashArr compacted hash array
   * @param summaryArr compacted summary array
   * @param thetaLong long value of theta
   * @param empty empty flag
   */
  CompactSketch(final long[] hashArr, final S[] summaryArr, final long thetaLong, final boolean empty) {
    hashArr_ = hashArr;
    summaryArr_ = summaryArr;
    thetaLong_ = thetaLong;
    empty_ = empty;
  }

  /**
   * This is to create an instance of a CompactSketch given a serialized form
   *
   * @param mem Memory object with serialized CompactSketch
   * @param deserializer the SummaryDeserializer
   */
  @SuppressWarnings({"unchecked"})
  CompactSketch(final Memory mem, final SummaryDeserializer<S> deserializer) {
    int offset = 0;
    final byte preambleLongs = mem.getByte(offset++);
    final byte version = mem.getByte(offset++);
    final byte familyId = mem.getByte(offset++);
    SerializerDeserializer.validateFamily(familyId, preambleLongs);
    if (version > serialVersionUID) {
      throw new SketchesArgumentException(
          "Unsupported serial version. Expected: " + serialVersionUID + " or lower, actual: " + version);
    }
    SerializerDeserializer
      .validateType(mem.getByte(offset++), SerializerDeserializer.SketchType.CompactSketch);
    if (version <= serialVersionUIDLegacy) { // legacy serial format
      final byte flags = mem.getByte(offset++);
      final boolean isBigEndian = (flags & 1 << FlagsLegacy.IS_BIG_ENDIAN.ordinal()) > 0;
      if (isBigEndian ^ ByteOrder.nativeOrder().equals(ByteOrder.BIG_ENDIAN)) {
        throw new SketchesArgumentException("Byte order mismatch");
      }
      empty_ = (flags & 1 << FlagsLegacy.IS_EMPTY.ordinal()) > 0;
      final boolean isThetaIncluded = (flags & 1 << FlagsLegacy.IS_THETA_INCLUDED.ordinal()) > 0;
      if (isThetaIncluded) {
        thetaLong_ = mem.getLong(offset);
        offset += Long.BYTES;
      } else {
        thetaLong_ = Long.MAX_VALUE;
      }
      final boolean hasEntries = (flags & 1 << FlagsLegacy.HAS_ENTRIES.ordinal()) > 0;
      if (hasEntries) {
        int classNameLength = 0;
        if (version == serialVersionWithSummaryClassNameUID) {
          classNameLength = mem.getByte(offset++);
        }
        final int count = mem.getInt(offset);
        offset += Integer.BYTES;
        if (version == serialVersionWithSummaryClassNameUID) {
          offset += classNameLength;
        }
        hashArr_ = new long[count];
        for (int i = 0; i < count; i++) {
          hashArr_[i] = mem.getLong(offset);
          offset += Long.BYTES;
        }
        for (int i = 0; i < count; i++) {
          offset += readSummary(mem, offset, i, count, deserializer);
        }
      }
    } else { // current serial format
      offset++;
      final byte flags = mem.getByte(offset++);
      offset += 2;
      empty_ = (flags & 1 << Flags.IS_EMPTY.ordinal()) > 0;
      thetaLong_ = Long.MAX_VALUE;
      int count = 0;
      if (!empty_) {
        if (preambleLongs == 1) {
          count = 1;
        } else {
          count = mem.getInt(offset);
          offset += Integer.BYTES;
          offset += 4; // unused
          if (preambleLongs > 2) {
            thetaLong_ = mem.getLong(offset);
            offset += Long.BYTES;
          }
        }
      }
      hashArr_ = new long[count];
      for (int i = 0; i < count; i++) {
        hashArr_[i] = mem.getLong(offset);
        offset += Long.BYTES;
        offset += readSummary(mem, offset, i, count, deserializer);
      }
    }
  }

  @SuppressWarnings({"unchecked"})
  private int readSummary(final Memory mem, final int offset, final int i, final int count,
      final SummaryDeserializer<S> deserializer) {
    final Memory memRegion = mem.region(offset, mem.getCapacity() - offset);
    final DeserializeResult<S> result = deserializer.heapifySummary(memRegion);
    final S summary = result.getObject();
    final Class<S> summaryType = (Class<S>) result.getObject().getClass();
    if (summaryArr_ == null) {
      summaryArr_ = (S[]) Array.newInstance(summaryType, count);
    }
    summaryArr_[i] = summary;
    return result.getSize();
  }

  @Override
  public CompactSketch<S> compact() {
    return this;
  }

  long[] getHashArr() {
    return hashArr_;
  }

  S[] getSummaryArr() {
    return summaryArr_;
  }

  @Override
  public int getRetainedEntries() {
    return hashArr_ == null ? 0 : hashArr_.length;
  }

  @Override
  public int getCountLessThanThetaLong(final long thetaLong) {
    return count(hashArr_, thetaLong);
  }

  // Layout of first 8 bytes:
  // Long || Start Byte Adr:
  // Adr:
  //      ||    7   |    6   |    5   |    4   |    3   |    2   |    1   |     0              |
  //  0   ||    seed hash    |  Flags | unused | SkType | FamID  | SerVer |  Preamble_Longs    |
  @SuppressWarnings("null")
  @Override
  public byte[] toByteArray() {
  final int count = getRetainedEntries();
    final boolean isSingleItem = count == 1 && !isEstimationMode();
    final int preambleLongs = isEmpty() || isSingleItem ? 1 : isEstimationMode() ? 3 : 2;

    int summariesSizeBytes = 0;
    byte[][] summariesBytes = null;
    if (count > 0) {
      summariesBytes = new byte[count][];
      for (int i = 0; i < count; i++) {
        summariesBytes[i] = summaryArr_[i].toByteArray();
        summariesSizeBytes += summariesBytes[i].length;
      }
    }

    final int sizeBytes = Long.BYTES * preambleLongs + Long.BYTES * count + summariesSizeBytes;
    final byte[] bytes = new byte[sizeBytes];
    int offset = 0;
    bytes[offset++] = (byte) preambleLongs;
    bytes[offset++] = serialVersionUID;
    bytes[offset++] = (byte) Family.TUPLE.getID();
    bytes[offset++] = (byte) SerializerDeserializer.SketchType.CompactSketch.ordinal();
    offset++; // unused
    bytes[offset++] = (byte) (
        (1 << Flags.IS_COMPACT.ordinal())
      | (1 << Flags.IS_READ_ONLY.ordinal())
      | (isEmpty() ? 1 << Flags.IS_EMPTY.ordinal() : 0)
    );
    ByteArrayUtil.putShortLE(bytes, offset, defaultSeedHash);
    offset += Short.BYTES;
    if (!isEmpty()) {
      if (!isSingleItem) {
        ByteArrayUtil.putIntLE(bytes, offset, count);
        offset += Integer.BYTES;
        offset += 4; // unused
        if (isEstimationMode()) {
          ByteArrayUtil.putLongLE(bytes, offset, thetaLong_);
          offset += Long.BYTES;
        }
      }
    }
    for (int i = 0; i < count; i++) {
      ByteArrayUtil.putLongLE(bytes, offset, hashArr_[i]);
      offset += Long.BYTES;
      System.arraycopy(summariesBytes[i], 0, bytes, offset, summariesBytes[i].length);
      offset += summariesBytes[i].length;
    }
    return bytes;
  }

  @SuppressWarnings("unchecked")
  CompactSketch<S> trimToTheta(final long thetaLong) {
    final QuickSelectSketch<S> qsSk =
        new QuickSelectSketch<>(this.getRetainedEntries(), ResizeFactor.X1.lg(), null);
    int countOut = 0;
    final SketchIterator<S> it = iterator();

    while (it.next()) {
      final long hash = it.getHash();
      final S summary = it.getSummary();
      if (hash < thetaLong) {
        qsSk.insert(it.getHash(), (S)summary.copy());
        countOut++;
      }
    }

    qsSk.setThetaLong(thetaLong);
    if (countOut == 0) {
      if (thetaLong == Long.MAX_VALUE) {
        return new CompactSketch<>(null, null, thetaLong, true);
      } else {
        return new CompactSketch<>(null, null, thetaLong, false);
      }
    } else {
      return new CompactSketch<>(qsSk.getHashTable(), qsSk.summaryTable_, thetaLong, false);
    }
  }

  @Override
  public SketchIterator<S> iterator() {
    return new SketchIterator<>(hashArr_, summaryArr_);
  }

}

1	/*
2	* Licensed to the Apache Software Foundation (ASF) under one
3	* or more contributor license agreements. See the NOTICE file
4	* distributed with this work for additional information
5	* regarding copyright ownership. The ASF licenses this file
6	* to you under the Apache License, Version 2.0 (the
7	* "License"); you may not use this file except in compliance
8	* with the License. You may obtain a copy of the License at
9	*
10	* http://www.apache.org/licenses/LICENSE-2.0
11	*
12	* Unless required by applicable law or agreed to in writing,
13	* software distributed under the License is distributed on an
14	* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15	* KIND, either express or implied. See the License for the
16	* specific language governing permissions and limitations
17	* under the License.
18	*/
19
20	package org.apache.datasketches.tuple;
21
22	import static org.apache.datasketches.HashOperations.count;
23
24	import java.lang.reflect.Array;
25	import java.nio.ByteOrder;
26
27	import org.apache.datasketches.ByteArrayUtil;
28	import org.apache.datasketches.Family;
29	import org.apache.datasketches.ResizeFactor;
30	import org.apache.datasketches.SketchesArgumentException;
31	import org.apache.datasketches.memory.Memory;
32
33	/**
34	* CompactSketches are never created directly. They are created as a result of
35	* the compact() method of an UpdatableSketch or as a result of the getResult()
36	* method of a set operation like Union, Intersection or AnotB. CompactSketch
37	* consists of a compact list (i.e. no intervening spaces) of hash values,
38	* corresponding list of Summaries, and a value for theta. The lists may or may
39	* not be ordered. CompactSketch is read-only.
40	*
41	* @param <S> type of Summary
42	*/
43	public class CompactSketch<S extends Summary> extends Sketch<S> {
44	private static final byte serialVersionWithSummaryClassNameUID = 1;
45	private static final byte serialVersionUIDLegacy = 2;
46	private static final byte serialVersionUID = 3;
47	private static final short defaultSeedHash = (short) 37836; // for compatibility with C++
48	private long[] hashArr_;
49	private S[] summaryArr_;
50
51	private enum FlagsLegacy { IS_BIG_ENDIAN, IS_EMPTY, HAS_ENTRIES, IS_THETA_INCLUDED }	1✔
52
53	private enum Flags { IS_BIG_ENDIAN, IS_READ_ONLY, IS_EMPTY, IS_COMPACT, IS_ORDERED }	1✔
54
55	/**
56	* Create a CompactSketch from correct components
57	* @param hashArr compacted hash array
58	* @param summaryArr compacted summary array
59	* @param thetaLong long value of theta
60	* @param empty empty flag
61	*/
62	CompactSketch(final long[] hashArr, final S[] summaryArr, final long thetaLong, final boolean empty) {	1✔
63	hashArr_ = hashArr;	1✔
64	summaryArr_ = summaryArr;	1✔
65	thetaLong_ = thetaLong;	1✔
66	empty_ = empty;	1✔
67	}	1✔
68
69	/**
70	* This is to create an instance of a CompactSketch given a serialized form
71	*
72	* @param mem Memory object with serialized CompactSketch
73	* @param deserializer the SummaryDeserializer
74	*/
75	@SuppressWarnings({"unchecked"})
76	CompactSketch(final Memory mem, final SummaryDeserializer<S> deserializer) {	1✔
77	int offset = 0;	1✔
78	final byte preambleLongs = mem.getByte(offset++);	1✔
79	final byte version = mem.getByte(offset++);	1✔
80	final byte familyId = mem.getByte(offset++);	1✔
81	SerializerDeserializer.validateFamily(familyId, preambleLongs);	1✔
82	if (version > serialVersionUID) {	1✔
83	throw new SketchesArgumentException(	×
84	"Unsupported serial version. Expected: " + serialVersionUID + " or lower, actual: " + version);
85	}
86	SerializerDeserializer	1✔
87	.validateType(mem.getByte(offset++), SerializerDeserializer.SketchType.CompactSketch);	1✔
88	if (version <= serialVersionUIDLegacy) { // legacy serial format	1✔
89	final byte flags = mem.getByte(offset++);	1✔
90	final boolean isBigEndian = (flags & 1 << FlagsLegacy.IS_BIG_ENDIAN.ordinal()) > 0;	1✔
91	if (isBigEndian ^ ByteOrder.nativeOrder().equals(ByteOrder.BIG_ENDIAN)) {	1✔
92	throw new SketchesArgumentException("Byte order mismatch");	×
93	}
94	empty_ = (flags & 1 << FlagsLegacy.IS_EMPTY.ordinal()) > 0;	1✔
95	final boolean isThetaIncluded = (flags & 1 << FlagsLegacy.IS_THETA_INCLUDED.ordinal()) > 0;	1✔
96	if (isThetaIncluded) {	1✔
97	thetaLong_ = mem.getLong(offset);	1✔
98	offset += Long.BYTES;	1✔
99	} else {
100	thetaLong_ = Long.MAX_VALUE;	×
101	}
102	final boolean hasEntries = (flags & 1 << FlagsLegacy.HAS_ENTRIES.ordinal()) > 0;	1✔
103	if (hasEntries) {	1✔
104	int classNameLength = 0;	1✔
105	if (version == serialVersionWithSummaryClassNameUID) {	1✔
106	classNameLength = mem.getByte(offset++);	1✔
107	}
108	final int count = mem.getInt(offset);	1✔
109	offset += Integer.BYTES;	1✔
110	if (version == serialVersionWithSummaryClassNameUID) {	1✔
111	offset += classNameLength;	1✔
112	}
113	hashArr_ = new long[count];	1✔
114	for (int i = 0; i < count; i++) {	1✔
115	hashArr_[i] = mem.getLong(offset);	1✔
116	offset += Long.BYTES;	1✔
117	}
118	for (int i = 0; i < count; i++) {	1✔
119	offset += readSummary(mem, offset, i, count, deserializer);	1✔
120	}
121	}
122	} else { // current serial format	1✔
123	offset++;	1✔
124	final byte flags = mem.getByte(offset++);	1✔
125	offset += 2;	1✔
126	empty_ = (flags & 1 << Flags.IS_EMPTY.ordinal()) > 0;	1✔
127	thetaLong_ = Long.MAX_VALUE;	1✔
128	int count = 0;	1✔
129	if (!empty_) {	1✔
130	if (preambleLongs == 1) {	1✔
131	count = 1;	1✔
132	} else {
133	count = mem.getInt(offset);	1✔
134	offset += Integer.BYTES;	1✔
135	offset += 4; // unused	1✔
136	if (preambleLongs > 2) {	1✔
137	thetaLong_ = mem.getLong(offset);	1✔
138	offset += Long.BYTES;	1✔
139	}
140	}
141	}
142	hashArr_ = new long[count];	1✔
143	for (int i = 0; i < count; i++) {	1✔
144	hashArr_[i] = mem.getLong(offset);	1✔
145	offset += Long.BYTES;	1✔
146	offset += readSummary(mem, offset, i, count, deserializer);	1✔
147	}
148	}
149	}	1✔
150
151	@SuppressWarnings({"unchecked"})
152	private int readSummary(final Memory mem, final int offset, final int i, final int count,
153	final SummaryDeserializer<S> deserializer) {
154	final Memory memRegion = mem.region(offset, mem.getCapacity() - offset);	1✔
155	final DeserializeResult<S> result = deserializer.heapifySummary(memRegion);	1✔
156	final S summary = result.getObject();	1✔
157	final Class<S> summaryType = (Class<S>) result.getObject().getClass();	1✔
158	if (summaryArr_ == null) {	1✔
159	summaryArr_ = (S[]) Array.newInstance(summaryType, count);	1✔
160	}
161	summaryArr_[i] = summary;	1✔
162	return result.getSize();	1✔
163	}
164
165	@Override
166	public CompactSketch<S> compact() {
167	return this;	×
168	}
169
170	long[] getHashArr() {
171	return hashArr_;	1✔
172	}
173
174	S[] getSummaryArr() {
175	return summaryArr_;	1✔
176	}
177
178	@Override
179	public int getRetainedEntries() {
180	return hashArr_ == null ? 0 : hashArr_.length;	1✔
181	}
182
183	@Override
184	public int getCountLessThanThetaLong(final long thetaLong) {
185	return count(hashArr_, thetaLong);	×
186	}
187
188	// Layout of first 8 bytes:
189	// Long \|\| Start Byte Adr:
190	// Adr:
191	// \|\| 7 \| 6 \| 5 \| 4 \| 3 \| 2 \| 1 \| 0 \|
192	// 0 \|\| seed hash \| Flags \| unused \| SkType \| FamID \| SerVer \| Preamble_Longs \|
193	@SuppressWarnings("null")
194	@Override
195	public byte[] toByteArray() {
196	final int count = getRetainedEntries();	1✔
197	final boolean isSingleItem = count == 1 && !isEstimationMode();	1✔
198	final int preambleLongs = isEmpty() \|\| isSingleItem ? 1 : isEstimationMode() ? 3 : 2;	1✔
199
200	int summariesSizeBytes = 0;	1✔
201	byte[][] summariesBytes = null;	1✔
202	if (count > 0) {	1✔
203	summariesBytes = new byte[count][];	1✔
204	for (int i = 0; i < count; i++) {	1✔
205	summariesBytes[i] = summaryArr_[i].toByteArray();	1✔
206	summariesSizeBytes += summariesBytes[i].length;	1✔
207	}
208	}
209
210	final int sizeBytes = Long.BYTES * preambleLongs + Long.BYTES * count + summariesSizeBytes;	1✔
211	final byte[] bytes = new byte[sizeBytes];	1✔
212	int offset = 0;	1✔
213	bytes[offset++] = (byte) preambleLongs;	1✔
214	bytes[offset++] = serialVersionUID;	1✔
215	bytes[offset++] = (byte) Family.TUPLE.getID();	1✔
216	bytes[offset++] = (byte) SerializerDeserializer.SketchType.CompactSketch.ordinal();	1✔
217	offset++; // unused	1✔
218	bytes[offset++] = (byte) (	1✔
219	(1 << Flags.IS_COMPACT.ordinal())	1✔
220	\| (1 << Flags.IS_READ_ONLY.ordinal())	1✔
221	\| (isEmpty() ? 1 << Flags.IS_EMPTY.ordinal() : 0)	1✔
222	);
223	ByteArrayUtil.putShortLE(bytes, offset, defaultSeedHash);	1✔
224	offset += Short.BYTES;	1✔
225	if (!isEmpty()) {	1✔
226	if (!isSingleItem) {	1✔
227	ByteArrayUtil.putIntLE(bytes, offset, count);	1✔
228	offset += Integer.BYTES;	1✔
229	offset += 4; // unused	1✔
230	if (isEstimationMode()) {	1✔
231	ByteArrayUtil.putLongLE(bytes, offset, thetaLong_);	1✔
232	offset += Long.BYTES;	1✔
233	}
234	}
235	}
236	for (int i = 0; i < count; i++) {	1✔
237	ByteArrayUtil.putLongLE(bytes, offset, hashArr_[i]);	1✔
238	offset += Long.BYTES;	1✔
239	System.arraycopy(summariesBytes[i], 0, bytes, offset, summariesBytes[i].length);	1✔
240	offset += summariesBytes[i].length;	1✔
241	}
242	return bytes;	1✔
243	}
244
245	@SuppressWarnings("unchecked")
246	CompactSketch<S> trimToTheta(final long thetaLong) {
247	final QuickSelectSketch<S> qsSk =	×
248	new QuickSelectSketch<>(this.getRetainedEntries(), ResizeFactor.X1.lg(), null);	×
249	int countOut = 0;	×
250	final SketchIterator<S> it = iterator();	×
251
252	while (it.next()) {	×
253	final long hash = it.getHash();	×
254	final S summary = it.getSummary();	×
255	if (hash < thetaLong) {	×
256	qsSk.insert(it.getHash(), (S)summary.copy());	×
257	countOut++;	×
258	}
259	}	×
260
261	qsSk.setThetaLong(thetaLong);	×
262	if (countOut == 0) {	×
263	if (thetaLong == Long.MAX_VALUE) {	×
264	return new CompactSketch<>(null, null, thetaLong, true);	×
265	} else {
266	return new CompactSketch<>(null, null, thetaLong, false);	×
267	}
268	} else {
269	return new CompactSketch<>(qsSk.getHashTable(), qsSk.summaryTable_, thetaLong, false);	×
270	}
271	}
272
273	@Override
274	public SketchIterator<S> iterator() {
275	return new SketchIterator<>(hashArr_, summaryArr_);	1✔
276	}
277
278	}

apache / datasketches-java / #106

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous