Palacios Public Git Repository

To checkout Palacios execute

  git clone http://v3vee.org/palacios/palacios.web/palacios.git
This will give you the master branch. You probably want the devel branch or one of the release branches. To switch to the devel branch, simply execute
  cd palacios
  git checkout --track -b devel origin/devel
The other branches are similar.


Fix for option processing
[palacios.git] / palacios / include / palacios / vmm_rbtree.h
1 /*
2   Red Black Trees
3   (C) 1999  Andrea Arcangeli <andrea@suse.de>
4   
5   This program is free software; you can redistribute it and/or modify
6   it under the terms of the GNU General Public License as published by
7   the Free Software Foundation; either version 2 of the License, or
8   (at your option) any later version.
9
10   This program is distributed in the hope that it will be useful,
11   but WITHOUT ANY WARRANTY; without even the implied warranty of
12   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13   GNU General Public License for more details.
14
15   You should have received a copy of the GNU General Public License
16   along with this program; if not, write to the Free Software
17   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
18
19   linux/include/linux/rbtree.h
20
21   To use rbtrees you'll have to implement your own insert and search cores.
22   This will avoid us to use callbacks and to drop drammatically performances.
23   I know it's not the cleaner way,  but in C (not in C++) to get
24   performances and genericity...
25
26   Some example of insert and search follows here. The search is a plain
27   normal search over an ordered tree. The insert instead must be implemented
28   int two steps: as first thing the code must insert the element in
29   order as a red leaf in the tree, then the support library function
30   rb_insert_color() must be called. Such function will do the
31   not trivial work to rebalance the rbtree if necessary.
32
33 -----------------------------------------------------------------------
34 static inline struct page * rb_search_page_cache(struct inode * inode,
35                                                  unsigned long offset)
36 {
37         struct rb_node * n = inode->i_rb_page_cache.rb_node;
38         struct page * page;
39
40         while (n)
41         {
42                 page = rb_entry(n, struct page, rb_page_cache);
43
44                 if (offset < page->offset)
45                         n = n->rb_left;
46                 else if (offset > page->offset)
47                         n = n->rb_right;
48                 else
49                         return page;
50         }
51         return NULL;
52 }
53
54 static inline struct page * __rb_insert_page_cache(struct inode * inode,
55                                                    unsigned long offset,
56                                                    struct rb_node * node)
57 {
58         struct rb_node ** p = &inode->i_rb_page_cache.rb_node;
59         struct rb_node * parent = NULL;
60         struct page * page;
61
62         while (*p)
63         {
64                 parent = *p;
65                 page = rb_entry(parent, struct page, rb_page_cache);
66
67                 if (offset < page->offset)
68                         p = &(*p)->rb_left;
69                 else if (offset > page->offset)
70                         p = &(*p)->rb_right;
71                 else
72                         return page;
73         }
74
75         rb_link_node(node, parent, p);
76
77         return NULL;
78 }
79
80 static inline struct page * rb_insert_page_cache(struct inode * inode,
81                                                  unsigned long offset,
82                                                  struct rb_node * node)
83 {
84         struct page * ret;
85         if ((ret = __rb_insert_page_cache(inode, offset, node)))
86                 goto out;
87         rb_insert_color(node, &inode->i_rb_page_cache);
88  out:
89         return ret;
90 }
91 -----------------------------------------------------------------------
92 */
93
94 #ifndef _VMM_RBTREE_H
95 #define _VMM_RBTREE_H
96
97 #ifdef __V3VEE__
98
99 #include <palacios/vmm_types.h>
100
101
102 #undef offsetof
103 #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
104
105 #define container_of(ptr, type, member) ({                              \
106             const typeof( ((type *)0)->member ) *__mptr = (ptr);        \
107             (type *)( (char *)__mptr - offsetof(type,member) );})
108
109
110
111 struct rb_node
112 {
113     unsigned long  rb_parent_color;
114 #define RB_RED          0
115 #define RB_BLACK        1
116     struct rb_node *rb_right;
117     struct rb_node *rb_left;
118 } __attribute__((aligned(sizeof(long))));
119 /* The alignment might seem pointless, but allegedly CRIS needs it */
120
121 struct rb_root
122 {
123     struct rb_node *rb_node;
124 };
125
126
127 #define rb_parent(r)   ((struct rb_node *)((r)->rb_parent_color & ~3))
128 #define rb_color(r)   ((r)->rb_parent_color & 1)
129 #define rb_is_red(r)   (!rb_color(r))
130 #define rb_is_black(r) rb_color(r)
131 #define rb_set_red(r)  do { (r)->rb_parent_color &= ~1; } while (0)
132 #define rb_set_black(r)  do { (r)->rb_parent_color |= 1; } while (0)
133
134 static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
135 {
136     rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
137 }
138 static inline void rb_set_color(struct rb_node *rb, int color)
139 {
140     rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
141 }
142
143 #define RB_ROOT (struct rb_root) { NULL, }
144 #define rb_entry(ptr, type, member) container_of(ptr, type, member)
145
146 #define RB_EMPTY_ROOT(root)     ((root)->rb_node == NULL)
147 #define RB_EMPTY_NODE(node)     (rb_parent(node) != node)
148 #define RB_CLEAR_NODE(node)     (rb_set_parent(node, node))
149
150 extern void v3_rb_insert_color(struct rb_node *, struct rb_root *);
151 extern void v3_rb_erase(struct rb_node *, struct rb_root *);
152
153 /* Find logical next and previous nodes in a tree */
154 extern struct rb_node *v3_rb_next(struct rb_node *);
155 extern struct rb_node *v3_rb_prev(struct rb_node *);
156 extern struct rb_node *v3_rb_first(struct rb_root *);
157 extern struct rb_node *v3_rb_last(struct rb_root *);
158
159 /* Fast replacement of a single node without remove/rebalance/add/rebalance */
160 extern void v3_rb_replace_node(struct rb_node *victim, struct rb_node *new, 
161                             struct rb_root *root);
162
163 static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
164                                 struct rb_node ** rb_link)
165 {
166     node->rb_parent_color = (unsigned long )parent;
167     node->rb_left = node->rb_right = NULL;
168
169     *rb_link = node;
170 }
171
172 #define v3_rb_for_each_entry(pos, root, member)                         \
173     for (pos = rb_entry(v3_rb_first(root), typeof(*pos), member);       \
174          &pos->member != v3_rb_last(root);                              \
175          pos = rb_entry(v3_rb_next(&(pos->member)), typeof(*pos), member))
176
177
178 #endif
179
180 #endif  /* _LINUX_RBTREE_H */