[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Qemu-devel] [PATCH 07/10] util: implement simple interval tree logi
From: |
Peter Xu |
Subject: |
Re: [Qemu-devel] [PATCH 07/10] util: implement simple interval tree logic |
Date: |
Fri, 27 Apr 2018 14:27:44 +0800 |
User-agent: |
Mutt/1.9.1 (2017-09-22) |
On Fri, Apr 27, 2018 at 01:53:35PM +0800, Jason Wang wrote:
[...]
> > + /* Merge right adjacent range */
> > + overlap = it_tree_find_value(tree, end + 1);
> > + if (overlap) {
> > + range->end = overlap->end;
> > + g_tree_remove(gtree, overlap);
> > + }
> > +
> > + /* Key and value are sharing the same range data */
> > + it_tree_insert_internal(gtree, range);
>
> A small optimization here is to delay the allocation until you're sure
> there's not overlapping.
Yes I can.
[...]
> > +int it_tree_remove(ITTree *tree, ITValue start, ITValue end)
> > +{
> > + ITRange range = { .start = start, .end = end }, *overlap, and;
> > + GTree *gtree;
> > +
> > + g_assert(tree);
> > +
> > + gtree = tree->tree;
> > + while ((overlap = g_tree_lookup(gtree, &range))) {
> > + if (it_range_equal(overlap, &range)) {
> > + /* Exactly what we want to remove; done */
> > + g_tree_remove(gtree, overlap);
> > + break;
> > + } else if (it_range_cover(overlap, &range)) {
> > + /* Split existing range into two; done */
> > + it_tree_remove_subset(gtree, overlap, &range);
> > + break;
> > + } else if (it_range_cover(&range, overlap)) {
> > + /* Drop this range and continue */
> > + g_tree_remove(gtree, overlap);
> > + } else {
> > + /*
> > + * The range to remove has intersection with existing
> > + * ranges. Remove part of the range and continue
> > + */
> > + it_range_and(&and, overlap, &range);
> > + g_assert(and.start <= and.end);
> > + it_tree_remove_subset(gtree, overlap, &and);
> > + }
> > + }
> > +
>
> Looks like what we need here is just calculate the intersection part the
> remove it.
Yes. Will fix that. Thanks,
--
Peter Xu
- Re: [Qemu-devel] [PATCH 03/10] intel-iommu: add iommu lock, (continued)
- Re: [Qemu-devel] [PATCH 03/10] intel-iommu: add iommu lock, Peter Xu, 2018/04/27
- Re: [Qemu-devel] [PATCH 03/10] intel-iommu: add iommu lock, Tian, Kevin, 2018/04/27
- Re: [Qemu-devel] [PATCH 03/10] intel-iommu: add iommu lock, Peter Xu, 2018/04/27
- Re: [Qemu-devel] [PATCH 03/10] intel-iommu: add iommu lock, Tian, Kevin, 2018/04/27
- Re: [Qemu-devel] [PATCH 03/10] intel-iommu: add iommu lock, Jason Wang, 2018/04/27
[Qemu-devel] [PATCH 05/10] intel-iommu: introduce vtd_page_walk_info, Peter Xu, 2018/04/25
[Qemu-devel] [PATCH 06/10] intel-iommu: pass in address space when page walk, Peter Xu, 2018/04/25
[Qemu-devel] [PATCH 04/10] intel-iommu: only do page walk for MAP notifiers, Peter Xu, 2018/04/25
[Qemu-devel] [PATCH 07/10] util: implement simple interval tree logic, Peter Xu, 2018/04/25
[Qemu-devel] [PATCH 08/10] intel-iommu: maintain per-device iova ranges, Peter Xu, 2018/04/25
- Re: [Qemu-devel] [PATCH 08/10] intel-iommu: maintain per-device iova ranges, Jason Wang, 2018/04/27
- Re: [Qemu-devel] [PATCH 08/10] intel-iommu: maintain per-device iova ranges, Peter Xu, 2018/04/27
- Re: [Qemu-devel] [PATCH 08/10] intel-iommu: maintain per-device iova ranges, Tian, Kevin, 2018/04/27
- Re: [Qemu-devel] [PATCH 08/10] intel-iommu: maintain per-device iova ranges, Peter Xu, 2018/04/27
- Re: [Qemu-devel] [PATCH 08/10] intel-iommu: maintain per-device iova ranges, Tian, Kevin, 2018/04/27
- Re: [Qemu-devel] [PATCH 08/10] intel-iommu: maintain per-device iova ranges, Peter Xu, 2018/04/27
- Re: [Qemu-devel] [PATCH 08/10] intel-iommu: maintain per-device iova ranges, Peter Xu, 2018/04/27
- Re: [Qemu-devel] [PATCH 08/10] intel-iommu: maintain per-device iova ranges, Tian, Kevin, 2018/04/27
- Re: [Qemu-devel] [PATCH 08/10] intel-iommu: maintain per-device iova ranges, Jason Wang, 2018/04/27