MultiLevelSkipListReader.cs

Go to the documentation of this file.

/* 
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 * 
 * http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

using System;

using BufferedIndexInput = Lucene.Net.Store.BufferedIndexInput;
using IndexInput = Lucene.Net.Store.IndexInput;

namespace Lucene.Net.Index
{
    
    /// <summary> This abstract class reads skip lists with multiple levels.
    /// 
    /// See <see cref="MultiLevelSkipListWriter" /> for the information about the encoding 
    /// of the multi level skip lists. 
    /// 
    /// Subclasses must implement the abstract method <see cref="ReadSkipData(int, IndexInput)" />
    /// which defines the actual format of the skip data.
    /// </summary>
    abstract class MultiLevelSkipListReader : IDisposable
    {
        // the maximum number of skip levels possible for this index
        private readonly int maxNumberOfSkipLevels;
        
        // number of levels in this skip list
        private int numberOfSkipLevels;
        
        // Expert: defines the number of top skip levels to buffer in memory.
        // Reducing this number results in less memory usage, but possibly
        // slower performance due to more random I/Os.
        // Please notice that the space each level occupies is limited by
        // the skipInterval. The top level can not contain more than
        // skipLevel entries, the second top level can not contain more
        // than skipLevel^2 entries and so forth.
        private const int numberOfLevelsToBuffer = 1;

        private int docCount;
        private bool haveSkipped;

        private bool isDisposed;
        
        private readonly IndexInput[] skipStream; // skipStream for each level
        private readonly long[] skipPointer; // the start pointer of each skip level
        private readonly int[] skipInterval; // skipInterval of each level
        private readonly int[] numSkipped; // number of docs skipped per level
        
        private readonly int[] skipDoc; // doc id of current skip entry per level 
        private int lastDoc; // doc id of last read skip entry with docId <= target
        private readonly long[] childPointer; // child pointer of current skip entry per level
        private long lastChildPointer; // childPointer of last read skip entry with docId <= target
        
        private readonly bool inputIsBuffered;

        protected MultiLevelSkipListReader(IndexInput skipStream, int maxSkipLevels, int skipInterval)
        {
            this.skipStream = new IndexInput[maxSkipLevels];
            this.skipPointer = new long[maxSkipLevels];
            this.childPointer = new long[maxSkipLevels];
            this.numSkipped = new int[maxSkipLevels];
            this.maxNumberOfSkipLevels = maxSkipLevels;
            this.skipInterval = new int[maxSkipLevels];
            this.skipStream[0] = skipStream;
            this.inputIsBuffered = (skipStream is BufferedIndexInput);
            this.skipInterval[0] = skipInterval;
            for (int i = 1; i < maxSkipLevels; i++)
            {
                // cache skip intervals
                this.skipInterval[i] = this.skipInterval[i - 1] * skipInterval;
            }
            skipDoc = new int[maxSkipLevels];
        }
        
        
        /// <summary>Returns the id of the doc to which the last call of <see cref="SkipTo(int)" />
        /// has skipped.  
        /// </summary>
        internal virtual int GetDoc()
        {
            return lastDoc;
        }
        
        
        /// <summary>Skips entries to the first beyond the current whose document number is
        /// greater than or equal to <i>target</i>. Returns the current doc count. 
        /// </summary>
        internal virtual int SkipTo(int target)
        {
            if (!haveSkipped)
            {
                // first time, load skip levels
                LoadSkipLevels();
                haveSkipped = true;
            }
            
            // walk up the levels until highest level is found that has a skip
            // for this target
            int level = 0;
            while (level < numberOfSkipLevels - 1 && target > skipDoc[level + 1])
            {
                level++;
            }
            
            while (level >= 0)
            {
                if (target > skipDoc[level])
                {
                    if (!LoadNextSkip(level))
                    {
                        continue;
                    }
                }
                else
                {
                    // no more skips on this level, go down one level
                    if (level > 0 && lastChildPointer > skipStream[level - 1].FilePointer)
                    {
                        SeekChild(level - 1);
                    }
                    level--;
                }
            }
            
            return numSkipped[0] - skipInterval[0] - 1;
        }
        
        private bool LoadNextSkip(int level)
        {
            // we have to skip, the target document is greater than the current
            // skip list entry        
            SetLastSkipData(level);
            
            numSkipped[level] += skipInterval[level];
            
            if (numSkipped[level] > docCount)
            {
                // this skip list is exhausted
                skipDoc[level] = System.Int32.MaxValue;
                if (numberOfSkipLevels > level)
                    numberOfSkipLevels = level;
                return false;
            }
            
            // read next skip entry
            skipDoc[level] += ReadSkipData(level, skipStream[level]);
            
            if (level != 0)
            {
                // read the child pointer if we are not on the leaf level
                childPointer[level] = skipStream[level].ReadVLong() + skipPointer[level - 1];
            }
            
            return true;
        }
        
        /// <summary>Seeks the skip entry on the given level </summary>
        protected internal virtual void  SeekChild(int level)
        {
            skipStream[level].Seek(lastChildPointer);
            numSkipped[level] = numSkipped[level + 1] - skipInterval[level + 1];
            skipDoc[level] = lastDoc;
            if (level > 0)
            {
                childPointer[level] = skipStream[level].ReadVLong() + skipPointer[level - 1];
            }
        }

        public void Dispose()
        {
            Dispose(true);
        }

        protected virtual void Dispose(bool disposing)
        {
            if (isDisposed) return;

            if (disposing)
            {
                for (int i = 1; i < skipStream.Length; i++)
                {
                    if (skipStream[i] != null)
                    {
                        skipStream[i].Close();
                    }
                }
            }

            isDisposed = true;
        }
        
        /// <summary>initializes the reader </summary>
        internal virtual void  Init(long skipPointer, int df)
        {
            this.skipPointer[0] = skipPointer;
            this.docCount = df;
            System.Array.Clear(skipDoc, 0, skipDoc.Length);
            System.Array.Clear(numSkipped, 0, numSkipped.Length);
            System.Array.Clear(childPointer, 0, childPointer.Length);
            
            haveSkipped = false;
            for (int i = 1; i < numberOfSkipLevels; i++)
            {
                skipStream[i] = null;
            }
        }
        
        /// <summary>Loads the skip levels  </summary>
        private void  LoadSkipLevels()
        {
            numberOfSkipLevels = docCount == 0?0:(int) System.Math.Floor(System.Math.Log(docCount) / System.Math.Log(skipInterval[0]));
            if (numberOfSkipLevels > maxNumberOfSkipLevels)
            {
                numberOfSkipLevels = maxNumberOfSkipLevels;
            }
            
            skipStream[0].Seek(skipPointer[0]);
            
            int toBuffer = numberOfLevelsToBuffer;
            
            for (int i = numberOfSkipLevels - 1; i > 0; i--)
            {
                // the length of the current level
                long length = skipStream[0].ReadVLong();
                
                // the start pointer of the current level
                skipPointer[i] = skipStream[0].FilePointer;
                if (toBuffer > 0)
                {
                    // buffer this level
                    skipStream[i] = new SkipBuffer(skipStream[0], (int) length);
                    toBuffer--;
                }
                else
                {
                    // clone this stream, it is already at the start of the current level
                    skipStream[i] = (IndexInput) skipStream[0].Clone();
                    if (inputIsBuffered && length < BufferedIndexInput.BUFFER_SIZE)
                    {
                        ((BufferedIndexInput) skipStream[i]).SetBufferSize((int) length);
                    }
                    
                    // move base stream beyond the current level
                    skipStream[0].Seek(skipStream[0].FilePointer + length);
                }
            }
            
            // use base stream for the lowest level
            skipPointer[0] = skipStream[0].FilePointer;
        }
        
        /// <summary> Subclasses must implement the actual skip data encoding in this method.
        /// 
        /// </summary>
        /// <param name="level">the level skip data shall be read from
        /// </param>
        /// <param name="skipStream">the skip stream to read from
        /// </param>
        protected internal abstract int ReadSkipData(int level, IndexInput skipStream);
        
        /// <summary>Copies the values of the last read skip entry on this level </summary>
        protected internal virtual void  SetLastSkipData(int level)
        {
            lastDoc = skipDoc[level];
            lastChildPointer = childPointer[level];
        }
        
        
        /// <summary>used to buffer the top skip levels </summary>
        private sealed class SkipBuffer : IndexInput
        {
            private byte[] data;
            private readonly long pointer;
            private int pos;

            private bool isDisposed;
            
            internal SkipBuffer(IndexInput input, int length)
            {
                data = new byte[length];
                pointer = input.FilePointer;
                input.ReadBytes(data, 0, length);
            }

            protected override void Dispose(bool disposing)
            {
                if (isDisposed) return;
                if (disposing)
                {
                    data = null;
                }

                isDisposed = true;
            }

            public override long FilePointer
            {
                get { return pointer + pos; }
            }

            public override long Length()
            {
                return data.Length;
            }
            
            public override byte ReadByte()
            {
                return data[pos++];
            }
            
            public override void  ReadBytes(byte[] b, int offset, int len)
            {
                Array.Copy(data, pos, b, offset, len);
                pos += len;
            }
            
            public override void  Seek(long pos)
            {
                this.pos = (int) (pos - pointer);
            }
            
            override public System.Object Clone()
            {
                System.Diagnostics.Debug.Fail("Port issue:", "Lets see if we need this FilterIndexReader.Clone()"); // {{Aroush-2.9}}
                return null;
            }
        }
    }
}