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

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



> From: Jason Gunthorpe <jgg@xxxxxxxxxx>
> Sent: Saturday, November 5, 2022 3:38 AM
> 
> On Thu, Nov 03, 2022 at 05:31:17AM +0000, Tian, Kevin wrote:
> > > From: Jason Gunthorpe <jgg@xxxxxxxxxx>
> > > 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.
> +	 */

/* Members below here are part of the external interface */

>  	union {
>  		unsigned long start_hole;
>  		unsigned long start_used;
> 
> > > +void interval_tree_span_iter_advance(struct interval_tree_span_iter
> *iter,
> > > +				     struct rb_root_cached *itree,
> > > +				     unsigned long new_index)
> > > +{
> > > +	if (iter->is_hole == -1)
> > > +		return;
> > > +
> > > +	iter->first_index = new_index;
> > > +	if (new_index == iter->last_index) {
> > > +		iter->is_hole = -1;
> > > +		return;
> > > +	}
> > > +
> > > +	/* Rely on the union aliasing hole/used */
> > > +	if (iter->start_hole <= new_index && new_index <= iter->last_hole) {
> >
> > "<=" to "<"
> >
> > > +		iter->start_hole = new_index;
> > > +		return;
> > > +	}
> 
> Hrm, I don't think so..  This is testing if new_index is valid for the
> current span. new_index == start_XXX is a valid index of the span and
> new_index == last_XX is also a valid index, so either of them should
> just update start_XX and do nothing else.
> 

You are right.




[Index of Archives]     [Linux Wireless]     [Linux Kernel]     [ATH6KL]     [Linux Bluetooth]     [Linux Netdev]     [Kernel Newbies]     [Share Photos]     [IDE]     [Security]     [Git]     [Netfilter]     [Bugtraq]     [Yosemite News]     [MIPS Linux]     [ARM Linux]     [Linux Security]     [Linux RAID]     [Linux ATA RAID]     [Samba]     [Device Mapper]

  Powered by Linux