X-Git-Url: https://git.mdrn.pl/pylucene.git/blobdiff_plain/a2e61f0c04805cfcb8706176758d1283c7e3a55c..aaeed5504b982cf3545252ab528713250aa33eed:/lucene-java-3.5.0/lucene/src/java/org/apache/lucene/index/MultiLevelSkipListWriter.java

diff --git a/lucene-java-3.5.0/lucene/src/java/org/apache/lucene/index/MultiLevelSkipListWriter.java b/lucene-java-3.5.0/lucene/src/java/org/apache/lucene/index/MultiLevelSkipListWriter.java
new file mode 100644
index 0000000..f4f43e2
--- /dev/null
+++ b/lucene-java-3.5.0/lucene/src/java/org/apache/lucene/index/MultiLevelSkipListWriter.java
@@ -0,0 +1,151 @@
+package org.apache.lucene.index;
+
+/**
+ * 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;
+
+import org.apache.lucene.store.IndexOutput;
+import org.apache.lucene.store.RAMOutputStream;
+
+/**
+ * This abstract class writes skip lists with multiple levels.
+ * 
+ * Example for skipInterval = 3:
+ *                                                     c            (skip level 2)
+ *                 c                 c                 c            (skip level 1) 
+ *     x     x     x     x     x     x     x     x     x     x      (skip level 0)
+ * d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d  (posting list)
+ *     3     6     9     12    15    18    21    24    27    30     (df)
+ * 
+ * d - document
+ * x - skip data
+ * c - skip data with child pointer
+ * 
+ * Skip level i contains every skipInterval-th entry from skip level i-1.
+ * Therefore the number of entries on level i is: floor(df / ((skipInterval ^ (i + 1))).
+ * 
+ * Each skip entry on a level i>0 contains a pointer to the corresponding skip entry in list i-1.
+ * This guarantees a logarithmic amount of skips to find the target document.
+ * 
+ * While this class takes care of writing the different skip levels,
+ * subclasses must define the actual format of the skip data.
+ * 
+ */
+abstract class MultiLevelSkipListWriter {
+  // number of levels in this skip list
+  private int numberOfSkipLevels;
+  
+  // the skip interval in the list with level = 0
+  private int skipInterval;
+  
+  // for every skip level a different buffer is used 
+  private RAMOutputStream[] skipBuffer;
+
+  protected MultiLevelSkipListWriter(int skipInterval, int maxSkipLevels, int df) {
+    this.skipInterval = skipInterval;
+    
+    // calculate the maximum number of skip levels for this document frequency
+    numberOfSkipLevels = df == 0 ? 0 : (int) Math.floor(Math.log(df) / Math.log(skipInterval));
+    
+    // make sure it does not exceed maxSkipLevels
+    if (numberOfSkipLevels > maxSkipLevels) {
+      numberOfSkipLevels = maxSkipLevels;
+    }
+  }
+  
+  protected void init() {
+    skipBuffer = new RAMOutputStream[numberOfSkipLevels];
+    for (int i = 0; i < numberOfSkipLevels; i++) {
+      skipBuffer[i] = new RAMOutputStream();
+    }
+  }
+
+  protected void resetSkip() {
+    // creates new buffers or empties the existing ones
+    if (skipBuffer == null) {
+      init();
+    } else {
+      for (int i = 0; i < skipBuffer.length; i++) {
+        skipBuffer[i].reset();
+      }
+    }      
+  }
+
+  /**
+   * Subclasses must implement the actual skip data encoding in this method.
+   *  
+   * @param level the level skip data shall be writing for
+   * @param skipBuffer the skip buffer to write to
+   */
+  protected abstract void writeSkipData(int level, IndexOutput skipBuffer) throws IOException;
+  
+  /**
+   * Writes the current skip data to the buffers. The current document frequency determines
+   * the max level is skip data is to be written to. 
+   * 
+   * @param df the current document frequency 
+   * @throws IOException
+   */
+  void bufferSkip(int df) throws IOException {
+    int numLevels;
+   
+    // determine max level
+    for (numLevels = 0; (df % skipInterval) == 0 && numLevels < numberOfSkipLevels; df /= skipInterval) {
+      numLevels++;
+    }
+    
+    long childPointer = 0;
+    
+    for (int level = 0; level < numLevels; level++) {
+      writeSkipData(level, skipBuffer[level]);
+      
+      long newChildPointer = skipBuffer[level].getFilePointer();
+      
+      if (level != 0) {
+        // store child pointers for all levels except the lowest
+        skipBuffer[level].writeVLong(childPointer);
+      }
+      
+      //remember the childPointer for the next level
+      childPointer = newChildPointer;
+    }
+  }
+
+  /**
+   * Writes the buffered skip lists to the given output.
+   * 
+   * @param output the IndexOutput the skip lists shall be written to 
+   * @return the pointer the skip list starts
+   */
+  long writeSkip(IndexOutput output) throws IOException {
+    long skipPointer = output.getFilePointer();
+    if (skipBuffer == null || skipBuffer.length == 0) return skipPointer;
+    
+    for (int level = numberOfSkipLevels - 1; level > 0; level--) {
+      long length = skipBuffer[level].getFilePointer();
+      if (length > 0) {
+        output.writeVLong(length);
+        skipBuffer[level].writeTo(output);
+      }
+    }
+    skipBuffer[0].writeTo(output);
+    
+    return skipPointer;
+  }
+
+}