[Lldb-commits] [PATCH] D74759: Treat RangeDataVector as an augmented BST

unnar created this revision. unnar added reviewers: labath, teemperor. Herald added subscribers: lldb-commits, JDevlieghere. Herald added a project: LLDB. Since RangeDataVector is assumed to always be sorted we can treat it as an flattened BST and augment it with additional information about the

[Lldb-commits] [PATCH] D74759: Treat RangeDataVector as an augmented BST

jarin added a comment. Thanks for putting this together, some comments below. Let us see what Pavel thinks. Comment at: lldb/include/lldb/Utility/RangeMap.h:634 + // We can treat the vector as a flattened BST, augmenting it with upper bounds (max of + // range endpoints)

[Lldb-commits] [PATCH] D74759: Treat RangeDataVector as an augmented BST

labath added a comment. I like this idea a lot, in principle. It is much simpler than a full blown interval tree, and it should give us similar performance characteristics. Have you done a proper complexity analysis here? I doubt the `O(log n)` claim is true in general. It would have to be at l

[Lldb-commits] [PATCH] D74759: Treat RangeDataVector as an augmented BST

jarin added a comment. In D74759#1880499 , @labath wrote: > I like this idea a lot, in principle. It is much simpler than a full blown > interval tree, and it should give us similar performance characteristics. > > Have you done a proper complexity analys

[Lldb-commits] [PATCH] D74759: Treat RangeDataVector as an augmented BST

teemperor added a comment. If we get away with this approach them I'm completely fine with it. But I would feel better if we first have some more unit tests for RangeDataVector first. Repository: rLLDB LLDB CHANGES SINCE LAST ACTION https://reviews.llvm.org/D74759/new/ https://reviews.llv

[Lldb-commits] [PATCH] D74759: Treat RangeDataVector as an augmented BST

labath added a comment. In D74759#1880559 , @jarin wrote: > In D74759#1880499 , @labath wrote: > > > I like this idea a lot, in principle. It is much simpler than a full blown > > interval tree, and it should give

[Lldb-commits] [PATCH] D74759: Treat RangeDataVector as an augmented BST

unnar updated this revision to Diff 246679. unnar marked 5 inline comments as done. unnar added a comment. In D74759#1880499 , @labath wrote: > Have you done a proper complexity analysis here? I doubt the `O(log n)` claim > is true in general. It would ha

[Lldb-commits] [PATCH] D74759: Treat RangeDataVector as an augmented BST

unnar added inline comments. Comment at: lldb/include/lldb/Utility/RangeMap.h:642 + B ComputeUpperBounds(int lo, int hi) { +if (lo > hi) return B(); + jarin wrote: > Here, B() should be the min value of type B, no? Perhaps this should be > `std::numeric_lim

[Lldb-commits] [PATCH] D74759: Treat RangeDataVector as an augmented BST

unnar updated this revision to Diff 246681. unnar added a comment. Added reference to Wikipedia article. CHANGES SINCE LAST ACTION https://reviews.llvm.org/D74759/new/ https://reviews.llvm.org/D74759 Files: lldb/include/lldb/Utility/RangeMap.h lldb/unittests/Utility/RangeMapTest.cpp Ind

[Lldb-commits] [PATCH] D74759: Treat RangeDataVector as an augmented BST

labath added a comment. Thanks for adding the tests. They look good. Could you split them off into a separate patch? I believe @teemperor wanted (and I do agree it's a good idea) to check them in first in order to demonstrate that this patch does not change the behavior (or to make it what exac

[Lldb-commits] [PATCH] D74759: Treat RangeDataVector as an augmented BST

unnar updated this revision to Diff 246716. unnar marked 2 inline comments as done. CHANGES SINCE LAST ACTION https://reviews.llvm.org/D74759/new/ https://reviews.llvm.org/D74759 Files: lldb/include/lldb/Utility/RangeMap.h Index: lldb/include/lldb/Utility/RangeMap.h

[Lldb-commits] [PATCH] D74759: Treat RangeDataVector as an augmented BST

labath added a comment. In D74759#1893186 , @unnar wrote: > In D74759#1880499 , @labath wrote: > > > Have you done a proper complexity analysis here? I doubt the `O(log n)` > > claim is true in general. It would ha

[Lldb-commits] [PATCH] D74759: Treat RangeDataVector as an augmented BST

unnar added a comment. Sure, removed tests from this patch. They are now at D75180 Comment at: lldb/unittests/Utility/RangeMapTest.cpp:22 +const std::vector FindEntryIndexes(uint32_t address, + Ran

[Lldb-commits] [PATCH] D74759: Treat RangeDataVector as an augmented BST

unnar added a comment. In D74759#1893450 , @labath wrote: > In D74759#1893186 , @unnar wrote: > > > In D74759#1880499 , @labath wrote: > > > > > Have you done a proper comple

[Lldb-commits] [PATCH] D74759: Treat RangeDataVector as an augmented BST

labath added a comment. In D74759#1893485 , @unnar wrote: > That should work...although I'm not sure how that is any different to the > range or data being public. If a user modifies anything then it has > essentially invalidated the whole structure anyw

[Lldb-commits] [PATCH] D74759: Treat RangeDataVector as an augmented BST

unnar added a comment. In D74759#1895748 , @labath wrote: > In D74759#1893485 , @unnar wrote: > > > That should work...although I'm not sure how that is any different to the > > range or data being public. If a use

[Lldb-commits] [PATCH] D74759: Treat RangeDataVector as an augmented BST

labath added a comment. In D74759#1896100 , @unnar wrote: > In D74759#1895748 , @labath wrote: > > > That is a fair point. I suppose the reason why I see this as different is > > because this field is an implementa

[Lldb-commits] [PATCH] D74759: Treat RangeDataVector as an augmented BST

unnar updated this revision to Diff 247211. unnar marked 2 inline comments as done. unnar added a comment. As discussed with labath@ I made a separate struct called AugmentedEntry that is used internally but we only ever expose the Entry part to the user. CHANGES SINCE LAST ACTION https://rev

[Lldb-commits] [PATCH] D74759: Treat RangeDataVector as an augmented BST

labath added a comment. I think this is looking very good now. Just a few polishing comments. Comment at: lldb/include/lldb/Utility/RangeMap.h:604 +template +struct AugmentedRangeData : public RangeData { Add a short comment about the purpose of this class.

[Lldb-commits] [PATCH] D74759: Treat RangeDataVector as an augmented BST

unnar added a comment. Thanks for the feedback! I addressed all of your comments in the latest patch. CHANGES SINCE LAST ACTION https://reviews.llvm.org/D74759/new/ https://reviews.llvm.org/D74759 ___ lldb-commits mailing list lldb-commits@lists.

[Lldb-commits] [PATCH] D74759: Treat RangeDataVector as an augmented BST

unnar updated this revision to Diff 247597. unnar marked 3 inline comments as done. CHANGES SINCE LAST ACTION https://reviews.llvm.org/D74759/new/ https://reviews.llvm.org/D74759 Files: lldb/include/lldb/Utility/RangeMap.h Index: lldb/include/lldb/Utility/RangeMap.h

[Lldb-commits] [PATCH] D74759: Treat RangeDataVector as an augmented BST

labath accepted this revision. labath added a comment. This revision is now accepted and ready to land. Awesome. Thanks for the patch. Do you need me to commit this for you? CHANGES SINCE LAST ACTION https://reviews.llvm.org/D74759/new/ https://reviews.llvm.org/D74759 _

[Lldb-commits] [PATCH] D74759: Treat RangeDataVector as an augmented BST

unnar added a comment. Yes please. :) CHANGES SINCE LAST ACTION https://reviews.llvm.org/D74759/new/ https://reviews.llvm.org/D74759 ___ lldb-commits mailing list lldb-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-co

[Lldb-commits] [PATCH] D74759: Treat RangeDataVector as an augmented BST

This revision was automatically updated to reflect the committed changes. Closed by commit rG6304368818a1: [lldb] Treat RangeDataVector as an augmented binary search tree (authored by unnar, committed by labath). Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.l