--- /dev/null
+package org.apache.lucene.util.fst;
+
+/**
+ * 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.
+ */
+
+import java.io.IOException;
+
+// Used to dedup states (lookup already-frozen states)
+final class NodeHash<T> {
+
+ private int[] table;
+ private int count;
+ private int mask;
+ private final FST<T> fst;
+ private final FST.Arc<T> scratchArc = new FST.Arc<T>();
+
+ public NodeHash(FST<T> fst) {
+ table = new int[16];
+ mask = 15;
+ this.fst = fst;
+ }
+
+ private boolean nodesEqual(Builder.UnCompiledNode<T> node, int address) throws IOException {
+ final FST<T>.BytesReader in = fst.getBytesReader(0);
+ fst.readFirstRealArc(address, scratchArc);
+ if (scratchArc.bytesPerArc != 0 && node.numArcs != scratchArc.numArcs) {
+ return false;
+ }
+ for(int arcUpto=0;arcUpto<node.numArcs;arcUpto++) {
+ final Builder.Arc<T> arc = node.arcs[arcUpto];
+ if (arc.label != scratchArc.label ||
+ !arc.output.equals(scratchArc.output) ||
+ ((Builder.CompiledNode) arc.target).address != scratchArc.target ||
+ !arc.nextFinalOutput.equals(scratchArc.nextFinalOutput) ||
+ arc.isFinal != scratchArc.isFinal()) {
+ return false;
+ }
+
+ if (scratchArc.isLast()) {
+ if (arcUpto == node.numArcs-1) {
+ return true;
+ } else {
+ return false;
+ }
+ }
+ fst.readNextRealArc(scratchArc, in);
+ }
+
+ return false;
+ }
+
+ // hash code for an unfrozen node. This must be identical
+ // to the un-frozen case (below)!!
+ private int hash(Builder.UnCompiledNode<T> node) {
+ final int PRIME = 31;
+ //System.out.println("hash unfrozen");
+ int h = 0;
+ // TODO: maybe if number of arcs is high we can safely subsample?
+ for(int arcIdx=0;arcIdx<node.numArcs;arcIdx++) {
+ final Builder.Arc<T> arc = node.arcs[arcIdx];
+ //System.out.println(" label=" + arc.label + " target=" + ((Builder.CompiledNode) arc.target).address + " h=" + h + " output=" + fst.outputs.outputToString(arc.output) + " isFinal?=" + arc.isFinal);
+ h = PRIME * h + arc.label;
+ h = PRIME * h + ((Builder.CompiledNode) arc.target).address;
+ h = PRIME * h + arc.output.hashCode();
+ h = PRIME * h + arc.nextFinalOutput.hashCode();
+ if (arc.isFinal) {
+ h += 17;
+ }
+ }
+ //System.out.println(" ret " + (h&Integer.MAX_VALUE));
+ return h & Integer.MAX_VALUE;
+ }
+
+ // hash code for a frozen node
+ private int hash(int node) throws IOException {
+ final int PRIME = 31;
+ final FST<T>.BytesReader in = fst.getBytesReader(0);
+ //System.out.println("hash frozen");
+ int h = 0;
+ fst.readFirstRealArc(node, scratchArc);
+ while(true) {
+ //System.out.println(" label=" + scratchArc.label + " target=" + scratchArc.target + " h=" + h + " output=" + fst.outputs.outputToString(scratchArc.output) + " next?=" + scratchArc.flag(4) + " final?=" + scratchArc.isFinal());
+ h = PRIME * h + scratchArc.label;
+ h = PRIME * h + scratchArc.target;
+ h = PRIME * h + scratchArc.output.hashCode();
+ h = PRIME * h + scratchArc.nextFinalOutput.hashCode();
+ if (scratchArc.isFinal()) {
+ h += 17;
+ }
+ if (scratchArc.isLast()) {
+ break;
+ }
+ fst.readNextRealArc(scratchArc, in);
+ }
+ //System.out.println(" ret " + (h&Integer.MAX_VALUE));
+ return h & Integer.MAX_VALUE;
+ }
+
+ public int add(Builder.UnCompiledNode<T> node) throws IOException {
+ // System.out.println("hash: add count=" + count + " vs " + table.length);
+ final int h = hash(node);
+ int pos = h & mask;
+ int c = 0;
+ while(true) {
+ final int v = table[pos];
+ if (v == 0) {
+ // freeze & add
+ final int address = fst.addNode(node);
+ //System.out.println(" now freeze addr=" + address);
+ assert hash(address) == h : "frozenHash=" + hash(address) + " vs h=" + h;
+ count++;
+ table[pos] = address;
+ if (table.length < 2*count) {
+ rehash();
+ }
+ return address;
+ } else if (nodesEqual(node, v)) {
+ // same node is already here
+ return v;
+ }
+
+ // quadratic probe
+ pos = (pos + (++c)) & mask;
+ }
+ }
+
+ // called only by rehash
+ private void addNew(int address) throws IOException {
+ int pos = hash(address) & mask;
+ int c = 0;
+ while(true) {
+ if (table[pos] == 0) {
+ table[pos] = address;
+ break;
+ }
+
+ // quadratic probe
+ pos = (pos + (++c)) & mask;
+ }
+ }
+
+ private void rehash() throws IOException {
+ final int[] oldTable = table;
+ table = new int[2*table.length];
+ mask = table.length-1;
+ for(int idx=0;idx<oldTable.length;idx++) {
+ final int address = oldTable[idx];
+ if (address != 0) {
+ addNew(address);
+ }
+ }
+ }
+
+ public int count() {
+ return count;
+ }
+}
fnp / pylucene.git / blobdiff