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