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

> Did a blog post explaining the $subject,
> http://www.dimuthu.org/blog/2008/11/21/apache-axis2c-restful-url-mapping-algorithm/
>
> Thanks
> Dimuthu
>
> On Thu, Nov 20, 2008 at 10:01 AM, Dimuthu Gamage <dimuthuc@...
> <mailto:dimuthuc@...>> 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
>
>
>
>
> --
> Thanks,
> Dimuthu Gamage
>
> http://www.dimuthu.org
> http://www.wso2.org