ia64/xen-unstable

view xen/include/xen/rbtree.h @ 19800:78962f85c562

IOMMU: Add two generic functions to vendor neutral interface

Add 2 generic functions into the vendor neutral iommu interface, The
reason is that from changeset 19732, there is only one global flag
"iommu_enabled" that controls iommu enablement for both vtd and amd
systems, so we need different code paths for vtd and amd iommu systems
if this flag has been turned on. Also, the early checking of
"iommu_enabled" in iommu_setup() is removed to prevent iommu
functionalities from been disabled on amd systems.

Signed-off-by: Wei Wang <wei.wang2@amd.com>
author Keir Fraser <keir.fraser@citrix.com>
date Fri Jun 19 08:41:50 2009 +0100 (2009-06-19)
parents f210a633571c
children
line source
1 /*
2 Red Black Trees
3 (C) 1999 Andrea Arcangeli <andrea@suse.de>
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.
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.
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 */
20 #ifndef __RBTREE_H__
21 #define __RBTREE_H__
23 struct rb_node
24 {
25 unsigned long rb_parent_color;
26 #define RB_RED 0
27 #define RB_BLACK 1
28 struct rb_node *rb_right;
29 struct rb_node *rb_left;
30 };
32 struct rb_root
33 {
34 struct rb_node *rb_node;
35 };
37 #define rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3))
38 #define rb_color(r) ((r)->rb_parent_color & 1)
39 #define rb_is_red(r) (!rb_color(r))
40 #define rb_is_black(r) rb_color(r)
41 #define rb_set_red(r) do { (r)->rb_parent_color &= ~1; } while (0)
42 #define rb_set_black(r) do { (r)->rb_parent_color |= 1; } while (0)
44 static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
45 {
46 rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
47 }
48 static inline void rb_set_color(struct rb_node *rb, int color)
49 {
50 rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
51 }
53 #define RB_ROOT (struct rb_root) { NULL, }
54 #define rb_entry(ptr, type, member) container_of(ptr, type, member)
56 #define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL)
57 #define RB_EMPTY_NODE(node) (rb_parent(node) == node)
58 #define RB_CLEAR_NODE(node) (rb_set_parent(node, node))
60 extern void rb_insert_color(struct rb_node *, struct rb_root *);
61 extern void rb_erase(struct rb_node *, struct rb_root *);
63 /* Find logical next and previous nodes in a tree */
64 extern struct rb_node *rb_next(struct rb_node *);
65 extern struct rb_node *rb_prev(struct rb_node *);
66 extern struct rb_node *rb_first(struct rb_root *);
67 extern struct rb_node *rb_last(struct rb_root *);
69 /* Fast replacement of a single node without remove/rebalance/add/rebalance */
70 extern void rb_replace_node(struct rb_node *victim, struct rb_node *new,
71 struct rb_root *root);
73 static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
74 struct rb_node ** rb_link)
75 {
76 node->rb_parent_color = (unsigned long )parent;
77 node->rb_left = node->rb_right = NULL;
79 *rb_link = node;
80 }
82 #endif /* __RBTREE_H__ */