[DISPATCH-1682] Optimize the parse tree match algorithm to avoid O(N) lookup

• Type: Bug
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Affects Version/s: 1.12.0
• Fix Version/s: 1.13.0
• Component/s: Routing Engine
• Assignee: Ken Giusti
• Reporter: Ken Giusti
• Created: 01/Jun/20 19:55
• Updated: 18/Aug/20 01:01
• Resolved: 11/Jun/20 12:34

Description

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.