2 * Copyright (C) 2008 Oracle. All rights reserved.
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.
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.
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.
19 #include <linux/sched.h>
20 #include <linux/slab.h>
21 #include <linux/sort.h>
23 #include "ref-cache.h"
24 #include "transaction.h"
26 static struct rb_node *tree_insert(struct rb_root *root, u64 bytenr,
29 struct rb_node **p = &root->rb_node;
30 struct rb_node *parent = NULL;
31 struct btrfs_leaf_ref *entry;
35 entry = rb_entry(parent, struct btrfs_leaf_ref, rb_node);
37 if (bytenr < entry->bytenr)
39 else if (bytenr > entry->bytenr)
45 entry = rb_entry(node, struct btrfs_leaf_ref, rb_node);
46 rb_link_node(node, parent, p);
47 rb_insert_color(node, root);
51 static struct rb_node *tree_search(struct rb_root *root, u64 bytenr)
53 struct rb_node *n = root->rb_node;
54 struct btrfs_leaf_ref *entry;
57 entry = rb_entry(n, struct btrfs_leaf_ref, rb_node);
58 WARN_ON(!entry->in_tree);
60 if (bytenr < entry->bytenr)
62 else if (bytenr > entry->bytenr)