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