lucene-java-3.4.0/lucene/src/java/org/apache/lucene/index/MultiLevelSkipListReader.java

   1 package org.apache.lucene.index;
   2
   3 /**
   4  * Licensed to the Apache Software Foundation (ASF) under one or more
   5  * contributor license agreements.  See the NOTICE file distributed with
   6  * this work for additional information regarding copyright ownership.
   7  * The ASF licenses this file to You under the Apache License, Version 2.0
   8  * (the "License"); you may not use this file except in compliance with
   9  * the License.  You may obtain a copy of the License at
  10  *
  11  *     http://www.apache.org/licenses/LICENSE-2.0
  12  *
  13  * Unless required by applicable law or agreed to in writing, software
  14  * distributed under the License is distributed on an "AS IS" BASIS,
  15  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  16  * See the License for the specific language governing permissions and
  17  * limitations under the License.
  18  */
  19
  20 import java.io.IOException;
  21 import java.util.Arrays;
  22
  23 import org.apache.lucene.store.BufferedIndexInput;
  24 import org.apache.lucene.store.IndexInput;
  25
  26 /**
  27  * This abstract class reads skip lists with multiple levels.
  28  *
  29  * See {@link MultiLevelSkipListWriter} for the information about the encoding
  30  * of the multi level skip lists.
  31  *
  32  * Subclasses must implement the abstract method {@link #readSkipData(int, IndexInput)}
  33  * which defines the actual format of the skip data.
  34  */
  35 abstract class MultiLevelSkipListReader {
  36   // the maximum number of skip levels possible for this index
  37   private int maxNumberOfSkipLevels;
  38
  39   // number of levels in this skip list
  40   private int numberOfSkipLevels;
  41
  42   // Expert: defines the number of top skip levels to buffer in memory.
  43   // Reducing this number results in less memory usage, but possibly
  44   // slower performance due to more random I/Os.
  45   // Please notice that the space each level occupies is limited by
  46   // the skipInterval. The top level can not contain more than
  47   // skipLevel entries, the second top level can not contain more
  48   // than skipLevel^2 entries and so forth.
  49   private int numberOfLevelsToBuffer = 1;
  50
  51   private int docCount;
  52   private boolean haveSkipped;
  53
  54   private IndexInput[] skipStream;    // skipStream for each level
  55   private long skipPointer[];         // the start pointer of each skip level
  56   private int skipInterval[];         // skipInterval of each level
  57   private int[] numSkipped;           // number of docs skipped per level
  58
  59   private int[] skipDoc;              // doc id of current skip entry per level
  60   private int lastDoc;                // doc id of last read skip entry with docId <= target
  61   private long[] childPointer;        // child pointer of current skip entry per level
  62   private long lastChildPointer;      // childPointer of last read skip entry with docId <= target
  63
  64   private boolean inputIsBuffered;
  65
  66   public MultiLevelSkipListReader(IndexInput skipStream, int maxSkipLevels, int skipInterval) {
  67     this.skipStream = new IndexInput[maxSkipLevels];
  68     this.skipPointer = new long[maxSkipLevels];
  69     this.childPointer = new long[maxSkipLevels];
  70     this.numSkipped = new int[maxSkipLevels];
  71     this.maxNumberOfSkipLevels = maxSkipLevels;
  72     this.skipInterval = new int[maxSkipLevels];
  73     this.skipStream [0]= skipStream;
  74     this.inputIsBuffered = (skipStream instanceof BufferedIndexInput);
  75     this.skipInterval[0] = skipInterval;
  76     for (int i = 1; i < maxSkipLevels; i++) {
  77       // cache skip intervals
  78       this.skipInterval[i] = this.skipInterval[i - 1] * skipInterval;
  79     }
  80     skipDoc = new int[maxSkipLevels];
  81   }
  82
  83
  84   /** Returns the id of the doc to which the last call of {@link #skipTo(int)}
  85    *  has skipped.  */
  86   int getDoc() {
  87     return lastDoc;
  88   }
  89
  90
  91   /** Skips entries to the first beyond the current whose document number is
  92    *  greater than or equal to <i>target</i>. Returns the current doc count.
  93    */
  94   int skipTo(int target) throws IOException {
  95     if (!haveSkipped) {
  96       // first time, load skip levels
  97       loadSkipLevels();
  98       haveSkipped = true;
  99     }
 100
 101     // walk up the levels until highest level is found that has a skip
 102     // for this target
 103     int level = 0;
 104     while (level < numberOfSkipLevels - 1 && target > skipDoc[level + 1]) {
 105       level++;
 106     }
 107
 108     while (level >= 0) {
 109       if (target > skipDoc[level]) {
 110         if (!loadNextSkip(level)) {
 111           continue;
 112         }
 113       } else {
 114         // no more skips on this level, go down one level
 115         if (level > 0 && lastChildPointer > skipStream[level - 1].getFilePointer()) {
 116           seekChild(level - 1);
 117         }
 118         level--;
 119       }
 120     }
 121
 122     return numSkipped[0] - skipInterval[0] - 1;
 123   }
 124
 125   private boolean loadNextSkip(int level) throws IOException {
 126     // we have to skip, the target document is greater than the current
 127     // skip list entry
 128     setLastSkipData(level);
 129
 130     numSkipped[level] += skipInterval[level];
 131
 132     if (numSkipped[level] > docCount) {
 133       // this skip list is exhausted
 134       skipDoc[level] = Integer.MAX_VALUE;
 135       if (numberOfSkipLevels > level) numberOfSkipLevels = level;
 136       return false;
 137     }
 138
 139     // read next skip entry
 140     skipDoc[level] += readSkipData(level, skipStream[level]);
 141
 142     if (level != 0) {
 143       // read the child pointer if we are not on the leaf level
 144       childPointer[level] = skipStream[level].readVLong() + skipPointer[level - 1];
 145     }
 146
 147     return true;
 148
 149   }
 150
 151   /** Seeks the skip entry on the given level */
 152   protected void seekChild(int level) throws IOException {
 153     skipStream[level].seek(lastChildPointer);
 154     numSkipped[level] = numSkipped[level + 1] - skipInterval[level + 1];
 155     skipDoc[level] = lastDoc;
 156     if (level > 0) {
 157         childPointer[level] = skipStream[level].readVLong() + skipPointer[level - 1];
 158     }
 159   }
 160
 161   void close() throws IOException {
 162     for (int i = 1; i < skipStream.length; i++) {
 163       if (skipStream[i] != null) {
 164         skipStream[i].close();
 165       }
 166     }
 167   }
 168
 169   /** initializes the reader */
 170   void init(long skipPointer, int df) {
 171     this.skipPointer[0] = skipPointer;
 172     this.docCount = df;
 173     Arrays.fill(skipDoc, 0);
 174     Arrays.fill(numSkipped, 0);
 175     Arrays.fill(childPointer, 0);
 176
 177     haveSkipped = false;
 178     for (int i = 1; i < numberOfSkipLevels; i++) {
 179       skipStream[i] = null;
 180     }
 181   }
 182
 183   /** Loads the skip levels  */
 184   private void loadSkipLevels() throws IOException {
 185     numberOfSkipLevels = docCount == 0 ? 0 : (int) Math.floor(Math.log(docCount) / Math.log(skipInterval[0]));
 186     if (numberOfSkipLevels > maxNumberOfSkipLevels) {
 187       numberOfSkipLevels = maxNumberOfSkipLevels;
 188     }
 189
 190     skipStream[0].seek(skipPointer[0]);
 191
 192     int toBuffer = numberOfLevelsToBuffer;
 193
 194     for (int i = numberOfSkipLevels - 1; i > 0; i--) {
 195       // the length of the current level
 196       long length = skipStream[0].readVLong();
 197
 198       // the start pointer of the current level
 199       skipPointer[i] = skipStream[0].getFilePointer();
 200       if (toBuffer > 0) {
 201         // buffer this level
 202         skipStream[i] = new SkipBuffer(skipStream[0], (int) length);
 203         toBuffer--;
 204       } else {
 205         // clone this stream, it is already at the start of the current level
 206         skipStream[i] = (IndexInput) skipStream[0].clone();
 207         if (inputIsBuffered && length < BufferedIndexInput.BUFFER_SIZE) {
 208           ((BufferedIndexInput) skipStream[i]).setBufferSize((int) length);
 209         }
 210
 211         // move base stream beyond the current level
 212         skipStream[0].seek(skipStream[0].getFilePointer() + length);
 213       }
 214     }
 215
 216     // use base stream for the lowest level
 217     skipPointer[0] = skipStream[0].getFilePointer();
 218   }
 219
 220   /**
 221    * Subclasses must implement the actual skip data encoding in this method.
 222    *
 223    * @param level the level skip data shall be read from
 224    * @param skipStream the skip stream to read from
 225    */
 226   protected abstract int readSkipData(int level, IndexInput skipStream) throws IOException;
 227
 228   /** Copies the values of the last read skip entry on this level */
 229   protected void setLastSkipData(int level) {
 230     lastDoc = skipDoc[level];
 231     lastChildPointer = childPointer[level];
 232   }
 233
 234
 235   /** used to buffer the top skip levels */
 236   private final static class SkipBuffer extends IndexInput {
 237     private byte[] data;
 238     private long pointer;
 239     private int pos;
 240
 241     SkipBuffer(IndexInput input, int length) throws IOException {
 242       data = new byte[length];
 243       pointer = input.getFilePointer();
 244       input.readBytes(data, 0, length);
 245     }
 246
 247     @Override
 248     public void close() throws IOException {
 249       data = null;
 250     }
 251
 252     @Override
 253     public long getFilePointer() {
 254       return pointer + pos;
 255     }
 256
 257     @Override
 258     public long length() {
 259       return data.length;
 260     }
 261
 262     @Override
 263     public byte readByte() throws IOException {
 264       return data[pos++];
 265     }
 266
 267     @Override
 268     public void readBytes(byte[] b, int offset, int len) throws IOException {
 269       System.arraycopy(data, pos, b, offset, len);
 270       pos += len;
 271     }
 272
 273     @Override
 274     public void seek(long pos) throws IOException {
 275       this.pos =  (int) (pos - pointer);
 276     }
 277
 278   }
 279 }