1#ifndef _LINUX_PRIO_TREE_H 2#define _LINUX_PRIO_TREE_H 3 4struct prio_tree_node { 5 struct prio_tree_node *left; 6 struct prio_tree_node *right; 7 struct prio_tree_node *parent; 8}; 9 10struct prio_tree_root { 11 struct prio_tree_node *prio_tree_node; 12 unsigned int index_bits; 13}; 14 15struct prio_tree_iter { 16 struct prio_tree_node *cur; 17 unsigned long mask; 18 unsigned long value; 19 int size_level; 20 21 struct prio_tree_root *root; 22 pgoff_t r_index; 23 pgoff_t h_index; 24}; 25 26static inline void prio_tree_iter_init(struct prio_tree_iter *iter, 27 struct prio_tree_root *root, pgoff_t r_index, pgoff_t h_index) 28{ 29 iter->root = root; 30 iter->r_index = r_index; 31 iter->h_index = h_index; 32} 33 34#define INIT_PRIO_TREE_ROOT(ptr) \ 35do { \ 36 (ptr)->prio_tree_node = NULL; \ 37 (ptr)->index_bits = 1; \ 38} while (0) 39 40#define INIT_PRIO_TREE_NODE(ptr) \ 41do { \ 42 (ptr)->left = (ptr)->right = (ptr)->parent = (ptr); \ 43} while (0) 44 45#define INIT_PRIO_TREE_ITER(ptr) \ 46do { \ 47 (ptr)->cur = NULL; \ 48 (ptr)->mask = 0UL; \ 49 (ptr)->value = 0UL; \ 50 (ptr)->size_level = 0; \ 51} while (0) 52 53#define prio_tree_entry(ptr, type, member) \ 54 ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member))) 55 56static inline int prio_tree_empty(const struct prio_tree_root *root) 57{ 58 return root->prio_tree_node == NULL; 59} 60 61static inline int prio_tree_root(const struct prio_tree_node *node) 62{ 63 return node->parent == node; 64} 65 66static inline int prio_tree_left_empty(const struct prio_tree_node *node) 67{ 68 return node->left == node; 69} 70 71static inline int prio_tree_right_empty(const struct prio_tree_node *node) 72{ 73 return node->right == node; 74} 75 76#endif /* _LINUX_PRIO_TREE_H */ 77