jackrabbit-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From thom...@apache.org
Subject svn commit: r1160283 - in /jackrabbit/sandbox/microkernel/src: main/java/org/apache/jackrabbit/mk/index/ test/java/org/apache/jackrabbit/mk/index/
Date Mon, 22 Aug 2011 14:51:59 GMT
Author: thomasm
Date: Mon Aug 22 14:51:58 2011
New Revision: 1160283

URL: http://svn.apache.org/viewvc?rev=1160283&view=rev
Log:
A simple indexing mechanism (work in progress).

Added:
    jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/
    jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/Cursor.java
    jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/Index.java
    jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/IndexLeaf.java
    jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/IndexNode.java
    jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/IndexPage.java
    jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/Indexer.java
Modified:
    jackrabbit/sandbox/microkernel/src/test/java/org/apache/jackrabbit/mk/index/IndexTest.java

Added: jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/Cursor.java
URL: http://svn.apache.org/viewvc/jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/Cursor.java?rev=1160283&view=auto
==============================================================================
--- jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/Cursor.java (added)
+++ jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/Cursor.java Mon Aug 22 14:51:58 2011
@@ -0,0 +1,72 @@
+/*
+ * 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.index;
+
+import java.util.Iterator;
+
+/**
+ * A cursor to navigate in a result list.
+ */
+public class Cursor implements Iterator<String> {
+
+    private IndexLeaf current;
+    private int pos;
+    private String currentPath;
+
+    public boolean hasNext() {
+        return current != null;
+    }
+
+    public String next() {
+        if (current == null) {
+            currentPath = null;
+            return null;
+        }
+        String data = current.data[pos];
+        currentPath = current.getPath(pos);
+        step();
+        return data;
+    }
+
+    public String getPath() {
+        return currentPath;
+    }
+
+    void step() {
+        while (true) {
+            pos++;
+            if (pos < current.size()) {
+                return;
+            }
+            pos = 0;
+            current = current.nextLeaf();
+            if (current == null || pos < current.size()) {
+                return;
+            }
+        }
+    }
+
+    public void remove() {
+        throw new UnsupportedOperationException();
+    }
+
+    void setCurrent(IndexLeaf current, int pos) {
+        this.current = current;
+        this.pos = pos;
+    }
+
+}

Added: jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/Index.java
URL: http://svn.apache.org/viewvc/jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/Index.java?rev=1160283&view=auto
==============================================================================
--- jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/Index.java (added)
+++ jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/Index.java Mon Aug 22 14:51:58 2011
@@ -0,0 +1,298 @@
+/*
+ * 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.index;
+
+import java.util.Arrays;
+import org.apache.jackrabbit.mk.json.JsopBuilder;
+import org.apache.jackrabbit.mk.mem.NodeImpl;
+import org.apache.jackrabbit.mk.util.PathUtils;
+
+/**
+ * An index allows to query a value for a given key, similar to
+ * <code>java.util.SortedMap</code>. The index is updated automatically.
+ */
+public class Index {
+
+    private final static int DEFAULT_MIN_SIZE = 2;
+
+    private Indexer indexer;
+
+    private String name;
+    private boolean unique = true;
+    private String propertyName;
+    private int minSize = DEFAULT_MIN_SIZE;
+
+    private UnsupportedOperationException uniqueKeyViolation = new UnsupportedOperationException("Unique key violation");
+
+    public Index(Indexer indexer, String name, String propertyName, boolean unique) {
+        this.indexer = indexer;
+        this.name = name;
+        this.propertyName = propertyName;
+        this.unique = unique;
+
+        if (!indexer.nodeExists(name)) {
+            JsopBuilder jsop = new JsopBuilder();
+            jsop.append("+ ").key(name).append("{}");
+            indexer.commit(jsop.toString());
+        }
+    }
+
+    public void setMinSize(int minSize) {
+        if (minSize < 2) {
+            throw new IllegalArgumentException("minSize: " + minSize);
+        }
+        this.minSize = minSize;
+    }
+
+    private boolean isIndexed(NodeImpl a) {
+        return a.hasProperty(propertyName);
+    }
+
+    int find(NodeImpl n, String[] data) {
+        String v = n.getProperty(propertyName);
+        return Arrays.binarySearch(data, v);
+    }
+
+    int compare(NodeImpl a, NodeImpl b) {
+        if (a == b) {
+            return 0;
+        }
+        String pa = a.getProperty(propertyName);
+        String pb = b.getProperty(propertyName);
+        if (pa == null) {
+            return pb == null ? 0 : 1;
+        } else if (pb == null) {
+            return -1;
+        }
+        return pa.compareTo(pb);
+    }
+
+    String data(NodeImpl n) {
+        return n.getProperty(propertyName);
+    }
+
+    IndexPage getPage(IndexNode parent, String name) {
+        return indexer.getPage(this, parent, name);
+    }
+
+    static String[] insert(String[] data, int pos, String d) {
+        String[] data2 = new String[data.length + 1];
+        if (pos > 0 && data.length > 0) {
+            System.arraycopy(data, 0, data2, 0, pos);
+        }
+        data2[pos] = d;
+        if (pos < data.length) {
+            System.arraycopy(data, pos, data2, pos + 1, data.length - pos);
+        }
+        return data2;
+    }
+
+    static String[] delete(String[] data, int pos) {
+        String[] data2 = new String[data.length - 1];
+        if (pos > 0 && data.length > 0) {
+            System.arraycopy(data, 0, data2, 0, pos);
+        }
+        if (pos < data.length) {
+            System.arraycopy(data, pos + 1, data2, pos, data.length - pos - 1);
+        }
+        return data2;
+    }
+
+    public Cursor findFirst(String value) {
+        Cursor c = new Cursor();
+        NodeImpl find = new NodeImpl(0);
+        find.cloneAndSetProperty(propertyName, value, 0);
+        IndexPage node = getPage(null, "");
+        while (true) {
+            int pos = node.find(find);
+            if (node instanceof IndexLeaf) {
+                if (pos < 0) {
+                    pos = -pos - 1;
+                }
+                c.setCurrent((IndexLeaf) node, pos);
+                if (node.size() == 0 || pos >= node.size()) {
+                    c.step();
+                }
+                break;
+            }
+            if (pos < 0) {
+                pos = -pos - 1;
+            } else {
+                pos++;
+            }
+            node = ((IndexNode) node).getChild(pos);
+        }
+        return c;
+    }
+
+    void bufferSetArray(String path, String propertyName, String[] data) {
+        JsopBuilder jsop = new JsopBuilder();
+        path = PathUtils.concat(name, path);
+        jsop.append("^ ").key(PathUtils.concat(path, propertyName));
+        if (data.length == 0) {
+            jsop.append(null);
+        } else {
+            jsop.array();
+            for (String d : data) {
+                jsop.value(d);
+            }
+            jsop.endArray();
+        }
+        jsop.appendWhitespace("\n");
+        indexer.buffer(jsop.toString());
+    }
+
+    void bufferMove(String path, String newPath) {
+        JsopBuilder jsop = new JsopBuilder();
+        jsop.append("> ").key(path).value(newPath);
+        jsop.appendWhitespace("\n");
+        indexer.buffer(jsop.toString());
+    }
+
+    void bufferDelete(String path) {
+        JsopBuilder jsop = new JsopBuilder();
+        jsop.append("- ").value(PathUtils.concat(name, path));
+        jsop.appendWhitespace("\n");
+        indexer.buffer(jsop.toString());
+    }
+
+    void buffer(String jsop) {
+        indexer.buffer(jsop);
+    }
+
+    public boolean remove(NodeImpl remove) {
+        if (!isIndexed(remove)) {
+            return false;
+        }
+        IndexNode parent = null;
+        int parentPos = 0;
+        IndexPage n = getPage(null, "");
+        while (true) {
+            if (n instanceof IndexNode) {
+                IndexNode page = (IndexNode) n;
+                int pos = page.find(remove);
+                if (pos < 0) {
+                    pos = -pos - 1;
+                } else {
+                    pos++;
+                }
+                parent = page;
+                parentPos = pos;
+                n = page.getChild(pos);
+            } else {
+                IndexLeaf page = (IndexLeaf) n;
+                int pos = page.find(remove);
+                if (pos < 0) {
+                    return false;
+                }
+                page.delete(pos);
+                if (n.size() == 0 && parent != null) {
+                    bufferDelete(page.getPath());
+                    // empty leaf with a parent
+                    parent.delete(parentPos);
+                    parent.writeData();
+                } else {
+                    page.writeData();
+                }
+                break;
+            }
+        }
+        commit();
+        return true;
+    }
+
+    public void add(NodeImpl add) {
+        if (!isIndexed(add)) {
+            return;
+        }
+        IndexNode parent = null;
+        int parentPos = 0;
+        IndexPage n = getPage(null, "");
+        while (true) {
+            if (n.size() >= getMaxSize()) {
+                // split
+                int split = getMinSize();
+                if (parent == null) {
+                    // new root
+                    IndexNode root = new IndexNode(this, null, "",
+                            new String[] { n.data[split] },
+                            new String[] { "0", "1" });
+                    n.split(root, "0", split, "1");
+                    n = root;
+                } else {
+                    String data = n.data[split];
+                    String path = parent.getNextChildPath();
+                    n.split(null, null, split, path);
+                    parent.insert(parentPos, data, PathUtils.getName(path));
+                    parent.writeData();
+                    // go back one step (the entry might be in the
+                    // other node now)
+                    n = parent;
+                }
+                // subsequent operations are based on the new structure
+                commit();
+            }
+            if (n instanceof IndexNode) {
+                IndexNode page = (IndexNode) n;
+                int pos = page.find(add);
+                if (pos < 0) {
+                    pos = -pos - 1;
+                } else {
+                    pos++;
+                }
+                parent = page;
+                parentPos = pos;
+                n = page.getChild(pos);
+            } else {
+                IndexLeaf page = (IndexLeaf) n;
+                int pos = page.find(add);
+                if (pos < 0) {
+                    pos = -pos - 1;
+                } else {
+                    if (unique) {
+                        throw uniqueKeyViolation;
+                    }
+                }
+                page.insert(pos, add);
+                page.writeData();
+                break;
+            }
+        }
+        commit();
+    }
+
+    private void commit() {
+        indexer.commit();
+    }
+
+    String getName() {
+        return name;
+    }
+
+    private int getMinSize() {
+        return minSize;
+    }
+
+    private int getMaxSize() {
+        return minSize + minSize + 1;
+    }
+
+    public void setUnique(boolean unique) {
+        this.unique = unique;
+    }
+
+}

Added: jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/IndexLeaf.java
URL: http://svn.apache.org/viewvc/jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/IndexLeaf.java?rev=1160283&view=auto
==============================================================================
--- jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/IndexLeaf.java (added)
+++ jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/IndexLeaf.java Mon Aug 22 14:51:58 2011
@@ -0,0 +1,92 @@
+/*
+ * 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.index;
+
+import java.util.Arrays;
+import org.apache.jackrabbit.mk.json.JsopBuilder;
+import org.apache.jackrabbit.mk.mem.NodeImpl;
+import org.apache.jackrabbit.mk.util.PathUtils;
+
+/**
+ * An index leaf page.
+ */
+class IndexLeaf extends IndexPage {
+
+    private String[] paths;
+
+    IndexLeaf(Index index, IndexNode parent, String path, String[] data, String[] paths) {
+        super(index, parent, path, data);
+        this.paths = paths;
+    }
+
+    IndexLeaf nextLeaf() {
+        return parent == null ? null : parent.next(this);
+    }
+
+    IndexLeaf firstLeaf() {
+        return this;
+    }
+
+    void split(IndexNode newParent, String newName, int pos, String siblingName) {
+        setParent(newParent, newName);
+        String[] d2 = Arrays.copyOfRange(data, pos, data.length, String[].class);
+        String[] p2 = Arrays.copyOfRange(paths, pos, paths.length, String[].class);
+        IndexLeaf n2 = new IndexLeaf(index, parent, siblingName, d2, p2);
+        data = Arrays.copyOfRange(data, 0, pos, String[].class);
+        paths = Arrays.copyOfRange(paths, 0, pos, String[].class);
+        writeData();
+        n2.writeCreate();
+    }
+
+    void insert(int pos, NodeImpl n) {
+        data = Index.insert(data, pos, index.data(n));
+        paths = Index.insert(paths, pos, n.getPath());
+    }
+
+    void delete(int pos) {
+        data = Index.delete(data, pos);
+        paths = Index.delete(paths, pos);
+    }
+
+    void writeData() {
+        index.bufferSetArray(getPath(), "data", data);
+        index.bufferSetArray(getPath(), "paths", paths);
+    }
+
+    void writeCreate() {
+        JsopBuilder jsop = new JsopBuilder();
+        jsop.append("+ ").key(PathUtils.concat(index.getName(), getPath())).object();
+        jsop.key("data").array();
+        for (String d : data) {
+            jsop.value(d);
+        }
+        jsop.endArray();
+        jsop.key("paths").array();
+        for (String d : paths) {
+            jsop.value(d);
+        }
+        jsop.endArray();
+        jsop.endObject();
+        jsop.appendWhitespace("\n");
+        index.buffer(jsop.toString());
+    }
+
+    String getPath(int pos) {
+        return paths[pos];
+    }
+
+}
\ No newline at end of file

Added: jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/IndexNode.java
URL: http://svn.apache.org/viewvc/jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/IndexNode.java?rev=1160283&view=auto
==============================================================================
--- jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/IndexNode.java (added)
+++ jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/IndexNode.java Mon Aug 22 14:51:58 2011
@@ -0,0 +1,125 @@
+/*
+ * 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.index;
+
+import java.util.Arrays;
+import org.apache.jackrabbit.mk.json.JsopBuilder;
+import org.apache.jackrabbit.mk.util.PathUtils;
+
+/**
+ * An index node page.
+ */
+class IndexNode extends IndexPage {
+
+    private String[] children;
+
+    IndexNode(Index index, IndexNode parent, String path, String[] data, String[] children) {
+        super(index, parent, path, data);
+        this.children = children;
+    }
+
+    String getNextChildPath() {
+        int max = 0;
+        for(String c : children) {
+            int x = Integer.parseInt(c);
+            if (x > max) {
+                max = x;
+            }
+        }
+        return Integer.toString(max + 1);
+    }
+
+    IndexLeaf firstLeaf() {
+        return index.getPage(this, children[0]).firstLeaf();
+    }
+
+    void split(IndexNode newParent, String newName, int pos, String siblingName) {
+        setParent(newParent, newName);
+        String[] d2 = Arrays.copyOfRange(data, pos + 1, data.length, String[].class);
+        String[] c2 = Arrays.copyOfRange(children, pos + 1, children.length, String[].class);
+        IndexNode n2 = new IndexNode(index, parent, siblingName, d2, c2);
+        data = Arrays.copyOfRange(data, 0, pos, String[].class);
+        children = Arrays.copyOfRange(children, 0, pos + 1, String[].class);
+        n2.writeCreate();
+        for (String c : n2.children) {
+            index.bufferMove(
+                    PathUtils.concat(index.getName(), getPath(), c),
+                    PathUtils.concat(index.getName(), getParentPath(), siblingName, c)
+            );
+        }
+        writeData();
+    }
+
+    IndexLeaf next(IndexPage child) {
+        int i = 0;
+        String childName = child.name;
+        for (; i < children.length; i++) {
+            if (children[i].equals(childName)) {
+                break;
+            }
+        }
+        if (i == children.length - 1) {
+            return parent == null ? null : parent.next(this);
+        }
+        return index.getPage(this, children[i + 1]).firstLeaf();
+    }
+
+    IndexPage getChild(int pos) {
+        return index.getPage(this, children[pos]);
+    }
+
+    void writeData() {
+        index.bufferSetArray(getPath(), "data", data);
+        index.bufferSetArray(getPath(), "children", children);
+    }
+
+    void writeCreate() {
+        JsopBuilder jsop = new JsopBuilder();
+        jsop.append("+ ").key(PathUtils.concat(index.getName(), getPath())).object();
+        jsop.key("data").array();
+        for (String d : data) {
+            jsop.value(d);
+        }
+        jsop.endArray();
+        // could just use child node list, but then
+        // new children need to be ordered at the right position,
+        // and we would need a way to distinguish empty lists
+        // from a leaf
+        jsop.key("children").array();
+        for (String d : children) {
+            jsop.value(d);
+        }
+        jsop.endArray();
+        jsop.endObject();
+        jsop.appendWhitespace("\n");
+        index.buffer(jsop.toString());
+    }
+
+    void delete(int pos) {
+        if (size() > 0) {
+            // empty parent
+            data = Index.delete(data, Math.max(0, pos - 1));
+        }
+        children = Index.delete(children, pos);
+    }
+
+    void insert(int pos, String d, String c) {
+        data = Index.insert(data, pos, d);
+        children = Index.insert(children, pos + 1, c);
+    }
+
+}
\ No newline at end of file

Added: jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/IndexPage.java
URL: http://svn.apache.org/viewvc/jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/IndexPage.java?rev=1160283&view=auto
==============================================================================
--- jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/IndexPage.java (added)
+++ jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/IndexPage.java Mon Aug 22 14:51:58 2011
@@ -0,0 +1,73 @@
+/*
+ * 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.index;
+
+import org.apache.jackrabbit.mk.mem.NodeImpl;
+import org.apache.jackrabbit.mk.util.PathUtils;
+
+/**
+ * An index page.
+ */
+abstract class IndexPage {
+
+    protected final Index index;
+    protected IndexNode parent;
+    protected String name;
+    protected String[] data;
+
+    IndexPage(Index index, IndexNode parent, String name, String[] data) {
+        this.index = index;
+        this.parent = parent;
+        this.name = name;
+        this.data = data;
+    }
+
+    abstract void writeCreate();
+    abstract void split(IndexNode newParent, String newPath, int pos, String siblingPath);
+    abstract IndexLeaf firstLeaf();
+
+    void setParent(IndexNode newParent, String newName) {
+        if (newParent != null) {
+            index.bufferMove(
+                    PathUtils.concat(index.getName(), getPath()),
+                    "temp");
+            newParent.writeCreate();
+            index.bufferMove(
+                    "temp",
+                    PathUtils.concat(index.getName(), getParentPath(), newName));
+            parent = newParent;
+            name = newName;
+        }
+    }
+
+    String getParentPath() {
+        return parent == null ? "" : parent.getPath();
+    }
+
+    String getPath() {
+        return PathUtils.concat(getParentPath(), name);
+    }
+
+    int size() {
+        return data.length;
+    }
+
+    int find(NodeImpl n) {
+        return index.find(n, data);
+    }
+
+}
\ No newline at end of file

Added: 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=1160283&view=auto
==============================================================================
--- jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/Indexer.java (added)
+++ jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/Indexer.java Mon Aug 22 14:51:58 2011
@@ -0,0 +1,120 @@
+/*
+ * 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.index;
+
+import java.util.ArrayList;
+import org.apache.jackrabbit.mk.api.MicroKernel;
+import org.apache.jackrabbit.mk.json.JsopBuilder;
+import org.apache.jackrabbit.mk.json.JsopTokenizer;
+import org.apache.jackrabbit.mk.mem.NodeImpl;
+import org.apache.jackrabbit.mk.util.PathUtils;
+
+/**
+ * A index mechanism. An index is bound to a certain repository, and supports
+ * one or more indexes.
+ */
+public class Indexer {
+
+    private MicroKernel mk;
+    private String revision;
+    private String indexRootNode;
+    private StringBuilder buffer;
+
+    public Indexer(MicroKernel mk) {
+        this.mk = mk;
+
+        revision = mk.getHeadRevision();
+        indexRootNode = "index";
+        if (!mk.nodeExists("/" + indexRootNode, revision)) {
+            JsopBuilder jsop = new JsopBuilder();
+            jsop.append("+ ").key(indexRootNode).append("{}");
+            revision = mk.commit("/", jsop.toString(), revision, null);
+        }
+    }
+
+    boolean nodeExists(String name) {
+        revision = mk.getHeadRevision();
+        return mk.nodeExists(PathUtils.concat("/" + indexRootNode, name), revision);
+    }
+
+    void commit(String jsop) {
+        revision = mk.commit("/" + indexRootNode, jsop, revision, null);
+    }
+
+    IndexPage getPage(Index index, IndexNode parent, String name) {
+        String p = parent == null ? name : PathUtils.concat(parent.getPath(), name);
+        String indexRoot = PathUtils.concat(indexRootNode, index.getName());
+        String json = mk.getNodes("/" + PathUtils.concat(indexRoot, p), revision);
+        IndexPage page;
+        if (json == null) {
+            page = new IndexLeaf(index, parent, name,
+                    new String[0], new String[0]);
+        } else {
+            JsopTokenizer t = new JsopTokenizer(json);
+            t.read('{');
+            NodeImpl n = NodeImpl.parse(t, 0);
+            String data = n.getProperty("data");
+            String paths = n.getProperty("paths");
+            String children = n.getProperty("children");
+            if (children != null) {
+                IndexNode node = new IndexNode(index, parent, name,
+                        readArray(data), readArray(children));
+                page = node;
+            } else {
+                IndexLeaf leaf = new IndexLeaf(index, parent, name,
+                        readArray(data), readArray(paths));
+                page = leaf;
+            }
+        }
+        return page;
+    }
+
+    private static String[] readArray(String json) {
+        if (json == null) {
+            return new String[0];
+        }
+        ArrayList<String> dataList = new ArrayList<String>();
+        JsopTokenizer t = new JsopTokenizer(json);
+        t.read('[');
+        if (!t.matches(']')) {
+            do {
+                dataList.add(t.readString());
+            } while (t.matches(','));
+            t.read(']');
+        }
+        String[] data = new String[dataList.size()];
+        dataList.toArray(data);
+        return data;
+    }
+
+    void buffer(String diff) {
+        if (buffer == null) {
+            buffer = new StringBuilder(diff.length());
+        }
+        buffer.append(diff);
+    }
+
+    void commit() {
+        if (buffer != null) {
+            String jsop = buffer.toString();
+            // System.out.println(jsop);
+            revision = mk.commit("/" + indexRootNode, jsop, revision, null);
+            buffer = null;
+        }
+    }
+
+}

Modified: jackrabbit/sandbox/microkernel/src/test/java/org/apache/jackrabbit/mk/index/IndexTest.java
URL: http://svn.apache.org/viewvc/jackrabbit/sandbox/microkernel/src/test/java/org/apache/jackrabbit/mk/index/IndexTest.java?rev=1160283&r1=1160282&r2=1160283&view=diff
==============================================================================
--- jackrabbit/sandbox/microkernel/src/test/java/org/apache/jackrabbit/mk/index/IndexTest.java (original)
+++ jackrabbit/sandbox/microkernel/src/test/java/org/apache/jackrabbit/mk/index/IndexTest.java Mon Aug 22 14:51:58 2011
@@ -16,39 +16,37 @@
  */
 package org.apache.jackrabbit.mk.index;
 
-import java.util.ArrayList;
-import java.util.Arrays;
-import java.util.Iterator;
+import java.util.Random;
+import java.util.TreeMap;
+import junit.framework.TestCase;
 import org.apache.jackrabbit.mk.MicroKernelFactory;
 import org.apache.jackrabbit.mk.api.MicroKernel;
-import org.apache.jackrabbit.mk.json.JsopBuilder;
 import org.apache.jackrabbit.mk.json.JsopTest;
-import org.apache.jackrabbit.mk.json.JsopTokenizer;
 import org.apache.jackrabbit.mk.mem.NodeImpl;
-import org.apache.jackrabbit.mk.util.PathUtils;
 
 /**
- * An indexing mechanism.
+ * Tests the indexing mechanism.
  */
-public class IndexTest {
+public class IndexTest extends TestCase {
 
-    public static void main(String... args) {
-        test("mem:");
+    // private static final String URL = "fs:{homeDir}/target;clean";
+    private static final String URL = "mem:fs:target/temp;clean";
+    // private static final String URL = "mem:";
 
-        // TODO doesn't work yet (problems with move operations?)
-        // test("fs:{homeDir}/target;clean");
-
-    }
-
-    static void log(String s) {
-        System.out.println(s);
+    public void test() {
+        testAscending(URL);
+        testRandom(URL);
+        testDuplicateKey(URL, true);
+        testDuplicateKey(URL, false);
     }
 
-    private static void test(String url) {
+    private void testAscending(String url) {
         MicroKernel mk = MicroKernelFactory.getInstance(url);
-        Index index = new Index(mk, "test", "id");
+        Indexer indexer = new Indexer(mk);
+        Index index = new Index(indexer, "test", "id", true);
+        index.setMinSize(2);
         print(mk, index);
-        int len = 1000;
+        int len = 30;
         for (int i = 0; i < len; i++) {
             NodeImpl n;
             n = new NodeImpl(0);
@@ -58,6 +56,13 @@ public class IndexTest {
             index.add(n);
             // print(mk, index);
         }
+        for (int i = 0; i < len; i++) {
+            // log("#test " + i);
+            Cursor c = index.findFirst("" + i);
+            if (c.hasNext()) {
+                assertEquals("" + i, c.next());
+            }
+        }
         print(mk, index);
         for (int i = 0; i < len; i++) {
             NodeImpl n;
@@ -65,590 +70,122 @@ public class IndexTest {
             n = n.cloneAndSetProperty("id", "" + i, 0);
             n.setPath("i" + i);
             log("#remove " + i);
-            if (!index.remove(n)) {
-                throw new AssertionError("" + i);
-            }
-            print(mk, index);
+            assertTrue("not found when removing " + i, index.remove(n));
+            // print(mk, index);
         }
         print(mk, index);
-        mk.dispose();
-    }
-
-    static void print(MicroKernel mk, Index index) {
-        String head = mk.getHeadRevision();
-        String tree = mk.getNodes("/index", head, 100, 0, -1);
-        log(JsopTest.format(tree));
-        Cursor c = index.findFirst("0");
-        StringBuilder buff = new StringBuilder();
-        while (c.hasNext()) {
-            buff.append(c.next()).append(' ');
+        for (int i = 0; i < len; i++) {
+            Cursor c = index.findFirst("" + i);
+            assertFalse(c.hasNext());
         }
-        log(buff.toString());
+        mk.dispose();
     }
 
-    static class IndexComparator {
-        String propertyName;
-        IndexComparator(String propertyName) {
-            this.propertyName = propertyName;
-        }
-        boolean isIndexed(NodeImpl a) {
-            return a.hasProperty(propertyName);
-        }
-        int find(NodeImpl n, String[] data) {
-            String v = n.getProperty(propertyName);
-            return Arrays.binarySearch(data, v);
-        }
-        int compare(NodeImpl a, NodeImpl b) {
-            if (a == b) {
-                return 0;
-            }
-            String pa = a.getProperty(propertyName);
-            String pb = b.getProperty(propertyName);
-            if (pa == null) {
-                return pb == null ? 0 : 1;
-            } else if (pb == null) {
-                return -1;
+    private void testDuplicateKey(String url, boolean unique) {
+        MicroKernel mk = MicroKernelFactory.getInstance(url);
+        Indexer indexer = new Indexer(mk);
+        Index index = new Index(indexer, "test", "id", true);
+        index.setUnique(unique);
+        index.setMinSize(2);
+        NodeImpl n = new NodeImpl(0);
+        n.setPath("p1");
+        n.cloneAndSetProperty("id", "1", 0);
+        index.add(n);
+        n = new NodeImpl(0);
+        n.setPath("p1b");
+        n.cloneAndSetProperty("id", "1", 0);
+        if (unique) {
+            try {
+                index.add(n);
+                fail();
+            } catch (UnsupportedOperationException e) {
+                // expected
             }
-            return pa.compareTo(pb);
-        }
-
-        String data(NodeImpl n) {
-            return n.getProperty(propertyName);
+        } else {
+            index.add(n);
         }
-
-        public String[] remove(String[] data, int pos) {
-            String[] data2 = new String[data.length - 1];
-            System.arraycopy(data, 0, data2, 0, pos);
-            System.arraycopy(data, pos + 1, data2, pos, data.length - pos);
-            return data2;
+        Cursor c = index.findFirst("1");
+        if (!unique) {
+            assertEquals("1", c.next());
+            assertEquals("p1b", c.getPath());
+        }
+        assertEquals("1", c.next());
+        assertEquals("p1", c.getPath());
+        try {
+            c.remove();
+            fail();
+        } catch (UnsupportedOperationException e) {
+            // expected
         }
-
+        assertFalse(c.hasNext());
+        assertEquals(null, c.next());
+        mk.dispose();
     }
 
-    static class Index {
-        MicroKernel mk;
-        String revision;
-        String name;
-        IndexComparator comparator;
-        boolean unique = true;
-        RuntimeException uniqueKeyViolation = new RuntimeException("Unique key violation");
-        private String indexRootNode;
-        private StringBuilder buffer;
-
-        static String[] insert(String[] data, int pos, String d) {
-            String[] data2 = new String[data.length + 1];
-            if (pos > 0 && data.length > 0) {
-                System.arraycopy(data, 0, data2, 0, pos);
-            }
-            data2[pos] = d;
-            if (pos < data.length) {
-                System.arraycopy(data, pos, data2, pos + 1, data.length - pos);
-            }
-            return data2;
-        }
-
-        static String[] delete(String[] data, int pos) {
-            String[] data2 = new String[data.length - 1];
-            if (pos > 0 && data.length > 0) {
-                System.arraycopy(data, 0, data2, 0, pos);
-            }
-            if (pos < data.length) {
-                System.arraycopy(data, pos + 1, data2, pos, data.length - pos - 1);
-            }
-            return data2;
-        }
-
-        IndexPage getPage(IndexNode parent, String name) {
-            String p = parent == null ? name : PathUtils.concat(parent.getPath(), name);
-            String index = PathUtils.concat(indexRootNode, this.name);
-            String json = mk.getNodes("/" + PathUtils.concat(index, p), revision);
-            IndexPage page;
-            if (json == null) {
-                page = new IndexLeaf(this, parent, name);
-            } else {
-                JsopTokenizer t = new JsopTokenizer(json);
-                t.read('{');
-                NodeImpl n = NodeImpl.parse(t, 0);
-                String data = n.getProperty("data");
-                String paths = n.getProperty("paths");
-                String children = n.getProperty("children");
-                if (children != null) {
-                    IndexNode node = new IndexNode(this, parent, name);
-                    node.data = readArray(data);
-                    node.children = readArray(children);
-                    page = node;
-                } else {
-                    IndexLeaf leaf = new IndexLeaf(this, parent, name);
-                    leaf.data = readArray(data);
-                    leaf.paths = readArray(paths);
-                    page = leaf;
-                }
-            }
-            return page;
-        }
-
-        static String[] readArray(String json) {
-            if (json == null) {
-                return new String[0];
-            }
-            ArrayList<String> dataList = new ArrayList<String>();
-            JsopTokenizer t = new JsopTokenizer(json);
-            t.read('[');
-            if (!t.matches(']')) {
-                do {
-                    dataList.add(t.readString());
-                } while (t.matches(','));
-                t.read(']');
-            }
-            String[] data = new String[dataList.size()];
-            dataList.toArray(data);
-            return data;
-        }
-
-        Index(MicroKernel mk, String name, String propertyName) {
-            this.mk = mk;
-            this.name = name;
-            comparator = new IndexComparator(propertyName);
-            revision = mk.getHeadRevision();
-            indexRootNode = "index";
-            if (!mk.nodeExists(PathUtils.concat("/" + indexRootNode, name), revision)) {
-                if (!mk.nodeExists("/" + indexRootNode, revision)) {
-                    JsopBuilder jsop = new JsopBuilder();
-                    jsop.append("+ ").key(indexRootNode).append("{}");
-                    revision = mk.commit("/", jsop.toString(), revision, null);
-                }
-                JsopBuilder jsop = new JsopBuilder();
-                jsop.append("+ ").key(name).append("{}");
-                revision = mk.commit("/" + indexRootNode, jsop.toString(), revision, null);
-            }
-        }
-
-        Cursor findFirst(String value) {
-            Cursor c = new Cursor();
-            NodeImpl find = new NodeImpl(0);
-            find.cloneAndSetProperty(comparator.propertyName, value, 0);
-            IndexPage node = getPage(null, "");
-            while (true) {
-                int pos = node.find(find);
-                if (pos >= 0) {
-                    c.pos = pos;
-                } else {
-                    pos = -pos - 1;
-                }
-                if (node instanceof IndexLeaf) {
-                    c.current = (IndexLeaf) node;
-                    if (node.size() == 0) {
-                        c.step();
-                    }
-                    break;
-                } else {
-                    node = ((IndexNode) node).getChild(pos);
+    private void testRandom(String url) {
+        MicroKernel mk = MicroKernelFactory.getInstance(url);
+        Indexer indexer = new Indexer(mk);
+        Index index = new Index(indexer, "test", "id", true);
+        index.setMinSize(2);
+        Random r = new Random(1);
+        TreeMap<Integer, String> tree = new TreeMap<Integer, String>();
+        for (int i = 0; i < 100; i++) {
+            if (i==31)
+            log("op #" + i);
+            print(mk, index);
+            int x = r.nextInt(10);
+            boolean exists = tree.containsKey(x);
+            Cursor c = index.findFirst("" + x);
+            boolean gotExists = c.hasNext();
+            String x2 = null;
+            if (gotExists) {
+                x2 = c.next();
+                if (!x2.equals("" + x)) {
+                    gotExists = false;
+                }
+            }
+            assertEquals(exists, gotExists);
+            if (exists) {
+                assertEquals("" + x, x2);
+                assertEquals(tree.get(x), c.getPath());
+            }
+            boolean add = r.nextBoolean();
+            if (add) {
+                if (!exists) {
+                    log("#insert " + x + " = p" + i);
+                    NodeImpl n = new NodeImpl(0);
+                    tree.put(x, "p" + i);
+                    n.setPath("p" + i);
+                    n.cloneAndSetProperty("id", "" + x, 0);
+                    index.add(n);
                 }
-            }
-            return c;
-        }
-
-        void bufferSetArray(String path, String propertyName, String[] data) {
-            JsopBuilder jsop = new JsopBuilder();
-            path = PathUtils.concat(name, path);
-            jsop.append("^ ").key(PathUtils.concat(path, propertyName));
-            if (data.length == 0) {
-                jsop.append(null);
             } else {
-                jsop.array();
-                for (String d : data) {
-                    jsop.value(d);
+                if (exists) {
+                    log("#remove " + x);
+                    tree.remove(x);
+                    NodeImpl n = new NodeImpl(0);
+                    n.cloneAndSetProperty("id", "" + x, 0);
+                    index.remove(n);
                 }
-                jsop.endArray();
-            }
-            jsop.appendWhitespace("\n");
-            buffer(jsop.toString());
-        }
-
-        void bufferMove(String path, String newPath) {
-            JsopBuilder jsop = new JsopBuilder();
-            jsop.append("> ").key(path).value(newPath);
-            jsop.appendWhitespace("\n");
-            buffer(jsop.toString());
-        }
-
-        public void bufferDelete(String path) {
-            JsopBuilder jsop = new JsopBuilder();
-            jsop.append("- ").value(PathUtils.concat(name, path));
-            jsop.appendWhitespace("\n");
-            buffer(jsop.toString());
-        }
-
-        void buffer(String diff) {
-            if (buffer == null) {
-                buffer = new StringBuilder(diff.length());
-            }
-            buffer.append(diff);
-        }
-
-        boolean remove(NodeImpl remove) {
-            if (!comparator.isIndexed(remove)) {
-                return false;
-            }
-            IndexNode parent = null;
-            int parentPos = 0;
-            IndexPage n = getPage(null, "");
-            while (true) {
-                if (n instanceof IndexNode) {
-                    IndexNode page = (IndexNode) n;
-                    int pos = page.find(remove);
-                    if (pos < 0) {
-                        pos = -pos - 1;
-                    } else {
-                        pos++;
-                    }
-                    parent = page;
-                    parentPos = pos;
-                    n = page.getChild(pos);
-                } else {
-                    IndexLeaf page = (IndexLeaf) n;
-                    int pos = page.find(remove);
-                    if (pos < 0) {
-                        return false;
-                    }
-                    page.delete(pos);
-                    page.writeData();
-                    if (n.size() == 0 && parent != null) {
-                        // empty leaf with a parent
-                        if (parent.size() > 0) {
-                            // empty parent
-                            parent.data = Index.delete(parent.data, Math.max(0, parentPos - 1));
-                        }
-                        parent.children = Index.delete(parent.children, parentPos);
-                        parent.writeData();
-                    }
-                    break;
-                }
-            }
-            commit();
-            return true;
-        }
-
-        void add(NodeImpl add) {
-            if (!comparator.isIndexed(add)) {
-                return;
-            }
-            IndexNode parent = null;
-            int parentPos = 0;
-            IndexPage n = getPage(null, "");
-            while (true) {
-                if (n.size() >= IndexPage.MAX_SIZE) {
-                    // split
-                    int split = IndexPage.MIN_SIZE;
-                    if (parent == null) {
-                        // new root
-                        IndexNode root = new IndexNode(this, null, null);
-                        root.children = new String[] { "0", "1" };
-                        root.data = new String[] { n.data[split] };
-                        root.name = "";
-                        n.split(root, "0", split, "1");
-                        n = root;
-                    } else {
-                        String data = n.data[split];
-                        String path = parent.getNextChildPath();
-                        n.split(null, null, split, path);
-                        parent.data = Index.insert(parent.data, parentPos, data);
-                        parent.children = Index.insert(parent.children, parentPos + 1, PathUtils.getName(path));
-                        parent.writeData();
-                        // go back one step (the entry might be in the
-                        // other node now)
-                        n = parent;
-                    }
-                    // subsequent operations are based on the new structure
-                    commit();
-                }
-                if (n instanceof IndexNode) {
-                    IndexNode page = (IndexNode) n;
-                    int pos = page.find(add);
-                    if (pos < 0) {
-                        pos = -pos - 1;
-                    }
-                    parent = page;
-                    parentPos = pos;
-                    n = page.getChild(pos);
-                } else {
-                    IndexLeaf page = (IndexLeaf) n;
-                    int pos = page.find(add);
-                    if (pos < 0) {
-                        pos = -pos - 1;
-                    } else {
-                        if (unique) {
-                            throw uniqueKeyViolation;
-                        }
-                    }
-                    page.insert(pos, add);
-                    page.writeData();
-                    break;
-                }
-            }
-            commit();
-        }
-
-        private void commit() {
-            if (buffer != null) {
-                String jsop = buffer.toString();
-                // log(jsop);
-                revision = mk.commit("/" + indexRootNode, jsop, revision, null);
-                buffer = null;
-            }
-        }
-
-        public String getName() {
-            return name;
-        }
-
-    }
-
-    abstract static class IndexPage {
-
-        final static int MIN_SIZE = 2;
-        final static int MAX_SIZE = 2 * MIN_SIZE + 1;
-        protected final Index index;
-        protected IndexNode parent;
-        String name;
-
-        String[] data;
-
-        IndexPage(Index index, IndexNode parent, String name) {
-            this.index = index;
-            this.parent = parent;
-            this.name = name;
-        }
-
-        abstract void writeCreate();
-        abstract void split(IndexNode newParent, String newPath, int pos, String siblingPath);
-        abstract IndexLeaf firstLeaf();
-
-        void setParent(IndexNode newParent, String newName) {
-            if (newParent != null) {
-                index.bufferMove(
-                        PathUtils.concat(index.getName(), getPath()),
-                        "temp");
-                newParent.writeCreate();
-                index.bufferMove(
-                        "temp",
-                        PathUtils.concat(index.getName(), getParentPath(), newName));
-                parent = newParent;
-                name = newName;
-            }
-        }
-
-        String getParentPath() {
-            return parent == null ? "" : parent.getPath();
-        }
-
-        String getPath() {
-            return PathUtils.concat(getParentPath(), name);
-        }
-
-        int size() {
-            return data.length;
-        }
-
-        int find(NodeImpl n) {
-            return index.comparator.find(n, data);
-        }
-
-    }
-
-    static class IndexLeaf extends IndexPage {
-
-        String[] paths = new String[0];
-
-        IndexLeaf(Index index, IndexNode parent, String path) {
-            super(index, parent, path);
-        }
-
-        IndexLeaf nextLeaf() {
-            return parent == null ? null : parent.next(this);
-        }
-
-        IndexLeaf firstLeaf() {
-            return this;
-        }
-
-        void split(IndexNode newParent, String newName, int pos, String siblingName) {
-            setParent(newParent, newName);
-            IndexLeaf n2 = new IndexLeaf(index, parent, siblingName);
-            n2.data = Arrays.copyOfRange(data, pos, data.length, String[].class);
-            data = Arrays.copyOfRange(data, 0, pos, String[].class);
-            n2.paths = Arrays.copyOfRange(paths, pos, paths.length, String[].class);
-            paths = Arrays.copyOfRange(paths, 0, pos, String[].class);
-            writeData();
-            n2.writeCreate();
-        }
-
-        void insert(int pos, NodeImpl n) {
-            data = Index.insert(data, pos, index.comparator.data(n));
-            paths = Index.insert(paths, pos, n.getPath());
-        }
-
-        void delete(int pos) {
-            data = Index.delete(data, pos);
-            paths = Index.delete(paths, pos);
-        }
-
-        void writeData() {
-            if (data.length == 0) {
-                index.bufferDelete(getPath());
-            } else {
-                index.bufferSetArray(getPath(), "data", data);
-                index.bufferSetArray(getPath(), "paths", paths);
             }
         }
-
-        void writeCreate() {
-            JsopBuilder jsop = new JsopBuilder();
-            jsop.append("+ ").key(PathUtils.concat(index.getName(), getPath())).object();
-            jsop.key("data").array();
-            for (String d : data) {
-                jsop.value(d);
-            }
-            jsop.endArray();
-            jsop.key("paths").array();
-            for (String d : paths) {
-                jsop.value(d);
-            }
-            jsop.endArray();
-            jsop.endObject();
-            jsop.appendWhitespace("\n");
-            index.buffer(jsop.toString());
-        }
-
+        mk.dispose();
     }
 
-    static class IndexNode extends IndexPage {
-
-        String[] children = new String[0];
-
-        IndexNode(Index index, IndexNode parent, String path) {
-            super(index, parent, path);
-        }
-
-        void insert(int pos, NodeImpl n) {
-            data = Index.insert(data, pos, n.getPath());
-        }
-
-        public String getNextChildPath() {
-            int max = 0;
-            for(String c : children) {
-                int x = Integer.parseInt(c);
-                if (x > max) {
-                    max = x;
-                }
-            }
-            return Integer.toString(max + 1);
-        }
-
-        IndexLeaf firstLeaf() {
-            return index.getPage(this, children[0]).firstLeaf();
-        }
-
-        void split(IndexNode newParent, String newName, int pos, String siblingName) {
-            setParent(newParent, newName);
-            IndexNode n2 = new IndexNode(index, parent, siblingName);
-            n2.data = Arrays.copyOfRange(data, pos + 1, data.length, String[].class);
-            data = Arrays.copyOfRange(data, 0, pos, String[].class);
-            n2.children = Arrays.copyOfRange(children, pos + 1, children.length, String[].class);
-            children = Arrays.copyOfRange(children, 0, pos + 1, String[].class);
-            n2.writeCreate();
-            for (String c : n2.children) {
-                index.bufferMove(
-                        PathUtils.concat(index.getName(), getPath(), c),
-                        PathUtils.concat(index.getName(), getParentPath(), siblingName, c)
-                );
-            }
-            writeData();
-        }
-
-        IndexLeaf next(IndexPage child) {
-            int i = 0;
-            String childName = child.name;
-            for (; i < children.length; i++) {
-                if (children[i].equals(childName)) {
-                    break;
-                }
-            }
-            if (i == children.length - 1) {
-                return parent == null ? null : parent.next(this);
-            }
-            return index.getPage(this, children[i + 1]).firstLeaf();
-        }
-
-        public IndexPage getChild(int pos) {
-            return index.getPage(this, children[pos]);
-        }
-
-        void writeData() {
-            index.bufferSetArray(getPath(), "data", data);
-            index.bufferSetArray(getPath(), "children", children);
-        }
-
-        void writeCreate() {
-            JsopBuilder jsop = new JsopBuilder();
-            jsop.append("+ ").key(PathUtils.concat(index.getName(), getPath())).object();
-            jsop.key("data").array();
-            for (String d : data) {
-                jsop.value(d);
-            }
-            jsop.endArray();
-            // could just use child node list, but then
-            // new children need to be ordered at the right position,
-            // and we would need a way to distinguish empty lists
-            // from a leaf
-            jsop.key("children").array();
-            for (String d : children) {
-                jsop.value(d);
-            }
-            jsop.endArray();
-            jsop.endObject();
-            jsop.appendWhitespace("\n");
-            index.buffer(jsop.toString());
-        }
-
+    static void log(String s) {
+        // System.out.println(s);
     }
 
-    static class Cursor implements Iterator<String> {
-
-        IndexLeaf current;
-        int pos;
-
-        public boolean hasNext() {
-            return current != null;
-        }
-
-        public String next() {
-            if (current == null) {
-                return null;
-            }
-            String data = current.data[pos];
-            step();
-            return data;
-        }
-
-        void step() {
-            while (true) {
-                pos++;
-                if (pos < current.size()) {
-                    return;
-                }
-                pos = 0;
-                current = current.nextLeaf();
-                if (current == null || pos < current.size()) {
-                    return;
-                }
-            }
-        }
-
-        public void remove() {
-            throw new UnsupportedOperationException();
+    static void print(MicroKernel mk, Index index) {
+        String head = mk.getHeadRevision();
+        String tree = mk.getNodes("/index", head, 100, 0, -1);
+        log(JsopTest.format(tree));
+        Cursor c = index.findFirst("0");
+        StringBuilder buff = new StringBuilder();
+        while (c.hasNext()) {
+            buff.append(c.next()).append(' ');
         }
-
+        log(buff.toString());
     }
 
 }



Mime
View raw message