001: package org.apache.lucene.index;
002:
003: /**
004: * Licensed to the Apache Software Foundation (ASF) under one or more
005: * contributor license agreements. See the NOTICE file distributed with
006: * this work for additional information regarding copyright ownership.
007: * The ASF licenses this file to You under the Apache License, Version 2.0
008: * (the "License"); you may not use this file except in compliance with
009: * the License. You may obtain a copy of the License at
010: *
011: * http://www.apache.org/licenses/LICENSE-2.0
012: *
013: * Unless required by applicable law or agreed to in writing, software
014: * distributed under the License is distributed on an "AS IS" BASIS,
015: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
016: * See the License for the specific language governing permissions and
017: * limitations under the License.
018: */
019:
020: import java.io.IOException;
021:
022: import org.apache.lucene.store.IndexOutput;
023: import org.apache.lucene.store.RAMOutputStream;
024:
025: /**
026: * This abstract class writes skip lists with multiple levels.
027: *
028: * Example for skipInterval = 3:
029: * c (skip level 2)
030: * c c c (skip level 1)
031: * x x x x x x x x x x (skip level 0)
032: * 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)
033: * 3 6 9 12 15 18 21 24 27 30 (df)
034: *
035: * d - document
036: * x - skip data
037: * c - skip data with child pointer
038: *
039: * Skip level i contains every skipInterval-th entry from skip level i-1.
040: * Therefore the number of entries on level i is: floor(df / ((skipInterval ^ (i + 1))).
041: *
042: * Each skip entry on a level i>0 contains a pointer to the corresponding skip entry in list i-1.
043: * This guarantess a logarithmic amount of skips to find the target document.
044: *
045: * While this class takes care of writing the different skip levels,
046: * subclasses must define the actual format of the skip data.
047: *
048: */
049: abstract class MultiLevelSkipListWriter {
050: // number of levels in this skip list
051: private int numberOfSkipLevels;
052:
053: // the skip interval in the list with level = 0
054: private int skipInterval;
055:
056: // for every skip level a different buffer is used
057: private RAMOutputStream[] skipBuffer;
058:
059: protected MultiLevelSkipListWriter(int skipInterval,
060: int maxSkipLevels, int df) {
061: this .skipInterval = skipInterval;
062:
063: // calculate the maximum number of skip levels for this document frequency
064: numberOfSkipLevels = df == 0 ? 0 : (int) Math.floor(Math
065: .log(df)
066: / Math.log(skipInterval));
067:
068: // make sure it does not exceed maxSkipLevels
069: if (numberOfSkipLevels > maxSkipLevels) {
070: numberOfSkipLevels = maxSkipLevels;
071: }
072: }
073:
074: protected void init() {
075: skipBuffer = new RAMOutputStream[numberOfSkipLevels];
076: for (int i = 0; i < numberOfSkipLevels; i++) {
077: skipBuffer[i] = new RAMOutputStream();
078: }
079: }
080:
081: protected void resetSkip() {
082: // creates new buffers or empties the existing ones
083: if (skipBuffer == null) {
084: init();
085: } else {
086: for (int i = 0; i < skipBuffer.length; i++) {
087: skipBuffer[i].reset();
088: }
089: }
090: }
091:
092: /**
093: * Subclasses must implement the actual skip data encoding in this method.
094: *
095: * @param level the level skip data shall be writting for
096: * @param skipBuffer the skip buffer to write to
097: */
098: protected abstract void writeSkipData(int level,
099: IndexOutput skipBuffer) throws IOException;
100:
101: /**
102: * Writes the current skip data to the buffers. The current document frequency determines
103: * the max level is skip data is to be written to.
104: *
105: * @param df the current document frequency
106: * @throws IOException
107: */
108: void bufferSkip(int df) throws IOException {
109: int numLevels;
110:
111: // determine max level
112: for (numLevels = 0; (df % skipInterval) == 0
113: && numLevels < numberOfSkipLevels; df /= skipInterval) {
114: numLevels++;
115: }
116:
117: long childPointer = 0;
118:
119: for (int level = 0; level < numLevels; level++) {
120: writeSkipData(level, skipBuffer[level]);
121:
122: long newChildPointer = skipBuffer[level].getFilePointer();
123:
124: if (level != 0) {
125: // store child pointers for all levels except the lowest
126: skipBuffer[level].writeVLong(childPointer);
127: }
128:
129: //remember the childPointer for the next level
130: childPointer = newChildPointer;
131: }
132: }
133:
134: /**
135: * Writes the buffered skip lists to the given output.
136: *
137: * @param output the IndexOutput the skip lists shall be written to
138: * @return the pointer the skip list starts
139: */
140: long writeSkip(IndexOutput output) throws IOException {
141: long skipPointer = output.getFilePointer();
142: if (skipBuffer == null || skipBuffer.length == 0)
143: return skipPointer;
144:
145: for (int level = numberOfSkipLevels - 1; level > 0; level--) {
146: long length = skipBuffer[level].getFilePointer();
147: if (length > 0) {
148: output.writeVLong(length);
149: skipBuffer[level].writeTo(output);
150: }
151: }
152: skipBuffer[0].writeTo(output);
153:
154: return skipPointer;
155: }
156:
157: }
|