On Wed, Aug 21, 2019 at 9:49 PM Davidlohr Bueso <d...@stgolabs.net> wrote: > On Wed, 21 Aug 2019, Michel Lespinasse wrote: > >I'm not sure where to go with this - would it make sense to add a new > >interval tree header file that uses [start,end) intervals (with the > >thought of eventually converting all current interval tree users to it) > >instead of adding one more use of the less-natural [start,last] > >interval trees ? > > It might be the safest way, although I really hate having another > header file for interval_tree... The following is a diffstat of a > tentative conversion (I'll send the patch separately); I'm not sure > if a single shot conversion would be acceptable, albeit with relevant > maintainer acks.
That would make sense to me. Maybe doing it all in a single commit is too hard to review or bisect, but having a small series that duplicates the interval tree header at the start and removes the old (closed intervals) version at the end looks like it would work IMO. > >At first, I thought that you were handling that by removing 1 from the > >end of the interval, to adjust between the PAT and interval tree > >definitions. But, I don't see you doing that anywhere. > > This should have been my first approach. > > >Then, I thought that you were using [start, end( intervals everywhere, > >and the interval tree functions memtype_interval_iter_first and > >memtype_interval_iter_next would just return too many candidate > >matches as as you are passing "end" instead of "last" == end-1 as the > >interval endpoint, but then you would filter out the extra intervals > >using is_node_overlap(). But, if that is the case, then I don't > >understand why you need to redefine is_node_overlap() here. > > My original expectation was to actually remove a lot more of pat_rbtree, > including the is_node_overlap() and the filtering. Yes, I think this can > be done if the interval-tree is converted to [a,b[ and we can thus > just iterate the tree seamlessly. All right. So, my preference would be if we can use a version of interval trees that would work natively with half open intervals, as we discussed above. But, if that seems like too much change, I would also be ready to approve a version of pat_interval.c that would adjust the interval endpoint to compensate for the interval tree's use of closed intervals. I think either way, I can't approve the current version as it's too much of an in-between which makes it hard to follow IMO. > I think doing the conversion you suggested to [a,b[ for all users, then > redoing this series on top of that would be the way to move forward. That would be ideal; hopefully you don't see the vma_interval_tree thing as blocking this approach ? Thanks, -- Michel "Walken" Lespinasse A program is never fully debugged until the last user dies.
