001/*
002 *  Licensed to the Apache Software Foundation (ASF) under one
003 *  or more contributor license agreements.  See the NOTICE file
004 *  distributed with this work for additional information
005 *  regarding copyright ownership.  The ASF licenses this file
006 *  to you under the Apache License, Version 2.0 (the
007 *  "License"); you may not use this file except in compliance
008 *  with the License.  You may obtain a copy of the License at
009 *
010 *    http://www.apache.org/licenses/LICENSE-2.0
011 *
012 *  Unless required by applicable law or agreed to in writing,
013 *  software distributed under the License is distributed on an
014 *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
015 *  KIND, either express or implied.  See the License for the
016 *  specific language governing permissions and limitations
017 *  under the License.
018 *
019 */
020package org.apache.directory.mavibot.btree;
021
022
023import java.io.IOException;
024import java.util.Comparator;
025
026import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
027import org.apache.directory.mavibot.btree.serializer.ElementSerializer;
028
029
030/**
031 * A B-tree interface, to be implemented by the PersistedBTree or the InMemoryBTree
032 *
033 * @param <K> The Key type
034 * @param <V> The Value type
035 *
036 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
037 */
038public interface BTree<K, V>
039{
040    /** Default page size (number of entries per node) */
041    int DEFAULT_PAGE_SIZE = 16;
042
043    /** Default size of the buffer used to write data on disk. Around 1Mb */
044    int DEFAULT_WRITE_BUFFER_SIZE = 4096 * 250;
045
046    /** Define a default delay for a read transaction. This is 10 seconds */
047    long DEFAULT_READ_TIMEOUT = 10 * 1000L;
048
049    /** The B-tree allows duplicate values */
050    boolean ALLOW_DUPLICATES = true;
051
052    /** The B-tree forbids duplicate values */
053    boolean FORBID_DUPLICATES = false;
054
055
056    /**
057     * Close the B-tree, cleaning up all the data structure
058     */
059    void close() throws IOException;
060
061
062    /**
063     * Set the maximum number of elements we can store in a page. This must be a
064     * number greater than 1, and a power of 2. The default page size is 16.
065     * <br/>
066     * If the provided size is below 2, we will default to DEFAULT_PAGE_SIZE.<br/>
067     * If the provided size is not a power of 2, we will select the closest power of 2
068     * higher than the given number<br/>
069     *
070     * @param pageSize The requested page size
071     */
072    void setPageSize( int pageSize );
073
074
075    /**
076     * @return the number of elements per page
077     */
078    int getPageSize();
079
080
081    /**
082     * Insert an entry in the B-tree.
083     * <p>
084     * We will replace the value if the provided key already exists in the
085     * B-tree.
086     *
087     * @param key Inserted key
088     * @param value Inserted value
089     * @return Existing value, if any.
090     * @throws IOException TODO
091     */
092    V insert( K key, V value ) throws IOException;
093
094
095    /**
096     * Delete the entry which key is given as a parameter. If the entry exists, it will
097     * be removed from the tree, the old tuple will be returned. Otherwise, null is returned.
098     *
099     * @param key The key for the entry we try to remove
100     * @return A Tuple<K, V> containing the removed entry, or null if it's not found.
101     */
102    Tuple<K, V> delete( K key ) throws IOException;
103
104
105    /**
106     * Delete the value from an entry associated with the given key. If the value
107     * If the value is present, it will be deleted first, later if there are no other
108     * values associated with this key(which can happen when duplicates are enabled),
109     * we will remove the key from the tree.
110     *
111     * @param key The key for the entry we try to remove
112     * @param value The value to delete (can be null)
113     * @return A Tuple<K, V> containing the removed entry, or null if it's not found.
114     */
115    Tuple<K, V> delete( K key, V value ) throws IOException;
116
117
118    /**
119     * Find a value in the tree, given its key. If the key is not found,
120     * it will throw a KeyNotFoundException. <br/>
121     * Note that we can get a null value stored, or many values.
122     *
123     * @param key The key we are looking at
124     * @return The found value, or null if the key is not present in the tree
125     * @throws KeyNotFoundException If the key is not found in the B-tree
126     * @throws IOException TODO
127     */
128    V get( K key ) throws IOException, KeyNotFoundException;
129
130
131    /**
132     * Get the rootPage associated to a given revision.
133     *
134     * @param revision The revision we are looking for
135     * @return The rootPage associated to this revision
136     * @throws IOException If we had an issue while accessing the underlying file
137     * @throws KeyNotFoundException If the revision does not exist for this B-tree
138     */
139    Page<K, V> getRootPage( long revision ) throws IOException, KeyNotFoundException;
140
141
142    /**
143     * Get the current rootPage
144     *
145     * @return The current rootPage
146     */
147    Page<K, V> getRootPage();
148
149
150    /**
151     * @see Page#getValues(Object)
152     */
153    ValueCursor<V> getValues( K key ) throws IOException, KeyNotFoundException;
154
155
156    /**
157     * Find a value in the tree, given its key, at a specific revision. If the key is not found,
158     * it will throw a KeyNotFoundException. <br/>
159     * Note that we can get a null value stored, or many values.
160     *
161     * @param revision The revision for which we want to find a key
162     * @param key The key we are looking at
163     * @return The found value, or null if the key is not present in the tree
164     * @throws KeyNotFoundException If the key is not found in the B-tree
165     * @throws IOException If there was an issue while fetching data from the disk
166     */
167    V get( long revision, K key ) throws IOException, KeyNotFoundException;
168
169
170    /**
171     * Checks if the given key exists.
172     *
173     * @param key The key we are looking at
174     * @return true if the key is present, false otherwise
175     * @throws IOException If we have an error while trying to access the page
176     * @throws KeyNotFoundException If the key is not found in the B-tree
177     */
178    boolean hasKey( K key ) throws IOException, KeyNotFoundException;
179
180
181    /**
182     * Checks if the given key exists for a given revision.
183     *
184     * @param revision The revision for which we want to find a key
185     * @param key The key we are looking at
186     * @return true if the key is present, false otherwise
187     * @throws IOException If we have an error while trying to access the page
188     * @throws KeyNotFoundException If the key is not found in the B-tree
189     */
190    boolean hasKey( long revision, K key ) throws IOException, KeyNotFoundException;
191
192
193    /**
194     * Checks if the B-tree contains the given key with the given value.
195     *
196     * @param key The key we are looking for
197     * @param value The value associated with the given key
198     * @return true if the key and value are associated with each other, false otherwise
199     */
200    boolean contains( K key, V value ) throws IOException;
201
202
203    /**
204     * Checks if the B-tree contains the given key with the given value for a given revision
205     *
206     * @param revision The revision we would like to browse
207     * @param key The key we are looking for
208     * @param value The value associated with the given key
209     * @return true if the key and value are associated with each other, false otherwise
210     * @throws KeyNotFoundException If the key is not found in the B-tree
211     */
212    boolean contains( long revision, K key, V value ) throws IOException, KeyNotFoundException;
213
214
215    /**
216     * Creates a cursor starting at the beginning of the tree
217     *
218     * @return A cursor on the B-tree
219     * @throws IOException
220     */
221    TupleCursor<K, V> browse() throws IOException, KeyNotFoundException;
222
223
224    /**
225     * Creates a cursor starting at the beginning of the tree, for a given revision
226     *
227     * @param revision The revision we would like to browse
228     * @return A cursor on the B-tree
229     * @throws IOException If we had an issue while fetching data from the disk
230     * @throws KeyNotFoundException If the key is not found in the B-tree
231     */
232    TupleCursor<K, V> browse( long revision ) throws IOException, KeyNotFoundException;
233
234
235    /**
236     * Creates a cursor starting on the given key
237     *
238     * @param key The key which is the starting point. If the key is not found,
239     * then the cursor will always return null.
240     * @return A cursor on the B-tree
241     * @throws IOException
242     */
243    TupleCursor<K, V> browseFrom( K key ) throws IOException;
244
245
246    /**
247     * Creates a cursor starting on the given key at the given revision
248     *
249     * @param The revision we are looking for
250     * @param key The key which is the starting point. If the key is not found,
251     * then the cursor will always return null.
252     * @return A cursor on the B-tree
253     * @throws IOException If wxe had an issue reading the B-tree from disk
254     * @throws KeyNotFoundException  If we can't find a rootPage for this revision
255     */
256    TupleCursor<K, V> browseFrom( long revision, K key ) throws IOException, KeyNotFoundException;
257
258
259    /**
260     * Creates a cursor starting at the beginning of the tree
261     *
262     * @return A cursor on the B-tree keys
263     * @throws IOException
264     */
265    KeyCursor<K> browseKeys() throws IOException, KeyNotFoundException;
266
267
268    /**
269     * @return the key comparator
270     */
271    Comparator<K> getKeyComparator();
272
273
274    /**
275     * @return the value comparator
276     */
277    Comparator<V> getValueComparator();
278
279
280    /**
281     * @param keySerializer the Key serializer to set
282     */
283    void setKeySerializer( ElementSerializer<K> keySerializer );
284
285
286    /**
287     * @param valueSerializer the Value serializer to set
288     */
289    void setValueSerializer( ElementSerializer<V> valueSerializer );
290
291
292    /**
293     * Flush the latest revision to disk. We will replace the current file by the new one, as
294     * we flush in a temporary file.
295     */
296    void flush() throws IOException;
297
298
299    /**
300     * @return the readTimeOut
301     */
302    long getReadTimeOut();
303
304
305    /**
306     * @param readTimeOut the readTimeOut to set
307     */
308    void setReadTimeOut( long readTimeOut );
309
310
311    /**
312     * @return the name
313     */
314    String getName();
315
316
317    /**
318     * @param name the name to set
319     */
320    void setName( String name );
321
322
323    /**
324     * @return the writeBufferSize
325     */
326    int getWriteBufferSize();
327
328
329    /**
330     * @param writeBufferSize the writeBufferSize to set
331     */
332    void setWriteBufferSize( int writeBufferSize );
333
334
335    /**
336     * @return the keySerializer
337     */
338    ElementSerializer<K> getKeySerializer();
339
340
341    /**
342     * @return the keySerializer FQCN
343     */
344    String getKeySerializerFQCN();
345
346
347    /**
348     * @return the valueSerializer
349     */
350    ElementSerializer<V> getValueSerializer();
351
352
353    /**
354     * @return the valueSerializer FQCN
355     */
356    String getValueSerializerFQCN();
357
358
359    /**
360     * @return The current B-tree revision
361     */
362    long getRevision();
363
364
365    /**
366     * @return The current number of elements in the B-tree
367     */
368    long getNbElems();
369
370
371    /**
372     * @return true if this B-tree allow duplicate values
373     */
374    boolean isAllowDuplicates();
375
376
377    /**
378     * @param allowDuplicates True if the B-tree will allow duplicate values
379     */
380    void setAllowDuplicates( boolean allowDuplicates );
381
382
383    /**
384     * @return the type
385     */
386    BTreeTypeEnum getType();
387}