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 ju...@apache.org on 2013/07/18 12:30:04 UTC
svn commit: r1504418 - in
/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment:
MapLeaf.java MapRecord.java Template.java
Author: jukka
Date: Thu Jul 18 10:30:03 2013
New Revision: 1504418
URL: http://svn.apache.org/r1504418
Log:
OAK-630: SegmentMK: Implement compareAgainstBaseState
Optimize MapLeaf-to-MapLeaf comparisons
Modified:
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/MapLeaf.java
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/MapRecord.java
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/Template.java
Modified: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/MapLeaf.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/MapLeaf.java?rev=1504418&r1=1504417&r2=1504418&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/MapLeaf.java (original)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/MapLeaf.java Thu Jul 18 10:30:03 2013
@@ -96,6 +96,66 @@ class MapLeaf extends MapRecord {
return getMapEntries().values();
}
+ @Override
+ boolean compare(MapRecord base, MapDiff diff) {
+ if (base instanceof MapLeaf) {
+ return compare((MapLeaf) base, diff);
+ } else {
+ return super.compare(base, diff);
+ }
+ }
+
+ private boolean compare(MapLeaf before, MapDiff diff) {
+ Segment bs = before.getSegment();
+ int bi = 0;
+
+ MapLeaf after = this;
+ Segment as = after.getSegment();
+ int ai = 0;
+
+ while (ai < after.size) {
+ int afterHash = after.getHash(as, ai);
+ String afterKey = after.getKey(as, ai);
+ RecordId afterValue = after.getValue(as, ai);
+
+ while (bi < before.size
+ && (before.getHash(bs, bi) < afterHash
+ || (before.getHash(bs, bi) == afterHash
+ && before.getKey(bs, bi).compareTo(afterKey) < 0))) {
+ if (!diff.entryDeleted(
+ before.getKey(bs, bi), before.getValue(bs, bi))) {
+ return false;
+ }
+ bi++;
+ }
+
+ if (bi < before.size
+ && before.getHash(bs, bi) == afterHash
+ && before.getKey(bs, bi).equals(afterKey)) {
+ RecordId beforeValue = before.getValue(bs, bi);
+ if (!afterValue.equals(beforeValue)
+ && !diff.entryChanged(afterKey, beforeValue, afterValue)) {
+ return false;
+ }
+ bi++;
+ } else if (!diff.entryAdded(afterKey, afterValue)) {
+ return false;
+ }
+
+ ai++;
+ }
+
+ while (bi < before.size) {
+ if (!diff.entryDeleted(
+ before.getKey(bs, bi), before.getValue(bs, bi))) {
+ return false;
+ }
+ bi++;
+ }
+
+ return true;
+ }
+
//-----------------------------------------------------------< private >--
private Iterator<String> getKeyIterator() {
Modified: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/MapRecord.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/MapRecord.java?rev=1504418&r1=1504417&r2=1504418&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/MapRecord.java (original)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/MapRecord.java Thu Jul 18 10:30:03 2013
@@ -19,9 +19,11 @@ package org.apache.jackrabbit.oak.plugin
import static com.google.common.base.Preconditions.checkElementIndex;
import static com.google.common.base.Preconditions.checkNotNull;
import static com.google.common.base.Preconditions.checkPositionIndex;
+import static com.google.common.collect.Sets.newHashSet;
import static java.lang.Integer.highestOneBit;
import static java.lang.Integer.numberOfTrailingZeros;
+import java.util.Set;
import java.util.UUID;
abstract class MapRecord extends Record {
@@ -109,6 +111,40 @@ abstract class MapRecord extends Record
abstract Iterable<MapEntry> getEntries();
+ interface MapDiff {
+ boolean entryAdded(String key, RecordId after);
+ boolean entryChanged(String key, RecordId before, RecordId after);
+ boolean entryDeleted(String key, RecordId before);
+ }
+
+ boolean compare(MapRecord that, MapDiff diff) {
+ Set<String> keys = newHashSet();
+ for (MapEntry entry : getEntries()) {
+ String name = entry.getName();
+ RecordId thisId = entry.getValue();
+ RecordId thatId = that.getEntry(name);
+ if (thatId == null) {
+ if (!diff.entryAdded(name, thisId)) {
+ return false;
+ }
+ } else if (!thisId.equals(thatId)) {
+ if (!diff.entryChanged(name, thatId, thisId)) {
+ return false;
+ }
+ }
+ keys.add(name);
+ }
+ for (MapEntry entry : that.getEntries()) {
+ String name = entry.getName();
+ if (!keys.contains(name)) {
+ if (!diff.entryDeleted(name, entry.getValue())) {
+ return false;
+ }
+ }
+ }
+ return true;
+ }
+
//------------------------------------------------------------< Object >--
@Override
Modified: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/Template.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/Template.java?rev=1504418&r1=1504417&r2=1504418&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/Template.java (original)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/Template.java Thu Jul 18 10:30:03 2013
@@ -36,6 +36,7 @@ import javax.annotation.Nonnull;
import org.apache.jackrabbit.oak.api.PropertyState;
import org.apache.jackrabbit.oak.api.Type;
import org.apache.jackrabbit.oak.plugins.memory.MemoryChildNodeEntry;
+import org.apache.jackrabbit.oak.plugins.segment.MapRecord.MapDiff;
import org.apache.jackrabbit.oak.spi.state.ChildNodeEntry;
import org.apache.jackrabbit.oak.spi.state.NodeState;
import org.apache.jackrabbit.oak.spi.state.NodeStateDiff;
@@ -395,9 +396,9 @@ public class Template {
}
public boolean compareAgainstBaseState(
- SegmentStore store, RecordId afterId,
+ final SegmentStore store, RecordId afterId,
Template beforeTemplate, RecordId beforeId,
- NodeStateDiff diff) {
+ final NodeStateDiff diff) {
checkNotNull(store);
checkNotNull(afterId);
checkNotNull(beforeTemplate);
@@ -517,34 +518,27 @@ public class Template {
}
} else {
// TODO: Leverage the HAMT data structure for the comparison
- Set<String> baseChildNodes = new HashSet<String>();
- for (ChildNodeEntry beforeCNE
- : beforeTemplate.getChildNodeEntries(store, beforeId)) {
- String name = beforeCNE.getName();
- NodeState beforeChild = beforeCNE.getNodeState();
- NodeState afterChild = getChildNode(name, store, afterId);
- if (!afterChild.exists()) {
- if (!diff.childNodeDeleted(name, beforeChild)) {
- return false;
- }
- } else {
- baseChildNodes.add(name);
- if (!afterChild.equals(beforeChild)) {
- if (!diff.childNodeChanged(name, beforeChild, afterChild)) {
- return false;
- }
- }
+ MapRecord afterMap = getChildNodeMap(store, afterId);
+ MapRecord beforeMap = beforeTemplate.getChildNodeMap(store, beforeId);
+ return afterMap.compare(beforeMap, new MapDiff() {
+ @Override
+ public boolean entryAdded(String key, RecordId after) {
+ return diff.childNodeAdded(
+ key, new SegmentNodeState(store, after));
+ }
+ @Override
+ public boolean entryChanged(
+ String key, RecordId before, RecordId after) {
+ SegmentNodeState b = new SegmentNodeState(store, before);
+ SegmentNodeState a = new SegmentNodeState(store, after);
+ return a.equals(b) || diff.childNodeChanged(key, b, a);
+ }
+ @Override
+ public boolean entryDeleted(String key, RecordId before) {
+ return diff.childNodeDeleted(
+ key, new SegmentNodeState(store, before));
}
- }
- for (ChildNodeEntry afterChild
- : getChildNodeEntries(store, afterId)) {
- String name = afterChild.getName();
- if (!baseChildNodes.contains(name)) {
- if (!diff.childNodeAdded(name, afterChild.getNodeState())) {
- return false;
- }
- }
- }
+ });
}
return true;