[
https://issues.apache.org/jira/browse/DISPATCH-1682?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17130728#comment-17130728
]
ASF subversion and git services commented on DISPATCH-1682:
-----------------------------------------------------------
Commit 0853244e59aa2f71a9cba0a171701c2b04c28bb1 in qpid-dispatch's branch
refs/heads/master from Ken Giusti
[ https://gitbox.apache.org/repos/asf?p=qpid-dispatch.git;h=0853244 ]
DISPATCH-1682: Augment parse tree with hash table lookup
This closes #755
> Optimize the parse tree match algorithm to avoid O(N) lookup
> ------------------------------------------------------------
>
> Key: DISPATCH-1682
> URL: https://issues.apache.org/jira/browse/DISPATCH-1682
> Project: Qpid Dispatch
> Issue Type: Bug
> Components: Routing Engine
> Affects Versions: 1.12.0
> Reporter: Ken Giusti
> Assignee: Ken Giusti
> Priority: Major
> Fix For: Backlog
>
>
> The parse tree pattern match algorithm is optimized to search using a key
> that is made up of a sequence of tokens.
> If all keys inserted into the parse tree are only single tokens then the
> lookup degrades into a linear list search.
> The treatment for every address is looked up in the parse tree. If the
> address is not found the default treatment is used. Lookups that miss end up
> performing O(N) searches.
> The match algorithm should be re-designed to avoid O(N) searches for single
> token patterns.
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@qpid.apache.org
For additional commands, e-mail: dev-h...@qpid.apache.org
