jackrabbit-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From thom...@apache.org
Subject svn commit: r1209568 - in /jackrabbit/sandbox/microkernel/src: main/java/org/apache/jackrabbit/mk/mem/ test/java/org/apache/jackrabbit/mk/large/
Date Fri, 02 Dec 2011 16:31:38 GMT
Author: thomasm
Date: Fri Dec  2 16:31:31 2011
New Revision: 1209568

URL: http://svn.apache.org/viewvc?rev=1209568&view=rev
Log:
Count and persist the number of descendants (direct or indirect child nodes)

Added:
    jackrabbit/sandbox/microkernel/src/test/java/org/apache/jackrabbit/mk/large/DescendantCountTest.java
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/NodeListLarge.java
    jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/NodeMap.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=1209568&r1=1209567&r2=1209568&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
Fri Dec  2 16:31:31 2011
@@ -324,7 +324,7 @@ public class MemoryKernelImpl extends Wr
         head = revNode.store(head, new NodeImpl(nodeMap, rev));
         root = root.setChild("head", head, rev);
         NodeImpl old = root.getNode("old");
-        if (old.getChildNodeCount() > MAX_REVISIONS_PER_NODE) {
+        if (old.getChildCount() > MAX_REVISIONS_PER_NODE) {
             NodeImpl newOld = new NodeImpl(nodeMap, rev);
             old = newOld.setChild("old", old, rev);
         }
@@ -483,6 +483,8 @@ public class MemoryKernelImpl extends Wr
         }
         if (PathUtils.denotesRoot(path)) {
             return true;
+        } else if (path.equals("/:info")) {
+            return true;
         }
         // TODO possibly use a cache / a bloom filter
         return getRevision(revisionId).exists(path.substring(1));

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=1209568&r1=1209567&r2=1209568&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
Fri Dec  2 16:31:31 2011
@@ -34,6 +34,39 @@ import org.apache.jackrabbit.mk.util.Str
  */
 public class NodeImpl implements Cache.Value {
 
+    /**
+     * The child node count.
+     */
+    public static final String CHILREN_COUNT = ":childNodeCount";
+
+    /**
+     * The total number of child nodes.
+     */
+    public static final String DESCENDANT_COUNT = ":descendantCount";
+
+    /**
+     * Used by NodeListLarge when there are many child nodes.
+     * The id of an internal node.
+     */
+    static final String CHILDREN = ":children";
+
+    /**
+     * Used by NodeListLarge when there are many child nodes.
+     * The name bloom filter for a internal node.
+     */
+    static final String NAMES = ":names";
+
+    /**
+     * Used by NodeListLarge when there are many child nodes.
+     * The number of child nodes for an internal node.
+     */
+    static final String COUNT = ":childCount";
+
+    /**
+     * The node name.
+     */
+    private static final String NAME = ":name";
+
     private final long revId;
     private final NodeMap map;
     private String[] propertyValuePairs;
@@ -41,6 +74,7 @@ public class NodeImpl implements Cache.V
     private String path;
     private long id;
     private int memory;
+    private long descendantCount;
 
     public NodeImpl(NodeMap map, long revId) {
         this.map = map;
@@ -67,14 +101,19 @@ public class NodeImpl implements Cache.V
         }
         if (childNodes != null) {
             clone.childNodes = childNodes.createClone(map, revId);
+            clone.descendantCount = descendantCount;
         }
         return clone;
     }
 
-    long getChildNodeCount() {
+    long getChildCount() {
         return childNodes == null ? 0 : childNodes.size();
     }
 
+    public long getDescendantCount() {
+        return descendantCount;
+    }
+
     public boolean exists(String path) {
         if (childNodes == null) {
             return false;
@@ -136,8 +175,11 @@ public class NodeImpl implements Cache.V
         if (n == null) {
             throw ExceptionFactory.get("Node not found: " + path);
         }
+        long diff = -n.descendantCount;
         NodeImpl n2 = n.cloneAndAddChildNode(path.substring(index + 1), before, position,
newNode, revId);
+        diff += n2.descendantCount;
         NodeImpl c = createClone(revId);
+        c.descendantCount += diff;
         c.childNodes.remove(child);
         c.addNode(child, n2);
         return c;
@@ -155,8 +197,11 @@ public class NodeImpl implements Cache.V
         if (n == null) {
             throw ExceptionFactory.get("Node not found: " + path);
         }
+        long diff = -n.descendantCount;
         NodeImpl n2 = n.cloneAndRemoveChildNode(path.substring(index + 1), revId);
+        diff += n2.descendantCount;
         NodeImpl c = createClone(revId);
+        c.descendantCount += diff;
         c.childNodes.remove(child);
         c.addNode(child, n2);
         return c;
@@ -234,11 +279,16 @@ public class NodeImpl implements Cache.V
         }
         if (childNodes == null) {
             if (childNodeCount) {
-                json.key(":childNodeCount").value(0);
+                json.key(CHILREN_COUNT).value(0);
             }
         } else {
             if (childNodeCount) {
-                json.key(":childNodeCount").value(childNodes.size());
+                json.key(CHILREN_COUNT).value(childNodes.size());
+            }
+            if (descendantCount > childNodes.size()) {
+                if (map.getDescendantCount()) {
+                    json.key(DESCENDANT_COUNT).value(descendantCount);
+                }
             }
             if (count != 0) {
                 for (Iterator<String> it = childNodes.getNames(offset, count); it.hasNext();)
{
@@ -266,9 +316,10 @@ public class NodeImpl implements Cache.V
             throw ExceptionFactory.get("Node already exists: " + name);
         }
         if (Constants.NODE_NAME_AS_PROPERTY) {
-            node.setProperty(":name", JsopBuilder.encode(name));
+            node.setProperty(NAME, JsopBuilder.encode(name));
         }
         addNode(name, node);
+        descendantCount += node.descendantCount + 1;
         if (before || position != null) {
             boolean moveNext = false;
             ArrayList<String> move = new ArrayList<String>();
@@ -298,6 +349,12 @@ public class NodeImpl implements Cache.V
         if (childNodes == null) {
             throw ExceptionFactory.get("Node not found: " + name);
         }
+        if (childNodes.size() == 1 || descendantCount <= 1) {
+            descendantCount = 0;
+        } else {
+            NodeImpl n = map.getNode(childNodes.get(name));
+            descendantCount -= n.descendantCount + 1;
+        }
         childNodes.remove(name);
         if (childNodes.size() == 0) {
             childNodes = null;
@@ -368,7 +425,15 @@ public class NodeImpl implements Cache.V
                     node.addChildNode(key, false, null, parse(map, t, revId, childPath));
                 } else {
                     String value = t.readRawValue().trim();
-                    if (!key.equals(":childNodeCount")) {
+                    if (key.length() > 0 && key.charAt(0) == ':') {
+                        if (key.equals(CHILREN_COUNT)) {
+                            // ignore
+                        } else if (key.equals(DESCENDANT_COUNT)) {
+                            node.descendantCount = Long.parseLong(value);
+                        } else {
+                            node.setProperty(key, value);
+                        }
+                    } else {
                         node.setProperty(key, value);
                     }
                 }
@@ -432,6 +497,9 @@ public class NodeImpl implements Cache.V
             }
         }
         if (childNodes != null && childNodes.size() > 0) {
+            if (descendantCount > childNodes.size()) {
+                json.key(DESCENDANT_COUNT).value(descendantCount);
+            }
             childNodes.append(json, map);
         }
         return json.endObject().toString();
@@ -448,8 +516,14 @@ public class NodeImpl implements Cache.V
                 String key = t.readString();
                 t.read(':');
                 String value = t.readRawValue();
-                if (key.equals(":children")) {
-                    node.childNodes = NodeListLarge.read(t, map, value);
+                if (key.length() > 0 && key.charAt(0) == ':') {
+                    if (key.equals(CHILDREN)) {
+                        node.childNodes = NodeListLarge.read(t, map, value);
+                    } else if (key.equals(DESCENDANT_COUNT)) {
+                        node.descendantCount = Long.parseLong(value);
+                    } else {
+                        node.setProperty(key, value);
+                    }
                 } else if (map.isId(value)) {
                     if (node.childNodes == null) {
                         node.childNodes = new NodeListSmall();

Modified: jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/NodeListLarge.java
URL: http://svn.apache.org/viewvc/jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/NodeListLarge.java?rev=1209568&r1=1209567&r2=1209568&view=diff
==============================================================================
--- jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/NodeListLarge.java
(original)
+++ jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/NodeListLarge.java
Fri Dec  2 16:31:31 2011
@@ -232,16 +232,16 @@ public class NodeListLarge implements No
 
     public void append(JsopWriter json, NodeMap map) {
         for (Child c : children) {
-            json.key(":children");
+            json.key(NodeImpl.CHILDREN);
             long x = c.id;
             long y = map.getId(x);
             if (x != y) {
                 c.id = y;
             }
             json.encodedValue(map.formatId(y));
-            json.key(":names").value(StringUtils.convertBytesToHex(c.nameFilter));
+            json.key(NodeImpl.NAMES).value(StringUtils.convertBytesToHex(c.nameFilter));
         }
-        json.key(":childCount").value(size);
+        json.key(NodeImpl.COUNT).value(size);
     }
 
     static NodeListLarge read(JsopTokenizer t, NodeMap map, String value) {
@@ -252,14 +252,14 @@ public class NodeListLarge implements No
         while (t.matches(',')) {
             String k = t.readString();
             t.read(':');
-            if (k.endsWith(":childCount")) {
+            if (k.endsWith(NodeImpl.COUNT)) {
                 list.size = Long.parseLong(t.readRawValue());
-            } else if (k.equals(":children")) {
+            } else if (k.equals(NodeImpl.CHILDREN)) {
                 value = t.readRawValue();
                 c = new Child();
                 c.id = map.parseId(value);
                 list.children.add(c);
-            } else if (k.equals(":names")) {
+            } else if (k.equals(NodeImpl.NAMES)) {
                 c.nameFilter = StringUtils.convertHexToBytes(t.readString());
             } else {
                 throw ExceptionFactory.get("Unexpected " + k);

Modified: jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/NodeMap.java
URL: http://svn.apache.org/viewvc/jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/NodeMap.java?rev=1209568&r1=1209567&r2=1209568&view=diff
==============================================================================
--- jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/NodeMap.java
(original)
+++ jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/NodeMap.java
Fri Dec  2 16:31:31 2011
@@ -25,12 +25,14 @@ import org.apache.jackrabbit.mk.util.Exc
 public class NodeMap {
 
     private static final String MAX_MEMORY_CHILDREN = "maxMemoryChildren";
+    private static final String DESCENDANT_COUNT = "descendantCount";
     private static final int DEFAULT_MAX_MEMORY_CHILDREN = Integer.MAX_VALUE;
 
     private Map<Long, NodeImpl> nodes = Collections.synchronizedMap(new HashMap<Long,
NodeImpl>());
     private AtomicLong nextId = new AtomicLong();
     private AtomicLong rootId = new AtomicLong();
     private int maxMemoryChildren = DEFAULT_MAX_MEMORY_CHILDREN;
+    private boolean descendantCount;
 
     public long addNode(NodeImpl node) {
         long x = node.getId();
@@ -49,6 +51,8 @@ public class NodeMap {
     public void setSetting(String key, String value) {
         if (key.equals(MAX_MEMORY_CHILDREN)) {
             maxMemoryChildren = Integer.parseInt(value);
+        } else if (key.equals(DESCENDANT_COUNT)) {
+            descendantCount = Boolean.parseBoolean(value);
         } else {
             throw ExceptionFactory.get("Unknown setting: " + key);
         }
@@ -99,4 +103,8 @@ public class NodeMap {
         return n;
     }
 
+    public boolean getDescendantCount() {
+        return descendantCount;
+    }
+
 }

Added: jackrabbit/sandbox/microkernel/src/test/java/org/apache/jackrabbit/mk/large/DescendantCountTest.java
URL: http://svn.apache.org/viewvc/jackrabbit/sandbox/microkernel/src/test/java/org/apache/jackrabbit/mk/large/DescendantCountTest.java?rev=1209568&view=auto
==============================================================================
--- jackrabbit/sandbox/microkernel/src/test/java/org/apache/jackrabbit/mk/large/DescendantCountTest.java
(added)
+++ jackrabbit/sandbox/microkernel/src/test/java/org/apache/jackrabbit/mk/large/DescendantCountTest.java
Fri Dec  2 16:31:31 2011
@@ -0,0 +1,89 @@
+/*
+ * 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.mk.large;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.fail;
+import org.apache.jackrabbit.mk.MultiMkTestBase;
+import org.apache.jackrabbit.mk.json.JsopBuilder;
+import org.apache.jackrabbit.mk.json.JsopTokenizer;
+import org.apache.jackrabbit.mk.json.fast.Jsop;
+import org.apache.jackrabbit.mk.json.fast.JsopObject;
+import org.apache.jackrabbit.mk.mem.NodeImpl;
+import org.apache.jackrabbit.mk.mem.NodeMap;
+import org.apache.jackrabbit.mk.util.NodeCreator;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+/**
+ * Test the combined child node count (number of descendants).
+ */
+@RunWith(Parameterized.class)
+public class DescendantCountTest extends MultiMkTestBase {
+
+    public DescendantCountTest(String url) {
+        super(url);
+    }
+
+    @Test
+    public void test() throws Exception {
+        if (!isMemoryKernel(mk)) {
+            return;
+        }
+
+        String head = mk.getHeadRevision();
+        head = mk.commit("/:root/head/config", "^ \"descendantCount\": true", head, "");
+
+        NodeMap map = new NodeMap();
+        NodeCreator c = new NodeCreator(mk);
+        for (int i = 1; i < 100; i++) {
+            c.setNodeName("test" + i);
+            c.setWidth(2);
+            c.setTotalCount(i);
+            c.setData(null);
+            c.create();
+            head = mk.getHeadRevision();
+            String json = JsopBuilder.prettyPrint(mk.getNodes("/test" + i, head, Integer.MAX_VALUE,
0, -1));
+            JsopTokenizer t = new JsopTokenizer(json);
+            t.read('{');
+            NodeImpl n = NodeImpl.parse(map, t, 0);
+            long count = count(n);
+            JsopObject o = (JsopObject) Jsop.parse(json);
+            Object d = o.get(NodeImpl.DESCENDANT_COUNT);
+            if (d != null) {
+                long descendants = Long.parseLong(d.toString());
+                if (count != descendants) {
+                    assertEquals(json, count, descendants + 1);
+                }
+            } else if (i > 10) {
+                fail();
+            }
+        }
+    }
+
+    long count(NodeImpl n) {
+        int count = 1;
+        for (long pos = 0;; pos++) {
+            String childName = n.getChildNodeName(pos);
+            if (childName == null) {
+                break;
+            }
+            NodeImpl c = n.getNode(childName);
+            count += count(c);
+        }
+        return count;
+    }
+
+}



Mime
View raw message