Re: REST URL Mapping - The changes done in pattern matching Algorithm

> 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
>