[lucene-solr] branch master updated: LUCENE-8781: add FST array-with-gap addressing to Util.readCeilArc

[so...@apache.org]

This is an automated email from the ASF dual-hosted git repository.

sokolov pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/lucene-solr.git


The following commit(s) were added to refs/heads/master by this push:
     new 2e49f13  LUCENE-8781: add FST array-with-gap addressing to Util.readCeilArc
2e49f13 is described below

commit 2e49f13aa1ec5afbee0afb61e797a6acf9ad07e3
Author: Michael Sokolov <so...@amazon.com>
AuthorDate: Fri Jun 14 20:47:18 2019 -0400

    LUCENE-8781: add FST array-with-gap addressing to Util.readCeilArc
---
 .../core/src/java/org/apache/lucene/util/fst/Util.java   | 16 ++++++++++++++--
 1 file changed, 14 insertions(+), 2 deletions(-)

diff --git a/lucene/core/src/java/org/apache/lucene/util/fst/Util.java b/lucene/core/src/java/org/apache/lucene/util/fst/Util.java
index 04cd182..f8dd6fd 100644
--- a/lucene/core/src/java/org/apache/lucene/util/fst/Util.java
+++ b/lucene/core/src/java/org/apache/lucene/util/fst/Util.java
@@ -924,7 +924,7 @@ public final class Util {
   */
 
   /**
-   * Reads the first arc greater or equal that the given label into the provided
+   * Reads the first arc greater or equal than the given label into the provided
    * arc in place and returns it iff found, otherwise return <code>null</code>.
    * 
    * @param label the label to ceil on
@@ -958,7 +958,19 @@ public final class Util {
     }
     fst.readFirstTargetArc(follow, arc, in);
     if (arc.bytesPerArc != 0 && arc.label != FST.END_LABEL) {
-      // Arcs are fixed array -- use binary search to find
+      if (arc.arcIdx == Integer.MIN_VALUE) {
+        // Arcs are in an array-with-gaps
+        int offset = label - arc.label;
+        if (offset >= arc.numArcs) {
+          return null;
+        } else if (offset < 0) {
+          return arc;
+        } else {
+          arc.nextArc = arc.posArcsStart - offset * arc.bytesPerArc;
+          return fst.readNextRealArc(arc, in);
+        }
+      }
+      // Arcs are packed array -- use binary search to find
       // the target.
 
       int low = arc.arcIdx;