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
MultiLevelSkipListReader.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 BufferedIndexInput = Lucene.Net.Store.BufferedIndexInput;
21 using IndexInput = Lucene.Net.Store.IndexInput;
22 
23 namespace Lucene.Net.Index
24 {
25 
26  /// <summary> This abstract class reads skip lists with multiple levels.
27  ///
28  /// See <see cref="MultiLevelSkipListWriter" /> for the information about the encoding
29  /// of the multi level skip lists.
30  ///
31  /// Subclasses must implement the abstract method <see cref="ReadSkipData(int, IndexInput)" />
32  /// which defines the actual format of the skip data.
33  /// </summary>
34  abstract class MultiLevelSkipListReader : IDisposable
35  {
36  // the maximum number of skip levels possible for this index
37  private readonly int maxNumberOfSkipLevels;
38 
39  // number of levels in this skip list
40  private int numberOfSkipLevels;
41 
42  // Expert: defines the number of top skip levels to buffer in memory.
43  // Reducing this number results in less memory usage, but possibly
44  // slower performance due to more random I/Os.
45  // Please notice that the space each level occupies is limited by
46  // the skipInterval. The top level can not contain more than
47  // skipLevel entries, the second top level can not contain more
48  // than skipLevel^2 entries and so forth.
49  private const int numberOfLevelsToBuffer = 1;
50 
51  private int docCount;
52  private bool haveSkipped;
53 
54  private bool isDisposed;
55 
56  private readonly IndexInput[] skipStream; // skipStream for each level
57  private readonly long[] skipPointer; // the start pointer of each skip level
58  private readonly int[] skipInterval; // skipInterval of each level
59  private readonly int[] numSkipped; // number of docs skipped per level
60 
61  private readonly int[] skipDoc; // doc id of current skip entry per level
62  private int lastDoc; // doc id of last read skip entry with docId <= target
63  private readonly long[] childPointer; // child pointer of current skip entry per level
64  private long lastChildPointer; // childPointer of last read skip entry with docId <= target
65 
66  private readonly bool inputIsBuffered;
67 
68  protected MultiLevelSkipListReader(IndexInput skipStream, int maxSkipLevels, int skipInterval)
69  {
70  this.skipStream = new IndexInput[maxSkipLevels];
71  this.skipPointer = new long[maxSkipLevels];
72  this.childPointer = new long[maxSkipLevels];
73  this.numSkipped = new int[maxSkipLevels];
74  this.maxNumberOfSkipLevels = maxSkipLevels;
75  this.skipInterval = new int[maxSkipLevels];
76  this.skipStream[0] = skipStream;
77  this.inputIsBuffered = (skipStream is BufferedIndexInput);
78  this.skipInterval[0] = skipInterval;
79  for (int i = 1; i < maxSkipLevels; i++)
80  {
81  // cache skip intervals
82  this.skipInterval[i] = this.skipInterval[i - 1] * skipInterval;
83  }
84  skipDoc = new int[maxSkipLevels];
85  }
86 
87 
88  /// <summary>Returns the id of the doc to which the last call of <see cref="SkipTo(int)" />
89  /// has skipped.
90  /// </summary>
91  internal virtual int GetDoc()
92  {
93  return lastDoc;
94  }
95 
96 
97  /// <summary>Skips entries to the first beyond the current whose document number is
98  /// greater than or equal to <i>target</i>. Returns the current doc count.
99  /// </summary>
100  internal virtual int SkipTo(int target)
101  {
102  if (!haveSkipped)
103  {
104  // first time, load skip levels
105  LoadSkipLevels();
106  haveSkipped = true;
107  }
108 
109  // walk up the levels until highest level is found that has a skip
110  // for this target
111  int level = 0;
112  while (level < numberOfSkipLevels - 1 && target > skipDoc[level + 1])
113  {
114  level++;
115  }
116 
117  while (level >= 0)
118  {
119  if (target > skipDoc[level])
120  {
121  if (!LoadNextSkip(level))
122  {
123  continue;
124  }
125  }
126  else
127  {
128  // no more skips on this level, go down one level
129  if (level > 0 && lastChildPointer > skipStream[level - 1].FilePointer)
130  {
131  SeekChild(level - 1);
132  }
133  level--;
134  }
135  }
136 
137  return numSkipped[0] - skipInterval[0] - 1;
138  }
139 
140  private bool LoadNextSkip(int level)
141  {
142  // we have to skip, the target document is greater than the current
143  // skip list entry
144  SetLastSkipData(level);
145 
146  numSkipped[level] += skipInterval[level];
147 
148  if (numSkipped[level] > docCount)
149  {
150  // this skip list is exhausted
151  skipDoc[level] = System.Int32.MaxValue;
152  if (numberOfSkipLevels > level)
153  numberOfSkipLevels = level;
154  return false;
155  }
156 
157  // read next skip entry
158  skipDoc[level] += ReadSkipData(level, skipStream[level]);
159 
160  if (level != 0)
161  {
162  // read the child pointer if we are not on the leaf level
163  childPointer[level] = skipStream[level].ReadVLong() + skipPointer[level - 1];
164  }
165 
166  return true;
167  }
168 
169  /// <summary>Seeks the skip entry on the given level </summary>
170  protected internal virtual void SeekChild(int level)
171  {
172  skipStream[level].Seek(lastChildPointer);
173  numSkipped[level] = numSkipped[level + 1] - skipInterval[level + 1];
174  skipDoc[level] = lastDoc;
175  if (level > 0)
176  {
177  childPointer[level] = skipStream[level].ReadVLong() + skipPointer[level - 1];
178  }
179  }
180 
181  public void Dispose()
182  {
183  Dispose(true);
184  }
185 
186  protected virtual void Dispose(bool disposing)
187  {
188  if (isDisposed) return;
189 
190  if (disposing)
191  {
192  for (int i = 1; i < skipStream.Length; i++)
193  {
194  if (skipStream[i] != null)
195  {
196  skipStream[i].Close();
197  }
198  }
199  }
200 
201  isDisposed = true;
202  }
203 
204  /// <summary>initializes the reader </summary>
205  internal virtual void Init(long skipPointer, int df)
206  {
207  this.skipPointer[0] = skipPointer;
208  this.docCount = df;
209  System.Array.Clear(skipDoc, 0, skipDoc.Length);
210  System.Array.Clear(numSkipped, 0, numSkipped.Length);
211  System.Array.Clear(childPointer, 0, childPointer.Length);
212 
213  haveSkipped = false;
214  for (int i = 1; i < numberOfSkipLevels; i++)
215  {
216  skipStream[i] = null;
217  }
218  }
219 
220  /// <summary>Loads the skip levels </summary>
221  private void LoadSkipLevels()
222  {
223  numberOfSkipLevels = docCount == 0?0:(int) System.Math.Floor(System.Math.Log(docCount) / System.Math.Log(skipInterval[0]));
224  if (numberOfSkipLevels > maxNumberOfSkipLevels)
225  {
226  numberOfSkipLevels = maxNumberOfSkipLevels;
227  }
228 
229  skipStream[0].Seek(skipPointer[0]);
230 
231  int toBuffer = numberOfLevelsToBuffer;
232 
233  for (int i = numberOfSkipLevels - 1; i > 0; i--)
234  {
235  // the length of the current level
236  long length = skipStream[0].ReadVLong();
237 
238  // the start pointer of the current level
239  skipPointer[i] = skipStream[0].FilePointer;
240  if (toBuffer > 0)
241  {
242  // buffer this level
243  skipStream[i] = new SkipBuffer(skipStream[0], (int) length);
244  toBuffer--;
245  }
246  else
247  {
248  // clone this stream, it is already at the start of the current level
249  skipStream[i] = (IndexInput) skipStream[0].Clone();
250  if (inputIsBuffered && length < BufferedIndexInput.BUFFER_SIZE)
251  {
252  ((BufferedIndexInput) skipStream[i]).SetBufferSize((int) length);
253  }
254 
255  // move base stream beyond the current level
256  skipStream[0].Seek(skipStream[0].FilePointer + length);
257  }
258  }
259 
260  // use base stream for the lowest level
261  skipPointer[0] = skipStream[0].FilePointer;
262  }
263 
264  /// <summary> Subclasses must implement the actual skip data encoding in this method.
265  ///
266  /// </summary>
267  /// <param name="level">the level skip data shall be read from
268  /// </param>
269  /// <param name="skipStream">the skip stream to read from
270  /// </param>
271  protected internal abstract int ReadSkipData(int level, IndexInput skipStream);
272 
273  /// <summary>Copies the values of the last read skip entry on this level </summary>
274  protected internal virtual void SetLastSkipData(int level)
275  {
276  lastDoc = skipDoc[level];
277  lastChildPointer = childPointer[level];
278  }
279 
280 
281  /// <summary>used to buffer the top skip levels </summary>
282  private sealed class SkipBuffer : IndexInput
283  {
284  private byte[] data;
285  private readonly long pointer;
286  private int pos;
287 
288  private bool isDisposed;
289 
290  internal SkipBuffer(IndexInput input, int length)
291  {
292  data = new byte[length];
293  pointer = input.FilePointer;
294  input.ReadBytes(data, 0, length);
295  }
296 
297  protected override void Dispose(bool disposing)
298  {
299  if (isDisposed) return;
300  if (disposing)
301  {
302  data = null;
303  }
304 
305  isDisposed = true;
306  }
307 
308  public override long FilePointer
309  {
310  get { return pointer + pos; }
311  }
312 
313  public override long Length()
314  {
315  return data.Length;
316  }
317 
318  public override byte ReadByte()
319  {
320  return data[pos++];
321  }
322 
323  public override void ReadBytes(byte[] b, int offset, int len)
324  {
325  Array.Copy(data, pos, b, offset, len);
326  pos += len;
327  }
328 
329  public override void Seek(long pos)
330  {
331  this.pos = (int) (pos - pointer);
332  }
333 
334  override public System.Object Clone()
335  {
336  System.Diagnostics.Debug.Fail("Port issue:", "Lets see if we need this FilterIndexReader.Clone()"); // {{Aroush-2.9}}
337  return null;
338  }
339  }
340  }
341 }