litmus-rt.git - The LITMUS^RT kernel.

The LITMUS^RT kernel.

Bjoern Brandenburg

about summary refs log tree commit diff stats

diff options

author	Luming Yu <luming.yu@intel.com>	2005-08-12 00:31:00 -0400
committer	Len Brown <len.brown@intel.com>	2005-08-15 15:46:58 -0400
commit	30e332f3307e9f7718490a706e5ce99f0d3a7b26 (patch)
tree	39054cfaf058a369f2b75bd89265e83522c02b49 /lib/parser.c
parent	d4ab025b73a2d10548e17765eb76f3b7351dc611 (diff)

[ACPI] re-enable platform-specific hotkey drivers by default

When both platform-specific and generic drivers exist, enable generic over-ride with "acpi_generic_hotkey". http://bugzilla.kernel.org/show_bug.cgi?id=4953 Signed-off-by: Luming Yu <luming.yu@intel.com> Signed-off-by: Len Brown <len.brown@intel.com>

Diffstat (limited to 'lib/parser.c')

0 files changed, 0 insertions, 0 deletions

ions * * Note - before using this, please consider if non-generic version * (interval_tree.h) would work for you... */ #define INTERVAL_TREE_DEFINE(ITSTRUCT, ITRB, ITTYPE, ITSUBTREE, \ ITSTART, ITLAST, ITSTATIC, ITPREFIX) \ \ /* Callbacks for augmented rbtree insert and remove */ \ \ static inline ITTYPE ITPREFIX ## _compute_subtree_last(ITSTRUCT *node) \ { \ ITTYPE max = ITLAST(node), subtree_last; \ if (node->ITRB.rb_left) { \ subtree_last = rb_entry(node->ITRB.rb_left, \ ITSTRUCT, ITRB)->ITSUBTREE; \ if (max < subtree_last) \ max = subtree_last; \ } \ if (node->ITRB.rb_right) { \ subtree_last = rb_entry(node->ITRB.rb_right, \ ITSTRUCT, ITRB)->ITSUBTREE; \ if (max < subtree_last) \ max = subtree_last; \ } \ return max; \ } \ \ RB_DECLARE_CALLBACKS(static, ITPREFIX ## _augment, ITSTRUCT, ITRB, \ ITTYPE, ITSUBTREE, ITPREFIX ## _compute_subtree_last) \ \ /* Insert / remove interval nodes from the tree */ \ \ ITSTATIC void ITPREFIX ## _insert(ITSTRUCT *node, struct rb_root *root) \ { \ struct rb_node **link = &root->rb_node, *rb_parent = NULL; \ ITTYPE start = ITSTART(node), last = ITLAST(node); \ ITSTRUCT *parent; \ \ while (*link) { \ rb_parent = *link; \ parent = rb_entry(rb_parent, ITSTRUCT, ITRB); \ if (parent->ITSUBTREE < last) \ parent->ITSUBTREE = last; \ if (start < ITSTART(parent)) \ link = &parent->ITRB.rb_left; \ else \ link = &parent->ITRB.rb_right; \ } \ \ node->ITSUBTREE = last; \ rb_link_node(&node->ITRB, rb_parent, link); \ rb_insert_augmented(&node->ITRB, root, &ITPREFIX ## _augment); \ } \ \ ITSTATIC void ITPREFIX ## _remove(ITSTRUCT *node, struct rb_root *root) \ { \ rb_erase_augmented(&node->ITRB, root, &ITPREFIX ## _augment); \ } \ \ /* \ * Iterate over intervals intersecting [start;last] \ * \ * Note that a node's interval intersects [start;last] iff: \ * Cond1: ITSTART(node) <= last \ * and \ * Cond2: start <= ITLAST(node) \ */ \ \ static ITSTRUCT * \ ITPREFIX ## _subtree_search(ITSTRUCT *node, ITTYPE start, ITTYPE last) \ { \ while (true) { \ /* \ * Loop invariant: start <= node->ITSUBTREE \ * (Cond2 is satisfied by one of the subtree nodes) \ */ \ if (node->ITRB.rb_left) { \ ITSTRUCT *left = rb_entry(node->ITRB.rb_left, \ ITSTRUCT, ITRB); \ if (start <= left->ITSUBTREE) { \ /* \ * Some nodes in left subtree satisfy Cond2. \ * Iterate to find the leftmost such node N. \ * If it also satisfies Cond1, that's the \ * match we are looking for. Otherwise, there \ * is no matching interval as nodes to the \ * right of N can't satisfy Cond1 either. \ */ \ node = left; \ continue; \ } \ } \ if (ITSTART(node) <= last) { /* Cond1 */ \ if (start <= ITLAST(node)) /* Cond2 */ \ return node; /* node is leftmost match */ \ if (node->ITRB.rb_right) { \ node = rb_entry(node->ITRB.rb_right, \ ITSTRUCT, ITRB); \ if (start <= node->ITSUBTREE) \ continue; \ } \ } \ return NULL; /* No match */ \ } \ } \ \ ITSTATIC ITSTRUCT * \ ITPREFIX ## _iter_first(struct rb_root *root, ITTYPE start, ITTYPE last) \ { \ ITSTRUCT *node; \ \ if (!root->rb_node) \ return NULL; \ node = rb_entry(root->rb_node, ITSTRUCT, ITRB); \ if (node->ITSUBTREE < start) \ return NULL; \ return ITPREFIX ## _subtree_search(node, start, last); \ } \ \ ITSTATIC ITSTRUCT * \ ITPREFIX ## _iter_next(ITSTRUCT *node, ITTYPE start, ITTYPE last) \ { \ struct rb_node *rb = node->ITRB.rb_right, *prev; \ \ while (true) { \ /* \ * Loop invariants: \ * Cond1: ITSTART(node) <= last \ * rb == node->ITRB.rb_right \ * \ * First, search right subtree if suitable \ */ \ if (rb) { \ ITSTRUCT *right = rb_entry(rb, ITSTRUCT, ITRB); \ if (start <= right->ITSUBTREE) \ return ITPREFIX ## _subtree_search(right, \ start, last); \ } \ \ /* Move up the tree until we come from a node's left child */ \ do { \ rb = rb_parent(&node->ITRB); \ if (!rb) \ return NULL; \ prev = &node->ITRB; \ node = rb_entry(rb, ITSTRUCT, ITRB); \ rb = node->ITRB.rb_right; \ } while (prev == rb); \ \ /* Check if the node intersects [start;last] */ \ if (last < ITSTART(node)) /* !Cond1 */ \ return NULL; \ else if (start <= ITLAST(node)) /* Cond2 */ \ return node; \ } \ }


context:
space:
mode: