jackrabbit-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From thom...@apache.org
Subject svn commit: r1232860 - in /jackrabbit/sandbox/microkernel/src: main/java/org/apache/jackrabbit/mk/mem/ test/java/org/apache/jackrabbit/mk/large/ test/java/org/apache/jackrabbit/mk/mem/
Date Wed, 18 Jan 2012 12:40:17 GMT
Author: thomasm
Date: Wed Jan 18 12:40:16 2012
New Revision: 1232860

URL: http://svn.apache.org/viewvc?rev=1232860&view=rev
Log:
More efficient revision data structure (similar to a skip list)

Modified:
    jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/MemoryKernelImpl.java
    jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/NodeImpl.java
    jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/Revision.java
    jackrabbit/sandbox/microkernel/src/test/java/org/apache/jackrabbit/mk/large/LargeNodeTest.java
    jackrabbit/sandbox/microkernel/src/test/java/org/apache/jackrabbit/mk/mem/MemoryNodeTest.java

Modified: jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/MemoryKernelImpl.java
URL: http://svn.apache.org/viewvc/jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/MemoryKernelImpl.java?rev=1232860&r1=1232859&r2=1232860&view=diff
==============================================================================
--- jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/MemoryKernelImpl.java
(original)
+++ jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/MemoryKernelImpl.java
Wed Jan 18 12:40:16 2012
@@ -38,23 +38,22 @@ import java.io.InputStream;
 import java.util.ArrayList;
 import java.util.Collections;
 import java.util.HashMap;
-import java.util.Iterator;
 
 /*
 
 Node structure:
 
 /head/rev = 100
-/head/time = now()
-/head/commit/diff = "+ "/test ..."
+/head/time = millis
+/head/commit/diff = [+ "/test"{}]
 /head/commit/msg = "hello ..."
-/head/data/<user root>
-/old/90/rev = 90
-/old/90/data/<user root of revision 90>
-/old/91/rev = 91
-/old/99/rev = 99
-/old/old/80/rev = 80
-/old/old/89/rev = 89
+/head/config/ (optional)
+/head/data/
+/99/head/time = millis
+/99/98/head
+/99/98/97/head
+/99/90/head
+/99/90/89/head
 
 */
 
@@ -64,14 +63,16 @@ Node structure:
  */
 public class MemoryKernelImpl extends WrapperBase implements MicroKernel {
 
-    private static final int MAX_REVISIONS_PER_NODE = 5;
     private static final HashMap<String, MemoryKernelImpl> INSTANCES = new HashMap<String,
MemoryKernelImpl>();
 
+    private static final int REV_SKIP_OFFSET = 20;
+
     private final String name;
     private final AbstractBlobStore ds;
     private final NonDescendingClock clock = new NonDescendingClock(System.currentTimeMillis());
     private final CommitGate gate = new CommitGate();
     private final Cache<Long, Revision> revisionCache = Cache.newInstance(null, 1024
* 1024);
+
     private volatile long headRevId;
     private volatile String headRevision;
     private NodeMap nodeMap;
@@ -102,10 +103,8 @@ public class MemoryKernelImpl extends Wr
             Revision revNode = new Revision(0, 0, "", "");
             head = revNode.store(head, new NodeImpl(nodeMap, 0));
             head.addChildNode("data", new NodeImpl(nodeMap, 0));
-            head.addChildNode("config", new NodeImpl(nodeMap, 0));
             NodeImpl root = new NodeImpl(nodeMap, 0);
             root.addChildNode("head", head);
-            root.addChildNode("old", new NodeImpl(nodeMap, 0));
             nodeMap.commit(root);
         } else {
             NodeImpl head = getRoot().getNode("head");
@@ -161,9 +160,12 @@ public class MemoryKernelImpl extends Wr
     }
 
     private void applyConfig(NodeImpl head) {
-        NodeImpl config = head.getNode("config");
-        for (int i = 0, size = config.getPropertyCount(); i < size; i++) {
-            nodeMap.setSetting(config.getProperty(i), config.getPropertyValue(i));
+        // /head/config doesn't always exist
+        if (head.exists("config")) {
+            NodeImpl config = head.getNode("config");
+            for (int i = 0, size = config.getPropertyCount(); i < size; i++) {
+                nodeMap.setSetting(config.getProperty(i), config.getPropertyValue(i));
+            }
         }
     }
 
@@ -242,6 +244,9 @@ public class MemoryKernelImpl extends Wr
                 }
                 if (isConfigChange) {
                     String p = PathUtils.relativize(":root/head", from);
+                    if (!head.exists("config")) {
+                        head = head.setChild("config", new NodeImpl(nodeMap, rev), rev);
+                    }
                     head = head.cloneAndSetProperty(p, value, rev);
                     applyConfig(head);
                 } else {
@@ -340,13 +345,24 @@ public class MemoryKernelImpl extends Wr
         revisionCache.put(rev, revNode);
         head = revNode.store(head, new NodeImpl(nodeMap, rev));
         root = root.setChild("head", head, rev);
-        NodeImpl old = root.getNode("old");
-        if (old.getChildCount() > MAX_REVISIONS_PER_NODE) {
-            NodeImpl newOld = new NodeImpl(nodeMap, rev);
-            old = newOld.setChild("old", old, rev);
+        String old = Revision.formatId(oldRevision);
+        NodeImpl oldRev = new NodeImpl(nodeMap, rev);
+        oldRev.addChildNode("head", oldHead);
+        String lastRev = Revision.formatId(oldRevision - 1);
+        if (root.exists(lastRev)) {
+            NodeImpl lastRevNode = root.getNode(lastRev);
+            root = root.cloneAndRemoveChildNode(lastRev, rev);
+            oldRev.setChild(lastRev, lastRevNode, rev);
+            if (oldRevision % REV_SKIP_OFFSET == 0) {
+                long skip = oldRevision - REV_SKIP_OFFSET;
+                NodeImpl n = getRevisionNode(getRoot(), skip, skip);
+                if (n != null) {
+                    oldRev.setChild(Revision.formatId(skip), n, rev);
+                    // TODO remove old link to reduce descendant count
+                }
+            }
         }
-        old = old.setChild(Revision.formatId(oldRevision), oldHead, rev);
-        root = root.setChild("old", old, rev);
+        root = root.setChild(old, oldRev, rev);
         nodeMap.commit(root);
         headRevId = rev;
         headRevision = Revision.formatId(rev);
@@ -368,16 +384,24 @@ public class MemoryKernelImpl extends Wr
         Revision r = Revision.get(node.getNode("head"));
         if (since < r.getTime() && maxEntries > 0) {
             revisions.add(r);
-            while (node.exists("old") && revisions.size() < maxEntries) {
-                node = node.getNode("old");
-                for (Iterator<String> it = node.getChildNodeNames(Integer.MAX_VALUE);
it.hasNext();) {
-                    r = Revision.get(node.getNode(it.next()));
-                    if (r != null) {
-                        revisions.add(r);
+            while (revisions.size() < maxEntries) {
+                String newest = null;
+                for (int i = 0;; i++) {
+                    String next = node.getChildNodeName(i);
+                    if (next == null) {
+                        break;
+                    } else if (!next.equals("head") && !next.equals("config")) {
+                        if (newest == null || next.compareTo(newest) >= 0) {
+                            newest = next;
+                        }
                     }
                 }
-                if (since >= r.getTime()) {
-                    break;
+                if (newest != null) {
+                    r = Revision.get(node);
+                    if (r == null) {
+                        break;
+                    }
+                    revisions.add(r);
                 }
             }
         }
@@ -401,29 +425,67 @@ public class MemoryKernelImpl extends Wr
         NodeImpl node = getRoot();
         ArrayList<Revision> revisions = new ArrayList<Revision>();
         Revision r = Revision.get(node.getNode("head"));
-        if (r.getId() >= fromRev) {
+        if (r.getId() >= fromRev && r.getId() <= toRev) {
             revisions.add(r);
         }
-        while (r.getId() > fromRev && node.exists("old")) {
-            node = node.getNode("old");
-            for (Iterator<String> it = node.getChildNodeNames(Integer.MAX_VALUE); it.hasNext();)
{
-                r = Revision.get(node.getNode(it.next()));
-                if (r != null && r.getId() >= fromRev && r.getId() <=
toRev) {
+        if (r.getId() > fromRev) {
+            node = getRevisionNode(node, fromRev, toRev);
+            while (node != null) {
+                r = Revision.get(node.getNode("head"));
+                if (r.getId() >= fromRev && r.getId() <= toRev) {
                     r = revisionCache.replace(r.getId(), r);
                     revisions.add(r);
                 }
+                String next = Revision.formatId(r.getId() - 1);
+                if (!node.exists(next)) {
+                    break;
+                }
+                node = node.getNode(next);
             }
         }
-        Collections.sort(revisions);
         JsopStream buff = new JsopStream().array().newline();
-        for (Revision rev : revisions) {
+        for (int i = revisions.size() - 1; i >= 0; i--) {
+            Revision rev = revisions.get(i);
             if (rev.getId() >= fromRev && rev.getId() <= toRev) {
                 rev.appendJournal(buff);
             }
         }
         return buff.endArray();
+   }
+
+    private NodeImpl getRevisionNode(NodeImpl node, long fromRev, long toRev) {
+        while (true) {
+            long next = -1;
+            String nextRev = null;
+            for (int i = 0;; i++) {
+                String n = node.getChildNodeName(i);
+                if (n == null) {
+                    break;
+                }
+                if ("head".equals(n)) {
+                    continue;
+                }
+                long rev = Revision.parseId(n);
+                if (next == -1 || (rev >= toRev && rev < next)) {
+                    next = rev;
+                    nextRev = n;
+                }
+            }
+            if (next == -1 || fromRev > next) {
+                if (!node.exists("head")) {
+                    return null;
+                }
+                node = node.getNode("head");
+            } else {
+                node = node.getNode(nextRev);
+                if (next <= toRev) {
+                    return node;
+                }
+            }
+        }
     }
 
+
     public JsopReader diffStream(String fromRevisionId, String toRevisionId, String path)
{
         // TODO implement if required
         return new JsopStream();
@@ -458,10 +520,10 @@ public class MemoryKernelImpl extends Wr
             } else if (path.startsWith("/:info")) {
                 n = nodeMap.getInfo(PathUtils.relativize("/:info", path));
             } else {
-                n = getRevision(revisionId).getNode(path.substring(1));
+                n = getRevisionDataRoot(revisionId).getNode(path.substring(1));
             }
         } else {
-            n = getRevision(revisionId).getNode(path.substring(1));
+            n = getRevisionDataRoot(revisionId).getNode(path.substring(1));
         }
         if (n == null) {
             throw ExceptionFactory.get("Path not found: " + path);
@@ -471,27 +533,27 @@ public class MemoryKernelImpl extends Wr
         return json;
     }
 
-    private NodeImpl getRevision(String revisionId) {
+    private NodeImpl getRevisionDataRoot(String revisionId) {
+        NodeImpl rev = getRevisionIfExists(revisionId);
+        if (rev == null) {
+            throw ExceptionFactory.get("Revision not found: " + revisionId);
+        }
+        return rev.getNode("data");
+    }
+
+    private NodeImpl getRevisionIfExists(String revisionId) {
         NodeImpl node = getRoot();
         NodeImpl head = node.getNode("head");
-        String headRev = head.getProperty("rev");
+        String headRev;
+        headRev = head.getProperty("rev");
         headRev = headRev == null ? null : JsopTokenizer.decodeQuoted(headRev);
         // we can't rely on headRevId, as it's a volatile field
         if (revisionId.equals(headRev)) {
-            node = head;
+            return head;
         } else {
-            while (true) {
-                if (!node.exists("old")) {
-                    throw ExceptionFactory.get("Revision not found: " + revisionId);
-                }
-                node = node.getNode("old");
-                if (node.exists(revisionId)) {
-                    node = node.getNode(revisionId);
-                    break;
-                }
-            }
+            long rev = Revision.parseId(revisionId);
+            return getRevisionNode(node, rev, rev).getNode("head");
         }
-        return node.getNode("data");
     }
 
     public boolean nodeExists(String path, String revisionId) {
@@ -504,7 +566,7 @@ public class MemoryKernelImpl extends Wr
             return true;
         }
         // TODO possibly use a cache / a bloom filter
-        return getRevision(revisionId).exists(path.substring(1));
+        return getRevisionDataRoot(revisionId).exists(path.substring(1));
     }
 
     public long getLength(String blobId) {

Modified: jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/NodeImpl.java
URL: http://svn.apache.org/viewvc/jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/NodeImpl.java?rev=1232860&r1=1232859&r2=1232860&view=diff
==============================================================================
--- jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/NodeImpl.java
(original)
+++ jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/NodeImpl.java
Wed Jan 18 12:40:16 2012
@@ -47,12 +47,12 @@ public class NodeImpl implements Cache.V
     /**
      * The total number of child nodes.
      */
-    public static final String DESCENDANT_COUNT = ":descendantCount";
+    public static final String DESCENDANT_COUNT = ":size";
 
     /**
      * The total number of child nodes that are stored inline.
      */
-    public static final String DESCENDANT_INLINE_COUNT = ":descendantInlineCount";
+    public static final String DESCENDANT_INLINE_COUNT = ":sizeInline";
 
     /**
      * The content hash.
@@ -570,11 +570,15 @@ public class NodeImpl implements Cache.V
     }
 
     public String asString() {
+        // TODO ALLOW_UNQUOTED_FIELD_NAMES to safe space
+        // (check what Javascript supports and what are the keywords)
         JsopWriter json = new JsopBuilder();
         json.setLineLength(120);
+        boolean inline = true;
         if (id != null && !id.isInline()) {
             String nodeId = map.formatId(id);
             if (nodeId != null) {
+                inline = false;
                 json.encodedValue(nodeId).tag('=');
             }
         }
@@ -590,12 +594,18 @@ public class NodeImpl implements Cache.V
             json.key(HASH).value(StringUtils.convertBytesToHex(hash));
         }
         if (childNodes != null && childNodes.size() > 0) {
-            if (descendantCount > childNodes.size()) {
-                json.key(DESCENDANT_COUNT).value(descendantCount);
+            if (map.getDescendantCount()) {
+                if (descendantCount > childNodes.size()) {
+                    json.key(DESCENDANT_COUNT).value(descendantCount);
+                }
             }
             childNodes.append(json, map);
         }
-        return json.endObject().toString();
+        json.endObject();
+        if (!inline) {
+            json.tag(';');
+        }
+        return json.toString();
     }
 
     public static NodeImpl fromString(NodeMap map, String s) {

Modified: jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/Revision.java
URL: http://svn.apache.org/viewvc/jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/Revision.java?rev=1232860&r1=1232859&r2=1232860&view=diff
==============================================================================
--- jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/Revision.java
(original)
+++ jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/Revision.java
Wed Jan 18 12:40:16 2012
@@ -65,14 +65,24 @@ public class Revision implements Compara
 
     private String getDiff() {
         if (diff == null) {
-            diff = getCommitValue("diff");
+            String s = getCommitValue("diff");
+            if (s.length() == 0) {
+                s = "";
+            } else if (s.charAt(0) == '[') {
+                // remove the surrounding "[" and "]"
+                s = s.substring(1, s.length() - 1);
+            } else {
+                s = JsopTokenizer.decodeQuoted(s);
+            }
+            diff = s;
         }
         return diff;
     }
 
     private String getMsg() {
         if (msg == null) {
-            msg = getCommitValue("msg");
+            String m = getCommitValue("msg");
+            msg = m.length() == 0 ? "" : JsopTokenizer.decodeQuoted(m);
         }
         return msg;
     }
@@ -81,7 +91,7 @@ public class Revision implements Compara
         if (node.exists("commit")) {
             String v = node.getNode("commit").getProperty(s);
             if (v != null) {
-                return JsopTokenizer.decodeQuoted(v);
+                return v;
             }
         }
         return "";
@@ -109,7 +119,11 @@ public class Revision implements Compara
     NodeImpl store(NodeImpl head, NodeImpl commit) {
         head = head.cloneAndSetProperty("rev", JsopBuilder.encode(formatId(id)), id);
         head = head.cloneAndSetProperty("time", Long.toString(time), id);
-        commit.setProperty("diff", JsopBuilder.encode(diff));
+        if (diff.indexOf(";\n") >= 0) {
+            commit.setProperty("diff", JsopBuilder.encode(diff));
+        } else {
+            commit.setProperty("diff", "[" + diff + "]");
+        }
         if (msg != null) {
             commit.setProperty("msg", JsopBuilder.encode(msg));
         }

Modified: jackrabbit/sandbox/microkernel/src/test/java/org/apache/jackrabbit/mk/large/LargeNodeTest.java
URL: http://svn.apache.org/viewvc/jackrabbit/sandbox/microkernel/src/test/java/org/apache/jackrabbit/mk/large/LargeNodeTest.java?rev=1232860&r1=1232859&r2=1232860&view=diff
==============================================================================
--- jackrabbit/sandbox/microkernel/src/test/java/org/apache/jackrabbit/mk/large/LargeNodeTest.java
(original)
+++ jackrabbit/sandbox/microkernel/src/test/java/org/apache/jackrabbit/mk/large/LargeNodeTest.java
Wed Jan 18 12:40:16 2012
@@ -73,7 +73,6 @@ public class LargeNodeTest extends Multi
             return;
         }
         int max = 90;
-        Assert.assertEquals("{\":childNodeCount\":0}", mk.getNodes("/:root/head/config",
head));
         head = mk.commit("/:root/head/config", "^ \"maxMemoryChildren\":" + max, head, "");
         Assert.assertEquals("{\"maxMemoryChildren\":"+max+",\":childNodeCount\":0}", mk.getNodes("/:root/head/config",
head));
         head = mk.commit("/", "+ \"t\": {}", head, "");
@@ -88,7 +87,6 @@ public class LargeNodeTest extends Multi
     public void veryLargeNodeList() {
         if (isMemoryKernel(mk)) {
             int max = 2000;
-            Assert.assertEquals("{\":childNodeCount\":0}", mk.getNodes("/:root/head/config",
head));
             head = mk.commit("/:root/head/config", "^ \"maxMemoryChildren\":" + max, head,
"");
             Assert.assertEquals("{\"maxMemoryChildren\":"+max+",\":childNodeCount\":0}",
mk.getNodes("/:root/head/config", head));
         }
@@ -127,7 +125,6 @@ public class LargeNodeTest extends Multi
             return;
         }
 
-        Assert.assertEquals("{\":childNodeCount\":0}", mk.getNodes("/:root/head/config",
head));
         head = mk.commit("/:root/head/config", "^ \"maxMemoryChildren\": 10", head, "");
         Assert.assertEquals("{\"maxMemoryChildren\":10,\":childNodeCount\":0}", mk.getNodes("/:root/head/config",
head));
         for (int i = 0; i < 100; i++) {

Modified: jackrabbit/sandbox/microkernel/src/test/java/org/apache/jackrabbit/mk/mem/MemoryNodeTest.java
URL: http://svn.apache.org/viewvc/jackrabbit/sandbox/microkernel/src/test/java/org/apache/jackrabbit/mk/mem/MemoryNodeTest.java?rev=1232860&r1=1232859&r2=1232860&view=diff
==============================================================================
--- jackrabbit/sandbox/microkernel/src/test/java/org/apache/jackrabbit/mk/mem/MemoryNodeTest.java
(original)
+++ jackrabbit/sandbox/microkernel/src/test/java/org/apache/jackrabbit/mk/mem/MemoryNodeTest.java
Wed Jan 18 12:40:16 2012
@@ -34,9 +34,9 @@ public class MemoryNodeTest {
         NodeImpl n = new NodeImpl(map, 0);
         Assert.assertEquals("{}", n.asString());
         n.setId(NodeId.get(255));
-        Assert.assertEquals("nff={}", n.asString());
+        Assert.assertEquals("nff={};", n.asString());
         n.setPath("/test");
-        Assert.assertEquals("nff={}/* /test */", n.toString());
+        Assert.assertEquals("nff={};/* /test */", n.toString());
         n = n.createClone(10);
         Assert.assertEquals("{}", n.asString());
         NodeImpl a = new NodeImpl(map, 0);
@@ -50,9 +50,9 @@ public class MemoryNodeTest {
         n = n.cloneAndAddChildNode("a", false, null, a, 11);
         n = n.cloneAndSetProperty("x", "1", 12);
         n.setId(NodeId.get(3));
-        Assert.assertEquals("n3={\"x\":1,\"a\":n1}", n.asString());
+        Assert.assertEquals("n3={\"x\":1,\"a\":n1};", n.asString());
         NodeImpl n2 = NodeImpl.fromString(map, n.asString());
-        Assert.assertEquals("n3={\"x\":1,\"a\":n1}", n2.asString());
+        Assert.assertEquals("n3={\"x\":1,\"a\":n1};", n2.asString());
 
         n = new NodeImpl(map, 0);
         n = n.cloneAndAddChildNode("a", false, null, a, 1);
@@ -97,9 +97,9 @@ public class MemoryNodeTest {
         n = n.cloneAndAddChildNode("a", false, null, a, 11);
         n = n.cloneAndSetProperty("x", "1", 12);
         n.setId(NodeId.get(3));
-        Assert.assertEquals("n3={\"x\":1,\"a\":{\"name\":\"a\"}}", n.asString());
+        Assert.assertEquals("n3={\"x\":1,\"a\":{\"name\":\"a\"}};", n.asString());
         NodeImpl n2 = NodeImpl.fromString(map, n.asString());
-        Assert.assertEquals("n3={\"x\":1,\"a\":{\"name\":\"a\"}}", n2.asString());
+        Assert.assertEquals("n3={\"x\":1,\"a\":{\"name\":\"a\"}};", n2.asString());
 
         n = new NodeImpl(map, 0);
         n = n.cloneAndAddChildNode("a", false, null, a, 1);
@@ -121,13 +121,13 @@ public class MemoryNodeTest {
 
         NodeImpl root = new NodeImpl(map, 0);
         root = root.cloneAndAddChildNode("test", false, null, n2, 1);
-        Assert.assertEquals("{\":descendantCount\":4,\"test\":n1}", root.asString());
+        Assert.assertEquals("{\":size\":4,\"test\":n1}", root.asString());
         Assert.assertEquals(0, root.getDescendantInlineCount());
 
         n2 = n2.cloneAndRemoveChildNode("c", 4);
         root = new NodeImpl(map, 0);
         root = root.cloneAndAddChildNode("test", false, null, n2, 1);
-        Assert.assertEquals("{\":descendantCount\":3,\"test\":" + ab + "}", root.asString());
+        Assert.assertEquals("{\":size\":3,\"test\":" + ab + "}", root.asString());
 
     }
 



Mime
View raw message