1 package org.apache.lucene.index;
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
11 * http://www.apache.org/licenses/LICENSE-2.0
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.
20 import java.io.IOException;
22 import org.apache.lucene.store.IndexOutput;
23 import org.apache.lucene.store.RAMOutputStream;
26 * This abstract class writes skip lists with multiple levels.
28 * Example for skipInterval = 3:
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)
37 * c - skip data with child pointer
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))).
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.
45 * While this class takes care of writing the different skip levels,
46 * subclasses must define the actual format of the skip data.
49 abstract class MultiLevelSkipListWriter {
50 // number of levels in this skip list
51 private int numberOfSkipLevels;
53 // the skip interval in the list with level = 0
54 private int skipInterval;
56 // for every skip level a different buffer is used
57 private RAMOutputStream[] skipBuffer;
59 protected MultiLevelSkipListWriter(int skipInterval, int maxSkipLevels, int df) {
60 this.skipInterval = skipInterval;
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));
65 // make sure it does not exceed maxSkipLevels
66 if (numberOfSkipLevels > maxSkipLevels) {
67 numberOfSkipLevels = maxSkipLevels;
71 protected void init() {
72 skipBuffer = new RAMOutputStream[numberOfSkipLevels];
73 for (int i = 0; i < numberOfSkipLevels; i++) {
74 skipBuffer[i] = new RAMOutputStream();
78 protected void resetSkip() {
79 // creates new buffers or empties the existing ones
80 if (skipBuffer == null) {
83 for (int i = 0; i < skipBuffer.length; i++) {
84 skipBuffer[i].reset();
90 * Subclasses must implement the actual skip data encoding in this method.
92 * @param level the level skip data shall be writing for
93 * @param skipBuffer the skip buffer to write to
95 protected abstract void writeSkipData(int level, IndexOutput skipBuffer) throws IOException;
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.
101 * @param df the current document frequency
102 * @throws IOException
104 void bufferSkip(int df) throws IOException {
107 // determine max level
108 for (numLevels = 0; (df % skipInterval) == 0 && numLevels < numberOfSkipLevels; df /= skipInterval) {
112 long childPointer = 0;
114 for (int level = 0; level < numLevels; level++) {
115 writeSkipData(level, skipBuffer[level]);
117 long newChildPointer = skipBuffer[level].getFilePointer();
120 // store child pointers for all levels except the lowest
121 skipBuffer[level].writeVLong(childPointer);
124 //remember the childPointer for the next level
125 childPointer = newChildPointer;
130 * Writes the buffered skip lists to the given output.
132 * @param output the IndexOutput the skip lists shall be written to
133 * @return the pointer the skip list starts
135 long writeSkip(IndexOutput output) throws IOException {
136 long skipPointer = output.getFilePointer();
137 if (skipBuffer == null || skipBuffer.length == 0) return skipPointer;
139 for (int level = numberOfSkipLevels - 1; level > 0; level--) {
140 long length = skipBuffer[level].getFilePointer();
142 output.writeVLong(length);
143 skipBuffer[level].writeTo(output);
146 skipBuffer[0].writeTo(output);