Root/
1 | #ifndef _LINUX_PRIO_TREE_H |
2 | #define _LINUX_PRIO_TREE_H |
3 | |
4 | /* |
5 | * K&R 2nd ed. A8.3 somewhat obliquely hints that initial sequences of struct |
6 | * fields with identical types should end up at the same location. We'll use |
7 | * this until we can scrap struct raw_prio_tree_node. |
8 | * |
9 | * Note: all this could be done more elegantly by using unnamed union/struct |
10 | * fields. However, gcc 2.95.3 and apparently also gcc 3.0.4 don't support this |
11 | * language extension. |
12 | */ |
13 | |
14 | struct raw_prio_tree_node { |
15 | struct prio_tree_node *left; |
16 | struct prio_tree_node *right; |
17 | struct prio_tree_node *parent; |
18 | }; |
19 | |
20 | struct prio_tree_node { |
21 | struct prio_tree_node *left; |
22 | struct prio_tree_node *right; |
23 | struct prio_tree_node *parent; |
24 | unsigned long start; |
25 | unsigned long last; /* last location _in_ interval */ |
26 | }; |
27 | |
28 | struct prio_tree_root { |
29 | struct prio_tree_node *prio_tree_node; |
30 | unsigned short index_bits; |
31 | unsigned short raw; |
32 | /* |
33 | * 0: nodes are of type struct prio_tree_node |
34 | * 1: nodes are of type raw_prio_tree_node |
35 | */ |
36 | }; |
37 | |
38 | struct prio_tree_iter { |
39 | struct prio_tree_node *cur; |
40 | unsigned long mask; |
41 | unsigned long value; |
42 | int size_level; |
43 | |
44 | struct prio_tree_root *root; |
45 | pgoff_t r_index; |
46 | pgoff_t h_index; |
47 | }; |
48 | |
49 | static inline void prio_tree_iter_init(struct prio_tree_iter *iter, |
50 | struct prio_tree_root *root, pgoff_t r_index, pgoff_t h_index) |
51 | { |
52 | iter->root = root; |
53 | iter->r_index = r_index; |
54 | iter->h_index = h_index; |
55 | iter->cur = NULL; |
56 | } |
57 | |
58 | #define __INIT_PRIO_TREE_ROOT(ptr, _raw) \ |
59 | do { \ |
60 | (ptr)->prio_tree_node = NULL; \ |
61 | (ptr)->index_bits = 1; \ |
62 | (ptr)->raw = (_raw); \ |
63 | } while (0) |
64 | |
65 | #define INIT_PRIO_TREE_ROOT(ptr) __INIT_PRIO_TREE_ROOT(ptr, 0) |
66 | #define INIT_RAW_PRIO_TREE_ROOT(ptr) __INIT_PRIO_TREE_ROOT(ptr, 1) |
67 | |
68 | #define INIT_PRIO_TREE_NODE(ptr) \ |
69 | do { \ |
70 | (ptr)->left = (ptr)->right = (ptr)->parent = (ptr); \ |
71 | } while (0) |
72 | |
73 | #define INIT_PRIO_TREE_ITER(ptr) \ |
74 | do { \ |
75 | (ptr)->cur = NULL; \ |
76 | (ptr)->mask = 0UL; \ |
77 | (ptr)->value = 0UL; \ |
78 | (ptr)->size_level = 0; \ |
79 | } while (0) |
80 | |
81 | #define prio_tree_entry(ptr, type, member) \ |
82 | ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member))) |
83 | |
84 | static inline int prio_tree_empty(const struct prio_tree_root *root) |
85 | { |
86 | return root->prio_tree_node == NULL; |
87 | } |
88 | |
89 | static inline int prio_tree_root(const struct prio_tree_node *node) |
90 | { |
91 | return node->parent == node; |
92 | } |
93 | |
94 | static inline int prio_tree_left_empty(const struct prio_tree_node *node) |
95 | { |
96 | return node->left == node; |
97 | } |
98 | |
99 | static inline int prio_tree_right_empty(const struct prio_tree_node *node) |
100 | { |
101 | return node->right == node; |
102 | } |
103 | |
104 | |
105 | struct prio_tree_node *prio_tree_replace(struct prio_tree_root *root, |
106 | struct prio_tree_node *old, struct prio_tree_node *node); |
107 | struct prio_tree_node *prio_tree_insert(struct prio_tree_root *root, |
108 | struct prio_tree_node *node); |
109 | void prio_tree_remove(struct prio_tree_root *root, struct prio_tree_node *node); |
110 | struct prio_tree_node *prio_tree_next(struct prio_tree_iter *iter); |
111 | |
112 | #define raw_prio_tree_replace(root, old, node) \ |
113 | prio_tree_replace(root, (struct prio_tree_node *) (old), \ |
114 | (struct prio_tree_node *) (node)) |
115 | #define raw_prio_tree_insert(root, node) \ |
116 | prio_tree_insert(root, (struct prio_tree_node *) (node)) |
117 | #define raw_prio_tree_remove(root, node) \ |
118 | prio_tree_remove(root, (struct prio_tree_node *) (node)) |
119 | |
120 | #endif /* _LINUX_PRIO_TREE_H */ |
121 |
Branches:
ben-wpan
ben-wpan-stefan
javiroman/ks7010
jz-2.6.34
jz-2.6.34-rc5
jz-2.6.34-rc6
jz-2.6.34-rc7
jz-2.6.35
jz-2.6.36
jz-2.6.37
jz-2.6.38
jz-2.6.39
jz-3.0
jz-3.1
jz-3.11
jz-3.12
jz-3.13
jz-3.15
jz-3.16
jz-3.18-dt
jz-3.2
jz-3.3
jz-3.4
jz-3.5
jz-3.6
jz-3.6-rc2-pwm
jz-3.9
jz-3.9-clk
jz-3.9-rc8
jz47xx
jz47xx-2.6.38
master
Tags:
od-2011-09-04
od-2011-09-18
v2.6.34-rc5
v2.6.34-rc6
v2.6.34-rc7
v3.9