Lucene.Net  3.0.3
Lucene.Net is a port of the Lucene search engine library, written in C# and targeted at .NET runtime users.
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Properties Pages
MultiLevelSkipListWriter.cs
Go to the documentation of this file.
1 /*
2  * Licensed to the Apache Software Foundation (ASF) under one or more
3  * contributor license agreements. See the NOTICE file distributed with
4  * this work for additional information regarding copyright ownership.
5  * The ASF licenses this file to You under the Apache License, Version 2.0
6  * (the "License"); you may not use this file except in compliance with
7  * the License. You may obtain a copy of the License at
8  *
9  * http://www.apache.org/licenses/LICENSE-2.0
10  *
11  * Unless required by applicable law or agreed to in writing, software
12  * distributed under the License is distributed on an "AS IS" BASIS,
13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  * See the License for the specific language governing permissions and
15  * limitations under the License.
16  */
17 
18 using System;
19 
20 using IndexOutput = Lucene.Net.Store.IndexOutput;
21 using RAMOutputStream = Lucene.Net.Store.RAMOutputStream;
22 
23 namespace Lucene.Net.Index
24 {
25 
26  /// <summary> This abstract class writes skip lists with multiple levels.
27  ///
28  /// Example for skipInterval = 3:
29  /// c (skip level 2)
30  /// c c c (skip level 1)
31  /// x x x x x x x x x x (skip level 0)
32  /// 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)
33  /// 3 6 9 12 15 18 21 24 27 30 (df)
34  ///
35  /// d - document
36  /// x - skip data
37  /// c - skip data with child pointer
38  ///
39  /// Skip level i contains every skipInterval-th entry from skip level i-1.
40  /// Therefore the number of entries on level i is: floor(df / ((skipInterval ^ (i + 1))).
41  ///
42  /// Each skip entry on a level i>0 contains a pointer to the corresponding skip entry in list i-1.
43  /// This guarantess a logarithmic amount of skips to find the target document.
44  ///
45  /// While this class takes care of writing the different skip levels,
46  /// subclasses must define the actual format of the skip data.
47  ///
48  /// </summary>
49  abstract class MultiLevelSkipListWriter
50  {
51  // number of levels in this skip list
52  private int numberOfSkipLevels;
53 
54  // the skip interval in the list with level = 0
55  private int skipInterval;
56 
57  // for every skip level a different buffer is used
58  private RAMOutputStream[] skipBuffer;
59 
60  protected internal MultiLevelSkipListWriter(int skipInterval, int maxSkipLevels, int df)
61  {
62  this.skipInterval = skipInterval;
63 
64  // calculate the maximum number of skip levels for this document frequency
65  numberOfSkipLevels = df == 0?0:(int) System.Math.Floor(System.Math.Log(df) / System.Math.Log(skipInterval));
66 
67  // make sure it does not exceed maxSkipLevels
68  if (numberOfSkipLevels > maxSkipLevels)
69  {
70  numberOfSkipLevels = maxSkipLevels;
71  }
72  }
73 
74  protected internal virtual void Init()
75  {
76  skipBuffer = new RAMOutputStream[numberOfSkipLevels];
77  for (int i = 0; i < numberOfSkipLevels; i++)
78  {
79  skipBuffer[i] = new RAMOutputStream();
80  }
81  }
82 
83  protected internal virtual void ResetSkip()
84  {
85  // creates new buffers or empties the existing ones
86  if (skipBuffer == null)
87  {
88  Init();
89  }
90  else
91  {
92  for (int i = 0; i < skipBuffer.Length; i++)
93  {
94  skipBuffer[i].Reset();
95  }
96  }
97  }
98 
99  /// <summary> Subclasses must implement the actual skip data encoding in this method.
100  ///
101  /// </summary>
102  /// <param name="level">the level skip data shall be writting for
103  /// </param>
104  /// <param name="skipBuffer">the skip buffer to write to
105  /// </param>
106  protected internal abstract void WriteSkipData(int level, IndexOutput skipBuffer);
107 
108  /// <summary> Writes the current skip data to the buffers. The current document frequency determines
109  /// the max level is skip data is to be written to.
110  ///
111  /// </summary>
112  /// <param name="df">the current document frequency
113  /// </param>
114  /// <throws> IOException </throws>
115  internal virtual void BufferSkip(int df)
116  {
117  int numLevels;
118 
119  // determine max level
120  for (numLevels = 0; (df % skipInterval) == 0 && numLevels < numberOfSkipLevels; df /= skipInterval)
121  {
122  numLevels++;
123  }
124 
125  long childPointer = 0;
126 
127  for (int level = 0; level < numLevels; level++)
128  {
129  WriteSkipData(level, skipBuffer[level]);
130 
131  long newChildPointer = skipBuffer[level].FilePointer;
132 
133  if (level != 0)
134  {
135  // store child pointers for all levels except the lowest
136  skipBuffer[level].WriteVLong(childPointer);
137  }
138 
139  //remember the childPointer for the next level
140  childPointer = newChildPointer;
141  }
142  }
143 
144  /// <summary> Writes the buffered skip lists to the given output.
145  ///
146  /// </summary>
147  /// <param name="output">the IndexOutput the skip lists shall be written to
148  /// </param>
149  /// <returns> the pointer the skip list starts
150  /// </returns>
151  internal virtual long WriteSkip(IndexOutput output)
152  {
153  long skipPointer = output.FilePointer;
154  if (skipBuffer == null || skipBuffer.Length == 0)
155  return skipPointer;
156 
157  for (int level = numberOfSkipLevels - 1; level > 0; level--)
158  {
159  long length = skipBuffer[level].FilePointer;
160  if (length > 0)
161  {
162  output.WriteVLong(length);
163  skipBuffer[level].WriteTo(output);
164  }
165  }
166  skipBuffer[0].WriteTo(output);
167 
168  return skipPointer;
169  }
170  }
171 }