mavibot/src/main/java/org/apache/directory/mavibot/btree/BTree.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.directory.mavibot.btree;


import java.io.IOException;
import java.util.Comparator;

import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
import org.apache.directory.mavibot.btree.serializer.ElementSerializer;


/**
 * A B-tree interface, to be implemented by the PersistedBTree or the InMemoryBTree
 *
 * @param <K> The Key type
 * @param <V> The Value type
 *
 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
 */
public interface BTree<K, V>
{
    /** Default page size (number of entries per node) */
    static final int DEFAULT_PAGE_SIZE = 16;

    /** Default size of the buffer used to write data on disk. Around 1Mb */
    static final int DEFAULT_WRITE_BUFFER_SIZE = 4096 * 250;

    /** Define a default delay for a read transaction. This is 10 seconds */
    static final long DEFAULT_READ_TIMEOUT = 10 * 1000L;

    /** The B-tree allows duplicate values */
    static final boolean ALLOW_DUPLICATES = true;

    /** The B-tree forbids duplicate values */
    static final boolean FORBID_DUPLICATES = false;


    /**
     * Close the B-tree, cleaning up all the data structure
     */
    void close() throws IOException;


    /**
     * Set the maximum number of elements we can store in a page. This must be a
     * number greater than 1, and a power of 2. The default page size is 16.
     * <br/>
     * If the provided size is below 2, we will default to DEFAULT_PAGE_SIZE.<br/>
     * If the provided size is not a power of 2, we will select the closest power of 2
     * higher than the given number<br/>
     *
     * @param pageSize The requested page size
     */
    void setPageSize( int pageSize );


    /**
     * @return the number of elements per page
     */
    int getPageSize();


    /**
     * Insert an entry in the B-tree.
     * <p>
     * We will replace the value if the provided key already exists in the
     * B-tree.
     *
     * @param key Inserted key
     * @param value Inserted value
     * @return Existing value, if any.
     * @throws IOException TODO
     */
    V insert( K key, V value ) throws IOException;


    /**
     * Delete the entry which key is given as a parameter. If the entry exists, it will
     * be removed from the tree, the old tuple will be returned. Otherwise, null is returned.
     *
     * @param key The key for the entry we try to remove
     * @return A Tuple<K, V> containing the removed entry, or null if it's not found.
     */
    Tuple<K, V> delete( K key ) throws IOException;


    /**
     * Delete the value from an entry associated with the given key. If the value
     * If the value is present, it will be deleted first, later if there are no other
     * values associated with this key(which can happen when duplicates are enabled),
     * we will remove the key from the tree.
     *
     * @param key The key for the entry we try to remove
     * @param value The value to delete (can be null)
     * @return A Tuple<K, V> containing the removed entry, or null if it's not found.
     */
    Tuple<K, V> delete( K key, V value ) throws IOException;


    /**
     * Find a value in the tree, given its key. If the key is not found,
     * it will throw a KeyNotFoundException. <br/>
     * Note that we can get a null value stored, or many values.
     *
     * @param key The key we are looking at
     * @return The found value, or null if the key is not present in the tree
     * @throws KeyNotFoundException If the key is not found in the B-tree
     * @throws IOException TODO
     */
    V get( K key ) throws IOException, KeyNotFoundException;


    /**
     * Get the rootPage associated to a given revision.
     *
     * @param revision The revision we are looking for
     * @return The rootPage associated to this revision
     * @throws IOException If we had an issue while accessing the underlying file
     * @throws KeyNotFoundException If the revision does not exist for this B-tree
     */
    Page<K, V> getRootPage( long revision ) throws IOException, KeyNotFoundException;


    /**
     * Get the current rootPage
     *
     * @return The current rootPage
     */
    Page<K, V> getRootPage();


    /**
     * @see Page#getValues(Object)
     */
    ValueCursor<V> getValues( K key ) throws IOException, KeyNotFoundException;


    /**
     * Find a value in the tree, given its key, at a specific revision. If the key is not found,
     * it will throw a KeyNotFoundException. <br/>
     * Note that we can get a null value stored, or many values.
     *
     * @param revision The revision for which we want to find a key
     * @param key The key we are looking at
     * @return The found value, or null if the key is not present in the tree
     * @throws KeyNotFoundException If the key is not found in the B-tree
     * @throws IOException If there was an issue while fetching data from the disk
     */
    V get( long revision, K key ) throws IOException, KeyNotFoundException;


    /**
     * Checks if the given key exists.
     *
     * @param key The key we are looking at
     * @return true if the key is present, false otherwise
     * @throws IOException If we have an error while trying to access the page
     * @throws KeyNotFoundException If the key is not found in the B-tree
     */
    boolean hasKey( K key ) throws IOException, KeyNotFoundException;


    /**
     * Checks if the given key exists for a given revision.
     *
     * @param revision The revision for which we want to find a key
     * @param key The key we are looking at
     * @return true if the key is present, false otherwise
     * @throws IOException If we have an error while trying to access the page
     * @throws KeyNotFoundException If the key is not found in the B-tree
     */
    boolean hasKey( long revision, K key ) throws IOException, KeyNotFoundException;


    /**
     * Checks if the B-tree contains the given key with the given value.
     *
     * @param key The key we are looking for
     * @param value The value associated with the given key
     * @return true if the key and value are associated with each other, false otherwise
     */
    boolean contains( K key, V value ) throws IOException;


    /**
     * Checks if the B-tree contains the given key with the given value for a given revision
     *
     * @param revision The revision we would like to browse
     * @param key The key we are looking for
     * @param value The value associated with the given key
     * @return true if the key and value are associated with each other, false otherwise
     * @throws KeyNotFoundException If the key is not found in the B-tree
     */
    boolean contains( long revision, K key, V value ) throws IOException, KeyNotFoundException;


    /**
     * Creates a cursor starting at the beginning of the tree
     *
     * @return A cursor on the B-tree
     * @throws IOException
     */
    TupleCursor<K, V> browse() throws IOException, KeyNotFoundException;


    /**
     * Creates a cursor starting at the beginning of the tree, for a given revision
     *
     * @param revision The revision we would like to browse
     * @return A cursor on the B-tree
     * @throws IOException If we had an issue while fetching data from the disk
     * @throws KeyNotFoundException If the key is not found in the B-tree
     */
    TupleCursor<K, V> browse( long revision ) throws IOException, KeyNotFoundException;


    /**
     * Creates a cursor starting on the given key
     *
     * @param key The key which is the starting point. If the key is not found,
     * then the cursor will always return null.
     * @return A cursor on the B-tree
     * @throws IOException
     */
    TupleCursor<K, V> browseFrom( K key ) throws IOException;


    /**
     * Creates a cursor starting on the given key at the given revision
     *
     * @param The revision we are looking for
     * @param key The key which is the starting point. If the key is not found,
     * then the cursor will always return null.
     * @return A cursor on the B-tree
     * @throws IOException If wxe had an issue reading the B-tree from disk
     * @throws KeyNotFoundException  If we can't find a rootPage for this revision
     */
    TupleCursor<K, V> browseFrom( long revision, K key ) throws IOException, KeyNotFoundException;


    /**
     * Creates a cursor starting at the beginning of the tree
     *
     * @return A cursor on the B-tree keys
     * @throws IOException
     */
    KeyCursor<K> browseKeys() throws IOException, KeyNotFoundException;


    /**
     * @return the key comparator
     */
    Comparator<K> getKeyComparator();


    /**
     * @return the value comparator
     */
    Comparator<V> getValueComparator();


    /**
     * @param keySerializer the Key serializer to set
     */
    void setKeySerializer( ElementSerializer<K> keySerializer );


    /**
     * @param valueSerializer the Value serializer to set
     */
    void setValueSerializer( ElementSerializer<V> valueSerializer );


    /**
     * Flush the latest revision to disk. We will replace the current file by the new one, as
     * we flush in a temporary file.
     */
    void flush() throws IOException;


    /**
     * @return the readTimeOut
     */
    long getReadTimeOut();


    /**
     * @param readTimeOut the readTimeOut to set
     */
    void setReadTimeOut( long readTimeOut );


    /**
     * @return the name
     */
    String getName();


    /**
     * @param name the name to set
     */
    void setName( String name );


    /**
     * @return the writeBufferSize
     */
    int getWriteBufferSize();


    /**
     * @param writeBufferSize the writeBufferSize to set
     */
    void setWriteBufferSize( int writeBufferSize );


    /**
     * @return the keySerializer
     */
    ElementSerializer<K> getKeySerializer();


    /**
     * @return the keySerializer FQCN
     */
    String getKeySerializerFQCN();


    /**
     * @return the valueSerializer
     */
    ElementSerializer<V> getValueSerializer();


    /**
     * @return the valueSerializer FQCN
     */
    String getValueSerializerFQCN();


    /**
     * @return The current B-tree revision
     */
    long getRevision();


    /**
     * @return The current number of elements in the B-tree
     */
    long getNbElems();


    /**
     * @return true if this B-tree allow duplicate values
     */
    boolean isAllowDuplicates();


    /**
     * @param allowDuplicates True if the B-tree will allow duplicate values
     */
    void setAllowDuplicates( boolean allowDuplicates );


    /**
     * @return the type
     */
    BTreeTypeEnum getType();
}