jackrabbit-oak-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From ju...@apache.org
Subject 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/
Date Fri, 22 Feb 2013 15:58:02 GMT
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());



Mime
View raw message