dungba88 commented on code in PR #12738:
URL: https://github.com/apache/lucene/pull/12738#discussion_r1378704913
##########
lucene/core/src/java/org/apache/lucene/util/fst/NodeHash.java:
##########
@@ -186,119 +197,85 @@ private long hash(FSTCompiler.UnCompiledNode<T> node) {
return h;
}
- // hash code for a frozen node. this must precisely match the hash
computation of an unfrozen
- // node!
- private long hash(long node) throws IOException {
- final int PRIME = 31;
-
- long h = 0;
- fstCompiler.fst.readFirstRealTargetArc(node, scratchArc, in);
- while (true) {
- h = PRIME * h + scratchArc.label();
- h = PRIME * h + (int) (scratchArc.target() ^ (scratchArc.target() >>
32));
- h = PRIME * h + scratchArc.output().hashCode();
- h = PRIME * h + scratchArc.nextFinalOutput().hashCode();
- if (scratchArc.isFinal()) {
- h += 17;
- }
- if (scratchArc.isLast()) {
- break;
- }
- fstCompiler.fst.readNextRealArc(scratchArc, in);
- }
-
- return h;
- }
-
- /**
- * Compares an unfrozen node (UnCompiledNode) with a frozen node at byte
location address (long),
- * returning true if they are equal.
- */
- private boolean nodesEqual(FSTCompiler.UnCompiledNode<T> node, long address)
throws IOException {
- fstCompiler.fst.readFirstRealTargetArc(address, scratchArc, in);
-
- // fail fast for a node with fixed length arcs
- if (scratchArc.bytesPerArc() != 0) {
- assert node.numArcs > 0;
- // the frozen node uses fixed-with arc encoding (same number of bytes
per arc), but may be
- // sparse or dense
- switch (scratchArc.nodeFlags()) {
- case FST.ARCS_FOR_BINARY_SEARCH:
- // sparse
- if (node.numArcs != scratchArc.numArcs()) {
- return false;
- }
- break;
- case FST.ARCS_FOR_DIRECT_ADDRESSING:
- // dense -- compare both the number of labels allocated in the array
(some of which may
- // not actually be arcs), and the number of arcs
- if ((node.arcs[node.numArcs - 1].label - node.arcs[0].label + 1) !=
scratchArc.numArcs()
- || node.numArcs != FST.Arc.BitTable.countBits(scratchArc, in)) {
- return false;
- }
- break;
- default:
- throw new AssertionError("unhandled scratchArc.nodeFlag() " +
scratchArc.nodeFlags());
- }
- }
-
- // compare arc by arc to see if there is a difference
- for (int arcUpto = 0; arcUpto < node.numArcs; arcUpto++) {
- final FSTCompiler.Arc<T> arc = node.arcs[arcUpto];
- if (arc.label != scratchArc.label()
- || arc.output.equals(scratchArc.output()) == false
- || ((FSTCompiler.CompiledNode) arc.target).node !=
scratchArc.target()
- || arc.nextFinalOutput.equals(scratchArc.nextFinalOutput()) == false
- || arc.isFinal != scratchArc.isFinal()) {
- return false;
- }
-
- if (scratchArc.isLast()) {
- if (arcUpto == node.numArcs - 1) {
- return true;
- } else {
- return false;
- }
- }
-
- fstCompiler.fst.readNextRealArc(scratchArc, in);
- }
-
- // unfrozen node has fewer arcs than frozen node
-
- return false;
- }
-
/** Inner class because it needs access to hash function and FST bytes. */
private class PagedGrowableHash {
+ public long copiedBytes;
private PagedGrowableWriter entries;
+ // mapping from FST real address to copiedNodes offsets
+ private PagedGrowableWriter copiedOffsets;
private long count;
+ // mask for entries
private long mask;
+ // mask for copiedOffsets
+ private long offsetMask;
+ private final List<byte[]> copiedNodes;
// 256K blocks, but note that the final block is sized only as needed so
it won't use the full
// block size when just a few elements were written to it
private static final int BLOCK_SIZE_BYTES = 1 << 18;
public PagedGrowableHash() {
entries = new PagedGrowableWriter(16, BLOCK_SIZE_BYTES, 8,
PackedInts.COMPACT);
+ copiedOffsets = new PagedGrowableWriter(32, BLOCK_SIZE_BYTES, 8,
PackedInts.COMPACT);
mask = 15;
+ offsetMask = 31;
+ copiedNodes = new ArrayList<>();
}
public PagedGrowableHash(long lastNodeAddress, long size) {
entries =
new PagedGrowableWriter(
size, BLOCK_SIZE_BYTES,
PackedInts.bitsRequired(lastNodeAddress), PackedInts.COMPACT);
+ copiedOffsets =
+ new PagedGrowableWriter(
+ size * 2,
+ BLOCK_SIZE_BYTES,
+ PackedInts.bitsRequired(lastNodeAddress),
+ PackedInts.COMPACT);
mask = size - 1;
+ offsetMask = size * 2 - 1;
assert (mask & size) == 0 : "size must be a power-of-2; got size=" +
size + " mask=" + mask;
+ copiedNodes = new ArrayList<>();
+ }
+
+ public byte[] getBytes(long node) {
+ long pos = offsetHash(node) & offsetMask;
+ while (true) {
+ long value = copiedOffsets.get(pos);
+ assert value != 0;
+ if (value == node) {
+ return copiedNodes.get(Math.toIntExact(copiedOffsets.get(pos + 1)));
+ }
+ pos = (pos + 2) & offsetMask;
+ }
}
public long get(long index) {
return entries.get(index);
}
- public void set(long index, long pointer) throws IOException {
+ public void set(long index, long pointer, byte[] bytes) {
entries.set(index, pointer);
+ copiedNodes.add(bytes);
+ setOffset(pointer);
count++;
+ copiedBytes += bytes.length;
+ }
+
+ private void setOffset(long pointer) {
+ long pos = offsetHash(pointer) & offsetMask;
+ // find an empty slot
+ while (copiedOffsets.get(pos) != 0) {
+ pos = (pos + 2) & offsetMask;
+ }
+ copiedOffsets.set(pos, pointer); // write the address
+ copiedOffsets.set(pos + 1, copiedNodes.size() - 1); // write the offsets
Review Comment:
I see, will break down into 2 different `PagedGrowableWriter`
--
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: issues-unsubscr...@lucene.apache.org
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org
For additional commands, e-mail: issues-h...@lucene.apache.org
