View Javadoc

1   /*
2    *  Licensed to the Apache Software Foundation (ASF) under one
3    *  or more contributor license agreements.  See the NOTICE file
4    *  distributed with this work for additional information
5    *  regarding copyright ownership.  The ASF licenses this file
6    *  to you under the Apache License, Version 2.0 (the
7    *  "License"); you may not use this file except in compliance
8    *  with the License.  You may obtain a copy of the License at
9    *
10   *    http://www.apache.org/licenses/LICENSE-2.0
11   *
12   *  Unless required by applicable law or agreed to in writing,
13   *  software distributed under the License is distributed on an
14   *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15   *  KIND, either express or implied.  See the License for the
16   *  specific language governing permissions and limitations
17   *  under the License.
18   *
19   */
20  package org.apache.directory.mavibot.btree;
21  
22  
23  import java.io.IOException;
24  
25  import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
26  import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
27  
28  
29  /**
30   * A MVCC Page interface. A Page can be either a Leaf (containing keys and values) or a Node
31   * (containing keys and references to child pages).<br/>
32   * A Page can be stored on disk. If so, we store the serialized value of this Page into
33   * one or more {@link PageIO} (they will be linked)
34   * 
35   * @param <K> The type for the Key
36   * @param <V> The type for the stored value
37   *
38   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
39   */
40  public interface Page<K, V>
41  {
42      /**
43       * @return The number of keys present in this page
44       */
45      int getNbElems();
46  
47  
48      /**
49       * Inserts the given key and value into this page. We first find the place were to
50       * inject the <K,V> into the tree, by recursively browsing the pages :<br/>
51       * <ul>
52       * <li>If the index is below zero, the key is present in the Page : we modify the
53       * value and return</li>
54       * <li>If the page is a node, we have to go down to the right child page</li>
55       * <li>If the page is a leaf, we insert the new <K,V> element into the page, and if
56       * the Page is full, we split it and propagate the new pivot up into the tree</li>
57       * </ul>
58       * <p>
59       * 
60       * @param revision The new revision for the modified pages
61       * @param key Inserted key
62       * @param value Inserted value
63       * @return Either a modified Page or an Overflow element if the Page was full
64       * @throws IOException If we have an error while trying to access the page
65       */
66      InsertResult<K, V> insert( long revision, K key, V value ) throws IOException;
67  
68  
69      /**
70       * Deletes the value from an entry associated with the given key in this page. We first find 
71       * the place were to remove the <K,V> into the tree, by recursively browsing the pages.
72       * If the value is present, it will be deleted first, later if there are no other values associated with 
73       * this key(which can happen when duplicates are enabled), we will remove the key from the tree.
74       * 
75       * @param revision The new revision for the modified pages
76       * @param key The key to delete
77       * @param value The value to delete (can be null)
78       * @param parent The parent page
79       * @param parentPos The position of the current page in it's parent
80       * @return Either a modified Page if the key has been removed from the page, or a NotPresentResult.
81       * @throws IOException If we have an error while trying to access the page
82       */
83      DeleteResult<K, V> delete( long revision, K key, V value, Page<K, V> parent, int parentPos ) throws IOException;
84  
85  
86      /**
87       * Gets the value associated with the given key, if any. If we don't have 
88       * one, this method will throw a KeyNotFoundException.<br/>
89       * Note that we may get back null if a null value has been associated 
90       * with the key.
91       * 
92       * @param key The key we are looking for
93       * @return The associated value, which can be null
94       * @throws KeyNotFoundException If no entry with the given key can be found
95       * @throws IOException If we have an error while trying to access the page
96       */
97      V get( K key ) throws KeyNotFoundException, IOException;
98  
99  
100     /**
101      * Gets the values associated with the given key, if any. If we don't have 
102      * the key, this method will throw a KeyNotFoundException.<br/>
103      * Note that we may get back null if a null value has been associated 
104      * with the key.
105      * 
106      * @param key The key we are looking for
107      * @return The associated value, which can be null
108      * @throws KeyNotFoundException If no entry with the given key can be found
109      * @throws IOException If we have an error while trying to access the page
110      * @throws IllegalArgumentException If duplicates are not enabled 
111      */
112     ValueCursor<V> getValues( K key ) throws KeyNotFoundException, IOException, IllegalArgumentException;
113 
114 
115     /**
116      * Checks if the page contains the given key with the given value.
117      * 
118      * @param key The key we are looking for
119      * @param value The value associated with the given key
120      * @return true if the key and value are associated with each other, false otherwise
121      */
122     boolean contains( K key, V value ) throws IOException;
123 
124 
125     /**
126      * Browses the tree, looking for the given key, and creates a Cursor on top
127      * of the found result.
128      * 
129      * @param key The key we are looking for.
130      * @param transaction The started transaction for this operation
131      * @param stack The stack of parents we go through to get to this page
132      * @return A Cursor to browse the next elements
133      * @throws IOException If we have an error while trying to access the page
134      */
135     TupleCursor<K, V> browse( K key, Transaction<K, V> transaction, ParentPos<K, V>[] stack, int depth )
136         throws IOException;
137 
138 
139     /**
140      * Browses the whole tree, and creates a Cursor on top of it.
141      * 
142      * @param transaction The started transaction for this operation
143      * @param stack The stack of parents we go through to get to this page
144      * @return A Cursor to browse the next elements
145      * @throws IOException If we have an error while trying to access the page
146      */
147     TupleCursor<K, V> browse( Transaction<K, V> transaction, ParentPos<K, V>[] stack, int depth )
148         throws EndOfFileExceededException, IOException;
149 
150 
151     /**
152      * @return the revision
153      */
154     long getRevision();
155 
156 
157     /**
158      * Returns the key at a given position
159      * 
160      * @param pos The position of the key we want to retrieve
161      * @return The key found at the given position
162      */
163     K getKey( int pos );
164 
165 
166     /**
167      * Finds the leftmost key in this page. If the page is a node, it will go
168      * down in the leftmost children to recursively find the leftmost key.
169      * 
170      * @return The leftmost key in the tree
171      * @throws IOException If we have an error while trying to access the page
172      */
173     K getLeftMostKey() throws IOException;
174 
175 
176     /**
177      * Finds the rightmost key in this page. If the page is a node, it will go
178      * down in the rightmost children to recursively find the rightmost key.
179      * 
180      * @return The rightmost key in the tree
181      * @throws IOException If we have an error while trying to access the page
182      */
183     K getRightMostKey() throws IOException;
184 
185 
186     /**
187      * Finds the leftmost element in this page. If the page is a node, it will go
188      * down in the leftmost children to recursively find the leftmost element.
189      * 
190      * @return The leftmost element in the tree
191      * @throws IOException If we have an error while trying to access the page
192      */
193     Tuple<K, V> findLeftMost() throws IOException;
194 
195 
196     /**
197      * Finds the rightmost element in this page. If the page is a node, it will go
198      * down in the rightmost children to recursively find the rightmost element.
199      * 
200      * @return The rightmost element in the tree
201      * @throws IOException If we have an error while trying to access the page
202      */
203     Tuple<K, V> findRightMost() throws EndOfFileExceededException, IOException;
204 
205 
206     /**
207      * Pretty-prints the tree with tabs
208      * @param tabs The tabs to add in front of each node
209      * @return A pretty-print dump of the tree
210      */
211     String dumpPage( String tabs );
212 
213 
214     /**
215      * Find the position of the given key in the page. If we have found the key,
216      * we will return its position as a negative value.
217      * <p/>
218      * Assuming that the array is zero-indexed, the returned value will be : <br/>
219      *   position = - ( position + 1)
220      * <br/>
221      * So for the following table of keys : <br/>
222      * <pre>
223      * +---+---+---+---+
224      * | b | d | f | h |
225      * +---+---+---+---+
226      *   0   1   2   3
227      * </pre>
228      * looking for 'b' will return -1 (-(0+1)) and looking for 'f' will return -3 (-(2+1)).<br/>
229      * Computing the real position is just a matter to get -(position++).
230      * <p/>
231      * If we don't find the key in the table, we will return the position of the key
232      * immediately above the key we are looking for. <br/>
233      * For instance, looking for :
234      * <ul>
235      * <li>'a' will return 0</li>
236      * <li>'b' will return -1</li>
237      * <li>'c' will return 1</li>
238      * <li>'d' will return -2</li>
239      * <li>'e' will return 2</li>
240      * <li>'f' will return -3</li>
241      * <li>'g' will return 3</li>
242      * <li>'h' will return -4</li>
243      * <li>'i' will return 4</li>
244      * </ul>
245      * 
246      * 
247      * @param key The key to find
248      * @return The position in the page.
249      */
250     int findPos( K key );
251 
252 
253     /**
254      * Checks if the given key exists.
255      *  
256      * @param key The key we are looking at
257      * @return true if the key is present, false otherwise
258      * @throws IOException If we have an error while trying to access the page
259      */
260     boolean hasKey( K key ) throws IOException;
261 
262 
263     /**
264      * @return the offset of the first {@link PageIO} which stores the Page on disk.
265      */
266     long getOffset();
267 
268 
269     /**
270      * @return the offset of the last {@link PageIO} which stores the Page on disk.
271      */
272     long getLastOffset();
273 }