Hi Dimuthu,
Yes the blog post explain it very well. I could not understand it by
looking at your previous mail or by looking at the code.
Is there a way we can avoid recursion?
thanks
Damitha
Dimuthu Gamage wrote:
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 <[EMAIL PROTECTED]
<mailto:[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
--
Thanks,
Dimuthu Gamage
http://www.dimuthu.org
http://www.wso2.org
--
__________________________________________________________________
Damitha Kumarage
http://people.apache.org/
__________________________________________________________________
---------------------------------------------------------------------
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
