FileDocCategorySizeDatePackage
MultiLevelSkipListReader.javaAPI DocApache Lucene 2.2.09297Sat Jun 16 22:20:36 BST 2007org.apache.lucene.index

MultiLevelSkipListReader

public abstract class MultiLevelSkipListReader extends Object
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.

Fields Summary
private int
maxNumberOfSkipLevels
private int
numberOfSkipLevels
private int
numberOfLevelsToBuffer
private int
docCount
private boolean
haveSkipped
private IndexInput[]
skipStream
private long[]
skipPointer
private int[]
skipInterval
private int[]
numSkipped
private int[]
skipDoc
private int
lastDoc
private long[]
childPointer
private long
lastChildPointer
private boolean
inputIsBuffered
Constructors Summary
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];
Methods Summary
voidclose()

    for (int i = 1; i < skipStream.length; i++) {
      if (skipStream[i] != null) {
        skipStream[i].close();
      }
    }
intgetDoc()
Returns the id of the doc to which the last call of {@link #skipTo(int)} has skipped.

    return lastDoc;
voidinit(long skipPointer, int df)
initializes the reader

    this.skipPointer[0] = skipPointer;
    this.docCount = df;
    Arrays.fill(skipDoc, 0);
    Arrays.fill(numSkipped, 0);
    haveSkipped = false;
    for (int i = 1; i < numberOfSkipLevels; i++) {
      skipStream[0] = null;
    }
private booleanloadNextSkip(int level)

    // 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;
private voidloadSkipLevels()
Loads the skip levels

    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();
protected abstract intreadSkipData(int level, org.apache.lucene.store.IndexInput skipStream)
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 voidseekChild(int level)
Seeks the skip entry on the given level
    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];
    }
  
protected voidsetLastSkipData(int level)
Copies the values of the last read skip entry on this level
    lastDoc = skipDoc[level];
    lastChildPointer = childPointer[level];
  
intskipTo(int target)
Skips entries to the first beyond the current whose document number is
greater than or equal to target. Returns the current doc count.
    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;