Now, within the bowels of Asterisk, each channel records the context name, the extension name, and the priority number of the next priority to execute. The first thing Asterisk does is lookup the context, then looks up the extension in that context, and then searches for the priority number to execute. These three lookups get done for every line of code. Why? Millions of reasons: with goto's, etc, the context/exten/priority is just plugged into the channel, and the engine will then fetch that. Saving these refs by name makes it so the dialplan can be reloaded mid-stream, and for the most part survive without a hitch.

The important thing to remember is that all 3 of these objects are stored in linear linked lists.

Now, the fun part. The lookups for the extensions and priorities get done quite often. So, I did studies of the 3 individual lookups that are done to find an arbitrary priority to execute. I am currently using threaded red-black binary trees instead of the simple linked-lists for contexts and priorities. It's not LGPL code, so I can't use them in asterisk, but until I get LGPL'd code, or our own hashtabs, I'm using them for an experiment.

The extension patterns are matched in a linear fashion, with no early cutoffs; that last extension in the list might yield the best match. To speed this up, I take a different route. I take the first character of each pattern, and I form a tree, where each level down is another, subsequent character set from the patterns. Patterns that start with similar character sequences share a path down the tree. The maximum depth of the tree coincides with the longest pattern in the set. To match, I follow a path down thru the tree until the final leaf is reached. It is possible that one sequence of characters can match more than one path down the tree. In this case, all possible paths are followed, and the metrics followed along the way determine the 'best' match. This algorithm is fairly simple, and much faster-- when you have a lot of patterns. Let's see, it's about O(5*(averagePatternLength)). You form this tree after the context is created and populated. It is stored in the ast_context structure.

Threaded red-black binary trees are a cousin of the AVL trees, binary trees that implement algorithms to keep them optimally balanced at all times. They have log(n) search times, which is pretty good compared to linked lists, which will have n/2 search times, where n is the number of items in the structure. So, if your set has 1000 items, a linear search will find the result, by looking at 500 items, on the average. With RB trees, you'd look thru at less than 9 or 10 items on the average. Much nicer!