jackrabbit-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From thom...@apache.org
Subject svn commit: r1162723 - in /jackrabbit/sandbox/microkernel/src: main/java/org/apache/jackrabbit/mk/index/ main/java/org/apache/jackrabbit/mk/mem/ test/java/org/apache/jackrabbit/mk/index/
Date Mon, 29 Aug 2011 10:44:13 GMT
Author: thomasm
Date: Mon Aug 29 10:44:12 2011
New Revision: 1162723

URL: http://svn.apache.org/viewvc?rev=1162723&view=rev
Log:
Index mechanism (WIP)

Added:
    jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/BTree.java
    jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/BTreeLeaf.java
      - copied, changed from r1162161, jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/IndexLeaf.java
    jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/BTreePage.java
      - copied, changed from r1162161, jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/IndexPage.java
    jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/PrefixIndex.java
    jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/PropertyIndex.java
    jackrabbit/sandbox/microkernel/src/test/java/org/apache/jackrabbit/mk/index/PrefixIndexTest.java
    jackrabbit/sandbox/microkernel/src/test/java/org/apache/jackrabbit/mk/index/PropertyIndexTest.java
      - copied, changed from r1162115, jackrabbit/sandbox/microkernel/src/test/java/org/apache/jackrabbit/mk/index/IdentifierIndexTest.java
Modified:
    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
    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/test/java/org/apache/jackrabbit/mk/index/IdentifierIndexTest.java
    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/BTree.java
URL: http://svn.apache.org/viewvc/jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/BTree.java?rev=1162723&view=auto
==============================================================================
--- jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/BTree.java (added)
+++ jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/BTree.java Mon Aug 29 10:44:12 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 org.apache.jackrabbit.mk.json.JsopBuilder;
+import org.apache.jackrabbit.mk.util.PathUtils;
+
+/**
+ * A tree allows to query a value for a given key, similar to
+ * <code>java.util.SortedMap</code>.
+ */
+public class BTree {
+
+    private static final int DEFAULT_MIN_SIZE = 2;
+
+    private Indexer indexer;
+
+    private String name;
+    private boolean unique = true;
+    private int minSize = DEFAULT_MIN_SIZE;
+
+    private UnsupportedOperationException uniqueKeyViolation = new UnsupportedOperationException("Unique key violation");
+
+    public BTree(Indexer indexer, String name, boolean unique) {
+        this.indexer = indexer;
+        this.name = name;
+        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;
+    }
+
+    /**
+     * Find the given key or key/value pair in the page.
+     *
+     * @param key the key (required)
+     * @param value the value (optional)
+     * @param keys the key list
+     * @param values the value list
+     * @return the position
+     */
+    int find(String key, String value, String[] keys, String[] values) {
+        // modified binary search:
+        // return the first elements for non-unique
+        // indexes, if multiple elements were found
+        int min = 0, max = keys.length - 1;
+        while (min <= max) {
+            int test = (min + max) >>> 1;
+            int compare = keys[test].compareTo(key);
+            if (compare == 0) {
+                if (unique) {
+                    return test;
+                }
+                if (value != null) {
+                    compare = values[test].compareTo(value);
+                } else {
+                    // consider equality as bigger, so
+                    // that the first element is found
+                    compare = 1;
+                }
+            }
+            if (compare > 0) {
+                max = test - 1;
+            } else if (compare < 0) {
+                min = test + 1;
+            } else {
+                return test;
+            }
+        }
+        // not found: return negative insertion point
+        return -(min + 1);
+    }
+
+    BTreePage 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 key) {
+        Cursor c = new Cursor();
+        BTreePage node = getPage(null, "");
+        while (true) {
+            int pos = node.find(key, null);
+            if (node instanceof BTreeLeaf) {
+                if (pos < 0) {
+                    pos = -pos - 1;
+                }
+                c.setCurrent((BTreeLeaf) 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(String key, String value) {
+        IndexNode parent = null;
+        int parentPos = 0;
+        BTreePage n = getPage(null, "");
+        while (true) {
+            if (n instanceof IndexNode) {
+                IndexNode page = (IndexNode) n;
+                int pos = page.find(key, value);
+                if (pos < 0) {
+                    pos = -pos - 1;
+                } else {
+                    pos++;
+                }
+                parent = page;
+                parentPos = pos;
+                n = page.getChild(pos);
+            } else {
+                BTreeLeaf page = (BTreeLeaf) n;
+                int pos = page.find(key, value);
+                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(String key, String value) {
+        IndexNode parent = null;
+        int parentPos = 0;
+        BTreePage 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.keys[split] },
+                            new String[] { n.values[split] },
+                            new String[] { "0", "1" });
+                    n.split(root, "0", split, "1");
+                    n = root;
+                } else {
+                    String k = n.keys[split];
+                    String v = n.values[split];
+                    String path = parent.getNextChildPath();
+                    n.split(null, null, split, path);
+                    parent.insert(parentPos, k, v, 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(key, value);
+                if (pos < 0) {
+                    pos = -pos - 1;
+                } else {
+                    pos++;
+                }
+                parent = page;
+                parentPos = pos;
+                n = page.getChild(pos);
+            } else {
+                BTreeLeaf page = (BTreeLeaf) n;
+                int pos = page.find(key, value);
+                if (pos < 0) {
+                    pos = -pos - 1;
+                } else {
+                    if (unique) {
+                        throw uniqueKeyViolation;
+                    }
+                }
+                page.insert(pos, key, value);
+                page.writeData();
+                break;
+            }
+        }
+        commit();
+    }
+
+    void commit() {
+        indexer.commit();
+    }
+
+    String getName() {
+        return name;
+    }
+
+    private int getMinSize() {
+        return minSize;
+    }
+
+    private int getMaxSize() {
+        return minSize + minSize + 1;
+    }
+
+}

Copied: jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/BTreeLeaf.java (from r1162161, 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/BTreeLeaf.java?p2=jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/BTreeLeaf.java&p1=jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/IndexLeaf.java&r1=1162161&r2=1162723&rev=1162723&view=diff
==============================================================================
--- jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/IndexLeaf.java (original)
+++ jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/BTreeLeaf.java Mon Aug 29 10:44:12 2011
@@ -18,72 +18,71 @@ 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 {
+class BTreeLeaf extends BTreePage {
 
-    IndexLeaf(Index index, IndexNode parent, String path, String[] data, String[] paths) {
-        super(index, parent, path, data, paths);
+    BTreeLeaf(BTree tree, IndexNode parent, String path, String[] data, String[] paths) {
+        super(tree, parent, path, data, paths);
     }
 
-    IndexLeaf nextLeaf() {
+    BTreeLeaf nextLeaf() {
         return parent == null ? null : parent.next(this);
     }
 
-    IndexLeaf firstLeaf() {
+    BTreeLeaf 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);
+        String[] k2 = Arrays.copyOfRange(keys, pos, keys.length, String[].class);
+        String[] v2 = Arrays.copyOfRange(values, pos, values.length, String[].class);
+        BTreeLeaf n2 = new BTreeLeaf(tree, parent, siblingName, k2, v2);
+        keys = Arrays.copyOfRange(keys, 0, pos, String[].class);
+        values = Arrays.copyOfRange(values, 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 insert(int pos, String key, String value) {
+        keys = BTree.insert(keys, pos, key);
+        values = BTree.insert(values, pos, value);
     }
 
     void delete(int pos) {
-        data = Index.delete(data, pos);
-        paths = Index.delete(paths, pos);
+        keys = BTree.delete(keys, pos);
+        values = BTree.delete(values, pos);
     }
 
     void writeData() {
-        index.bufferSetArray(getPath(), "data", data);
-        index.bufferSetArray(getPath(), "paths", paths);
+        tree.bufferSetArray(getPath(), "keys", keys);
+        tree.bufferSetArray(getPath(), "values", values);
     }
 
     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.append("+ ").key(PathUtils.concat(tree.getName(), getPath())).object();
+        jsop.key("keys").array();
+        for (String k : keys) {
+            jsop.value(k);
         }
         jsop.endArray();
-        jsop.key("paths").array();
-        for (String d : paths) {
-            jsop.value(d);
+        jsop.key("values").array();
+        for (String v : values) {
+            jsop.value(v);
         }
         jsop.endArray();
         jsop.endObject();
         jsop.appendWhitespace("\n");
-        index.buffer(jsop.toString());
+        tree.buffer(jsop.toString());
     }
 
-    String getPath(int pos) {
-        return paths[pos];
+    String getValue(int pos) {
+        return values[pos];
     }
 
 }
\ No newline at end of file

Copied: jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/BTreePage.java (from r1162161, 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/BTreePage.java?p2=jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/BTreePage.java&p1=jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/IndexPage.java&r1=1162161&r2=1162723&rev=1162723&view=diff
==============================================================================
--- jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/IndexPage.java (original)
+++ jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/BTreePage.java Mon Aug 29 10:44:12 2011
@@ -16,46 +16,45 @@
  */
 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 {
+abstract class BTreePage {
 
-    protected final Index index;
+    protected final BTree tree;
     protected IndexNode parent;
     protected String name;
-    protected String[] data;
-    protected String[] paths;
+    protected String[] keys;
+    protected String[] values;
 
-    IndexPage(Index index, IndexNode parent, String name, String[] data, String[] paths) {
-        this.index = index;
+    BTreePage(BTree tree, IndexNode parent, String name, String[] keys, String[] values) {
+        this.tree = tree;
         this.parent = parent;
         this.name = name;
-        this.data = data;
-        this.paths = paths;
+        this.keys = keys;
+        this.values = values;
     }
 
     abstract void writeCreate();
     abstract void split(IndexNode newParent, String newPath, int pos, String siblingPath);
-    abstract IndexLeaf firstLeaf();
+    abstract BTreeLeaf firstLeaf();
 
     void setParent(IndexNode newParent, String newName) {
         if (newParent != null) {
-            index.bufferMove(
-                    PathUtils.concat(index.getName(), getPath()),
+            tree.bufferMove(
+                    PathUtils.concat(tree.getName(), getPath()),
                     "temp");
             newParent.writeCreate();
-            index.bufferMove(
+            tree.bufferMove(
                     "temp",
-                    PathUtils.concat(index.getName(), getParentPath(), newName));
+                    PathUtils.concat(tree.getName(), getParentPath(), newName));
             parent = newParent;
             name = newName;
 
             int todoRequiredForMicroKernelImpl;
-            index.commit();
+            tree.commit();
         }
     }
 
@@ -68,11 +67,11 @@ abstract class IndexPage {
     }
 
     int size() {
-        return data.length;
+        return keys.length;
     }
 
-    int find(NodeImpl n) {
-        return index.find(n, data, paths);
+    int find(String key, String value) {
+        return tree.find(key, value, keys, values);
     }
 
 }

Modified: 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=1162723&r1=1162722&r2=1162723&view=diff
==============================================================================
--- jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/Cursor.java (original)
+++ jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/Cursor.java Mon Aug 29 10:44:12 2011
@@ -24,9 +24,9 @@ import java.util.Iterator;
 public class Cursor implements Iterator<String> {
 
     // TODO a cursor should be based on a specific revision
-    private IndexLeaf current;
+    private BTreeLeaf current;
     private int pos;
-    private String currentPath;
+    private String currentValue;
 
     public boolean hasNext() {
         return current != null;
@@ -34,17 +34,17 @@ public class Cursor implements Iterator<
 
     public String next() {
         if (current == null) {
-            currentPath = null;
+            currentValue = null;
             return null;
         }
-        String data = current.data[pos];
-        currentPath = current.getPath(pos);
+        String key = current.keys[pos];
+        currentValue = current.values[pos];
         step();
-        return data;
+        return key;
     }
 
-    public String getPath() {
-        return currentPath;
+    public String getValue() {
+        return currentValue;
     }
 
     void step() {
@@ -65,9 +65,40 @@ public class Cursor implements Iterator<
         throw new UnsupportedOperationException();
     }
 
-    void setCurrent(IndexLeaf current, int pos) {
+    void setCurrent(BTreeLeaf current, int pos) {
         this.current = current;
         this.pos = pos;
     }
 
+    public static class RangeIterator implements Iterator<String> {
+        private final Cursor cursor;
+        private final String maxKey;
+        private String value;
+        RangeIterator(Cursor cursor, String maxKey) {
+            this.cursor = cursor;
+            this.maxKey = maxKey;
+            step();
+        }
+        private void step() {
+            value = null;
+            if (cursor.hasNext()) {
+                String k = cursor.next();
+                if (k.compareTo(maxKey) <= 0) {
+                    value = cursor.getValue();
+                }
+            }
+        }
+        public boolean hasNext() {
+            return value != null;
+        }
+        public String next() {
+            String v = value;
+            step();
+            return v;
+        }
+        public void remove() {
+            throw new UnsupportedOperationException();
+        }
+    }
+
 }

Modified: 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=1162723&r1=1162722&r2=1162723&view=diff
==============================================================================
--- jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/Index.java (original)
+++ jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/Index.java Mon Aug 29 10:44:12 2011
@@ -16,327 +16,27 @@
  */
 package org.apache.jackrabbit.mk.index;
 
-import java.util.Iterator;
-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.
+ * An index is a lookup mechanism. It typically uses a tree to store data. It
+ * updates the tree whenever a node was changed. The index is updated
+ * automatically.
  */
-public class Index {
+public interface Index {
 
-    private static final 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 String getPath(String propertyValue, String revision) {
-        indexer.updateUntil(revision);
-        Cursor c = findFirst(propertyValue);
-        if (!c.hasNext()) {
-            return null;
-        }
-        c.next();
-        return c.getPath();
-    }
-
-    public Iterator<String> getPaths(String propertyValue, String revision) {
-        indexer.updateUntil(revision);
-        final Cursor c = findFirst(propertyValue);
-        return new Iterator<String>() {
-            public boolean hasNext() {
-                return c.hasNext();
-            }
-            public String next() {
-                c.next();
-                return c.getPath();
-            }
-            public void remove() {
-                c.remove();
-            }
-        };
-    }
-
-    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[] paths) {
-        String d = n.getProperty(propertyName);
-        String p = n.getPath();
-        // modified binary search:
-        // return the first elements for non-unique
-        // indexes, if multiple elements were found
-        int min = 0, max = data.length - 1;
-        while (min <= max) {
-            int test = (min + max) >>> 1;
-            int compare = data[test].compareTo(d);
-            if (compare == 0) {
-                if (unique) {
-                    return test;
-                }
-                if (p != null) {
-                    compare = paths[test].compareTo(p);
-                } else {
-                    // consider equality as bigger, so
-                    // that the first element is found
-                    compare = 1;
-                }
-            }
-            if (compare > 0) {
-                max = test - 1;
-            } else if (compare < 0) {
-                min = test + 1;
-            } else {
-                return test;
-            }
-        }
-        // not found: return negative insertion point
-        return -(min + 1);
-    }
-
-    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[] { n.paths[split] },
-                            new String[] { "0", "1" });
-                    n.split(root, "0", split, "1");
-                    n = root;
-                } else {
-                    String data = n.data[split];
-                    String p = n.paths[split];
-                    String path = parent.getNextChildPath();
-                    n.split(null, null, split, path);
-                    parent.insert(parentPos, data, p, 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();
-    }
-
-    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;
-    }
+    /**
+     * The given node was added.
+     *
+     * @param add the added node
+     */
+    void add(NodeImpl add);
+
+    /**
+     * The given node was removed.
+     *
+     * @param remove the removed node
+     */
+    void remove(NodeImpl remove);
 
 }

Modified: 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=1162723&r1=1162722&r2=1162723&view=diff
==============================================================================
--- jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/IndexNode.java (original)
+++ jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/IndexNode.java Mon Aug 29 10:44:12 2011
@@ -23,12 +23,12 @@ import org.apache.jackrabbit.mk.util.Pat
 /**
  * An index node page.
  */
-class IndexNode extends IndexPage {
+class IndexNode extends BTreePage {
 
     private String[] children;
 
-    IndexNode(Index index, IndexNode parent, String path, String[] data, String[] paths, String[] children) {
-        super(index, parent, path, data, paths);
+    IndexNode(BTree tree, IndexNode parent, String path, String[] keys, String[] values, String[] children) {
+        super(tree, parent, path, keys, values);
         this.children = children;
     }
 
@@ -43,29 +43,30 @@ class IndexNode extends IndexPage {
         return Integer.toString(max + 1);
     }
 
-    IndexLeaf firstLeaf() {
-        return index.getPage(this, children[0]).firstLeaf();
+    BTreeLeaf firstLeaf() {
+        return tree.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[] p2 = Arrays.copyOfRange(paths, pos + 1, paths.length, String[].class);
+        String[] k2 = Arrays.copyOfRange(keys, pos + 1, keys.length, String[].class);
+        String[] v2 = Arrays.copyOfRange(values, pos + 1, values.length, String[].class);
         String[] c2 = Arrays.copyOfRange(children, pos + 1, children.length, String[].class);
-        IndexNode n2 = new IndexNode(index, parent, siblingName, d2, p2, c2);
-        data = Arrays.copyOfRange(data, 0, pos, String[].class);
+        IndexNode n2 = new IndexNode(tree, parent, siblingName, k2, v2, c2);
+        keys = Arrays.copyOfRange(keys, 0, pos, String[].class);
+        values = Arrays.copyOfRange(values, 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)
+            tree.bufferMove(
+                    PathUtils.concat(tree.getName(), getPath(), c),
+                    PathUtils.concat(tree.getName(), getParentPath(), siblingName, c)
             );
         }
         writeData();
     }
 
-    IndexLeaf next(IndexPage child) {
+    BTreeLeaf next(BTreePage child) {
         int i = 0;
         String childName = child.name;
         for (; i < children.length; i++) {
@@ -76,30 +77,30 @@ class IndexNode extends IndexPage {
         if (i == children.length - 1) {
             return parent == null ? null : parent.next(this);
         }
-        return index.getPage(this, children[i + 1]).firstLeaf();
+        return tree.getPage(this, children[i + 1]).firstLeaf();
     }
 
-    IndexPage getChild(int pos) {
-        return index.getPage(this, children[pos]);
+    BTreePage getChild(int pos) {
+        return tree.getPage(this, children[pos]);
     }
 
     void writeData() {
-        index.bufferSetArray(getPath(), "data", data);
-        index.bufferSetArray(getPath(), "paths", paths);
-        index.bufferSetArray(getPath(), "children", children);
+        tree.bufferSetArray(getPath(), "keys", keys);
+        tree.bufferSetArray(getPath(), "values", values);
+        tree.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.append("+ ").key(PathUtils.concat(tree.getName(), getPath())).object();
+        jsop.key("keys").array();
+        for (String k : keys) {
+            jsop.value(k);
         }
         jsop.endArray();
-        jsop.key("paths").array();
-        for (String p : paths) {
-            jsop.value(p);
+        jsop.key("values").array();
+        for (String v : values) {
+            jsop.value(v);
         }
         jsop.endArray();
         // could just use child node list, but then
@@ -113,22 +114,22 @@ class IndexNode extends IndexPage {
         jsop.endArray();
         jsop.endObject();
         jsop.appendWhitespace("\n");
-        index.buffer(jsop.toString());
+        tree.buffer(jsop.toString());
     }
 
     void delete(int pos) {
         if (size() > 0) {
             // empty parent
-            data = Index.delete(data, Math.max(0, pos - 1));
-            paths = Index.delete(paths, Math.max(0, pos - 1));
+            keys = BTree.delete(keys, Math.max(0, pos - 1));
+            values = BTree.delete(values, Math.max(0, pos - 1));
         }
-        children = Index.delete(children, pos);
+        children = BTree.delete(children, pos);
     }
 
-    void insert(int pos, String d, String p, String c) {
-        data = Index.insert(data, pos, d);
-        paths = Index.insert(paths, pos, p);
-        children = Index.insert(children, pos + 1, c);
+    void insert(int pos, String key, String value, String child) {
+        keys = BTree.insert(keys, pos, key);
+        values = BTree.insert(values, pos, value);
+        children = BTree.insert(children, pos + 1, child);
     }
 
 }
\ No newline at end of file

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=1162723&r1=1162722&r2=1162723&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 Mon Aug 29 10:44:12 2011
@@ -59,16 +59,14 @@ public class Indexer {
         this(mk, "/index");
     }
 
-    public Index createUniqueIndex(String property) {
-        Index index = new Index(this, property, property, true);
-        index.setMinSize(10);
+    public PropertyIndex createPropertyIndex(String property, boolean unique) {
+        PropertyIndex index = new PropertyIndex(this, property, unique);
         indexes.add(index);
         return index;
     }
 
-    public Index createNonUniqueIndex(String property) {
-        Index index = new Index(this, property, property, false);
-        index.setMinSize(10);
+    public PrefixIndex createPrefixIndex(String prefix) {
+        PrefixIndex index = new PrefixIndex(this, prefix);
         indexes.add(index);
         return index;
     }
@@ -82,28 +80,28 @@ public class Indexer {
         revision = mk.commit(indexRootNode, jsop, revision, null);
     }
 
-    IndexPage getPage(Index index, IndexNode parent, String name) {
+    BTreePage getPage(BTree tree, 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;
+        String indexRoot = PathUtils.concat(indexRootNode, tree.getName());
+        String json = mk.getNodes(PathUtils.concat(indexRoot, p), revision, 0, 0, 0);
+        BTreePage page;
         if (json == null) {
-            page = new IndexLeaf(index, parent, name,
+            page = new BTreeLeaf(tree, 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 keys = n.getProperty("keys");
+            String values = n.getProperty("values");
             String children = n.getProperty("children");
             if (children != null) {
-                IndexNode node = new IndexNode(index, parent, name,
-                        readArray(data), readArray(paths), readArray(children));
+                IndexNode node = new IndexNode(tree, parent, name,
+                        readArray(keys), readArray(values), readArray(children));
                 page = node;
             } else {
-                IndexLeaf leaf = new IndexLeaf(index, parent, name,
-                        readArray(data), readArray(paths));
+                BTreeLeaf leaf = new BTreeLeaf(tree, parent, name,
+                        readArray(keys), readArray(values));
                 page = leaf;
             }
         }

Added: jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/PrefixIndex.java
URL: http://svn.apache.org/viewvc/jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/PrefixIndex.java?rev=1162723&view=auto
==============================================================================
--- jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/PrefixIndex.java (added)
+++ jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/PrefixIndex.java Mon Aug 29 10:44:12 2011
@@ -0,0 +1,88 @@
+/*
+ * 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;
+import java.util.Map.Entry;
+import org.apache.jackrabbit.mk.mem.NodeImpl;
+
+/**
+ * An index for all values with a given prefix.
+ */
+public class PrefixIndex implements Index {
+
+    private final Indexer indexer;
+    private final BTree tree;
+    private final String prefix;
+
+    public PrefixIndex(Indexer indexer, String prefix) {
+        int supportMultiValueProperties;
+
+        this.indexer = indexer;
+        this.prefix = prefix;
+        this.tree = new BTree(indexer, "prefix:" + prefix, false);
+        tree.setMinSize(10);
+    }
+
+    public void add(NodeImpl node) {
+        String path = null;
+        for (Entry<String, String> e : node.getProperties()) {
+            String value = e.getValue();
+            if (value.startsWith(prefix)) {
+                String v = value.substring(prefix.length());
+                if (path == null) {
+                    path = node.getPath();
+                }
+                tree.add(v, path);
+            }
+        }
+    }
+
+    public void remove(NodeImpl node) {
+        String path = null;
+        for (Entry<String, String> e : node.getProperties()) {
+            String value = e.getValue();
+            if (value.startsWith(prefix)) {
+                String v = value.substring(prefix.length());
+                if (path == null) {
+                    path = node.getPath();
+                }
+                tree.remove(v, path);
+            }
+        }
+    }
+
+    /**
+     * Get an iterator over the paths for the given property value.
+     *
+     * @param value the value (including the prefix)
+     * @param revision the revision
+     * @return an iterator of the paths (an empty iterator if not found)
+     * @throws IllegalArgumentException if the value doesn't start with the prefix
+     */
+    public Iterator<String> getPaths(String value, String revision) {
+        if (!value.startsWith(prefix)) {
+            throw new IllegalArgumentException(
+                    "The value doesn't start with \"" + prefix + "\": " + value);
+        }
+        String v = value.substring(prefix.length());
+        indexer.updateUntil(revision);
+        Cursor c = tree.findFirst(v);
+        return new Cursor.RangeIterator(c, v);
+    }
+
+}

Added: jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/PropertyIndex.java
URL: http://svn.apache.org/viewvc/jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/PropertyIndex.java?rev=1162723&view=auto
==============================================================================
--- jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/PropertyIndex.java (added)
+++ jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/index/PropertyIndex.java Mon Aug 29 10:44:12 2011
@@ -0,0 +1,86 @@
+/*
+ * 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;
+import org.apache.jackrabbit.mk.mem.NodeImpl;
+
+/**
+ * A node handler that maps the property value to the key, and the path of the
+ * node to the value.
+ */
+public class PropertyIndex implements Index {
+
+    private final Indexer indexer;
+    private final BTree tree;
+    private final String propertyName;
+
+    public PropertyIndex(Indexer indexer, String propertyName, boolean unique) {
+        this.indexer = indexer;
+        this.propertyName = propertyName;
+        this.tree = new BTree(indexer, "property:" + propertyName, unique);
+        tree.setMinSize(10);
+    }
+
+    public void add(NodeImpl node) {
+        String value = node.getProperty(propertyName);
+        if (value != null) {
+            tree.add(value, node.getPath());
+        }
+    }
+
+    public void remove(NodeImpl node) {
+        String value = node.getProperty(propertyName);
+        if (value != null) {
+            tree.remove(value, node.getPath());
+        }
+    }
+
+    /**
+     * Get the path for the given property value. For unique indexes, this will
+     * return the only path (if found). For non-unique indexes, this will return
+     * only one path.
+     *
+     * @param propertyValue the value
+     * @param revision the revision
+     * @return the path, or null if not found
+     */
+    public String getPath(String propertyValue, String revision) {
+        indexer.updateUntil(revision);
+        Cursor c = tree.findFirst(propertyValue);
+        if (!c.hasNext()) {
+            return null;
+        }
+        c.next();
+        return c.getValue();
+    }
+
+    /**
+     * Get an iterator over the paths for the given property value. For unique
+     * indexes, the iterator will contain at most one element.
+     *
+     * @param propertyValue the value
+     * @param revision the revision
+     * @return an iterator of the paths (an empty iterator if not found)
+     */
+    public Iterator<String> getPaths(String propertyValue, String revision) {
+        indexer.updateUntil(revision);
+        Cursor c = tree.findFirst(propertyValue);
+        return new Cursor.RangeIterator(c, propertyValue);
+    }
+
+}

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=1162723&r1=1162722&r2=1162723&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 Mon Aug 29 10:44:12 2011
@@ -127,11 +127,12 @@ public class MemoryKernelImpl implements
                 t.read('{');
                 NodeImpl n = NodeImpl.parse(t, headRevId);
                 headRoot = headRoot.cloneAndAddChildNode(PathUtils.concat(fromRoot, path), false, null, n, headRevId);
-                w.append(n.toString()).appendWhitespace("\n");
+                n.append(w, -1, 0, -1, false);
+                w.appendWhitespace("\n");
                 break;
             case '-':
                 path = t.readString();
-                w.append("- ").key(PathUtils.concat(rootPath, path));
+                w.append("- ").value(PathUtils.concat(rootPath, path));
                 headRoot = headRoot.cloneAndRemoveChildNode(PathUtils.concat(fromRoot, path), headRevId);
                 w.appendWhitespace("\n");
                 break;
@@ -302,7 +303,7 @@ public class MemoryKernelImpl implements
             throw new RuntimeException("path not found: " + path);
         }
         JsopBuilder json = new JsopBuilder();
-        n.append(json, depth, offset, count);
+        n.append(json, depth, offset, count, true);
         return json.toString();
     }
 

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=1162723&r1=1162722&r2=1162723&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 Mon Aug 29 10:44:12 2011
@@ -22,8 +22,10 @@ import org.apache.jackrabbit.mk.json.Jso
 import org.apache.jackrabbit.mk.util.PathUtils;
 
 import java.util.ArrayList;
+import java.util.Collections;
 import java.util.HashMap;
 import java.util.LinkedHashMap;
+import java.util.Map;
 import java.util.Map.Entry;
 
 /**
@@ -157,7 +159,7 @@ public class NodeImpl {
 
     public String toString() {
         JsopBuilder json = new JsopBuilder();
-        append(json, 0, 0, -1);
+        append(json, 0, 0, -1, false);
         if (path != null) {
             json.appendWhitespace("/* ").append(path).append(" */");
         }
@@ -172,7 +174,7 @@ public class NodeImpl {
         }
     }
 
-    public void append(JsopBuilder json, int depth, long offset, int count) {
+    public void append(JsopBuilder json, int depth, long offset, int count, boolean childNodeCount) {
         json.object();
         if (properties != null) {
             for (Entry<String, String> e : properties.entrySet()) {
@@ -180,9 +182,13 @@ public class NodeImpl {
             }
         }
         if (childNodes == null) {
-            json.key(":childNodeCount").value(0);
+            if (childNodeCount) {
+                json.key(":childNodeCount").value(0);
+            }
         } else {
-            json.key(":childNodeCount").value(childNodes.size());
+            if (childNodeCount) {
+                json.key(":childNodeCount").value(childNodes.size());
+            }
             if (count != 0) {
                 for (Entry<String, NodeImpl> e : childNodes.entrySet()) {
                     if (offset > 0) {
@@ -194,7 +200,7 @@ public class NodeImpl {
                         if (depth == 0) {
                             json.object().endObject();
                         } else {
-                            e.getValue().append(json, depth - 1, 0, -1);
+                            e.getValue().append(json, depth - 1, 0, -1, childNodeCount);
                         }
                     }
                 }
@@ -311,4 +317,12 @@ public class NodeImpl {
         return names;
     }
 
+    public Iterable<Entry<String, String>> getProperties() {
+        if (properties == null) {
+            Map<String, String> e = Collections.emptyMap();
+            return e.entrySet();
+        }
+        return properties.entrySet();
+    }
+
 }

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=1162723&r1=1162722&r2=1162723&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 29 10:44:12 2011
@@ -47,8 +47,9 @@ public class IndexTest extends TestCase 
     private void testNonUnique(String url) {
         MicroKernel mk = MicroKernelFactory.getInstance(url);
         Indexer indexer = new Indexer(mk);
-        Index index = indexer.createNonUniqueIndex("id");
+        PropertyIndex index = indexer.createPropertyIndex("id", false);
         mk.commit("/", "+ \"test\": { \"test2\": { \"id\": 1 }, \"id\": 1 }", mk.getHeadRevision(), "");
+        mk.commit("/", "+ \"test3\": { \"test2\": { \"id\": 2 }, \"id\": 2 }", mk.getHeadRevision(), "");
         Iterator<String> it = index.getPaths("1", mk.getHeadRevision());
         assertTrue(it.hasNext());
         assertEquals("/test", it.next());
@@ -61,7 +62,7 @@ public class IndexTest extends TestCase 
     private void testNestedAddNode(String url) {
         MicroKernel mk = MicroKernelFactory.getInstance(url);
         Indexer indexer = new Indexer(mk);
-        Index index = indexer.createUniqueIndex("id");
+        PropertyIndex index = indexer.createPropertyIndex("id", true);
         mk.commit("/", "+ \"test\": { \"test2\": { \"id\": 2 }, \"id\": 1 }", mk.getHeadRevision(), "");
         assertEquals("/test", index.getPath("1", mk.getHeadRevision()));
         assertEquals("/test/test2", index.getPath("2", mk.getHeadRevision()));
@@ -71,9 +72,9 @@ public class IndexTest extends TestCase 
     private void testAscending(String url) {
         MicroKernel mk = MicroKernelFactory.getInstance(url);
         Indexer indexer = new Indexer(mk);
-        Index index = new Index(indexer, "test", "id", true);
-        index.setMinSize(2);
-        print(mk, index);
+        BTree tree = new BTree(indexer, "test", true);
+        tree.setMinSize(2);
+        print(mk, tree);
         int len = 30;
         for (int i = 0; i < len; i++) {
             NodeImpl n;
@@ -81,29 +82,24 @@ public class IndexTest extends TestCase 
             n = n.cloneAndSetProperty("id", "" + i, 0);
             n.setPath("i" + i);
             log("#insert " + i);
-            index.add(n);
-            // print(mk, index);
+            tree.add("" + i, "p" + i);
+            // print(mk, tree);
         }
         for (int i = 0; i < len; i++) {
             // log("#test " + i);
-            Cursor c = index.findFirst("" + i);
+            Cursor c = tree.findFirst("" + i);
             if (c.hasNext()) {
                 assertEquals("" + i, c.next());
             }
         }
-        print(mk, index);
+        print(mk, tree);
         for (int i = 0; i < len; i++) {
-            NodeImpl n;
-            n = new NodeImpl(0);
-            n = n.cloneAndSetProperty("id", "" + i, 0);
-            n.setPath("i" + i);
-            log("#remove " + i);
-            assertTrue("not found when removing " + i, index.remove(n));
+            assertTrue("not found when removing " + i, tree.remove("" + i, null));
             // print(mk, index);
         }
-        print(mk, index);
+        print(mk, tree);
         for (int i = 0; i < len; i++) {
-            Cursor c = index.findFirst("" + i);
+            Cursor c = tree.findFirst("" + i);
             assertFalse(c.hasNext());
         }
         mk.dispose();
@@ -112,38 +108,31 @@ public class IndexTest extends TestCase 
     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);
+        BTree tree = new BTree(indexer, "test", unique);
+        tree.setMinSize(2);
 
         // add
-        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);
+        tree.add("1", "p1");
         if (unique) {
             try {
-                index.add(n);
+                tree.add("1", "p2");
                 fail();
             } catch (UnsupportedOperationException e) {
                 // expected
             }
         } else {
-            index.add(n);
+            tree.add("1", "p2");
         }
 
         // search
-        Cursor c = index.findFirst("1");
+        Cursor c = tree.findFirst("1");
         assertEquals("1", c.next());
-        assertEquals("p1", c.getPath());
+        assertEquals("p1", c.getValue());
         if (unique) {
             assertFalse(c.hasNext());
         } else {
             assertEquals("1", c.next());
-            assertEquals("p1b", c.getPath());
+            assertEquals("p2", c.getValue());
         }
         try {
             c.remove();
@@ -155,10 +144,7 @@ public class IndexTest extends TestCase 
         assertEquals(null, c.next());
 
         // remove
-        n = new NodeImpl(0);
-        n.setPath("p1");
-        n.cloneAndSetProperty("id", "1", 0);
-        index.remove(n);
+        tree.remove("1", "p1");
 
         mk.dispose();
     }
@@ -166,16 +152,16 @@ public class IndexTest extends TestCase 
     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);
+        BTree tree = new BTree(indexer, "test", true);
+        tree.setMinSize(2);
         Random r = new Random(1);
-        TreeMap<Integer, String> tree = new TreeMap<Integer, String>();
+        TreeMap<Integer, String> treeMap = new TreeMap<Integer, String>();
         for (int i = 0; i < 100; i++) {
             log("op #" + i);
-            print(mk, index);
+            // print(mk, tree);
             int x = r.nextInt(10);
-            boolean exists = tree.containsKey(x);
-            Cursor c = index.findFirst("" + x);
+            boolean exists = treeMap.containsKey(x);
+            Cursor c = tree.findFirst("" + x);
             boolean gotExists = c.hasNext();
             String x2 = null;
             if (gotExists) {
@@ -184,28 +170,23 @@ public class IndexTest extends TestCase 
                     gotExists = false;
                 }
             }
-            assertEquals(exists, gotExists);
+            assertEquals("find " + x, exists, gotExists);
             if (exists) {
                 assertEquals("" + x, x2);
-                assertEquals(tree.get(x), c.getPath());
+                assertEquals(treeMap.get(x), c.getValue());
             }
             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);
+                    treeMap.put(x, "p" + i);
+                    tree.add("" + x, "p" + i);
                 }
             } else {
                 if (exists) {
                     log("#remove " + x);
-                    tree.remove(x);
-                    NodeImpl n = new NodeImpl(0);
-                    n.cloneAndSetProperty("id", "" + x, 0);
-                    index.remove(n);
+                    treeMap.remove(x);
+                    tree.remove("" + x, null);
                 }
             }
         }
@@ -216,11 +197,11 @@ public class IndexTest extends TestCase 
         // System.out.println(s);
     }
 
-    static void print(MicroKernel mk, Index index) {
+    static void print(MicroKernel mk, BTree tree) {
         String head = mk.getHeadRevision();
-        String tree = mk.getNodes("/index", head, 100, 0, -1);
-        log(JsopTest.format(tree));
-        Cursor c = index.findFirst("0");
+        String t = mk.getNodes("/index", head, 100, 0, -1);
+        log(JsopTest.format(t));
+        Cursor c = tree.findFirst("0");
         StringBuilder buff = new StringBuilder();
         while (c.hasNext()) {
             buff.append(c.next()).append(' ');

Added: jackrabbit/sandbox/microkernel/src/test/java/org/apache/jackrabbit/mk/index/PrefixIndexTest.java
URL: http://svn.apache.org/viewvc/jackrabbit/sandbox/microkernel/src/test/java/org/apache/jackrabbit/mk/index/PrefixIndexTest.java?rev=1162723&view=auto
==============================================================================
--- jackrabbit/sandbox/microkernel/src/test/java/org/apache/jackrabbit/mk/index/PrefixIndexTest.java (added)
+++ jackrabbit/sandbox/microkernel/src/test/java/org/apache/jackrabbit/mk/index/PrefixIndexTest.java Mon Aug 29 10:44:12 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 java.util.Iterator;
+import junit.framework.TestCase;
+import org.apache.jackrabbit.mk.MicroKernelFactory;
+import org.apache.jackrabbit.mk.api.MicroKernel;
+
+/**
+ * Test the prefix index.
+ */
+public class PrefixIndexTest extends TestCase {
+
+    private static final String URL = "fs:{homeDir}/target";
+    // private static final String URL = "mem:fs:target/temp";
+    // private static final String URL = "mem:";
+
+    public void test() {
+        test(URL);
+    }
+
+    private void test(String url) {
+        MicroKernel mk = MicroKernelFactory.getInstance(url + ";clean");
+        Indexer indexer = new Indexer(mk);
+        PrefixIndex index = indexer.createPrefixIndex("\"d:");
+
+        String head = mk.getHeadRevision();
+
+        assertEquals("", getPathList(index, "\"d:1", head));
+
+        head = mk.commit("/", "+\"test\" : {\"blob\":\"d:1\"}", head, null);
+        head = mk.commit("/", "+\"test2\" : {\"blob\":\"d:2\"}", head, null);
+
+        assertEquals("/test", getPathList(index, "\"d:1\"", head));
+        assertEquals("/test2", getPathList(index, "\"d:2\"", head));
+
+        head = mk.commit("/", "+\"test3\" : {\"blob\":\"d:1\"}", head, null);
+        head = mk.commit("/", "+\"test4\" : {\"blob\":\"d:2\"}", head, null);
+
+        assertEquals("/test, /test3", getPathList(index, "\"d:1\"", head));
+        assertEquals("/test2, /test4", getPathList(index, "\"d:2\"", head));
+
+        mk.dispose();
+    }
+
+    private String getPathList(PrefixIndex index, String value, String revision) {
+        StringBuilder buff = new StringBuilder();
+        int i = 0;
+        for (Iterator<String> it = index.getPaths(value, revision); it.hasNext();) {
+            if (i++ > 0) {
+                buff.append(", ");
+            }
+            buff.append(it.next());
+        }
+        return buff.toString();
+    }
+
+}

Copied: jackrabbit/sandbox/microkernel/src/test/java/org/apache/jackrabbit/mk/index/PropertyIndexTest.java (from r1162115, jackrabbit/sandbox/microkernel/src/test/java/org/apache/jackrabbit/mk/index/IdentifierIndexTest.java)
URL: http://svn.apache.org/viewvc/jackrabbit/sandbox/microkernel/src/test/java/org/apache/jackrabbit/mk/index/PropertyIndexTest.java?p2=jackrabbit/sandbox/microkernel/src/test/java/org/apache/jackrabbit/mk/index/PropertyIndexTest.java&p1=jackrabbit/sandbox/microkernel/src/test/java/org/apache/jackrabbit/mk/index/IdentifierIndexTest.java&r1=1162115&r2=1162723&rev=1162723&view=diff
==============================================================================
--- jackrabbit/sandbox/microkernel/src/test/java/org/apache/jackrabbit/mk/index/IdentifierIndexTest.java (original)
+++ jackrabbit/sandbox/microkernel/src/test/java/org/apache/jackrabbit/mk/index/PropertyIndexTest.java Mon Aug 29 10:44:12 2011
@@ -21,9 +21,9 @@ import org.apache.jackrabbit.mk.MicroKer
 import org.apache.jackrabbit.mk.api.MicroKernel;
 
 /**
- * Test the indexer mechanism.
+ * Test the property index.
  */
-public class IdentifierIndexTest extends TestCase {
+public class PropertyIndexTest extends TestCase {
 
     private static final String URL = "fs:{homeDir}/target";
     // private static final String URL = "mem:fs:target/temp";
@@ -36,7 +36,7 @@ public class IdentifierIndexTest extends
     private void test(String url) {
         MicroKernel mk = MicroKernelFactory.getInstance(url + ";clean");
         Indexer indexer = new Indexer(mk);
-        Index index = indexer.createUniqueIndex("id");
+        PropertyIndex index = indexer.createPropertyIndex("id", true);
 
         String head = mk.getHeadRevision();
 
@@ -57,7 +57,7 @@ public class IdentifierIndexTest extends
 
         mk = MicroKernelFactory.getInstance(url);
         indexer = new Indexer(mk);
-        index = indexer.createUniqueIndex("id");
+        index = indexer.createPropertyIndex("id", true);
         head = mk.getHeadRevision();
         assertEquals("/test/test", index.getPath("\"3\"", head));
         mk.dispose();



Mime
View raw message