← Back to branch summary

~ubuntu-branches/ubuntu/precise/linux-lowlatency/precise

« back to all changes in this revision

Viewing changes to include/linux/prio_tree.h

  • Committer: Package Import Robot
  • Author(s): Alessio Igor Bogani
  • Date: 2011-10-26 11:13:05 UTC
  • Revision ID: package-import@ubuntu.com-20111026111305-tz023xykf0i6eosh
Tags: upstream-3.2.0
Import upstream version 3.2.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
include/linux/prio_tree.h
 
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 */