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