git.itanic.dy.fi Git - scan-pagemap/blob - treeops.c

   1 #include "pagemap.h"
   2
   3 struct pageframe *pf_insert(struct rb_root *root, struct pageframe *pf)
   4 {
   5         struct rb_node **new = &(root->rb_node), *parent = NULL;
   6
   7         /* Figure out where to put new node */
   8         while (*new) {
   9                 struct pageframe *this = rb_to_pageframe(*new);
  10                 int result = pf->pf - this->pf;
  11
  12                 parent = *new;
  13                 if (result < 0)
  14                         new = &((*new)->rb_left);
  15                 else if (result > 0)
  16                         new = &((*new)->rb_right);
  17                 else
  18                         /*
  19                          * We already have a matching node in the
  20                          * tree. Return that node to indicate the
  21                          * collision
  22                          */
  23                         return this;
  24         }
  25
  26         /* Add new node and rebalance tree. */
  27         rb_link_node(&pf->tree, parent, new);
  28         rb_insert_color(&pf->tree, root);
  29
  30         return pf;
  31 }
  32
  33 struct pageframe *pf_search(struct rb_root *root, struct pageframe *pf)
  34 {
  35         struct rb_node *node = root->rb_node;
  36
  37         while (node) {
  38                 struct pageframe *this = rb_to_pageframe(node);
  39                 int result;
  40
  41                 result = pf->pf - this->pf;
  42
  43                 if (result < 0)
  44                         node = node->rb_left;
  45                 else if (result > 0)
  46                         node = node->rb_right;
  47                 else
  48                         return this;
  49         }
  50         return NULL;
  51 }