diff options
Diffstat (limited to 'ext/http11_java/org')
| -rw-r--r-- | ext/http11_java/org/jruby/mongrel/Http11.java | 2 | ||||
| -rw-r--r-- | ext/http11_java/org/jruby/mongrel/URIClassifier.java | 129 | ||||
| -rw-r--r-- | ext/http11_java/org/jruby/tst/Node.java | 18 | ||||
| -rw-r--r-- | ext/http11_java/org/jruby/tst/NodeLines.java | 16 | ||||
| -rw-r--r-- | ext/http11_java/org/jruby/tst/TernarySearchTree.java | 433 |
5 files changed, 598 insertions, 0 deletions
diff --git a/ext/http11_java/org/jruby/mongrel/Http11.java b/ext/http11_java/org/jruby/mongrel/Http11.java index 4b2fd2e..a73c79b 100644 --- a/ext/http11_java/org/jruby/mongrel/Http11.java +++ b/ext/http11_java/org/jruby/mongrel/Http11.java @@ -83,6 +83,8 @@ public class Http11 extends RubyObject { cHttpParser.defineFastMethod("error?",cf.getFastMethod("has_error")); cHttpParser.defineFastMethod("finished?",cf.getFastMethod("is_finished")); cHttpParser.defineFastMethod("nread",cf.getFastMethod("nread")); + + URIClassifier.createURIClassifier(runtime, mMongrel); } private Ruby runtime; diff --git a/ext/http11_java/org/jruby/mongrel/URIClassifier.java b/ext/http11_java/org/jruby/mongrel/URIClassifier.java new file mode 100644 index 0000000..73ba1ba --- /dev/null +++ b/ext/http11_java/org/jruby/mongrel/URIClassifier.java @@ -0,0 +1,129 @@ +/***** BEGIN LICENSE BLOCK ***** + * Version: CPL 1.0/GPL 2.0/LGPL 2.1 + * + * The contents of this file are subject to the Common Public + * License Version 1.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.eclipse.org/legal/cpl-v10.html + * + * Software distributed under the License is distributed on an "AS + * IS" basis, WITHOUT WARRANTY OF ANY KIND, either express or + * implied. See the License for the specific language governing + * rights and limitations under the License. + * + * Copyright (C) 2007 Ola Bini <ola@ologix.com> + * + * Alternatively, the contents of this file may be used under the terms of + * either of the GNU General Public License Version 2 or later (the "GPL"), + * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"), + * in which case the provisions of the GPL or the LGPL are applicable instead + * of those above. If you wish to allow use of your version of this file only + * under the terms of either the GPL or the LGPL, and not to allow others to + * use your version of this file under the terms of the CPL, indicate your + * decision by deleting the provisions above and replace them with the notice + * and other provisions required by the GPL or the LGPL. If you do not delete + * the provisions above, a recipient may use your version of this file under + * the terms of any one of the CPL, the GPL or the LGPL. + ***** END LICENSE BLOCK *****/ +package org.jruby.mongrel; + +import org.jruby.Ruby; +import org.jruby.RubyArray; +import org.jruby.RubyClass; +import org.jruby.RubyHash; +import org.jruby.RubyModule; +import org.jruby.RubyObject; +import org.jruby.RubyString; + +import org.jruby.runtime.Block; +import org.jruby.runtime.CallbackFactory; +import org.jruby.runtime.ObjectAllocator; +import org.jruby.runtime.builtin.IRubyObject; + +import org.jruby.tst.TernarySearchTree; + +/** + * @author <a href="mailto:ola.bini@ki.se">Ola Bini</a> + */ +public class URIClassifier extends RubyObject { + public final static int TRIE_INCREASE = 30; + + private static ObjectAllocator ALLOCATOR = new ObjectAllocator() { + public IRubyObject allocate(Ruby runtime, RubyClass klass) { + return new URIClassifier(runtime, klass); + } + }; + + public static void createURIClassifier(Ruby runtime, RubyModule mMongrel) { + RubyClass cURIClassifier = mMongrel.defineClassUnder("URIClassifier",runtime.getObject(),ALLOCATOR); + CallbackFactory cf = runtime.callbackFactory(URIClassifier.class); + cURIClassifier.defineFastMethod("initialize",cf.getFastMethod("initialize")); + cURIClassifier.defineFastMethod("register",cf.getFastMethod("register",IRubyObject.class,IRubyObject.class)); + cURIClassifier.defineFastMethod("unregister",cf.getFastMethod("unregister",IRubyObject.class)); + cURIClassifier.defineFastMethod("resolve",cf.getFastMethod("resolve",IRubyObject.class)); + } + + private TernarySearchTree tst; + + public URIClassifier(Ruby runtime, RubyClass clazz) { + super(runtime,clazz); + tst = new TernarySearchTree(TRIE_INCREASE); + } + + public IRubyObject initialize() { + setInstanceVariable("@handler_map",RubyHash.newHash(getRuntime())); + return this; + } + + public IRubyObject register(IRubyObject uri, IRubyObject handler) { + Object[] ptr = new Object[]{null}; + int rc = 0; + rc = tst.insert(uri.toString(),handler,0,ptr); + if(rc == TernarySearchTree.TST_DUPLICATE_KEY) { + throw getRuntime().newStandardError("Handler already registered with that name"); + } else if(rc == TernarySearchTree.TST_ERROR) { + throw getRuntime().newStandardError("Memory error registering handler"); + } else if(rc == TernarySearchTree.TST_NULL_KEY) { + throw getRuntime().newStandardError("URI was empty"); + } + ((RubyHash)getInstanceVariable("@handler_map")).aset(uri,handler); + return getRuntime().getNil(); + } + + public IRubyObject unregister(IRubyObject uri) { + IRubyObject handler = (IRubyObject)tst.delete(uri.toString()); + if(null != handler) { + ((RubyHash)getInstanceVariable("@handler_map")).delete(uri,Block.NULL_BLOCK); + return handler; + } + return getRuntime().getNil(); + } + + public IRubyObject resolve(IRubyObject _ri) { + IRubyObject handler = null; + int[] pref_len = new int[]{0}; + RubyArray result; + String uri_str; + RubyString uri = _ri.convertToString(); + + uri_str = uri.toString(); + handler = (IRubyObject)tst.search(uri_str,pref_len); + + result = getRuntime().newArray(); + + if(handler != null) { + result.append(uri.substr(0, pref_len[0])); + if(pref_len[0] == 1 && uri_str.startsWith("/")) { + result.append(uri); + } else { + result.append(uri.substr(pref_len[0],uri.getByteList().length())); + } + result.append(handler); + } else { + result.append(getRuntime().getNil()); + result.append(getRuntime().getNil()); + result.append(getRuntime().getNil()); + } + return result; + } +}// URIClassifier diff --git a/ext/http11_java/org/jruby/tst/Node.java b/ext/http11_java/org/jruby/tst/Node.java new file mode 100644 index 0000000..334763d --- /dev/null +++ b/ext/http11_java/org/jruby/tst/Node.java @@ -0,0 +1,18 @@ +/* + * See LICENSE file. + */ +/** + * $Id: $ + */ +package org.jruby.tst; + +/** + * @author <a href="mailto:ola.bini@ki.se">Ola Bini</a> + * @version $Revision: $ + */ +public class Node { + public char value; + public Node left; + public Object middle; + public Node right; +}// Node diff --git a/ext/http11_java/org/jruby/tst/NodeLines.java b/ext/http11_java/org/jruby/tst/NodeLines.java new file mode 100644 index 0000000..87b56d7 --- /dev/null +++ b/ext/http11_java/org/jruby/tst/NodeLines.java @@ -0,0 +1,16 @@ +/* + * See LICENSE file. + */ +/** + * $Id: $ + */ +package org.jruby.tst; + +/** + * @author <a href="mailto:ola.bini@ki.se">Ola Bini</a> + * @version $Revision: $ + */ +public class NodeLines { + public Node[] node_line; + public NodeLines next; +}// NodeLines diff --git a/ext/http11_java/org/jruby/tst/TernarySearchTree.java b/ext/http11_java/org/jruby/tst/TernarySearchTree.java new file mode 100644 index 0000000..5637bf1 --- /dev/null +++ b/ext/http11_java/org/jruby/tst/TernarySearchTree.java @@ -0,0 +1,433 @@ +/* + * See LICENSE file. + */ +/** + * $Id: $ + */ +package org.jruby.tst; + +/** + * @author <a href="mailto:ola.bini@ki.se">Ola Bini</a> + * @version $Revision: $ + */ +public class TernarySearchTree { + public final static int TST_OK = 0x1; + public final static int TST_ERROR = 0x2; + public final static int TST_NULL_KEY = 0x4; + public final static int TST_DUPLICATE_KEY = 0x8; + public final static int TST_REPLACE = 0x10; + + public int node_line_width; + public NodeLines node_lines; + public Node free_list; + public Node[] head = new Node[127]; + + public TernarySearchTree(final int width) { + this.node_lines = new NodeLines(); + this.node_line_width = width; + + this.node_lines.next = null; + this.node_lines.node_line = new Node[width]; + for(int i=0;i<width;i++) { + this.node_lines.node_line[i] = new Node(); + } + + Node current_node = this.node_lines.node_line[0]; + this.free_list = current_node; + + for(int i=1; i<width; i++) { + current_node.middle = this.node_lines.node_line[i]; + current_node = (Node)current_node.middle; + } + current_node.middle = null; + } + + public int insert(final String key, final Object data, final int option, final Object[] exist_ptr) { + Node current_node = null; + Node new_node_tree_begin = null; + int key_index = 0; + boolean perform_loop = true; + + if(null == key || key.length() == 0) { + return TST_NULL_KEY; + } + + if(this.head[key.charAt(0)] == null) { + if(this.free_list == null) { + if(!grow_node_free_list()) { + return TST_ERROR; + } + } + this.head[key.charAt(0)] = this.free_list; + this.free_list = (Node)this.free_list.middle; + current_node = this.head[key.charAt(0)]; + + if(key.length() == 1) { + current_node.value = 0; + current_node.middle = data; + return TST_OK; + } else { + current_node.value = key.charAt(1); + perform_loop = false; + } + } + + current_node = this.head[key.charAt(0)]; + key_index = 1; + char curr = 0; + while(perform_loop) { + if(key_index < key.length()) { + curr = key.charAt(key_index); + } else { + curr = 0; + } + + if(curr == current_node.value) { + if(curr == 0) { + if(option == TST_REPLACE) { + if(exist_ptr.length > 0) { + exist_ptr[0] = current_node.middle; + } + current_node.middle = data; + return TST_OK; + } else { + if(exist_ptr.length > 0) { + exist_ptr[0] = current_node.middle; + } + return TST_DUPLICATE_KEY; + } + + } else { + if(current_node.middle == null) { + if(this.free_list == null) { + if(!grow_node_free_list()) { + return TST_ERROR; + } + } + current_node.middle = this.free_list; + this.free_list = (Node)this.free_list.middle; + new_node_tree_begin = current_node; + current_node = (Node)current_node.middle; + current_node.value = curr; + break; + } else { + current_node = (Node)current_node.middle; + key_index++; + continue; + } + } + } + + if((current_node.value == 0 && curr < 64) || + (current_node.value != 0 && curr < current_node.value)) { + if(current_node.left == null) { + if(this.free_list == null) { + if(!grow_node_free_list()) { + return TST_ERROR; + } + } + current_node.left = this.free_list; + this.free_list = (Node)this.free_list.middle; + new_node_tree_begin = current_node; + current_node = current_node.left; + current_node.value = curr; + if(curr == 0) { + current_node.middle = data; + return TST_OK; + } else { + break; + } + } else { + current_node = current_node.left; + continue; + } + } else { + if(current_node.right == null) { + if(this.free_list == null) { + if(!grow_node_free_list()) { + return TST_ERROR; + } + } + current_node.right = this.free_list; + this.free_list = (Node)this.free_list.middle; + new_node_tree_begin = current_node; + current_node = current_node.right; + current_node.value = curr; + break; + } else { + current_node = current_node.right; + continue; + } + } + } + + do { + key_index++; + if(key_index < key.length()) { + curr = key.charAt(key_index); + } else { + curr = 0; + } + + if(this.free_list == null) { + if(!grow_node_free_list()) { + current_node = (Node)new_node_tree_begin.middle; + while(current_node.middle != null) { + current_node = (Node)current_node.middle; + } + current_node.middle = this.free_list; + this.free_list = (Node)new_node_tree_begin.middle; + new_node_tree_begin.middle = null; + return TST_ERROR; + } + } + + if(this.free_list == null) { + if(!grow_node_free_list()) { + return TST_ERROR; + } + } + current_node.middle = this.free_list; + this.free_list = (Node)this.free_list.middle; + current_node = (Node)current_node.middle; + + current_node.value = curr; + } while(curr != 0); + + current_node.middle = data; + return TST_OK; + } + + public Object search(final String key, final int[] prefix_len) { + Node current_node = null; + Object longest_match = null; + int key_index = 0; + + if(key == null) { + throw new IllegalArgumentException("key can't be null"); + } + + if(key.length() == 0 || this.head[key.charAt(0)] == null) { + return null; + } + + if(prefix_len.length > 0) { + prefix_len[0] = 0; + } + + current_node = this.head[key.charAt(0)]; + key_index = 1; + + char curr = 0; + while(null != current_node) { + if(key_index < key.length()) { + curr = key.charAt(key_index); + } else { + curr = 0; + } + + if(curr == current_node.value) { + if(current_node.value == 0) { + if(prefix_len.length>0) { + prefix_len[0] = key_index; + } + return current_node.middle; + } else { + current_node = (Node)current_node.middle; + if(current_node != null && current_node.value == 0) { + if(prefix_len.length>0) { + prefix_len[0] = key_index+1; + } + longest_match = current_node.middle; + } + key_index++; + continue; + } + } else if((current_node.value == 0 && curr < 64) || + (current_node.value != 0 && curr < current_node.value)) { + if(current_node.value == 0) { + if(prefix_len.length>0) { + prefix_len[0] = key_index; + } + longest_match = current_node.middle; + } + current_node = current_node.left; + continue; + } else { + if(current_node.value == 0) { + if(prefix_len.length>0) { + prefix_len[0] = key_index; + } + longest_match = current_node.middle; + } + current_node = current_node.right; + continue; + } + } + + return longest_match; + } + + public Object delete(final String key) { + Node current_node = null; + Node current_node_parent = null; + Node last_branch = null; + Node last_branch_parent = null; + Object next_node = null; + Node last_branch_replacement = null; + Node last_branch_dangling_child = null; + int key_index = 1; + + if(key.length() == 0 || this.head[key.charAt(0)] == null) { + return null; + } + + current_node = this.head[key.charAt(0)]; + + char curr = 0; + while(null != current_node) { + if(key_index < key.length()) { + curr = key.charAt(key_index); + } else { + curr = 0; + } + if(curr == current_node.value) { + if(current_node.left != null || current_node.right != null) { + last_branch = current_node; + last_branch_parent = current_node_parent; + } + if(curr == 0) { + break; + } + current_node_parent = current_node; + current_node = (Node)current_node.middle; + key_index++; + continue; + } else if((current_node.value == 0 && curr < 64) || + (current_node.value != 0&& curr < current_node.value)) { + last_branch_parent = current_node; + current_node_parent = current_node; + current_node = current_node.left; + last_branch = current_node; + continue; + } else { + last_branch_parent = current_node; + current_node_parent = current_node; + current_node = current_node.right; + last_branch = current_node; + continue; + } + } + + if(null == current_node) { + return null; + } + + if(null == last_branch) { + next_node = this.head[key.charAt(0)]; + this.head[key.charAt(0)] = null; + } else if(last_branch.left == null && last_branch.right == null) { + if(last_branch_parent.left == last_branch) { + last_branch_parent.left = null; + } else { + last_branch_parent.right = null; + } + next_node = last_branch; + } else { + if(last_branch.left != null && last_branch.right != null) { + last_branch_replacement = last_branch.right; + last_branch_dangling_child = last_branch.left; + } else if(last_branch.right != null) { + last_branch_replacement = last_branch.right; + last_branch_dangling_child = null; + } else { + last_branch_replacement = last_branch.left; + last_branch_dangling_child = null; + } + + if(last_branch_parent == null) { + this.head[key.charAt(0)] = last_branch_replacement; + } else { + if(last_branch_parent.left == last_branch) { + last_branch_parent.left = last_branch_replacement; + } else if(last_branch_parent.right == last_branch) { + last_branch_parent.right = last_branch_replacement; + } else { + last_branch_parent.middle = last_branch_replacement; + } + } + + if(last_branch_dangling_child != null) { + current_node = last_branch_replacement; + while(current_node.left != null) { + current_node = current_node.left; + } + current_node.left = last_branch_dangling_child; + } + + next_node = last_branch; + } + + do { + current_node = (Node)next_node; + next_node = current_node.middle; + current_node.left = null; + current_node.right = null; + current_node.middle = this.free_list; + this.free_list = current_node; + } while(current_node.value != 0); + + + return next_node; + } + + public boolean grow_node_free_list() { + Node current_node = null; + NodeLines new_line = null; + + new_line = new NodeLines(); + + new_line.node_line = new Node[this.node_line_width]; + for(int i=0;i<this.node_line_width;i++) { + new_line.node_line[i] = new Node(); + } + + new_line.next = this.node_lines; + this.node_lines = new_line; + + current_node = this.node_lines.node_line[0]; + this.free_list = current_node; + for(int i=1;i<this.node_line_width;i++) { + current_node.middle = this.node_lines.node_line[i]; + current_node = (Node)current_node.middle; + } + current_node.middle = null; + + return true; + } + + + public static void main(final String[] args) { + final TernarySearchTree tst = new TernarySearchTree(30); + int ret = tst.insert("fOO","VAL1",0, new Object[0]); + System.err.println("ret: " + ret); + ret = tst.insert("bar","VAL2",0, new Object[0]); + System.err.println("ret: " + ret); + ret = tst.insert("baz","VAL3",0, new Object[0]); + System.err.println("ret: " + ret); + ret = tst.insert("zydsfgfd","VAL4",0, new Object[0]); + System.err.println("ret: " + ret); + ret = tst.insert("1242","VAL5",0, new Object[0]); + System.err.println("ret: " + ret); + + Object val = tst.delete("fOO"); + System.err.println("del: " + val); + + int[] pref_len = new int[1]; + pref_len[0] = 0; + val = tst.search("ba",pref_len); + System.err.println("search: " + val + " pref_len: " + pref_len[0]); + val = tst.search("bar",pref_len); + System.err.println("search: " + val + " pref_len: " + pref_len[0]); + } +}// TernarySearchTree |