Re: [PATCH 2] speedup for apr_table_t

2001-11-20 Thread dean gaudet
On Sun, 18 Nov 2001, Brian Pane wrote: > Good point--it's possible to construct an O(n^2) attack with this > patch. The same is true of qsort, which is O(n^2) in the worst > case, but it's admittedly a lot harder to construct the worst-case > data set with qsort. hmm yeah i guess that's true. >

Re: [PATCH 2] speedup for apr_table_t

2001-11-19 Thread Brian Pane
dean gaudet wrote: On Sat, 17 Nov 2001, Brian Pane wrote: * A rewrite of apr_table_overlap() that uses a hash table (sort of) instead of qsort i'm not sure this part of the patch is a good idea. the reason apr_table_overlap() uses qsort is to prevent various O(n^2) DoS attacks (both time &

Re: [PATCH 2] speedup for apr_table_t

2001-11-19 Thread dean gaudet
On Sat, 17 Nov 2001, Brian Pane wrote: * A rewrite of apr_table_overlap() that uses a hash table (sort of) instead of qsort i'm not sure this part of the patch is a good idea. the reason apr_table_overlap() uses qsort is to prevent various O(n^2) DoS attacks (both time & space). with your h

[PATCH 2] speedup for apr_table_t

2001-11-18 Thread Brian Pane
Attached is a new version of my table speedup patch. In this version, I added some additional optimizations to the table code: * A rewrite of apr_table_overlap() that uses a hash table (sort of) instead of qsort * Cliff's faster version of the prefix computation macro * apr_palloc instead of