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 /* No qualifier*/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 key Inserted key 61 * @param value Inserted value 62 * @param revision The new revision for the modified pages 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( K key, V value, long revision ) 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( K key, V value, long revision /*, 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, ReadTransaction<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( ReadTransaction<K, V> transaction, ParentPos<K, V>[] stack, int depth ) 148 throws EndOfFileExceededException, IOException; 149 150 151 /** 152 * Browses the keys of whole tree, and creates a Cursor on top of it. 153 * 154 * @param transaction The started transaction for this operation 155 * @param stack The stack of parents we go through to get to this page 156 * @return A Cursor to browse the keys 157 * @throws IOException If we have an error while trying to access the page 158 */ 159 KeyCursor<K> browseKeys( ReadTransaction<K, K> transaction, ParentPos<K, K>[] stack, int depth ) 160 throws EndOfFileExceededException, IOException; 161 162 163 /** 164 * @return the revision 165 */ 166 long getRevision(); 167 168 169 /** 170 * Returns the key at a given position 171 * 172 * @param pos The position of the key we want to retrieve 173 * @return The key found at the given position 174 */ 175 K getKey( int pos ); 176 177 178 /** 179 * Finds the leftmost key in this page. If the page is a node, it will go 180 * down in the leftmost children to recursively find the leftmost key. 181 * 182 * @return The leftmost key in the tree 183 */ 184 K getLeftMostKey(); 185 186 187 /** 188 * Finds the rightmost key in this page. If the page is a node, it will go 189 * down in the rightmost children to recursively find the rightmost key. 190 * 191 * @return The rightmost key in the tree 192 */ 193 K getRightMostKey(); 194 195 196 /** 197 * Finds the leftmost element in this page. If the page is a node, it will go 198 * down in the leftmost children to recursively find the leftmost element. 199 * 200 * @return The leftmost element in the tree 201 * @throws IOException If we have an error while trying to access the page 202 */ 203 Tuple<K, V> findLeftMost() throws IOException; 204 205 206 /** 207 * Finds the rightmost element in this page. If the page is a node, it will go 208 * down in the rightmost children to recursively find the rightmost element. 209 * 210 * @return The rightmost element in the tree 211 * @throws IOException If we have an error while trying to access the page 212 */ 213 Tuple<K, V> findRightMost() throws EndOfFileExceededException, IOException; 214 215 216 /** 217 * Pretty-prints the tree with tabs 218 * @param tabs The tabs to add in front of each node 219 * @return A pretty-print dump of the tree 220 */ 221 String dumpPage( String tabs ); 222 223 224 /** 225 * Find the position of the given key in the page. If we have found the key, 226 * we will return its position as a negative value. 227 * <p/> 228 * Assuming that the array is zero-indexed, the returned value will be : <br/> 229 * position = - ( position + 1) 230 * <br/> 231 * So for the following table of keys : <br/> 232 * <pre> 233 * +---+---+---+---+ 234 * | b | d | f | h | 235 * +---+---+---+---+ 236 * 0 1 2 3 237 * </pre> 238 * looking for 'b' will return -1 (-(0+1)) and looking for 'f' will return -3 (-(2+1)).<br/> 239 * Computing the real position is just a matter to get -(position++). 240 * <p/> 241 * If we don't find the key in the table, we will return the position of the key 242 * immediately above the key we are looking for. <br/> 243 * For instance, looking for : 244 * <ul> 245 * <li>'a' will return 0</li> 246 * <li>'b' will return -1</li> 247 * <li>'c' will return 1</li> 248 * <li>'d' will return -2</li> 249 * <li>'e' will return 2</li> 250 * <li>'f' will return -3</li> 251 * <li>'g' will return 3</li> 252 * <li>'h' will return -4</li> 253 * <li>'i' will return 4</li> 254 * </ul> 255 * 256 * 257 * @param key The key to find 258 * @return The position in the page. 259 */ 260 int findPos( K key ); 261 262 263 /** 264 * Checks if the given key exists. 265 * 266 * @param key The key we are looking at 267 * @return true if the key is present, false otherwise 268 * @throws IOException If we have an error while trying to access the page 269 */ 270 boolean hasKey( K key ) throws IOException; 271 272 273 /** 274 * Tells if the page is a leaf or not 275 * @return true if the page is a leaf 276 */ 277 boolean isLeaf(); 278 279 280 /** 281 * Tells if the page is a node or not 282 * @return true if the page is a node 283 */ 284 boolean isNode(); 285 }