cassandra-trunk/src/java/org/apache/cassandra/index/sasi/disk/OnDiskBlock.java
/*
 * 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.
 */
package org.apache.cassandra.index.sasi.disk;

import java.nio.ByteBuffer;

import org.apache.cassandra.index.sasi.Term;
import org.apache.cassandra.index.sasi.utils.MappedBuffer;
import org.apache.cassandra.db.marshal.AbstractType;

public abstract class OnDiskBlock<T extends Term>
{
    public enum BlockType
    {
        POINTER, DATA
    }

    // this contains offsets of the terms and term data
    protected final MappedBuffer blockIndex;
    protected final int blockIndexSize;

    protected final boolean hasCombinedIndex;
    protected final TokenTree combinedIndex;

    public OnDiskBlock(Descriptor descriptor, MappedBuffer block, BlockType blockType)
    {
        blockIndex = block;

        if (blockType == BlockType.POINTER)
        {
            hasCombinedIndex = false;
            combinedIndex = null;
            blockIndexSize = block.getInt() << 1; // num terms * sizeof(short)
            return;
        }

        long blockOffset = block.position();
        int combinedIndexOffset = block.getInt(blockOffset + OnDiskIndexBuilder.BLOCK_SIZE);

        hasCombinedIndex = (combinedIndexOffset >= 0);
        long blockIndexOffset = blockOffset + OnDiskIndexBuilder.BLOCK_SIZE + 4 + combinedIndexOffset;

        combinedIndex = hasCombinedIndex ? new TokenTree(descriptor, blockIndex.duplicate().position(blockIndexOffset)) : null;
        blockIndexSize = block.getInt() * 2;
    }

    public SearchResult<T> search(AbstractType<?> comparator, ByteBuffer query)
    {
        int cmp = -1, start = 0, end = termCount() - 1, middle = 0;

        T element = null;
        while (start <= end)
        {
            middle = start + ((end - start) >> 1);
            element = getTerm(middle);

            cmp = element.compareTo(comparator, query);
            if (cmp == 0)
                return new SearchResult<>(element, cmp, middle);
            else if (cmp < 0)
                start = middle + 1;
            else
                end = middle - 1;
        }

        return new SearchResult<>(element, cmp, middle);
    }

    @SuppressWarnings("resource")
    protected T getTerm(int index)
    {
        MappedBuffer dup = blockIndex.duplicate();
        long startsAt = getTermPosition(index);
        if (termCount() - 1 == index) // last element
            dup.position(startsAt);
        else
            dup.position(startsAt).limit(getTermPosition(index + 1));

        return cast(dup);
    }

    protected long getTermPosition(int idx)
    {
        return getTermPosition(blockIndex, idx, blockIndexSize);
    }

    protected int termCount()
    {
        return blockIndexSize >> 1;
    }

    protected abstract T cast(MappedBuffer data);

    static long getTermPosition(MappedBuffer data, int idx, int indexSize)
    {
        idx <<= 1;
        assert idx < indexSize;
        return data.position() + indexSize + data.getShort(data.position() + idx);
    }

    public TokenTree getBlockIndex()
    {
        return combinedIndex;
    }

    public int minOffset(OnDiskIndex.IteratorOrder order)
    {
        return order == OnDiskIndex.IteratorOrder.DESC ? 0 : termCount() - 1;
    }

    public int maxOffset(OnDiskIndex.IteratorOrder order)
    {
        return minOffset(order) == 0 ? termCount() - 1 : 0;
    }

    public static class SearchResult<T>
    {
        public final T result;
        public final int index, cmp;

        public SearchResult(T result, int cmp, int index)
        {
            this.result = result;
            this.index = index;
            this.cmp = cmp;
        }
    }
}
