initial import into trunk

git-svn-id: svn+ssh://rubyforge.org/var/svn/mongrel/trunk@4 19e92222-5c0b-0410-8929-a290d50e31e9

14 files changed, 2101 insertions, 0 deletions

diff --git a/ext/http11/MANIFEST b/ext/http11/MANIFEST
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/ext/http11/MANIFEST
diff --git a/ext/http11/ext_help.h b/ext/http11/ext_help.h
new file mode 100644
index 0000000..8b4d754
--- /dev/null
+++ b/ext/http11/ext_help.h
@@ -0,0 +1,14 @@
+#ifndef ext_help_h
+#define ext_help_h
+
+#define RAISE_NOT_NULL(T) if(T == NULL) rb_raise(rb_eArgError, "NULL found for " # T " when shouldn't be.");
+#define DATA_GET(from,type,name) Data_Get_Struct(from,type,name); RAISE_NOT_NULL(name);
+#define REQUIRE_TYPE(V, T) if(TYPE(V) != T) rb_raise(rb_eTypeError, "Wrong argument type for " # V " required " # T);
+
+#ifdef DEBUG
+#define TRACE()  fprintf(stderr, "> %s:%d:%s\n", __FILE__, __LINE__, __FUNCTION__)
+#else
+#define TRACE() 
+#endif
+
+#endif
diff --git a/ext/http11/extconf.rb b/ext/http11/extconf.rb
new file mode 100644
index 0000000..e4f6918
--- /dev/null
+++ b/ext/http11/extconf.rb
@@ -0,0 +1,6 @@
+require 'mkmf'
+
+dir_config("http11")
+have_library("c", "main")
+
+create_makefile("http11")
diff --git a/ext/http11/http11.c b/ext/http11/http11.c
new file mode 100644
index 0000000..3755d65
--- /dev/null
+++ b/ext/http11/http11.c
@@ -0,0 +1,429 @@
+#include "ruby.h"
+#include "ext_help.h"
+#include <assert.h>
+#include <string.h>
+#include "http11_parser.h"
+#include <ctype.h>
+#include "tst.h"
+
+static VALUE mMongrel;
+static VALUE cHttpParser;
+static VALUE cURIClassifier;
+
+
+void http_field(void *data, const char *field, size_t flen, const char *value, size_t vlen)
+{
+  char *ch, *end;
+  VALUE req = (VALUE)data;
+  VALUE f = rb_str_new2("HTTP_");
+  VALUE v = rb_str_new(value, vlen);
+  
+  rb_str_buf_cat(f, field, flen); 
+  
+  for(ch = RSTRING(f)->ptr, end = ch + RSTRING(f)->len; ch < end; ch++) {
+    if(*ch == '-') {
+      *ch = '_';
+    } else {
+      *ch = toupper(*ch);
+    }
+  }
+
+  rb_hash_aset(req, f, v);
+}
+
+void request_method(void *data, const char *at, size_t length)
+{
+  VALUE req = (VALUE)data;
+  VALUE val = rb_str_new(at, length);
+  VALUE id = rb_str_new2("REQUEST_METHOD");
+  rb_hash_aset(req, id, val);
+}
+
+void path_info(void *data, const char *at, size_t length)
+{
+  VALUE req = (VALUE)data;
+  VALUE val = rb_str_new(at, length);
+  VALUE id = rb_str_new2("PATH_INFO");
+  rb_hash_aset(req, id, val);
+}
+
+
+void query_string(void *data, const char *at, size_t length)
+{
+  VALUE req = (VALUE)data;
+  VALUE val = rb_str_new(at, length);
+  VALUE id = rb_str_new2("QUERY_STRING");
+  rb_hash_aset(req, id, val);
+}
+
+void http_version(void *data, const char *at, size_t length)
+{
+  VALUE req = (VALUE)data;
+  VALUE val = rb_str_new(at, length);
+  VALUE id = rb_str_new2("HTTP_VERSION");
+  rb_hash_aset(req, id, val);
+}
+
+
+
+
+
+void HttpParser_free(void *data) {
+    TRACE();
+    
+    if(data) {
+        free(data);
+    }
+}
+
+
+VALUE HttpParser_alloc(VALUE klass)
+{
+    TRACE();
+    VALUE obj;
+    http_parser *hp = calloc(1, sizeof(http_parser));
+    hp->http_field = http_field;
+    hp->request_method = request_method;
+    hp->path_info = path_info;
+    hp->query_string = query_string;
+    hp->http_version = http_version;
+    
+    obj = Data_Wrap_Struct(klass, NULL, HttpParser_free, hp);
+
+    return obj;
+}
+
+
+/**
+ * call-seq:
+ *    parser.new -> parser
+ *
+ * Creates a new parser.
+ */
+VALUE HttpParser_init(VALUE self)
+{
+  http_parser *http = NULL;
+  DATA_GET(self, http_parser, http);
+  http_parser_init(http);
+  
+  return self;
+}
+
+
+/**
+ * call-seq:
+ *    parser.reset -> nil
+ *
+ * Resets the parser to it's initial state so that you can reuse it
+ * rather than making new ones.
+ */
+VALUE HttpParser_reset(VALUE self)
+{
+  http_parser *http = NULL;
+  DATA_GET(self, http_parser, http);
+  http_parser_init(http);
+  
+  return Qnil;
+}
+
+
+/**
+ * call-seq:
+ *    parser.finish -> true/false
+ *
+ * Finishes a parser early which could put in a "good" or bad state.
+ * You should call reset after finish it or bad things will happen.
+ */
+VALUE HttpParser_finish(VALUE self)
+{
+  http_parser *http = NULL;
+  DATA_GET(self, http_parser, http);
+  http_parser_finish(http);
+  
+  return http_parser_is_finished(http) ? Qtrue : Qfalse;
+}
+
+
+/**
+ * call-seq:
+ *    parser.execute(req_hash, data) -> Integer
+ *
+ * Takes a Hash and a String of data, parses the String of data filling in the Hash
+ * returning an Integer to indicate how much of the data has been read.  No matter
+ * what the return value, you should call HttpParser#finished? and HttpParser#error?
+ * to figure out if it's done parsing or there was an error.
+ */
+VALUE HttpParser_execute(VALUE self, VALUE req_hash, VALUE data)
+{
+  http_parser *http = NULL;
+  DATA_GET(self, http_parser, http);
+
+  http->data = (void *)req_hash;
+  http_parser_execute(http, RSTRING(data)->ptr, RSTRING(data)->len);
+  
+  return INT2FIX(http_parser_nread(http));
+}
+
+
+/**
+ * call-seq:
+ *    parser.error? -> true/false
+ *
+ * Tells you whether the parser is in an error state.
+ */
+VALUE HttpParser_has_error(VALUE self)
+{
+  http_parser *http = NULL;
+  DATA_GET(self, http_parser, http);
+  
+  return http_parser_has_error(http) ? Qtrue : Qfalse;
+}
+
+
+/**
+ * call-seq:
+ *    parser.finished? -> true/false
+ *
+ * Tells you whether the parser is finished or not and in a good state.
+ */
+VALUE HttpParser_is_finished(VALUE self)
+{
+  http_parser *http = NULL;
+  DATA_GET(self, http_parser, http);
+  
+  return http_parser_is_finished(http) ? Qtrue : Qfalse;
+}
+
+
+/**
+ * call-seq:
+ *    parser.nread -> Integer
+ *
+ * Returns the amount of data processed so far during this processing cycle.  It is
+ * set to 0 on initialize or reset calls and is incremented each time execute is called.
+ */
+VALUE HttpParser_nread(VALUE self)
+{
+  http_parser *http = NULL;
+  DATA_GET(self, http_parser, http);
+  
+  return INT2FIX(http->nread);
+}
+
+
+void URIClassifier_free(void *data) 
+{
+    TRACE();
+    
+    if(data) {
+      tst_cleanup((struct tst *)data);
+    }
+}
+
+
+#define TRIE_INCREASE 30
+
+VALUE URIClassifier_alloc(VALUE klass)
+{
+    TRACE();
+    VALUE obj;
+    struct tst *tst = tst_init(TRIE_INCREASE);
+    assert(tst && "failed to initialize trie structure");
+
+    obj = Data_Wrap_Struct(klass, NULL, URIClassifier_free, tst);
+
+    return obj;
+}
+
+/**
+ * call-seq:
+ *    URIClassifier.new -> URIClassifier
+ *
+ * Initializes a new URIClassifier object that you can use to associate URI sequences
+ * with objects.  You can actually use it with any string sequence and any objects,
+ * but it's mostly used with URIs.
+ *
+ * It uses TST from http://www.octavian.org/cs/software.html to build an ternary search
+ * trie to hold all of the URIs.  It uses this to do an initial search for the a URI
+ * prefix, and then to break the URI into SCRIPT_NAME and PATH_INFO portions.  It actually
+ * will do two searches most of the time in order to find the right handler for the
+ * registered prefix portion.
+ *
+ * Here's how it all works.  Let's say you register "/blog" with a BlogHandler.  Great.
+ * Now, someone goes to "/blog/zedsucks/ass".  You want SCRIPT_NAME to be "/blog" and
+ * PATH_INFO to be "/zedsucks/ass".  URIClassifier first does a TST search and comes
+ * up with a failure, but knows that the failure ended at the "/blog" part.  So, that's
+ * the SCRIPT_NAME.  It then tries a second search for just "/blog".  If that comes back
+ * good then it sets the rest ("/zedsucks/ass") to the PATH_INFO and returns the BlogHandler.
+ *
+ * The optimal approach would be to not do the search twice, but the TST lib doesn't
+ * really support returning prefixes.  Might not be hard to add later.
+ *
+ * The key though is that it will try to match the *longest* match it can.  If you 
+ * also register "/blog/zed" then the above URI will give SCRIPT_NAME="/blog/zed", 
+ * PATH_INFO="sucks/ass".  Probably not what you want, so your handler will need to
+ * do the 404 thing.
+ *
+ * Take a look at the postamble of example/tepee.rb to see how this is handled for
+ * Camping. 
+ */
+VALUE URIClassifier_init(VALUE self)
+{
+  VALUE hash;
+
+  // we create an internal hash to protect stuff from the GC
+  hash = rb_hash_new();
+  rb_iv_set(self, "handler_map", hash);
+}
+
+
+/**
+ * call-seq:
+ *    uc.register("/someuri", SampleHandler.new) -> nil
+ *
+ * Registers the SampleHandler (one for all requests) with the "/someuri".
+ * When URIClassifier::resolve is called with "/someuri" it'll return
+ * SampleHandler immediately.  When "/someuri/pathhere" is called it'll
+ * find SomeHandler after a second search, and setup PATH_INFO="/pathhere".
+ *
+ * You actually can reuse this class to register nearly anything and 
+ * quickly resolve it.  This could be used for caching, fast mapping, etc.
+ * The downside is it uses much more memory than a Hash, but it can be
+ * a lot faster.  It's main advantage is that it works on prefixes, which
+ * is damn hard to get right with a Hash.
+ */
+VALUE URIClassifier_register(VALUE self, VALUE uri, VALUE handler)
+{
+  int rc = 0;
+  void *ptr = NULL;
+  struct tst *tst = NULL;
+  DATA_GET(self, struct tst, tst);
+
+  rc = tst_insert((unsigned char *)StringValueCStr(uri), (void *)handler , tst, 0, &ptr);
+
+  if(rc == TST_DUPLICATE_KEY) {
+    rb_raise(rb_eStandardError, "Handler already registered with that name");
+  } else if(rc == TST_ERROR) {
+    rb_raise(rb_eStandardError, "Memory error registering handler");
+  } else if(rc == TST_NULL_KEY) {
+    rb_raise(rb_eStandardError, "URI was empty");
+  }
+  
+  rb_hash_aset(rb_iv_get(self, "handler_map"), uri, handler);
+
+  return Qnil;
+}
+
+
+/**
+ * call-seq:
+ *    uc.unregister("/someuri")
+ *
+ * Yep, just removes this uri and it's handler from the trie.
+ */
+VALUE URIClassifier_unregister(VALUE self, VALUE uri)
+{
+  void *handler = NULL;
+  struct tst *tst = NULL;
+  DATA_GET(self, struct tst, tst);
+
+  handler = tst_delete((unsigned char *)StringValueCStr(uri), tst);
+
+  if(handler) {
+    rb_hash_delete(rb_iv_get(self, "handler_map"), uri);
+
+    return (VALUE)handler;
+  } else {
+    return Qnil;
+  }
+}
+
+
+/**
+ * call-seq:
+ *    uc.resolve("/someuri") -> "/someuri", "", handler
+ *    uc.resolve("/someuri/pathinfo") -> "/someuri", "/pathinfo", handler
+ *    uc.resolve("/notfound/orhere") -> nil, nil, nil
+ *
+ * Attempts to resolve either the whole URI or at the longest prefix, returning
+ * the prefix (as script_info), path (as path_info), and registered handler
+ * (usually an HttpHandler).
+ *
+ * It expects strings.  Don't try other string-line stuff yet.
+ */
+VALUE URIClassifier_resolve(VALUE self, VALUE uri)
+{
+  void *handler = NULL;
+  int pref_len = 0;
+  struct tst *tst = NULL;
+  VALUE result;
+  VALUE script_name;
+  VALUE path_info;
+  unsigned char *uri_str = NULL;
+  unsigned char *script_name_str = NULL;
+
+  DATA_GET(self, struct tst, tst);
+  uri_str = (unsigned char *)StringValueCStr(uri);
+
+  handler = tst_search(uri_str, tst, &pref_len);
+
+  // setup for multiple return values
+  result = rb_ary_new();
+
+
+  if(handler == NULL) {
+    script_name = rb_str_substr (uri, 0, pref_len);
+    script_name_str = (unsigned char *)StringValueCStr(script_name);
+
+    handler = tst_search(script_name_str, tst, NULL);
+
+    if(handler == NULL) {
+      // didn't find the script name at all
+      rb_ary_push(result, Qnil);
+      rb_ary_push(result, Qnil);
+      rb_ary_push(result, Qnil);
+      return result;
+    } else {
+      // found a handler, setup the path info and we're good
+      path_info = rb_str_substr(uri, pref_len, RSTRING(uri)->len);
+    }
+  } else {
+    // whole thing was found, so uri is the script name, path info empty
+    script_name = uri;
+    path_info = rb_str_new2("");
+  }
+
+  rb_ary_push(result, script_name);
+  rb_ary_push(result, path_info);
+  rb_ary_push(result, (VALUE)handler);
+  return result;
+}
+
+
+
+void Init_http11()
+{
+    
+  TRACE();
+  
+  mMongrel = rb_define_module("Mongrel");
+  
+  cHttpParser = rb_define_class_under(mMongrel, "HttpParser", rb_cObject);
+  rb_define_alloc_func(cHttpParser, HttpParser_alloc);
+  rb_define_method(cHttpParser, "initialize", HttpParser_init,0);
+  rb_define_method(cHttpParser, "reset", HttpParser_reset,0);
+  rb_define_method(cHttpParser, "finish", HttpParser_finish,0);
+  rb_define_method(cHttpParser, "execute", HttpParser_execute,2);
+  rb_define_method(cHttpParser, "error?", HttpParser_has_error,0);
+  rb_define_method(cHttpParser, "finished?", HttpParser_is_finished,0);
+  rb_define_method(cHttpParser, "nread", HttpParser_nread,0);
+
+  cURIClassifier = rb_define_class_under(mMongrel, "URIClassifier", rb_cObject);
+  rb_define_alloc_func(cURIClassifier, URIClassifier_alloc);
+  rb_define_method(cURIClassifier, "initialize", URIClassifier_init, 0);
+  rb_define_method(cURIClassifier, "register", URIClassifier_register, 2);
+  rb_define_method(cURIClassifier, "unregister", URIClassifier_unregister, 1);
+  rb_define_method(cURIClassifier, "resolve", URIClassifier_resolve, 1);
+}
+ 
+
diff --git a/ext/http11/http11_parser.c b/ext/http11/http11_parser.c
new file mode 100644
index 0000000..c256037
--- /dev/null
+++ b/ext/http11/http11_parser.c
@@ -0,0 +1,918 @@
+#line 1 "ext/http11/http11_parser.rl"
+#include "http11_parser.h"
+#include <stdio.h>
+#include <assert.h>
+#include <stdlib.h>
+#include <ctype.h>
+#include <string.h>
+
+#define MARK(S,F) assert((F) - (S)->mark >= 0); (S)->mark = (F);
+
+/** machine **/
+#line 100 "ext/http11/http11_parser.rl"
+
+
+/** Data **/
+
+#line 18 "ext/http11/http11_parser.c"
+static int http_parser_start = 0;
+
+static int http_parser_first_final = 56;
+
+static int http_parser_error = 1;
+
+#line 104 "ext/http11/http11_parser.rl"
+
+int http_parser_init(http_parser *parser)  {
+    int cs = 0;
+    
+#line 30 "ext/http11/http11_parser.c"
+        {
+        cs = http_parser_start;
+        }
+#line 108 "ext/http11/http11_parser.rl"
+    parser->cs = cs;
+    parser->body_start = NULL;
+    parser->content_len = 0;
+    parser->mark = NULL;
+    parser->nread = 0;
+
+    return(1);
+}
+
+
+/** exec **/
+size_t http_parser_execute(http_parser *parser, const char *buffer, size_t len)  {
+    const char *p, *pe;
+    int cs = parser->cs;
+
+    p = buffer;
+    pe = buffer+len;
+
+    
+#line 54 "ext/http11/http11_parser.c"
+        {
+        p -= 1;
+        if ( ++p == pe )
+                goto _out;
+        switch ( cs )
+        {
+case 0:
+        switch( (*p) ) {
+                case 68: goto tr13;
+                case 71: goto tr14;
+                case 72: goto tr15;
+                case 79: goto tr16;
+                case 80: goto tr17;
+                case 84: goto tr18;
+        }
+        goto st1;
+st1:
+        goto _out1;
+tr13:
+#line 14 "ext/http11/http11_parser.rl"
+        { MARK(parser, p); }
+        goto st2;
+st2:
+        if ( ++p == pe )
+                goto _out2;
+case 2:
+#line 81 "ext/http11/http11_parser.c"
+        if ( (*p) == 69 )
+                goto st3;
+        goto st1;
+st3:
+        if ( ++p == pe )
+                goto _out3;
+case 3:
+        if ( (*p) == 76 )
+                goto st4;
+        goto st1;
+st4:
+        if ( ++p == pe )
+                goto _out4;
+case 4:
+        if ( (*p) == 69 )
+                goto st5;
+        goto st1;
+st5:
+        if ( ++p == pe )
+                goto _out5;
+case 5:
+        if ( (*p) == 84 )
+                goto st6;
+        goto st1;
+st6:
+        if ( ++p == pe )
+                goto _out6;
+case 6:
+        if ( (*p) == 69 )
+                goto st7;
+        goto st1;
+st7:
+        if ( ++p == pe )
+                goto _out7;
+case 7:
+        if ( (*p) == 32 )
+                goto tr33;
+        goto st1;
+tr33:
+#line 29 "ext/http11/http11_parser.rl"
+        { 
+               if(parser->request_method != NULL)
+                              parser->request_method(parser->data, parser->mark, p - parser->mark);
+        }
+        goto st8;
+st8:
+        if ( ++p == pe )
+                goto _out8;
+case 8:
+#line 131 "ext/http11/http11_parser.c"
+        switch( (*p) ) {
+                case 42: goto tr27;
+                case 43: goto tr28;
+                case 47: goto tr29;
+                case 58: goto tr30;
+        }
+        if ( (*p) < 65 ) {
+                if ( 45 <= (*p) && (*p) <= 57 )
+                        goto tr28;
+        } else if ( (*p) > 90 ) {
+                if ( 97 <= (*p) && (*p) <= 122 )
+                        goto tr28;
+        } else
+                goto tr28;
+        goto st1;
+tr27:
+#line 14 "ext/http11/http11_parser.rl"
+        { MARK(parser, p); }
+        goto st9;
+st9:
+        if ( ++p == pe )
+                goto _out9;
+case 9:
+#line 155 "ext/http11/http11_parser.c"
+        if ( (*p) == 32 )
+                goto tr34;
+        goto st1;
+tr34:
+#line 33 "ext/http11/http11_parser.rl"
+        { 
+               if(parser->path_info != NULL)
+                              parser->path_info(parser->data, parser->mark, p - parser->mark);
+        }
+        goto st10;
+tr48:
+#line 37 "ext/http11/http11_parser.rl"
+        { 
+               if(parser->query_string != NULL)
+                              parser->query_string(parser->data, parser->mark, p - parser->mark);
+        }
+        goto st10;
+st10:
+        if ( ++p == pe )
+                goto _out10;
+case 10:
+#line 177 "ext/http11/http11_parser.c"
+        if ( (*p) == 72 )
+                goto tr11;
+        goto st1;
+tr11:
+#line 14 "ext/http11/http11_parser.rl"
+        { MARK(parser, p); }
+        goto st11;
+st11:
+        if ( ++p == pe )
+                goto _out11;
+case 11:
+#line 189 "ext/http11/http11_parser.c"
+        if ( (*p) == 84 )
+                goto st12;
+        goto st1;
+st12:
+        if ( ++p == pe )
+                goto _out12;
+case 12:
+        if ( (*p) == 84 )
+                goto st13;
+        goto st1;
+st13:
+        if ( ++p == pe )
+                goto _out13;
+case 13:
+        if ( (*p) == 80 )
+                goto st14;
+        goto st1;
+st14:
+        if ( ++p == pe )
+                goto _out14;
+case 14:
+        if ( (*p) == 47 )
+                goto st15;
+        goto st1;
+st15:
+        if ( ++p == pe )
+                goto _out15;
+case 15:
+        if ( 48 <= (*p) && (*p) <= 57 )
+                goto st16;
+        goto st1;
+st16:
+        if ( ++p == pe )
+                goto _out16;
+case 16:
+        if ( (*p) == 46 )
+                goto st17;
+        if ( 48 <= (*p) && (*p) <= 57 )
+                goto st16;
+        goto st1;
+st17:
+        if ( ++p == pe )
+                goto _out17;
+case 17:
+        if ( 48 <= (*p) && (*p) <= 57 )
+                goto st18;
+        goto st1;
+st18:
+        if ( ++p == pe )
+                goto _out18;
+case 18:
+        if ( (*p) == 13 )
+                goto tr37;
+        if ( 48 <= (*p) && (*p) <= 57 )
+                goto st18;
+        goto st1;
+tr37:
+#line 42 "ext/http11/http11_parser.rl"
+        {        
+               if(parser->http_version != NULL)
+                              parser->http_version(parser->data, parser->mark, p - parser->mark);
+        }
+        goto st19;
+st19:
+        if ( ++p == pe )
+                goto _out19;
+case 19:
+#line 257 "ext/http11/http11_parser.c"
+        if ( (*p) == 10 )
+                goto st20;
+        goto st1;
+st20:
+        if ( ++p == pe )
+                goto _out20;
+case 20:
+        switch( (*p) ) {
+                case 13: goto st21;
+                case 33: goto tr36;
+                case 124: goto tr36;
+                case 126: goto tr36;
+        }
+        if ( (*p) < 45 ) {
+                if ( (*p) > 39 ) {
+                        if ( 42 <= (*p) && (*p) <= 43 )
+                                goto tr36;
+                } else if ( (*p) >= 35 )
+                        goto tr36;
+        } else if ( (*p) > 46 ) {
+                if ( (*p) < 65 ) {
+                        if ( 48 <= (*p) && (*p) <= 57 )
+                                goto tr36;
+                } else if ( (*p) > 90 ) {
+                        if ( 94 <= (*p) && (*p) <= 122 )
+                                goto tr36;
+                } else
+                        goto tr36;
+        } else
+                goto tr36;
+        goto st1;
+st21:
+        if ( ++p == pe )
+                goto _out21;
+case 21:
+        if ( (*p) == 10 )
+                goto tr40;
+        goto st1;
+tr40:
+#line 46 "ext/http11/http11_parser.rl"
+        { 
+               parser->body_start = p+1; goto _out56;
+        }
+        goto st56;
+st56:
+        if ( ++p == pe )
+                goto _out56;
+case 56:
+#line 306 "ext/http11/http11_parser.c"
+        goto st1;
+tr36:
+#line 16 "ext/http11/http11_parser.rl"
+        { parser->field_start = p; }
+        goto st22;
+st22:
+        if ( ++p == pe )
+                goto _out22;
+case 22:
+#line 316 "ext/http11/http11_parser.c"
+        switch( (*p) ) {
+                case 33: goto st22;
+                case 58: goto tr32;
+                case 124: goto st22;
+                case 126: goto st22;
+        }
+        if ( (*p) < 45 ) {
+                if ( (*p) > 39 ) {
+                        if ( 42 <= (*p) && (*p) <= 43 )
+                                goto st22;
+                } else if ( (*p) >= 35 )
+                        goto st22;
+        } else if ( (*p) > 46 ) {
+                if ( (*p) < 65 ) {
+                        if ( 48 <= (*p) && (*p) <= 57 )
+                                goto st22;
+                } else if ( (*p) > 90 ) {
+                        if ( 94 <= (*p) && (*p) <= 122 )
+                                goto st22;
+                } else
+                        goto st22;
+        } else
+                goto st22;
+        goto st1;
+tr32:
+#line 17 "ext/http11/http11_parser.rl"
+        { 
+               parser->field_len = (p - parser->field_start);
+        }
+        goto st23;
+st23:
+        if ( ++p == pe )
+                goto _out23;
+case 23:
+#line 351 "ext/http11/http11_parser.c"
+        if ( (*p) == 13 )
+                goto tr56;
+        goto tr55;
+tr55:
+#line 21 "ext/http11/http11_parser.rl"
+        { MARK(parser, p); }
+        goto st24;
+st24:
+        if ( ++p == pe )
+                goto _out24;
+case 24:
+#line 363 "ext/http11/http11_parser.c"
+        if ( (*p) == 13 )
+                goto tr51;
+        goto st24;
+tr51:
+#line 22 "ext/http11/http11_parser.rl"
+        { 
+               if(parser->http_field != NULL) {
+                              parser->http_field(parser->data, 
+                                       parser->field_start, parser->field_len, 
+                                parser->mark+1, p - (parser->mark +1));
+                }
+        }
+        goto st25;
+tr56:
+#line 21 "ext/http11/http11_parser.rl"
+        { MARK(parser, p); }
+#line 22 "ext/http11/http11_parser.rl"
+        { 
+               if(parser->http_field != NULL) {
+                              parser->http_field(parser->data, 
+                                       parser->field_start, parser->field_len, 
+                                parser->mark+1, p - (parser->mark +1));
+                }
+        }
+        goto st25;
+st25:
+        if ( ++p == pe )
+                goto _out25;
+case 25:
+#line 393 "ext/http11/http11_parser.c"
+        switch( (*p) ) {
+                case 10: goto st26;
+                case 13: goto tr51;
+        }
+        goto st24;
+st26:
+        if ( ++p == pe )
+                goto _out26;
+case 26:
+        switch( (*p) ) {
+                case 13: goto st21;
+                case 33: goto tr42;
+                case 124: goto tr42;
+                case 126: goto tr42;
+        }
+        if ( (*p) < 45 ) {
+                if ( (*p) > 39 ) {
+                        if ( 42 <= (*p) && (*p) <= 43 )
+                                goto tr42;
+                } else if ( (*p) >= 35 )
+                        goto tr42;
+        } else if ( (*p) > 46 ) {
+                if ( (*p) < 65 ) {
+                        if ( 48 <= (*p) && (*p) <= 57 )
+                                goto tr42;
+                } else if ( (*p) > 90 ) {
+                        if ( 94 <= (*p) && (*p) <= 122 )
+                                goto tr42;
+                } else
+                        goto tr42;
+        } else
+                goto tr42;
+        goto st24;
+tr42:
+#line 16 "ext/http11/http11_parser.rl"
+        { parser->field_start = p; }
+        goto st27;
+st27:
+        if ( ++p == pe )
+                goto _out27;
+case 27:
+#line 435 "ext/http11/http11_parser.c"
+        switch( (*p) ) {
+                case 13: goto tr51;
+                case 33: goto st27;
+                case 58: goto tr32;
+                case 124: goto st27;
+                case 126: goto st27;
+        }
+        if ( (*p) < 45 ) {
+                if ( (*p) > 39 ) {
+                        if ( 42 <= (*p) && (*p) <= 43 )
+                                goto st27;
+                } else if ( (*p) >= 35 )
+                        goto st27;
+        } else if ( (*p) > 46 ) {
+                if ( (*p) < 65 ) {
+                        if ( 48 <= (*p) && (*p) <= 57 )
+                                goto st27;
+                } else if ( (*p) > 90 ) {
+                        if ( 94 <= (*p) && (*p) <= 122 )
+                                goto st27;
+                } else
+                        goto st27;
+        } else
+                goto st27;
+        goto st24;
+tr28:
+#line 14 "ext/http11/http11_parser.rl"
+        { MARK(parser, p); }
+        goto st28;
+st28:
+        if ( ++p == pe )
+                goto _out28;
+case 28:
+#line 469 "ext/http11/http11_parser.c"
+        switch( (*p) ) {
+                case 43: goto st28;
+                case 58: goto st29;
+        }
+        if ( (*p) < 48 ) {
+                if ( 45 <= (*p) && (*p) <= 46 )
+                        goto st28;
+        } else if ( (*p) > 57 ) {
+                if ( (*p) > 90 ) {
+                        if ( 97 <= (*p) && (*p) <= 122 )
+                                goto st28;
+                } else if ( (*p) >= 65 )
+                        goto st28;
+        } else
+                goto st28;
+        goto st1;
+tr30:
+#line 14 "ext/http11/http11_parser.rl"
+        { MARK(parser, p); }
+        goto st29;
+st29:
+        if ( ++p == pe )
+                goto _out29;
+case 29:
+#line 494 "ext/http11/http11_parser.c"
+        switch( (*p) ) {
+                case 32: goto tr34;
+                case 37: goto st30;
+                case 60: goto st1;
+                case 62: goto st1;
+                case 127: goto st1;
+        }
+        if ( (*p) > 31 ) {
+                if ( 34 <= (*p) && (*p) <= 35 )
+                        goto st1;
+        } else if ( (*p) >= 0 )
+                goto st1;
+        goto st29;
+st30:
+        if ( ++p == pe )
+                goto _out30;
+case 30:
+        if ( (*p) < 65 ) {
+                if ( 48 <= (*p) && (*p) <= 57 )
+                        goto st31;
+        } else if ( (*p) > 70 ) {
+                if ( 97 <= (*p) && (*p) <= 102 )
+                        goto st31;
+        } else
+                goto st31;
+        goto st1;
+st31:
+        if ( ++p == pe )
+                goto _out31;
+case 31:
+        if ( (*p) < 65 ) {
+                if ( 48 <= (*p) && (*p) <= 57 )
+                        goto st29;
+        } else if ( (*p) > 70 ) {
+                if ( 97 <= (*p) && (*p) <= 102 )
+                        goto st29;
+        } else
+                goto st29;
+        goto st1;
+tr29:
+#line 14 "ext/http11/http11_parser.rl"
+        { MARK(parser, p); }
+        goto st32;
+st32:
+        if ( ++p == pe )
+                goto _out32;
+case 32:
+#line 542 "ext/http11/http11_parser.c"
+        switch( (*p) ) {
+                case 32: goto tr34;
+                case 37: goto st34;
+                case 47: goto st1;
+                case 60: goto st1;
+                case 62: goto st1;
+                case 63: goto tr46;
+                case 127: goto st1;
+        }
+        if ( (*p) > 31 ) {
+                if ( 34 <= (*p) && (*p) <= 35 )
+                        goto st1;
+        } else if ( (*p) >= 0 )
+                goto st1;
+        goto st33;
+st33:
+        if ( ++p == pe )
+                goto _out33;
+case 33:
+        switch( (*p) ) {
+                case 32: goto tr34;
+                case 37: goto st34;
+                case 60: goto st1;
+                case 62: goto st1;
+                case 63: goto tr46;
+                case 127: goto st1;
+        }
+        if ( (*p) > 31 ) {
+                if ( 34 <= (*p) && (*p) <= 35 )
+                        goto st1;
+        } else if ( (*p) >= 0 )
+                goto st1;
+        goto st33;
+st34:
+        if ( ++p == pe )
+                goto _out34;
+case 34:
+        if ( (*p) < 65 ) {
+                if ( 48 <= (*p) && (*p) <= 57 )
+                        goto st35;
+        } else if ( (*p) > 70 ) {
+                if ( 97 <= (*p) && (*p) <= 102 )
+                        goto st35;
+        } else
+                goto st35;
+        goto st1;
+st35:
+        if ( ++p == pe )
+                goto _out35;
+case 35:
+        if ( (*p) < 65 ) {
+                if ( 48 <= (*p) && (*p) <= 57 )
+                        goto st33;
+        } else if ( (*p) > 70 ) {
+                if ( 97 <= (*p) && (*p) <= 102 )
+                        goto st33;
+        } else
+                goto st33;
+        goto st1;
+tr46:
+#line 33 "ext/http11/http11_parser.rl"
+        { 
+               if(parser->path_info != NULL)
+                              parser->path_info(parser->data, parser->mark, p - parser->mark);
+        }
+        goto st36;
+st36:
+        if ( ++p == pe )
+                goto _out36;
+case 36:
+#line 613 "ext/http11/http11_parser.c"
+        switch( (*p) ) {
+                case 32: goto tr48;
+                case 37: goto tr54;
+                case 60: goto st1;
+                case 62: goto st1;
+                case 127: goto st1;
+        }
+        if ( (*p) > 31 ) {
+                if ( 34 <= (*p) && (*p) <= 35 )
+                        goto st1;
+        } else if ( (*p) >= 0 )
+                goto st1;
+        goto tr53;
+tr53:
+#line 14 "ext/http11/http11_parser.rl"
+        { MARK(parser, p); }
+        goto st37;
+st37:
+        if ( ++p == pe )
+                goto _out37;
+case 37:
+#line 635 "ext/http11/http11_parser.c"
+        switch( (*p) ) {
+                case 32: goto tr48;
+                case 37: goto st38;
+                case 60: goto st1;
+                case 62: goto st1;
+                case 127: goto st1;
+        }
+        if ( (*p) > 31 ) {
+                if ( 34 <= (*p) && (*p) <= 35 )
+                        goto st1;
+        } else if ( (*p) >= 0 )
+                goto st1;
+        goto st37;
+tr54:
+#line 14 "ext/http11/http11_parser.rl"
+        { MARK(parser, p); }
+        goto st38;
+st38:
+        if ( ++p == pe )
+                goto _out38;
+case 38:
+#line 657 "ext/http11/http11_parser.c"
+        if ( (*p) < 65 ) {
+                if ( 48 <= (*p) && (*p) <= 57 )
+                        goto st39;
+        } else if ( (*p) > 70 ) {
+                if ( 97 <= (*p) && (*p) <= 102 )
+                        goto st39;
+        } else
+                goto st39;
+        goto st1;
+st39:
+        if ( ++p == pe )
+                goto _out39;
+case 39:
+        if ( (*p) < 65 ) {
+                if ( 48 <= (*p) && (*p) <= 57 )
+                        goto st37;
+        } else if ( (*p) > 70 ) {
+                if ( 97 <= (*p) && (*p) <= 102 )
+                        goto st37;
+        } else
+                goto st37;
+        goto st1;
+tr14:
+#line 14 "ext/http11/http11_parser.rl"
+        { MARK(parser, p); }
+        goto st40;
+st40:
+        if ( ++p == pe )
+                goto _out40;
+case 40:
+#line 688 "ext/http11/http11_parser.c"
+        if ( (*p) == 69 )
+                goto st41;
+        goto st1;
+st41:
+        if ( ++p == pe )
+                goto _out41;
+case 41:
+        if ( (*p) == 84 )
+                goto st7;
+        goto st1;
+tr15:
+#line 14 "ext/http11/http11_parser.rl"
+        { MARK(parser, p); }
+        goto st42;
+st42:
+        if ( ++p == pe )
+                goto _out42;
+case 42:
+#line 707 "ext/http11/http11_parser.c"
+        if ( (*p) == 69 )
+                goto st43;
+        goto st1;
+st43:
+        if ( ++p == pe )
+                goto _out43;
+case 43:
+        if ( (*p) == 65 )
+                goto st44;
+        goto st1;
+st44:
+        if ( ++p == pe )
+                goto _out44;
+case 44:
+        if ( (*p) == 68 )
+                goto st7;
+        goto st1;
+tr16:
+#line 14 "ext/http11/http11_parser.rl"
+        { MARK(parser, p); }
+        goto st45;
+st45:
+        if ( ++p == pe )
+                goto _out45;
+case 45:
+#line 733 "ext/http11/http11_parser.c"
+        if ( (*p) == 80 )
+                goto st46;
+        goto st1;
+st46:
+        if ( ++p == pe )
+                goto _out46;
+case 46:
+        if ( (*p) == 84 )
+                goto st47;
+        goto st1;
+st47:
+        if ( ++p == pe )
+                goto _out47;
+case 47:
+        if ( (*p) == 73 )
+                goto st48;
+        goto st1;
+st48:
+        if ( ++p == pe )
+                goto _out48;
+case 48:
+        if ( (*p) == 79 )
+                goto st49;
+        goto st1;
+st49:
+        if ( ++p == pe )
+                goto _out49;
+case 49:
+        if ( (*p) == 78 )
+                goto st50;
+        goto st1;
+st50:
+        if ( ++p == pe )
+                goto _out50;
+case 50:
+        if ( (*p) == 83 )
+                goto st7;
+        goto st1;
+tr17:
+#line 14 "ext/http11/http11_parser.rl"
+        { MARK(parser, p); }
+        goto st51;
+st51:
+        if ( ++p == pe )
+                goto _out51;
+case 51:
+#line 780 "ext/http11/http11_parser.c"
+        switch( (*p) ) {
+                case 79: goto st52;
+                case 85: goto st41;
+        }
+        goto st1;
+st52:
+        if ( ++p == pe )
+                goto _out52;
+case 52:
+        if ( (*p) == 83 )
+                goto st41;
+        goto st1;
+tr18:
+#line 14 "ext/http11/http11_parser.rl"
+        { MARK(parser, p); }
+        goto st53;
+st53:
+        if ( ++p == pe )
+                goto _out53;
+case 53:
+#line 801 "ext/http11/http11_parser.c"
+        if ( (*p) == 82 )
+                goto st54;
+        goto st1;
+st54:
+        if ( ++p == pe )
+                goto _out54;
+case 54:
+        if ( (*p) == 65 )
+                goto st55;
+        goto st1;
+st55:
+        if ( ++p == pe )
+                goto _out55;
+case 55:
+        if ( (*p) == 67 )
+                goto st6;
+        goto st1;
+        }
+        _out1: cs = 1; goto _out; 
+        _out2: cs = 2; goto _out; 
+        _out3: cs = 3; goto _out; 
+        _out4: cs = 4; goto _out; 
+        _out5: cs = 5; goto _out; 
+        _out6: cs = 6; goto _out; 
+        _out7: cs = 7; goto _out; 
+        _out8: cs = 8; goto _out; 
+        _out9: cs = 9; goto _out; 
+        _out10: cs = 10; goto _out; 
+        _out11: cs = 11; goto _out; 
+        _out12: cs = 12; goto _out; 
+        _out13: cs = 13; goto _out; 
+        _out14: cs = 14; goto _out; 
+        _out15: cs = 15; goto _out; 
+        _out16: cs = 16; goto _out; 
+        _out17: cs = 17; goto _out; 
+        _out18: cs = 18; goto _out; 
+        _out19: cs = 19; goto _out; 
+        _out20: cs = 20; goto _out; 
+        _out21: cs = 21; goto _out; 
+        _out56: cs = 56; goto _out; 
+        _out22: cs = 22; goto _out; 
+        _out23: cs = 23; goto _out; 
+        _out24: cs = 24; goto _out; 
+        _out25: cs = 25; goto _out; 
+        _out26: cs = 26; goto _out; 
+        _out27: cs = 27; goto _out; 
+        _out28: cs = 28; goto _out; 
+        _out29: cs = 29; goto _out; 
+        _out30: cs = 30; goto _out; 
+        _out31: cs = 31; goto _out; 
+        _out32: cs = 32; goto _out; 
+        _out33: cs = 33; goto _out; 
+        _out34: cs = 34; goto _out; 
+        _out35: cs = 35; goto _out; 
+        _out36: cs = 36; goto _out; 
+        _out37: cs = 37; goto _out; 
+        _out38: cs = 38; goto _out; 
+        _out39: cs = 39; goto _out; 
+        _out40: cs = 40; goto _out; 
+        _out41: cs = 41; goto _out; 
+        _out42: cs = 42; goto _out; 
+        _out43: cs = 43; goto _out; 
+        _out44: cs = 44; goto _out; 
+        _out45: cs = 45; goto _out; 
+        _out46: cs = 46; goto _out; 
+        _out47: cs = 47; goto _out; 
+        _out48: cs = 48; goto _out; 
+        _out49: cs = 49; goto _out; 
+        _out50: cs = 50; goto _out; 
+        _out51: cs = 51; goto _out; 
+        _out52: cs = 52; goto _out; 
+        _out53: cs = 53; goto _out; 
+        _out54: cs = 54; goto _out; 
+        _out55: cs = 55; goto _out; 
+
+        _out: {}
+        }
+#line 127 "ext/http11/http11_parser.rl"
+
+    parser->cs = cs;
+    parser->nread = p - buffer;
+    if(parser->body_start) {
+        /* final \r\n combo encountered so stop right here */
+        
+#line 886 "ext/http11/http11_parser.c"
+#line 133 "ext/http11/http11_parser.rl"
+        parser->nread++;
+    }
+
+    return(parser->nread);
+}
+
+int http_parser_finish(http_parser *parser)
+{
+        int cs = parser->cs;
+
+        
+#line 899 "ext/http11/http11_parser.c"
+#line 144 "ext/http11/http11_parser.rl"
+
+        parser->cs = cs;
+
+        if (http_parser_has_error(parser) ) {
+                return -1;
+        } else if (http_parser_is_finished(parser) ) {
+                return 1;
+        } else {
+               return 0;
+        }
+}
+
+int http_parser_has_error(http_parser *parser) {
+    return parser->cs == http_parser_error;
+}
+
+int http_parser_is_finished(http_parser *parser) {
+    return parser->cs == http_parser_first_final;
+}
diff --git a/ext/http11/http11_parser.h b/ext/http11/http11_parser.h
new file mode 100644
index 0000000..f4a205f
--- /dev/null
+++ b/ext/http11/http11_parser.h
@@ -0,0 +1,37 @@
+#ifndef http11_parser_h
+#define http11_parser_h
+
+#include <sys/types.h>
+
+typedef void (*element_cb)(void *data, const char *at, size_t length);
+typedef void (*field_cb)(void *data, const char *field, size_t flen, const char *value, size_t vlen);
+
+typedef struct http_parser { 
+  int cs;
+  const char *body_start;
+  int content_len;
+  size_t nread;
+  const char *mark;
+  const char *field_start;
+  size_t field_len;
+
+  void *data;
+
+  field_cb http_field;
+  element_cb request_method;
+  element_cb path_info;
+  element_cb query_string;
+  element_cb http_version;
+
+} http_parser;
+
+int http_parser_init(http_parser *parser);
+int http_parser_finish(http_parser *parser);
+size_t http_parser_execute(http_parser *parser, const char *data, size_t len );
+int http_parser_has_error(http_parser *parser);
+int http_parser_is_finished(http_parser *parser);
+void http_parser_destroy(http_parser *parser);
+
+#define http_parser_nread(parser) (parser)->nread 
+
+#endif
diff --git a/ext/http11/http11_parser.rl b/ext/http11/http11_parser.rl
new file mode 100644
index 0000000..7642cb1
--- /dev/null
+++ b/ext/http11/http11_parser.rl
@@ -0,0 +1,162 @@
+#include "http11_parser.h"
+#include <stdio.h>
+#include <assert.h>
+#include <stdlib.h>
+#include <ctype.h>
+#include <string.h>
+
+#define MARK(S,F) assert((F) - (S)->mark >= 0); (S)->mark = (F);
+
+/** machine **/
+%%{
+        machine http_parser;
+
+            action mark { MARK(parser, fpc); }
+
+        action start_field { parser->field_start = fpc; }        
+        action write_field { 
+               parser->field_len = (p - parser->field_start);
+        }
+
+        action start_value { MARK(parser, fpc); }
+        action write_value { 
+               if(parser->http_field != NULL) {
+                              parser->http_field(parser->data, 
+                                       parser->field_start, parser->field_len, 
+                                parser->mark+1, p - (parser->mark +1));
+                }
+        }
+        action request_method { 
+               if(parser->request_method != NULL)
+                              parser->request_method(parser->data, parser->mark, p - parser->mark);
+        }
+        action path_info { 
+               if(parser->path_info != NULL)
+                              parser->path_info(parser->data, parser->mark, p - parser->mark);
+        }
+        action query_string { 
+               if(parser->query_string != NULL)
+                              parser->query_string(parser->data, parser->mark, p - parser->mark);
+        }
+
+        action http_version {        
+               if(parser->http_version != NULL)
+                              parser->http_version(parser->data, parser->mark, p - parser->mark);
+        }
+            action done { 
+               parser->body_start = p+1; fbreak;
+        }
+
+
+        #### HTTP PROTOCOL GRAMMAR
+        # line endings
+        CRLF = "\r\n";
+
+        # character types
+        CTL = (cntrl | 127);
+        safe = ("$" | "-" | "_" | ".");
+        extra = ("!" | "*" | "'" | "(" | ")" | ",");
+        reserved = (";" | "/" | "?" | ":" | "@" | "&" | "=" | "+");
+        unsafe = (CTL | " " | "\"" | "#" | "%" | "<" | ">");
+        national = any - (alpha | digit | reserved | extra | safe | unsafe);
+        unreserved = (alpha | digit | safe | extra | national);
+        escape = ("%" xdigit xdigit);
+        uchar = (unreserved | escape);
+        pchar = (uchar | ":" | "@" | "&" | "=" | "+");
+        tspecials = ("(" | ")" | "<" | ">" | "@" | "," | ";" | ":" | "\\" | "\"" | "/" | "[" | "]" | "?" | "=" | "{" | "}" | " " | "\t");
+
+        # elements
+        token = (ascii - (CTL | tspecials));
+
+        # URI schemes and absolute paths
+        scheme = ( alpha | digit | "+" | "-" | "." )* ;
+        absolute_uri = (scheme ":" (uchar | reserved )*) >mark %path_info;
+
+        path = (pchar+ ( "/" pchar* )*) ;
+        query = ( uchar | reserved )* >mark %query_string ;
+        param = ( pchar | "/" )* ;
+        params = (param ( ";" param )*) ;
+        rel_path = (path? (";" params)?) %path_info  ("?" query)? ;
+        absolute_path = ("/" rel_path) >mark ;
+        
+        Request_URI = ("*" >mark %path_info | absolute_uri | absolute_path) ;
+        Method = ("OPTIONS"| "GET" | "HEAD" | "POST" | "PUT" | "DELETE" | "TRACE") >mark %request_method;
+        
+        http_number = (digit+ "." digit+) ;
+        HTTP_Version = ("HTTP/" http_number) >mark %http_version ;
+        Request_Line = (Method " " Request_URI " " HTTP_Version CRLF) ;
+
+       
+        
+        field_name = (token - ":")+ >start_field %write_field;
+
+        field_value = (any - CRLF)*;
+
+        message_header = field_name ":" field_value >start_value %write_value CRLF;
+        
+        Request = Request_Line (message_header)* $0 ( CRLF $1 @done );
+
+                main := Request;
+}%%
+
+/** Data **/
+%% write data;
+
+int http_parser_init(http_parser *parser)  {
+    int cs = 0;
+    %% write init;
+    parser->cs = cs;
+    parser->body_start = NULL;
+    parser->content_len = 0;
+    parser->mark = NULL;
+    parser->nread = 0;
+
+    return(1);
+}
+
+
+/** exec **/
+size_t http_parser_execute(http_parser *parser, const char *buffer, size_t len)  {
+    const char *p, *pe;
+    int cs = parser->cs;
+
+    p = buffer;
+    pe = buffer+len;
+
+    %% write exec;
+
+    parser->cs = cs;
+    parser->nread = p - buffer;
+    if(parser->body_start) {
+        /* final \r\n combo encountered so stop right here */
+        %%write eof;
+        parser->nread++;
+    }
+
+    return(parser->nread);
+}
+
+int http_parser_finish(http_parser *parser)
+{
+        int cs = parser->cs;
+
+        %%write eof;
+
+        parser->cs = cs;
+
+        if (http_parser_has_error(parser) ) {
+                return -1;
+        } else if (http_parser_is_finished(parser) ) {
+                return 1;
+        } else {
+               return 0;
+        }
+}
+
+int http_parser_has_error(http_parser *parser) {
+    return parser->cs == http_parser_error;
+}
+
+int http_parser_is_finished(http_parser *parser) {
+    return parser->cs == http_parser_first_final;
+}
diff --git a/ext/http11/tst.h b/ext/http11/tst.h
new file mode 100644
index 0000000..8e5ab2c
--- /dev/null
+++ b/ext/http11/tst.h
@@ -0,0 +1,40 @@
+
+
+struct node
+{
+   unsigned char value;
+   struct node *left;
+   struct node *middle;
+   struct node *right;
+};
+
+struct tst
+{
+   int node_line_width;
+   struct node_lines *node_lines;
+   struct node *free_list;
+   struct node *head[127];
+};
+
+struct node_lines
+{
+   struct node *node_line;
+   struct node_lines *next;
+};
+
+enum tst_constants
+{
+   TST_OK, TST_ERROR, TST_NULL_KEY, TST_DUPLICATE_KEY, TST_REPLACE
+};
+
+struct tst *tst_init(int node_line_width);
+
+int tst_insert(unsigned char *key, void *data, struct tst *tst, int option, void **exist_ptr);
+
+void *tst_search(unsigned char *key, struct tst *tst, int *prefix_len);
+
+void *tst_delete(unsigned char *key, struct tst *tst);
+
+void tst_cleanup(struct tst *tst);
+
+
diff --git a/ext/http11/tst_cleanup.c b/ext/http11/tst_cleanup.c
new file mode 100644
index 0000000..b574f9f
--- /dev/null
+++ b/ext/http11/tst_cleanup.c
@@ -0,0 +1,24 @@
+
+#include "tst.h"
+#include <stdio.h>
+#include <stdlib.h>
+
+void tst_cleanup(struct tst *tst)
+{
+   struct node_lines *current_line;
+   struct node_lines *next_line;
+
+   next_line = tst->node_lines;
+
+   do
+   {
+      current_line = next_line;
+      next_line = current_line->next;
+      free(current_line->node_line);
+      free(current_line);
+   }
+   while(next_line != NULL);
+
+   free(tst);
+}
+
diff --git a/ext/http11/tst_delete.c b/ext/http11/tst_delete.c
new file mode 100644
index 0000000..cb18f16
--- /dev/null
+++ b/ext/http11/tst_delete.c
@@ -0,0 +1,146 @@
+
+#include "tst.h"
+#include <stdio.h>
+#include <stdlib.h>
+
+void *tst_delete(unsigned char *key, struct tst *tst)
+{
+   struct node *current_node;
+   struct node *current_node_parent;
+   struct node *last_branch;
+   struct node *last_branch_parent;
+   struct node *next_node;
+   struct node *last_branch_replacement;
+   struct node *last_branch_dangling_child;
+   int key_index;
+
+   
+   if(key[0] == 0)
+      return NULL;
+   if(tst->head[(int)key[0]] == NULL)
+      return NULL;
+   
+   last_branch = NULL;
+   last_branch_parent = NULL;
+   current_node = tst->head[(int)key[0]];
+   current_node_parent = NULL;
+   key_index = 1;
+   while(current_node != NULL)
+   {
+      if(key[key_index] == current_node->value)
+      {
+         
+         if( (current_node->left != NULL) || (current_node->right != NULL) )
+         {
+            last_branch = current_node;
+            last_branch_parent = current_node_parent;
+         }
+         if(key[key_index] == 0)
+            break;
+         else
+         {
+            current_node_parent = current_node;
+            current_node = current_node->middle;
+            key_index++;
+            continue;
+         }
+      }
+      else if( ((current_node->value == 0) && (key[key_index] < 64)) ||
+         ((current_node->value != 0) && (key[key_index] <
+         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(current_node == NULL)
+      return NULL;
+   
+   if(last_branch == NULL)
+   {
+      
+         next_node = tst->head[(int)key[0]];
+         tst->head[(int)key[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)
+         tst->head[(int)key[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 = next_node;
+      next_node = current_node->middle;
+      
+      current_node->left = NULL;
+      current_node->right = NULL;
+      current_node->middle = tst->free_list;
+      tst->free_list = current_node;
+   }
+   while(current_node->value != 0);
+   
+   return next_node;
+   
+}
+
diff --git a/ext/http11/tst_grow_node_free_list.c b/ext/http11/tst_grow_node_free_list.c
new file mode 100644
index 0000000..da21333
--- /dev/null
+++ b/ext/http11/tst_grow_node_free_list.c
@@ -0,0 +1,38 @@
+
+#include "tst.h"
+#include <stdio.h>
+#include <stdlib.h>
+
+int tst_grow_node_free_list(struct tst *tst)
+{
+   struct node *current_node;
+   struct node_lines *new_line;
+   int i;
+
+   
+   if((new_line = (struct node_lines *) malloc(sizeof(struct node_lines))) == NULL)
+      return TST_ERROR;
+   
+   if((new_line->node_line = (struct node *)
+   calloc(tst->node_line_width, sizeof(struct node))) == NULL)
+   {
+      free(new_line);
+      return TST_ERROR;
+   }
+   else
+   {
+      new_line->next = tst->node_lines;
+      tst->node_lines = new_line;
+   }
+   
+   current_node = tst->node_lines->node_line;
+   tst->free_list = current_node;
+   for (i = 1; i < tst->node_line_width; i++)
+   {
+      current_node->middle = &(tst->node_lines->node_line[i]);
+      current_node = current_node->middle;
+   }
+   current_node->middle = NULL;
+   return 1;
+}
+
diff --git a/ext/http11/tst_init.c b/ext/http11/tst_init.c
new file mode 100644
index 0000000..259734a
--- /dev/null
+++ b/ext/http11/tst_init.c
@@ -0,0 +1,41 @@
+
+#include "tst.h"
+#include <stdio.h>
+#include <stdlib.h>
+
+struct tst *tst_init(int width)
+{
+   struct tst *tst;
+   struct node *current_node;
+   int i;
+
+
+if((tst = (struct tst *) calloc(1, sizeof(struct tst))) == NULL)
+   return NULL;
+
+if ((tst->node_lines = (struct node_lines *) calloc(1, sizeof(struct node_lines))) == NULL)
+{
+   free(tst);
+   return NULL;
+}
+
+tst->node_line_width = width;
+tst->node_lines->next = NULL;
+if ((tst->node_lines->node_line = (struct node *) calloc(width, sizeof(struct node))) == NULL)
+{
+   free(tst->node_lines);
+   free(tst);
+   return NULL;
+}
+
+current_node = tst->node_lines->node_line;
+tst->free_list = current_node;
+for (i = 1; i < width; i++)
+{
+   current_node->middle = &(tst->node_lines->node_line[i]);
+   current_node = current_node->middle;
+}
+current_node->middle = NULL;
+return tst;
+}
+
diff --git a/ext/http11/tst_insert.c b/ext/http11/tst_insert.c
new file mode 100644
index 0000000..0f83849
--- /dev/null
+++ b/ext/http11/tst_insert.c
@@ -0,0 +1,192 @@
+
+#include "tst.h"
+#include <stdio.h>
+#include <stdlib.h>
+
+
+int tst_grow_node_free_list(struct tst *tst);
+int tst_insert(unsigned char *key, void *data, struct tst *tst, int option, void **exist_ptr)
+{
+   struct node *current_node;
+   struct node *new_node_tree_begin = NULL;
+   int key_index;
+   int perform_loop = 1;
+
+   
+   if (key == NULL)
+      return TST_NULL_KEY;
+   
+   if(key[0] == 0)
+      return TST_NULL_KEY;
+   
+   if(tst->head[(int)key[0]] == NULL)
+   {
+      
+      if(tst->free_list == NULL)
+      {
+         if(tst_grow_node_free_list(tst) != 1)
+            return TST_ERROR;
+      }
+      tst->head[(int)key[0]] = tst->free_list;
+      
+      tst->free_list = tst->free_list->middle;
+      current_node = tst->head[(int)key[0]];
+      current_node->value = key[1];
+      if(key[1] == 0)
+      {
+         current_node->middle = data;
+         return TST_OK;
+      }
+      else
+         perform_loop = 0;
+   }
+   
+   current_node = tst->head[(int)key[0]];
+   key_index = 1;
+   while(perform_loop == 1)
+   {
+      if(key[key_index] == current_node->value)
+      {
+         
+         if(key[key_index] == 0)
+         {
+            if (option == TST_REPLACE)
+            {
+               if (exist_ptr != NULL)
+                  *exist_ptr = current_node->middle;
+         
+               current_node->middle = data;
+               return TST_OK;
+            }
+            else
+            {
+               if (exist_ptr != NULL)
+                  *exist_ptr = current_node->middle;
+               return TST_DUPLICATE_KEY;
+            }
+         }
+         else
+         {
+            if(current_node->middle == NULL)
+            {
+               
+               if(tst->free_list == NULL)
+               {
+                  if(tst_grow_node_free_list(tst) != 1)
+                     return TST_ERROR;
+               }
+               current_node->middle = tst->free_list;
+               
+               tst->free_list = tst->free_list->middle;
+               new_node_tree_begin = current_node;
+               current_node = current_node->middle;
+               current_node->value = key[key_index];
+               break;
+            }
+            else
+            {
+               current_node = current_node->middle;
+               key_index++;
+               continue;
+            }
+         }
+      }
+   
+      if( ((current_node->value == 0) && (key[key_index] < 64)) ||
+         ((current_node->value != 0) && (key[key_index] <
+         current_node->value)) )
+      {
+         
+         if (current_node->left == NULL)
+         {
+            
+            if(tst->free_list == NULL)
+            {
+               if(tst_grow_node_free_list(tst) != 1)
+                  return TST_ERROR;
+            }
+            current_node->left = tst->free_list;
+            
+            tst->free_list = tst->free_list->middle;
+            new_node_tree_begin = current_node;
+            current_node = current_node->left;
+            current_node->value = key[key_index];
+            if(key[key_index] == 0)
+            {
+               current_node->middle = data;
+               return TST_OK;
+            }
+            else
+               break;
+         }
+         else
+         {
+            current_node = current_node->left;
+            continue;
+         }
+      }
+      else
+      {
+         
+         if (current_node->right == NULL)
+         {
+            
+            if(tst->free_list == NULL)
+            {
+               if(tst_grow_node_free_list(tst) != 1)
+                  return TST_ERROR;
+            }
+            current_node->right = tst->free_list;
+            
+            tst->free_list = tst->free_list->middle;
+            new_node_tree_begin = current_node;
+            current_node = current_node->right;
+            current_node->value = key[key_index];
+            break;
+         }
+         else
+         {
+            current_node = current_node->right;
+            continue;
+         }
+      }
+   }
+   
+   do
+   {
+      key_index++;
+   
+      if(tst->free_list == NULL)
+      {
+         if(tst_grow_node_free_list(tst) != 1)
+         {
+            current_node = new_node_tree_begin->middle;
+   
+            while (current_node->middle != NULL)
+               current_node = current_node->middle;
+   
+            current_node->middle = tst->free_list;
+            tst->free_list = new_node_tree_begin->middle;
+            new_node_tree_begin->middle = NULL;
+   
+            return TST_ERROR;
+         }
+      }
+   
+      
+      if(tst->free_list == NULL)
+      {
+         if(tst_grow_node_free_list(tst) != 1)
+            return TST_ERROR;
+      }
+      current_node->middle = tst->free_list;
+      
+      tst->free_list = tst->free_list->middle;
+      current_node = current_node->middle;
+      current_node->value = key[key_index];
+   } while(key[key_index] !=0);
+   
+   current_node->middle = data;
+   return TST_OK;
+}
+
diff --git a/ext/http11/tst_search.c b/ext/http11/tst_search.c
new file mode 100644
index 0000000..efa1cfa
--- /dev/null
+++ b/ext/http11/tst_search.c
@@ -0,0 +1,54 @@
+
+#include "tst.h"
+#include <stdio.h>
+#include <stdlib.h>
+#include <assert.h>
+
+void *tst_search(unsigned char *key, struct tst *tst, int *prefix_len)
+{
+  struct node *current_node;
+  int key_index;
+  
+  assert(key != NULL && "key can't be NULL");
+  assert(tst != NULL && "tst can't be NULL");
+  
+  
+  if(key[0] == 0)
+    return NULL;
+  
+  if(tst->head[(int)key[0]] == NULL)
+    return NULL;
+  
+  current_node = tst->head[(int)key[0]];
+  key_index = 1;
+  
+  while (current_node != NULL)
+    {
+      if(key[key_index] == current_node->value)
+        {
+          if(current_node->value == 0) {
+            if(prefix_len) *prefix_len = key_index;
+            return current_node->middle;
+          } else {
+            current_node = current_node->middle;
+            key_index++;
+            continue;
+          }
+        }
+      else if( ((current_node->value == 0) && (key[key_index] < 64)) ||
+               ((current_node->value != 0) && (key[key_index] <
+                                               current_node->value)) )
+        {
+          current_node = current_node->left;
+          continue;
+        }
+      else
+        {
+          current_node = current_node->right;
+          continue;
+        }
+    }
+  
+  if(prefix_len) *prefix_len = key_index;
+  return NULL;
+}