+++ /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 org.apache.lucene.store.IndexOutput;
-import org.apache.lucene.store.RAMOutputStream;
-
-/**
- * This abstract class writes skip lists with multiple levels.
- *
- * Example for skipInterval = 3:
- * c (skip level 2)
- * c c c (skip level 1)
- * x x x x x x x x x x (skip level 0)
- * 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)
- * 3 6 9 12 15 18 21 24 27 30 (df)
- *
- * d - document
- * x - skip data
- * c - skip data with child pointer
- *
- * Skip level i contains every skipInterval-th entry from skip level i-1.
- * Therefore the number of entries on level i is: floor(df / ((skipInterval ^ (i + 1))).
- *
- * Each skip entry on a level i>0 contains a pointer to the corresponding skip entry in list i-1.
- * This guarantees a logarithmic amount of skips to find the target document.
- *
- * While this class takes care of writing the different skip levels,
- * subclasses must define the actual format of the skip data.
- *
- */
-abstract class MultiLevelSkipListWriter {
- // number of levels in this skip list
- private int numberOfSkipLevels;
-
- // the skip interval in the list with level = 0
- private int skipInterval;
-
- // for every skip level a different buffer is used
- private RAMOutputStream[] skipBuffer;
-
- protected MultiLevelSkipListWriter(int skipInterval, int maxSkipLevels, int df) {
- this.skipInterval = skipInterval;
-
- // calculate the maximum number of skip levels for this document frequency
- numberOfSkipLevels = df == 0 ? 0 : (int) Math.floor(Math.log(df) / Math.log(skipInterval));
-
- // make sure it does not exceed maxSkipLevels
- if (numberOfSkipLevels > maxSkipLevels) {
- numberOfSkipLevels = maxSkipLevels;
- }
- }
-
- protected void init() {
- skipBuffer = new RAMOutputStream[numberOfSkipLevels];
- for (int i = 0; i < numberOfSkipLevels; i++) {
- skipBuffer[i] = new RAMOutputStream();
- }
- }
-
- protected void resetSkip() {
- // creates new buffers or empties the existing ones
- if (skipBuffer == null) {
- init();
- } else {
- for (int i = 0; i < skipBuffer.length; i++) {
- skipBuffer[i].reset();
- }
- }
- }
-
- /**
- * Subclasses must implement the actual skip data encoding in this method.
- *
- * @param level the level skip data shall be writing for
- * @param skipBuffer the skip buffer to write to
- */
- protected abstract void writeSkipData(int level, IndexOutput skipBuffer) throws IOException;
-
- /**
- * Writes the current skip data to the buffers. The current document frequency determines
- * the max level is skip data is to be written to.
- *
- * @param df the current document frequency
- * @throws IOException
- */
- void bufferSkip(int df) throws IOException {
- int numLevels;
-
- // determine max level
- for (numLevels = 0; (df % skipInterval) == 0 && numLevels < numberOfSkipLevels; df /= skipInterval) {
- numLevels++;
- }
-
- long childPointer = 0;
-
- for (int level = 0; level < numLevels; level++) {
- writeSkipData(level, skipBuffer[level]);
-
- long newChildPointer = skipBuffer[level].getFilePointer();
-
- if (level != 0) {
- // store child pointers for all levels except the lowest
- skipBuffer[level].writeVLong(childPointer);
- }
-
- //remember the childPointer for the next level
- childPointer = newChildPointer;
- }
- }
-
- /**
- * Writes the buffered skip lists to the given output.
- *
- * @param output the IndexOutput the skip lists shall be written to
- * @return the pointer the skip list starts
- */
- long writeSkip(IndexOutput output) throws IOException {
- long skipPointer = output.getFilePointer();
- if (skipBuffer == null || skipBuffer.length == 0) return skipPointer;
-
- for (int level = numberOfSkipLevels - 1; level > 0; level--) {
- long length = skipBuffer[level].getFilePointer();
- if (length > 0) {
- output.writeVLong(length);
- skipBuffer[level].writeTo(output);
- }
- }
- skipBuffer[0].writeTo(output);
-
- return skipPointer;
- }
-
-}
fnp / pylucene.git / blobdiff