1 /*
2  * Copyright (c) 2006-2020, RT-Thread Development Team
3  *
4  * SPDX-License-Identifier: Apache-2.0
5  *
6  * Change Logs:
7  * Date           Author       Notes
8  * 2019-10-12     Jesven       first version
9  * 2022-11-14     WangXiaoyao  Optimize for generic use case
10  *                             and performance
11  */
12 #ifndef __UTIL_TREE_AVL_H__
13 #define __UTIL_TREE_AVL_H__
14 
15 #include <rtdef.h>
16 #include <stdint.h>
17 
18 struct util_avl_struct
19 {
20     struct util_avl_struct *avl_left;
21     struct util_avl_struct *avl_right;
22     struct util_avl_struct *parent;
23     size_t height;
24 };
25 
26 #define AVL_ROOT ((struct util_avl_struct *)0)
27 
28 struct util_avl_root
29 {
30     struct util_avl_struct *root_node;
31 };
32 
33 void util_avl_rebalance(struct util_avl_struct *node,
34                         struct util_avl_root *root);
35 
36 void util_avl_remove(struct util_avl_struct *node, struct util_avl_root *root);
37 
util_avl_link(struct util_avl_struct * new_node,struct util_avl_struct * parent,struct util_avl_struct ** nodeplace)38 static inline void util_avl_link(struct util_avl_struct *new_node,
39                                  struct util_avl_struct *parent,
40                                  struct util_avl_struct **nodeplace)
41 {
42     new_node->avl_left = AVL_ROOT;
43     new_node->avl_right = AVL_ROOT;
44     new_node->parent = parent;
45     new_node->height = 1;
46     *nodeplace = new_node;
47 }
48 
util_avl_next(struct util_avl_struct * node)49 static inline struct util_avl_struct *util_avl_next(
50     struct util_avl_struct *node)
51 {
52     struct util_avl_struct *successor = 0;
53     if (node)
54     {
55         if (node->avl_right)
56         {
57             node = node->avl_right;
58             while (node->avl_left)
59                 node = node->avl_left;
60             successor = node;
61         }
62         else
63         {
64             while ((successor = node->parent) && (node == successor->avl_right))
65                 node = successor;
66         }
67     }
68     return successor;
69 }
70 
util_avl_prev(struct util_avl_struct * node)71 static inline struct util_avl_struct *util_avl_prev(
72     struct util_avl_struct *node)
73 {
74     struct util_avl_struct *predecessor = 0;
75     if (node)
76     {
77         if (node->avl_left)
78         {
79             node = node->avl_left;
80             while (node->avl_right)
81                 node = node->avl_right;
82             predecessor = node;
83         }
84         else
85         {
86             while ((predecessor = node->parent) &&
87                    (node == predecessor->avl_left))
88                 node = predecessor;
89         }
90     }
91     return predecessor;
92 }
93 
util_avl_first(struct util_avl_root * root)94 static inline struct util_avl_struct *util_avl_first(struct util_avl_root *root)
95 {
96     struct util_avl_struct *first = root->root_node;
97     if (first)
98     {
99         while (first->avl_left)
100             first = first->avl_left;
101     }
102     return first;
103 }
104 
util_avl_last(struct util_avl_root * root)105 static inline struct util_avl_struct *util_avl_last(struct util_avl_root *root)
106 {
107     struct util_avl_struct *last = root->root_node;
108     if (last)
109     {
110         while (last->avl_right)
111             last = last->avl_right;
112     }
113     return last;
114 }
115 
116 #endif /* __UTIL_TREE_AVL_H__ */
117