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.


Merge branch 'devel' of palacios@newskysaw.cs.northwestern.edu:/home/palacios/palacio...
[palacios.git] / palacios / src / palacios / vmm_rbtree.c
1 /*
2   Red Black Trees
3   (C) 1999  Andrea Arcangeli <andrea@suse.de>
4   (C) 2002  David Woodhouse <dwmw2@infradead.org>
5   
6   This program is free software; you can redistribute it and/or modify
7   it under the terms of the GNU General Public License as published by
8   the Free Software Foundation; either version 2 of the License, or
9   (at your option) any later version.
10
11   This program is distributed in the hope that it will be useful,
12   but WITHOUT ANY WARRANTY; without even the implied warranty of
13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14   GNU General Public License for more details.
15
16   You should have received a copy of the GNU General Public License
17   along with this program; if not, write to the Free Software
18   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
19
20   linux/lib/rbtree.c
21 */
22
23 #include <palacios/vmm_rbtree.h>
24
25
26 static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
27 {
28     struct rb_node *right = node->rb_right;
29     struct rb_node *parent = rb_parent(node);
30
31     if ((node->rb_right = right->rb_left))
32         rb_set_parent(right->rb_left, node);
33     right->rb_left = node;
34
35     rb_set_parent(right, parent);
36
37     if (parent)
38         {
39             if (node == parent->rb_left)
40                 parent->rb_left = right;
41             else
42                 parent->rb_right = right;
43         }
44     else
45         root->rb_node = right;
46     rb_set_parent(node, right);
47 }
48
49 static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
50 {
51     struct rb_node * left = node->rb_left;
52     struct rb_node * parent = rb_parent(node);
53
54     if ((node->rb_left = left->rb_right)) {
55         rb_set_parent(left->rb_right, node);
56     }
57
58     left->rb_right = node;
59
60     rb_set_parent(left, parent);
61
62     if (parent) {
63         if (node == parent->rb_right) {
64             parent->rb_right = left;
65         } else { 
66             parent->rb_left = left;
67         }
68     } else {
69         root->rb_node = left;
70     }
71
72     rb_set_parent(node, left);
73 }
74
75 void v3_rb_insert_color(struct rb_node *node, struct rb_root *root)
76 {
77     struct rb_node *parent, *gparent;
78
79     while ((parent = rb_parent(node)) && rb_is_red(parent))
80         {
81             gparent = rb_parent(parent);
82
83             if (parent == gparent->rb_left)
84                 {
85                     {
86                         register struct rb_node *uncle = gparent->rb_right;
87                         if (uncle && rb_is_red(uncle))
88                             {
89                                 rb_set_black(uncle);
90                                 rb_set_black(parent);
91                                 rb_set_red(gparent);
92                                 node = gparent;
93                                 continue;
94                             }
95                     }
96
97                     if (parent->rb_right == node)
98                         {
99                             register struct rb_node *tmp;
100                             __rb_rotate_left(parent, root);
101                             tmp = parent;
102                             parent = node;
103                             node = tmp;
104                         }
105
106                     rb_set_black(parent);
107                     rb_set_red(gparent);
108                     __rb_rotate_right(gparent, root);
109                 } else {
110                 {
111                     register struct rb_node *uncle = gparent->rb_left;
112                     if (uncle && rb_is_red(uncle))
113                         {
114                             rb_set_black(uncle);
115                             rb_set_black(parent);
116                             rb_set_red(gparent);
117                             node = gparent;
118                             continue;
119                         }
120                 }
121
122                 if (parent->rb_left == node)
123                     {
124                         register struct rb_node *tmp;
125                         __rb_rotate_right(parent, root);
126                         tmp = parent;
127                         parent = node;
128                         node = tmp;
129                     }
130
131                 rb_set_black(parent);
132                 rb_set_red(gparent);
133                 __rb_rotate_left(gparent, root);
134             }
135         }
136
137     rb_set_black(root->rb_node);
138 }
139
140
141 static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
142                              struct rb_root *root)
143 {
144     struct rb_node *other;
145
146     while ((!node || rb_is_black(node)) && node != root->rb_node)
147         {
148             if (parent->rb_left == node)
149                 {
150                     other = parent->rb_right;
151                     if (rb_is_red(other))
152                         {
153                             rb_set_black(other);
154                             rb_set_red(parent);
155                             __rb_rotate_left(parent, root);
156                             other = parent->rb_right;
157                         }
158                     if ((!other->rb_left || rb_is_black(other->rb_left)) &&
159                         (!other->rb_right || rb_is_black(other->rb_right)))
160                         {
161                             rb_set_red(other);
162                             node = parent;
163                             parent = rb_parent(node);
164                         }
165                     else
166                         {
167                             if (!other->rb_right || rb_is_black(other->rb_right))
168                                 {
169                                     struct rb_node *o_left;
170                                     if ((o_left = other->rb_left))
171                                         rb_set_black(o_left);
172                                     rb_set_red(other);
173                                     __rb_rotate_right(other, root);
174                                     other = parent->rb_right;
175                                 }
176                             rb_set_color(other, rb_color(parent));
177                             rb_set_black(parent);
178                             if (other->rb_right)
179                                 rb_set_black(other->rb_right);
180                             __rb_rotate_left(parent, root);
181                             node = root->rb_node;
182                             break;
183                         }
184                 }
185             else
186                 {
187                     other = parent->rb_left;
188                     if (rb_is_red(other))
189                         {
190                             rb_set_black(other);
191                             rb_set_red(parent);
192                             __rb_rotate_right(parent, root);
193                             other = parent->rb_left;
194                         }
195                     if ((!other->rb_left || rb_is_black(other->rb_left)) &&
196                         (!other->rb_right || rb_is_black(other->rb_right)))
197                         {
198                             rb_set_red(other);
199                             node = parent;
200                             parent = rb_parent(node);
201                         }
202                     else
203                         {
204                             if (!other->rb_left || rb_is_black(other->rb_left))
205                                 {
206                                     register struct rb_node *o_right;
207                                     if ((o_right = other->rb_right))
208                                         rb_set_black(o_right);
209                                     rb_set_red(other);
210                                     __rb_rotate_left(other, root);
211                                     other = parent->rb_left;
212                                 }
213                             rb_set_color(other, rb_color(parent));
214                             rb_set_black(parent);
215                             if (other->rb_left)
216                                 rb_set_black(other->rb_left);
217                             __rb_rotate_right(parent, root);
218                             node = root->rb_node;
219                             break;
220                         }
221                 }
222         }
223     if (node)
224         rb_set_black(node);
225 }
226
227 void v3_rb_erase(struct rb_node *node, struct rb_root *root)
228 {
229     struct rb_node *child, *parent;
230     int color;
231
232     if (!node->rb_left)
233         child = node->rb_right;
234     else if (!node->rb_right)
235         child = node->rb_left;
236     else
237         {
238             struct rb_node *old = node, *left;
239
240             node = node->rb_right;
241             while ((left = node->rb_left) != NULL)
242                 node = left;
243             child = node->rb_right;
244             parent = rb_parent(node);
245             color = rb_color(node);
246
247             if (child)
248                 rb_set_parent(child, parent);
249             if (parent == old) {
250                 parent->rb_right = child;
251                 parent = node;
252             } else
253                 parent->rb_left = child;
254
255             node->rb_parent_color = old->rb_parent_color;
256             node->rb_right = old->rb_right;
257             node->rb_left = old->rb_left;
258
259             if (rb_parent(old))
260                 {
261                     if (rb_parent(old)->rb_left == old)
262                         rb_parent(old)->rb_left = node;
263                     else
264                         rb_parent(old)->rb_right = node;
265                 } else
266                 root->rb_node = node;
267
268             rb_set_parent(old->rb_left, node);
269             if (old->rb_right)
270                 rb_set_parent(old->rb_right, node);
271             goto color;
272         }
273
274     parent = rb_parent(node);
275     color = rb_color(node);
276
277     if (child)
278         rb_set_parent(child, parent);
279     if (parent)
280         {
281             if (parent->rb_left == node)
282                 parent->rb_left = child;
283             else
284                 parent->rb_right = child;
285         }
286     else
287         root->rb_node = child;
288
289  color:
290     if (color == RB_BLACK)
291         __rb_erase_color(child, parent, root);
292 }
293
294
295 /*
296  * This function returns the first node (in sort order) of the tree.
297  */
298 struct rb_node *v3_rb_first(struct rb_root *root)
299 {
300     struct rb_node      *n;
301
302     n = root->rb_node;
303     if (!n)
304         return NULL;
305     while (n->rb_left)
306         n = n->rb_left;
307     return n;
308 }
309
310
311 struct rb_node *v3_rb_last(struct rb_root *root)
312 {
313     struct rb_node      *n;
314
315     n = root->rb_node;
316     if (!n)
317         return NULL;
318     while (n->rb_right)
319         n = n->rb_right;
320     return n;
321 }
322
323
324 struct rb_node *v3_rb_next(struct rb_node *node)
325 {
326     struct rb_node *parent;
327
328     /* If we have a right-hand child, go down and then left as far
329        as we can. */
330     if (node->rb_right) {
331         node = node->rb_right; 
332         while (node->rb_left)
333             node=node->rb_left;
334         return node;
335     }
336
337     /* No right-hand children.  Everything down and left is
338        smaller than us, so any 'next' node must be in the general
339        direction of our parent. Go up the tree; any time the
340        ancestor is a right-hand child of its parent, keep going
341        up. First time it's a left-hand child of its parent, said
342        parent is our 'next' node. */
343     while ((parent = rb_parent(node)) && node == parent->rb_right)
344         node = parent;
345
346     return parent;
347 }
348
349
350 struct rb_node *v3_rb_prev(struct rb_node *node)
351 {
352     struct rb_node *parent;
353
354     /* If we have a left-hand child, go down and then right as far
355        as we can. */
356     if (node->rb_left) {
357         node = node->rb_left; 
358         while (node->rb_right)
359             node=node->rb_right;
360         return node;
361     }
362
363     /* No left-hand children. Go up till we find an ancestor which
364        is a right-hand child of its parent */
365     while ((parent = rb_parent(node)) && node == parent->rb_left)
366         node = parent;
367
368     return parent;
369 }
370
371
372 void v3_rb_replace_node(struct rb_node *victim, struct rb_node *new,
373                         struct rb_root *root)
374 {
375     struct rb_node *parent = rb_parent(victim);
376
377     /* Set the surrounding nodes to point to the replacement */
378     if (parent) {
379         if (victim == parent->rb_left)
380             parent->rb_left = new;
381         else
382             parent->rb_right = new;
383     } else {
384         root->rb_node = new;
385     }
386     if (victim->rb_left)
387         rb_set_parent(victim->rb_left, new);
388     if (victim->rb_right)
389         rb_set_parent(victim->rb_right, new);
390
391     /* Copy the pointers/colour from the victim to the replacement */
392     *new = *victim;
393 }
394