diff options
Diffstat (limited to 'ext/http11_java/org/jruby')
| -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, 0 insertions, 598 deletions
diff --git a/ext/http11_java/org/jruby/mongrel/Http11.java b/ext/http11_java/org/jruby/mongrel/Http11.java index a73c79b..4b2fd2e 100644 --- a/ext/http11_java/org/jruby/mongrel/Http11.java +++ b/ext/http11_java/org/jruby/mongrel/Http11.java @@ -83,8 +83,6 @@ 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 deleted file mode 100644 index 73ba1ba..0000000 --- a/ext/http11_java/org/jruby/mongrel/URIClassifier.java +++ /dev/null @@ -1,129 +0,0 @@ -/***** 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 deleted file mode 100644 index 334763d..0000000 --- a/ext/http11_java/org/jruby/tst/Node.java +++ /dev/null @@ -1,18 +0,0 @@ -/* - * 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 deleted file mode 100644 index 87b56d7..0000000 --- a/ext/http11_java/org/jruby/tst/NodeLines.java +++ /dev/null @@ -1,16 +0,0 @@ -/* - * 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 deleted file mode 100644 index 5637bf1..0000000 --- a/ext/http11_java/org/jruby/tst/TernarySearchTree.java +++ /dev/null @@ -1,433 +0,0 @@ -/* - * 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 |