Package org.apache.lucene.codecs

Class MultiLevelSkipListWriter

java.lang.Object

org.apache.lucene.codecs.MultiLevelSkipListWriter

Direct Known Subclasses:

Lucene99SkipWriter

public abstract class MultiLevelSkipListWriter
extends Object

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.
 

WARNING: This API is experimental and might change in incompatible ways in the next release.

Field Summary

Fields

Modifier and Type	Field	Description
protected int	numberOfSkipLevels	number of levels in this skip list

Constructor Summary

Constructors

Modifier	Constructor	Description
protected	MultiLevelSkipListWriter(int skipInterval, int maxSkipLevels, int df)	Creates a MultiLevelSkipListWriter, where skipInterval and skipMultiplier are the same.
protected	MultiLevelSkipListWriter(int skipInterval, int skipMultiplier, int maxSkipLevels, int df)	Creates a MultiLevelSkipListWriter.

Method Summary

Modifier and Type	Method	Description
void	bufferSkip(int df)	Writes the current skip data to the buffers.
protected void	init()	Allocates internal skip buffers.
protected void	resetSkip()	Creates new buffers or empties the existing ones
protected void	writeChildPointer(long childPointer, DataOutput skipBuffer)	Writes the child pointer of a block to the given output.
protected void	writeLevelLength(long levelLength, IndexOutput output)	Writes the length of a level to the given output.
long	writeSkip(IndexOutput output)	Writes the buffered skip lists to the given output.
protected abstract void	writeSkipData(int level, DataOutput skipBuffer)	Subclasses must implement the actual skip data encoding in this method.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

numberOfSkipLevels

protected final int numberOfSkipLevels

number of levels in this skip list

Constructor Detail

MultiLevelSkipListWriter

protected MultiLevelSkipListWriter(int skipInterval,
                                   int skipMultiplier,
                                   int maxSkipLevels,
                                   int df)

Creates a MultiLevelSkipListWriter.

MultiLevelSkipListWriter

protected MultiLevelSkipListWriter(int skipInterval,
                                   int maxSkipLevels,
                                   int df)

Creates a MultiLevelSkipListWriter, where skipInterval and skipMultiplier are the same.

Method Detail

init

protected void init()

Allocates internal skip buffers.

resetSkip

protected void resetSkip()

Creates new buffers or empties the existing ones

writeSkipData

protected abstract void writeSkipData(int level,
                                      DataOutput skipBuffer)
                               throws IOException

Subclasses must implement the actual skip data encoding in this method.

Parameters:

level - the level skip data shall be writing for

skipBuffer - the skip buffer to write to

Throws:

IOException

bufferSkip

public void bufferSkip(int df)
                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.

Parameters:

df - the current document frequency

Throws:

IOException - If an I/O error occurs

writeSkip

public long writeSkip(IndexOutput output)
               throws IOException

Writes the buffered skip lists to the given output.

Parameters:

output - the IndexOutput the skip lists shall be written to

Returns:

the pointer the skip list starts

Throws:

IOException

writeLevelLength

protected void writeLevelLength(long levelLength,
                                IndexOutput output)
                         throws IOException

Writes the length of a level to the given output.

Parameters:

levelLength - the length of a level

output - the IndexOutput the length shall be written to

Throws:

IOException

writeChildPointer

protected void writeChildPointer(long childPointer,
                                 DataOutput skipBuffer)
                          throws IOException

Writes the child pointer of a block to the given output.

Parameters:

childPointer - block of higher level point to the lower level

skipBuffer - the skip buffer to write to

Throws:

IOException