src/java/org/apache/cassandra/index/sasi/conf/view/PrefixTermTree.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.conf.view;

import java.nio.ByteBuffer;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

import org.apache.cassandra.index.sasi.SSTableIndex;
import org.apache.cassandra.index.sasi.disk.OnDiskIndexBuilder;
import org.apache.cassandra.index.sasi.plan.Expression;
import org.apache.cassandra.index.sasi.utils.trie.KeyAnalyzer;
import org.apache.cassandra.index.sasi.utils.trie.PatriciaTrie;
import org.apache.cassandra.index.sasi.utils.trie.Trie;
import org.apache.cassandra.db.marshal.AbstractType;
import org.apache.cassandra.utils.Interval;
import org.apache.cassandra.utils.IntervalTree;

import com.google.common.collect.Sets;

/**
 * This class is an extension over RangeTermTree for string terms,
 * it is required because interval tree can't handle matching if search is on the
 * prefix of min/max of the range, so for ascii/utf8 fields we build an additional
 * prefix trie (including both min/max terms of the index) and do union of the results
 * of the prefix tree search and results from the interval tree lookup.
 */
public class PrefixTermTree extends RangeTermTree
{
    private final OnDiskIndexBuilder.Mode mode;
    private final Trie<ByteBuffer, Set<SSTableIndex>> trie;

    public PrefixTermTree(ByteBuffer min, ByteBuffer max,
                          Trie<ByteBuffer, Set<SSTableIndex>> trie,
                          IntervalTree<Term, SSTableIndex, Interval<Term, SSTableIndex>> ranges,
                          OnDiskIndexBuilder.Mode mode,
                          AbstractType<?> comparator)
    {
        super(min, max, ranges, comparator);

        this.mode = mode;
        this.trie = trie;
    }

    public Set<SSTableIndex> search(Expression e)
    {
        Map<ByteBuffer, Set<SSTableIndex>> indexes = (e == null || e.lower == null || mode == OnDiskIndexBuilder.Mode.CONTAINS)
                                                        ? trie : trie.prefixMap(e.lower.value);

        Set<SSTableIndex> view = new HashSet<>(indexes.size());
        indexes.values().forEach(view::addAll);
        return Sets.union(view, super.search(e));
    }

    public static class Builder extends RangeTermTree.Builder
    {
        private final PatriciaTrie<ByteBuffer, Set<SSTableIndex>> trie;

        protected Builder(OnDiskIndexBuilder.Mode mode, final AbstractType<?> comparator)
        {
            super(mode, comparator);
            trie = new PatriciaTrie<>(new ByteBufferKeyAnalyzer(comparator));

        }

        public void addIndex(SSTableIndex index)
        {
            super.addIndex(index);
            addTerm(index.minTerm(), index);
            addTerm(index.maxTerm(), index);
        }

        public TermTree build()
        {
            return new PrefixTermTree(min, max, trie, IntervalTree.build(intervals), mode, comparator);
        }

        private void addTerm(ByteBuffer term, SSTableIndex index)
        {
            Set<SSTableIndex> indexes = trie.get(term);
            if (indexes == null)
                trie.put(term, (indexes = new HashSet<>()));

            indexes.add(index);
        }
    }

    private static class ByteBufferKeyAnalyzer implements KeyAnalyzer<ByteBuffer>
    {
        private final AbstractType<?> comparator;

        public ByteBufferKeyAnalyzer(AbstractType<?> comparator)
        {
            this.comparator = comparator;
        }

        /**
         * A bit mask where the first bit is 1 and the others are zero
         */
        private static final int MSB = 1 << Byte.SIZE-1;

        public int compare(ByteBuffer a, ByteBuffer b)
        {
            return comparator.compare(a, b);
        }

        public int lengthInBits(ByteBuffer o)
        {
            return o.remaining() * Byte.SIZE;
        }

        public boolean isBitSet(ByteBuffer key, int bitIndex)
        {
            if (bitIndex >= lengthInBits(key))
                return false;

            int index = bitIndex / Byte.SIZE;
            int bit = bitIndex % Byte.SIZE;
            return (key.get(index) & mask(bit)) != 0;
        }

        public int bitIndex(ByteBuffer key, ByteBuffer otherKey)
        {
            int length = Math.max(key.remaining(), otherKey.remaining());

            boolean allNull = true;
            for (int i = 0; i < length; i++)
            {
                byte b1 = valueAt(key, i);
                byte b2 = valueAt(otherKey, i);

                if (b1 != b2)
                {
                    int xor = b1 ^ b2;
                    for (int j = 0; j < Byte.SIZE; j++)
                    {
                        if ((xor & mask(j)) != 0)
                            return (i * Byte.SIZE) + j;
                    }
                }

                if (b1 != 0)
                    allNull = false;
            }

            return allNull ? KeyAnalyzer.NULL_BIT_KEY : KeyAnalyzer.EQUAL_BIT_KEY;
        }

        public boolean isPrefix(ByteBuffer key, ByteBuffer prefix)
        {
            if (key.remaining() < prefix.remaining())
                return false;

            for (int i = 0; i < prefix.remaining(); i++)
            {
                if (key.get(i) != prefix.get(i))
                    return false;
            }

            return true;
        }

        /**
         * Returns the {@code byte} value at the given index.
         */
        private byte valueAt(ByteBuffer value, int index)
        {
            return index >= 0 && index < value.remaining() ? value.get(index) : 0;
        }

        /**
         * Returns a bit mask where the given bit is set
         */
        private int mask(int bit)
        {
            return MSB >>> bit;
        }
    }
}