btrfs-progs: check: enhance return values of walk_down_tree_v2
[btrfs-progs-unstable/devel.git] / rbtree-utils.c
blob7371bbb442a0183d1ff273e33a439462b8140b9e
1 /*
2 * Copyright (C) 2014 Facebook. 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 "rbtree-utils.h"
21 int rb_insert(struct rb_root *root, struct rb_node *node,
22 rb_compare_nodes comp)
24 struct rb_node **p = &root->rb_node;
25 struct rb_node *parent = NULL;
26 int ret;
28 while(*p) {
29 parent = *p;
31 ret = comp(parent, node);
32 if (ret < 0)
33 p = &(*p)->rb_left;
34 else if (ret > 0)
35 p = &(*p)->rb_right;
36 else
37 return -EEXIST;
40 rb_link_node(node, parent, p);
41 rb_insert_color(node, root);
42 return 0;
45 struct rb_node *rb_search(struct rb_root *root, void *key, rb_compare_keys comp,
46 struct rb_node **next_ret)
48 struct rb_node *n = root->rb_node;
49 struct rb_node *parent = NULL;
50 int ret = 0;
52 while(n) {
53 parent = n;
55 ret = comp(n, key);
56 if (ret < 0)
57 n = n->rb_left;
58 else if (ret > 0)
59 n = n->rb_right;
60 else
61 return n;
64 if (!next_ret)
65 return NULL;
67 if (parent && ret > 0)
68 parent = rb_next(parent);
70 *next_ret = parent;
71 return NULL;
74 void rb_free_nodes(struct rb_root *root, rb_free_node free_node)
76 struct rb_node *node;
78 while ((node = rb_first(root))) {
79 rb_erase(node, root);
80 free_node(node);