1 11 package org.eclipse.core.internal.watson; 12 13 import java.util.HashMap ; 14 import org.eclipse.core.internal.dtree.*; 15 import org.eclipse.core.internal.utils.Messages; 16 import org.eclipse.core.internal.utils.StringPool; 17 import org.eclipse.core.runtime.*; 18 import org.eclipse.osgi.util.NLS; 19 20 76 public class ElementTree { 77 protected DeltaDataTree tree; 78 protected IElementTreeData userData; 79 80 private class ChildIDsCache { 81 ChildIDsCache(IPath path, IPath[] childPaths) { 82 this.path = path; 83 this.childPaths = childPaths; 84 } 85 86 IPath path; 87 IPath[] childPaths; 88 } 89 90 private volatile ChildIDsCache childIDsCache = null; 91 92 private volatile DataTreeLookup lookupCache = null; 93 94 private volatile DataTreeLookup lookupCacheIgnoreCase = null; 95 96 private static int treeCounter = 0; 97 private int treeStamp; 98 99 102 public ElementTree() { 103 initialize(new DeltaDataTree()); 104 } 105 106 109 protected ElementTree(DataTreeNode rootNode) { 110 initialize(rootNode); 111 } 112 113 116 protected ElementTree(DeltaDataTree tree) { 117 initialize(tree); 118 } 119 120 124 protected ElementTree(ElementTree parent) { 125 if (!parent.isImmutable()) { 126 parent.immutable(); 127 } 128 129 130 IElementTreeData data = parent.getTreeData(); 131 if (data != null) { 132 userData = (IElementTreeData) data.clone(); 133 } 134 135 initialize(parent.tree.newEmptyDeltaTree()); 136 } 137 138 150 public synchronized ElementTree collapseTo(ElementTree parent) { 151 Assert.isTrue(tree.isImmutable()); 152 if (this == parent) { 153 return this; 155 } 156 tree.collapseTo(parent.tree, DefaultElementComparator.getComparator()); 158 return this; 159 } 160 161 171 public synchronized void createElement(IPath key, Object data) { 172 173 if (key.isRoot()) 174 return; 175 176 childIDsCache = null; 178 179 IPath parent = key.removeLastSegments(1); 180 try { 181 tree.createChild(parent, key.lastSegment(), data); 182 } catch (ObjectNotFoundException e) { 183 elementNotFound(parent); 184 } 185 lookupCache = DataTreeLookup.newLookup(key, true, data, true); 187 lookupCacheIgnoreCase = null; 188 } 189 190 199 public synchronized void createSubtree(IPath key, ElementTree subtree) { 200 201 if (key.isRoot()) { 202 throw new IllegalArgumentException (Messages.watson_noModify); 203 } 204 205 childIDsCache = null; 208 lookupCache = lookupCacheIgnoreCase = null; 211 try { 212 213 IPath[] children = subtree.getChildren(subtree.getRoot()); 214 if (children.length != 1) { 215 throw new IllegalArgumentException (Messages.watson_illegalSubtree); 216 } 217 218 219 DataTreeNode node = (DataTreeNode) subtree.tree.copyCompleteSubtree(children[0]); 220 221 222 tree.createSubtree(key, node); 223 224 } catch (ObjectNotFoundException e) { 225 elementNotFound(key); 226 } 227 } 228 229 233 public synchronized void deleteElement(IPath key) { 234 235 if (key.isRoot()) 236 return; 237 238 childIDsCache = null; 241 lookupCache = lookupCacheIgnoreCase = null; 244 try { 245 tree.deleteChild(key.removeLastSegments(1), key.lastSegment()); 246 } catch (ObjectNotFoundException e) { 247 elementNotFound(key); 248 } 249 } 250 251 254 protected void elementNotFound(IPath key) { 255 throw new IllegalArgumentException (NLS.bind(Messages.watson_elementNotFound, key)); 256 } 257 258 266 public static int findOldest(ElementTree[] trees) { 267 268 269 HashMap candidates = new HashMap ((int) (trees.length * 1.5 + 1)); 270 for (int i = 0; i < trees.length; i++) { 271 candidates.put(trees[i], trees[i]); 272 } 273 274 275 ElementTree oldestSoFar = null; 276 while (candidates.size() > 0) { 277 278 ElementTree current = (ElementTree) candidates.values().iterator().next(); 279 280 281 candidates.remove(current); 282 283 284 ElementTree parent = current.getParent(); 285 286 287 while (parent != null && parent != oldestSoFar) { 288 candidates.remove(parent); 289 parent = parent.getParent(); 290 } 291 292 293 oldestSoFar = current; 294 295 296 } 297 Assert.isNotNull(oldestSoFar); 298 299 300 for (int i = 0; i < trees.length; i++) { 301 if (trees[i] == oldestSoFar) { 302 return i; 303 } 304 } 305 Assert.isTrue(false, "Should not get here"); return -1; 307 } 308 309 314 public synchronized int getChildCount(IPath key) { 315 Assert.isNotNull(key); 316 return getChildIDs(key).length; 317 } 318 319 323 protected IPath[] getChildIDs(IPath key) { 324 ChildIDsCache cache = childIDsCache; if (cache != null && cache.path == key) { 326 return cache.childPaths; 327 } 328 try { 329 if (key == null) 330 return new IPath[] {tree.rootKey()}; 331 IPath[] children = tree.getChildren(key); 332 childIDsCache = new ChildIDsCache(key, children); return children; 334 } catch (ObjectNotFoundException e) { 335 elementNotFound(key); 336 return null; } 338 } 339 340 345 public synchronized IPath[] getChildren(IPath key) { 346 Assert.isNotNull(key); 347 return getChildIDs(key); 348 } 349 350 353 public DeltaDataTree getDataTree() { 354 return tree; 355 } 356 357 361 public synchronized Object getElementData(IPath key) { 362 363 if (key.isRoot()) 364 return null; 365 DataTreeLookup lookup = lookupCache; if (lookup == null || lookup.key != key) 367 lookupCache = lookup = tree.lookup(key); 368 if (lookup.isPresent) 369 return lookup.data; 370 elementNotFound(key); 371 return null; } 373 374 378 public synchronized Object getElementDataIgnoreCase(IPath key) { 379 380 if (key.isRoot()) 381 return null; 382 DataTreeLookup lookup = lookupCacheIgnoreCase; if (lookup == null || lookup.key != key) 384 lookupCacheIgnoreCase = lookup = tree.lookupIgnoreCase(key); 385 if (lookup.isPresent) 386 return lookup.data; 387 elementNotFound(key); 388 return null; } 390 391 396 public synchronized String [] getNamesOfChildren(IPath key) { 397 try { 398 if (key == null) 399 return new String [] {""}; return tree.getNamesOfChildren(key); 401 } catch (ObjectNotFoundException e) { 402 elementNotFound(key); 403 return null; } 405 } 406 407 410 public ElementTree getParent() { 411 DeltaDataTree parentTree = tree.getParent(); 412 if (parentTree == null) { 413 return null; 414 } 415 return (ElementTree) parentTree.getData(tree.rootKey()); 418 } 419 420 423 public IPath getRoot() { 424 return getChildIDs(null)[0]; 425 } 426 427 436 public ElementTree getSubtree(IPath key) { 437 438 if (key.isRoot()) { 439 return this; 440 } 441 try { 442 DataTreeNode elementNode = (DataTreeNode) tree.copyCompleteSubtree(key); 443 return new ElementTree(elementNode); 444 } catch (ObjectNotFoundException e) { 445 elementNotFound(key); 446 return null; 447 } 448 } 449 450 453 public IElementTreeData getTreeData() { 454 return userData; 455 } 456 457 462 public static boolean hasChanges(ElementTree newLayer, ElementTree oldLayer, IElementComparator comparator, boolean inclusive) { 463 if (newLayer == null || oldLayer == null) 465 return true; 466 if (newLayer == oldLayer) 467 return false; 468 if (comparator.compare(newLayer.getTreeData(), oldLayer.getTreeData()) != IElementComparator.K_NO_CHANGE) 470 return true; 471 472 479 ElementTree stopLayer = null; 481 if (newLayer.isImmutable()) 482 stopLayer = newLayer.getParent(); 485 else { 486 ElementTree layer = newLayer; 487 while (layer != null && layer.getParent() != null) { 488 if (!layer.getDataTree().isEmptyDelta()) 489 return true; 490 layer = layer.getParent(); 491 } 492 } 493 494 ElementTree layer = inclusive ? oldLayer : oldLayer.getParent(); 497 while (layer != null && layer.getParent() != stopLayer) { 498 if (!layer.getDataTree().isEmptyDelta()) 499 return true; 500 layer = layer.getParent(); 501 } 502 return false; 504 } 505 506 510 public synchronized void immutable() { 511 if (!tree.isImmutable()) { 512 tree.immutable(); 513 515 lookupCache = lookupCacheIgnoreCase = null; 516 517 tree.reroot(); 518 } 519 } 520 521 525 public synchronized boolean includes(IPath key) { 526 DataTreeLookup lookup = lookupCache; if (lookup == null || lookup.key != key) { 528 lookupCache = lookup = tree.lookup(key); 529 } 530 return lookup.isPresent; 531 } 532 533 537 public boolean includesIgnoreCase(IPath key) { 538 DataTreeLookup lookup = lookupCacheIgnoreCase; if (lookup == null || lookup.key != key) { 540 lookupCacheIgnoreCase = lookup = tree.lookupIgnoreCase(key); 541 } 542 return lookup.isPresent; 543 } 544 545 protected void initialize(DataTreeNode rootNode) { 546 547 initialize(new DeltaDataTree(new DataTreeNode(null, null, new AbstractDataTreeNode[] {rootNode}))); 548 } 549 550 protected void initialize(DeltaDataTree newTree) { 551 treeStamp = treeCounter++; 555 newTree.setData(newTree.rootKey(), this); 556 this.tree = newTree; 557 } 558 559 562 public boolean isImmutable() { 563 return tree.isImmutable(); 564 } 565 566 579 public ElementTree mergeDeltaChain(IPath path, ElementTree[] trees) { 580 if (path == null || trees == null) { 581 throw new IllegalArgumentException (NLS.bind(Messages.watson_nullArg, "ElementTree.mergeDeltaChain")); } 583 584 585 if (isImmutable()) { 586 throw new IllegalArgumentException (Messages.watson_immutable); 587 } 588 ElementTree current = this; 589 if (trees.length > 0) { 590 591 ElementTree toMerge = trees[findOldest(trees)]; 592 593 594 while (toMerge != null) { 595 if (path.isRoot()) { 596 IPath[] children = toMerge.getChildren(Path.ROOT); 598 for (int i = 0; i < children.length; i++) { 599 current.createSubtree(children[i], toMerge.getSubtree(children[i])); 600 } 601 } else { 602 current.createSubtree(path, toMerge.getSubtree(path)); 604 } 605 current.immutable(); 606 607 608 609 for (int i = 0; i < trees.length; i++) { 610 if (trees[i] == toMerge) { 611 trees[i] = current; 612 } 613 } 614 current = current.newEmptyDelta(); 615 toMerge = toMerge.getParent(); 616 } 617 } 618 return current; 619 } 620 621 626 public synchronized ElementTree newEmptyDelta() { 627 lookupCache = lookupCacheIgnoreCase = null; 629 return new ElementTree(this); 630 } 631 632 639 public synchronized Object openElementData(IPath key) { 640 Assert.isTrue(!isImmutable()); 641 642 643 if (key.isRoot()) 644 return null; 645 DataTreeLookup lookup = lookupCache; if (lookup == null || lookup.key != key) { 647 lookupCache = lookup = tree.lookup(key); 648 } 649 if (lookup.isPresent) { 650 if (lookup.foundInFirstDelta) 651 return lookup.data; 652 656 IElementTreeData oldData = (IElementTreeData) lookup.data; 657 if (oldData != null) { 658 try { 659 Object newData = oldData.clone(); 660 tree.setData(key, newData); 661 lookupCache = lookupCacheIgnoreCase = null; 662 return newData; 663 } catch (ObjectNotFoundException e) { 664 elementNotFound(key); 665 } 666 } 667 } else { 668 elementNotFound(key); 669 } 670 return null; 671 } 672 673 679 public synchronized void setElementData(IPath key, Object data) { 680 681 if (key.isRoot()) 682 return; 683 684 Assert.isNotNull(key); 685 lookupCache = lookupCacheIgnoreCase = null; 688 try { 689 tree.setData(key, data); 690 } catch (ObjectNotFoundException e) { 691 elementNotFound(key); 692 } 693 } 694 695 698 public void setTreeData(IElementTreeData data) { 699 userData = data; 700 } 701 702 705 public void shareStrings(StringPool set) { 706 tree.storeStrings(set); 707 } 708 709 713 public String toDebugString() { 714 final StringBuffer buffer = new StringBuffer ("\n"); IElementContentVisitor visitor = new IElementContentVisitor() { 716 public boolean visitElement(ElementTree aTree, IPathRequestor elementID, Object elementContents) { 717 buffer.append(elementID.requestPath() + " " + elementContents + "\n"); return true; 719 } 720 }; 721 new ElementTreeIterator(this, Path.ROOT).iterate(visitor); 722 return buffer.toString(); 723 } 724 725 public String toString() { 726 return "ElementTree(" + treeStamp + ")"; } 728 } 729 | Popular Tags |