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); }
