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/10/03 16:05:50 UTC
svn commit: r1528872 -
/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/MapLeaf.java
Author: jukka
Date: Thu Oct 3 14:05:50 2013
New Revision: 1528872
URL: http://svn.apache.org/r1528872
Log:
OAK-1031: SegmentMK: Fewer segment lookups
Streamline MapLeaf comparisons to reduce the number of reads
Modified:
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/MapLeaf.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=1528872&r1=1528871&r2=1528872&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 Oct 3 14:05:50 2013
@@ -20,6 +20,9 @@ import static com.google.common.base.Pre
import static com.google.common.base.Preconditions.checkNotNull;
import java.util.Arrays;
+import java.util.Iterator;
+
+import com.google.common.collect.ComparisonChain;
class MapLeaf extends MapRecord {
@@ -104,87 +107,68 @@ class MapLeaf extends MapRecord {
@Override
boolean compare(MapRecord base, MapDiff diff) {
if (base instanceof MapLeaf) {
- return compare((MapLeaf) base, diff);
+ return compare((MapLeaf) base, this, 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.getEntry(bs, bi))) {
+ //-----------------------------------------------------------< private >--
+
+ private static boolean compare(
+ MapLeaf before, MapLeaf after, MapDiff diff) {
+ Iterator<MapEntry> beforeEntries = before.getEntries().iterator();
+ Iterator<MapEntry> afterEntries = after.getEntries().iterator();
+
+ MapEntry beforeEntry = nextOrNull(beforeEntries);
+ MapEntry afterEntry = nextOrNull(afterEntries);
+ while (beforeEntry != null || afterEntry != null) {
+ int d = compare(beforeEntry, afterEntry);
+ if (d < 0) {
+ if (!diff.entryDeleted(beforeEntry)) {
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(
- before.getEntry(bs, bi),
- after.getEntry(as, ai))) {
+ beforeEntry = nextOrNull(beforeEntries);
+ } else if (d == 0) {
+ if (!diff.entryChanged(beforeEntry, afterEntry)) {
return false;
}
- bi++;
- } else if (!diff.entryAdded(after.getEntry(as, ai))) {
- return false;
- }
-
- ai++;
- }
-
- while (bi < before.size) {
- if (!diff.entryDeleted(before.getEntry(bs, bi))) {
- return false;
+ beforeEntry = nextOrNull(beforeEntries);
+ afterEntry = nextOrNull(afterEntries);
+ } else {
+ if (!diff.entryAdded(afterEntry)) {
+ return false;
+ }
+ afterEntry = nextOrNull(afterEntries);
}
- bi++;
}
return true;
}
- //-----------------------------------------------------------< private >--
-
- private MapEntry getEntry(Segment segment, int index) {
- checkNotNull(segment);
- RecordId key =
- segment.readRecordId(getOffset(4 + size * 4, index));
- RecordId value =
- segment.readRecordId(getOffset(4 + size * 4, size + index));
- return new MapEntry(segment, segment.readString(key), key, value);
- }
-
- private int getHash(Segment segment, int index) {
- return checkNotNull(segment).readInt(getOffset() + 4 + index * 4);
- }
-
- private String getKey(Segment segment, int index) {
- checkNotNull(segment);
- int offset = getOffset(4 + size * 4, index);
- return segment.readString(segment.readRecordId(offset));
+ private static int compare(MapEntry before, MapEntry after) {
+ if (before == null) {
+ // A null value signifies the end of the list of entries,
+ // which is why the return value here is a bit counter-intuitive
+ // (null > non-null). The idea is to make a virtual end-of-list
+ // sentinel value appear greater than any normal value.
+ return 1;
+ } else if (after == null) {
+ return -1; // see above
+ } else {
+ return ComparisonChain.start()
+ .compare(before.getHash(), after.getHash())
+ .compare(before.getName(), after.getName())
+ .result();
+ }
}
- private RecordId getValue(Segment segment, int index) {
- int offset = getOffset(4 + size * 4, size + index);
- return checkNotNull(segment).readRecordId(offset);
+ private static MapEntry nextOrNull(Iterator<MapEntry> iterator) {
+ if (iterator.hasNext()) {
+ return iterator.next();
+ } else {
+ return null;
+ }
}
}