Closed Bug 1468984 Opened Last year Closed Last year

SplayTree::checkCoherency is using a recursive algorithm.

Categories

(Core :: JavaScript Engine, defect)

defect
Not set

Tracking

()

RESOLVED FIXED
mozilla62
Tracking Status
firefox62 --- fixed

People

(Reporter: nbp, Assigned: nbp)

References

Details

Attachments

(1 file)

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.
Attachment #8985645 - Flags: review?(tcampbell)
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 :)
Attachment #8985645 - Flags: review?(tcampbell) → review+
Pushed by npierron@mozilla.com:
https://hg.mozilla.org/integration/mozilla-inbound/rev/890d7af2b79c
Convert SplayTree::checkCoherency to a non-recursive algorithm. r=tcampbell
https://hg.mozilla.org/mozilla-central/rev/890d7af2b79c
Status: NEW → RESOLVED
Closed: Last year
Resolution: --- → FIXED
Target Milestone: --- → mozilla62
Assignee: nobody → nicolas.b.pierron
You need to log in before you can comment on or make changes to this bug.