Return-Path: X-Original-To: apmail-jackrabbit-commits-archive@www.apache.org Delivered-To: apmail-jackrabbit-commits-archive@www.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id BFCC074DF for ; Mon, 29 Aug 2011 10:44:54 +0000 (UTC) Received: (qmail 20204 invoked by uid 500); 29 Aug 2011 10:44:54 -0000 Delivered-To: apmail-jackrabbit-commits-archive@jackrabbit.apache.org Received: (qmail 20080 invoked by uid 500); 29 Aug 2011 10:44:40 -0000 Mailing-List: contact commits-help@jackrabbit.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@jackrabbit.apache.org Delivered-To: mailing list commits@jackrabbit.apache.org Received: (qmail 20071 invoked by uid 99); 29 Aug 2011 10:44:38 -0000 Received: from athena.apache.org (HELO athena.apache.org) (140.211.11.136) by apache.org (qpsmtpd/0.29) with ESMTP; Mon, 29 Aug 2011 10:44:38 +0000 X-ASF-Spam-Status: No, hits=-2000.0 required=5.0 tests=ALL_TRUSTED X-Spam-Check-By: apache.org Received: from [140.211.11.4] (HELO eris.apache.org) (140.211.11.4) by apache.org (qpsmtpd/0.29) with ESMTP; Mon, 29 Aug 2011 10:44:34 +0000 Received: from eris.apache.org (localhost [127.0.0.1]) by eris.apache.org (Postfix) with ESMTP id DA67223888FD; Mon, 29 Aug 2011 10:44:13 +0000 (UTC) Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit 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 -0000 To: commits@jackrabbit.apache.org From: thomasm@apache.org X-Mailer: svnmailer-1.0.8 Message-Id: <20110829104413.DA67223888FD@eris.apache.org> 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 + * java.util.SortedMap. + */ +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 { // 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 { + 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 - * java.util.SortedMap. 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 getPaths(String propertyValue, String revision) { - indexer.updateUntil(revision); - final Cursor c = findFirst(propertyValue); - return new Iterator() { - 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 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 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 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 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 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 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> getProperties() { + if (properties == null) { + Map 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 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 tree = new TreeMap(); + TreeMap treeMap = new TreeMap(); 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 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();