Hi, On Thu, Nov 20, 2008 at 2:51 PM, Dimuthu Gamage <[EMAIL PROTECTED]> wrote: > 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.
Ok. I'll take a look at my work here to see if I'll hit some limit where I can have this problem. If so, I'll have to fix it ;) Thanks. > 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'll take a closer look at the code to maybe suggest something. > 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? Looking at it too. > 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 > -- Thiago Rafael Becker http://www.monstros.org/trbecker --------------------------------------------------------------------- To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
