[zeromq-dev] subtree matching with ztrie (#1073)

Kevin Sapper kevinsapper88 at gmail.com
Thu Sep 3 10:31:23 CEST 2015


I'm really sorry for the spam :( This stupid gmail client is killing me.

Hi Michael,

your use case is currently not possible with ztrie as it cannot handle
routes of variable length. The current implementation only compares token
which are on the same level in the tree and a regular expression can only
be used to match one token of the same level.

For example the route '/config/redis/{[^/]+}' matched against
'/config/redis/foo/bar/baz' will match

  config => config
  redis => redis
  [^/]+ => foo

and then abort with a mismatch as the inserted route does not contain one
more tokens.

However I think your use case is valid, but I like to make some limitations
to the star operator:

  -  If the star operator is used, no other route can have children with
the common prefix

    ztrie_insert_route ('/config/redis/*') => valid
    ztrie_insert_route ('/config/redis/foo') => invalid

  OR

    ztrie_insert_route ('/config/redis/foo') => valid
    ztrie_insert_route ('/config/redis/*') => invalid

//Kevin
P.S: Sorry again for the spamming.

2015-09-03 10:26 GMT+02:00 Kevin Sapper <kevinsapper88 at gmail.com>:

> Sorry I didn't mean to send the first message, somehow my gmail got crazy.
>
> Hi Michael,
>
> your use case is currently not possible with ztrie as it cannot handle
> routes of variable length. The current implementation only compares token
> which are on the same level in the tree and a regular expression can only
> be used to match one token of the same level.
>
> For example the route '/config/redis/{[^/]+}' matched against
> '/config/redis/foo/bar/baz' will match
>
>   config => config
>   redis => redis
>   [^/]+ => foo
>
> and then abort with a mismatch as the inserted route does not contain one
> more tokens.
>
> However I think your use case is valid, but I like to make some
> limitations to the star operator:
>
>   -  If the star operator is used, no other route can have children with
> the common prefix
>
>     ztrie_insert_route ('/config/redis/*') => valid
>     ztrie_insert_route ('/config/redis/foo') => invalid
>
>   OR
>
>     ztrie_insert_route ('/config/redis/foo') => valid
>
>
> 2015-09-03 10:22 GMT+02:00 Kevin Sapper <kevinsapper88 at gmail.com>:
>
>> Hi Michael,
>>
>> your use case is currently not possible with ztrie as it cannot handle
>> routes of variable length. The current implementation only compares token
>> which are on the same level in the tree and a regular expression can only
>> be used to match one token of the same level.
>>
>> For example the route '/config/redis/{[^/]+}' matched against
>> '/config/redis/foo/bar/baz' will match
>>
>>   config => config
>>   redis => redis
>>   [^/]+ => foo
>>
>> and then abort with a mismatch as the inserted route does not contain one
>> more tokens.
>>
>> However I think your use case is valid but I like to make some
>> limitations to the star operator:
>>
>>   -  If the star operator is used, no other route can have children with
>> the common prefix
>>     '/config/redis/*' (valid)
>>
>>
>>
>>
>> 2015-09-02 14:24 GMT+02:00 Michael Haberler <mail17 at mah.priv.at>:
>>
>>> I like the ztrie idea from #1073!  I'm considering this use case: *)
>>>
>>> server-side you'd insert routes like
>>>
>>>   /config/redis/*
>>>   /config/zconfig/*
>>>   /config/init/*
>>>
>>> and associate a match of /config/<method>/ with what is essentially a
>>> vtable which knows how to handle that subtree type
>>>
>>> client-side operations would be roughly so:
>>>
>>>   lookup(/config/redis/<some path of length > 0>)
>>>   set(/config/redis/<some path of length > 0>/<value>)
>>>   subscribe(/config/redis/<some path of length > 0>, change_callback)
>>>
>>> I guess what I need is a way to store the routes as above, plus a match
>>> method which would
>>>
>>> given say "/config/redis/foo/bar/baz" :
>>>
>>> - yield the data for /config/redis (i.e. the redis methods vtable)
>>> - plus "foo/bar/baz" (as string or in tokenized 'ztrie_hit_parameters)'
>>> form)
>>>
>>> how would I do that? I am unclear how to match a (possibly indefinite
>>> length) number of route elements.
>>>
>>> thanks!
>>>
>>> - Michael
>>>
>>>
>>> *) a zeromq-based networked configuration store "borrowing with pride"
>>> from  zookeeper/etcd/webdis/augeas/libelektra - a tree-structure key/value
>>> space (but a tad less filling than those examples)
>>>  with a 'mount some method into the tree at a given point' capability to
>>> integrate various configuration sources (some of them legacy like INI
>>> files, or redis, or zconfig - maybe based on plugins)
>>> _______________________________________________
>>> zeromq-dev mailing list
>>> zeromq-dev at lists.zeromq.org
>>> http://lists.zeromq.org/mailman/listinfo/zeromq-dev
>>>
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.zeromq.org/pipermail/zeromq-dev/attachments/20150903/2c1c5024/attachment.htm>


More information about the zeromq-dev mailing list