mcs/tools/monkeydoc/Lucene.Net/Lucene.Net/Index/MultiLevelSkipListReader.cs

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