diff options
author | evanweaver <evanweaver@19e92222-5c0b-0410-8929-a290d50e31e9> | 2007-10-26 02:59:15 +0000 |
---|---|---|
committer | evanweaver <evanweaver@19e92222-5c0b-0410-8929-a290d50e31e9> | 2007-10-26 02:59:15 +0000 |
commit | d4ff84b8d3afa45a69c23eb18899194bf7219140 (patch) | |
tree | 4a8e4b4e36ea36a8f543bfaaa2e6ec50fa1e94b6 /ext/http11/tst_search.c | |
parent | 4ff4a7d915f01dabcb87125aa89159fcc5d48534 (diff) | |
download | unicorn-d4ff84b8d3afa45a69c23eb18899194bf7219140.tar.gz |
git-svn-id: svn+ssh://rubyforge.org/var/svn/mongrel/trunk@741 19e92222-5c0b-0410-8929-a290d50e31e9
Diffstat (limited to 'ext/http11/tst_search.c')
-rw-r--r-- | ext/http11/tst_search.c | 73 |
1 files changed, 73 insertions, 0 deletions
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; + +} |