httpd-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Brian Pane <bp...@pacbell.net>
Subject Fixing BrowserMatch: multi-string search algorithms?
Date Mon, 06 May 2002 01:39:50 GMT
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



Mime
View raw message