httpd-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Cliff Woolley <jwool...@virginia.edu>
Subject RE: mod_usertrack bugfix patch
Date Tue, 25 Feb 2003 22:44:27 GMT
On Tue, 25 Feb 2003, Manni Wood wrote:

> Interesting you should mention this. An older version of the patch I
> wrote (I've been working on the problem off an on for over a year) did
> what you said: loop over the delimiters and parse each name=value pair
> into an apache table. Then, I asked the apache table if the cookie was
> present. (These older patches are linked to from
> http://manniwood.net/mod_usertrack_patch.html, at the bottom of the
> page.)

Yes, I saw that on your page.  (Good work on that, by the way.  I agree
with Jeff that it's a great resource.)  But even the expense of creating a
table is unneeded.

If you put all the values into a table and look the one you want up
afterward and then throw the whole table away, that's a lot of unneeded
expense.  Building a table means building a red/black tree and all kinds
of goo that we don't need for a simple matching process.  This runs in
something like O(nlogn) time with a high constant coefficient where
n==strlen() (I'd have to go reread apr_tables.c to be sure about the exact
time complexity).

If the current cookie isn't the one you want, strcmp()  will tell you
that.  As soon as you find the one you want, you're done.  Move on to the
next one and try it.  And actually, you can do even better than
strcmp()... just use a loop that does the comparisons a character at a
time so you don't have to ever examine any character more than once.
It's a simple little state machine.  In essence, comparing against the
regex is doing the same thing, but since it's simple the readability won't
be bad, and you can get better performance out of it than calling into a
regex engine would give you.  This method will in straight-up O(n) time.

--Cliff


Mime
View raw message