From commits-return-11826-apmail-jackrabbit-commits-archive=jackrabbit.apache.org@jackrabbit.apache.org Wed Sep 7 08:55:23 2011 Return-Path: X-Original-To: apmail-jackrabbit-commits-archive@www.apache.org Delivered-To: apmail-jackrabbit-commits-archive@www.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id E465D89B7 for ; Wed, 7 Sep 2011 08:55:23 +0000 (UTC) Received: (qmail 64738 invoked by uid 500); 7 Sep 2011 08:55:22 -0000 Delivered-To: apmail-jackrabbit-commits-archive@jackrabbit.apache.org Received: (qmail 64610 invoked by uid 500); 7 Sep 2011 08:55:12 -0000 Mailing-List: contact commits-help@jackrabbit.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@jackrabbit.apache.org Delivered-To: mailing list commits@jackrabbit.apache.org Received: (qmail 64590 invoked by uid 99); 7 Sep 2011 08:55:11 -0000 Received: from athena.apache.org (HELO athena.apache.org) (140.211.11.136) by apache.org (qpsmtpd/0.29) with ESMTP; Wed, 07 Sep 2011 08:55:11 +0000 X-ASF-Spam-Status: No, hits=-2000.0 required=5.0 tests=ALL_TRUSTED,T_FILL_THIS_FORM_SHORT X-Spam-Check-By: apache.org Received: from [140.211.11.4] (HELO eris.apache.org) (140.211.11.4) by apache.org (qpsmtpd/0.29) with ESMTP; Wed, 07 Sep 2011 08:55:08 +0000 Received: from eris.apache.org (localhost [127.0.0.1]) by eris.apache.org (Postfix) with ESMTP id 311DF23888EA; Wed, 7 Sep 2011 08:54:48 +0000 (UTC) Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Subject: svn commit: r1166067 - in /jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk: index/ mem/ util/ Date: Wed, 07 Sep 2011 08:54:47 -0000 To: commits@jackrabbit.apache.org From: thomasm@apache.org X-Mailer: svnmailer-1.0.8 Message-Id: <20110907085448.311DF23888EA@eris.apache.org> Author: thomasm Date: Wed Sep 7 08:54:47 2011 New Revision: 1166067 URL: http://svn.apache.org/viewvc?rev=1166067&view=rev Log: Trying to support large child node lists (WIP) and other changes (exception handling). Modified: jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/Indexer.java 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/NodeList.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/NodeListSmall.java jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/NodeMap.java jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/Revision.java jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/util/IOUtils.java Modified: jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/Indexer.java URL: http://svn.apache.org/viewvc/jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/Indexer.java?rev=1166067&r1=1166066&r2=1166067&view=diff ============================================================================== --- jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/Indexer.java (original) +++ jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/Indexer.java Wed Sep 7 08:54:47 2011 @@ -328,7 +328,7 @@ public class Indexer { index.addOrRemoveNode(n, true); } } - for (Iterator it = n.getChildNodeNames(); it.hasNext();) { + for (Iterator it = n.getChildNodeNames(Integer.MAX_VALUE); it.hasNext();) { addOrRemoveRecursive(n.getNode(it.next()), remove, add); } } 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=1166067&r1=1166066&r2=1166067&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 Sep 7 08:54:47 2011 @@ -17,13 +17,13 @@ package org.apache.jackrabbit.mk.mem; import org.apache.jackrabbit.mk.api.MicroKernel; -import org.apache.jackrabbit.mk.api.MicroKernelException; import org.apache.jackrabbit.mk.blobs.AbstractBlobStore; import org.apache.jackrabbit.mk.blobs.FileBlobStore; import org.apache.jackrabbit.mk.blobs.MemoryBlobStore; import org.apache.jackrabbit.mk.json.JsopBuilder; import org.apache.jackrabbit.mk.json.JsopTokenizer; import org.apache.jackrabbit.mk.util.CommitGate; +import org.apache.jackrabbit.mk.util.ExceptionFactory; import org.apache.jackrabbit.mk.util.NonDescendingClock; import org.apache.jackrabbit.mk.util.PathUtils; import org.apache.jackrabbit.mk.util.SmallLRUCache; @@ -33,6 +33,7 @@ import java.util.ArrayList; import java.util.Collections; import java.util.HashMap; import java.util.Iterator; +import java.util.Map.Entry; /* @@ -71,6 +72,9 @@ public class MemoryKernelImpl implements private String lastJournalRevRange, lastJournal; private MemoryKernelImpl(String name) { + if (DEBUG) { + log("open " + name); + } nodeMap = new NodeMap(); if (name.startsWith("fs:")) { String dir = name.substring("fs:".length()); @@ -81,8 +85,10 @@ public class MemoryKernelImpl implements if (nodeMap.getRootId() == 0) { clear(); } else { - String rev = getRoot().getNode("head").getProperty("rev"); + NodeImpl head = getRoot().getNode("head"); + String rev = head.getProperty("rev"); headRevId = Revision.parseId(JsopTokenizer.decodeQuoted(rev)); + applyConfig(head); } } @@ -96,6 +102,9 @@ public class MemoryKernelImpl implements } public void clear() { + if (DEBUG) { + log("clear"); + } headRevId = 0; ds.clear(); nodeMap.clear(); @@ -103,112 +112,124 @@ public class MemoryKernelImpl implements 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); } + private void applyConfig(NodeImpl head) { + NodeImpl config = head.getNode("config"); + for (Entry e : config.getProperties()) { + nodeMap.setSetting(e.getKey(), e.getValue()); + } + } + public synchronized String commit(String rootPath, String jsonDiff, String revisionId, String message) { // TODO do we really need 'path'? store the path is in the diff instead // TODO what is the exact meaning of 'revisionId'? is it allowed to commit // using an old revision, if yes when is it allowed, or how is it different from using head? // TODO increment headRevId less often? commit in the background? // would be possible if we don't (always) return the head revision - // TODO property type as comment versus as special property // TODO metadata in storage (version) // TODO optional read / write version in json 'api' (as comments?) if (DEBUG) { - System.out.println("commit " + jsonDiff); + log("commit " + rootPath + " " + jsonDiff + " " + message); } - long oldRevision = headRevId; - long rev = headRevId + 1; + try { + return doCommit(rootPath, jsonDiff, revisionId, message); + } catch (Exception e) { + if (DEBUG) { + log("commit failed with exception: " + e); + } + throw ExceptionFactory.convert(e); + } + } + + private String doCommit(String rootPath, String jsonDiff, String revisionId, String message) { + long oldRevision = headRevId, rev = headRevId + 1; NodeImpl root = nodeMap.getNode(nodeMap.getRootId()); - NodeImpl head = root.getNode("head"); - NodeImpl oldHead = head; + NodeImpl head = root.getNode("head"), oldHead = head; NodeImpl data = head.getNode("data"); - JsopBuilder w = new JsopBuilder(); + JsopBuilder diff = new JsopBuilder(); JsopTokenizer t = new JsopTokenizer(jsonDiff); - String fromRoot = PathUtils.relativize("/", rootPath); while (true) { int r = t.read(); if (r == JsopTokenizer.END) { break; } - String path; + String path = PathUtils.concat(rootPath, t.readString()); + String from = PathUtils.relativize("/", path); switch (r) { case '+': - path = t.readString(); - w.appendTag("+ ").key(PathUtils.concat(rootPath, path)); t.read(':'); + diff.appendTag("+ ").key(path); // TODO support adding a property? t.read('{'); NodeImpl n = NodeImpl.parse(nodeMap, t, rev); - data = data.cloneAndAddChildNode(PathUtils.concat(fromRoot, path), false, null, n, rev); - n.append(w, -1, 0, -1, false); - w.newline(); + data = data.cloneAndAddChildNode(from, false, null, n, rev); + n.append(diff, -1, 0, Integer.MAX_VALUE, false); + diff.newline(); break; case '-': - path = t.readString(); - w.appendTag("- ").value(PathUtils.concat(rootPath, path)); - data = data.cloneAndRemoveChildNode(PathUtils.concat(fromRoot, path), rev); - w.newline(); + diff.appendTag("- ").value(path).newline(); + data = data.cloneAndRemoveChildNode(from, rev); break; case '^': - path = t.readString(); t.read(':'); + boolean isConfigChange = from.startsWith(":root/head/config/"); String value; if (t.matches(JsopTokenizer.NULL)) { value = null; - w.appendTag("^ ").key(PathUtils.concat(rootPath, path)); - w.value(null); + diff.appendTag("^ ").key(path).value(null); } else { value = t.readRawValue().trim(); - String nodeName = PathUtils.concat(fromRoot, PathUtils.getParentPath(path)); - String propertyName = PathUtils.getName(path); - if (data.getNode(nodeName).hasProperty(propertyName)) { - w.appendTag("^ ").key(PathUtils.concat(rootPath, path)); + String nodeName = PathUtils.getParentPath(from); + String propertyName = PathUtils.getName(from); + if (isConfigChange || data.getNode(nodeName).hasProperty(propertyName)) { + diff.appendTag("^ "); } else { - w.appendTag("+ ").key(PathUtils.concat(rootPath, path)); + diff.appendTag("+ "); } - w.encodedValue(value); + diff.key(path).encodedValue(value); } - data = data.cloneAndSetProperty(PathUtils.concat(fromRoot, path), value, rev); - w.newline(); + if (isConfigChange) { + String p = PathUtils.relativize(":root/head", from); + head = head.cloneAndSetProperty(p, value, rev); + applyConfig(head); + } else { + data = data.cloneAndSetProperty(from, value, rev); + } + diff.newline(); break; case '>': - path = t.readString(); - String from = PathUtils.concat(fromRoot, path); - String name = PathUtils.getName(from); - w.appendTag("> ").key(PathUtils.concat(rootPath, from)); t.read(':'); - String position, target; + diff.appendTag("> ").key(path); + String name = PathUtils.getName(from); + String position, target, to; boolean rename; - String to; if (t.matches('{')) { rename = false; position = t.readString(); t.read(':'); target = t.readString(); t.read('}'); - w.object().key(position); - if (PathUtils.isAbsolute(target)) { - w.value(target); - } else { - w.value(PathUtils.concat(rootPath, target)); + diff.object().key(position); + if (!PathUtils.isAbsolute(target)) { + target = PathUtils.concat(rootPath, target); } - w.endObject(); + diff.value(target).endObject(); } else { rename = true; position = null; target = t.readString(); - if (PathUtils.isAbsolute(target)) { - w.value(target); - } else { - w.value(PathUtils.concat(rootPath, target)); + if (!PathUtils.isAbsolute(target)) { + target = PathUtils.concat(rootPath, target); } + diff.value(target); } - w.newline(); + diff.newline(); boolean before = false; if ("last".equals(position)) { target = PathUtils.concat(target, name); @@ -229,13 +250,9 @@ public class MemoryKernelImpl implements } else if (position == null) { // move } else { - throw new AssertionError("position: " + position); - } - if (PathUtils.isAbsolute(target)) { - to = PathUtils.relativize("/", target); - } else { - to = PathUtils.concat(fromRoot, target); + throw ExceptionFactory.get("position: " + position); } + to = PathUtils.relativize("/", target); boolean inPlaceRename = false; if (rename) { if (PathUtils.getParentPath(from).equals(PathUtils.getParentPath(to))) { @@ -253,11 +270,14 @@ public class MemoryKernelImpl implements } break; default: - throw new AssertionError("token: " + (char) t.getTokenType()); + throw ExceptionFactory.get("token: " + (char) t.getTokenType()); } } + if (DEBUG) { + log(diff.toString()); + } head = head.setChild("data", data, rev); - Revision revNode = new Revision(rev, clock.time(), w.toString(), message); + Revision revNode = new Revision(rev, clock.time(), diff.toString(), message); revisionCache.put(rev, revNode); head = revNode.store(head, new NodeImpl(nodeMap, rev)); root = root.setChild("head", head, rev); @@ -275,7 +295,7 @@ public class MemoryKernelImpl implements return headRev; } - NodeImpl getRoot() { + private NodeImpl getRoot() { return nodeMap.getNode(nodeMap.getRootId()); } @@ -285,7 +305,7 @@ public class MemoryKernelImpl implements public String getRevisions(long since, int maxEntries) { if (DEBUG) { - System.out.println("getRevisions " + since); + log("getRevisions " + since); } NodeImpl node = getRoot(); ArrayList revisions = new ArrayList(); @@ -294,7 +314,7 @@ public class MemoryKernelImpl implements revisions.add(r); while (node.exists("old")) { node = node.getNode("old"); - for (Iterator it = node.getChildNodeNames(); it.hasNext();) { + for (Iterator it = node.getChildNodeNames(Integer.MAX_VALUE); it.hasNext();) { r = Revision.get(revisionCache, node.getNode(it.next())); if (r != null) { revisions.add(r); @@ -312,7 +332,11 @@ public class MemoryKernelImpl implements buff.encodedValue(rev.toString()); } } - return buff.endArray().toString(); + String result = buff.endArray().toString(); + if (DEBUG) { + log("getRevisions returned " + getHead(result)); + } + return result; } public String waitForCommit(String oldHeadRevision, long maxWaitMillis) throws InterruptedException { @@ -321,7 +345,7 @@ public class MemoryKernelImpl implements public String getJournal(String fromRevisionId, String toRevisionId) { if (DEBUG) { - System.out.println("getJournal " + fromRevisionId + " " + toRevisionId); + log("getJournal " + fromRevisionId + " " + toRevisionId); } String revRange = fromRevisionId + "-" + toRevisionId; synchronized (this) { @@ -329,19 +353,19 @@ public class MemoryKernelImpl implements return lastJournal; } } - long fromRevId = Revision.parseId(fromRevisionId); - long toRevId = Revision.parseId(toRevisionId); + long fromRev = Revision.parseId(fromRevisionId); + long toRev = Revision.parseId(toRevisionId); NodeImpl node = getRoot(); ArrayList revisions = new ArrayList(); Revision r = Revision.get(revisionCache, node.getNode("head")); - if (r.getId() >= fromRevId) { + if (r.getId() >= fromRev) { revisions.add(r); } - while (r.getId() > fromRevId && node.exists("old")) { + while (r.getId() > fromRev && node.exists("old")) { node = node.getNode("old"); - for (Iterator it = node.getChildNodeNames(); it.hasNext();) { + for (Iterator it = node.getChildNodeNames(Integer.MAX_VALUE); it.hasNext();) { r = Revision.get(revisionCache, node.getNode(it.next())); - if (r != null && r.getId() >= fromRevId && r.getId() <= toRevId) { + if (r != null && r.getId() >= fromRev && r.getId() <= toRev) { revisions.add(r); } } @@ -349,7 +373,7 @@ public class MemoryKernelImpl implements Collections.sort(revisions); JsopBuilder buff = new JsopBuilder().array().newline(); for (Revision rev : revisions) { - if (rev.getId() >= fromRevId && rev.getId() <= toRevId) { + if (rev.getId() >= fromRev && rev.getId() <= toRev) { rev.appendJournal(buff); } } @@ -357,23 +381,53 @@ public class MemoryKernelImpl implements lastJournalRevRange = revRange; lastJournal = buff.endArray().toString(); } + if (DEBUG) { + log("getJournal returned " + getHead(lastJournal)); + } return lastJournal; } + private String getHead(String s) { + return s.length() < 100 ? s : (s.substring(0, 100) + "..."); + } + public String getNodes(String path, String revisionId) { - return getNodes(path, revisionId, 1, 0, -1); + if (DEBUG) { + log("getNodes " + path + " revision:" + revisionId); + } + String result = doGetNodes(path, revisionId, 1, 0, -1); + if (DEBUG) { + log("getNodes returned " + getHead(result)); + } + return result; } public String getNodes(String path, String revisionId, int depth, long offset, int count) { if (DEBUG) { - System.out.println("getNodes " + path + " " + revisionId + " " + depth + " " + offset + " " + count); + log("getNodes " + path + " revision:" + revisionId + " depth:" + depth + " offset:" + offset + " count:" + count); + } + String result = doGetNodes(path, revisionId, depth, offset, count); + if (DEBUG) { + log("getNodes returned " + getHead(result)); + } + return result; + } + + private String doGetNodes(String path, String revisionId, int depth, long offset, int count) { + if (count < 0) { + count = nodeMap.getMaxMemoryChildren(); } if (!PathUtils.isAbsolute(path)) { - throw new IllegalArgumentException("Not an absolute path: " + path); + throw ExceptionFactory.get("Not an absolute path: " + path); + } + NodeImpl n; + if (path.startsWith("/:root")) { + n = getRoot().getNode(path.substring(7)); + } else { + n = getRevision(revisionId).getNode(path.substring(1)); } - NodeImpl n = getRevision(revisionId).getNode(path.substring(1)); if (n == null) { - throw new RuntimeException("Path not found: " + path); + throw ExceptionFactory.get("Path not found: " + path); } JsopBuilder json = new JsopBuilder(); n.append(json, depth, offset, count, true); @@ -387,11 +441,11 @@ public class MemoryKernelImpl implements node = node.getNode("head"); } else { if (DEBUG) { - System.out.println("getRevision " + revisionId); + log("getRevision " + revisionId); } while (true) { if (!node.exists("old")) { - throw new RuntimeException("Revision not found: " + revisionId); + throw ExceptionFactory.get("Revision not found: " + revisionId); } node = node.getNode("old"); if (node.exists(revisionId)) { @@ -405,55 +459,52 @@ public class MemoryKernelImpl implements public boolean nodeExists(String path, String revisionId) { if (DEBUG) { - System.out.println("nodeExists " + path + " " + revisionId); + log("nodeExists " + path + " revision:" + revisionId); } - - // TODO possibly use a bloom filter if (!PathUtils.isAbsolute(path)) { - throw new IllegalArgumentException("Not an absolute path: " + path); + throw ExceptionFactory.get("Not an absolute path: " + path); + } + // TODO possibly use a cache / a bloom filter + boolean result = getRevision(revisionId).exists(path.substring(1)); + if (DEBUG) { + log("nodeExists returned " + result); } - return getRevision(revisionId).exists(path.substring(1)); + return result; } public long getLength(String blobId) { if (DEBUG) { - System.out.println("getLength " + blobId); - } - try { - return ds.getBlobLength(blobId); - } catch (Exception e) { - throw new MicroKernelException(e); + log("getLength " + blobId); } + return ds.getBlobLength(blobId); } public int read(String blobId, long pos, byte[] buff, int off, int length) { if (DEBUG) { - System.out.println("read " + blobId); - } - try { - return ds.readBlob(blobId, pos, buff, off, length); - } catch (Exception e) { - throw new MicroKernelException(e); + log("read " + blobId); } + return ds.readBlob(blobId, pos, buff, off, length); } public String write(InputStream in) { if (DEBUG) { - System.out.println("write " + in); - } - try { - return ds.writeBlob(in); - } catch (Exception e) { - throw new MicroKernelException(e); + log("write " + in); } + return ds.writeBlob(in); } public void dispose() { if (DEBUG) { - System.out.println("dispose"); + log("dispose"); } gate.commit("end"); nodeMap.close(); } + private static void log(String s) { + if (DEBUG) { + System.out.println(s); + } + } + } 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=1166067&r1=1166066&r2=1166067&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 Sep 7 08:54:47 2011 @@ -19,6 +19,7 @@ package org.apache.jackrabbit.mk.mem; import org.apache.jackrabbit.mk.Constants; import org.apache.jackrabbit.mk.json.JsopBuilder; import org.apache.jackrabbit.mk.json.JsopTokenizer; +import org.apache.jackrabbit.mk.util.ExceptionFactory; import org.apache.jackrabbit.mk.util.PathUtils; import java.util.ArrayList; @@ -45,7 +46,7 @@ public class NodeImpl { this.revId = revId; } - public long getId() { + long getId() { return id; } @@ -62,12 +63,12 @@ public class NodeImpl { clone.properties = new HashMap(properties); } if (childNodes != null) { - clone.childNodes = childNodes.createClone(map); + clone.childNodes = childNodes.createClone(map, revId); } return clone; } - public long getChildNodeCount() { + long getChildNodeCount() { return childNodes == null ? 0 : childNodes.size(); } @@ -126,11 +127,11 @@ public class NodeImpl { } String child = path.substring(0, index); if (childNodes == null) { - throw new RuntimeException("Node not found: " + path); + throw ExceptionFactory.get("Node not found: " + path); } NodeImpl n = getChildNode(child); if (n == null) { - throw new RuntimeException("Node not found: " + path); + throw ExceptionFactory.get("Node not found: " + path); } NodeImpl n2 = n.cloneAndAddChildNode(path.substring(index + 1), before, position, newNode, revId); NodeImpl c = createClone(revId); @@ -139,7 +140,7 @@ public class NodeImpl { return c; } - public NodeImpl cloneAndRemoveChildNode(String path, long revId) { + NodeImpl cloneAndRemoveChildNode(String path, long revId) { int index = PathUtils.getNextSlash(path, 0); if (index < 0) { NodeImpl clone = createClone(revId); @@ -149,7 +150,7 @@ public class NodeImpl { String child = path.substring(0, index); NodeImpl n = getChildNode(child); if (n == null) { - throw new RuntimeException("Node not found: " + path); + throw ExceptionFactory.get("Node not found: " + path); } NodeImpl n2 = n.cloneAndRemoveChildNode(path.substring(index + 1), revId); NodeImpl c = createClone(revId); @@ -168,7 +169,7 @@ public class NodeImpl { String child = path.substring(0, index); NodeImpl n = getChildNode(child); if (n == null) { - throw new RuntimeException("Node not found: " + path); + throw ExceptionFactory.get("Node not found: " + path); } NodeImpl n2 = n.cloneAndSetProperty(path.substring(index + 1), value, revId); NodeImpl c = createClone(revId); @@ -185,7 +186,7 @@ public class NodeImpl { return properties == null ? null : properties.get(propertyName); } - public void append(JsopBuilder json, int depth, long offset, int count, boolean childNodeCount) { + void append(JsopBuilder json, int depth, long offset, int count, boolean childNodeCount) { json.object(); if (properties != null) { for (Entry e : properties.entrySet()) { @@ -201,10 +202,7 @@ public class NodeImpl { json.key(":childNodeCount").value(childNodes.size()); } if (count != 0) { - for (Iterator it = childNodes.getNames(offset); it.hasNext() && count != 0;) { - if (count > 0) { - count--; - } + for (Iterator it = childNodes.getNames(offset, count); it.hasNext();) { String s = it.next(); json.key(s); if (depth == 0) { @@ -226,7 +224,7 @@ public class NodeImpl { if (childNodes == null) { childNodes = new NodeListSmall(); } else if (childNodes.containsKey(name)) { - throw new RuntimeException("Node already exists: " + name); + throw ExceptionFactory.get("Node already exists: " + name); } if (Constants.NODE_NAME_AS_PROPERTY) { node.setProperty(":name", JsopBuilder.encode(name)); @@ -235,7 +233,7 @@ public class NodeImpl { if (before || position != null) { boolean moveNext = false; ArrayList move = new ArrayList(); - for (Iterator it = childNodes.getNames(0); it.hasNext();) { + for (Iterator it = childNodes.getNames(0, Integer.MAX_VALUE); it.hasNext();) { String entry = it.next(); if (entry.equals(name)) { // don't move new entry @@ -257,9 +255,9 @@ public class NodeImpl { } } - void removeChildNode(String name) { + private void removeChildNode(String name) { if (childNodes == null) { - throw new RuntimeException("Node not found: " + name); + throw ExceptionFactory.get("Node not found: " + name); } childNodes.remove(name); if (childNodes.size() == 0) { @@ -317,11 +315,11 @@ public class NodeImpl { return path; } - public Iterator getChildNodeNames() { + public Iterator getChildNodeNames(int maxCount) { if (childNodes == null || childNodes.size() == 0) { return new ArrayList().iterator(); } - return childNodes.getNames(0); + return childNodes.getNames(0, maxCount); } public Iterable> getProperties() { @@ -351,16 +349,7 @@ public class NodeImpl { } } if (childNodes != null && childNodes.size() > 0) { - for (Iterator it = childNodes.getNames(0); it.hasNext();) { - String n = it.next(); - json.key(n); - long x = childNodes.get(n); - long y = map.getId(x); - if (x != y) { - childNodes.setId(n, y); - } - json.encodedValue(map.formatId(y)); - } + childNodes.append(json, map); } return json.endObject().toString(); } @@ -376,7 +365,9 @@ public class NodeImpl { String key = t.readString(); t.read(':'); String value = t.readRawValue(); - if (map.isId(value)) { + if (key.equals(":children")) { + node.childNodes = NodeListLarge.read(t, map, value); + } else if (map.isId(value)) { if (node.childNodes == null) { node.childNodes = new NodeListSmall(); } @@ -391,9 +382,16 @@ public class NodeImpl { } NodeList getNodeList() { + if (childNodes == null) { + childNodes = new NodeListSmall(); + } return childNodes; } + void setNodeList(NodeList childNodes) { + this.childNodes = childNodes; + } + NodeImpl setChild(String name, NodeImpl child, long revId) { NodeImpl result = this; if (exists(name)) { Modified: jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/NodeList.java URL: http://svn.apache.org/viewvc/jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/NodeList.java?rev=1166067&r1=1166066&r2=1166067&view=diff ============================================================================== --- jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/NodeList.java (original) +++ jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/NodeList.java Wed Sep 7 08:54:47 2011 @@ -1,8 +1,28 @@ +/* + * 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.mem; import java.util.Iterator; +import org.apache.jackrabbit.mk.json.JsopBuilder; import org.apache.jackrabbit.mk.mem.NodeImpl.ChildVisitor; +/** + * A list of child nodes. + */ interface NodeList { long size(); @@ -13,14 +33,16 @@ interface NodeList { void add(String name, long x); - void setId(String name, long x); - - Iterator getNames(long offset); + Iterator getNames(long offset, int maxCount); long remove(String name); - NodeList createClone(NodeMap map); + NodeList createClone(NodeMap map, long revId); void visit(ChildVisitor v); + void append(JsopBuilder json, NodeMap map); + + byte[] getNameFilter(NodeMap map); + } 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=1166067&r1=1166066&r2=1166067&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 Wed Sep 7 08:54:47 2011 @@ -17,97 +17,101 @@ package org.apache.jackrabbit.mk.mem; import java.util.ArrayList; -import java.util.BitSet; import java.util.Iterator; -import java.util.LinkedHashMap; +import org.apache.jackrabbit.mk.json.JsopBuilder; +import org.apache.jackrabbit.mk.json.JsopTokenizer; import org.apache.jackrabbit.mk.mem.NodeImpl.ChildVisitor; - +import org.apache.jackrabbit.mk.util.ExceptionFactory; +import org.apache.jackrabbit.mk.util.IOUtils; +import org.h2.util.StringUtils; + +/** + * A large list of nodes. + */ public class NodeListLarge implements NodeList { - private static final int BLOOM_FILTER_SIZE = 256; - ArrayList children; private final NodeMap map; + private final long revId; private long size; - NodeListLarge(NodeMap map, ArrayList children) { + private NodeListLarge(NodeMap map, ArrayList children, long revId) { this.map = map; - children = new ArrayList(); + this.children = children; + this.revId = revId; + for (Child c : children) { + size += getList(c, false).size(); + } } - public NodeListLarge(NodeMap map, LinkedHashMap list) { + NodeListLarge(NodeMap map, NodeList list, long size, long revId) { this.map = map; - NodeImpl childNode = new NodeImpl(map, 0); - long id = map.addNode(childNode); + this.children = new ArrayList(); + this.revId = revId; Child c = new Child(); - c.id = id; - children = new ArrayList(); + NodeImpl n = new NodeImpl(map, revId); + n.setNodeList(list); + c.id = map.addNode(n); + c.nameFilter = list.getNameFilter(map); children.add(c); - // TODO Auto-generated constructor stub + this.size = size; } public boolean containsKey(String name) { for (Child c : children) { if (c.possiblyContains(name)) { - return getList(c).containsKey(name); - } - } - return false; - } - - public void setId(String name, long x) { - for (Child c : children) { - if (c.possiblyContains(name)) { - if (getList(c).containsKey(name)) { -// getList(c).get + if (getList(c, false).containsKey(name)) { + return true; } } } - throw new RuntimeException("Node node found: " + name); + return false; } - NodeList getList(Child c) { + NodeList getList(Child c, boolean modify) { NodeImpl n = map.getNode(c.id); + if (modify) { + n = n.createClone(revId); + c.id = map.addNode(n); + } return n.getNodeList(); } public long get(String name) { for (Child c : children) { if (c.possiblyContains(name)) { - NodeList child = getList(c); + NodeList child = getList(c, false); if (child.containsKey(name)) { return child.get(name); } } } - throw new RuntimeException("Node node found: " + name); + throw ExceptionFactory.get("Node not found: " + name); } - public Iterator getNames(long offset) { + public Iterator getNames(long offset, final int maxCount) { int i = 0; for (; i < children.size(); i++) { Child c = children.get(i); - if (c.size < offset) { - offset -= c.size; - continue; + long size = getList(c, false).size(); + if (size > offset) { + break; } + offset -= size; } final int start = i; final long off = offset; Iterator it = new Iterator() { int pos = start; + int remaining = maxCount; long offset = off; Iterator it; public boolean hasNext() { - if (it == null) { - return false; - } - if (it.hasNext()) { + if (it != null && it.hasNext()) { return true; } - it = null; while (pos < children.size()) { - it = getList(children.get(pos++)).getNames(offset); + it = getList(children.get(pos++), false).getNames(offset, remaining); offset = 0; if (it.hasNext()) { return true; @@ -118,6 +122,7 @@ public class NodeListLarge implements No public String next() { if (hasNext()) { + remaining--; return it.next(); } else { return null; @@ -133,26 +138,33 @@ public class NodeListLarge implements No public void add(String name, long x) { Child c = children.get(children.size() - 1); - NodeList child = getList(c); + NodeList child = getList(c, false); + if (child.size() >= map.getMaxMemoryChildren()) { + c = new Child(); + c.id = map.addNode(new NodeImpl(map, revId)); + children.add(c); + } + child = getList(c, true); child.add(name, x); + c.nameFilter = child.getNameFilter(map); size++; } public long remove(String name) { for (Child c : children) { if (c.possiblyContains(name)) { - NodeList child = getList(c); + NodeList child = getList(c, true); if (child.containsKey(name)) { Long x = child.remove(name); if (x == null) { - throw new RuntimeException("Could not remove " + name); + throw ExceptionFactory.get("Could not remove " + name); } size--; return x; } } } - throw new RuntimeException("Node node found: " + name); + throw ExceptionFactory.get("Node node found: " + name); } public long size() { @@ -160,30 +172,42 @@ public class NodeListLarge implements No } static class Child { - NodeMap map; + long id; + byte[] nameFilter; - BitSet nameBloomFilter = new BitSet(BLOOM_FILTER_SIZE); - long size; boolean possiblyContains(String name) { - return nameBloomFilter.get(name.hashCode() & (BLOOM_FILTER_SIZE - 1)); - } - void addName(String name) { - nameBloomFilter.set(name.hashCode() & (BLOOM_FILTER_SIZE - 1)); + int h = name.hashCode(); + int b = nameFilter[(h >> 3) & (nameFilter.length - 1)] & (h & 255); + return b != 0; } + } - public NodeList createClone(NodeMap map) { + public NodeList createClone(NodeMap map, long revId) { + if (revId == this.revId) { + return this; + } if (size < map.getMaxMemoryChildren() / 2) { NodeListSmall s = new NodeListSmall(); - for (Iterator it = getNames(0); it.hasNext();) { + for (Iterator it = getNames(0, Integer.MAX_VALUE); it.hasNext();) { String n = it.next(); s.add(n, get(n)); } return s; } - int todo; - return new NodeListLarge(map, children); + ArrayList newChildren = new ArrayList(); + for (Child c : children) { + Child c2 = new Child(); + c2.id = map.addNode(map.getNode(c.id)); + c2.nameFilter = c.nameFilter; + newChildren.add(c2); + } + NodeListLarge result = new NodeListLarge(map, newChildren, revId); + if (children.size() > map.getMaxMemoryChildren()) { + return new NodeListLarge(map, result, size, revId); + } + return result; } public void visit(ChildVisitor v) { @@ -192,4 +216,58 @@ public class NodeListLarge implements No } } + public void append(JsopBuilder json, NodeMap map) { + for (Child c : children) { + json.key(":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(":childCount").value(size); + } + + static NodeListLarge read(JsopTokenizer t, NodeMap map, String value) { + NodeListLarge list = new NodeListLarge(map, new ArrayList(), 0); + Child c = new Child(); + c.id = map.parseId(value); + list.children.add(c); + while (t.matches(',')) { + String k = t.readString(); + t.read(':'); + if (k.endsWith(":childCount")) { + list.size = Long.parseLong(t.readRawValue()); + } else if (k.equals(":children")) { + value = t.readRawValue(); + c = new Child(); + c.id = map.parseId(value); + list.children.add(c); + } else if (k.equals(":names")) { + c.nameFilter = StringUtils.convertHexToBytes(t.readString()); + } else { + throw ExceptionFactory.get("Unexpected " + k); + } + } + return list; + } + + public byte[] getNameFilter(NodeMap map) { + int len = IOUtils.nextPowerOf2(Math.min(64, map.getMaxMemoryChildren() / 4)); + for (Child c : children) { + if (c.nameFilter.length < len) { + len = c.nameFilter.length; + } + } + byte[] data = new byte[len]; + for (Child c : children) { + for (int i = 0; i < len; i++) { + data[i] |= c.nameFilter[i]; + } + } + return data; + } + } Modified: jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/NodeListSmall.java URL: http://svn.apache.org/viewvc/jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/NodeListSmall.java?rev=1166067&r1=1166066&r2=1166067&view=diff ============================================================================== --- jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/NodeListSmall.java (original) +++ jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/NodeListSmall.java Wed Sep 7 08:54:47 2011 @@ -19,6 +19,8 @@ package org.apache.jackrabbit.mk.mem; import java.util.Iterator; import org.apache.jackrabbit.mk.json.JsopBuilder; import org.apache.jackrabbit.mk.mem.NodeImpl.ChildVisitor; +import org.apache.jackrabbit.mk.util.ExceptionFactory; +import org.apache.jackrabbit.mk.util.IOUtils; import org.apache.jackrabbit.mk.util.StringUtils; public class NodeListSmall implements NodeList { @@ -77,7 +79,7 @@ public class NodeListSmall implements No public long get(String name) { int index = find(name); if (index < 0) { - throw new RuntimeException("Node node found: " + name); + throw ExceptionFactory.get("Node node found: " + name); } return children[sort[index]]; } @@ -85,7 +87,7 @@ public class NodeListSmall implements No public void add(String name, long x) { int index = find(name); if (index >= 0) { - throw new RuntimeException("Node already exists: " + name); + throw ExceptionFactory.get("Node already exists: " + name); } index = -index - 1; names = StringUtils.arrayInsert(names, size, name); @@ -94,21 +96,15 @@ public class NodeListSmall implements No size++; } - public void setId(String name, long x) { - int index = find(name); - if (index < 0) { - throw new RuntimeException("Node node found: " + name); - } - children[sort[index]] = x; - } - - public Iterator getNames(final long offset) { + public Iterator getNames(final long offset, final int maxCount) { return new Iterator() { int pos = (int) offset; + int remaining = maxCount; public boolean hasNext() { - return pos < size; + return pos < size && remaining > 0; } public String next() { + remaining--; return names[pos++]; } public void remove() { @@ -120,7 +116,7 @@ public class NodeListSmall implements No public long remove(String name) { int index = find(name); if (index < 0) { - throw new RuntimeException("Node not found: " + name); + throw ExceptionFactory.get("Node not found: " + name); } int s = sort[index]; long result = children[s]; @@ -148,11 +144,12 @@ public class NodeListSmall implements No return json.toString(); } - public NodeList createClone(NodeMap map) { -// if (size > map.getMaxMemoryChildren()) { -// return new NodeListLarge(map, list); -// } - return new NodeListSmall(names, children, sort, size); + public NodeList createClone(NodeMap map, long revId) { + NodeList result = new NodeListSmall(names, children, sort, size); + if (size > map.getMaxMemoryChildren()) { + return new NodeListLarge(map, result, size, revId); + } + return result; } public void visit(ChildVisitor v) { @@ -161,4 +158,26 @@ public class NodeListSmall implements No } } + public void append(JsopBuilder json, NodeMap map) { + for (int i = 0; i < size; i++) { + json.key(names[i]); + long x = children[i]; + long y = map.getId(x); + if (x != y) { + children[i] = y; + } + json.encodedValue(map.formatId(y)); + } + } + + public byte[] getNameFilter(NodeMap map) { + int len = IOUtils.nextPowerOf2(Math.min(64, map.getMaxMemoryChildren() / 4)); + byte[] data = new byte[len]; + for (String n : names) { + int h = n.hashCode(); + data[(h >> 3) & (data.length - 1)] |= h & 255; + } + return data; + } + } 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=1166067&r1=1166066&r2=1166067&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 Wed Sep 7 08:54:47 2011 @@ -17,15 +17,17 @@ package org.apache.jackrabbit.mk.mem; import java.util.HashMap; +import org.apache.jackrabbit.mk.util.ExceptionFactory; public class NodeMap { - private static final int MAX_MEMORY_CHILDREN = Integer.MAX_VALUE; + private static final String MAX_MEMORY_CHILDREN = "maxMemoryChildren"; + private static final int DEFAULT_MAX_MEMORY_CHILDREN = Integer.MAX_VALUE; private HashMap nodes = new HashMap(); private long nextId = 1; private long rootId; - private int maxMemoryChildren = MAX_MEMORY_CHILDREN; + private int maxMemoryChildren = DEFAULT_MAX_MEMORY_CHILDREN; public long addNode(NodeImpl node) { long x = node.getId(); @@ -46,6 +48,14 @@ public class NodeMap { nextId = 1; } + public void setSetting(String key, String value) { + if (key.equals(MAX_MEMORY_CHILDREN)) { + maxMemoryChildren = Integer.parseInt(value); + } else { + throw ExceptionFactory.get("Unknown setting: " + key); + } + } + public void setMaxMemoryChildren(int max) { maxMemoryChildren = max; } @@ -71,11 +81,11 @@ public class NodeMap { } public String formatId(long id) { - return "n" + id; + return "n" + Long.toHexString(id); } public long parseId(String id) { - return Long.parseLong(id.substring(1)); + return Long.parseLong(id.substring(1), 16); } public boolean isId(String value) { 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=1166067&r1=1166066&r2=1166067&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 Sep 7 08:54:47 2011 @@ -31,7 +31,7 @@ public class Revision implements Compara private String diff; private String msg; - public Revision(long id, long time, String diff, String msg) { + Revision(long id, long time, String diff, String msg) { this.id = id; this.time = time; this.diff = diff; @@ -58,22 +58,22 @@ public class Revision implements Compara return r; } - public long getId() { + long getId() { return id; } - public long getTime() { + long getTime() { return time; } - public String getDiff() { + private String getDiff() { if (diff == null) { diff = getCommitValue("diff"); } return diff; } - public String getMsg() { + private String getMsg() { if (msg == null) { msg = getCommitValue("msg"); } @@ -119,7 +119,7 @@ public class Revision implements Compara return head.setChild("commit", commit, id); } - public void appendJournal(JsopBuilder buff) { + void appendJournal(JsopBuilder buff) { buff.object(). key("id").value(Revision.formatId(id)). key("ts").value(time). Modified: jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/util/IOUtils.java URL: http://svn.apache.org/viewvc/jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/util/IOUtils.java?rev=1166067&r1=1166066&r2=1166067&view=diff ============================================================================== --- jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/util/IOUtils.java (original) +++ jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/util/IOUtils.java Wed Sep 7 08:54:47 2011 @@ -222,4 +222,19 @@ public class IOUtils { } } + /** + * Get the value that is equal or higher than this value, and that is a + * power of two. + * + * @param x the original value + * @return the next power of two value + */ + public static int nextPowerOf2(int x) { + long i = 1; + while (i < x && i < (Integer.MAX_VALUE / 2)) { + i += i; + } + return (int) i; + } + }