jackrabbit-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From thom...@apache.org
Subject svn commit: r1162161 - in /jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk: index/Cursor.java index/Index.java index/IndexLeaf.java index/IndexNode.java index/IndexPage.java index/Indexer.java mem/NodeImpl.java
Date Fri, 26 Aug 2011 16:43:18 GMT
Author: thomasm
Date: Fri Aug 26 16:43:18 2011
New Revision: 1162161

URL: http://svn.apache.org/viewvc?rev=1162161&view=rev
Log:
Non-unique indexes (WIP)

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/NodeImpl.java

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=1162161&r1=1162160&r2=1162161&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
Fri Aug 26 16:43:18 2011
@@ -23,6 +23,7 @@ import java.util.Iterator;
  */
 public class Cursor implements Iterator<String> {
 
+    // TODO a cursor should be based on a specific revision
     private IndexLeaf current;
     private int pos;
     private String currentPath;

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=1162161&r1=1162160&r2=1162161&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
Fri Aug 26 16:43:18 2011
@@ -16,7 +16,7 @@
  */
 package org.apache.jackrabbit.mk.index;
 
-import java.util.Arrays;
+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;
@@ -61,6 +61,23 @@ public class Index {
         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);
@@ -72,23 +89,38 @@ public class Index {
         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;
+    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;
+            }
         }
-        return pa.compareTo(pb);
+        // not found: return negative insertion point
+        return -(min + 1);
     }
 
     String data(NodeImpl n) {
@@ -240,14 +272,16 @@ public class Index {
                     // 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, PathUtils.getName(path));
+                    parent.insert(parentPos, data, p, PathUtils.getName(path));
                     parent.writeData();
                     // go back one step (the entry might be in the
                     // other node now)

Modified: 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=1162161&r1=1162160&r2=1162161&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/IndexLeaf.java
Fri Aug 26 16:43:18 2011
@@ -26,11 +26,8 @@ import org.apache.jackrabbit.mk.util.Pat
  */
 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;
+        super(index, parent, path, data, paths);
     }
 
     IndexLeaf nextLeaf() {

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=1162161&r1=1162160&r2=1162161&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
Fri Aug 26 16:43:18 2011
@@ -27,8 +27,8 @@ class IndexNode extends IndexPage {
 
     private String[] children;
 
-    IndexNode(Index index, IndexNode parent, String path, String[] data, String[] children)
{
-        super(index, parent, path, data);
+    IndexNode(Index index, IndexNode parent, String path, String[] data, String[] paths,
String[] children) {
+        super(index, parent, path, data, paths);
         this.children = children;
     }
 
@@ -50,8 +50,9 @@ class IndexNode extends IndexPage {
     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[] c2 = Arrays.copyOfRange(children, pos + 1, children.length, String[].class);
-        IndexNode n2 = new IndexNode(index, parent, siblingName, d2, c2);
+        IndexNode n2 = new IndexNode(index, parent, siblingName, d2, p2, c2);
         data = Arrays.copyOfRange(data, 0, pos, String[].class);
         children = Arrays.copyOfRange(children, 0, pos + 1, String[].class);
         n2.writeCreate();
@@ -84,6 +85,7 @@ class IndexNode extends IndexPage {
 
     void writeData() {
         index.bufferSetArray(getPath(), "data", data);
+        index.bufferSetArray(getPath(), "paths", paths);
         index.bufferSetArray(getPath(), "children", children);
     }
 
@@ -95,6 +97,11 @@ class IndexNode extends IndexPage {
             jsop.value(d);
         }
         jsop.endArray();
+        jsop.key("paths").array();
+        for (String p : paths) {
+            jsop.value(p);
+        }
+        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
@@ -113,12 +120,14 @@ class IndexNode extends IndexPage {
         if (size() > 0) {
             // empty parent
             data = Index.delete(data, Math.max(0, pos - 1));
+            paths = Index.delete(paths, Math.max(0, pos - 1));
         }
         children = Index.delete(children, pos);
     }
 
-    void insert(int pos, String d, String c) {
+    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);
     }
 

Modified: 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=1162161&r1=1162160&r2=1162161&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/IndexPage.java
Fri Aug 26 16:43:18 2011
@@ -28,12 +28,14 @@ abstract class IndexPage {
     protected IndexNode parent;
     protected String name;
     protected String[] data;
+    protected String[] paths;
 
-    IndexPage(Index index, IndexNode parent, String name, String[] data) {
+    IndexPage(Index index, IndexNode parent, String name, String[] data, String[] paths)
{
         this.index = index;
         this.parent = parent;
         this.name = name;
         this.data = data;
+        this.paths = paths;
     }
 
     abstract void writeCreate();
@@ -70,7 +72,7 @@ abstract class IndexPage {
     }
 
     int find(NodeImpl n) {
-        return index.find(n, data);
+        return index.find(n, data, paths);
     }
 
 }

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=1162161&r1=1162160&r2=1162161&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
Fri Aug 26 16:43:18 2011
@@ -40,12 +40,15 @@ public class Indexer {
 
     public Indexer(MicroKernel mk, String indexRootNode) {
         this.mk = mk;
+        if (!PathUtils.isAbsolute(indexRootNode)) {
+            indexRootNode = "/" + indexRootNode;
+        }
         this.indexRootNode = indexRootNode;
-        
+
         revision = mk.getHeadRevision();
-        if (!mk.nodeExists("/" + indexRootNode, revision)) {
+        if (!mk.nodeExists(indexRootNode, revision)) {
             JsopBuilder jsop = new JsopBuilder();
-            jsop.append("+ ").key(indexRootNode).append("{}");
+            jsop.append("+ ").key(PathUtils.relativize("/", indexRootNode)).append("{}");
             revision = mk.commit("/", jsop.toString(), revision, null);
         }
         int todoReadIfAlreadyExists;
@@ -53,7 +56,7 @@ public class Indexer {
     }
 
     public Indexer(MicroKernel mk) {
-        this(mk, "index");
+        this(mk, "/index");
     }
 
     public Index createUniqueIndex(String property) {
@@ -63,19 +66,26 @@ public class Indexer {
         return index;
     }
 
+    public Index createNonUniqueIndex(String property) {
+        Index index = new Index(this, property, property, false);
+        index.setMinSize(10);
+        indexes.add(index);
+        return index;
+    }
+
     boolean nodeExists(String name) {
         revision = mk.getHeadRevision();
-        return mk.nodeExists(PathUtils.concat("/" + indexRootNode, name), revision);
+        return mk.nodeExists(PathUtils.concat(indexRootNode, name), revision);
     }
 
     void commit(String jsop) {
-        revision = mk.commit("/" + indexRootNode, jsop, revision, null);
+        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);
+        String json = mk.getNodes(PathUtils.concat(indexRoot, p), revision);
         IndexPage page;
         if (json == null) {
             page = new IndexLeaf(index, parent, name,
@@ -89,7 +99,7 @@ public class Indexer {
             String children = n.getProperty("children");
             if (children != null) {
                 IndexNode node = new IndexNode(index, parent, name,
-                        readArray(data), readArray(children));
+                        readArray(data), readArray(paths), readArray(children));
                 page = node;
             } else {
                 IndexLeaf leaf = new IndexLeaf(index, parent, name,
@@ -129,7 +139,7 @@ public class Indexer {
         if (buffer != null) {
             String jsop = buffer.toString();
             // System.out.println(jsop);
-            revision = mk.commit("/" + indexRootNode, jsop, revision, null);
+            revision = mk.commit(indexRootNode, jsop, revision, null);
             buffer = null;
         }
     }
@@ -269,6 +279,10 @@ public class Indexer {
     }
 
     private void addNodeRecursive(NodeImpl n) {
+        if (isInIndex(n.getPath())) {
+            // don't index the index
+            return;
+        }
         for (Index index : indexes) {
             index.remove(n);
             index.add(n);
@@ -278,7 +292,15 @@ public class Indexer {
         }
     }
 
+    private boolean isInIndex(String path) {
+        return path.startsWith(indexRootNode);
+    }
+
     private void removeNode(String path) {
+        if (isInIndex(path)) {
+            // don't index the index
+            return;
+        }
         int todo;
         // ignore currently, because we don't know the property value
         // (we need to read it separately)

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=1162161&r1=1162160&r2=1162161&view=diff
==============================================================================
--- jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/NodeImpl.java
(original)
+++ jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/NodeImpl.java
Fri Aug 26 16:43:18 2011
@@ -158,6 +158,9 @@ public class NodeImpl {
     public String toString() {
         JsopBuilder json = new JsopBuilder();
         append(json, 0, 0, -1);
+        if (path != null) {
+            json.appendWhitespace("/* ").append(path).append(" */");
+        }
         return json.toString();
     }
 



Mime
View raw message