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
