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 }