xref: /kvmtool/util/rbtree-interval.c (revision ffc83de3572f96c484b199d743ed4fbf8ce1caba)

#include <kvm/rbtree-interval.h>
#include <stddef.h>
#include <errno.h>

struct rb_int_node *rb_int_search_single(struct rb_root *root, u64 point)
{
	struct rb_node *node = root->rb_node;

	while (node) {
		struct rb_int_node *cur = rb_int(node);

		if (point < cur->low)
			node = node->rb_left;
		else if (cur->high <= point)
			node = node->rb_right;
		else
			return cur;
	}

	return NULL;
}

struct rb_int_node *rb_int_search_range(struct rb_root *root, u64 low, u64 high)
{
	struct rb_int_node *range;

	range = rb_int_search_single(root, low);
	if (range == NULL)
		return NULL;

	/* We simply verify that 'high' is smaller than the end of the range where 'low' is located */
	if (range->high < high)
		return NULL;

	return range;
}

/*
 * Update a node after it has been linked into the tree:
 */
static void propagate_callback(struct rb_node *node, struct rb_node *stop)
{
	struct rb_int_node *i_node;

	if (node == stop)
		return;

	i_node = rb_int(node);
	i_node->max_high = i_node->high;

	if (node->rb_left)
		i_node->max_high = max(i_node->max_high, rb_int(node->rb_left)->max_high);
	if (node->rb_right)
		i_node->max_high = max(i_node->max_high, rb_int(node->rb_right)->max_high);
}

/*
 * Copy the extra data to a new node:
 */
static void copy_callback(struct rb_node *node_old, struct rb_node *node_new)
{
	struct rb_int_node *i_node_old = rb_int(node_old);
	struct rb_int_node *i_node_new = rb_int(node_new);

	i_node_new->low		= i_node_old->low;
	i_node_new->high	= i_node_old->high;

	i_node_new->max_high	= i_node_old->max_high;
}

/*
 * Update after tree rotation:
 */
static void rotate_callback(struct rb_node *node_old, struct rb_node *node_new)
{
	propagate_callback(node_old, NULL);
	propagate_callback(node_new, NULL);
}

/*
 * All augmented rbtree callbacks:
 */
struct rb_augment_callbacks callbacks = {
	.propagate	= propagate_callback,
	.copy		= copy_callback,
	.rotate		= rotate_callback,
};

int rb_int_insert(struct rb_root *root, struct rb_int_node *i_node)
{
	struct rb_node **node = &root->rb_node, *parent = NULL;

	while (*node) {
		struct rb_int_node *cur = rb_int(*node);

		parent = *node;
		if (i_node->high <= cur->low)
			node = &cur->node.rb_left;
		else if (cur->high <= i_node->low)
			node = &cur->node.rb_right;
		else
			return -EEXIST;
	}

	rb_link_node(&i_node->node, parent, node);
	rb_insert_augmented(&i_node->node, root, &callbacks);

	return 0;
}

void rb_int_erase(struct rb_root *root, struct rb_int_node *node)
{
	rb_erase_augmented(&node->node, root, &callbacks);
}