reverts for 1.0.2

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

8 files changed, 773 insertions, 0 deletions

diff --git a/ext/http11/http11.c b/ext/http11/http11.c
index 7a84db8..2c6e119 100644
--- a/ext/http11/http11.c
+++ b/ext/http11/http11.c
@@ -8,9 +8,11 @@
 #include <string.h>
 #include "http11_parser.h"
 #include <ctype.h>
+#include "tst.h"
 
 static VALUE mMongrel;
 static VALUE cHttpParser;
+static VALUE cURIClassifier;
 static VALUE eHttpParserError;
 
 #define id_handler_map rb_intern("@handler_map")
@@ -361,6 +363,191 @@ VALUE HttpParser_nread(VALUE self)
   return INT2FIX(http->nread);
 }
 
+
+void URIClassifier_free(void *data) 
+{
+  TRACE();
+
+  if(data) {
+    tst_cleanup((struct tst *)data);
+  }
+}
+
+
+
+VALUE URIClassifier_alloc(VALUE klass)
+{
+  VALUE obj;
+  struct tst *tst = tst_init(TRIE_INCREASE);
+  TRACE();
+  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.
+ *
+ */
+VALUE URIClassifier_init(VALUE self)
+{
+  VALUE hash;
+
+  /* we create an internal hash to protect stuff from the GC */
+  hash = rb_hash_new();
+  rb_ivar_set(self, id_handler_map, hash);
+
+  return self;
+}
+
+
+/**
+ * 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 called with "/someuri/iwant" it'll also
+ * return SomeHandler immediatly, with no additional searches, but it will
+ * return path info with "/iwant".
+ *
+ * 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_ivar_get(self, id_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_ivar_get(self, id_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
+ *    uc.resolve("/") -> "/", "/", handler  # if uc.register("/", handler)
+ *    uc.resolve("/path/from/root") -> "/", "/path/from/root", handler  # if uc.register("/", handler) 
+ * 
+ * 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).  If it doesn't find a handler registered at the longest
+ * match then it returns nil,nil,nil.
+ *
+ * Because the resolver uses a trie you are able to register a handler at *any* character
+ * in the URI and it will be handled as long as it's the longest prefix.  So, if you 
+ * registered handler #1 at "/something/lik", and #2 at "/something/like/that", then a
+ * a search for "/something/like" would give you #1.  A search for "/something/like/that/too"
+ * would give you #2.
+ * 
+ * This is very powerful since it means you can also attach handlers to parts of the ; 
+ * (semi-colon) separated path params, any part of the path, use off chars, anything really.
+ * It also means that it's very efficient to do this only taking as long as the URI has
+ * characters.
+ *
+ * A slight modification to the CGI 1.2 standard is given for handlers registered to "/".
+ * CGI expects all CGI scripts to be at some script path, so it doesn't really say anything
+ * about a script that handles the root.  To make this work, the resolver will detect that
+ * the requested handler is at "/", and return that for script_name, and then simply return
+ * the full URI back as path_info.
+ *
+ * It expects strings with no embedded '\0' characters.  Don't try other string-like stuff yet.
+ */
+VALUE URIClassifier_resolve(VALUE self, VALUE uri)
+{
+  void *handler = NULL;
+  int pref_len = 0;
+  struct tst *tst = NULL;
+  VALUE result;
+  unsigned char *uri_str = NULL;
+
+  DATA_GET(self, struct tst, tst);
+  uri_str = (unsigned char *)StringValueCStr(uri);
+
+  handler = tst_search(uri_str, tst, TST_LONGEST_MATCH, &pref_len);
+
+  /* setup for multiple return values */
+  result = rb_ary_new();
+
+  if(handler) {
+    rb_ary_push(result, rb_str_substr (uri, 0, pref_len));
+    /* compensate for a script_name="/" where we need to add the "/" to path_info to keep it consistent */
+    if(pref_len == 1 && uri_str[0] == '/') {
+      /* matches the root URI so we have to use the whole URI as the path_info */
+      rb_ary_push(result, uri);
+    } else {
+      /* matches a script so process like normal */
+      rb_ary_push(result, rb_str_substr(uri, pref_len, RSTRING(uri)->len));
+    }
+
+    rb_ary_push(result, (VALUE)handler);
+  } else {
+    /* not found so push back nothing */
+    rb_ary_push(result, Qnil);
+    rb_ary_push(result, Qnil);
+    rb_ary_push(result, Qnil);
+  }
+
+  return result;
+}
+
+
 void Init_http11()
 {
 
@@ -399,4 +586,11 @@ void Init_http11()
   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/tst.h b/ext/http11/tst.h
new file mode 100644
index 0000000..3a58a65
--- /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, TST_LONGEST_MATCH
+};
+
+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(const unsigned char *key, struct tst *tst, int option, unsigned int *match_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..a85491d
--- /dev/null
+++ b/ext/http11/tst_cleanup.c
@@ -0,0 +1,23 @@
+
+#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..de50f4a
--- /dev/null
+++ b/ext/http11/tst_insert.c
@@ -0,0 +1,218 @@
+
+#include "tst.h"
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.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;
+   struct node *new_node;
+   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(key[key_index] == 0)
+      {
+               if(tst->free_list == NULL)
+         {
+             if(tst_grow_node_free_list(tst) != 1)
+                 return TST_ERROR;
+         }
+         new_node = tst->free_list;
+         tst->free_list = tst->free_list->middle;
+
+         memcpy((void*)new_node, (void*)current_node, sizeof(struct node));
+         current_node->value = 0;
+         if(new_node->value < 64)
+         {
+            current_node->left = new_node;
+            current_node->right = '\0';
+         }
+         else
+         {
+            current_node->left = '\0';
+            current_node->right = new_node;
+         }
+
+         current_node->middle = data;
+         return TST_OK;
+      }
+
+      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..176f953
--- /dev/null
+++ b/ext/http11/tst_search.c
@@ -0,0 +1,73 @@
+
+#include "tst.h"
+#include <stdio.h>
+#include <stdlib.h>
+#include <assert.h>
+
+
+void *tst_search(const unsigned char *key, struct tst *tst, int option,
+                 unsigned int *match_len)
+{
+    struct node *current_node;
+    struct node *longest_match = NULL;
+    unsigned int longest_match_len = 0;
+    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;
+
+    if (match_len)
+        *match_len = 0;
+
+    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 (match_len)
+                    *match_len = key_index;
+                return current_node->middle;
+            } else {
+                current_node = current_node->middle;
+                key_index++;
+                continue;
+            }
+        } else {
+            if (current_node->value == 0) {
+                if (option & TST_LONGEST_MATCH) {
+                    longest_match = current_node->middle;
+                    longest_match_len = key_index;
+                }
+
+                if (key[key_index] < 64) {
+                    current_node = current_node->left;
+                    continue;
+                } else {
+                    current_node = current_node->right;
+                    continue;
+                }
+            } else {
+                if (key[key_index] < current_node->value) {
+                    current_node = current_node->left;
+                    continue;
+                } else {
+                    current_node = current_node->right;
+                    continue;
+                }
+            }
+        }
+    }
+
+    if (match_len)
+        *match_len = longest_match_len;
+
+    return longest_match;
+
+}