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;
21 import java.util.Arrays;
23 import org.apache.lucene.store.BufferedIndexInput;
24 import org.apache.lucene.store.IndexInput;
27 * This abstract class reads skip lists with multiple levels.
29 * See {@link MultiLevelSkipListWriter} for the information about the encoding
30 * of the multi level skip lists.
32 * Subclasses must implement the abstract method {@link #readSkipData(int, IndexInput)}
33 * which defines the actual format of the skip data.
35 abstract class MultiLevelSkipListReader {
36 // the maximum number of skip levels possible for this index
37 private int maxNumberOfSkipLevels;
39 // number of levels in this skip list
40 private int numberOfSkipLevels;
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;
52 private boolean haveSkipped;
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
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
64 private boolean inputIsBuffered;
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;
80 skipDoc = new int[maxSkipLevels];
84 /** Returns the id of the doc to which the last call of {@link #skipTo(int)}
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.
94 int skipTo(int target) throws IOException {
96 // first time, load skip levels
101 // walk up the levels until highest level is found that has a skip
104 while (level < numberOfSkipLevels - 1 && target > skipDoc[level + 1]) {
109 if (target > skipDoc[level]) {
110 if (!loadNextSkip(level)) {
114 // no more skips on this level, go down one level
115 if (level > 0 && lastChildPointer > skipStream[level - 1].getFilePointer()) {
116 seekChild(level - 1);
122 return numSkipped[0] - skipInterval[0] - 1;
125 private boolean loadNextSkip(int level) throws IOException {
126 // we have to skip, the target document is greater than the current
128 setLastSkipData(level);
130 numSkipped[level] += skipInterval[level];
132 if (numSkipped[level] > docCount) {
133 // this skip list is exhausted
134 skipDoc[level] = Integer.MAX_VALUE;
135 if (numberOfSkipLevels > level) numberOfSkipLevels = level;
139 // read next skip entry
140 skipDoc[level] += readSkipData(level, skipStream[level]);
143 // read the child pointer if we are not on the leaf level
144 childPointer[level] = skipStream[level].readVLong() + skipPointer[level - 1];
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;
157 childPointer[level] = skipStream[level].readVLong() + skipPointer[level - 1];
161 void close() throws IOException {
162 for (int i = 1; i < skipStream.length; i++) {
163 if (skipStream[i] != null) {
164 skipStream[i].close();
169 /** initializes the reader */
170 void init(long skipPointer, int df) {
171 this.skipPointer[0] = skipPointer;
173 Arrays.fill(skipDoc, 0);
174 Arrays.fill(numSkipped, 0);
175 Arrays.fill(childPointer, 0);
178 for (int i = 1; i < numberOfSkipLevels; i++) {
179 skipStream[i] = null;
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;
190 skipStream[0].seek(skipPointer[0]);
192 int toBuffer = numberOfLevelsToBuffer;
194 for (int i = numberOfSkipLevels - 1; i > 0; i--) {
195 // the length of the current level
196 long length = skipStream[0].readVLong();
198 // the start pointer of the current level
199 skipPointer[i] = skipStream[0].getFilePointer();
202 skipStream[i] = new SkipBuffer(skipStream[0], (int) length);
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);
211 // move base stream beyond the current level
212 skipStream[0].seek(skipStream[0].getFilePointer() + length);
216 // use base stream for the lowest level
217 skipPointer[0] = skipStream[0].getFilePointer();
221 * Subclasses must implement the actual skip data encoding in this method.
223 * @param level the level skip data shall be read from
224 * @param skipStream the skip stream to read from
226 protected abstract int readSkipData(int level, IndexInput skipStream) throws IOException;
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];
235 /** used to buffer the top skip levels */
236 private final static class SkipBuffer extends IndexInput {
238 private long pointer;
241 SkipBuffer(IndexInput input, int length) throws IOException {
242 data = new byte[length];
243 pointer = input.getFilePointer();
244 input.readBytes(data, 0, length);
248 public void close() throws IOException {
253 public long getFilePointer() {
254 return pointer + pos;
258 public long length() {
263 public byte readByte() throws IOException {
268 public void readBytes(byte[] b, int offset, int len) throws IOException {
269 System.arraycopy(data, pos, b, offset, len);
274 public void seek(long pos) throws IOException {
275 this.pos = (int) (pos - pointer);