jackrabbit-oak-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From ju...@apache.org
Subject svn commit: r1504418 - in /jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment: MapLeaf.java MapRecord.java Template.java
Date Thu, 18 Jul 2013 10:30:04 GMT
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;



Mime
View raw message