#include "pagemap.h"

struct pageframe *pf_insert(struct rb_root *root, struct pageframe *pf)
{
	struct rb_node **new = &(root->rb_node), *parent = NULL;

	/* Figure out where to put new node */
	while (*new) {
		struct pageframe *this = rb_to_pageframe(*new);
		int result = pf->pf - this->pf;

		parent = *new;
		if (result < 0)
			new = &((*new)->rb_left);
		else if (result > 0)
			new = &((*new)->rb_right);
		else
			/* 
			 * We already have a matching node in the
			 * tree. Return that node to indicate the
			 * collision
			 */
			return NULL;
	}

	/* Add new node and rebalance tree. */
	rb_link_node(&pf->tree, parent, new);
	rb_insert_color(&pf->tree, root);

	return pf;
}

struct pageframe *pf_search(struct rb_root *root, struct pageframe *pf)
{
	struct rb_node *node = root->rb_node;

	while (node) {
		struct pageframe *this = rb_to_pageframe(node);
		int result;

		result = pf->pf - this->pf;

		if (result < 0)
			node = node->rb_left;
		else if (result > 0)
			node = node->rb_right;
		else
			return this;
	}
	return NULL;
}