> From: Valdis.Kletnieksat_private [mailto:Valdis.Kletnieksat_private] > Sent: Friday, November 22, 2002 9:35 AM > On the other hand, the Unix libc usually contains the qsort() and ftw() > routines, which might be interesting. qsort() is sometimes implemented iteratively rather than recursively. (For that matter, it can be implemented with any sorting algorithm that preserves the semantics in the standard - it needn't be Quicksort.) Hoare, in his Turing Award speech, said that his original Quicksort design (it's not clear he ever implemented it this way) was iterative, not recursive. Since qsort() uses a size_t for the number of elements, and the implementation decides how large a size_t is, the implementation also knows how deep the qsort() stack can get (log-2 of the maximum value of a size_t, if memory serves), so it can use a manual fixed-size stack and iterate. Regardless of qsort() implementation, though, I agree that recursion overflow doesn't look like a very promising area for vulnerability research. Michael Wojcik Principal Software Systems Developer, Micro Focus
This archive was generated by hypermail 2b30 : Mon Nov 25 2002 - 10:27:50 PST