fs/btrfs/ref-cache.c

   1 /*
   2  * Copyright (C) 2008 Oracle.  All rights reserved.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public
   6  * License v2 as published by the Free Software Foundation.
   7  *
   8  * This program is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11  * General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU General Public
  14  * License along with this program; if not, write to the
  15  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  16  * Boston, MA 021110-1307, USA.
  17  */
  18
  19 #include <linux/sched.h>
  20 #include <linux/slab.h>
  21 #include <linux/sort.h>
  22 #include "ctree.h"
  23 #include "ref-cache.h"
  24 #include "transaction.h"
  25
  26 static struct rb_node *tree_insert(struct rb_root *root, u64 bytenr,
  27                                    struct rb_node *node)
  28 {
  29         struct rb_node **p = &root->rb_node;
  30         struct rb_node *parent = NULL;
  31         struct btrfs_leaf_ref *entry;
  32
  33         while (*p) {
  34                 parent = *p;
  35                 entry = rb_entry(parent, struct btrfs_leaf_ref, rb_node);
  36
  37                 if (bytenr < entry->bytenr)
  38                         p = &(*p)->rb_left;
  39                 else if (bytenr > entry->bytenr)
  40                         p = &(*p)->rb_right;
  41                 else
  42                         return parent;
  43         }
  44
  45         entry = rb_entry(node, struct btrfs_leaf_ref, rb_node);
  46         rb_link_node(node, parent, p);
  47         rb_insert_color(node, root);
  48         return NULL;
  49 }
  50
  51 static struct rb_node *tree_search(struct rb_root *root, u64 bytenr)
  52 {
  53         struct rb_node *n = root->rb_node;
  54         struct btrfs_leaf_ref *entry;
  55
  56         while (n) {
  57                 entry = rb_entry(n, struct btrfs_leaf_ref, rb_node);
  58                 WARN_ON(!entry->in_tree);
  59
  60                 if (bytenr < entry->bytenr)
  61                         n = n->rb_left;
  62                 else if (bytenr > entry->bytenr)
  63                         n = n->rb_right;
  64                 else
  65                         return n;
  66         }
  67         return NULL;
  68 }