You are viewing a plain text version of this content. The canonical link for it is here.
Posted to oak-commits@jackrabbit.apache.org by mr...@apache.org on 2016/01/07 13:46:36 UTC
svn commit: r1723532 [3/5] - in /jackrabbit/oak/trunk:
oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/
oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/util/
oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/d...
Modified: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/NodeDocument.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/NodeDocument.java?rev=1723532&r1=1723531&r2=1723532&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/NodeDocument.java (original)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/NodeDocument.java Thu Jan 7 12:46:35 2016
@@ -18,7 +18,6 @@ package org.apache.jackrabbit.oak.plugin
import java.util.ArrayList;
import java.util.Collections;
-import java.util.Comparator;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
@@ -55,7 +54,9 @@ import org.slf4j.LoggerFactory;
import com.google.common.collect.Iterables;
import com.google.common.collect.Maps;
import com.google.common.collect.Sets;
+import com.google.common.primitives.Longs;
+import static com.google.common.base.Objects.equal;
import static com.google.common.base.Preconditions.checkArgument;
import static com.google.common.base.Preconditions.checkNotNull;
import static com.google.common.collect.Iterables.filter;
@@ -64,7 +65,6 @@ import static org.apache.jackrabbit.oak.
import static org.apache.jackrabbit.oak.plugins.document.StableRevisionComparator.REVERSE;
import static org.apache.jackrabbit.oak.plugins.document.UpdateOp.Key;
import static org.apache.jackrabbit.oak.plugins.document.UpdateOp.Operation;
-import static org.apache.jackrabbit.oak.plugins.document.util.Utils.isRevisionNewer;
import static org.apache.jackrabbit.oak.plugins.document.util.Utils.resolveCommitRevision;
/**
@@ -654,42 +654,31 @@ public final class NodeDocument extends
}
/**
- * Returns the most recent conflict on the given {@code branchCommits} if
- * there are any. The returned revision is the commit, which created the
- * collision marker for one of the {@code branchCommits}.
- *
- * @param branchCommits the branch commits to check.
- * @param context a revision context.
- * @return the conflict revision or {@code null} if there aren't any or
- * the collision marker does not have a revision value.
+ * Returns the conflicts on the given {@code changes} if there are any. The
+ * returned revisions are the commits, which created the collision markers
+ * for one of the {@code changes}.
+ *
+ * @param changes the changes to check.
+ * @return the conflict revisions.
*/
- @CheckForNull
- Revision getMostRecentConflictFor(@Nonnull Iterable<Revision> branchCommits,
- @Nonnull RevisionContext context) {
- checkNotNull(branchCommits);
- checkNotNull(context);
-
- Comparator<Revision> comparator = context.getRevisionComparator();
- Revision conflict = null;
+ @Nonnull
+ Set<Revision> getConflictsFor(@Nonnull Iterable<Revision> changes) {
+ checkNotNull(changes);
+ Set<Revision> conflicts = Sets.newHashSet();
Map<Revision, String> collisions = getLocalMap(COLLISIONS);
- for (Revision r : branchCommits) {
+ for (Revision r : changes) {
String value = collisions.get(r.asTrunkRevision());
if (value == null) {
continue;
}
- Revision c;
try {
- c = Revision.fromString(value);
+ conflicts.add(Revision.fromString(value));
} catch (IllegalArgumentException e) {
// backward compatibility: collision marker with value 'true'
- continue;
- }
- if (conflict == null || comparator.compare(conflict, c) < 0) {
- conflict = c;
}
}
- return conflict;
+ return conflicts;
}
/**
@@ -740,20 +729,21 @@ public final class NodeDocument extends
*/
@CheckForNull
Revision getNewestRevision(final RevisionContext context,
- final Revision baseRev,
+ final RevisionVector baseRev,
final Revision changeRev,
final Branch branch,
final Set<Revision> collisions) {
checkArgument(!baseRev.isBranch() || branch != null,
"Branch must be non-null if baseRev is a branch revision");
- Revision head = context.getHeadRevision();
- Revision lower = branch != null ? branch.getBase() : baseRev;
+ RevisionVector head = context.getHeadRevision();
+ RevisionVector lower = branch != null ? branch.getBase() : baseRev;
// the clusterIds to check when walking the changes
Set<Integer> clusterIds = Collections.emptySet();
if (!getPreviousRanges().isEmpty()) {
clusterIds = Sets.newHashSet();
for (Revision prevRev : getPreviousRanges().keySet()) {
- if (!isRevisionNewer(context, lower, prevRev)) {
+ if (lower.isRevisionNewer(prevRev) ||
+ equal(prevRev, lower.getRevision(prevRev.getClusterId()))) {
clusterIds.add(prevRev.getClusterId());
}
}
@@ -796,7 +786,7 @@ public final class NodeDocument extends
if (!fullScan) {
// check if we can stop going through changes
if (clusterIds.contains(r.getClusterId())
- && isRevisionNewer(context, lower, r)
+ && !lower.isRevisionNewer(r)
&& newestRevs.containsKey(r.getClusterId())) {
clusterIds.remove(r.getClusterId());
if (clusterIds.isEmpty()) {
@@ -813,7 +803,7 @@ public final class NodeDocument extends
// of the branch if this is for a commit on a branch
if (branch != null && !branch.containsCommit(r)) {
// change does not belong to the branch
- if (isRevisionNewer(context, r, branch.getBase())) {
+ if (branch.getBase().isRevisionNewer(r)) {
// and happened after the base of the branch
collisions.add(r);
}
@@ -843,12 +833,12 @@ public final class NodeDocument extends
commitRevision = commitRoot.getCommitRevision(r);
}
if (commitRevision != null // committed but not yet visible
- && isRevisionNewer(context, commitRevision, head)) {
+ && head.isRevisionNewer(commitRevision)) {
// case 4)
collisions.add(r);
} else if (commitRevision != null // committed
&& branch == null // changeRev not on branch
- && isRevisionNewer(context, r, baseRev)) {
+ && baseRev.isRevisionNewer(r)) {
// case 5)
newestRevs.put(r.getClusterId(), r);
} else {
@@ -862,7 +852,7 @@ public final class NodeDocument extends
// select the newest committed change
Revision newestRev = null;
for (Revision r : newestRevs.values()) {
- newestRev = Utils.max(newestRev, r, context.getRevisionComparator());
+ newestRev = Utils.max(newestRev, r, StableRevisionComparator.INSTANCE);
}
if (newestRev == null) {
@@ -913,7 +903,7 @@ public final class NodeDocument extends
boolean isValidRevision(@Nonnull RevisionContext context,
@Nonnull Revision rev,
@Nullable String commitValue,
- @Nonnull Revision readRevision,
+ @Nonnull RevisionVector readRevision,
@Nonnull Map<Revision, String> validRevisions) {
if (validRevisions.containsKey(rev)) {
return true;
@@ -944,13 +934,12 @@ public final class NodeDocument extends
*/
@CheckForNull
public DocumentNodeState getNodeAtRevision(@Nonnull DocumentNodeStore nodeStore,
- @Nonnull Revision readRevision,
+ @Nonnull RevisionVector readRevision,
@Nullable Revision lastModified) {
Map<Revision, String> validRevisions = Maps.newHashMap();
Branch branch = nodeStore.getBranches().getBranch(readRevision);
- LastRevs lastRevs = new LastRevs(getLastRev(), readRevision, branch);
- // overlay with unsaved last modified from this instance
- lastRevs.update(lastModified);
+ LastRevs lastRevs = createLastRevs(readRevision,
+ validRevisions, branch, lastModified);
Revision min = getLiveRevision(nodeStore, readRevision, validRevisions, lastRevs);
if (min == null) {
@@ -959,7 +948,6 @@ public final class NodeDocument extends
}
String path = getPath();
DocumentNodeState n = new DocumentNodeState(nodeStore, path, readRevision, hasChildren());
- Revision lastRevision = min;
for (String key : keySet()) {
if (!Utils.isPropertyName(key)) {
continue;
@@ -970,80 +958,79 @@ public final class NodeDocument extends
continue;
}
// first check local map, which contains most recent values
- Value value = getLatestValue(nodeStore, local,
- min, readRevision, validRevisions, lastRevs);
+ Value value = getLatestValue(nodeStore, local, readRevision, validRevisions, lastRevs);
// check if there may be more recent values in a previous document
- if (!getPreviousRanges().isEmpty()) {
- if (!isMostRecentCommitted(nodeStore, local, value.revision)) {
- // not reading the most recent value, we may need to
- // consider previous documents as well
- Revision newestPrev = getPreviousRanges().firstKey();
- if (isRevisionNewer(nodeStore, newestPrev, value.revision)) {
+ if (value != null
+ && !getPreviousRanges().isEmpty()
+ && !isMostRecentCommitted(local, value.revision)) {
+ // not reading the most recent value, we may need to
+ // consider previous documents as well
+ for (Revision prev : getPreviousRanges().keySet()) {
+ if (prev.compareRevisionTimeThenClusterId(value.revision) > 0) {
// a previous document has more recent changes
// than value.revision
value = null;
+ break;
}
}
}
if (value == null && !getPreviousRanges().isEmpty()) {
// check complete revision history
- value = getLatestValue(nodeStore, getValueMap(key),
- min, readRevision, validRevisions, lastRevs);
+ value = getLatestValue(nodeStore, getValueMap(key), readRevision, validRevisions, lastRevs);
}
String propertyName = Utils.unescapePropertyName(key);
String v = value != null ? value.value : null;
n.setProperty(propertyName, v);
- // keep track of when this node was last modified
- if (value != null && isRevisionNewer(nodeStore, value.revision, lastRevision)) {
- lastRevision = value.revision;
- }
}
- // lastRevision now points to the revision when this node was
- // last modified directly. but it may also have been 'modified'
- // by an operation on a descendant node, which is tracked in
- // _lastRev.
-
// when was this node last modified?
- Revision branchBase = null;
+ RevisionVector lastRevision = new RevisionVector(min);
+ RevisionVector branchBase = null;
if (branch != null) {
- branchBase = branch.getBase(readRevision);
+ branchBase = branch.getBase(readRevision.getBranchRevision());
}
- for (Revision r : lastRevs.get().values()) {
- // ignore if newer than readRevision
- if (isRevisionNewer(nodeStore, r, readRevision)) {
+ for (Revision r : lastRevs) {
+ if (readRevision.isRevisionNewer(r)) {
// the node has a _lastRev which is newer than readRevision
// this means we don't know when this node was
// modified by an operation on a descendant node between
// current lastRevision and readRevision. therefore we have
// to stay on the safe side and use readRevision
- lastRevision = readRevision;
- continue;
- } else if (branchBase != null && isRevisionNewer(nodeStore, r, branchBase)) {
+ Revision rev = readRevision.getRevision(r.getClusterId());
+ if (rev != null) {
+ lastRevision = lastRevision.update(rev);
+ } else {
+ // readRevision does not have a revision for this
+ // clusterId -> remove from lastRevision
+ lastRevision = lastRevision.remove(r.getClusterId());
+ }
+ } else if (branchBase != null && branchBase.isRevisionNewer(r)) {
// readRevision is on a branch and the node has a
// _lastRev which is newer than the base of the branch
// we cannot use this _lastRev because it is not visible
// from this branch. highest possible revision of visible
// changes is the base of the branch
- r = branchBase;
- }
- if (revisionAreAmbiguous(nodeStore, r, lastRevision)) {
- // _lastRev entries from multiple cluster nodes are ambiguous
- // use readRevision to make sure read is consistent
- lastRevision = readRevision;
- } else if (isRevisionNewer(nodeStore, r, lastRevision)) {
- lastRevision = r;
+ Revision rev = branchBase.getRevision(r.getClusterId());
+ if (rev != null) {
+ lastRevision = lastRevision.update(rev);
+ } else {
+ // branchBase does not have a revision for this
+ // clusterId -> remove from lastRevision
+ lastRevision = lastRevision.remove(r.getClusterId());
+ }
+ } else if (lastRevision.isRevisionNewer(r)) {
+ lastRevision = lastRevision.update(r);
}
}
if (branch != null) {
// read from a branch
// -> possibly overlay with unsaved last revs from branch
- lastRevs.updateBranch(branch.getUnsavedLastRevision(path, readRevision));
+ lastRevs.updateBranch(branch.getUnsavedLastRevision(path, readRevision.getBranchRevision()));
Revision r = lastRevs.getBranchRevision();
if (r != null) {
- lastRevision = r;
+ lastRevision = lastRevision.update(r);
}
}
n.setLastRevision(lastRevision);
@@ -1055,27 +1042,26 @@ public final class NodeDocument extends
* the provided revision, if the node was alive at the given revision.
*
* @param context the revision context
- * @param maxRev the maximum revision to return
+ * @param readRevision the read revision
* @param validRevisions the map of revisions to commit value already
- * checked against maxRev and considered valid.
+ * checked against readRevision and considered valid.
* @param lastRevs to keep track of the last modification.
* @return the earliest revision, or null if the node is deleted at the
* given revision
*/
@CheckForNull
- public Revision getLiveRevision(RevisionContext context, Revision maxRev,
+ public Revision getLiveRevision(RevisionContext context,
+ RevisionVector readRevision,
Map<Revision, String> validRevisions,
LastRevs lastRevs) {
// check local deleted map first
- Value value = getLatestValue(context, getLocalDeleted(),
- null, maxRev, validRevisions, lastRevs);
- if (value.value == null && !getPreviousRanges().isEmpty()) {
+ Value value = getLatestValue(context, getLocalDeleted(), readRevision, validRevisions, lastRevs);
+ if (value == null && !getPreviousRanges().isEmpty()) {
// need to check complete map
- value = getLatestValue(context, getDeleted(),
- null, maxRev, validRevisions, lastRevs);
+ value = getLatestValue(context, getDeleted(), readRevision, validRevisions, lastRevs);
}
- return "false".equals(value.value) ? value.revision : null;
+ return value != null && "false".equals(value.value) ? value.revision : null;
}
/**
@@ -1085,14 +1071,12 @@ public final class NodeDocument extends
* @param op the update operation.
* @param baseRevision the base revision for the update operation.
* @param commitRevision the commit revision of the update operation.
- * @param context the revision context.
* @param enableConcurrentAddRemove feature flag for OAK-2673.
* @return <code>true</code> if conflicting, <code>false</code> otherwise.
*/
boolean isConflicting(@Nonnull UpdateOp op,
- @Nonnull Revision baseRevision,
+ @Nonnull RevisionVector baseRevision,
@Nonnull Revision commitRevision,
- @Nonnull RevisionContext context,
boolean enableConcurrentAddRemove) {
// did existence of node change after baseRevision?
// only check local deleted map, which contains the most
@@ -1105,7 +1089,7 @@ public final class NodeDocument extends
continue;
}
- if (isRevisionNewer(context, entry.getKey(), baseRevision)) {
+ if (baseRevision.isRevisionNewer(entry.getKey())) {
boolean newerDeleted = Boolean.parseBoolean(entry.getValue());
if (!allowConflictingDeleteChange || op.isDelete() != newerDeleted) {
return true;
@@ -1127,11 +1111,11 @@ public final class NodeDocument extends
continue;
}
// was this property touched after baseRevision?
- for (Revision rev : getChanges(name, baseRevision, context)) {
+ for (Revision rev : getChanges(name, baseRevision)) {
if (rev.equals(commitRevision)) {
continue;
}
- if (isRevisionNewer(context, rev, baseRevision)) {
+ if (baseRevision.isRevisionNewer(rev)) {
return true;
}
}
@@ -1203,7 +1187,7 @@ public final class NodeDocument extends
*/
@Nonnull
public Iterable<UpdateOp> split(@Nonnull RevisionContext context,
- @Nonnull Revision head) {
+ @Nonnull RevisionVector head) {
return SplitOperations.forDocument(this, context, head, NUM_REVS_THRESHOLD);
}
@@ -1551,13 +1535,11 @@ public final class NodeDocument extends
*
* @param property the name of the property.
* @param min the lower bound revision (exclusive).
- * @param context the revision context.
* @return changes back to {@code min} revision.
*/
@Nonnull
Iterable<Revision> getChanges(@Nonnull final String property,
- @Nonnull final Revision min,
- @Nonnull final RevisionContext context) {
+ @Nonnull final RevisionVector min) {
return new Iterable<Revision>() {
@Override
public Iterator<Revision> iterator() {
@@ -1567,7 +1549,7 @@ public final class NodeDocument extends
clusterIds.add(r.getClusterId());
}
for (Range r : getPreviousRanges().values()) {
- if (isRevisionNewer(context, r.high, min)) {
+ if (min.isRevisionNewer(r.high)) {
clusterIds.add(r.high.getClusterId());
}
}
@@ -1577,7 +1559,7 @@ public final class NodeDocument extends
protected Revision computeNext() {
while (unfiltered.hasNext()) {
Revision next = unfiltered.next();
- if (isRevisionNewer(context, next, min)) {
+ if (min.isRevisionNewer(next)) {
return next;
} else {
// further revisions with this clusterId
@@ -1769,33 +1751,85 @@ public final class NodeDocument extends
//----------------------------< internal >----------------------------------
+ private LastRevs createLastRevs(@Nonnull RevisionVector readRevision,
+ @Nonnull Map<Revision, String> validRevisions,
+ @Nullable Branch branch,
+ @Nullable Revision pendingLastRev) {
+ LastRevs lastRevs = new LastRevs(getLastRev(), readRevision, branch);
+ // overlay with unsaved last modified from this instance
+ lastRevs.update(pendingLastRev);
+ // collect clusterIds
+ SortedSet<Revision> mostRecentChanges = Sets.newTreeSet(REVERSE);
+ mostRecentChanges.addAll(getLocalRevisions().keySet());
+ mostRecentChanges.addAll(getLocalCommitRoot().keySet());
+ Set<Integer> clusterIds = Sets.newHashSet();
+ for (Revision r : getLocalRevisions().keySet()) {
+ clusterIds.add(r.getClusterId());
+ }
+ for (Revision r : getLocalCommitRoot().keySet()) {
+ clusterIds.add(r.getClusterId());
+ }
+ for (Revision r : mostRecentChanges) {
+ if (!clusterIds.contains(r.getClusterId())) {
+ // already found most recent change from this cluster node
+ continue;
+ }
+ String commitValue = validRevisions.get(r);
+ if (commitValue == null) {
+ commitValue = resolveCommitValue(r);
+ }
+ if (commitValue == null) {
+ continue;
+ }
+ // resolve revision
+ Revision commitRev = resolveCommitRevision(r, commitValue);
+ if (Utils.isCommitted(commitValue)) {
+ lastRevs.update(commitRev);
+ clusterIds.remove(r.getClusterId());
+ } else if (branch != null) {
+ Revision branchRev = commitRev.asBranchRevision();
+ if (branch.containsCommit(branchRev)) {
+ lastRevs.updateBranch(branchRev);
+ clusterIds.remove(r.getClusterId());
+ }
+ }
+ }
+ return lastRevs;
+ }
+
+ private String resolveCommitValue(Revision revision) {
+ NodeDocument commitRoot = getCommitRoot(revision);
+ if (commitRoot == null) {
+ return null;
+ }
+ return commitRoot.getCommitValue(revision);
+ }
+
/**
* Returns {@code true} if the given {@code revision} is more recent or
* equal to the committed revision in {@code valueMap}. This method assumes
* the given {@code revision} is committed.
*
- * @param context the revision context.
* @param valueMap the value map sorted most recent first.
* @param revision a committed revision.
* @return if {@code revision} is the most recent committed revision in the
* {@code valueMap}.
*/
- private boolean isMostRecentCommitted(RevisionContext context,
- SortedMap<Revision, String> valueMap,
+ private boolean isMostRecentCommitted(SortedMap<Revision, String> valueMap,
Revision revision) {
if (valueMap.isEmpty()) {
return true;
}
// shortcut when revision is the first key
Revision first = valueMap.firstKey();
- if (!isRevisionNewer(context, first, revision)) {
+ if (first.compareRevisionTimeThenClusterId(revision) <= 0) {
return true;
}
// need to check commit status
for (Revision r : valueMap.keySet()) {
Revision c = getCommitRevision(r);
if (c != null) {
- return !isRevisionNewer(context, c, revision);
+ return c.compareRevisionTimeThenClusterId(revision) <= 0;
}
}
// no committed revision found in valueMap
@@ -1803,34 +1837,6 @@ public final class NodeDocument extends
}
/**
- * Returns {@code true} if the two revisions are ambiguous. That is, they
- * are from different cluster nodes and the comparison of the two revision
- * depends on the seen at revision and is different when just comparing the
- * timestamps of the revisions.
- *
- * @param context the revision context.
- * @param r1 the first revision.
- * @param r2 the second revision.
- * @return {@code true} if ambiguous, {@code false} otherwise.
- */
- static boolean revisionAreAmbiguous(@Nonnull RevisionContext context,
- @Nonnull Revision r1,
- @Nonnull Revision r2) {
- if (r1.getClusterId() == r2.getClusterId()) {
- return false;
- }
- int c1 = context.getRevisionComparator().compare(r1, r2);
- int c2 = r1.compareTo(r2);
- if (c1 == 0) {
- return c2 == 0;
- } else if (c1 < 0) {
- return c2 >= 0;
- } else {
- return c2 <= 0;
- }
- }
-
- /**
* Returns the commit root document for the given revision. This may either
* be this document or another one.
*
@@ -1922,7 +1928,7 @@ public final class NodeDocument extends
private boolean isCommitted(@Nonnull RevisionContext context,
@Nonnull Revision revision,
@Nullable String commitValue,
- @Nonnull Revision readRevision) {
+ @Nonnull RevisionVector readRevision) {
if (commitValue == null) {
commitValue = getCommitValue(revision);
}
@@ -1936,17 +1942,18 @@ public final class NodeDocument extends
revision = resolveCommitRevision(revision, commitValue);
// readRevision is not from a branch
// compare resolved revision as is
- return !isRevisionNewer(context, revision, readRevision);
+ return !readRevision.isRevisionNewer(revision);
} else {
// on same merged branch?
- if (commitValue.equals(getCommitValue(readRevision.asTrunkRevision()))) {
+ if (commitValue.equals(getCommitValue(readRevision.getBranchRevision().asTrunkRevision()))) {
// compare unresolved revision
- return !isRevisionNewer(context, revision, readRevision);
+ return !readRevision.isRevisionNewer(revision);
}
}
} else {
// branch commit (not merged)
- if (Revision.fromString(commitValue).getClusterId() != context.getClusterId()) {
+ RevisionVector branchCommit = RevisionVector.fromString(commitValue);
+ if (branchCommit.getBranchRevision().getClusterId() != context.getClusterId()) {
// this is an unmerged branch commit from another cluster node,
// hence never visible to us
return false;
@@ -1978,70 +1985,61 @@ public final class NodeDocument extends
private static boolean includeRevision(RevisionContext context,
Revision x,
- Revision requestRevision) {
- Branch b = context.getBranches().getBranch(x);
+ RevisionVector readRevision) {
+ Branch b = null;
+ if (x.getClusterId() == context.getClusterId()) {
+ RevisionVector branchRev = new RevisionVector(x).asBranchRevision(context.getClusterId());
+ b = context.getBranches().getBranch(branchRev);
+ }
if (b != null) {
- // only include if requested revision is also a branch revision
+ // only include if read revision is also a branch revision
// with a history including x
- if (b.containsCommit(requestRevision)) {
+ if (readRevision.isBranch()
+ && b.containsCommit(readRevision.getBranchRevision())) {
// in same branch, include if the same revision or
- // requestRevision is newer
- return x.equalsIgnoreBranch(requestRevision)
- || isRevisionNewer(context, requestRevision, x);
+ // readRevision is newer
+ return !readRevision.isRevisionNewer(x);
}
// not part of branch identified by requestedRevision
return false;
}
// assert: x is not a branch commit
- b = context.getBranches().getBranch(requestRevision);
+ b = context.getBranches().getBranch(readRevision);
if (b != null) {
- // reset requestRevision to branch base revision to make
+ // reset readRevision to branch base revision to make
// sure we don't include revisions committed after branch
// was created
- requestRevision = b.getBase(requestRevision);
+ readRevision = b.getBase(readRevision.getBranchRevision());
}
- return context.getRevisionComparator().compare(requestRevision, x) >= 0;
+ return !readRevision.isRevisionNewer(x);
}
/**
- * Get the latest property value that is larger or equal the min revision,
- * and smaller or equal the readRevision revision. The returned value will
- * provide the revision when the value was set between the {@code min} and
- * {@code readRevision}. The returned value will have a {@code null} value
- * contained if there is no valid change within the given range. In this
- * case the associated revision is {@code min} or {@code readRevision} if
- * no {@code min} is provided.
+ * Get the latest property value smaller or equal the readRevision revision.
*
* @param valueMap the sorted revision-value map
- * @param min the minimum revision (null meaning unlimited)
* @param readRevision the maximum revision
* @param validRevisions map of revision to commit value considered valid
* against the given readRevision.
* @param lastRevs to keep track of the most recent modification.
* @return the latest value from the {@code readRevision} point of view.
*/
- @Nonnull
+ @CheckForNull
private Value getLatestValue(@Nonnull RevisionContext context,
@Nonnull Map<Revision, String> valueMap,
- @Nullable Revision min,
- @Nonnull Revision readRevision,
+ @Nonnull RevisionVector readRevision,
@Nonnull Map<Revision, String> validRevisions,
@Nonnull LastRevs lastRevs) {
for (Map.Entry<Revision, String> entry : valueMap.entrySet()) {
Revision propRev = entry.getKey();
String commitValue = validRevisions.get(propRev);
if (commitValue == null) {
- // resolve revision
- NodeDocument commitRoot = getCommitRoot(propRev);
- if (commitRoot == null) {
- continue;
- }
- commitValue = commitRoot.getCommitValue(propRev);
- if (commitValue == null) {
- continue;
- }
+ commitValue = resolveCommitValue(propRev);
}
-
+ if (commitValue == null) {
+ continue;
+ }
+ // resolve revision
Revision commitRev = resolveCommitRevision(propRev, commitValue);
if (Utils.isCommitted(commitValue)) {
lastRevs.update(commitRev);
@@ -2050,17 +2048,11 @@ public final class NodeDocument extends
lastRevs.updateBranch(commitRev.asBranchRevision());
}
- if (min != null && isRevisionNewer(context, min, commitRev)) {
- continue;
- }
if (isValidRevision(context, propRev, commitValue, readRevision, validRevisions)) {
- // TODO: need to check older revisions as well?
return new Value(commitRev, entry.getValue());
}
}
-
- Revision r = min != null ? min : readRevision;
- return new Value(r, null);
+ return null;
}
@Override
Modified: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/PathRev.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/PathRev.java?rev=1723532&r1=1723531&r2=1723532&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/PathRev.java (original)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/PathRev.java Thu Jan 7 12:46:35 2016
@@ -21,6 +21,7 @@ package org.apache.jackrabbit.oak.plugin
import javax.annotation.Nonnull;
import org.apache.jackrabbit.oak.cache.CacheValue;
+import org.apache.jackrabbit.oak.commons.StringUtils;
import static com.google.common.base.Preconditions.checkNotNull;
@@ -32,18 +33,18 @@ public final class PathRev implements Ca
private final String path;
- private final Revision revision;
+ private final RevisionVector revision;
- public PathRev(@Nonnull String path, @Nonnull Revision revision) {
+ public PathRev(@Nonnull String path, @Nonnull RevisionVector revision) {
this.path = checkNotNull(path);
this.revision = checkNotNull(revision);
}
@Override
public int getMemory() {
- return 24 // shallow size
- + 40 + path.length() * 2 // path
- + 32; // revision
+ return 24 // shallow size
+ + StringUtils.estimateMemoryUsage(path) // path
+ + revision.getMemory(); // revision
}
//----------------------------< Object >------------------------------------
@@ -76,7 +77,8 @@ public final class PathRev implements Ca
public static PathRev fromString(String s) {
int index = s.lastIndexOf('@');
- return new PathRev(s.substring(0, index), Revision.fromString(s.substring(index + 1)));
+ return new PathRev(s.substring(0, index),
+ RevisionVector.fromString(s.substring(index + 1)));
}
public int compareTo(PathRev b) {
Modified: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/Revision.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/Revision.java?rev=1723532&r1=1723531&r2=1723532&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/Revision.java (original)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/Revision.java Thu Jan 7 12:46:35 2016
@@ -16,16 +16,7 @@
*/
package org.apache.jackrabbit.oak.plugins.document;
-import java.util.ArrayList;
-import java.util.Comparator;
-import java.util.List;
-import java.util.Map;
-import java.util.TreeSet;
-import java.util.concurrent.ConcurrentHashMap;
-import java.util.concurrent.ConcurrentMap;
-
-import javax.annotation.Nonnull;
-
+import org.apache.jackrabbit.oak.cache.CacheValue;
import org.apache.jackrabbit.oak.plugins.document.util.Utils;
import org.apache.jackrabbit.oak.stats.Clock;
@@ -34,7 +25,9 @@ import static com.google.common.base.Pre
/**
* A revision.
*/
-public class Revision {
+public final class Revision implements CacheValue {
+
+ static final int SHALLOW_MEMORY_USAGE = 32;
private static volatile long lastTimestamp;
@@ -339,7 +332,7 @@ public class Revision {
* Returns a revision with the same timestamp, counter and clusterId as this
* revision and the branch flag set to <code>false</code>.
*
- * @return trunkrevision with this timestamp, counter and clusterId.
+ * @return trunk revision with this timestamp, counter and clusterId.
*/
public Revision asTrunkRevision() {
if (!isBranch()) {
@@ -370,379 +363,12 @@ public class Revision {
r.branch == this.branch;
}
- public boolean equalsIgnoreBranch(Revision other) {
- if (this == other) {
- return true;
- } else if (other == null) {
- return false;
- }
- return other.timestamp == this.timestamp &&
- other.counter == this.counter &&
- other.clusterId == this.clusterId;
- }
-
public int getClusterId() {
return clusterId;
}
- /**
- * Revision ranges allow to compare revisions ids of different cluster instances. A
- * range tells when a list of revisions from a certain cluster instance was seen by
- * the current process.
- */
- static class RevisionRange {
-
- /**
- * The newest revision for the given cluster instance and time.
- */
- Revision revision;
-
- /**
- * The (local) revision; the time when this revision was seen by this
- * cluster instance.
- */
- Revision seenAt;
-
- @Override
- public String toString() {
- return revision + ":" + seenAt;
- }
-
- }
-
- /**
- * A facility that is able to compare revisions of different cluster instances.
- * It contains a map of revision ranges.
- */
- public static class RevisionComparator implements Comparator<Revision> {
-
- static final Revision NEWEST = new Revision(Long.MAX_VALUE, 0, 0);
-
- static final Revision FUTURE = new Revision(Long.MAX_VALUE, Integer.MAX_VALUE, 0);
-
- /**
- * The map of cluster instances to lists of revision ranges.
- */
- private final ConcurrentMap<Integer, List<RevisionRange>> map =
- new ConcurrentHashMap<Integer, List<RevisionRange>>();
-
- /**
- * When comparing revisions that occurred before, the timestamp is ignored.
- */
- private long oldestTimestamp;
-
- /**
- * The cluster node id of the current cluster node. Revisions
- * from this cluster node that are newer than the newest range
- * (new local revisions)
- * are considered to be the newest revisions overall.
- */
- private final int currentClusterNodeId;
-
- RevisionComparator(int currentClusterNodId) {
- this.currentClusterNodeId = currentClusterNodId;
- }
-
- /**
- * Forget the order of older revisions. After calling this method, when comparing
- * revisions that happened before the given value, the timestamp order is used
- * (time dilation is ignored for older events).
- *
- * @param timestamp the time in milliseconds (see {@link #getCurrentTimestamp})
- */
- public void purge(long timestamp) {
- oldestTimestamp = timestamp;
- for (int clusterId : map.keySet()) {
- while (true) {
- List<RevisionRange> list = map.get(clusterId);
- List<RevisionRange> newList = purge(list);
- if (newList == null) {
- // retry if removing was not successful
- if (map.remove(clusterId, list)) {
- break;
- }
- } else if (newList == list) {
- // no change
- break;
- } else {
- // retry if replacing was not successful
- if (map.replace(clusterId, list, newList)) {
- break;
- }
- }
- }
- }
- }
-
- private List<RevisionRange> purge(List<RevisionRange> list) {
- int i = 0;
- for (; i < list.size(); i++) {
- RevisionRange r = list.get(i);
- if (r.seenAt.getTimestamp() > oldestTimestamp) {
- break;
- }
- }
- if (i > list.size() - 1) {
- return null;
- } else if (i == 0) {
- return list;
- }
- return new ArrayList<RevisionRange>(list.subList(i, list.size()));
- }
-
- /**
- * Add the revision to the top of the queue for the given cluster node.
- * If an entry for this timestamp already exists, it is replaced.
- *
- * @param r the revision
- * @param seenAt the (local) revision where this revision was seen here
- */
- public void add(Revision r, Revision seenAt) {
- int clusterId = r.getClusterId();
- while (true) {
- List<RevisionRange> list = map.get(clusterId);
- List<RevisionRange> newList;
- if (list == null) {
- newList = new ArrayList<RevisionRange>();
- } else {
- RevisionRange last = list.get(list.size() - 1);
- if (last.seenAt.equals(seenAt)) {
- // replace existing
- if (r.compareRevisionTime(last.revision) > 0) {
- // but only if newer
- last.revision = r;
- }
- return;
- }
- if (last.revision.compareRevisionTime(r) > 0) {
- throw new IllegalArgumentException(
- "Can not add an earlier revision: " + last.revision + " > " + r +
- "; current cluster node is " + currentClusterNodeId);
- }
- newList = new ArrayList<RevisionRange>(list);
- }
- RevisionRange range = new RevisionRange();
- range.seenAt = seenAt;
- range.revision = r;
- newList.add(range);
- if (list == null) {
- if (map.putIfAbsent(clusterId, newList) == null) {
- return;
- }
- } else {
- if (map.replace(clusterId, list, newList)) {
- return;
- }
- }
- }
- }
-
- /**
- * Returns the minimum timestamp of the most recent revisions from all
- * active cluster nodes as seen from the given {@code revision}.
- *
- * @param revision a revision.
- * @param inactive map of cluster nodes considered inactive.
- * @return the minimum timestamp.
- */
- public long getMinimumTimestamp(@Nonnull Revision revision,
- @Nonnull Map<Integer, Long> inactive) {
- long timestamp = checkNotNull(revision).getTimestamp();
- Revision seenAt = getRevisionSeen(revision);
- if (seenAt == null) {
- // already purged
- return timestamp;
- }
- // go through all known cluster nodes
- for (Map.Entry<Integer, List<RevisionRange>> e : map.entrySet()) {
- if (revision.getClusterId() == currentClusterNodeId
- && e.getKey() == currentClusterNodeId) {
- // range and revision is for current cluster node
- // no need to adjust timestamp
- continue;
- }
- List<RevisionRange> list = e.getValue();
- RevisionRange range;
- for (int i = list.size() - 1; i >= 0; i--) {
- range = list.get(i);
- if (range.seenAt.compareRevisionTimeThenClusterId(seenAt) <= 0) {
- // found newest range older or equal the given seenAt
- // check if the cluster node is still active
- Long inactiveSince = inactive.get(range.revision.getClusterId());
- if (inactiveSince != null
- && revision.getTimestamp() > inactiveSince
- && range.revision.getTimestamp() < inactiveSince) {
- // ignore, because the revision is after the
- // cluster node became inactive and the most recent
- // range is before it became inactive
- } else {
- timestamp = Math.min(timestamp, range.revision.getTimestamp());
- }
- break;
- }
- }
- }
- return timestamp;
- }
-
- @Override
- public int compare(Revision o1, Revision o2) {
- if (o1.getClusterId() == o2.getClusterId()) {
- return o1.compareRevisionTime(o2);
- }
- Revision range1 = getRevisionSeen(o1);
- Revision range2 = getRevisionSeen(o2);
- if (range1 == FUTURE && range2 == FUTURE) {
- return o1.compareTo(o2);
- }
- if (range1 == null && range2 == null) {
- return o1.compareTo(o2);
- }
- if (range1 == null) {
- return -1;
- } else if (range2 == null) {
- return 1;
- }
- int comp = range1.compareTo(range2);
- if (comp != 0) {
- return comp;
- }
- return o1.compareTo(o2);
- }
-
- /**
- * Get the seen-at revision from the revision range.
- * <p>
- * <ul>
- * <li>
- * {@code null} if the revision is older than the earliest range
- * and the revision timestamp is less than or equal the time
- * of the last {@link #purge(long)} (see also
- * {@link #oldestTimestamp}).
- * </li>
- * <li>
- * if the revision is newer than the lower bound of the newest
- * range, then {@link #NEWEST} is returned for a local cluster
- * revision and {@link #FUTURE} for a foreign cluster revision.
- * </li>
- * <li>
- * if the revision matches the lower seen-at bound of a range,
- * then this seen-at revision is returned.
- * </li>
- * <li>
- * otherwise the lower bound seen-at revision of next higher
- * range is returned.
- * </li>
- * </ul>
- *
- * Below is a graph for a revision comparison example as seen from one
- * cluster node with some known revision ranges. Revision ranges less
- * than or equal r2-0-0 have been purged and there are known ranges for
- * cluster node 1 (this cluster node) and cluster node 2 (some other
- * cluster node).
- * <pre>
- * View from cluster node 1:
- *
- * purge r3-0-1 r5-0-2 r7-0-1
- * Ë
Ë
Ë
Ë
- * ---+---------+---------+---------+---------+---------
- * r1-0-0 r2-0-0 r3-0-0 r4-0-0 r5-0-0
- *
- * ^
- * r1-0-1 -> null (1)
- *
- * ^
- * r4-0-2 -> r4-0-0 (2)
- *
- * ^
- * r3-0-1 -> r3-0-0 (3)
- *
- * ^
- * r6-0-2 -> FUTURE (4)
- *
- * ^
- * r9-0-1 -> NEWEST (5)
- * </pre>
- * <ol>
- * <li>older than earliest range and purge time</li>
- * <li>seen-at of next higher range</li>
- * <li>seen-at of matching lower bound of range</li>
- * <li>foreign revision is newer than most recent range</li>
- * <li>local revision is newer than most recent range</li>
- * </ol>
- * This gives the following revision ordering:
- * <pre>
- * r1-0-1 < r3-0-1 < r-4-0-2 < r9-0-1 < r6-0-2
- * </pre>
- *
- * @param r the revision
- * @return the seen-at revision or {@code null} if the revision is older
- * than the earliest range and purge time.
- */
- Revision getRevisionSeen(Revision r) {
- List<RevisionRange> list = map.get(r.getClusterId());
- if (list == null) {
- if (r.getTimestamp() <= oldestTimestamp) {
- // old revision with already purged range
- return null;
- }
- if (r.getClusterId() != currentClusterNodeId) {
- // this is from a cluster node we did not see yet
- // see also OAK-1170
- return FUTURE;
- }
- return null;
- }
- // search from latest backward
- // (binary search could be used, but we expect most queries
- // at the end of the list)
- RevisionRange range = null;
- for (int i = list.size() - 1; i >= 0; i--) {
- range = list.get(i);
- int compare = r.compareRevisionTime(range.revision);
- if (compare == 0) {
- return range.seenAt;
- } else if (compare > 0) {
- if (i == list.size() - 1) {
- // newer than the newest range
- if (r.getClusterId() == currentClusterNodeId) {
- // newer than all others, except for FUTURE
- return NEWEST;
- } else {
- // happens in the future (not visible yet)
- return FUTURE;
- }
- } else {
- // there is a newer range
- return list.get(i + 1).seenAt;
- }
- }
- }
- if (range != null && r.getTimestamp() > oldestTimestamp) {
- // revision is older than earliest range and after purge
- // timestamp. return seen-at revision of earliest range.
- return range.seenAt;
- }
- return null;
- }
-
- @Override
- public String toString() {
- StringBuilder buff = new StringBuilder();
- for (int clusterId : new TreeSet<Integer>(map.keySet())) {
- int i = 0;
- buff.append(clusterId).append(":");
- for (RevisionRange r : map.get(clusterId)) {
- if (i++ % 4 == 0) {
- buff.append('\n');
- }
- buff.append(" ").append(r);
- }
- buff.append("\n");
- }
- return buff.toString();
- }
-
+ @Override
+ public int getMemory() {
+ return SHALLOW_MEMORY_USAGE;
}
-
}
Modified: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/RevisionContext.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/RevisionContext.java?rev=1723532&r1=1723531&r2=1723532&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/RevisionContext.java (original)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/RevisionContext.java Thu Jan 7 12:46:35 2016
@@ -37,11 +37,6 @@ public interface RevisionContext {
UnsavedModifications getPendingModifications();
/**
- * @return the revision comparator.
- */
- Comparator<Revision> getRevisionComparator();
-
- /**
* @return the cluster id of the local DocumentMK instance.
*/
int getClusterId();
@@ -50,7 +45,7 @@ public interface RevisionContext {
* @return the current head revision.
*/
@Nonnull
- Revision getHeadRevision();
+ RevisionVector getHeadRevision();
/**
* @return a new revision for the local document node store instance.
Added: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/RevisionVector.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/RevisionVector.java?rev=1723532&view=auto
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/RevisionVector.java (added)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/RevisionVector.java Thu Jan 7 12:46:35 2016
@@ -0,0 +1,499 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.jackrabbit.oak.plugins.document;
+
+import java.util.Arrays;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Set;
+
+import javax.annotation.CheckForNull;
+import javax.annotation.Nonnull;
+
+import com.google.common.collect.AbstractIterator;
+import com.google.common.collect.Iterators;
+import com.google.common.collect.Lists;
+import com.google.common.collect.PeekingIterator;
+import com.google.common.collect.Sets;
+import com.google.common.primitives.Ints;
+
+import org.apache.jackrabbit.oak.cache.CacheValue;
+import org.apache.jackrabbit.oak.plugins.document.util.Utils;
+
+import static com.google.common.base.Preconditions.checkNotNull;
+import static com.google.common.collect.Iterables.toArray;
+import static com.google.common.collect.Iterators.peekingIterator;
+import static com.google.common.collect.Lists.newArrayListWithCapacity;
+import static java.util.Arrays.sort;
+
+/**
+ * A vector of revisions. Instances of this class are immutable and methods
+ * like {@link #update(Revision)} create a new instance as needed.
+ *
+ * This class implements {@link Comparable}. While
+ * {@link #compareTo(RevisionVector)} provides a total order of revision
+ * vector instances, this order is unrelated to when changes are visible in
+ * a DocumentNodeStore cluster. Do not use this method to determine whether
+ * a given revision vector happened before or after another!
+ */
+public final class RevisionVector implements Iterable<Revision>, Comparable<RevisionVector>, CacheValue {
+
+ private final static RevisionVector EMPTY = new RevisionVector();
+
+ private final Revision[] revisions;
+
+ private RevisionVector(@Nonnull Revision[] revisions,
+ boolean checkUniqueClusterIds,
+ boolean sort) {
+ checkNotNull(revisions);
+ if (checkUniqueClusterIds) {
+ checkUniqueClusterIds(revisions);
+ }
+ if (sort) {
+ sort(revisions, RevisionComparator.INSTANCE);
+ }
+ this.revisions = revisions;
+ }
+
+ public RevisionVector(@Nonnull Revision... revisions) {
+ this(Arrays.copyOf(revisions, revisions.length), true, true);
+ }
+
+ public RevisionVector(@Nonnull Iterable<Revision> revisions) {
+ this(toArray(revisions, Revision.class), true, true);
+ }
+
+ public RevisionVector(@Nonnull Set<Revision> revisions) {
+ this(toArray(revisions, Revision.class), false, true);
+ }
+
+ /**
+ * Creates a new revision vector with based on this vector and the given
+ * {@code revision}. If this vector contains a revision with the same
+ * clusterId as {@code revision}, the returned vector will have the
+ * revision updated with the given one. Otherwise the returned vector will
+ * have all elements of this vector plus the given {@code revision}.
+ *
+ * @param revision the revision set to use for the new vector.
+ * @return the resulting revision vector.
+ */
+ public RevisionVector update(@Nonnull Revision revision) {
+ checkNotNull(revision);
+ Revision existing = null;
+ int i;
+ for (i = 0; i < revisions.length; i++) {
+ Revision r = revisions[i];
+ if (r.getClusterId() == revision.getClusterId()) {
+ existing = r;
+ break;
+ }
+ }
+ Revision[] newRevisions;
+ boolean sort;
+ if (existing != null) {
+ if (revision.equals(existing)) {
+ return this;
+ } else {
+ newRevisions = Arrays.copyOf(revisions, revisions.length);
+ newRevisions[i] = revision;
+ sort = false;
+ }
+ } else {
+ newRevisions = new Revision[revisions.length + 1];
+ System.arraycopy(revisions, 0, newRevisions, 0, revisions.length);
+ newRevisions[revisions.length] = revision;
+ sort = true;
+ }
+ return new RevisionVector(newRevisions, false, sort);
+ }
+
+ /**
+ * Returns a RevisionVector without the revision element with the given
+ * {@code clusterId}.
+ *
+ * @param clusterId the clusterId of the revision to remove.
+ * @return RevisionVector without the revision element.
+ */
+ public RevisionVector remove(int clusterId) {
+ if (revisions.length == 0) {
+ return this;
+ }
+ boolean found = false;
+ for (Revision r : revisions) {
+ if (r.getClusterId() == clusterId) {
+ found = true;
+ break;
+ } else if (r.getClusterId() > clusterId) {
+ break;
+ }
+ }
+ if (!found) {
+ return this;
+ }
+ Revision[] revs = new Revision[revisions.length - 1];
+ int idx = 0;
+ for (Revision r : revisions) {
+ if (r.getClusterId() != clusterId) {
+ revs[idx++] = r;
+ }
+ }
+ return new RevisionVector(revs, false, false);
+ }
+
+ /**
+ * Calculates the parallel minimum of this and the given {@code vector}.
+ *
+ * @param vector the other vector.
+ * @return the parallel minimum of the two.
+ */
+ public RevisionVector pmin(@Nonnull RevisionVector vector) {
+ // optimize single revision case
+ if (revisions.length == 1 && vector.revisions.length == 1) {
+ if (revisions[0].getClusterId() == vector.revisions[0].getClusterId()) {
+ return revisions[0].compareRevisionTime(vector.revisions[0]) < 0 ? this : vector;
+ } else {
+ return EMPTY;
+ }
+ }
+ int capacity = Math.min(revisions.length, vector.revisions.length);
+ List<Revision> pmin = newArrayListWithCapacity(capacity);
+ PeekingIterator<Revision> it = peekingIterator(vector.iterator());
+ for (Revision r : revisions) {
+ Revision other = peekRevision(it, r.getClusterId());
+ if (other != null) {
+ if (other.getClusterId() == r.getClusterId()) {
+ pmin.add(Utils.min(r, other));
+ }
+ } else {
+ break;
+ }
+ }
+ return new RevisionVector(toArray(pmin, Revision.class), false, false);
+ }
+
+ /**
+ * Calculates the parallel maximum of this and the given {@code vector}.
+ *
+ * @param vector the other vector.
+ * @return the parallel maximum of the two.
+ */
+ public RevisionVector pmax(@Nonnull RevisionVector vector) {
+ // optimize single revision case
+ if (revisions.length == 1 && vector.revisions.length == 1) {
+ if (revisions[0].getClusterId() == vector.revisions[0].getClusterId()) {
+ return revisions[0].compareRevisionTime(vector.revisions[0]) > 0 ? this : vector;
+ } else {
+ return new RevisionVector(revisions[0], vector.revisions[0]);
+ }
+ }
+ int capacity = Math.max(revisions.length, vector.revisions.length);
+ List<Revision> pmax = newArrayListWithCapacity(capacity);
+ PeekingIterator<Revision> it = peekingIterator(vector.iterator());
+ for (Revision r : revisions) {
+ while (it.hasNext() && it.peek().getClusterId() < r.getClusterId()) {
+ pmax.add(it.next());
+ }
+ Revision other = peekRevision(it, r.getClusterId());
+ if (other != null && other.getClusterId() == r.getClusterId()) {
+ pmax.add(Utils.max(r, other));
+ it.next();
+ } else {
+ // other does not have a revision with r.clusterId
+ pmax.add(r);
+ }
+ }
+ // add remaining
+ Iterators.addAll(pmax, it);
+ return new RevisionVector(toArray(pmax, Revision.class), false, false);
+ }
+
+ /**
+ * Returns the difference of this and the other vector. The returned vector
+ * contains all revisions of this vector that are not contained in the
+ * other vector.
+ *
+ * @param vector the other vector.
+ * @return the difference of the two vectors.
+ */
+ public RevisionVector difference(RevisionVector vector) {
+ List<Revision> diff = newArrayListWithCapacity(revisions.length);
+ PeekingIterator<Revision> it = peekingIterator(vector.iterator());
+ for (Revision r : revisions) {
+ Revision other = peekRevision(it, r.getClusterId());
+ if (!r.equals(other)) {
+ diff.add(r);
+ }
+ }
+ return new RevisionVector(toArray(diff, Revision.class), false, false);
+ }
+
+ /**
+ * Returns {@code true} if the given revision is newer than the revision
+ * element with the same clusterId in the vector. The given revision is
+ * also considered newer if there is no revision element with the same
+ * clusterId in this vector.
+ *
+ * @param revision the revision to check.
+ * @return {@code true} if considered newer, {@code false} otherwise.
+ */
+ public boolean isRevisionNewer(@Nonnull Revision revision) {
+ checkNotNull(revision);
+ for (Revision r : revisions) {
+ if (r.getClusterId() == revision.getClusterId()) {
+ return r.compareRevisionTime(revision) < 0;
+ } else if (r.getClusterId() > revision.getClusterId()) {
+ // revisions are sorted by clusterId ascending
+ break;
+ }
+ }
+ return true;
+ }
+
+ /**
+ * @return {@code true} if any of the revisions in this vector is a branch
+ * revision, {@code false} otherwise.
+ */
+ public boolean isBranch() {
+ for (Revision r : revisions) {
+ if (r.isBranch()) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ /**
+ * @return the first branch revision in this vector.
+ * @throws IllegalStateException if this vector does not contain a branch
+ * revision.
+ */
+ @Nonnull
+ public Revision getBranchRevision() {
+ for (Revision r : revisions) {
+ if (r.isBranch()) {
+ return r;
+ }
+ }
+ throw new IllegalStateException(
+ "This vector does not contain a branch revision: " + this);
+ }
+
+ /**
+ * Returns the revision element with the given clusterId or {@code null}
+ * if there is no such revision in this vector.
+ *
+ * @param clusterId a clusterId.
+ * @return the revision element with the given clusterId or {@code null}
+ * if none exists.
+ */
+ public Revision getRevision(int clusterId) {
+ for (Revision r : revisions) {
+ int cmp = Ints.compare(r.getClusterId(), clusterId);
+ if (cmp == 0) {
+ return r;
+ } else if (cmp > 0) {
+ break;
+ }
+ }
+ return null;
+ }
+
+ /**
+ * Returns a string representation of this revision vector, which can be
+ * parsed again by {@link #fromString(String)}.
+ *
+ * @return a string representation of this revision vector.
+ */
+ public String asString() {
+ StringBuilder sb = new StringBuilder();
+ String comma = "";
+ for (Revision r : revisions) {
+ sb.append(comma);
+ comma = ",";
+ r.toStringBuilder(sb);
+ }
+ return sb.toString();
+ }
+
+ /**
+ * Creates a revision vector from a string representation as returned by
+ * {@link #asString()}.
+ *
+ * @param s the string representation of a revision vector.
+ * @return the revision vector.
+ * @throws IllegalArgumentException if the string is malformed
+ */
+ public static RevisionVector fromString(String s) {
+ List<Revision> revisions = Lists.newArrayListWithCapacity(3);
+ for (String str : s.split(",")) {
+ revisions.add(Revision.fromString(str));
+ }
+ return new RevisionVector(revisions);
+ }
+
+ /**
+ * Returns a revision vector where all revision elements are turned into
+ * trunk revisions.
+ *
+ * @return a trunk representation of this revision vector.
+ */
+ public RevisionVector asTrunkRevision() {
+ if (!isBranch()) {
+ return this;
+ }
+ Revision[] revs = new Revision[revisions.length];
+ for (int i = 0; i < revisions.length; i++) {
+ revs[i] = revisions[i].asTrunkRevision();
+ }
+ return new RevisionVector(revs, false, false);
+ }
+
+ /**
+ * A clone of this revision vector with the revision for the given
+ * clusterId set to a branch revision.
+ *
+ * @param clusterId the clusterId of the revision to be turned into a branch
+ * revision.
+ * @return the revision vector with the branch revision.
+ * @throws IllegalArgumentException if there is no revision element with the
+ * given clusterId.
+ */
+ public RevisionVector asBranchRevision(int clusterId) {
+ boolean found = false;
+ Revision[] revs = new Revision[revisions.length];
+ for (int i = 0; i < revisions.length; i++) {
+ Revision r = revisions[i];
+ if (r.getClusterId() == clusterId) {
+ r = r.asBranchRevision();
+ found = true;
+ }
+ revs[i] = r;
+ }
+ if (!found) {
+ throw new IllegalArgumentException("RevisionVector [" + asString() +
+ "] does not have a revision for clusterId " + clusterId);
+ }
+ return new RevisionVector(revs, false, false);
+ }
+
+ //------------------------< CacheValue >------------------------------------
+
+ @Override
+ public int getMemory() {
+ return 32 // shallow size
+ + revisions.length * (Revision.SHALLOW_MEMORY_USAGE + 4);
+ }
+
+ //------------------------< Comparable >------------------------------------
+
+ @Override
+ public int compareTo(@Nonnull RevisionVector other) {
+ Iterator<Revision> it = other.iterator();
+ for (Revision r : revisions) {
+ if (!it.hasNext()) {
+ return 1;
+ }
+ Revision otherRev = it.next();
+ int cmp = -Ints.compare(r.getClusterId(), otherRev.getClusterId());
+ if (cmp != 0) {
+ return cmp;
+ }
+ cmp = r.compareTo(otherRev);
+ if (cmp != 0) {
+ return cmp;
+ }
+ }
+ return it.hasNext() ? -1 : 0;
+ }
+
+ //-------------------------< Iterable >-------------------------------------
+
+ @Override
+ public Iterator<Revision> iterator() {
+ return new AbstractIterator<Revision>() {
+ int i = 0;
+ @Override
+ protected Revision computeNext() {
+ if (i >= revisions.length) {
+ return endOfData();
+ } else {
+ return revisions[i++];
+ }
+ }
+ };
+ }
+
+ //--------------------------< Object >--------------------------------------
+
+ @Override
+ public String toString() {
+ return asString();
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (obj instanceof RevisionVector) {
+ RevisionVector other = (RevisionVector) obj;
+ return Arrays.equals(revisions, other.revisions);
+ }
+ return false;
+ }
+
+ @Override
+ public int hashCode() {
+ return Arrays.hashCode(revisions);
+ }
+
+ //-------------------------< internal >-------------------------------------
+
+ @CheckForNull
+ private Revision peekRevision(PeekingIterator<Revision> it,
+ int minClusterId) {
+ while (it.hasNext() && it.peek().getClusterId() < minClusterId) {
+ it.next();
+ }
+ return it.hasNext() ? it.peek() : null;
+ }
+
+ private static void checkUniqueClusterIds(Revision[] revisions)
+ throws IllegalArgumentException {
+ if (revisions.length < 2) {
+ return;
+ }
+ Set<Integer> known = Sets.newHashSetWithExpectedSize(revisions.length);
+ for (Revision revision : revisions) {
+ if (!known.add(revision.getClusterId())) {
+ throw new IllegalArgumentException(
+ "Multiple revisions with clusterId " + revision.getClusterId());
+ }
+ }
+ }
+
+ /**
+ * Compares revisions according to their clusterId.
+ */
+ private static final class RevisionComparator implements Comparator<Revision> {
+
+ private static final Comparator<Revision> INSTANCE = new RevisionComparator();
+
+ @Override
+ public int compare(Revision o1, Revision o2) {
+ return Ints.compare(o1.getClusterId(), o2.getClusterId());
+ }
+ }
+}
Propchange: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/RevisionVector.java
------------------------------------------------------------------------------
svn:eol-style = native
Modified: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/SplitOperations.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/SplitOperations.java?rev=1723532&r1=1723531&r2=1723532&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/SplitOperations.java (original)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/SplitOperations.java Thu Jan 7 12:46:35 2016
@@ -20,7 +20,6 @@ package org.apache.jackrabbit.oak.plugin
import java.util.ArrayList;
import java.util.Collections;
-import java.util.Comparator;
import java.util.List;
import java.util.Map;
import java.util.NavigableMap;
@@ -55,7 +54,6 @@ import static org.apache.jackrabbit.oak.
import static org.apache.jackrabbit.oak.plugins.document.NodeDocument.setPrevious;
import static org.apache.jackrabbit.oak.plugins.document.util.Utils.PROPERTY_OR_DELETED;
import static org.apache.jackrabbit.oak.plugins.document.util.Utils.getPreviousIdFor;
-import static org.apache.jackrabbit.oak.plugins.document.util.Utils.isRevisionNewer;
/**
* Utility class to create document split operations.
@@ -86,13 +84,13 @@ class SplitOperations {
private SplitOperations(@Nonnull NodeDocument doc,
@Nonnull RevisionContext context,
- @Nonnull Revision headRevision,
+ @Nonnull RevisionVector headRevision,
int numRevsThreshold) {
this.doc = checkNotNull(doc);
this.context = checkNotNull(context);
this.path = doc.getPath();
this.id = doc.getId();
- this.headRevision = checkNotNull(headRevision);
+ this.headRevision = checkNotNull(headRevision).getRevision(context.getClusterId());
this.numRevsThreshold = numRevsThreshold;
}
@@ -117,7 +115,7 @@ class SplitOperations {
@Nonnull
static List<UpdateOp> forDocument(@Nonnull NodeDocument doc,
@Nonnull RevisionContext context,
- @Nonnull Revision headRevision,
+ @Nonnull RevisionVector headRevision,
int numRevsThreshold) {
if (doc.isSplitDocument()) {
throw new IllegalArgumentException(
@@ -208,7 +206,7 @@ class SplitOperations {
*/
private void collectRevisionsAndCommitRoot() {
NavigableMap<Revision, String> revisions =
- new TreeMap<Revision, String>(context.getRevisionComparator());
+ new TreeMap<Revision, String>(StableRevisionComparator.INSTANCE);
for (Map.Entry<Revision, String> entry : doc.getLocalRevisions().entrySet()) {
if (splitRevs.contains(entry.getKey())) {
revisions.put(entry.getKey(), entry.getValue());
@@ -232,7 +230,7 @@ class SplitOperations {
}
committedChanges.put(REVISIONS, revisions);
NavigableMap<Revision, String> commitRoot =
- new TreeMap<Revision, String>(context.getRevisionComparator());
+ new TreeMap<Revision, String>(StableRevisionComparator.INSTANCE);
boolean mostRecent = true;
for (Map.Entry<Revision, String> entry : doc.getLocalCommitRoot().entrySet()) {
Revision r = entry.getKey();
@@ -269,10 +267,10 @@ class SplitOperations {
Revision h = null;
Revision l = null;
for (Range r : entry.getValue()) {
- if (h == null || isRevisionNewer(context, r.high, h)) {
+ if (h == null || r.high.compareRevisionTime(h) > 0) {
h = r.high;
}
- if (l == null || isRevisionNewer(context, l, r.low)) {
+ if (l == null || l.compareRevisionTime(r.low) > 0) {
l = r.low;
}
removePrevious(main, r);
@@ -391,7 +389,7 @@ class SplitOperations {
Set<Revision> changes) {
for (String property : filter(doc.keySet(), PROPERTY_OR_DELETED)) {
NavigableMap<Revision, String> splitMap
- = new TreeMap<Revision, String>(context.getRevisionComparator());
+ = new TreeMap<Revision, String>(StableRevisionComparator.INSTANCE);
committedLocally.put(property, splitMap);
Map<Revision, String> valueMap = doc.getLocalMap(property);
// collect committed changes of this cluster node
@@ -411,10 +409,9 @@ class SplitOperations {
}
private boolean isGarbage(Revision rev) {
- Comparator<Revision> comp = context.getRevisionComparator();
// use headRevision as passed in the constructor instead
// of the head revision from the RevisionContext. see OAK-3081
- if (comp.compare(headRevision, rev) <= 0) {
+ if (headRevision.compareRevisionTime(rev) <= 0) {
// this may be an in-progress commit
return false;
}
@@ -489,13 +486,13 @@ class SplitOperations {
}
private void trackHigh(Revision r) {
- if (high == null || isRevisionNewer(context, r, high)) {
+ if (high == null || r.compareRevisionTime(high) > 0) {
high = r;
}
}
private void trackLow(Revision r) {
- if (low == null || isRevisionNewer(context, low, r)) {
+ if (low == null || low.compareRevisionTime(r) > 0) {
low = r;
}
}
Modified: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/StableRevisionComparator.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/StableRevisionComparator.java?rev=1723532&r1=1723531&r2=1723532&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/StableRevisionComparator.java (original)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/StableRevisionComparator.java Thu Jan 7 12:46:35 2016
@@ -22,9 +22,7 @@ import java.util.Comparator;
/**
* <code>StableRevisionComparator</code> implements a revision comparator, which
* is only based on stable information available in the two revisions presented
- * to this comparator. This is different from {@link Revision.RevisionComparator},
- * which also takes the time into account when a foreign revision (from another
- * cluster nodes) was first seen. This class is used in sorted collections where
+ * to this comparator. This class is used in sorted collections where
* revision keys must have a stable ordering independent from the time when
* a revision was seen.
* <p>
Modified: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/TieredDiffCache.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/TieredDiffCache.java?rev=1723532&r1=1723531&r2=1723532&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/TieredDiffCache.java (original)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/TieredDiffCache.java Thu Jan 7 12:46:35 2016
@@ -38,8 +38,8 @@ class TieredDiffCache extends DiffCache
}
@Override
- public String getChanges(@Nonnull Revision from,
- @Nonnull Revision to,
+ public String getChanges(@Nonnull RevisionVector from,
+ @Nonnull RevisionVector to,
@Nonnull String path,
@Nullable Loader loader) {
// check local first without loader
@@ -60,7 +60,7 @@ class TieredDiffCache extends DiffCache
*/
@Nonnull
@Override
- public Entry newEntry(@Nonnull Revision from, @Nonnull Revision to, boolean local) {
+ public Entry newEntry(@Nonnull RevisionVector from, @Nonnull RevisionVector to, boolean local) {
if (local) {
return localCache.newEntry(from, to, true);
} else {
Modified: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/UnmergedBranches.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/UnmergedBranches.java?rev=1723532&r1=1723531&r2=1723532&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/UnmergedBranches.java (original)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/UnmergedBranches.java Thu Jan 7 12:46:35 2016
@@ -17,7 +17,6 @@
package org.apache.jackrabbit.oak.plugins.document;
import java.lang.ref.ReferenceQueue;
-import java.util.Comparator;
import java.util.List;
import java.util.SortedSet;
import java.util.TreeSet;
@@ -64,15 +63,6 @@ class UnmergedBranches {
private final AtomicBoolean initialized = new AtomicBoolean(false);
/**
- * The revision comparator.
- */
- private final Comparator<Revision> comparator;
-
- UnmergedBranches(@Nonnull Comparator<Revision> comparator) {
- this.comparator = checkNotNull(comparator);
- }
-
- /**
* Initialize with un-merged branches from <code>store</code> for this
* <code>clusterId</code>.
*
@@ -112,14 +102,14 @@ class UnmergedBranches {
* or {@code initial} is not a branch revision.
*/
@Nonnull
- Branch create(@Nonnull Revision base,
+ Branch create(@Nonnull RevisionVector base,
@Nonnull Revision initial,
@Nullable Object guard) {
checkArgument(!checkNotNull(base).isBranch(),
"base is not a trunk revision: %s", base);
checkArgument(checkNotNull(initial).isBranch(),
"initial is not a branch revision: %s", initial);
- SortedSet<Revision> commits = new TreeSet<Revision>(comparator);
+ SortedSet<Revision> commits = new TreeSet<Revision>(StableRevisionComparator.INSTANCE);
commits.add(initial);
Branch b = new Branch(commits, base, queue, guard);
branches.add(b);
@@ -134,9 +124,13 @@ class UnmergedBranches {
* @return the branch containing the given revision or <code>null</code>.
*/
@CheckForNull
- Branch getBranch(@Nonnull Revision r) {
+ Branch getBranch(@Nonnull RevisionVector r) {
+ if (!r.isBranch()) {
+ return null;
+ }
+ Revision branchRev = r.getBranchRevision();
for (Branch b : branches) {
- if (b.containsCommit(r)) {
+ if (b.containsCommit(branchRev)) {
return b;
}
}
Modified: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/VersionGarbageCollector.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/VersionGarbageCollector.java?rev=1723532&r1=1723531&r2=1723532&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/VersionGarbageCollector.java (original)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/VersionGarbageCollector.java Thu Jan 7 12:46:35 2016
@@ -85,7 +85,7 @@ public class VersionGarbageCollector {
Stopwatch sw = Stopwatch.createStarted();
VersionGCStats stats = new VersionGCStats();
final long oldestRevTimeStamp = nodeStore.getClock().getTime() - maxRevisionAgeInMillis;
- final Revision headRevision = nodeStore.getHeadRevision();
+ final RevisionVector headRevision = nodeStore.getHeadRevision();
log.info("Starting revision garbage collection. Revisions older than [{}] will be " +
"removed", Utils.timestampToString(oldestRevTimeStamp));
@@ -121,7 +121,7 @@ public class VersionGarbageCollector {
}
private void collectDeletedDocuments(VersionGCStats stats,
- Revision headRevision,
+ RevisionVector headRevision,
long oldestRevTimeStamp)
throws IOException {
int docsTraversed = 0;
@@ -190,13 +190,13 @@ public class VersionGarbageCollector {
*/
private class DeletedDocsGC implements Closeable {
- private final Revision headRevision;
+ private final RevisionVector headRevision;
private final StringSort docIdsToDelete = newStringSort();
private final StringSort prevDocIdsToDelete = newStringSort();
private final Set<String> exclude = Sets.newHashSet();
private boolean sorted = false;
- public DeletedDocsGC(@Nonnull Revision headRevision) {
+ public DeletedDocsGC(@Nonnull RevisionVector headRevision) {
this.headRevision = checkNotNull(headRevision);
}