1// SPDX-License-Identifier: GPL-2.0-only
 2#include <linux/interval_tree.h>
 3#include <linux/interval_tree_generic.h>
 4#include <linux/compiler.h>
 5#include <linux/export.h>
 6
 7#define START(node) ((node)->start)
 8#define LAST(node)  ((node)->last)
 9
10INTERVAL_TREE_DEFINE(struct interval_tree_node, rb,
11		     unsigned long, __subtree_last,
12		     START, LAST,, interval_tree)
13
14EXPORT_SYMBOL_GPL(interval_tree_insert);
15EXPORT_SYMBOL_GPL(interval_tree_remove);
16EXPORT_SYMBOL_GPL(interval_tree_iter_first);
17EXPORT_SYMBOL_GPL(interval_tree_iter_next);

  1// SPDX-License-Identifier: GPL-2.0-only
  2#include <linux/interval_tree.h>
  3#include <linux/interval_tree_generic.h>
  4#include <linux/compiler.h>
  5#include <linux/export.h>
  6
  7#define START(node) ((node)->start)
  8#define LAST(node)  ((node)->last)
  9
 10INTERVAL_TREE_DEFINE(struct interval_tree_node, rb,
 11		     unsigned long, __subtree_last,
 12		     START, LAST,, interval_tree)
 13
 14EXPORT_SYMBOL_GPL(interval_tree_insert);
 15EXPORT_SYMBOL_GPL(interval_tree_remove);
 16EXPORT_SYMBOL_GPL(interval_tree_iter_first);
 17EXPORT_SYMBOL_GPL(interval_tree_iter_next);
 18
 19#ifdef CONFIG_INTERVAL_TREE_SPAN_ITER
 20/*
 21 * Roll nodes[1] into nodes[0] by advancing nodes[1] to the end of a contiguous
 22 * span of nodes. This makes nodes[0]->last the end of that contiguous used span
 23 * indexes that started at the original nodes[1]->start. nodes[1] is now the
 24 * first node starting the next used span. A hole span is between nodes[0]->last
 25 * and nodes[1]->start. nodes[1] must be !NULL.
 26 */
 27static void
 28interval_tree_span_iter_next_gap(struct interval_tree_span_iter *state)
 29{
 30	struct interval_tree_node *cur = state->nodes[1];
 31
 32	state->nodes[0] = cur;
 33	do {
 34		if (cur->last > state->nodes[0]->last)
 35			state->nodes[0] = cur;
 36		cur = interval_tree_iter_next(cur, state->first_index,
 37					      state->last_index);
 38	} while (cur && (state->nodes[0]->last >= cur->start ||
 39			 state->nodes[0]->last + 1 == cur->start));
 40	state->nodes[1] = cur;
 41}
 42
 43void interval_tree_span_iter_first(struct interval_tree_span_iter *iter,
 44				   struct rb_root_cached *itree,
 45				   unsigned long first_index,
 46				   unsigned long last_index)
 47{
 48	iter->first_index = first_index;
 49	iter->last_index = last_index;
 50	iter->nodes[0] = NULL;
 51	iter->nodes[1] =
 52		interval_tree_iter_first(itree, first_index, last_index);
 53	if (!iter->nodes[1]) {
 54		/* No nodes intersect the span, whole span is hole */
 55		iter->start_hole = first_index;
 56		iter->last_hole = last_index;
 57		iter->is_hole = 1;
 58		return;
 59	}
 60	if (iter->nodes[1]->start > first_index) {
 61		/* Leading hole on first iteration */
 62		iter->start_hole = first_index;
 63		iter->last_hole = iter->nodes[1]->start - 1;
 64		iter->is_hole = 1;
 65		interval_tree_span_iter_next_gap(iter);
 66		return;
 67	}
 68
 69	/* Starting inside a used */
 70	iter->start_used = first_index;
 71	iter->is_hole = 0;
 72	interval_tree_span_iter_next_gap(iter);
 73	iter->last_used = iter->nodes[0]->last;
 74	if (iter->last_used >= last_index) {
 75		iter->last_used = last_index;
 76		iter->nodes[0] = NULL;
 77		iter->nodes[1] = NULL;
 78	}
 79}
 80EXPORT_SYMBOL_GPL(interval_tree_span_iter_first);
 81
 82void interval_tree_span_iter_next(struct interval_tree_span_iter *iter)
 83{
 84	if (!iter->nodes[0] && !iter->nodes[1]) {
 85		iter->is_hole = -1;
 86		return;
 87	}
 88
 89	if (iter->is_hole) {
 90		iter->start_used = iter->last_hole + 1;
 91		iter->last_used = iter->nodes[0]->last;
 92		if (iter->last_used >= iter->last_index) {
 93			iter->last_used = iter->last_index;
 94			iter->nodes[0] = NULL;
 95			iter->nodes[1] = NULL;
 96		}
 97		iter->is_hole = 0;
 98		return;
 99	}
100
101	if (!iter->nodes[1]) {
102		/* Trailing hole */
103		iter->start_hole = iter->nodes[0]->last + 1;
104		iter->last_hole = iter->last_index;
105		iter->nodes[0] = NULL;
106		iter->is_hole = 1;
107		return;
108	}
109
110	/* must have both nodes[0] and [1], interior hole */
111	iter->start_hole = iter->nodes[0]->last + 1;
112	iter->last_hole = iter->nodes[1]->start - 1;
113	iter->is_hole = 1;
114	interval_tree_span_iter_next_gap(iter);
115}
116EXPORT_SYMBOL_GPL(interval_tree_span_iter_next);
117
118/*
119 * Advance the iterator index to a specific position. The returned used/hole is
120 * updated to start at new_index. This is faster than calling
121 * interval_tree_span_iter_first() as it can avoid full searches in several
122 * cases where the iterator is already set.
123 */
124void interval_tree_span_iter_advance(struct interval_tree_span_iter *iter,
125				     struct rb_root_cached *itree,
126				     unsigned long new_index)
127{
128	if (iter->is_hole == -1)
129		return;
130
131	iter->first_index = new_index;
132	if (new_index > iter->last_index) {
133		iter->is_hole = -1;
134		return;
135	}
136
137	/* Rely on the union aliasing hole/used */
138	if (iter->start_hole <= new_index && new_index <= iter->last_hole) {
139		iter->start_hole = new_index;
140		return;
141	}
142	if (new_index == iter->last_hole + 1)
143		interval_tree_span_iter_next(iter);
144	else
145		interval_tree_span_iter_first(iter, itree, new_index,
146					      iter->last_index);
147}
148EXPORT_SYMBOL_GPL(interval_tree_span_iter_advance);
149#endif