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.
>
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 &
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
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