[lldb] Treat RangeDataVector as an augmented binary search tree
authorUnnar Freyr Erlendsson <unnar@google.com>
Tue, 3 Mar 2020 10:22:33 +0000 (11:22 +0100)
committerPavel Labath <pavel@labath.sk>
Tue, 3 Mar 2020 10:28:16 +0000 (11:28 +0100)
commit6304368818a1e9883b694b9d8c21ef568176168d
treee19b99aa55bf45731d8e2e8545a9ba0cfcd79a99
parent93c73d4834a96ac749dabb624e07f9a146186875
[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
lldb/include/lldb/Utility/RangeMap.h