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