lucene-java-3.5.0/lucene/src/java/org/apache/lucene/index/MultiLevelSkipListWriter.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
  22 import org.apache.lucene.store.IndexOutput;
  23 import org.apache.lucene.store.RAMOutputStream;
  24
  25 /**
  26  * This abstract class writes skip lists with multiple levels.
  27  *
  28  * Example for skipInterval = 3:
  29  *                                                     c            (skip level 2)
  30  *                 c                 c                 c            (skip level 1)
  31  *     x     x     x     x     x     x     x     x     x     x      (skip level 0)
  32  * 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)
  33  *     3     6     9     12    15    18    21    24    27    30     (df)
  34  *
  35  * d - document
  36  * x - skip data
  37  * c - skip data with child pointer
  38  *
  39  * Skip level i contains every skipInterval-th entry from skip level i-1.
  40  * Therefore the number of entries on level i is: floor(df / ((skipInterval ^ (i + 1))).
  41  *
  42  * Each skip entry on a level i>0 contains a pointer to the corresponding skip entry in list i-1.
  43  * This guarantees a logarithmic amount of skips to find the target document.
  44  *
  45  * While this class takes care of writing the different skip levels,
  46  * subclasses must define the actual format of the skip data.
  47  *
  48  */
  49 abstract class MultiLevelSkipListWriter {
  50   // number of levels in this skip list
  51   private int numberOfSkipLevels;
  52
  53   // the skip interval in the list with level = 0
  54   private int skipInterval;
  55
  56   // for every skip level a different buffer is used
  57   private RAMOutputStream[] skipBuffer;
  58
  59   protected MultiLevelSkipListWriter(int skipInterval, int maxSkipLevels, int df) {
  60     this.skipInterval = skipInterval;
  61
  62     // calculate the maximum number of skip levels for this document frequency
  63     numberOfSkipLevels = df == 0 ? 0 : (int) Math.floor(Math.log(df) / Math.log(skipInterval));
  64
  65     // make sure it does not exceed maxSkipLevels
  66     if (numberOfSkipLevels > maxSkipLevels) {
  67       numberOfSkipLevels = maxSkipLevels;
  68     }
  69   }
  70
  71   protected void init() {
  72     skipBuffer = new RAMOutputStream[numberOfSkipLevels];
  73     for (int i = 0; i < numberOfSkipLevels; i++) {
  74       skipBuffer[i] = new RAMOutputStream();
  75     }
  76   }
  77
  78   protected void resetSkip() {
  79     // creates new buffers or empties the existing ones
  80     if (skipBuffer == null) {
  81       init();
  82     } else {
  83       for (int i = 0; i < skipBuffer.length; i++) {
  84         skipBuffer[i].reset();
  85       }
  86     }
  87   }
  88
  89   /**
  90    * Subclasses must implement the actual skip data encoding in this method.
  91    *
  92    * @param level the level skip data shall be writing for
  93    * @param skipBuffer the skip buffer to write to
  94    */
  95   protected abstract void writeSkipData(int level, IndexOutput skipBuffer) throws IOException;
  96
  97   /**
  98    * Writes the current skip data to the buffers. The current document frequency determines
  99    * the max level is skip data is to be written to.
 100    *
 101    * @param df the current document frequency
 102    * @throws IOException
 103    */
 104   void bufferSkip(int df) throws IOException {
 105     int numLevels;
 106
 107     // determine max level
 108     for (numLevels = 0; (df % skipInterval) == 0 && numLevels < numberOfSkipLevels; df /= skipInterval) {
 109       numLevels++;
 110     }
 111
 112     long childPointer = 0;
 113
 114     for (int level = 0; level < numLevels; level++) {
 115       writeSkipData(level, skipBuffer[level]);
 116
 117       long newChildPointer = skipBuffer[level].getFilePointer();
 118
 119       if (level != 0) {
 120         // store child pointers for all levels except the lowest
 121         skipBuffer[level].writeVLong(childPointer);
 122       }
 123
 124       //remember the childPointer for the next level
 125       childPointer = newChildPointer;
 126     }
 127   }
 128
 129   /**
 130    * Writes the buffered skip lists to the given output.
 131    *
 132    * @param output the IndexOutput the skip lists shall be written to
 133    * @return the pointer the skip list starts
 134    */
 135   long writeSkip(IndexOutput output) throws IOException {
 136     long skipPointer = output.getFilePointer();
 137     if (skipBuffer == null || skipBuffer.length == 0) return skipPointer;
 138
 139     for (int level = numberOfSkipLevels - 1; level > 0; level--) {
 140       long length = skipBuffer[level].getFilePointer();
 141       if (length > 0) {
 142         output.writeVLong(length);
 143         skipBuffer[level].writeTo(output);
 144       }
 145     }
 146     skipBuffer[0].writeTo(output);
 147
 148     return skipPointer;
 149   }
 150
 151 }