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. > The most straightforward solution that I can think of is to > build a balanced tree, rather than a chained hash table, out > of the "overlap_key" nodes. I'll post a revised patch once > I get a tree implementation working. dude you're hard core. wouldn't a heap sort be better? it's guaranteed O(n lg n), but the constant factor tends to be 2x qsort's constant factor (which is why it's not generally used). however it needs less memory than a tree does. btw we might want to just continue with qsort or your hash or something for n less than some fixed constant -- and fall back to heap sort or a tree for large n. that way you get the perf benefit you desired with the DoS protection. -dean
