You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@jackrabbit.apache.org by th...@apache.org on 2011/08/26 18:43:18 UTC
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
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();
}