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/MultiLevelSkipListReader.java

diff --git a/lucene-java-3.5.0/lucene/src/java/org/apache/lucene/index/MultiLevelSkipListReader.java b/lucene-java-3.5.0/lucene/src/java/org/apache/lucene/index/MultiLevelSkipListReader.java
new file mode 100644
index 0000000..c1176bf
--- /dev/null
+++ b/lucene-java-3.5.0/lucene/src/java/org/apache/lucene/index/MultiLevelSkipListReader.java
@@ -0,0 +1,280 @@
+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 java.util.Arrays;
+
+import org.apache.lucene.store.BufferedIndexInput;
+import org.apache.lucene.store.IndexInput;
+
+/**
+ * This abstract class reads skip lists with multiple levels.
+ * 
+ * See {@link MultiLevelSkipListWriter} for the information about the encoding 
+ * of the multi level skip lists. 
+ * 
+ * Subclasses must implement the abstract method {@link #readSkipData(int, IndexInput)}
+ * which defines the actual format of the skip data.
+ */
+abstract class MultiLevelSkipListReader {
+  // the maximum number of skip levels possible for this index
+  private int maxNumberOfSkipLevels; 
+  
+  // number of levels in this skip list
+  private int numberOfSkipLevels;
+  
+  // Expert: defines the number of top skip levels to buffer in memory.
+  // Reducing this number results in less memory usage, but possibly
+  // slower performance due to more random I/Os.
+  // Please notice that the space each level occupies is limited by
+  // the skipInterval. The top level can not contain more than
+  // skipLevel entries, the second top level can not contain more
+  // than skipLevel^2 entries and so forth.
+  private int numberOfLevelsToBuffer = 1;
+  
+  private int docCount;
+  private boolean haveSkipped;
+  
+  private IndexInput[] skipStream;    // skipStream for each level
+  private long skipPointer[];         // the start pointer of each skip level
+  private int skipInterval[];         // skipInterval of each level
+  private int[] numSkipped;           // number of docs skipped per level
+    
+  private int[] skipDoc;              // doc id of current skip entry per level 
+  private int lastDoc;                // doc id of last read skip entry with docId <= target
+  private long[] childPointer;        // child pointer of current skip entry per level
+  private long lastChildPointer;      // childPointer of last read skip entry with docId <= target
+  
+  private boolean inputIsBuffered;
+  
+  public MultiLevelSkipListReader(IndexInput skipStream, int maxSkipLevels, int skipInterval) {
+    this.skipStream = new IndexInput[maxSkipLevels];
+    this.skipPointer = new long[maxSkipLevels];
+    this.childPointer = new long[maxSkipLevels];
+    this.numSkipped = new int[maxSkipLevels];
+    this.maxNumberOfSkipLevels = maxSkipLevels;
+    this.skipInterval = new int[maxSkipLevels];
+    this.skipStream [0]= skipStream;
+    this.inputIsBuffered = (skipStream instanceof BufferedIndexInput);
+    this.skipInterval[0] = skipInterval;
+    for (int i = 1; i < maxSkipLevels; i++) {
+      // cache skip intervals
+      this.skipInterval[i] = this.skipInterval[i - 1] * skipInterval;
+    }
+    skipDoc = new int[maxSkipLevels];
+  }
+
+  
+  /** Returns the id of the doc to which the last call of {@link #skipTo(int)}
+   *  has skipped.  */
+  int getDoc() {
+    return lastDoc;
+  }
+  
+  
+  /** Skips entries to the first beyond the current whose document number is
+   *  greater than or equal to <i>target</i>. Returns the current doc count. 
+   */
+  int skipTo(int target) throws IOException {
+    if (!haveSkipped) {
+      // first time, load skip levels
+      loadSkipLevels();
+      haveSkipped = true;
+    }
+  
+    // walk up the levels until highest level is found that has a skip
+    // for this target
+    int level = 0;
+    while (level < numberOfSkipLevels - 1 && target > skipDoc[level + 1]) {
+      level++;
+    }    
+
+    while (level >= 0) {
+      if (target > skipDoc[level]) {
+        if (!loadNextSkip(level)) {
+          continue;
+        }
+      } else {
+        // no more skips on this level, go down one level
+        if (level > 0 && lastChildPointer > skipStream[level - 1].getFilePointer()) {
+          seekChild(level - 1);
+        } 
+        level--;
+      }
+    }
+    
+    return numSkipped[0] - skipInterval[0] - 1;
+  }
+  
+  private boolean loadNextSkip(int level) throws IOException {
+    // we have to skip, the target document is greater than the current
+    // skip list entry        
+    setLastSkipData(level);
+      
+    numSkipped[level] += skipInterval[level];
+      
+    if (numSkipped[level] > docCount) {
+      // this skip list is exhausted
+      skipDoc[level] = Integer.MAX_VALUE;
+      if (numberOfSkipLevels > level) numberOfSkipLevels = level; 
+      return false;
+    }
+
+    // read next skip entry
+    skipDoc[level] += readSkipData(level, skipStream[level]);
+    
+    if (level != 0) {
+      // read the child pointer if we are not on the leaf level
+      childPointer[level] = skipStream[level].readVLong() + skipPointer[level - 1];
+    }
+    
+    return true;
+
+  }
+  
+  /** Seeks the skip entry on the given level */
+  protected void seekChild(int level) throws IOException {
+    skipStream[level].seek(lastChildPointer);
+    numSkipped[level] = numSkipped[level + 1] - skipInterval[level + 1];
+    skipDoc[level] = lastDoc;
+    if (level > 0) {
+        childPointer[level] = skipStream[level].readVLong() + skipPointer[level - 1];
+    }
+  }
+  
+  void close() throws IOException {
+    for (int i = 1; i < skipStream.length; i++) {
+      if (skipStream[i] != null) {
+        skipStream[i].close();
+      }
+    }
+  }
+
+  /** initializes the reader */
+  void init(long skipPointer, int df) {
+    this.skipPointer[0] = skipPointer;
+    this.docCount = df;
+    Arrays.fill(skipDoc, 0);
+    Arrays.fill(numSkipped, 0);
+    Arrays.fill(childPointer, 0);
+    
+    haveSkipped = false;
+    for (int i = 1; i < numberOfSkipLevels; i++) {
+      skipStream[i] = null;
+    }
+  }
+  
+  /** Loads the skip levels  */
+  private void loadSkipLevels() throws IOException {
+    numberOfSkipLevels = docCount == 0 ? 0 : (int) Math.floor(Math.log(docCount) / Math.log(skipInterval[0]));
+    if (numberOfSkipLevels > maxNumberOfSkipLevels) {
+      numberOfSkipLevels = maxNumberOfSkipLevels;
+    }
+
+    skipStream[0].seek(skipPointer[0]);
+    
+    int toBuffer = numberOfLevelsToBuffer;
+    
+    for (int i = numberOfSkipLevels - 1; i > 0; i--) {
+      // the length of the current level
+      long length = skipStream[0].readVLong();
+      
+      // the start pointer of the current level
+      skipPointer[i] = skipStream[0].getFilePointer();
+      if (toBuffer > 0) {
+        // buffer this level
+        skipStream[i] = new SkipBuffer(skipStream[0], (int) length);
+        toBuffer--;
+      } else {
+        // clone this stream, it is already at the start of the current level
+        skipStream[i] = (IndexInput) skipStream[0].clone();
+        if (inputIsBuffered && length < BufferedIndexInput.BUFFER_SIZE) {
+          ((BufferedIndexInput) skipStream[i]).setBufferSize((int) length);
+        }
+        
+        // move base stream beyond the current level
+        skipStream[0].seek(skipStream[0].getFilePointer() + length);
+      }
+    }
+   
+    // use base stream for the lowest level
+    skipPointer[0] = skipStream[0].getFilePointer();
+  }
+  
+  /**
+   * Subclasses must implement the actual skip data encoding in this method.
+   *  
+   * @param level the level skip data shall be read from
+   * @param skipStream the skip stream to read from
+   */  
+  protected abstract int readSkipData(int level, IndexInput skipStream) throws IOException;
+  
+  /** Copies the values of the last read skip entry on this level */
+  protected void setLastSkipData(int level) {
+    lastDoc = skipDoc[level];
+    lastChildPointer = childPointer[level];
+  }
+
+  
+  /** used to buffer the top skip levels */
+  private final static class SkipBuffer extends IndexInput {
+    private byte[] data;
+    private long pointer;
+    private int pos;
+    
+    SkipBuffer(IndexInput input, int length) throws IOException {
+      super("SkipBuffer on " + input);
+      data = new byte[length];
+      pointer = input.getFilePointer();
+      input.readBytes(data, 0, length);
+    }
+    
+    @Override
+    public void close() throws IOException {
+      data = null;
+    }
+
+    @Override
+    public long getFilePointer() {
+      return pointer + pos;
+    }
+
+    @Override
+    public long length() {
+      return data.length;
+    }
+
+    @Override
+    public byte readByte() throws IOException {
+      return data[pos++];
+    }
+
+    @Override
+    public void readBytes(byte[] b, int offset, int len) throws IOException {
+      System.arraycopy(data, pos, b, offset, len);
+      pos += len;
+    }
+
+    @Override
+    public void seek(long pos) throws IOException {
+      this.pos =  (int) (pos - pointer);
+    }
+    
+  }
+}