OpenCores
URL https://opencores.org/ocsvn/test_project/test_project/trunk

Subversion Repositories test_project

[/] [test_project/] [trunk/] [linux_sd_driver/] [include/] [linux/] [prio_tree.h] - Blame information for rev 81

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 62 marcus.erl
#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 */

powered by: WebSVN 2.1.0

© copyright 1999-2025 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.