Author: thomasm
Date: Thu Aug 18 15:30:49 2011
New Revision: 1159280
URL: http://svn.apache.org/viewvc?rev=1159280&view=rev
Log:
A simple indexing mechanism (work in progress).
Modified:
jackrabbit/sandbox/microkernel/src/test/java/org/apache/jackrabbit/mk/index/IndexTest.java
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=1159280&r1=1159279&r2=1159280&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
Thu Aug 18 15:30:49 2011
@@ -46,24 +46,44 @@ public class IndexTest {
private static void test(String url) {
MicroKernel mk = MicroKernelFactory.getInstance(url);
- String head = mk.getHeadRevision();
Index index = new Index(mk, "test", "id");
- for (int i = 0; i < 1000; i++) {
+ print(mk, index);
+ int len = 1000;
+ for (int i = 0; i < len; i++) {
NodeImpl n;
n = new NodeImpl(0);
n = n.cloneAndSetProperty("id", "" + i, 0);
n.setPath("i" + i);
log("#insert " + i);
index.add(n);
+ // print(mk, index);
}
- head = mk.getHeadRevision();
+ print(mk, index);
+ 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);
+ if (!index.remove(n)) {
+ throw new AssertionError("" + i);
+ }
+ print(mk, index);
+ }
+ print(mk, index);
+ mk.dispose();
+ }
+
+ static void print(MicroKernel mk, Index index) {
+ String head = mk.getHeadRevision();
String tree = mk.getNodes("/index", head, 100, 0, -1);
log(JsopTest.format(tree));
- Cursor c = index.findFirst("1");
+ Cursor c = index.findFirst("0");
+ StringBuilder buff = new StringBuilder();
while (c.hasNext()) {
- log(c.next());
+ buff.append(c.next()).append(' ');
}
- mk.dispose();
+ log(buff.toString());
}
static class IndexComparator {
@@ -127,6 +147,17 @@ public class IndexTest {
return data2;
}
+ static String[] delete(String[] data, int pos) {
+ String[] data2 = new String[data.length - 1];
+ if (pos > 0 && data.length > 0) {
+ System.arraycopy(data, 0, data2, 0, pos);
+ }
+ if (pos < data.length) {
+ System.arraycopy(data, pos + 1, data2, pos, data.length - pos - 1);
+ }
+ return data2;
+ }
+
IndexPage getPage(IndexNode parent, String name) {
String p = parent == null ? name : PathUtils.concat(parent.getPath(), name);
String index = PathUtils.concat(indexRootNode, this.name);
@@ -206,6 +237,9 @@ public class IndexTest {
}
if (node instanceof IndexLeaf) {
c.current = (IndexLeaf) node;
+ if (node.size() == 0) {
+ c.step();
+ }
break;
} else {
node = ((IndexNode) node).getChild(pos);
@@ -217,11 +251,16 @@ public class IndexTest {
void bufferSetArray(String path, String propertyName, String[] data) {
JsopBuilder jsop = new JsopBuilder();
path = PathUtils.concat(name, path);
- jsop.append("^ ").key(PathUtils.concat(path, propertyName)).array();
- for (String d : data) {
- jsop.value(d);
+ 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.endArray();
jsop.appendWhitespace("\n");
buffer(jsop.toString());
}
@@ -233,6 +272,13 @@ public class IndexTest {
buffer(jsop.toString());
}
+ public void bufferDelete(String path) {
+ JsopBuilder jsop = new JsopBuilder();
+ jsop.append("- ").value(PathUtils.concat(name, path));
+ jsop.appendWhitespace("\n");
+ buffer(jsop.toString());
+ }
+
void buffer(String diff) {
if (buffer == null) {
buffer = new StringBuilder(diff.length());
@@ -240,6 +286,49 @@ public class IndexTest {
buffer.append(diff);
}
+ boolean remove(NodeImpl remove) {
+ if (!comparator.isIndexed(remove)) {
+ return false;
+ }
+ IndexNode parent = null;
+ int parentPos = 0;
+ IndexPage n = getPage(null, "");
+ while (true) {
+ if (n instanceof IndexNode) {
+ IndexNode page = (IndexNode) n;
+ int pos = page.find(remove);
+ if (pos < 0) {
+ pos = -pos - 1;
+ } else {
+ pos++;
+ }
+ parent = page;
+ parentPos = pos;
+ n = page.getChild(pos);
+ } else {
+ IndexLeaf page = (IndexLeaf) n;
+ int pos = page.find(remove);
+ if (pos < 0) {
+ return false;
+ }
+ page.delete(pos);
+ page.writeData();
+ if (n.size() == 0 && parent != null) {
+ // empty leaf with a parent
+ if (parent.size() > 0) {
+ // empty parent
+ parent.data = Index.delete(parent.data, Math.max(0, parentPos
- 1));
+ }
+ parent.children = Index.delete(parent.children, parentPos);
+ parent.writeData();
+ }
+ break;
+ }
+ }
+ commit();
+ return true;
+ }
+
void add(NodeImpl add) {
if (!comparator.isIndexed(add)) {
return;
@@ -303,18 +392,12 @@ public class IndexTest {
private void commit() {
if (buffer != null) {
String jsop = buffer.toString();
- log(jsop);
+ // log(jsop);
revision = mk.commit("/" + indexRootNode, jsop, revision, null);
buffer = null;
}
}
- void remove(NodeImpl node) {
- if (!comparator.isIndexed(node)) {
- return;
- }
- }
-
public String getName() {
return name;
}
@@ -405,9 +488,18 @@ public class IndexTest {
paths = Index.insert(paths, pos, n.getPath());
}
+ void delete(int pos) {
+ data = Index.delete(data, pos);
+ paths = Index.delete(paths, pos);
+ }
+
void writeData() {
- index.bufferSetArray(getPath(), "data", data);
- index.bufferSetArray(getPath(), "paths", paths);
+ if (data.length == 0) {
+ index.bufferDelete(getPath());
+ } else {
+ index.bufferSetArray(getPath(), "data", data);
+ index.bufferSetArray(getPath(), "paths", paths);
+ }
}
void writeCreate() {
@@ -475,9 +567,9 @@ public class IndexTest {
}
IndexLeaf next(IndexPage child) {
- int i=0;
+ int i = 0;
String childName = child.name;
- for (; i<children.length; i++) {
+ for (; i < children.length; i++) {
if (children[i].equals(childName)) {
break;
}
@@ -539,11 +631,17 @@ public class IndexTest {
return data;
}
- private void step() {
- pos++;
- if (pos == current.size()) {
+ void step() {
+ while (true) {
+ pos++;
+ if (pos < current.size()) {
+ return;
+ }
pos = 0;
current = current.nextLeaf();
+ if (current == null || pos < current.size()) {
+ return;
+ }
}
}
|