Author: chetanm
Date: Fri Feb 20 07:40:13 2015
New Revision: 1661069
URL: http://svn.apache.org/r1661069
Log:
OAK-2513 - algorithm with O(n!) in mongoMk rebase - not finishing in years
Change the RebaseCommit to only keep track of previous non rebase commits. This
avoids the nested structure and keep lookup cost to O(n)
Modified:
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/Branch.java
jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/document/DocumentNodeStoreTest.java
Modified:
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/Branch.java
URL:
http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/Branch.java?rev=1661069&r1=1661068&r2=1661069&view=diff
==============================================================================
---
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/Branch.java
(original)
+++
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/Branch.java
Fri Feb 20 07:40:13 2015
@@ -22,9 +22,11 @@ import static com.google.common.collect.
import java.lang.ref.ReferenceQueue;
import java.lang.ref.WeakReference;
+import java.util.Map;
import java.util.NavigableMap;
import java.util.Set;
import java.util.SortedSet;
+import java.util.TreeMap;
import java.util.concurrent.ConcurrentSkipListMap;
import javax.annotation.CheckForNull;
@@ -33,7 +35,6 @@ import javax.annotation.Nullable;
import com.google.common.base.Function;
import com.google.common.collect.Iterables;
-import com.google.common.collect.Maps;
import com.google.common.collect.Sets;
/**
@@ -277,6 +278,8 @@ class Branch {
abstract boolean isModified(String path);
abstract Iterable<String> getModifiedPaths();
+
+ protected abstract boolean isRebase();
}
/**
@@ -307,6 +310,11 @@ class Branch {
return modifications;
}
+ @Override
+ protected boolean isRebase() {
+ return false;
+ }
+
//------------------< LastRevTracker
>----------------------------------
@Override
@@ -320,14 +328,14 @@ class Branch {
}
}
- static class RebaseCommit extends BranchCommit {
+ private static class RebaseCommit extends BranchCommit {
private final NavigableMap<Revision, BranchCommit> previous;
RebaseCommit(Revision base, Revision commit,
NavigableMap<Revision, BranchCommit> previous) {
super(base, commit);
- this.previous = Maps.newTreeMap(previous);
+ this.previous = squash(previous);
}
@Override
@@ -348,6 +356,11 @@ class Branch {
}
@Override
+ protected boolean isRebase() {
+ return true;
+ }
+
+ @Override
Iterable<String> getModifiedPaths() {
Iterable<Iterable<String>> paths = transform(previous.values(),
new Function<BranchCommit, Iterable<String>>() {
@@ -359,6 +372,22 @@ class Branch {
return Iterables.concat(paths);
}
+ /**
+ * Filter out the RebaseCommits as they are just container of previous
BranchCommit
+ *
+ * @param previous branch commit history
+ * @return filtered branch history only containing non rebase commits
+ */
+ private static NavigableMap<Revision, BranchCommit>
squash(NavigableMap<Revision, BranchCommit> previous) {
+ NavigableMap<Revision, BranchCommit> result = new
TreeMap<Revision, BranchCommit>(previous.comparator());
+ for (Map.Entry<Revision, BranchCommit> e : previous.entrySet()){
+ if (!e.getValue().isRebase()){
+ result.put(e.getKey(), e.getValue());
+ }
+ }
+ return result;
+ }
+
//------------------< LastRevTracker
>----------------------------------
@Override
Modified:
jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/document/DocumentNodeStoreTest.java
URL:
http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/document/DocumentNodeStoreTest.java?rev=1661069&r1=1661068&r2=1661069&view=diff
==============================================================================
---
jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/document/DocumentNodeStoreTest.java
(original)
+++
jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/document/DocumentNodeStoreTest.java
Fri Feb 20 07:40:13 2015
@@ -73,7 +73,6 @@ import org.apache.jackrabbit.oak.spi.sta
import org.apache.jackrabbit.oak.spi.state.NodeStore;
import org.apache.jackrabbit.oak.stats.Clock;
import org.junit.After;
-import org.junit.Ignore;
import org.junit.Test;
public class DocumentNodeStoreTest {
@@ -1076,7 +1075,6 @@ public class DocumentNodeStoreTest {
store.dispose();
}
- @Ignore("OAK-2513")
@Test
public void slowRebase() throws Exception {
final int NUM_NODES = DocumentRootBuilder.UPDATE_LIMIT / 2;
