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.managed; 21 22 23 import java.io.IOException; 24 import java.lang.reflect.Array; 25 26 import org.apache.directory.mavibot.btree.Page; 27 import org.apache.directory.mavibot.btree.exception.KeyNotFoundException; 28 29 30 /** 31 * A MVCC abstract Page. It stores the field and the methods shared by the Node and Leaf 32 * classes. 33 * 34 * @param <K> The type for the Key 35 * @param <V> The type for the stored value 36 * 37 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a> 38 */ 39 /* No qualifier */abstract class AbstractPage<K, V> implements Page<K, V> 40 { 41 /** Parent B+Tree. */ 42 protected transient BTree<K, V> btree; 43 44 /** This BPage's revision */ 45 protected long revision; 46 47 /** Keys of children nodes */ 48 protected KeyHolder<K>[] keys; 49 50 /** The number of current values in the Page */ 51 protected int nbElems; 52 53 /** The first {@link PageIO} storing the serialized Page on disk */ 54 private long offset = -1L; 55 56 /** The last {@link PageIO} storing the serialized Page on disk */ 57 private long lastOffset = -1L; 58 59 /** A static Exception used to avoid creating a new one every time */ 60 protected KeyNotFoundException KEY_NOT_FOUND_EXCEPTION = new KeyNotFoundException( 61 "Cannot find an entry associated with this key" ); 62 63 64 /** 65 * Creates a default empty AbstractPage 66 * 67 * @param btree The associated BTree 68 */ 69 protected AbstractPage( BTree<K, V> btree ) 70 { 71 this.btree = btree; 72 } 73 74 75 /** 76 * Internal constructor used to create Page instance used when a page is being copied or overflow 77 */ 78 @SuppressWarnings("unchecked") 79 // Cannot create an array of generic objects 80 protected AbstractPage( BTree<K, V> btree, long revision, int nbElems ) 81 { 82 this.btree = btree; 83 this.revision = revision; 84 this.nbElems = nbElems; 85 this.keys = ( KeyHolder[] ) Array.newInstance( KeyHolder.class, nbElems ); 86 } 87 88 89 /** 90 * Selects the sibling (the previous or next page with the same parent) which has 91 * the more element assuming it's above N/2 92 * 93 * @param parent The parent of the current page 94 * @param The position of the current page reference in its parent 95 * @return The position of the sibling, or -1 if we have'nt found any sibling 96 * @throws IOException If we have an error while trying to access the page 97 */ 98 protected int selectSibling( Node<K, V> parent, int parentPos ) throws IOException 99 { 100 if ( parentPos == 0 ) 101 { 102 // The current page is referenced on the left of its parent's page : 103 // we will not have a previous page with the same parent 104 return 1; 105 } 106 107 if ( parentPos == parent.getNbElems() ) 108 { 109 // The current page is referenced on the right of its parent's page : 110 // we will not have a next page with the same parent 111 return parentPos - 1; 112 } 113 114 Page<K, V> prevPage = parent.children[parentPos - 1].getValue( btree ); 115 Page<K, V> nextPage = parent.children[parentPos + 1].getValue( btree ); 116 117 int prevPageSize = prevPage.getNbElems(); 118 int nextPageSize = nextPage.getNbElems(); 119 120 if ( prevPageSize >= nextPageSize ) 121 { 122 return parentPos - 1; 123 } 124 else 125 { 126 return parentPos + 1; 127 } 128 } 129 130 131 /** 132 * {@inheritDoc} 133 */ 134 public int getNbElems() 135 { 136 return nbElems; 137 } 138 139 140 /** 141 * Finds the position of the given key in the page. If we have found the key, 142 * we will return its position as a negative value. 143 * <p/> 144 * Assuming that the array is zero-indexed, the returned value will be : <br/> 145 * position = - ( position + 1) 146 * <br/> 147 * So for the following table of keys : <br/> 148 * <pre> 149 * +---+---+---+---+ 150 * | b | d | f | h | 151 * +---+---+---+---+ 152 * 0 1 2 3 153 * </pre> 154 * looking for 'b' will return -1 (-(0+1)) and looking for 'f' will return -3 (-(2+1)).<br/> 155 * Computing the real position is just a matter to get -(position++). 156 * <p/> 157 * If we don't find the key in the table, we will return the position of the key 158 * immediately above the key we are looking for. <br/> 159 * For instance, looking for : 160 * <ul> 161 * <li>'a' will return 0</li> 162 * <li>'b' will return -1</li> 163 * <li>'c' will return 1</li> 164 * <li>'d' will return -2</li> 165 * <li>'e' will return 2</li> 166 * <li>'f' will return -3</li> 167 * <li>'g' will return 3</li> 168 * <li>'h' will return -4</li> 169 * <li>'i' will return 4</li> 170 * </ul> 171 * 172 * 173 * @param key The key to find 174 * @return The position in the page. 175 */ 176 public int findPos( K key ) 177 { 178 // Deal with the special key where we have an empty page 179 if ( nbElems == 0 ) 180 { 181 return 0; 182 } 183 184 int min = 0; 185 int max = nbElems - 1; 186 187 // binary search 188 while ( min < max ) 189 { 190 int middle = ( min + max + 1 ) >> 1; 191 192 int comp = compare( keys[middle].getKey(), key ); 193 194 if ( comp < 0 ) 195 { 196 min = middle + 1; 197 } 198 else if ( comp > 0 ) 199 { 200 max = middle - 1; 201 } 202 else 203 { 204 // Special case : the key already exists, 205 // we can return immediately. The value will be 206 // negative, and as the index may be 0, we subtract 1 207 return -( middle + 1 ); 208 } 209 } 210 211 // Special case : we don't know if the key is present 212 int comp = compare( keys[max].getKey(), key ); 213 214 if ( comp == 0 ) 215 { 216 return -( max + 1 ); 217 } 218 else 219 { 220 if ( comp < 0 ) 221 { 222 return max + 1; 223 } 224 else 225 { 226 return max; 227 } 228 } 229 } 230 231 232 /** 233 * Compares two keys 234 * 235 * @param key1 The first key 236 * @param key2 The second key 237 * @return -1 if the first key is above the second one, 1 if it's below, and 0 238 * if the two keys are equal 239 */ 240 private final int compare( K key1, K key2 ) 241 { 242 if ( key1 == key2 ) 243 { 244 return 0; 245 } 246 247 if ( key1 == null ) 248 { 249 return 1; 250 } 251 252 if ( key2 == null ) 253 { 254 return -1; 255 } 256 257 return btree.getComparator().compare( key1, key2 ); 258 } 259 260 261 /** 262 * {@inheritDoc} 263 */ 264 public long getRevision() 265 { 266 return revision; 267 } 268 269 270 /** 271 * {@inheritDoc} 272 */ 273 public K getKey( int pos ) 274 { 275 if ( pos < nbElems ) 276 { 277 return keys[pos].getKey(); 278 } 279 else 280 { 281 return null; 282 } 283 } 284 285 286 /** 287 * Sets the key at a give position 288 * 289 * @param pos The position in the keys array 290 * @param key the key to inject 291 */ 292 /* No qualifier*/void setKey( int pos, K key ) 293 { 294 keys[pos] = new KeyHolder<K>( btree.getKeySerializer(), key ); 295 } 296 297 298 /** 299 * Sets the key at a give position 300 * 301 * @param pos The position in the keys array 302 * @param buffer the serialized key to inject 303 */ 304 /* No qualifier*/void setKey( int pos, byte[] buffer ) 305 { 306 keys[pos] = new KeyHolder<K>( btree.getKeySerializer(), buffer ); 307 } 308 309 310 /** 311 * {@inheritDoc} 312 */ 313 public long getOffset() 314 { 315 return offset; 316 } 317 318 319 /** 320 * @param offset the offset to set 321 */ 322 /* No qualifier */void setOffset( long offset ) 323 { 324 this.offset = offset; 325 } 326 327 328 /** 329 * {@inheritDoc} 330 */ 331 public long getLastOffset() 332 { 333 return lastOffset; 334 } 335 336 337 /** 338 * {@inheritDoc} 339 */ 340 /* No qualifier */void setLastOffset( long lastOffset ) 341 { 342 this.lastOffset = lastOffset; 343 } 344 345 346 /** 347 * @see Object#toString() 348 */ 349 public String toString() 350 { 351 StringBuilder sb = new StringBuilder(); 352 353 sb.append( "r" ).append( revision ); 354 sb.append( ", nbElems:" ).append( nbElems ); 355 356 if ( offset > 0 ) 357 { 358 sb.append( ", offset:" ).append( offset ); 359 } 360 361 return sb.toString(); 362 } 363 364 365 /** 366 * {@inheritDoc} 367 */ 368 public String dumpPage( String tabs ) 369 { 370 return ""; 371 } 372 }