Given a set of n BrowserMatch directives (as in, for example, the default config that we ship with httpd-2.0), mod_setenvif will do O(n) regex comparisons on every request.
I want to fix that. The best solution I've thought of so far is to fix the (very common) special case in which the BrowserMatch pattern doesn't really require a regex match. If we detect during config processing that agiven pattern only requires a simple substring match, then we can use a Boyer-Moore search instead of a regex search. That would speed things up, but the implementation would still take O(n) searches for n BrowserMatch directives. I'd really rather have a solution in which the request processing cost doesn't grow linearly with the number of config directives. Does anyone know of an efficient algorithm for comparing an input string against a set of multiple pattern strings? Thanks, --Brian
