Line data Source code
1 : /*-
2 : * Copyright (c) 2010 Isilon Systems, Inc.
3 : * Copyright (c) 2010 iX Systems, Inc.
4 : * Copyright (c) 2010 Panasas, Inc.
5 : * Copyright (c) 2013, 2014 Mellanox Technologies, Ltd.
6 : * All rights reserved.
7 : *
8 : * Redistribution and use in source and binary forms, with or without
9 : * modification, are permitted provided that the following conditions
10 : * are met:
11 : * 1. Redistributions of source code must retain the above copyright
12 : * notice unmodified, this list of conditions, and the following
13 : * disclaimer.
14 : * 2. Redistributions in binary form must reproduce the above copyright
15 : * notice, this list of conditions and the following disclaimer in the
16 : * documentation and/or other materials provided with the distribution.
17 : *
18 : * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
19 : * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
20 : * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
21 : * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
22 : * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
23 : * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24 : * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 : * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 : * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
27 : * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 : */
29 : #ifndef _LINUX_RBTREE_H_
30 : #define _LINUX_RBTREE_H_
31 :
32 : #include <sys/tree.h>
33 :
34 : struct rb_node {
35 : RB_ENTRY(rb_node) __entry;
36 : };
37 : #define rb_left __entry.rbe_left
38 : #define rb_right __entry.rbe_right
39 :
40 : /*
41 : * We provide a false structure that has the same bit pattern as tree.h
42 : * presents so it matches the member names expected by linux.
43 : */
44 : struct rb_root {
45 : struct rb_node *rb_node;
46 : };
47 :
48 : /*
49 : * In linux all of the comparisons are done by the caller.
50 : */
51 : int panic_cmp(struct rb_node *one, struct rb_node *two);
52 :
53 : RB_HEAD(linux_root, rb_node);
54 : RB_PROTOTYPE(linux_root, rb_node, __entry, panic_cmp);
55 :
56 : #define rb_parent(r) RB_PARENT(r, __entry)
57 : #define rb_color(r) RB_COLOR(r, __entry)
58 : #define rb_is_red(r) (rb_color(r) == RB_RED)
59 : #define rb_is_black(r) (rb_color(r) == RB_BLACK)
60 : #define rb_set_parent(r, p) rb_parent((r)) = (p)
61 : #define rb_set_color(r, c) rb_color((r)) = (c)
62 : #define rb_entry(ptr, type, member) container_of(ptr, type, member)
63 : #define rb_entry_safe(ptr, type, member) \
64 : (ptr ? rb_entry(ptr, type, member) : NULL)
65 :
66 : #define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL)
67 : #define RB_EMPTY_NODE(node) (rb_parent(node) == node)
68 : #define RB_CLEAR_NODE(node) (rb_set_parent(node, node))
69 :
70 : #define rb_insert_color(node, root) \
71 : linux_root_RB_INSERT_COLOR((struct linux_root *)(root), (node))
72 : #define rb_erase(node, root) \
73 : linux_root_RB_REMOVE((struct linux_root *)(root), (node))
74 : #define rb_next(node) RB_NEXT(linux_root, NULL, (node))
75 : #define rb_prev(node) RB_PREV(linux_root, NULL, (node))
76 : #define rb_first(root) RB_MIN(linux_root, (struct linux_root *)(root))
77 : #define rb_last(root) RB_MAX(linux_root, (struct linux_root *)(root))
78 : #define rbtree_postorder_for_each_entry_safe(x, y, head, member) \
79 : for ((x) = rb_entry_safe(RB_MIN(linux_root, (struct linux_root *)head), \
80 : __typeof(*x), member); \
81 : ((x) != NULL) && ({(y) = \
82 : rb_entry_safe(linux_root_RB_NEXT(&x->member), typeof(*x), member); 1; }); \
83 : (x) = (y))
84 :
85 : static inline void
86 0 : rb_link_node(struct rb_node *node, struct rb_node *parent,
87 : struct rb_node **rb_link)
88 : {
89 0 : rb_set_parent(node, parent);
90 0 : rb_set_color(node, RB_RED);
91 0 : node->__entry.rbe_left = node->__entry.rbe_right = NULL;
92 0 : *rb_link = node;
93 0 : }
94 :
95 : static inline void
96 : rb_replace_node(struct rb_node *victim, struct rb_node *new,
97 : struct rb_root *root)
98 : {
99 : struct rb_node *p;
100 :
101 : p = rb_parent(victim);
102 : if (p) {
103 : if (p->rb_left == victim)
104 : p->rb_left = new;
105 : else
106 : p->rb_right = new;
107 : } else
108 : root->rb_node = new;
109 : if (victim->rb_left)
110 : rb_set_parent(victim->rb_left, new);
111 : if (victim->rb_right)
112 : rb_set_parent(victim->rb_right, new);
113 : *new = *victim;
114 : }
115 :
116 : #undef RB_ROOT
117 : #define RB_ROOT (struct rb_root) { NULL }
118 :
119 : struct interval_tree_node {
120 : struct rb_node rb;
121 : unsigned long start;
122 : unsigned long last;
123 : };
124 :
125 : static inline struct interval_tree_node *
126 0 : interval_tree_iter_first(struct rb_root *root,
127 : unsigned long start, unsigned long last)
128 : {
129 : #ifdef DRMDEBUG
130 : printf("%s: stub start: 0x%lx last: 0x%lx\n", __func__, start, last);
131 : #endif
132 0 : return NULL;
133 : }
134 :
135 : static inline void
136 0 : interval_tree_insert(struct interval_tree_node *node, struct rb_root *root)
137 : {
138 : #ifdef DRMDEBUG
139 : printf("%s: stub start: 0x%lx last: 0x%lx\n", __func__, node->start, node->last);
140 : #endif
141 0 : }
142 :
143 : static inline void
144 0 : interval_tree_remove(struct interval_tree_node *node, struct rb_root *root)
145 : {
146 : #ifdef DRMDEBUG
147 : printf("%s: stub start: 0x%lx last: 0x%lx\n", __func__, node->start, node->last);
148 : #endif
149 0 : }
150 :
151 : #endif /* _LINUX_RBTREE_H_ */
|
