HomePhabricator

[lldb] Treat RangeDataVector as an augmented binary search tree

Authored by unnar on Mar 3 2020, 2:22 AM.

Description

[lldb] Treat RangeDataVector as an augmented binary search tree

Summary:
Since RangeDataVector is assumed to always be sorted we can treat it as
an flattened BST and augment it with additional information about the
ranges belonging to each "subtree". By storing the maximum endpoint in
every subtree we can query for intervals in O(log n) time.

Reviewers: labath, teemperor

Reviewed By: labath

Subscribers: jarin, JDevlieghere, lldb-commits

Tags: #lldb

Differential Revision: https://reviews.llvm.org/D74759

Details

Committed
labathMar 3 2020, 2:28 AM
Reviewer
labath
Differential Revision
D74759: Treat RangeDataVector as an augmented BST
Parents
rG93c73d4834a9: Revert "Reland "[gn build] (manually) merge 68a235d07f9e70""
Branches
Unknown
Tags
Unknown