Re: [PATCH v3 03/15] interval-tree: Add a utility to iterate over spans in an interval tree

From: Matthew Wilcox <willy@infradead.org>
To: Jason Gunthorpe <jgg@nvidia.com>
Cc: "Tian, Kevin" <kevin.tian@intel.com>,
	Lu Baolu <baolu.lu@linux.intel.com>,
	"bpf@vger.kernel.org" <bpf@vger.kernel.org>,
	Jonathan Corbet <corbet@lwn.net>,
	David Woodhouse <dwmw2@infradead.org>,
	"iommu@lists.linux.dev" <iommu@lists.linux.dev>,
	Joerg Roedel <joro@8bytes.org>,
	"linux-doc@vger.kernel.org" <linux-doc@vger.kernel.org>,
	"linux-kselftest@vger.kernel.org"
	<linux-kselftest@vger.kernel.org>,
	"llvm@lists.linux.dev" <llvm@lists.linux.dev>,
	Nathan Chancellor <nathan@kernel.org>,
	Nick Desaulniers <ndesaulniers@google.com>,
	Miguel Ojeda <ojeda@kernel.org>,
	Robin Murphy <robin.murphy@arm.com>,
	Shuah Khan <shuah@kernel.org>,
	Suravee Suthikulpanit <suravee.suthikulpanit@amd.com>,
	Tom Rix <trix@redhat.com>, Will Deacon <will@kernel.org>,
	Alex Williamson <alex.williamson@redhat.com>,
	Chaitanya Kulkarni <chaitanyak@nvidia.com>,
	Cornelia Huck <cohuck@redhat.com>,
	Daniel Jordan <daniel.m.jordan@oracle.com>,
	David Gibson <david@gibson.dropbear.id.au>,
	Eric Auger <eric.auger@redhat.com>,
	Eric Farman <farman@linux.ibm.com>,
	Jason Wang <jasowang@redhat.com>,
	Jean-Philippe Brucker <jean-philippe@linaro.org>,
	"Martins, Joao" <joao.m.martins@oracle.com>,
	"kvm@vger.kernel.org" <kvm@vger.kernel.org>,
	Matthew Rosato <mjrosato@linux.ibm.com>,
	"Michael S. Tsirkin" <mst@redhat.com>,
	Nicolin Chen <nicolinc@nvidia.com>,
	Niklas Schnelle <schnelle@linux.ibm.com>,
	Shameerali Kolothum Thodi <shameerali.kolothum.thodi@huawei.com>,
	"Liu, Yi L" <yi.l.liu@intel.com>,
	Keqian Zhu <zhukeqian1@huawei.com>
Subject: Re: [PATCH v3 03/15] interval-tree: Add a utility to iterate over spans in an interval tree
Date: Sat, 5 Nov 2022 01:48:31 +0000	[thread overview]
Message-ID: <Y2XA702nWRGfP7mo@casper.infradead.org> (raw)
In-Reply-To: <Y2VqK3m9i6FlQd9+@nvidia.com>

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 <jgg@nvidia.com>
> > > 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;
...
};