1 /*
2 * Copyright (C) 2014 Facebook. 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/errno.h>
20 #include "rbtree-utils.h"
21
rb_insert(struct rb_root * root,struct rb_node * node,rb_compare_nodes comp)22 int rb_insert(struct rb_root *root, struct rb_node *node,
23 rb_compare_nodes comp)
24 {
25 struct rb_node **p = &root->rb_node;
26 struct rb_node *parent = NULL;
27 int ret;
28
29 while(*p) {
30 parent = *p;
31
32 ret = comp(parent, node);
33 if (ret < 0)
34 p = &(*p)->rb_left;
35 else if (ret > 0)
36 p = &(*p)->rb_right;
37 else
38 return -EEXIST;
39 }
40
41 rb_link_node(node, parent, p);
42 rb_insert_color(node, root);
43 return 0;
44 }
45
rb_search(struct rb_root * root,void * key,rb_compare_keys comp,struct rb_node ** next_ret)46 struct rb_node *rb_search(struct rb_root *root, void *key, rb_compare_keys comp,
47 struct rb_node **next_ret)
48 {
49 struct rb_node *n = root->rb_node;
50 struct rb_node *parent = NULL;
51 int ret = 0;
52
53 while(n) {
54 parent = n;
55
56 ret = comp(n, key);
57 if (ret < 0)
58 n = n->rb_left;
59 else if (ret > 0)
60 n = n->rb_right;
61 else
62 return n;
63 }
64
65 if (!next_ret)
66 return NULL;
67
68 if (parent && ret > 0)
69 parent = rb_next(parent);
70
71 *next_ret = parent;
72 return NULL;
73 }
74
rb_free_nodes(struct rb_root * root,rb_free_node free_node)75 void rb_free_nodes(struct rb_root *root, rb_free_node free_node)
76 {
77 struct rb_node *node;
78
79 while ((node = rb_first(root))) {
80 rb_erase(node, root);
81 free_node(node);
82 }
83 }
84