#306

Committed 30 Apr 2024 10:01PM UTC coverage: 97.645% (-0.5%) from 98.139%

Build # #306

Build Type

push

Committed by

Commit Message

Merge pull request #555 from apache/fix_pom_xml_header

Fix pom xml header

Run Details

26865 of 27513 relevant lines covered (97.64%)

0.98 hits per line

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

98.91

/src/main/java/org/apache/datasketches/quantiles/HeapCompactDoublesSketch.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.quantiles;

import static org.apache.datasketches.quantiles.ClassicUtil.computeBaseBufferItems;
import static org.apache.datasketches.quantiles.ClassicUtil.computeBitPattern;
import static org.apache.datasketches.quantiles.ClassicUtil.computeRetainedItems;
import static org.apache.datasketches.quantiles.PreambleUtil.COMPACT_FLAG_MASK;
import static org.apache.datasketches.quantiles.PreambleUtil.EMPTY_FLAG_MASK;
import static org.apache.datasketches.quantiles.PreambleUtil.MAX_DOUBLE;
import static org.apache.datasketches.quantiles.PreambleUtil.MIN_DOUBLE;
import static org.apache.datasketches.quantiles.PreambleUtil.READ_ONLY_FLAG_MASK;
import static org.apache.datasketches.quantiles.PreambleUtil.extractFamilyID;
import static org.apache.datasketches.quantiles.PreambleUtil.extractFlags;
import static org.apache.datasketches.quantiles.PreambleUtil.extractK;
import static org.apache.datasketches.quantiles.PreambleUtil.extractN;
import static org.apache.datasketches.quantiles.PreambleUtil.extractPreLongs;
import static org.apache.datasketches.quantiles.PreambleUtil.extractSerVer;

import java.util.Arrays;

import org.apache.datasketches.common.SketchesArgumentException;
import org.apache.datasketches.memory.Memory;
import org.apache.datasketches.memory.WritableMemory;
import org.apache.datasketches.quantilescommon.QuantilesAPI;

/**
 * Implements the DoublesSketch on the Java heap.
 *
 * @author Lee Rhodes
 * @author Jon Malkin
 */
final class HeapCompactDoublesSketch extends CompactDoublesSketch {
  static final int MIN_HEAP_DOUBLES_SER_VER = 1;

  /**
   * The smallest item ever seen in the stream.
   */
  private double minItem_;

  /**
   * The largest item ever seen in the stream.
   */
  private double maxItem_;

  /**
   * The total count of items seen.
   */
  private long n_;

  /**
   * Number of items currently in base buffer.
   *
   * <p>Count = N % (2*K)
   */
  private int baseBufferCount_;

  /**
   * Active levels expressed as a bit pattern.
   *
   * <p>Pattern = N / (2 * K)
   */
  private long bitPattern_;

  /**
   * This single array contains the base buffer plus all used levels.
   * A level is of size K and is either full and sorted.
   * Whether a level buffer is present is indicated by the bitPattern_.
   * The base buffer is sorted and has max length 2*K but uses only baseBufferCount_ items.
   * The base buffer precedes the level buffers. This buffer does not include the min, max items.
   *
   * <p>The levels arrays require quite a bit of explanation, which we defer until later.</p>
   */
  private double[] combinedBuffer_;

  //**CONSTRUCTORS**********************************************************
  private HeapCompactDoublesSketch(final int k) {
    super(k); //Checks k
  }

  /**
   * Converts the given UpdateDoublesSketch to this compact form.
   *
   * @param sketch the sketch to convert
   * @return a HeapCompactDoublesSketch created from an UpdateDoublesSketch
   */
  static HeapCompactDoublesSketch createFromUpdateSketch(final UpdateDoublesSketch sketch) {
    final int k = sketch.getK();
    final long n = sketch.getN();

    final HeapCompactDoublesSketch hcds = new HeapCompactDoublesSketch(k); // checks k

    hcds.n_ = n;
    hcds.bitPattern_ = computeBitPattern(k, n);
    assert hcds.bitPattern_ == sketch.getBitPattern();

    hcds.minItem_ = sketch.isEmpty() ? Double.NaN : sketch.getMinItem();
    hcds.maxItem_ = sketch.isEmpty() ? Double.NaN : sketch.getMaxItem();
    hcds.baseBufferCount_ = computeBaseBufferItems(k, n);
    assert hcds.baseBufferCount_ == sketch.getBaseBufferCount();

    //if (sketch.isEmpty()) {
    //  hcds.combinedBuffer_ = null;
    //  return hcds;
    //}

    final int retainedItems = computeRetainedItems(k, n);
    final double[] combinedBuffer = new double[retainedItems];

    final DoublesSketchAccessor accessor = DoublesSketchAccessor.wrap(sketch);
    assert hcds.baseBufferCount_ == accessor.numItems();

    // copy and sort base buffer
    System.arraycopy(accessor.getArray(0, hcds.baseBufferCount_), 0,
            combinedBuffer, 0,
            hcds.baseBufferCount_);
    Arrays.sort(combinedBuffer, 0, hcds.baseBufferCount_);

    int combinedBufferOffset = hcds.baseBufferCount_;
    long bitPattern = hcds.bitPattern_;
    for (int lvl = 0; bitPattern > 0; ++lvl, bitPattern >>>= 1) {
      if ((bitPattern & 1L) > 0L) {
        accessor.setLevel(lvl);
        System.arraycopy(accessor.getArray(0, k), 0,
                combinedBuffer, combinedBufferOffset, k);
        combinedBufferOffset += k;
      }
    }
    hcds.combinedBuffer_ = combinedBuffer;

    return hcds;
  }

  /**
   * Heapifies the given srcMem, which must be a Memory image of a DoublesSketch and may have data.
   *
   * @param srcMem a Memory image of a sketch, which may be in compact or not compact form.
   * <a href="{@docRoot}/resources/dictionary.html#mem">See Memory</a>
   * @return a DoublesSketch on the Java heap.
   */
  static HeapCompactDoublesSketch heapifyInstance(final Memory srcMem) {
    final long memCapBytes = srcMem.getCapacity();
    if (memCapBytes < Long.BYTES) {
      throw new SketchesArgumentException("Source Memory too small: " + memCapBytes + " < 8");
    }

    final int preLongs = extractPreLongs(srcMem);
    final int serVer = extractSerVer(srcMem);
    final int familyID = extractFamilyID(srcMem);
    final int flags = extractFlags(srcMem);
    final int k = extractK(srcMem);

    final boolean empty = (flags & EMPTY_FLAG_MASK) > 0; //Preamble flags empty state
    final long n = empty ? 0 : extractN(srcMem);

    //VALIDITY CHECKS
    DoublesUtil.checkDoublesSerVer(serVer, MIN_HEAP_DOUBLES_SER_VER);
    ClassicUtil.checkHeapFlags(flags);
    HeapUpdateDoublesSketch.checkPreLongsFlagsSerVer(flags, serVer, preLongs);
    ClassicUtil.checkFamilyID(familyID);

    final HeapCompactDoublesSketch hds = new HeapCompactDoublesSketch(k); //checks k
    if (empty) {
      hds.n_ = 0;
      hds.combinedBuffer_ = null;
      hds.baseBufferCount_ = 0;
      hds.bitPattern_ = 0;
      hds.minItem_ = Double.NaN;
      hds.maxItem_ = Double.NaN;
      return hds;
    }

    //Not empty, must have valid preamble + min, max, n.
    //Forward compatibility from SerVer = 1 :
    final boolean srcIsCompact = (serVer == 2) | ((flags & (COMPACT_FLAG_MASK | READ_ONLY_FLAG_MASK)) > 0);

    HeapUpdateDoublesSketch.checkHeapMemCapacity(k, n, srcIsCompact, serVer, memCapBytes);

    //set class members by computing them
    hds.n_ = n;
    hds.baseBufferCount_ = computeBaseBufferItems(k, n);
    hds.bitPattern_ = computeBitPattern(k, n);
    hds.minItem_ = srcMem.getDouble(MIN_DOUBLE);
    hds.maxItem_ = srcMem.getDouble(MAX_DOUBLE);

    final int totItems = ClassicUtil.computeRetainedItems(k, n);
    hds.srcMemoryToCombinedBuffer(srcMem, serVer, srcIsCompact, totItems);

    return hds;
  }

  @Override
  public long getN() {
    return n_;
  }

  @Override
  public boolean hasMemory() {
    return false;
  }

  @Override
  public boolean isDirect() {
    return false;
  }

  @Override
  public double getMinItem() {
    if (isEmpty()) { throw new IllegalArgumentException(QuantilesAPI.EMPTY_MSG); }
    return minItem_;
  }

  @Override
  public double getMaxItem() {
    if (isEmpty()) { throw new IllegalArgumentException(QuantilesAPI.EMPTY_MSG); }
    return maxItem_;
  }

  /**
   * Loads the Combined Buffer from the given source Memory.
   * The resulting Combined Buffer is allocated in this method and is always in compact form.
   * @param srcMem the given source Memory
   * @param serVer the serialization version of the source
   * @param srcIsCompact true if the given source Memory is in compact form
   * @param combBufCap total items for the combined buffer (size in doubles)
   */
  private void srcMemoryToCombinedBuffer(final Memory srcMem, final int serVer,
                                         final boolean srcIsCompact, final int combBufCap) {
    final int preLongs = 2;
    final int extra = (serVer == 1) ? 3 : 2; // space for min and max quantiles, buf alloc (SerVer 1)
    final int preBytes = (preLongs + extra) << 3;

    final int k = getK();
    combinedBuffer_ = new double[combBufCap];

    if (srcIsCompact) {
      // just load the array, sort base buffer if serVer 2
      srcMem.getDoubleArray(preBytes, combinedBuffer_, 0, combBufCap);
      if (serVer == 2) {
        Arrays.sort(combinedBuffer_, 0, baseBufferCount_);
      }
    } else {
      // non-compact source
      // load base buffer and ensure it's sorted
      srcMem.getDoubleArray(preBytes, combinedBuffer_, 0, baseBufferCount_);
      Arrays.sort(combinedBuffer_, 0, baseBufferCount_);

      // iterate through levels
      int srcOffset = preBytes + ((2 * k) << 3);
      int dstOffset = baseBufferCount_;
      long bitPattern = bitPattern_;
      for (; bitPattern != 0; srcOffset += (k << 3), bitPattern >>>= 1) {
        if ((bitPattern & 1L) > 0L) {
          srcMem.getDoubleArray(srcOffset, combinedBuffer_, dstOffset, k);
          dstOffset += k;
        }
      }
    }
  }

  //Restricted overrides
  //Gets

  @Override
  int getBaseBufferCount() {
    return baseBufferCount_;
  }

  @Override
  int getCombinedBufferItemCapacity() {
    return combinedBuffer_.length;
  }

  @Override
  double[] getCombinedBuffer() {
    return combinedBuffer_;
  }

  @Override
  long getBitPattern() {
    return bitPattern_;
  }

  @Override
  WritableMemory getMemory() {
    return null;
  }
}

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.quantiles;
21
22	import static org.apache.datasketches.quantiles.ClassicUtil.computeBaseBufferItems;
23	import static org.apache.datasketches.quantiles.ClassicUtil.computeBitPattern;
24	import static org.apache.datasketches.quantiles.ClassicUtil.computeRetainedItems;
25	import static org.apache.datasketches.quantiles.PreambleUtil.COMPACT_FLAG_MASK;
26	import static org.apache.datasketches.quantiles.PreambleUtil.EMPTY_FLAG_MASK;
27	import static org.apache.datasketches.quantiles.PreambleUtil.MAX_DOUBLE;
28	import static org.apache.datasketches.quantiles.PreambleUtil.MIN_DOUBLE;
29	import static org.apache.datasketches.quantiles.PreambleUtil.READ_ONLY_FLAG_MASK;
30	import static org.apache.datasketches.quantiles.PreambleUtil.extractFamilyID;
31	import static org.apache.datasketches.quantiles.PreambleUtil.extractFlags;
32	import static org.apache.datasketches.quantiles.PreambleUtil.extractK;
33	import static org.apache.datasketches.quantiles.PreambleUtil.extractN;
34	import static org.apache.datasketches.quantiles.PreambleUtil.extractPreLongs;
35	import static org.apache.datasketches.quantiles.PreambleUtil.extractSerVer;
36
37	import java.util.Arrays;
38
39	import org.apache.datasketches.common.SketchesArgumentException;
40	import org.apache.datasketches.memory.Memory;
41	import org.apache.datasketches.memory.WritableMemory;
42	import org.apache.datasketches.quantilescommon.QuantilesAPI;
43
44	/**
45	* Implements the DoublesSketch on the Java heap.
46	*
47	* @author Lee Rhodes
48	* @author Jon Malkin
49	*/
50	final class HeapCompactDoublesSketch extends CompactDoublesSketch {	1✔
51	static final int MIN_HEAP_DOUBLES_SER_VER = 1;
52
53	/**
54	* The smallest item ever seen in the stream.
55	*/
56	private double minItem_;
57
58	/**
59	* The largest item ever seen in the stream.
60	*/
61	private double maxItem_;
62
63	/**
64	* The total count of items seen.
65	*/
66	private long n_;
67
68	/**
69	* Number of items currently in base buffer.
70	*
71	* <p>Count = N % (2*K)
72	*/
73	private int baseBufferCount_;
74
75	/**
76	* Active levels expressed as a bit pattern.
77	*
78	* <p>Pattern = N / (2 * K)
79	*/
80	private long bitPattern_;
81
82	/**
83	* This single array contains the base buffer plus all used levels.
84	* A level is of size K and is either full and sorted.
85	* Whether a level buffer is present is indicated by the bitPattern_.
86	* The base buffer is sorted and has max length 2*K but uses only baseBufferCount_ items.
87	* The base buffer precedes the level buffers. This buffer does not include the min, max items.
88	*
89	* <p>The levels arrays require quite a bit of explanation, which we defer until later.</p>
90	*/
91	private double[] combinedBuffer_;
92
93	//CONSTRUCTORS********************************************************
94	private HeapCompactDoublesSketch(final int k) {
95	super(k); //Checks k	1✔
96	}	1✔
97
98	/**
99	* Converts the given UpdateDoublesSketch to this compact form.
100	*
101	* @param sketch the sketch to convert
102	* @return a HeapCompactDoublesSketch created from an UpdateDoublesSketch
103	*/
104	static HeapCompactDoublesSketch createFromUpdateSketch(final UpdateDoublesSketch sketch) {
105	final int k = sketch.getK();	1✔
106	final long n = sketch.getN();	1✔
107
108	final HeapCompactDoublesSketch hcds = new HeapCompactDoublesSketch(k); // checks k	1✔
109
110	hcds.n_ = n;	1✔
111	hcds.bitPattern_ = computeBitPattern(k, n);	1✔
112	assert hcds.bitPattern_ == sketch.getBitPattern();	1✔
113
114	hcds.minItem_ = sketch.isEmpty() ? Double.NaN : sketch.getMinItem();	1✔
115	hcds.maxItem_ = sketch.isEmpty() ? Double.NaN : sketch.getMaxItem();	1✔
116	hcds.baseBufferCount_ = computeBaseBufferItems(k, n);	1✔
117	assert hcds.baseBufferCount_ == sketch.getBaseBufferCount();	1✔
118
119	//if (sketch.isEmpty()) {
120	// hcds.combinedBuffer_ = null;
121	// return hcds;
122	//}
123
124	final int retainedItems = computeRetainedItems(k, n);	1✔
125	final double[] combinedBuffer = new double[retainedItems];	1✔
126
127	final DoublesSketchAccessor accessor = DoublesSketchAccessor.wrap(sketch);	1✔
128	assert hcds.baseBufferCount_ == accessor.numItems();	1✔
129
130	// copy and sort base buffer
131	System.arraycopy(accessor.getArray(0, hcds.baseBufferCount_), 0,	1✔
132	combinedBuffer, 0,
133	hcds.baseBufferCount_);
134	Arrays.sort(combinedBuffer, 0, hcds.baseBufferCount_);	1✔
135
136	int combinedBufferOffset = hcds.baseBufferCount_;	1✔
137	long bitPattern = hcds.bitPattern_;	1✔
138	for (int lvl = 0; bitPattern > 0; ++lvl, bitPattern >>>= 1) {	1✔
139	if ((bitPattern & 1L) > 0L) {	1✔
140	accessor.setLevel(lvl);	1✔
141	System.arraycopy(accessor.getArray(0, k), 0,	1✔
142	combinedBuffer, combinedBufferOffset, k);
143	combinedBufferOffset += k;	1✔
144	}
145	}
146	hcds.combinedBuffer_ = combinedBuffer;	1✔
147
148	return hcds;	1✔
149	}
150
151	/**
152	* Heapifies the given srcMem, which must be a Memory image of a DoublesSketch and may have data.
153	*
154	* @param srcMem a Memory image of a sketch, which may be in compact or not compact form.
155	* <a href="{@docRoot}/resources/dictionary.html#mem">See Memory</a>
156	* @return a DoublesSketch on the Java heap.
157	*/
158	static HeapCompactDoublesSketch heapifyInstance(final Memory srcMem) {
159	final long memCapBytes = srcMem.getCapacity();	1✔
160	if (memCapBytes < Long.BYTES) {	1✔
161	throw new SketchesArgumentException("Source Memory too small: " + memCapBytes + " < 8");	1✔
162	}
163
164	final int preLongs = extractPreLongs(srcMem);	1✔
165	final int serVer = extractSerVer(srcMem);	1✔
166	final int familyID = extractFamilyID(srcMem);	1✔
167	final int flags = extractFlags(srcMem);	1✔
168	final int k = extractK(srcMem);	1✔
169
170	final boolean empty = (flags & EMPTY_FLAG_MASK) > 0; //Preamble flags empty state	1✔
171	final long n = empty ? 0 : extractN(srcMem);	1✔
172
173	//VALIDITY CHECKS
174	DoublesUtil.checkDoublesSerVer(serVer, MIN_HEAP_DOUBLES_SER_VER);	1✔
175	ClassicUtil.checkHeapFlags(flags);	1✔
176	HeapUpdateDoublesSketch.checkPreLongsFlagsSerVer(flags, serVer, preLongs);	1✔
177	ClassicUtil.checkFamilyID(familyID);	1✔
178
179	final HeapCompactDoublesSketch hds = new HeapCompactDoublesSketch(k); //checks k	1✔
180	if (empty) {	1✔
181	hds.n_ = 0;	1✔
182	hds.combinedBuffer_ = null;	1✔
183	hds.baseBufferCount_ = 0;	1✔
184	hds.bitPattern_ = 0;	1✔
185	hds.minItem_ = Double.NaN;	1✔
186	hds.maxItem_ = Double.NaN;	1✔
187	return hds;	1✔
188	}
189
190	//Not empty, must have valid preamble + min, max, n.
191	//Forward compatibility from SerVer = 1 :
192	final boolean srcIsCompact = (serVer == 2) \| ((flags & (COMPACT_FLAG_MASK \| READ_ONLY_FLAG_MASK)) > 0);	1✔
193
194	HeapUpdateDoublesSketch.checkHeapMemCapacity(k, n, srcIsCompact, serVer, memCapBytes);	1✔
195
196	//set class members by computing them
197	hds.n_ = n;	1✔
198	hds.baseBufferCount_ = computeBaseBufferItems(k, n);	1✔
199	hds.bitPattern_ = computeBitPattern(k, n);	1✔
200	hds.minItem_ = srcMem.getDouble(MIN_DOUBLE);	1✔
201	hds.maxItem_ = srcMem.getDouble(MAX_DOUBLE);	1✔
202
203	final int totItems = ClassicUtil.computeRetainedItems(k, n);	1✔
204	hds.srcMemoryToCombinedBuffer(srcMem, serVer, srcIsCompact, totItems);	1✔
205
206	return hds;	1✔
207	}
208
209	@Override
210	public long getN() {
211	return n_;	1✔
212	}
213
214	@Override
215	public boolean hasMemory() {
216	return false;	1✔
217	}
218
219	@Override
220	public boolean isDirect() {
221	return false;	×
222	}
223
224	@Override
225	public double getMinItem() {
226	if (isEmpty()) { throw new IllegalArgumentException(QuantilesAPI.EMPTY_MSG); }	1✔
227	return minItem_;	1✔
228	}
229
230	@Override
231	public double getMaxItem() {
232	if (isEmpty()) { throw new IllegalArgumentException(QuantilesAPI.EMPTY_MSG); }	1✔
233	return maxItem_;	1✔
234	}
235
236	/**
237	* Loads the Combined Buffer from the given source Memory.
238	* The resulting Combined Buffer is allocated in this method and is always in compact form.
239	* @param srcMem the given source Memory
240	* @param serVer the serialization version of the source
241	* @param srcIsCompact true if the given source Memory is in compact form
242	* @param combBufCap total items for the combined buffer (size in doubles)
243	*/
244	private void srcMemoryToCombinedBuffer(final Memory srcMem, final int serVer,
245	final boolean srcIsCompact, final int combBufCap) {
246	final int preLongs = 2;	1✔
247	final int extra = (serVer == 1) ? 3 : 2; // space for min and max quantiles, buf alloc (SerVer 1)	1✔
248	final int preBytes = (preLongs + extra) << 3;	1✔
249
250	final int k = getK();	1✔
251	combinedBuffer_ = new double[combBufCap];	1✔
252
253	if (srcIsCompact) {	1✔
254	// just load the array, sort base buffer if serVer 2
255	srcMem.getDoubleArray(preBytes, combinedBuffer_, 0, combBufCap);	1✔
256	if (serVer == 2) {	1✔
257	Arrays.sort(combinedBuffer_, 0, baseBufferCount_);	1✔
258	}
259	} else {
260	// non-compact source
261	// load base buffer and ensure it's sorted
262	srcMem.getDoubleArray(preBytes, combinedBuffer_, 0, baseBufferCount_);	1✔
263	Arrays.sort(combinedBuffer_, 0, baseBufferCount_);	1✔
264
265	// iterate through levels
266	int srcOffset = preBytes + ((2 * k) << 3);	1✔
267	int dstOffset = baseBufferCount_;	1✔
268	long bitPattern = bitPattern_;	1✔
269	for (; bitPattern != 0; srcOffset += (k << 3), bitPattern >>>= 1) {	1✔
270	if ((bitPattern & 1L) > 0L) {	1✔
271	srcMem.getDoubleArray(srcOffset, combinedBuffer_, dstOffset, k);	1✔
272	dstOffset += k;	1✔
273	}
274	}
275	}
276	}	1✔
277
278	//Restricted overrides
279	//Gets
280
281	@Override
282	int getBaseBufferCount() {
283	return baseBufferCount_;	1✔
284	}
285
286	@Override
287	int getCombinedBufferItemCapacity() {
288	return combinedBuffer_.length;	1✔
289	}
290
291	@Override
292	double[] getCombinedBuffer() {
293	return combinedBuffer_;	1✔
294	}
295
296	@Override
297	long getBitPattern() {
298	return bitPattern_;	1✔
299	}
300
301	@Override
302	WritableMemory getMemory() {
303	return null;	1✔
304	}
305	}

apache / datasketches-java / #306

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