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