SecondaryStoreCache implements DocumentNodeStateCache, SecondaryStoreRootObserver { @Nullable private AbstractDocumentNodeState findMatchingRoot(RevisionVector rr) { if (isEmpty()){ return null; } AbstractDocumentNodeState[] roots = previousRoots; AbstractDocumentNodeState latest = roots[roots.length - 1]; AbstractDocumentNodeState oldest = roots[0]; if (rr.compareTo(latest.getRootRevision()) > 0){ knownMissedNew.mark(); return null; } if (rr.compareTo(oldest.getRootRevision()) < 0){ knownMissedOld.mark(); return null; } AbstractDocumentNodeState result = findMatchingRoot(roots, rr); if (result != null){ return result; } knownMissedInRange.mark(); return null; } SecondaryStoreCache(NodeStore nodeStore, NodeStateDiffer differ, PathFilter pathFilter,
                               StatisticsProvider statisticsProvider); @Nullable @Override AbstractDocumentNodeState getDocumentNodeState(Path path, RevisionVector rootRevision,
                                                          RevisionVector lastRev); @Override boolean isCached(Path path); @Override void contentChanged(@NotNull AbstractDocumentNodeState root);  }
@Test public void binarySearch() throws Exception{ SecondaryStoreCache cache = createCache(new PathFilter(of("/a"), empty)); List<AbstractDocumentNodeState> roots = Lists.newArrayList(); List<RevisionVector> revs = Lists.newArrayList(); for (int i = 0; i < 50; i++) { NodeBuilder nb = primary.getRoot().builder(); create(nb, "/a/b"+i); AbstractDocumentNodeState r = merge(nb); roots.add(r); revs.add(r.getRootRevision()); } AbstractDocumentNodeState[] rootsArr = Iterables.toArray(roots, AbstractDocumentNodeState.class); Collections.shuffle(revs); for (RevisionVector rev : revs){ AbstractDocumentNodeState result = SecondaryStoreCache.findMatchingRoot(rootsArr, rev); assertNotNull(result); assertEquals(rev, result.getRootRevision()); } NodeBuilder nb = primary.getRoot().builder(); create(nb, "/a/m"); AbstractDocumentNodeState r = merge(nb); AbstractDocumentNodeState result = SecondaryStoreCache.findMatchingRoot(rootsArr, r.getRootRevision()); assertNull(result); }