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

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

+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;
  

• }
• if (new_index == iter->last_hole + 1)

• interval_tree_span_iter_next(iter);
  

• else

• interval_tree_span_iter_first(iter, itree, new_index,
  

• 			      iter->last_index);
  

+} +EXPORT_SYMBOL_GPL(interval_tree_span_iter_advance); +#endif

Apart from those,

Reviewed-by: Kevin Tian kevin.tian@intel.com