Hi Thiago, Yes, recursive should anyway cause problems with small stacks. But I think we can safely assume the number of url component will not exceed 4/5 times. If the call stack is still smaller than that number, the code will fail.
On Thu, Nov 20, 2008 at 3:40 PM, Thiago Rafael Becker < [EMAIL PROTECTED]> wrote: > The only thing that worries me is the recursion. Suppose that I have a > small stack (which is common on embedded systems), and a long chain of > possibilities to a single pattern or even several patterns (which may > be common). Can this overflow the application stack? Can these > functions be implemented with iterative functions instead? We can iteratively implement that with a manual hash which simulate the recursive call stack. So we can traverse a branch of the tree and return to the root and traverse the other branches if the first branch is not successful. I will check the possibility of such an algorithm. > > > I was thinking about using dynamic hash tables for this. Do you think > this can lead to more improvement in the performance? The hash we uses is already a dynamic one. Anyway we have to go out from the hash and do linear searches, if the url contains params (since we have to do simple pattern matching). Where do you think, you can place dynamic hash? Thanks Dimuthu > > > On Thu, Nov 20, 2008 at 2:31 AM, Dimuthu Gamage <[EMAIL PROTECTED]> > wrote: > > Hi devs, > > > > As you may have already noticed, I changed the REST URL pattern matching > > algorithm while fixing the > > https://issues.apache.org/jira/browse/AXIS2C-1290 issue and the WSF/PHP > > issue, https://wso2.org/jira/browse/WSFPHP-347. Since Apache's principle > is > > to 'Commit first' I committed the code first (after making sure > everything > > works), decided to start a discussion on that :) > > > > Basically What I have done is changing the code > > 1. Initializing the REST Mapping per operation - > > axis2_svc_get_rest_op_list_with_method_and_location ( in > > src/core/description/svc.c) > > 2. REST dispaching algorithm to find the operation and the matching > > patterns - axis2_rest_disp_find_op (in src/core/engine/rest_disp.c ) > > > > At the initializing face It store the url pattern in a internal recursive > > structure call 'axutil_core_utils_map_internal_t' whcih is only used > inside > > the core_utils.c function. And it store this structure for each operation > in > > the svc->op_rest_map hash. Here is the structure of the struct. > > > > /* internal structure to keep the rest map in a multi level hash */ > > typedef struct { > > /* the structure will keep as many as following fields */ > > > > /* if the mapped value is directly the operation */ > > axis2_op_t *op_desc; > > > > /* if the mapped value is a constant, this keeps a hash map of > > possible constants => corrosponding map_internal structure */ > > axutil_hash_t *consts_map; > > > > /* if the mapped value is a param, this keeps a hash map of > > possible param_values => corrosponding_map_internal structre */ > > axutil_hash_t *params_map; > > > > } axutil_core_utils_map_internal_t; > > > > For an example think you have operations with following REST mapping > (Using > > the example attached in the > > https://issues.apache.org/jira/browse/AXIS2C-1290 and > > http://www.dimuthu.org/blog/2008/10/18/write-restful-services-in-c/ ) > > > > GET students > > GET students/{stduent_id} > > GET students/{student_id}/marks/{subject_id} > > > > Then thes svc->op_rest_map will be like > > > > <pre> > > svc->op_rest_map (hash) > > | > > "GET:students" --------- axutil_core_utils_map_internal_t > > (instance) > > | > > op_desc > (axis2_op_t* > > for "GET students" op) > > | > > consts_map (empty > > hash) > > | > > params_map (hash) > > > | > > > > "{student_id}" ------------- axutil_core_utils_map_internal_t (instance) > > > > | > > > > op_desc (axis2_op_t* for "GET students/{student_id}" > op) > > > > | > > > > parms_map (empty hash) > > > > | > > > > const_map (hash) > > > > | > > > > "marks" ------------------- > > axutil_core_utils_map_internal_t (instance) > > > > | > > > > op_desc (NULL) > > > > | > > > > consts_map (empty > > hash) > > > > | > > > > params_map (hash) > > > > > | > > > > > "{subject_id}" > > ----------- axutil_core_utils_map_internal_t (instance) > > > > > > | > > > > op_desc > (axis2_op_t* > > for "GET students/{student_id}/marks/{subject_id}" op) > > > > | > > > > consts_map / params_map (Both NULL) > > > > </pre> > > > > So at the Dispatching URL we can clearly sort out the operation and the > > parameter values. > > > > For matching patterns like {student_id}, {subject_id} and more complex > > matching like xx{p}yy{q}zz{r} the logic uses the function > > axis2_core_utils_match_url_component_with_pattern ( in > > src/core/util/core_utils.c) > > This is O(n^2) order (in worse case) algorithm. > > > > And what I want to discuss is the point whether the above described logic > is > > better than the early logic which sequentilly checks all the mapping. > > > > Calculating the approximate time complexity takng n =numbe of operations, > p > > = average URL mapping length > > The early logic = n/2 (<--go through all the operation in average) * > > O(p^2) (<--the complexity of > > axis2_core_utils_match_url_component_with_pattern) =>O (n*p^2) > > > > For the second logic it is really complex to do a methematical analysis > of > > the tiime complexity. Assuming (being optimistic:) average length of the > url > > component is d (d <= p) and the average parameters in a url is k (k > <=p/d) > > and taking hash search is O(1) > > > > The new logic = log(n) (<-- long n number of hash search) *(k*O(d^2)) > (<-- > > assuming k parameters have to execute the function > > axis2_core_utils_match_url_component_with_pattern) => O(logn * k* d^2) > > > > Clearly O(logn *k *d ^2) < O(n*p^2) (taking logn < n and d <=p and k > > <=p/d) > > > > Anyway the new logic contain some recursive functions and hash functions > > heavily which may slow down things at little n (number of operations), > > littld k (little number of url components) and little d (small length > urls). > > > > So my question is do we need to favor on the smal number of operation so > go > > back to old logic(after correcting bugs) or do we stay with the current > > logic?. Your opinions? > > > > > > > > -- > > Thanks, > > Dimuthu Gamage > > > > http://www.dimuthu.org > > http://www.wso2.org > > > > --------------------------------------------------------------------- > To unsubscribe, e-mail: [EMAIL PROTECTED] > For additional commands, e-mail: [EMAIL PROTECTED] > > -- Thanks, Dimuthu Gamage http://www.dimuthu.org http://www.wso2.org
