From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:59280) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fE8gw-0000UA-7F for qemu-devel@nongnu.org; Thu, 03 May 2018 03:30:15 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1fE8gs-0002pd-Lt for qemu-devel@nongnu.org; Thu, 03 May 2018 03:30:13 -0400 Received: from mx3-rdu2.redhat.com ([66.187.233.73]:52472 helo=mx1.redhat.com) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1fE8gs-0002ov-Gp for qemu-devel@nongnu.org; Thu, 03 May 2018 03:30:10 -0400 Date: Thu, 3 May 2018 15:30:04 +0800 From: Peter Xu Message-ID: <20180503073004.GB29580@xz-mi> References: <20180425045129.17449-1-peterx@redhat.com> <20180425045129.17449-8-peterx@redhat.com> <20180503071041.GC2378@xz-mi> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline In-Reply-To: Content-Transfer-Encoding: quoted-printable Subject: Re: [Qemu-devel] [PATCH 07/10] util: implement simple interval tree logic List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: Jason Wang Cc: qemu-devel@nongnu.org, "Michael S . Tsirkin" , Alex Williamson , Jintack Lim On Thu, May 03, 2018 at 03:21:13PM +0800, Jason Wang wrote: >=20 >=20 > On 2018=E5=B9=B405=E6=9C=8803=E6=97=A5 15:10, Peter Xu wrote: > > On Fri, Apr 27, 2018 at 01:53:35PM +0800, Jason Wang wrote: > >=20 > > [...] > >=20 > > > > +int it_tree_remove(ITTree *tree, ITValue start, ITValue end) > > > > +{ > > > > + ITRange range =3D { .start =3D start, .end =3D end }, *overl= ap, and; > > > > + GTree *gtree; > > > > + > > > > + g_assert(tree); > > > > + > > > > + gtree =3D tree->tree; > > > > + while ((overlap =3D g_tree_lookup(gtree, &range))) { > > > > + if (it_range_equal(overlap, &range)) { > > > > + /* Exactly what we want to remove; done */ > > [1] > >=20 > > > > + g_tree_remove(gtree, overlap); > > > > + break; > > > > + } else if (it_range_cover(overlap, &range)) { > > [2] > >=20 > > > > + /* Split existing range into two; done */ > > > > + it_tree_remove_subset(gtree, overlap, &range); > > > > + break; > > > > + } else if (it_range_cover(&range, overlap)) { > > [3] > >=20 > > > > + /* Drop this range and continue */ > > > > + g_tree_remove(gtree, overlap); > > > > + } else { > > [4] > >=20 > > > > + /* > > > > + * The range to remove has intersection with existin= g > > > > + * ranges. Remove part of the range and continue > > > > + */ > > > > + it_range_and(&and, overlap, &range); > > > > + g_assert(and.start <=3D and.end); > > > > + it_tree_remove_subset(gtree, overlap, &and); > > > > + } > > > > + } > > > > + > > > Looks like what we need here is just calculate the intersection par= t the > > > remove it. > > Here after a second thought, I am thining whether it'll be good I use > > a general routine in [4] to replace all [1-4]. > >=20 > > The problem is that if we do that we'll depend on the next > > g_tree_lookup() to detect case [1-2] (in that case we'll find nothing > > in the lookup, but still we'll need to walk the tree) to break the > > loop, while IMHO that sometimes can be more expensive than the if > > clauses, especially when the tree is a bit large (each branch needs a > > if clause actually) and also note that in our use case we really have > > lots of cases for [1] and [2]. > >=20 > > I think I can merge [3] into [4], but I might consider keeping [1] an= d > > [2] since I don't really know whether merging them would be better. > > Anyway we can do that as follow up enhancement after the series > > merged. But I think we'll need some performance benchmarks. > >=20 > > Jason, what do you think? > >=20 > > Regards, > >=20 >=20 > Sounds good (but I don't promise I won't have new comments :)) Sure! I suppose that's why we post patches - we let people see so that one can leave comments. :) --=20 Peter Xu