+++ /dev/null
-package org.apache.lucene.index;
-
-/**
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-import java.io.IOException;
-import java.util.Arrays;
-
-import org.apache.lucene.store.BufferedIndexInput;
-import org.apache.lucene.store.IndexInput;
-
-/**
- * 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.
- */
-abstract class MultiLevelSkipListReader {
- // the maximum number of skip levels possible for this index
- private int maxNumberOfSkipLevels;
-
- // number of levels in this skip list
- private int numberOfSkipLevels;
-
- // Expert: defines the number of top skip levels to buffer in memory.
- // Reducing this number results in less memory usage, but possibly
- // slower performance due to more random I/Os.
- // Please notice that the space each level occupies is limited by
- // the skipInterval. The top level can not contain more than
- // skipLevel entries, the second top level can not contain more
- // than skipLevel^2 entries and so forth.
- private int numberOfLevelsToBuffer = 1;
-
- private int docCount;
- private boolean haveSkipped;
-
- private IndexInput[] skipStream; // skipStream for each level
- private long skipPointer[]; // the start pointer of each skip level
- private int skipInterval[]; // skipInterval of each level
- private int[] numSkipped; // number of docs skipped per level
-
- private int[] skipDoc; // doc id of current skip entry per level
- private int lastDoc; // doc id of last read skip entry with docId <= target
- private long[] childPointer; // child pointer of current skip entry per level
- private long lastChildPointer; // childPointer of last read skip entry with docId <= target
-
- private boolean inputIsBuffered;
-
- 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];
- }
-
-
- /** Returns the id of the doc to which the last call of {@link #skipTo(int)}
- * has skipped. */
- int getDoc() {
- return lastDoc;
- }
-
-
- /** Skips entries to the first beyond the current whose document number is
- * greater than or equal to <i>target</i>. Returns the current doc count.
- */
- int skipTo(int target) throws IOException {
- 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;
- }
-
- private boolean loadNextSkip(int level) throws IOException {
- // 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;
-
- }
-
- /** Seeks the skip entry on the given level */
- protected void seekChild(int level) throws IOException {
- 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];
- }
- }
-
- void close() throws IOException {
- for (int i = 1; i < skipStream.length; i++) {
- if (skipStream[i] != null) {
- skipStream[i].close();
- }
- }
- }
-
- /** initializes the reader */
- void init(long skipPointer, int df) {
- this.skipPointer[0] = skipPointer;
- this.docCount = df;
- Arrays.fill(skipDoc, 0);
- Arrays.fill(numSkipped, 0);
- Arrays.fill(childPointer, 0);
-
- haveSkipped = false;
- for (int i = 1; i < numberOfSkipLevels; i++) {
- skipStream[i] = null;
- }
- }
-
- /** Loads the skip levels */
- private void loadSkipLevels() throws IOException {
- 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();
- }
-
- /**
- * 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 abstract int readSkipData(int level, IndexInput skipStream) throws IOException;
-
- /** Copies the values of the last read skip entry on this level */
- protected void setLastSkipData(int level) {
- lastDoc = skipDoc[level];
- lastChildPointer = childPointer[level];
- }
-
-
- /** used to buffer the top skip levels */
- private final static class SkipBuffer extends IndexInput {
- private byte[] data;
- private long pointer;
- private int pos;
-
- SkipBuffer(IndexInput input, int length) throws IOException {
- data = new byte[length];
- pointer = input.getFilePointer();
- input.readBytes(data, 0, length);
- }
-
- @Override
- public void close() throws IOException {
- data = null;
- }
-
- @Override
- public long getFilePointer() {
- return pointer + pos;
- }
-
- @Override
- public long length() {
- return data.length;
- }
-
- @Override
- public byte readByte() throws IOException {
- return data[pos++];
- }
-
- @Override
- public void readBytes(byte[] b, int offset, int len) throws IOException {
- System.arraycopy(data, pos, b, offset, len);
- pos += len;
- }
-
- @Override
- public void seek(long pos) throws IOException {
- this.pos = (int) (pos - pointer);
- }
-
- }
-}
fnp / pylucene.git / blobdiff