github-advanced-security[bot] commented on code in PR #579: URL: https://github.com/apache/datasketches-java/pull/579#discussion_r1712285665
########## src/main/java/org/apache/datasketches/filters/quotientfilter/QuotientFilter.java: ########## @@ -0,0 +1,569 @@ +/* + * 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.filters.quotientfilter; + +import static org.apache.datasketches.common.Util.LS; + +import java.util.HashSet; +import java.util.LinkedList; +import java.util.Queue; +import java.util.Set; + +import org.apache.datasketches.common.SketchesArgumentException; +import org.apache.datasketches.common.SketchesException; +import org.apache.datasketches.filters.common.BitArray; +import org.apache.datasketches.filters.common.HeapBitArray; + +public class QuotientFilter extends Filter { + + public static final float DEFAULT_LOAD_FACTOR = 0.8f; + + int lgQ_; + int numFingerprintBits_; + float loadFactor_; + int numEntries_; + int numExpansions_; + BitArray bitArray_; + + public QuotientFilter(final int lgQ, final int numFingerprintBits) { + this(lgQ, numFingerprintBits, DEFAULT_LOAD_FACTOR); + } + + public QuotientFilter(final int lgQ, final int numFingerprintBits, final float loadFactor) { + lgQ_ = lgQ; + numFingerprintBits_ = numFingerprintBits; + loadFactor_ = loadFactor; + bitArray_ = makeFilter(getNumSlots(), getNumBitsPerEntry()); + numExpansions_ = 0; + } + + public boolean rejuvenate(final long key) { + return false; + } + + public long getNumEntries() { + return numEntries_; + } + + public int getNumExpansions() { + return numExpansions_; + } + + public long getMaxEntriesBeforeExpansion() { + return (long)(getNumSlots() * loadFactor_); + } + + BitArray makeFilter(final long initSize, final int bitsPerEntry) { + return new HeapBitArray(initSize * bitsPerEntry); + } + + public int getFingerprintLength() { + return numFingerprintBits_; + } + + void expand() { + if (getFingerprintLength() < 2) { + throw new SketchesException("for expansion value must have at least 2 bits"); + } + final QuotientFilter other = new QuotientFilter(lgQ_ + 1, numFingerprintBits_ - 1, loadFactor_); + + long i = 0; + if (!isSlotEmpty(i)) { i = findClusterStart(i); } + + final Queue<Long> fifo = new LinkedList<Long>(); + long count = 0; + while (count < numEntries_) { + if (!isSlotEmpty(i)) { + if (isOccupied(i)) { fifo.add(i); } + final long fingerprint = getFingerprint(i); + final long newQuotient = (fifo.element() << 1) | (fingerprint >> other.getFingerprintLength()); + final long newFingerprint = fingerprint & other.getFingerprintMask(); + other.insert(newFingerprint, newQuotient); + count++; + } + i = (i + 1) & getSlotMask(); + if (!fifo.isEmpty() && ! isContinuation(i)) { fifo.remove(); } + } + lgQ_++; + numFingerprintBits_--; + bitArray_ = other.bitArray_; + numExpansions_++; + } + + public int getLgQ() { + return lgQ_; + } + + public float getLoadFactor() { + return loadFactor_; + } + + // returns the number of slots in the filter without the extension/buffer slots + public long getNumSlots() { + return 1L << lgQ_; + } + + long getSlotMask() { + return getNumSlots() - 1; + } + + long getFingerprintMask() { + return (1L << getFingerprintLength()) - 1; + } + + // sets the metadata flag bits for a given slot index + void modifySlot(final boolean isOccupied, final boolean isContinuation, final boolean isShifted, final long index) { + setOccupied(index, isOccupied); + setContinuation(index, isContinuation); + setShifted(index, isShifted); + } + + // sets the fingerprint for a given slot index + void setFingerprint(final long index, final long fingerprint) { + bitArray_.setBits(index * getNumBitsPerEntry() + 3, getFingerprintLength(), fingerprint); + } + + // print a nice representation of the filter that can be understood. + // if vertical is on, each line will represent a slot + public String getPrettyStr(final boolean vertical) { + final StringBuffer sbr = new StringBuffer(); + final long numBits = getNumSlots() * getNumBitsPerEntry(); + for (long i = 0; i < numBits; i++) { + final long remainder = i % getNumBitsPerEntry(); + if (remainder == 0) { + final long slot = i / getNumBitsPerEntry(); + sbr.append(" "); + if (vertical) { + sbr.append("\n" + String.format("%-10d", slot) + "\t"); + } + } + if (remainder == 3) { + sbr.append(" "); + } + sbr.append(bitArray_.getBit(i) ? "1" : "0"); + } + sbr.append("\n"); + return sbr.toString(); + } + + // print a representation of the filter that can be humanly read. + public void prettyPrint() { + System.out.print(getPrettyStr(true)); + } + + // return a fingerprint in a given slot index + long getFingerprint(final long index) { + return bitArray_.getBits(index * getNumBitsPerEntry() + 3, getFingerprintLength()); + } + + // return an entire slot representation, including metadata flags and fingerprint + long getSlot(final long index) { + return bitArray_.getBits(index * getNumBitsPerEntry(), getNumBitsPerEntry()); + } + + // compare a fingerprint input to the fingerprint in some slot index + protected boolean compare(final long index, final long fingerprint) { + return getFingerprint(index) == fingerprint; + } + + // modify the flags and fingerprint of a given slot + void modifySlot(final boolean isOccupied, final boolean isContinuation, final boolean isShifted, + final long index, final long fingerprint) { + modifySlot(isOccupied, isContinuation, isShifted, index); + setFingerprint(index, fingerprint); + } + + public String toString() { Review Comment: ## Missing Override annotation This method overrides [Object.toString](1); it is advisable to add an Override annotation. [Show more details](https://github.com/apache/datasketches-java/security/code-scanning/736) -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
