From 706aef01fbbcee885fcb6d76228f669d48d16f25 Mon Sep 17 00:00:00 2001 From: filipe Date: Thu, 13 Sep 2007 04:12:01 +0000 Subject: After some discussion with tst upstream author (Peter A friend), he changed the tst library to meet mongrel needs, and he also close the bug upstream :D So we are in sync with his source code and bug 10279 is closed with this commit. git-svn-id: svn+ssh://rubyforge.org/var/svn/mongrel/trunk@586 19e92222-5c0b-0410-8929-a290d50e31e9 --- ext/http11/http11.c | 2 +- ext/http11/tst.h | 4 +- ext/http11/tst_cleanup.c | 1 - ext/http11/tst_insert.c | 32 +++++++++++-- ext/http11/tst_search.c | 115 ++++++++++++++++++++++++----------------------- 5 files changed, 92 insertions(+), 62 deletions(-) (limited to 'ext') diff --git a/ext/http11/http11.c b/ext/http11/http11.c index a201e0e..23df7d6 100644 --- a/ext/http11/http11.c +++ b/ext/http11/http11.c @@ -506,7 +506,7 @@ VALUE URIClassifier_resolve(VALUE self, VALUE uri) DATA_GET(self, struct tst, tst); uri_str = (unsigned char *)StringValueCStr(uri); - handler = tst_search(uri_str, tst, &pref_len); + handler = tst_search(uri_str, tst, TST_LONGEST_MATCH, &pref_len); /* setup for multiple return values */ result = rb_ary_new(); diff --git a/ext/http11/tst.h b/ext/http11/tst.h index 8e5ab2c..3a58a65 100644 --- a/ext/http11/tst.h +++ b/ext/http11/tst.h @@ -24,14 +24,14 @@ struct node_lines enum tst_constants { - TST_OK, TST_ERROR, TST_NULL_KEY, TST_DUPLICATE_KEY, TST_REPLACE + 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(unsigned char *key, struct tst *tst, int *prefix_len); +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); diff --git a/ext/http11/tst_cleanup.c b/ext/http11/tst_cleanup.c index b574f9f..a85491d 100644 --- a/ext/http11/tst_cleanup.c +++ b/ext/http11/tst_cleanup.c @@ -21,4 +21,3 @@ void tst_cleanup(struct tst *tst) free(tst); } - diff --git a/ext/http11/tst_insert.c b/ext/http11/tst_insert.c index 0f83849..de50f4a 100644 --- a/ext/http11/tst_insert.c +++ b/ext/http11/tst_insert.c @@ -2,16 +2,16 @@ #include "tst.h" #include #include - +#include 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; @@ -91,7 +91,33 @@ int tst_insert(unsigned char *key, void *data, struct tst *tst, int option, void } } } - + 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)) ) diff --git a/ext/http11/tst_search.c b/ext/http11/tst_search.c index 44aee7a..176f953 100644 --- a/ext/http11/tst_search.c +++ b/ext/http11/tst_search.c @@ -4,65 +4,70 @@ #include #include -void *tst_search(unsigned char *key, struct tst *tst, int *prefix_len) + +void *tst_search(const unsigned char *key, struct tst *tst, int option, + unsigned int *match_len) { - struct node *current_node; - void *longest_match = NULL; - 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; + 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; - - if(prefix_len) *prefix_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(prefix_len) *prefix_len = key_index; - return current_node->middle; - } else { - current_node = current_node->middle; - if(current_node && current_node->value == 0) { - if(prefix_len) *prefix_len = key_index+1; - longest_match = current_node->middle; + 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; + } - key_index++; - continue; - } - } - else if( ((current_node->value == 0) && (key[key_index] < 64)) || - ((current_node->value != 0) && (key[key_index] < - current_node->value)) ) - { - if(current_node->value == 0) { - if(prefix_len) *prefix_len = key_index; - longest_match = current_node->middle; - } - current_node = current_node->left; - continue; - } - else - { - if(current_node->value == 0) { - if(prefix_len) *prefix_len = key_index; - longest_match = current_node->middle; - } - current_node = current_node->right; - continue; + 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; + } + } } } - - return longest_match; + + if (match_len) + *match_len = longest_match_len; + + return longest_match; + } -- cgit v1.2.3-24-ge0c7