jackrabbit-oak-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From ju...@apache.org
Subject svn commit: r1443278 - in /jackrabbit/oak/trunk/oak-core/src: main/java/org/apache/jackrabbit/oak/plugins/segment/ test/java/org/apache/jackrabbit/oak/plugins/segment/
Date Wed, 06 Feb 2013 23:54:40 GMT
Author: jukka
Date: Wed Feb  6 23:54:40 2013
New Revision: 1443278

URL: http://svn.apache.org/viewvc?rev=1443278&view=rev
Log:
OAK-593: Segment-based MK

Initial implementation of map records

Added:
    jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/MapRecord.java
  (with props)
Modified:
    jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/Record.java
    jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/RecordId.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/SegmentReader.java
    jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/SegmentWriter.java
    jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/segment/RecordTest.java

Added: 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=1443278&view=auto
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/MapRecord.java
(added)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/MapRecord.java
Wed Feb  6 23:54:40 2013
@@ -0,0 +1,74 @@
+/*
+ * 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;
+
+class MapRecord extends Record {
+
+    static final int LEVEL_BITS = 6;
+
+    MapRecord(SegmentReader reader, RecordId id) {
+        super(reader, id);
+    }
+
+    public int size() {
+        return readInt(0);
+    }
+
+    public RecordId getEntry(String key) {
+        checkNotNull(key);
+        return getEntry(key, 0);
+    }
+
+    private RecordId getEntry(String key, int level) {
+        int size = 1 << LEVEL_BITS;
+        int mask = size - 1;
+        int shift = level * LEVEL_BITS;
+
+        int code = key.hashCode();
+        int bucketSize = readInt(0);
+        if (bucketSize == 0) {
+            return null;
+        } else if (bucketSize <= size) {
+            int offset = 0;
+            while (offset < bucketSize && readInt(4 + offset * 4) < code) {
+                offset++;
+            }
+            while (offset < bucketSize && readInt(4 + offset * 4) == code) {
+                RecordId keyId = readRecordId(4 + (bucketSize + offset) * 4);
+                if (key.equals(getReader().readString(keyId))) {
+                    return readRecordId(4 + (2 * bucketSize + offset) * 4);
+                }
+                offset++;
+            }
+            return null;
+        } else {
+            long bucketMap = readLong(4);
+            int bucketIndex = (code >> shift) & mask;
+            long bucketBit = 1L << bucketIndex;
+            if ((bucketMap & bucketBit) != 0) {
+                bucketIndex = Long.bitCount(bucketMap & (bucketBit - 1));
+                RecordId bucketId = readRecordId(12 + bucketIndex * 4);
+                return new MapRecord(getReader(), bucketId).getEntry(key, level + 1);
+            } else {
+                return null;
+            }
+        }
+    }
+
+}

Propchange: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/MapRecord.java
------------------------------------------------------------------------------
    svn:eol-style = native

Modified: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/Record.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/Record.java?rev=1443278&r1=1443277&r2=1443278&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/Record.java
(original)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/Record.java
Wed Feb  6 23:54:40 2013
@@ -35,6 +35,14 @@ class Record {
         return reader.readRecordId(id, position);
     }
 
+    protected int readInt(int position) {
+        return reader.readInt(id, position);
+    }
+
+    protected long readLong(int position) {
+        return reader.readLong(id, position);
+    }
+
     public RecordId getRecordId() {
         return id;
     }

Modified: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/RecordId.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/RecordId.java?rev=1443278&r1=1443277&r2=1443278&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/RecordId.java
(original)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/RecordId.java
Wed Feb  6 23:54:40 2013
@@ -20,7 +20,7 @@ import java.util.UUID;
 
 import com.google.common.base.Preconditions;
 
-public final class RecordId {
+public final class RecordId implements Comparable<RecordId> {
 
     public static RecordId[] EMPTY_ARRAY = new RecordId[0];
 
@@ -41,6 +41,17 @@ public final class RecordId {
         return offset;
     }
 
+    //--------------------------------------------------------< Comparable >--
+
+    @Override
+    public int compareTo(RecordId that) {
+        int diff = segmentId.compareTo(that.segmentId);
+        if (diff == 0) {
+            diff = offset - that.offset;
+        }
+        return diff;
+    }
+
     //------------------------------------------------------------< Object >--
 
     @Override

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=1443278&r1=1443277&r2=1443278&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
Wed Feb  6 23:54:40 2013
@@ -16,6 +16,7 @@
  */
 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;
 
@@ -50,6 +51,11 @@ class Segment {
         return data.length;
     }
 
+    public byte readByte(int position) {
+        checkElementIndex(position, data.length);
+        return data[position];
+    }
+
     /**
      * Reads the given number of bytes starting from the given position
      * in this segment.
@@ -75,7 +81,12 @@ class Segment {
                 | (data[offset + 3] & 0xff));
     }
 
-    public long readLength(int offset) {
+    public int readInt(int offset) {
+        checkPositionIndexes(offset, offset + 4, data.length);
+        return ByteBuffer.wrap(data).getInt(offset);
+    }
+
+    public long readLong(int offset) {
         checkPositionIndexes(offset, offset + 8, data.length);
         return ByteBuffer.wrap(data).getLong(offset);
     }

Modified: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/SegmentReader.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/SegmentReader.java?rev=1443278&r1=1443277&r2=1443278&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/SegmentReader.java
(original)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/SegmentReader.java
Wed Feb  6 23:54:40 2013
@@ -54,13 +54,27 @@ public class SegmentReader {
     public SegmentStream readStream(RecordId recordId) {
         Segment segment = store.readSegment(recordId.getSegmentId());
         int offset = recordId.getOffset();
-        long length = segment.readLength(offset);
+        long length = segment.readLong(offset);
         int size = (int) ((length + BLOCK_SIZE - 1) / BLOCK_SIZE);
         ListRecord list = new ListRecord(
                 this, segment.readRecordId(offset + 8), size);
         return new SegmentStream(this, list, length);
     }
 
+    public int readInt(RecordId recordId, int position) {
+        checkNotNull(recordId);
+        checkArgument(position >= 0);
+        Segment segment = store.readSegment(recordId.getSegmentId());
+        return segment.readInt(recordId.getOffset() + position);
+    }
+
+    public long readLong(RecordId recordId, int position) {
+        checkNotNull(recordId);
+        checkArgument(position >= 0);
+        Segment segment = store.readSegment(recordId.getSegmentId());
+        return segment.readLong(recordId.getOffset() + position);
+    }
+
     public void readBytes(
             RecordId recordId, int position,
             byte[] buffer, int offset, int length) {

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=1443278&r1=1443277&r2=1443278&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
Wed Feb  6 23:54:40 2013
@@ -27,6 +27,7 @@ import java.util.Collection;
 import java.util.Collections;
 import java.util.HashSet;
 import java.util.List;
+import java.util.Map;
 import java.util.Set;
 import java.util.UUID;
 
@@ -144,6 +145,83 @@ public class SegmentWriter {
         return bucketId;
     }
 
+    class MapEntry implements Comparable<MapEntry> {
+        private final int hashCode;
+        private final RecordId key;
+        private final RecordId value;
+
+        MapEntry(int hashCode, RecordId key, RecordId value) {
+            this.hashCode = hashCode;
+            this.key = key;
+            this.value = value;
+        }
+
+        @Override
+        public int compareTo(MapEntry that) {
+            int diff = hashCode - that.hashCode;
+            if (diff == 0) {
+                diff = key.compareTo(that.key);
+            }
+            return diff;
+        }
+    }
+
+    private synchronized RecordId writeMapBucket(
+            List<MapEntry> entries, int level) {
+        int size = 1 << MapRecord.LEVEL_BITS;
+        int mask = size - 1;
+        int shift = level * MapRecord.LEVEL_BITS;
+
+        if (entries.size() <= size) {
+            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() * 12, ids);
+            buffer.putInt(entries.size());
+            for (MapEntry entry : entries) {
+                buffer.putInt(entry.hashCode);
+            }
+            for (MapEntry entry : entries) {
+                writeRecordId(entry.key);
+            }
+            for (MapEntry entry : entries) {
+                writeRecordId(entry.value);
+            }
+            return bucketId;
+        } else {
+            List<MapEntry>[] buckets = new List[size];
+            for (MapEntry entry : entries) {
+                int bucketIndex = (entry.hashCode >> shift) & mask;
+                if (buckets[bucketIndex] == null) {
+                    buckets[bucketIndex] = Lists.newArrayList();
+                }
+                buckets[bucketIndex].add(entry);
+            }
+
+            List<RecordId> bucketIds = Lists.newArrayList();
+            long bucketMap = 0L;
+            for (int i = 0; i < buckets.length; i++) {
+                if (buckets[i] != null) {
+                    bucketIds.add(writeMapBucket(buckets[i], level + 1));
+                    bucketMap |= 1L << i;
+                }
+            }
+
+            RecordId bucketId = prepare(12 + bucketIds.size() * 4, bucketIds);
+            buffer.putInt(entries.size());
+            buffer.putLong(bucketMap);
+            for (RecordId id : bucketIds) {
+                writeRecordId(id);
+            }
+            return bucketId;
+        }
+    }
+
     private synchronized RecordId writeValueRecord(
             long length, RecordId blocks) {
         RecordId valueId = prepare(8, Collections.singleton(blocks));
@@ -173,27 +251,36 @@ public class SegmentWriter {
     /**
      * Writes a list record containing the given list of record identifiers.
      *
-     * @param ids list of record identifiers
+     * @param list list of record identifiers
      * @return list record identifier
      */
-    public RecordId writeList(List<RecordId> ids) {
-        checkNotNull(ids);
+    public RecordId writeList(List<RecordId> list) {
+        checkNotNull(list);
 
-        int size = ids.size();
-        if (size == 0) {
-            return prepare(0);
-        } else {
-            List<RecordId> thisLevel = ids;
-            while (thisLevel.size() > 1) {
-                List<RecordId> nextLevel = new ArrayList<RecordId>();
-                for (List<RecordId> bucket :
-                        Lists.partition(thisLevel, ListRecord.LEVEL_SIZE)) {
-                    nextLevel.add(writeListBucket(bucket));
-                }
-                thisLevel = nextLevel;
+        if (list.isEmpty()) {
+            return prepare(0); // special case
+        }
+
+        List<RecordId> thisLevel = list;
+        while (thisLevel.size() > 1) {
+            List<RecordId> nextLevel = Lists.newArrayList();
+            for (List<RecordId> bucket :
+                    Lists.partition(thisLevel, ListRecord.LEVEL_SIZE)) {
+                nextLevel.add(writeListBucket(bucket));
             }
-            return thisLevel.iterator().next();
+            thisLevel = nextLevel;
+        }
+        return thisLevel.iterator().next();
+    }
+
+    public RecordId writeMap(Map<String, RecordId> map) {
+        List<MapEntry> entries = Lists.newArrayList();
+        for (Map.Entry<String, RecordId> entry : map.entrySet()) {
+            String key = entry.getKey();
+            entries.add(new MapEntry(
+                    key.hashCode(), writeString(key), entry.getValue()));
         }
+        return writeMapBucket(entries, 0);
     }
 
     /**

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=1443278&r1=1443277&r2=1443278&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
Wed Feb  6 23:54:40 2013
@@ -18,6 +18,7 @@ package org.apache.jackrabbit.oak.plugin
 
 import static org.apache.jackrabbit.oak.plugins.segment.ListRecord.LEVEL_SIZE;
 import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNull;
 
 import java.io.ByteArrayInputStream;
 import java.io.IOException;
@@ -25,11 +26,14 @@ import java.io.InputStream;
 import java.util.Arrays;
 import java.util.Collections;
 import java.util.List;
+import java.util.Map;
 import java.util.Random;
 
 import org.junit.Test;
 
 import com.google.common.base.Charsets;
+import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.Maps;
 
 public class RecordTest {
 
@@ -158,4 +162,38 @@ public class RecordTest {
         assertEquals(builder.toString(), reader.readString(large));
     }
 
+    @Test
+    public void testMapRecord() {
+        RecordId blockId = writer.writeBlock(bytes, 0, bytes.length);
+
+        MapRecord zero = new MapRecord(reader, writer.writeMap(
+                ImmutableMap.<String, RecordId>of()));
+        MapRecord one = new MapRecord(reader, writer.writeMap(
+                ImmutableMap.of("one", blockId)));
+        MapRecord two = new MapRecord(reader, writer.writeMap(
+                ImmutableMap.of("one", blockId, "two", blockId)));
+        Map<String, RecordId> map = Maps.newHashMap();
+        for (int i = 0; i < 1000; i++) {
+            map.put("key" + i, blockId);
+        }
+         MapRecord many = new MapRecord(reader, writer.writeMap(map));
+
+        writer.flush();
+
+        assertEquals(0, zero.size());
+        assertNull(zero.getEntry("one"));
+        assertEquals(1, one.size());
+        assertEquals(blockId, one.getEntry("one"));
+        assertNull(one.getEntry("two"));
+        assertEquals(2, two.size());
+        assertEquals(blockId, two.getEntry("one"));
+        assertEquals(blockId, two.getEntry("two"));
+        assertNull(two.getEntry("three"));
+        assertEquals(1000, many.size());
+        for (int i = 0; i < 1000; i++) {
+            assertEquals(blockId, many.getEntry("key" + i));
+        }
+        assertNull(many.getEntry("foo"));
+    }
+
 }



Mime
View raw message