You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@jackrabbit.apache.org by th...@apache.org on 2011/12/02 17:31:38 UTC
svn commit: r1209568 - in /jackrabbit/sandbox/microkernel/src:
main/java/org/apache/jackrabbit/mk/mem/
test/java/org/apache/jackrabbit/mk/large/
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;
+ }
+
+}