Re: [boost] [http] Design ideas for a request router

Subject: Re: [boost] [http] Design ideas for a request router
From: Uisleandro (uisleandro_at_[hidden])
Date: 2016-03-20 18:06:13

Hello everybody it is my first post here,

I am implementing a routing algorithm for boost, i intend to create a
"PATRICIA Tree", this is a reperesentation of the structure:

"/ip/%s/to_bin"N[1]

"/ip/%s/to_bin"N[10]                          --->
"/client/list"N[8]

"/ip/%s/to_bin"  ---> "/ip/%s/to_dec"                    "/client/list/%i"
-->  "/client/%i/select"N[11] --> "/client/%s/find" --> ... [ ]

                          "/client/%i/select" --> "/client/%d/update"

I believe that this algorithm has the following advantages:

1. Allocating and copying strings are not needed to create the structure
(because they are defined as "const char *");
2. Because of this algorithm it is possible to test each route from a
certain neighborhood without need to test all the routes, which means that
after the first character "/", in this case, if the current character is
'i', and it is accepted, there is not need of going to the "/client" side,
so the complexity of this algorithm is from the size of the key (in our
case an URL string), in comparison with a normal three algorithm, that
should be be "Log(N) * the_key_size", because the same key is tested
"Log(N)" times;
3. Seems it is possible to make some improvement, by ordering the
"neighbors": (at first it can be treated as a list, but some improvement
can be done here);
5. Once each character is verified separately it is possible to make some
"parsing" from the URL received from the user side (the URL searching
algorithm is actually a parsing);
4. This implementation considers "%i", "%d" and "%f" as the same, which
means that they will be placed in group,
but "%s" (which means an string before the character '/') or "%%" (which
means all the characters from the current position) are placed separately;
5. Seems it is possible to have a PATRICIA Tree "structure" completly made
of TMP because it don't need to split strings, but just mark the point
where some route is different from another (the problem maybe is splitting
a "node" vertically, which occurs when a node is "divided", or when the
tree grows);
6. The URL patterns "%d","%i","%f","%s","%%" are short;
7. The maximum routes per node is predefined, so, at least, in this point
of the code there is no dynamic allocation (no pointer to next).

This implementation is not complete, the class 'http_caller' is based on
CROW, and already has support to compile time type checking (that is also
my only concern about this, code because I'm somehow using their idea of
"numeric system", I've reading their code and understood how they did some
things, it is all commented in the source code). I'll be attempting to
integrate to the boost.http at the time I finish testing my code. Of course
you can choose never use it, but if you just consider I'll be very
satisfied.

My best regards,
Uisleandro Costa dos Santos

On Thu, Mar 17, 2016 at 2:00 PM, Sorin Fetche <sorin.fetche_at_[hidden]>
wrote:

> Hi all,
>
> On Sun, Mar 13, 2016 at 11:58 PM, Vinícius dos Santos Oliveira <> wrote:
>
> > The "tree style" is the style where you declare some paths to be handled
> > and each request will be routed to at most one handler. You'll find this
> > style usually when the author advertise a ReST support library
> > (e.g.crow[1]).
>
> This is also the style we used in an in house server side library
> meant to be used mainly for REST and WebSocket connections.
>
> The routing is inspired from Python Flask and Python aiohttp [1] with
> these features:
> - the routes can be added and removed at runtime (and from other route
> handlers)
> - we needed dynamic routes - moreover the dynamic part needed to match
> multiple path segments and more "specific" route handlers needed to
> take precedence over the more "generic" ones (example below)
> - support for asynchronous (deferred) route handlers - to support the
> cases when handling a request requires a lengthy operation.
> - full access to request / response objects to offload as much logic
> as possible from the core server library.
>
>
> Example of specific / generic route handlers:
> ("POST", "/api/v1/<device_id>/operation_a/") - handles some POST requests
> ("POST", "<url>/") - handles all the other POST requests regardless
> how many path segments (matches both "/a/" and "a/b/" and so on)
>
>
> [1] Python aiohttp: http://aiohttp.readthedocs.org/en/stable/web.html
>
>
> Best regards,
> Sorin Fetche
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>