SplayTree::checkCoherency can cause stack overflows in degenerated cases which are causing large unbalanced trees.

This patch converts the recursive decent in the splay tree into a depth-first traversal of the tree. Using a depth-first search ensures that we are going to visit the elements of the splay tree in increasing order, thus updating the minimum at every node which is visited in the depth-first search. The depth-first traversal is using the parent link instead of allocating memory to recall the last choice point. It works as follow: - Find the left-most element, and visit it. If there is a right branch on the left-most node, go down, and resume finding the left-most node by re-looping. OTherwise, we reached a leaf node (left-most node with no right branch). - When reaching a leaf node, walk all the nodes until we reach a right branch which we did not visit yet, and visit parent nodes if we are coming back from a left-branch decent. Right branches which were not visited are cases when we are coming back the left branch and a right branch exists.

Comment on attachment 8985645 [details] [diff] [review] Convert SplayTree::checkCoherency to a non-recursive algorithm. Review of attachment 8985645 [details] [diff] [review]: ----------------------------------------------------------------- Great. Comments are pretty clear :)

Pushed by npierron@mozilla.com: https://hg.mozilla.org/integration/mozilla-inbound/rev/890d7af2b79c Convert SplayTree::checkCoherency to a non-recursive algorithm. r=tcampbell