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.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 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 86 // We get the type of array to create from the btree 87 // Yes, this is an hack... 88 Class<?> keyType = btree.getKeyType(); 89 this.keys = ( K[] ) Array.newInstance( keyType, nbElems ); 90 } 91 92 93 /** 94 * Selects the sibling (the previous or next page with the same parent) which has 95 * the more element assuming it's above N/2 96 * 97 * @param parent The parent of the current page 98 * @param The position of the current page reference in its parent 99 * @return The position of the sibling, or -1 if we have'nt found any sibling 100 * @throws IOException If we have an error while trying to access the page 101 */ 102 protected int selectSibling( Node<K, V> parent, int parentPos ) throws IOException 103 { 104 if ( parentPos == 0 ) 105 { 106 // The current page is referenced on the left of its parent's page : 107 // we will not have a previous page with the same parent 108 return 1; 109 } 110 111 if ( parentPos == parent.getNbElems() ) 112 { 113 // The current page is referenced on the right of its parent's page : 114 // we will not have a next page with the same parent 115 return parentPos - 1; 116 } 117 118 Page<K, V> prevPage = parent.children[parentPos - 1]; 119 Page<K, V> nextPage = parent.children[parentPos + 1]; 120 121 int prevPageSize = prevPage.getNbElems(); 122 int nextPageSize = nextPage.getNbElems(); 123 124 if ( prevPageSize >= nextPageSize ) 125 { 126 return parentPos - 1; 127 } 128 else 129 { 130 return parentPos + 1; 131 } 132 } 133 134 135 /** 136 * {@inheritDoc} 137 */ 138 public int getNbElems() 139 { 140 return nbElems; 141 } 142 143 144 /** 145 * Finds the position of the given key in the page. If we have found the key, 146 * we will return its position as a negative value. 147 * <p/> 148 * Assuming that the array is zero-indexed, the returned value will be : <br/> 149 * position = - ( position + 1) 150 * <br/> 151 * So for the following table of keys : <br/> 152 * <pre> 153 * +---+---+---+---+ 154 * | b | d | f | h | 155 * +---+---+---+---+ 156 * 0 1 2 3 157 * </pre> 158 * looking for 'b' will return -1 (-(0+1)) and looking for 'f' will return -3 (-(2+1)).<br/> 159 * Computing the real position is just a matter to get -(position++). 160 * <p/> 161 * If we don't find the key in the table, we will return the position of the key 162 * immediately above the key we are looking for. <br/> 163 * For instance, looking for : 164 * <ul> 165 * <li>'a' will return 0</li> 166 * <li>'b' will return -1</li> 167 * <li>'c' will return 1</li> 168 * <li>'d' will return -2</li> 169 * <li>'e' will return 2</li> 170 * <li>'f' will return -3</li> 171 * <li>'g' will return 3</li> 172 * <li>'h' will return -4</li> 173 * <li>'i' will return 4</li> 174 * </ul> 175 * 176 * 177 * @param key The key to find 178 * @return The position in the page. 179 */ 180 public int findPos( K key ) 181 { 182 // Deal with the special key where we have an empty page 183 if ( nbElems == 0 ) 184 { 185 return 0; 186 } 187 188 int min = 0; 189 int max = nbElems - 1; 190 191 // binary search 192 while ( min < max ) 193 { 194 int middle = ( min + max + 1 ) >> 1; 195 196 int comp = compare( keys[middle], key ); 197 198 if ( comp < 0 ) 199 { 200 min = middle + 1; 201 } 202 else if ( comp > 0 ) 203 { 204 max = middle - 1; 205 } 206 else 207 { 208 // Special case : the key already exists, 209 // we can return immediately. The value will be 210 // negative, and as the index may be 0, we subtract 1 211 return -( middle + 1 ); 212 } 213 } 214 215 // Special case : we don't know if the key is present 216 int comp = compare( keys[max], key ); 217 218 if ( comp == 0 ) 219 { 220 return -( max + 1 ); 221 } 222 else 223 { 224 if ( comp < 0 ) 225 { 226 return max + 1; 227 } 228 else 229 { 230 return max; 231 } 232 } 233 } 234 235 236 /** 237 * Compares two keys 238 * 239 * @param key1 The first key 240 * @param key2 The second key 241 * @return -1 if the first key is above the second one, 1 if it's below, and 0 242 * if the two keys are equal 243 */ 244 private final int compare( K key1, K key2 ) 245 { 246 if ( key1 == key2 ) 247 { 248 return 0; 249 } 250 251 if ( key1 == null ) 252 { 253 return 1; 254 } 255 256 if ( key2 == null ) 257 { 258 return -1; 259 } 260 261 return btree.getComparator().compare( key1, key2 ); 262 } 263 264 265 /** 266 * {@inheritDoc} 267 */ 268 public long getRevision() 269 { 270 return revision; 271 } 272 273 274 /** 275 * {@inheritDoc} 276 */ 277 public K getKey( int pos ) 278 { 279 if ( pos < nbElems ) 280 { 281 return keys[pos]; 282 } 283 else 284 { 285 return null; 286 } 287 } 288 289 290 /** 291 * Sets the key at a give position 292 * 293 * @param pos The position in the keys array 294 * @param key the key to inject 295 */ 296 /* No qualifier*/void setKey( int pos, K key ) 297 { 298 keys[pos] = key; 299 } 300 301 302 /** 303 * {@inheritDoc} 304 */ 305 public long getOffset() 306 { 307 return offset; 308 } 309 310 311 /** 312 * @param offset the offset to set 313 */ 314 /* No qualifier */void setOffset( long offset ) 315 { 316 this.offset = offset; 317 } 318 319 320 /** 321 * {@inheritDoc} 322 */ 323 public long getLastOffset() 324 { 325 return lastOffset; 326 } 327 328 329 /** 330 * {@inheritDoc} 331 */ 332 /* No qualifier */void setLastOffset( long lastOffset ) 333 { 334 this.lastOffset = lastOffset; 335 } 336 337 338 /** 339 * @see Object#toString() 340 */ 341 public String toString() 342 { 343 StringBuilder sb = new StringBuilder(); 344 345 sb.append( "r" ).append( revision ); 346 sb.append( ", nbElems:" ).append( nbElems ); 347 348 if ( offset > 0 ) 349 { 350 sb.append( ", offset:" ).append( offset ); 351 } 352 353 return sb.toString(); 354 } 355 356 357 /** 358 * {@inheritDoc} 359 */ 360 public String dumpPage( String tabs ) 361 { 362 return ""; 363 } 364 }