From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from casper.infradead.org (casper.infradead.org [90.155.50.34]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 321EB1101; Sat, 5 Nov 2022 01:49:10 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=casper.20170209; h=In-Reply-To:Content-Type:MIME-Version: References:Message-ID:Subject:Cc:To:From:Date:Sender:Reply-To: Content-Transfer-Encoding:Content-ID:Content-Description; bh=9U5xi3PcgZdoJ36o8T9jPl/wvWDSsiwJ5sUl4RJdjZk=; b=ePD8DfII+AqMG+pbpQoEpH39TY s+hVP+5iEsxjJ8oU86NNuGgxNscBI7RVuaMQbhuxsUyc/NKsegOoKTu/d3lCJQEInm5686UJ6Wa2e p0O0X1IJWg4TguqnCcpF2gp22n3prg5INmSuVElNXeIumuzFhWMKz93GgmUd124H5vWdo9DX2GC/Q L6RAQPhrX291UPkprEzJu1CtIYExY65loSeybACFw2S2XzgqwWva6KN++Siq3RaGhJlXWgJofVPCm v29GnWL13GD+OZXJbOGFp2kJC0vlR+ZkeoBgCdlerynfZczDbJysumW3Tp8rsw/r4ky5ORlT1kUl/ ze9pMWlA==; Received: from willy by casper.infradead.org with local (Exim 4.94.2 #2 (Red Hat Linux)) id 1or8IR-007rC4-5c; Sat, 05 Nov 2022 01:48:31 +0000 Date: Sat, 5 Nov 2022 01:48:31 +0000 From: Matthew Wilcox To: Jason Gunthorpe Cc: "Tian, Kevin" , Lu Baolu , "bpf@vger.kernel.org" , Jonathan Corbet , David Woodhouse , "iommu@lists.linux.dev" , Joerg Roedel , "linux-doc@vger.kernel.org" , "linux-kselftest@vger.kernel.org" , "llvm@lists.linux.dev" , Nathan Chancellor , Nick Desaulniers , Miguel Ojeda , Robin Murphy , Shuah Khan , Suravee Suthikulpanit , Tom Rix , Will Deacon , Alex Williamson , Chaitanya Kulkarni , Cornelia Huck , Daniel Jordan , David Gibson , Eric Auger , Eric Farman , Jason Wang , Jean-Philippe Brucker , "Martins, Joao" , "kvm@vger.kernel.org" , Matthew Rosato , "Michael S. Tsirkin" , Nicolin Chen , Niklas Schnelle , Shameerali Kolothum Thodi , "Liu, Yi L" , Keqian Zhu Subject: Re: [PATCH v3 03/15] interval-tree: Add a utility to iterate over spans in an interval tree Message-ID: References: <0-v3-402a7d6459de+24b-iommufd_jgg@nvidia.com> <3-v3-402a7d6459de+24b-iommufd_jgg@nvidia.com> Precedence: bulk X-Mailing-List: llvm@lists.linux.dev List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: On Fri, Nov 04, 2022 at 04:38:19PM -0300, Jason Gunthorpe wrote: > On Thu, Nov 03, 2022 at 05:31:17AM +0000, Tian, Kevin wrote: > > > From: Jason Gunthorpe > > > Sent: Wednesday, October 26, 2022 2:12 AM > > > +/* > > > + * This iterator travels over spans in an interval tree. It does not return > > > + * nodes but classifies each span as either a hole, where no nodes intersect, > > > or > > > + * a used, which is fully covered by nodes. Each iteration step toggles > > > between > > > + * hole and used until the entire range is covered. The returned spans > > > always > > > + * fully cover the requested range. > > > + * > > > + * The iterator is greedy, it always returns the largest hole or used possible, > > > + * consolidating all consecutive nodes. > > > + * > > > + * Only is_hole, start_hole/used and last_hole/used are part of the external > > > + * interface. > > > > slightly better readability if moving this sentence into the structure as > > the break line > > Do you mean like this? > > @@ -37,13 +37,16 @@ interval_tree_iter_next(struct interval_tree_node *node, > * The iterator is greedy, it always returns the largest hole or used possible, > * consolidating all consecutive nodes. > - * > - * Only is_hole, start_hole/used and last_hole/used are part of the external > - * interface. > */ > struct interval_tree_span_iter { > struct interval_tree_node *nodes[2]; > unsigned long first_index; > unsigned long last_index; > + > + /* > + * Only is_hole, start_hole/used and last_hole/used are part of the > + * external interface. > + */ > union { > unsigned long start_hole; > unsigned long start_used; Or you could kernel-doc it ... /** * struct interval_tree_span_iter - Find used and unused spans. * @start_hole: ... * @start_used: ... ... * * This iterator travels over spans in an interval tree. It does not return * nodes but classifies each span as either a hole, where no nodes intersect, * or as used, which is fully covered by nodes. Each iteration step * alternates between hole and used until the entire range is covered. The * returned spans always fully cover the requested range. * * The iterator is greedy, it always returns the largest span possible, * consolidating all consecutive nodes. */ struct interval_tree_span_iter { /* private: not for use by the caller */ struct interval_tree_node *nodes[2]; unsigned long first_index; unsigned long last_index; /* public: */ union { unsigned long start_hole; unsigned long start_used; ... };