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/02/22 16:58:02 UTC
svn commit: r1449084 - in /jackrabbit/oak/trunk/oak-core/src:
main/java/org/apache/jackrabbit/oak/plugins/segment/
test/java/org/apache/jackrabbit/oak/plugins/segment/
Author: jukka
Date: Fri Feb 22 15:58:02 2013
New Revision: 1449084
URL: http://svn.apache.org/r1449084
Log:
OAK-632: SegmentMK: Efficient updates of flat nodes
More cleanup and optimization of the HAMT code
Added:
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/MapEntry.java
Modified:
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/MapBranch.java
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/Segment.java
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/SegmentWriter.java
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/Template.java
jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/segment/RecordTest.java
Modified: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/MapBranch.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/MapBranch.java?rev=1449084&r1=1449083&r2=1449084&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/MapBranch.java (original)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/MapBranch.java Fri Feb 22 15:58:02 2013
@@ -21,14 +21,14 @@ import static com.google.common.base.Pre
import static com.google.common.collect.Iterables.concat;
import static com.google.common.collect.Iterables.transform;
import static java.lang.Integer.bitCount;
+import static java.util.Arrays.asList;
import static org.apache.jackrabbit.oak.plugins.segment.Segment.RECORD_ID_BYTES;
-import java.util.List;
+import java.util.Collections;
import javax.annotation.Nullable;
import com.google.common.base.Function;
-import com.google.common.collect.Lists;
class MapBranch extends MapRecord {
@@ -41,6 +41,22 @@ class MapBranch extends MapRecord {
this.bitmap = bitmap;
}
+ RecordId[] getBuckets() {
+ Segment segment = getSegment();
+ int offset = getOffset() + 8;
+
+ RecordId[] buckets = new RecordId[BUCKETS_PER_LEVEL];
+ for (int i = 0; i < buckets.length; i++) {
+ if ((bitmap & (1 << i)) != 0) {
+ buckets[i] = segment.readRecordId(offset);
+ offset += RECORD_ID_BYTES;
+ } else {
+ buckets[i] = null;
+ }
+ }
+ return buckets;
+ }
+
@Override
RecordId getEntry(String key) {
checkNotNull(key);
@@ -63,38 +79,33 @@ class MapBranch extends MapRecord {
@Override
Iterable<String> getKeys() {
return concat(transform(
- getBuckets(),
+ asList(getBuckets()),
new Function<RecordId, Iterable<String>>() {
@Override @Nullable
public Iterable<String> apply(@Nullable RecordId input) {
- return MapRecord.readMap(store, input).getKeys();
+ if (input != null) {
+ return MapRecord.readMap(store, input).getKeys();
+ } else {
+ return Collections.emptyList();
+ }
}
}));
}
@Override
- Iterable<Entry> getEntries() {
+ Iterable<MapEntry> getEntries() {
return concat(transform(
- getBuckets(),
- new Function<RecordId, Iterable<Entry>>() {
+ asList(getBuckets()),
+ new Function<RecordId, Iterable<MapEntry>>() {
@Override @Nullable
- public Iterable<Entry> apply(@Nullable RecordId input) {
- return MapRecord.readMap(store, input).getEntries();
+ public Iterable<MapEntry> apply(@Nullable RecordId input) {
+ if (input != null) {
+ return MapRecord.readMap(store, input).getEntries();
+ } else {
+ return Collections.emptyList();
+ }
}
}));
}
- private Iterable<RecordId> getBuckets() {
- int n = Integer.bitCount(bitmap);
- int p = getOffset() + 8;
- int q = p + n * RECORD_ID_BYTES;
- Segment segment = getSegment();
-
- List<RecordId> buckets = Lists.newArrayListWithCapacity(n);
- for (int o = p; o < q; o += RECORD_ID_BYTES) {
- buckets.add(segment.readRecordId(o));
- }
- return buckets;
- }
-
}
Added: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/MapEntry.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/MapEntry.java?rev=1449084&view=auto
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/MapEntry.java (added)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/MapEntry.java Fri Feb 22 15:58:02 2013
@@ -0,0 +1,95 @@
+/*
+ * 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.segment;
+
+import static com.google.common.base.Preconditions.checkNotNull;
+import static com.google.common.base.Preconditions.checkState;
+
+import java.util.Map;
+
+import javax.annotation.Nonnull;
+
+import org.apache.jackrabbit.oak.spi.state.AbstractChildNodeEntry;
+import org.apache.jackrabbit.oak.spi.state.NodeState;
+
+import com.google.common.collect.ComparisonChain;
+
+/**
+ * Representation of a single key-value entry in a map.
+ */
+class MapEntry extends AbstractChildNodeEntry
+ implements Map.Entry<RecordId, RecordId>, Comparable<MapEntry> {
+
+ private final SegmentStore store;
+
+ private final String name;
+
+ private final RecordId key;
+
+ private RecordId value;
+
+ MapEntry(SegmentStore store, String name, RecordId key, RecordId value) {
+ this.store = checkNotNull(store);
+ this.name = checkNotNull(name);
+ this.key = checkNotNull(key);
+ this.value = value;
+ }
+
+ //----------------------------------------------------< ChildNodeEntry >--
+
+ @Override @Nonnull
+ public String getName() {
+ return name;
+ }
+
+ @Override @Nonnull
+ public NodeState getNodeState() {
+ checkState(value != null);
+ return new SegmentNodeState(new SegmentReader(store), value);
+ }
+
+ //---------------------------------------------------------< Map.Entry >--
+
+ @Override
+ public RecordId getKey() {
+ return key;
+ }
+
+ @Override
+ public RecordId getValue() {
+ return value;
+ }
+
+ @Override
+ public RecordId setValue(RecordId value) {
+ RecordId old = this.value;
+ this.value = value;
+ return old;
+ }
+
+ //--------------------------------------------------------< Comparable >--
+
+ @Override
+ public int compareTo(MapEntry that) {
+ return ComparisonChain.start()
+ .compare(name.hashCode(), that.name.hashCode())
+ .compare(name, that.name)
+ .compare(value, that.value)
+ .result();
+ }
+
+}
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=1449084&r1=1449083&r2=1449084&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 Fri Feb 22 15:58:02 2013
@@ -21,17 +21,42 @@ import static com.google.common.base.Pre
import static org.apache.jackrabbit.oak.plugins.segment.Segment.RECORD_ID_BYTES;
import java.util.Iterator;
+import java.util.Map;
import java.util.NoSuchElementException;
+import com.google.common.collect.Maps;
+
class MapLeaf extends MapRecord {
MapLeaf(SegmentStore store, RecordId id, int size, int level) {
super(store, id, size, level);
- System.out.println(size + " " + level);
checkArgument(size != 0 || level == 0);
checkArgument(size <= BUCKETS_PER_LEVEL || level == MAX_NUMBER_OF_LEVELS);
}
+ Map<String, MapEntry> getMapEntries() {
+ RecordId[] keys = new RecordId[size];
+ RecordId[] values = new RecordId[size];
+
+ Segment segment = getSegment();
+ int offset = getOffset() + 4 + size * 4;
+ for (int i = 0; i < size; i++) {
+ keys[i] = segment.readRecordId(offset);
+ offset += RECORD_ID_BYTES;
+ }
+ for (int i = 0; i < size; i++) {
+ values[i] = segment.readRecordId(offset);
+ offset += RECORD_ID_BYTES;
+ }
+
+ Map<String, MapEntry> entries = Maps.newHashMapWithExpectedSize(size);
+ for (int i = 0; i < size; i++) {
+ String name = segment.readString(keys[i]);
+ entries.put(name, new MapEntry(store, name, keys[i], values[i]));
+ }
+ return entries;
+ }
+
@Override
RecordId getEntry(String key) {
checkNotNull(key);
@@ -67,13 +92,8 @@ class MapLeaf extends MapRecord {
}
@Override
- Iterable<Entry> getEntries() {
- return new Iterable<Entry>() {
- @Override
- public Iterator<Entry> iterator() {
- return getEntryIterator();
- }
- };
+ Iterable<MapEntry> getEntries() {
+ return getMapEntries().values();
}
//-----------------------------------------------------------< private >--
@@ -102,55 +122,14 @@ class MapLeaf extends MapRecord {
};
}
- private Iterator<Entry> getEntryIterator() {
- return new Iterator<Entry>() {
- private final Segment segment = getSegment();
- private int index = 0;
- @Override
- public boolean hasNext() {
- return index < size;
- }
- @Override
- public Entry next() {
- final int i = index++;
- if (i < size) {
- return new Entry() {
- @Override
- public String getKey() {
- return MapLeaf.this.getKey(segment, i);
- }
- @Override
- public RecordId getValue() {
- return MapLeaf.this.getValue(segment, i);
- }
- @Override
- public RecordId setValue(RecordId value) {
- throw new UnsupportedOperationException();
- }
- };
- } else {
- throw new NoSuchElementException();
- }
- }
- @Override
- public void remove() {
- throw new UnsupportedOperationException();
- }
- };
- }
-
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 * RECORD_ID_BYTES;
- RecordId id = checkNotNull(segment).readRecordId(offset);
- if (!segment.getSegmentId().equals(id.getSegmentId())) {
- // the string is stored in another segment
- segment = store.readSegment(id.getSegmentId());
- }
- return segment.readString(id.getOffset());
+ return segment.readString(segment.readRecordId(offset));
}
private RecordId getValue(Segment segment, int index) {
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=1449084&r1=1449083&r2=1449084&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 Fri Feb 22 15:58:02 2013
@@ -21,7 +21,6 @@ import static com.google.common.base.Pre
import static java.lang.Integer.highestOneBit;
import static java.lang.Integer.numberOfTrailingZeros;
-import java.util.Map;
import java.util.UUID;
abstract class MapRecord extends Record {
@@ -75,9 +74,6 @@ abstract class MapRecord extends Record
}
}
- public interface Entry extends Map.Entry<String, RecordId> {
- }
-
protected final SegmentStore store;
protected final int size;
@@ -111,22 +107,20 @@ abstract class MapRecord extends Record
abstract Iterable<String> getKeys();
- abstract Iterable<Entry> getEntries();
+ abstract Iterable<MapEntry> getEntries();
//------------------------------------------------------------< Object >--
@Override
public String toString() {
StringBuilder builder = null;
- for (Entry entry : getEntries()) {
+ for (MapEntry entry : getEntries()) {
if (builder == null) {
builder = new StringBuilder("{ ");
} else {
builder.append(", ");
}
- builder.append(entry.getKey());
- builder.append("=");
- builder.append(entry.getValue());
+ builder.append(entry);
}
if (builder == null) {
return "{}";
Modified: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/Segment.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/Segment.java?rev=1449084&r1=1449083&r2=1449084&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/Segment.java (original)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/Segment.java Fri Feb 22 15:58:02 2013
@@ -1,179 +1,188 @@
-/*
- * 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.segment;
-
-import static com.google.common.base.Preconditions.checkElementIndex;
-import static com.google.common.base.Preconditions.checkNotNull;
-import static com.google.common.base.Preconditions.checkPositionIndexes;
-
-import java.nio.ByteBuffer;
-import java.util.UUID;
-
-import com.google.common.cache.Weigher;
-
-class Segment {
-
- /**
- * Number of bytes used for storing a record identifier. One byte
- * is used for identifying the segment and two for the record offset
- * within that segment.
- */
- static final int RECORD_ID_BYTES = 1 + 2;
-
- /**
- * The limit on segment references within one segment. Since record
- * identifiers use one byte to indicate the referenced segment, a single
- * segment can hold references to up to 256 segments.
- */
- static final int SEGMENT_REFERENCE_LIMIT = 1 << 8; // 256
-
- /**
- * The number of bytes (or bits of address space) to use for the
- * alignment boundary of segment records.
- */
- static final int RECORD_ALIGN_BITS = 2;
- static final int RECORD_ALIGN_BYTES = 1 << RECORD_ALIGN_BITS; // 4
-
- /**
- * Maximum segment size. Record identifiers are stored as three-byte
- * sequences with the first byte indicating the segment and the next
- * two the offset within that segment. Since all records are aligned
- * at four-byte boundaries, the two bytes can address up to 256kB of
- * record data.
- */
- static final int MAX_SEGMENT_SIZE = 1 << (16 + RECORD_ALIGN_BITS); // 256kB
-
- /**
- * The size limit for small values. The variable length of small values
- * is encoded as a single byte with the high bit as zero, which gives us
- * seven bits for encoding the length of the value.
- */
- static final int SMALL_LIMIT = 1 << 7;
-
- /**
- * The size limit for medium values. The variable length of medium values
- * is encoded as two bytes with the highest bits of the first byte set to
- * one and zero, which gives us 14 bits for encoding the length of the
- * value. And since small values are never stored as medium ones, we can
- * extend the size range to cover that many longer values.
- */
- static final int MEDIUM_LIMIT = 1 << (16-2) + SMALL_LIMIT;
-
- static final Weigher<UUID, Segment> WEIGHER =
- new Weigher<UUID, Segment>() {
- @Override
- public int weigh(UUID key, Segment value) {
- return value.size();
- }
- };
-
- private final SegmentStore store;
-
- private final UUID uuid;
-
- private final byte[] data;
-
- private final UUID[] uuids;
-
- private final OffsetCache<String> strings = new OffsetCache<String>() {
- @Override
- protected String load(int offset) {
- return new SegmentReader(store).readString(
- new RecordId(uuid, offset));
- }
- };
-
- private final OffsetCache<Template> templates = new OffsetCache<Template>() {
- @Override
- protected Template load(int offset) {
- return null;
- }
- };
-
- Segment(SegmentStore store, UUID uuid, byte[] data, UUID[] uuids) {
- this.store = store;
- this.uuid = uuid;
- this.data = data;
- this.uuids = uuids;
- }
-
- public UUID getSegmentId() {
- return uuid;
- }
-
- public byte[] getData() {
- return data;
- }
-
- public UUID[] getUUIDs() {
- return uuids;
- }
-
- public int size() {
- return data.length;
- }
-
- public byte readByte(int position) {
- int pos = position - (MAX_SEGMENT_SIZE - data.length);
- checkElementIndex(pos, data.length);
- return data[pos];
- }
-
- /**
- * Reads the given number of bytes starting from the given position
- * in this segment.
- *
- * @param position position within segment
- * @param buffer target buffer
- * @param offset offset within target buffer
- * @param length number of bytes to read
- */
- public void readBytes(int position, byte[] buffer, int offset, int length) {
- int pos = position - (MAX_SEGMENT_SIZE - data.length);
- checkPositionIndexes(pos, pos + length, data.length);
- checkNotNull(buffer);
- checkPositionIndexes(offset, offset + length, buffer.length);
-
- System.arraycopy(data, pos, buffer, offset, length);
- }
-
- RecordId readRecordId(int position) {
- int pos = position - (MAX_SEGMENT_SIZE - data.length);
- checkPositionIndexes(pos, pos + RECORD_ID_BYTES, data.length);
- return new RecordId(
- uuids[data[pos] & 0xff],
- (data[pos + 1] & 0xff) << (8 + Segment.RECORD_ALIGN_BITS)
- | (data[pos + 2] & 0xff) << Segment.RECORD_ALIGN_BITS);
- }
-
- public int readInt(int position) {
- int pos = position - (MAX_SEGMENT_SIZE - data.length);
- checkPositionIndexes(pos, pos + 4, data.length);
- return ByteBuffer.wrap(data).getInt(pos);
- }
-
- public long readLong(int position) {
- int pos = position - (Segment.MAX_SEGMENT_SIZE - data.length);
- checkPositionIndexes(pos, pos + 8, data.length);
- return ByteBuffer.wrap(data).getLong(pos);
- }
-
- String readString(int offset) {
- return strings.get(offset);
- }
-
-}
+/*
+ * 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.segment;
+
+import static com.google.common.base.Preconditions.checkElementIndex;
+import static com.google.common.base.Preconditions.checkNotNull;
+import static com.google.common.base.Preconditions.checkPositionIndexes;
+
+import java.nio.ByteBuffer;
+import java.util.UUID;
+
+import com.google.common.cache.Weigher;
+
+class Segment {
+
+ /**
+ * Number of bytes used for storing a record identifier. One byte
+ * is used for identifying the segment and two for the record offset
+ * within that segment.
+ */
+ static final int RECORD_ID_BYTES = 1 + 2;
+
+ /**
+ * The limit on segment references within one segment. Since record
+ * identifiers use one byte to indicate the referenced segment, a single
+ * segment can hold references to up to 256 segments.
+ */
+ static final int SEGMENT_REFERENCE_LIMIT = 1 << 8; // 256
+
+ /**
+ * The number of bytes (or bits of address space) to use for the
+ * alignment boundary of segment records.
+ */
+ static final int RECORD_ALIGN_BITS = 2;
+ static final int RECORD_ALIGN_BYTES = 1 << RECORD_ALIGN_BITS; // 4
+
+ /**
+ * Maximum segment size. Record identifiers are stored as three-byte
+ * sequences with the first byte indicating the segment and the next
+ * two the offset within that segment. Since all records are aligned
+ * at four-byte boundaries, the two bytes can address up to 256kB of
+ * record data.
+ */
+ static final int MAX_SEGMENT_SIZE = 1 << (16 + RECORD_ALIGN_BITS); // 256kB
+
+ /**
+ * The size limit for small values. The variable length of small values
+ * is encoded as a single byte with the high bit as zero, which gives us
+ * seven bits for encoding the length of the value.
+ */
+ static final int SMALL_LIMIT = 1 << 7;
+
+ /**
+ * The size limit for medium values. The variable length of medium values
+ * is encoded as two bytes with the highest bits of the first byte set to
+ * one and zero, which gives us 14 bits for encoding the length of the
+ * value. And since small values are never stored as medium ones, we can
+ * extend the size range to cover that many longer values.
+ */
+ static final int MEDIUM_LIMIT = 1 << (16-2) + SMALL_LIMIT;
+
+ static final Weigher<UUID, Segment> WEIGHER =
+ new Weigher<UUID, Segment>() {
+ @Override
+ public int weigh(UUID key, Segment value) {
+ return value.size();
+ }
+ };
+
+ private final SegmentStore store;
+
+ private final UUID uuid;
+
+ private final byte[] data;
+
+ private final UUID[] uuids;
+
+ private final OffsetCache<String> strings = new OffsetCache<String>() {
+ @Override
+ protected String load(int offset) {
+ return new SegmentReader(store).readString(
+ new RecordId(uuid, offset));
+ }
+ };
+
+ private final OffsetCache<Template> templates = new OffsetCache<Template>() {
+ @Override
+ protected Template load(int offset) {
+ return null;
+ }
+ };
+
+ Segment(SegmentStore store, UUID uuid, byte[] data, UUID[] uuids) {
+ this.store = store;
+ this.uuid = uuid;
+ this.data = data;
+ this.uuids = uuids;
+ }
+
+ public UUID getSegmentId() {
+ return uuid;
+ }
+
+ public byte[] getData() {
+ return data;
+ }
+
+ public UUID[] getUUIDs() {
+ return uuids;
+ }
+
+ public int size() {
+ return data.length;
+ }
+
+ public byte readByte(int position) {
+ int pos = position - (MAX_SEGMENT_SIZE - data.length);
+ checkElementIndex(pos, data.length);
+ return data[pos];
+ }
+
+ /**
+ * Reads the given number of bytes starting from the given position
+ * in this segment.
+ *
+ * @param position position within segment
+ * @param buffer target buffer
+ * @param offset offset within target buffer
+ * @param length number of bytes to read
+ */
+ public void readBytes(int position, byte[] buffer, int offset, int length) {
+ int pos = position - (MAX_SEGMENT_SIZE - data.length);
+ checkPositionIndexes(pos, pos + length, data.length);
+ checkNotNull(buffer);
+ checkPositionIndexes(offset, offset + length, buffer.length);
+
+ System.arraycopy(data, pos, buffer, offset, length);
+ }
+
+ RecordId readRecordId(int position) {
+ int pos = position - (MAX_SEGMENT_SIZE - data.length);
+ checkPositionIndexes(pos, pos + RECORD_ID_BYTES, data.length);
+ return new RecordId(
+ uuids[data[pos] & 0xff],
+ (data[pos + 1] & 0xff) << (8 + Segment.RECORD_ALIGN_BITS)
+ | (data[pos + 2] & 0xff) << Segment.RECORD_ALIGN_BITS);
+ }
+
+ public int readInt(int position) {
+ int pos = position - (MAX_SEGMENT_SIZE - data.length);
+ checkPositionIndexes(pos, pos + 4, data.length);
+ return ByteBuffer.wrap(data).getInt(pos);
+ }
+
+ public long readLong(int position) {
+ int pos = position - (Segment.MAX_SEGMENT_SIZE - data.length);
+ checkPositionIndexes(pos, pos + 8, data.length);
+ return ByteBuffer.wrap(data).getLong(pos);
+ }
+
+ String readString(int offset) {
+ return strings.get(offset);
+ }
+
+ String readString(RecordId id) {
+ checkNotNull(id);
+ Segment segment = this;
+ if (!uuid.equals(id.getSegmentId())) {
+ segment = store.readSegment(id.getSegmentId());
+ }
+ return segment.readString(id.getOffset());
+ }
+
+}
Modified: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/SegmentWriter.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/SegmentWriter.java?rev=1449084&r1=1449083&r2=1449084&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/SegmentWriter.java (original)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/SegmentWriter.java Fri Feb 22 15:58:02 2013
@@ -17,9 +17,12 @@
package org.apache.jackrabbit.oak.plugins.segment;
import static com.google.common.base.Preconditions.checkArgument;
+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.base.Preconditions.checkPositionIndexes;
import static com.google.common.base.Preconditions.checkState;
+import static org.apache.jackrabbit.oak.plugins.segment.MapRecord.BUCKETS_PER_LEVEL;
import java.io.ByteArrayInputStream;
import java.io.IOException;
@@ -45,7 +48,6 @@ import org.apache.jackrabbit.oak.spi.sta
import org.apache.jackrabbit.oak.spi.state.NodeState;
import com.google.common.base.Charsets;
-import com.google.common.base.Preconditions;
import com.google.common.collect.Lists;
import com.google.common.collect.Maps;
import com.google.common.io.ByteStreams;
@@ -173,70 +175,53 @@ public class SegmentWriter {
writeInt((int) value);
}
- private synchronized RecordId writeListBucket(List<RecordId> bucket) {
- RecordId bucketId = prepare(0, bucket);
- for (RecordId id : bucket) {
- writeRecordId(id);
- }
- return bucketId;
- }
+ private synchronized MapLeaf writeLeaf(
+ int level, Collection<MapEntry> entries) {
+ checkNotNull(entries);
- private class MapEntry implements Comparable<MapEntry> {
- private final int hashCode;
- private final String string;
- private final RecordId key;
- private final RecordId value;
-
- MapEntry(String key, RecordId value) {
- this.hashCode = key.hashCode();
- this.string = key;
- this.key = writeString(key);
- this.value = value;
- }
-
- @Override
- public int compareTo(MapEntry that) {
- // int diff = Integer.compare(hashCode, that.hashCode);
- int diff = hashCode == that.hashCode ? 0 : hashCode < that.hashCode ? -1 : 1;
- if (diff == 0) {
- diff = key.compareTo(that.key);
- }
- if (diff == 0) {
- diff = value.compareTo(that.value);
- }
- return diff;
- }
-
- public boolean equals(Object object) {
- if (this == object) {
- return true;
- } else if (object instanceof MapEntry) {
- MapEntry that = (MapEntry) object;
- return hashCode == that.hashCode
- && key.equals(that.key)
- && value.equals(that.value);
- } else {
- return false;
- }
+ int size = entries.size();
+ checkElementIndex(size, MapRecord.MAX_SIZE);
+ checkPositionIndex(level, MapRecord.MAX_NUMBER_OF_LEVELS);
+ checkArgument(size != 0 || level == MapRecord.MAX_NUMBER_OF_LEVELS);
+
+ List<RecordId> ids = Lists.newArrayListWithCapacity(2 * size);
+ for (MapEntry entry : entries) {
+ ids.add(entry.getKey());
+ ids.add(entry.getValue());
}
+ // copy the entries to an array so we can sort them before writing
+ MapEntry[] array = entries.toArray(new MapEntry[entries.size()]);
+ Arrays.sort(array);
+
+ RecordId id = prepare(4 + size * 4, ids);
+ writeInt((level << MapRecord.SIZE_BITS) | size);
+ for (MapEntry entry : array) {
+ writeInt(entry.getName().hashCode());
+ }
+ for (MapEntry entry : array) {
+ writeRecordId(entry.getKey());
+ }
+ for (MapEntry entry : array) {
+ writeRecordId(entry.getValue());
+ }
+ return new MapLeaf(store, id, size, level);
}
- private static class BucketInfo {
- RecordId id;
- int size;
- BucketInfo(RecordId id, int size) {
- this.id = id;
- this.size = size;
+ private synchronized RecordId writeListBucket(List<RecordId> bucket) {
+ RecordId bucketId = prepare(0, bucket);
+ for (RecordId id : bucket) {
+ writeRecordId(id);
}
+ return bucketId;
}
private synchronized MapRecord writeMapBucket(
- RecordId baseId, List<MapEntry> entries, int level) {
+ RecordId baseId, Collection<MapEntry> entries, int level) {
int mask = MapRecord.BUCKETS_PER_LEVEL - 1;
int shift = level * MapRecord.LEVEL_BITS;
- if (entries.isEmpty()) {
+ if (entries == null || entries.isEmpty()) {
if (baseId != null) {
return MapRecord.readMap(store, baseId);
} else if (level == 0) {
@@ -249,62 +234,47 @@ public class SegmentWriter {
} else if (baseId != null) {
// FIXME: messy code with lots of duplication
MapRecord base = MapRecord.readMap(store, baseId);
- int baseSize = base.size();
- if (baseSize <= MapRecord.BUCKETS_PER_LEVEL) {
- Map<String, RecordId> update = Maps.newHashMap();
- for (MapRecord.Entry entry : base.getEntries()) {
- update.put(entry.getKey(), entry.getValue());
- }
+ if (base instanceof MapLeaf) {
+ Map<String, MapEntry> map = ((MapLeaf) base).getMapEntries();
for (MapEntry entry : entries) {
- if (entry.value != null) {
- update.put(entry.string, entry.value);
+ if (entry.getValue() != null) {
+ map.put(entry.getName(), entry);
} else {
- update.remove(entry.string);
+ map.remove(entry.getName());
}
}
- entries = Lists.newArrayListWithCapacity(update.size());
- for (Map.Entry<String, RecordId> entry : update.entrySet()) {
- entries.add(new MapEntry(entry.getKey(), entry.getValue()));
- }
- return writeMapBucket(null, entries, level);
+ return writeMapBucket(null, map.values(), level);
} else {
- List<MapEntry>[] buckets = new List[MapRecord.BUCKETS_PER_LEVEL];
+ List<Collection<MapEntry>> buckets =
+ Lists.newArrayListWithCapacity(BUCKETS_PER_LEVEL);
+ buckets.addAll(Collections.nCopies(
+ BUCKETS_PER_LEVEL, (Collection<MapEntry>) null));
for (MapEntry entry : entries) {
- int bucketIndex = (entry.hashCode >> shift) & mask;
- if (buckets[bucketIndex] == null) {
- buckets[bucketIndex] = Lists.newArrayList();
+ int bucketIndex = (entry.hashCode() >> shift) & mask;
+ Collection<MapEntry> bucket = buckets.get(bucketIndex);
+ if (bucket == null) {
+ bucket = Lists.newArrayList();
+ buckets.set(bucketIndex, bucket);
}
- buckets[bucketIndex].add(entry);
+ bucket.add(entry);
}
- int baseMap = reader.readInt(baseId, 4);
-
int newSize = 0;
- RecordId[] bucketIds = new RecordId[MapRecord.BUCKETS_PER_LEVEL];
- for (int i = 0; i < buckets.length; i++) {
- int bucketBit = 1 << i;
- RecordId baseBucketId = null;
- if ((baseMap & bucketBit) != 0) {
- int index = Integer.bitCount(baseMap & (bucketBit - 1));
- baseBucketId = reader.readRecordId(
- baseId, 8 + index * Segment.RECORD_ID_BYTES);
- }
- if (buckets[i] != null) {
- MapRecord map = writeMapBucket(
- baseBucketId, buckets[i], level + 1);
- bucketIds[i] = map.getRecordId();
- newSize += map.size();
+ RecordId[] bucketIds = ((MapBranch) base).getBuckets();
+ for (int i = 0; i < BUCKETS_PER_LEVEL; i++) {
+ MapRecord newBucket = writeMapBucket(
+ bucketIds[i], buckets.get(i), level + 1);
+ if (newBucket != null) {
+ bucketIds[i] = newBucket.getRecordId();
+ newSize += newBucket.size();
} else {
- bucketIds[i] = baseBucketId;
- if (baseBucketId != null) {
- newSize += MapRecord.readMap(store, baseBucketId).size();
- }
+ bucketIds[i] = null;
}
}
List<RecordId> ids = Lists.newArrayList();
int bucketMap = 0;
- for (int i = 0; i < buckets.length; i++) {
+ for (int i = 0; i < BUCKETS_PER_LEVEL; i++) {
if (bucketIds[i] != null) {
ids.add(bucketIds[i]);
bucketMap |= 1 << i;
@@ -320,32 +290,11 @@ public class SegmentWriter {
return new MapBranch(store, bucketId, newSize, level, bucketMap);
}
} else if (entries.size() <= MapRecord.BUCKETS_PER_LEVEL) {
- Collections.sort(entries);
-
- List<RecordId> ids = Lists.newArrayList();
- for (MapEntry entry : entries) {
- ids.add(entry.key);
- ids.add(entry.value);
- }
-
- RecordId bucketId = prepare(4 + entries.size() * 4, ids);
- // System.out.println("W: " + entries.size() + " " + level);
- Preconditions.checkState(entries.size() > 0 || level == 0);
- writeInt((level << MapRecord.SIZE_BITS) | entries.size());
- for (MapEntry entry : entries) {
- writeInt(entry.hashCode);
- }
- for (MapEntry entry : entries) {
- writeRecordId(entry.key);
- }
- for (MapEntry entry : entries) {
- writeRecordId(entry.value);
- }
- return new MapLeaf(store, bucketId, entries.size(), level);
+ return writeLeaf(level, entries);
} else {
List<MapEntry>[] buckets = new List[MapRecord.BUCKETS_PER_LEVEL];
for (MapEntry entry : entries) {
- int bucketIndex = (entry.hashCode >> shift) & mask;
+ int bucketIndex = (entry.hashCode() >> shift) & mask;
if (buckets[bucketIndex] == null) {
buckets[bucketIndex] = Lists.newArrayList();
}
@@ -423,7 +372,9 @@ public class SegmentWriter {
public MapRecord writeMap(MapRecord base, Map<String, RecordId> changes) {
List<MapEntry> entries = Lists.newArrayList();
for (Map.Entry<String, RecordId> entry : changes.entrySet()) {
- entries.add(new MapEntry(entry.getKey(), entry.getValue()));
+ String name = entry.getKey();
+ entries.add(new MapEntry(
+ store, name, writeString(name), entry.getValue()));
}
RecordId baseId = null;
if (base != null) {
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=1449084&r1=1449083&r2=1449084&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 Fri Feb 22 15:58:02 2013
@@ -28,19 +28,15 @@ import java.util.Set;
import javax.annotation.CheckForNull;
import javax.annotation.Nonnull;
-import javax.annotation.Nullable;
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.Entry;
import org.apache.jackrabbit.oak.spi.state.ChildNodeEntry;
import org.apache.jackrabbit.oak.spi.state.NodeState;
import org.apache.jackrabbit.oak.spi.state.NodeStateDiff;
-import com.google.common.base.Function;
import com.google.common.base.Objects;
-import com.google.common.collect.Iterables;
import com.google.common.collect.Lists;
class Template {
@@ -309,16 +305,7 @@ class Template {
if (hasNoChildNodes()) {
return Collections.emptyList();
} else if (hasManyChildNodes()) {
- return Iterables.transform(
- getChildNodeMap(reader, recordId).getEntries(),
- new Function<MapRecord.Entry, ChildNodeEntry>() {
- @Override @Nullable
- public ChildNodeEntry apply(@Nullable Entry input) {
- return new MemoryChildNodeEntry(
- input.getKey(),
- new SegmentNodeState(reader, input.getValue()));
- }
- });
+ return getChildNodeMap(reader, recordId).getEntries();
} else {
RecordId childNodeId =
reader.readRecordId(recordId, Segment.RECORD_ID_BYTES);
Modified: jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/segment/RecordTest.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/segment/RecordTest.java?rev=1449084&r1=1449083&r2=1449084&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/segment/RecordTest.java (original)
+++ jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/segment/RecordTest.java Fri Feb 22 15:58:02 2013
@@ -185,7 +185,7 @@ public class RecordTest {
MapRecord many = writer.writeMap(null, map);
writer.flush();
- Iterator<MapRecord.Entry> iterator;
+ Iterator<MapEntry> iterator;
assertEquals(0, zero.size());
assertNull(zero.getEntry("one"));
@@ -197,7 +197,7 @@ public class RecordTest {
assertNull(one.getEntry("two"));
iterator = one.getEntries().iterator();
assertTrue(iterator.hasNext());
- assertEquals("one", iterator.next().getKey());
+ assertEquals("one", iterator.next().getName());
assertFalse(iterator.hasNext());
assertEquals(2, two.size());