1 21 package com.db4o.inside.btree; 22 23 import com.db4o.*; 24 import com.db4o.foundation.*; 25 import com.db4o.inside.ix.*; 26 import com.db4o.inside.mapping.*; 27 28 31 public class BTree extends YapMeta implements TransactionParticipant { 32 33 private static final byte BTREE_VERSION = (byte)1; 34 35 private static final int DEFRAGMENT_INCREMENT_OFFSET = 36 1 + YapConst.INT_LENGTH * 2; 39 final Indexable4 _keyHandler; 40 41 final Indexable4 _valueHandler; 42 43 private BTreeNode _root; 44 45 48 private TreeIntObject _nodes; 49 50 private int _size; 51 52 private Visitor4 _removeListener; 53 54 private Hashtable4 _sizesByTransaction; 55 56 protected Queue4 _processing; 57 58 private int _nodeSize; 59 60 int _halfNodeSize; 61 62 private final int _cacheHeight; 63 64 public BTree(Transaction trans, int id, Indexable4 keyHandler){ 65 this(trans, id, keyHandler, null); 66 } 67 68 public BTree(Transaction trans, int id, Indexable4 keyHandler, Indexable4 valueHandler){ 69 this(trans, id, keyHandler, valueHandler, config(trans).bTreeNodeSize(), config(trans).bTreeCacheHeight()); 70 } 71 72 public BTree(Transaction trans, int id, Indexable4 keyHandler, Indexable4 valueHandler, final int treeNodeSize, final int treeCacheHeight) { 73 if (null == keyHandler) { 74 throw new ArgumentNullException(); 75 } 76 _nodeSize = treeNodeSize; 77 78 _halfNodeSize = _nodeSize / 2; 79 _nodeSize = _halfNodeSize * 2; 80 _cacheHeight = treeCacheHeight; 81 _keyHandler = keyHandler; 82 _valueHandler = (valueHandler == null) ? Null.INSTANCE : valueHandler; 83 _sizesByTransaction = new Hashtable4(); 84 if(id == 0){ 85 setStateDirty(); 86 _root = new BTreeNode(this, 0, true, 0, 0, 0); 87 _root.write(trans.systemTransaction()); 88 addNode(_root); 89 write(trans.systemTransaction()); 90 }else{ 91 setID(id); 92 setStateDeactivated(); 93 } 94 } 95 96 public BTreeNode root() { 97 return _root; 98 } 99 100 public int nodeSize() { 101 return _nodeSize; 102 } 103 104 public void add(Transaction trans, Object key){ 105 add(trans, key, null); 106 } 107 108 public void add(Transaction trans, Object key, Object value){ 109 keyCantBeNull(key); 110 _keyHandler.prepareComparison(key); 111 _valueHandler.prepareComparison(value); 112 ensureDirty(trans); 113 BTreeNode rootOrSplit = _root.add(trans); 114 if(rootOrSplit != null && rootOrSplit != _root){ 115 _root = new BTreeNode(trans, _root, rootOrSplit); 116 _root.write(trans.systemTransaction()); 117 addNode(_root); 118 } 119 } 120 121 public void remove(Transaction trans, Object key){ 122 keyCantBeNull(key); 123 124 final Iterator4 pointers = search(trans, key).pointers(); 125 if (!pointers.moveNext()) { 126 return; 127 } 128 BTreePointer first = (BTreePointer)pointers.current(); 129 ensureDirty(trans); 130 BTreeNode node = first.node(); 131 node.remove(trans, first.index()); 132 } 133 134 public BTreeRange search(Transaction trans, Object key) { 135 keyCantBeNull(key); 136 137 142 BTreeNodeSearchResult start = searchLeaf(trans, key, SearchTarget.LOWEST); 143 BTreeNodeSearchResult end = searchLeaf(trans, key, SearchTarget.HIGHEST); 144 return start.createIncludingRange(end); 145 } 146 147 private void keyCantBeNull(Object key) { 148 if (null == key) { 149 throw new ArgumentNullException(); 150 } 151 } 152 153 public BTreeNodeSearchResult searchLeaf(Transaction trans, Object key, SearchTarget target) { 154 ensureActive(trans); 155 _keyHandler.prepareComparison(key); 156 return _root.searchLeaf(trans, target); 157 } 158 159 public void commit(final Transaction trans){ 160 161 final Transaction systemTransaction = trans.systemTransaction(); 162 163 Object sizeDiff = _sizesByTransaction.get(trans); 164 if(sizeDiff != null){ 165 _size += ((Integer ) sizeDiff).intValue(); 166 } 167 _sizesByTransaction.remove(trans); 168 169 if(_nodes != null){ 170 171 processAllNodes(); 172 while(_processing.hasNext()){ 173 ((BTreeNode)_processing.next()).commit(trans); 174 } 175 _processing = null; 176 177 writeAllNodes(systemTransaction, true); 178 179 } 180 181 setStateDirty(); 182 write(systemTransaction); 183 184 purge(); 185 } 186 187 public void rollback(final Transaction trans){ 188 189 final Transaction systemTransaction = trans.systemTransaction(); 190 191 _sizesByTransaction.remove(trans); 192 193 if(_nodes == null){ 194 return; 195 } 196 197 processAllNodes(); 198 while(_processing.hasNext()){ 199 ((BTreeNode)_processing.next()).rollback(trans); 200 } 201 _processing = null; 202 203 writeAllNodes(systemTransaction, false); 204 205 setStateDirty(); 206 write(systemTransaction); 207 208 purge(); 209 } 210 211 private void writeAllNodes(final Transaction systemTransaction, final boolean setDirty){ 212 if(_nodes == null){ 213 return; 214 } 215 _nodes.traverse(new Visitor4() { 216 public void visit(Object obj) { 217 BTreeNode node = (BTreeNode)((TreeIntObject)obj).getObject(); 218 if(setDirty){ 219 node.setStateDirty(); 220 } 221 node.write(systemTransaction); 222 } 223 }); 224 } 225 226 227 private void purge(){ 228 if(_nodes == null){ 229 return; 230 } 231 232 Tree temp = _nodes; 233 _nodes = null; 234 235 if(_cacheHeight > 0){ 236 _root.markAsCached(_cacheHeight); 237 }else{ 238 _root.holdChildrenAsIDs(); 239 addNode(_root); 240 } 241 242 temp.traverse(new Visitor4() { 243 public void visit(Object obj) { 244 BTreeNode node = (BTreeNode)((TreeIntObject)obj).getObject(); 245 node.purge(); 246 } 247 }); 248 } 249 250 private void processAllNodes(){ 251 _processing = new Queue4(); 252 _nodes.traverse(new Visitor4() { 253 public void visit(Object obj) { 254 _processing.add(((TreeIntObject)obj).getObject()); 255 } 256 }); 257 } 258 259 private void ensureActive(Transaction trans){ 260 if(! isActive()){ 261 read(trans.systemTransaction()); 262 } 263 } 264 265 private void ensureDirty(Transaction trans){ 266 ensureActive(trans); 267 trans.enlist(this); 268 setStateDirty(); 269 } 270 271 public byte getIdentifier() { 272 return YapConst.BTREE; 273 } 274 275 public void setRemoveListener(Visitor4 vis){ 276 _removeListener = vis; 277 } 278 279 public int ownLength() { 280 return 1 + YapConst.OBJECT_LENGTH + (YapConst.INT_LENGTH * 2) + YapConst.ID_LENGTH; 281 } 282 283 BTreeNode produceNode(int id){ 284 TreeIntObject addtio = new TreeIntObject(id); 285 _nodes = (TreeIntObject)Tree.add(_nodes, addtio); 286 TreeIntObject tio = (TreeIntObject)addtio.duplicateOrThis(); 287 BTreeNode node = (BTreeNode)tio.getObject(); 288 if(node == null){ 289 node = new BTreeNode(id, this); 290 tio.setObject(node); 291 addToProcessing(node); 292 } 293 return node; 294 } 295 296 void addNode(BTreeNode node){ 297 _nodes = (TreeIntObject)Tree.add(_nodes, new TreeIntObject(node.getID(), node)); 298 addToProcessing(node); 299 } 300 301 void addToProcessing(BTreeNode node){ 302 if(_processing != null){ 303 _processing.add(node); 304 } 305 } 306 307 void removeNode(BTreeNode node){ 308 _nodes = (TreeIntObject)_nodes.removeLike(new TreeInt(node.getID())); 309 } 310 311 void notifyRemoveListener(Object obj){ 312 if(_removeListener != null){ 313 _removeListener.visit(obj); 314 } 315 } 316 317 public void readThis(Transaction a_trans, YapReader a_reader) { 318 a_reader.incrementOffset(1); _size = a_reader.readInt(); 320 _nodeSize = a_reader.readInt(); 321 _halfNodeSize = nodeSize() / 2; 322 _root = produceNode(a_reader.readInt()); 323 } 324 325 public void writeThis(Transaction trans, YapReader a_writer) { 326 a_writer.append(BTREE_VERSION); 327 a_writer.writeInt(_size); 328 a_writer.writeInt(nodeSize()); 329 a_writer.writeIDOf(trans, _root); 330 } 331 332 public int size(Transaction trans){ 333 ensureActive(trans); 334 Object sizeDiff = _sizesByTransaction.get(trans); 335 if(sizeDiff != null){ 336 return _size + ((Integer ) sizeDiff).intValue(); 337 } 338 return _size; 339 } 340 341 public void traverseKeys(Transaction trans, Visitor4 visitor){ 342 ensureActive(trans); 343 if(_root == null){ 344 return; 345 } 346 _root.traverseKeys(trans, visitor); 347 } 348 349 public void traverseValues(Transaction trans, Visitor4 visitor) { 350 ensureActive(trans); 351 if(_root == null){ 352 return; 353 } 354 _root.traverseValues(trans, visitor); 355 } 356 357 public void sizeChanged(Transaction trans, int changeBy){ 358 Object sizeDiff = _sizesByTransaction.get(trans); 359 if(sizeDiff == null){ 360 _sizesByTransaction.put(trans, new Integer (changeBy)); 361 return; 362 } 363 _sizesByTransaction.put(trans, new Integer (((Integer ) sizeDiff).intValue() + changeBy)); 364 } 365 366 public void dispose(Transaction transaction) { 367 } 369 370 public BTreePointer firstPointer(Transaction trans) { 371 ensureActive(trans); 372 if (null == _root) { 373 return null; 374 } 375 return _root.firstPointer(trans); 376 } 377 378 public BTreePointer lastPointer(Transaction trans) { 379 ensureActive(trans); 380 if (null == _root) { 381 return null; 382 } 383 return _root.lastPointer(trans); 384 } 385 386 public BTree debugLoadFully(Transaction trans) { 387 ensureActive(trans); 388 _root.debugLoadFully(trans); 389 return this; 390 } 391 392 private void traverseAllNodes(Transaction trans, Visitor4 command) { 393 ensureActive(trans); 394 _root.traverseAllNodes(trans, command); 395 } 396 397 public void defragIndex(ReaderPair readers) { 398 if (Deploy.debug) { 399 readers.readBegin(YapConst.BTREE); 400 } 401 readers.incrementOffset(DEFRAGMENT_INCREMENT_OFFSET); 402 readers.copyID(); 403 if (Deploy.debug) { 404 readers.readEnd(); 405 } 406 } 407 408 public void defragIndexNode(ReaderPair readers) { 409 BTreeNode.defragIndex(readers, _keyHandler, _valueHandler); 410 } 411 412 public void defragBTree(final DefragContext context) throws CorruptionException { 413 ReaderPair.processCopy(context,getID(),new SlotCopyHandler() { 414 public void processCopy(ReaderPair readers) throws CorruptionException { 415 defragIndex(readers); 416 } 417 }); 418 final CorruptionException[] exc={null}; 419 try { 420 context.traverseAllIndexSlots(this, new Visitor4() { 421 public void visit(Object obj) { 422 final int id=((Integer )obj).intValue(); 423 try { 424 ReaderPair.processCopy(context, id, new SlotCopyHandler() { 425 public void processCopy(ReaderPair readers) { 426 defragIndexNode(readers); 427 } 428 }); 429 } catch (CorruptionException e) { 430 exc[0]=e; 431 throw new RuntimeException (); 432 } 433 } 434 }); 435 } catch (RuntimeException e) { 436 if(exc[0]!=null) { 437 throw exc[0]; 438 } 439 throw e; 440 } 441 } 442 443 public int compareKeys(Object key1, Object key2) { 444 _keyHandler.prepareComparison(key2); 445 return _keyHandler.compareTo(key1); 446 } 447 448 private static Config4Impl config(Transaction trans) { 449 if (null == trans) { 450 throw new ArgumentNullException(); 451 } 452 return trans.stream().configImpl(); 453 } 454 455 public void free(Transaction systemTrans) { 456 freeAllNodeIds(systemTrans, allNodeIds(systemTrans)); 457 } 458 459 private void freeAllNodeIds(Transaction systemTrans, final Iterator4 allNodeIDs) { 460 while(allNodeIDs.moveNext()){ 461 int id = ((Integer )allNodeIDs.current()).intValue(); 462 systemTrans.slotFreePointerOnCommit(id); 463 } 464 } 465 466 public Iterator4 allNodeIds(Transaction systemTrans) { 467 final Collection4 allNodeIDs = new Collection4(); 468 traverseAllNodes(systemTrans, new Visitor4() { 469 public void visit(Object node) { 470 allNodeIDs.add(new Integer (((BTreeNode)node).getID())); 471 } 472 }); 473 return allNodeIDs.iterator(); 474 } 475 476 public BTreeRange asRange(Transaction trans){ 477 return new BTreeRangeSingle(trans, this, firstPointer(trans), null); 478 } 479 480 481 } 482 483 | Popular Tags |